# Optimal Model-Free Mean-Square Consensus for Multi-Agents with Markov Switching Topology
## 2 Preliminaries  
### Algebraic Graph Theory  
Envision a multi-agent system consisting of \(N\) agents, with each agent depicted as a node and their interactions as edges connecting these nodes. A directed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})\) is composed of a node set \(\mathcal{V}=\{v_{1},v_{2},\ldots,v_{N}\}\), an edge set \(\mathcal{E}=\{e_{ij}=(v_{i},v_{j})\}\subseteq\mathcal{V}\times\mathcal{V}\), and a weighted adjacency matrix \(\mathcal{A}=[a_{ij}]\) with non-negative adjacency elements \(a_{ij}\geqslant 0\), where \(a_{ij}>0\) if and only if \(e_{ji}=(v_{j},v_{i})\in\mathcal{E}\), which represents that agent \(i\) is enabled to obtain the information from agent \(j\); otherwise, \(a_{ij}=0\). For \(\forall i=1,2,\ldots,N\), \(a_{ii}=0\). Furthermore, define a leader node (denoted as node \(0\)), and introduce a pinning matrix \(\mathcal{B}=diag\{b_{1},b_{2},\ldots,b_{N}\}\) to characterize the interaction between followers and the leader node, with \(b_{i}~{}=~{}1\) indicating that node \(i\) is adjacent to the leader; otherwise, \(b_{i}~{}=~{}0\). \(\mathcal{N}_{i}=\{j:(v_{j},v_{i})\in\mathcal{E}\}\) denotes the set of neighbors of node \(v_{i}\). The in-degree matrix \(\mathcal{D}\) is written as \(\mathcal{D}=diag\{d_{i}\}\) with \(d_{i}=\sum_{j\in\mathcal{N}_{i}}a_{ij}\). The digraph Laplacian matrix \(\mathcal{L}=[l_{ij}]\in\mathbb{R}^{N\times N}\) may be obtained via \(\mathcal{L}=\mathcal{D}-\mathcal{A}\). A directed path from node \(v_{i}\) to node \(v_{j}\) means that there exists a sequence of edges \((v_{i},v_{k1}),(v_{k1},v_{k2}),\ldots,(v_{km},v_{j})\) in \(\mathcal{E}\). A directed path connecting any node to the root of a digraph is present if the digraph has a directed spanning tree.  
Assume a time-varying communication topology \(\mathcal{G}(k)~{}=~{}(\mathcal{V},\mathcal{E}(k),\mathcal{A}(k))\), which is Markovian switching. The adjacency matrix and edge set of \(\mathcal{G}(k)\) are denoted by \(\mathcal{A}(k)\) and \(\mathcal{E}(k)\), respectively. \(\{\sigma(k),~{}k\in\mathbb{N}^{+}\}\) is an ergodic homogeneous Markovian chain whose state space is \(\mathcal{F}~{}=~{}\{1,2,\ldots,f\}\), where \(f\in\mathbb{N}^{+}\). Then, \(\mathcal{G}(k)=\mathcal{G}_{\sigma(k)}\) can be used to represent the communication graph at time \(k\). \(\mathcal{G}(k)~{}=~{}\mathcal{G}_{\tau}\) if and only if \(\sigma(k)~{}=~{}\tau\), where a finite set \(\{\mathcal{G}_{1},\mathcal{G}_{2},\ldots,\mathcal{G}_{f}\}\) is employed to represent all possible topologies. To convey the union of all conceivable topologies, \(\mathcal{G}_{\text{un}}\) is expressed as \(\mathcal{G}_{\text{un}}~{}=~{}\bigcup_{\tau\in\mathcal{F}}\mathcal{G}_{\tau}\). \(P~{}=~{}[P_{ji}]\) is the transition probability matrix of \(\sigma(k)\), with the element \(P_{\tau_{1}\tau_{2}}~{}=~{}Pr\{\sigma(k+1)~{}=~{}\tau_{2}|\sigma(k)~{}=~{}\tau_ {1}\}\), \(\forall\tau_{1},\tau_{2}\in\mathcal{F}\); that is, \(P_{\tau_{1}\tau_{2}}\) indicates the probability of moving from the \(\tau_{1}\)-th topological structure to the \(\tau_{2}\)-th topological structure. Obviously, \(\sum_{\tau_{2}=1}^{f}P_{\tau_{1}\tau_{2}}~{}=~{}1,\forall\tau_{1}\in\mathcal{F}\).  
**Assumption 1**.: _For the Markovian switching topologies, the graph \(\mathcal{G}_{\text{un}}\) contains a directed spanning tree, where the leader is the root node._