Kirchhoff determinant and Markov chain tree

This post is devoted to the Gustav Kirchhoff formula which expresses the invariant measure of an irreducible finite Markov chain in terms of spanning trees. Many of us have already encountered the name of Gustav Kirchhoff in Physics classes when studying electricity.

Let ${X={(X_t)}_{t\geq0}}$ be a continuous time Markov chain with finite state space ${V=\{1,\ldots,n\}}$, and with infinitesimal generator or Q-matrix ${Q}$, meaning that

$$Q_{i,j}=\partial_{t=0^+}\mathbb{P}(X_t=j|X_0=i), \quad \mathbb{P}(X_t=j|X_0=i)=\left(e^{tQ}\right)_{i,j}.$$

The off-diagonal entries of ${Q}$ are non-negative and the rows of ${Q}$ have zero sum:

$$\forall i,j\in V, \quad i\neq j, \quad Q_{i,j}\geq0, \quad Q_{i,i}=-\sum_{k\neq i}Q_{i,k}.$$

The skeleton graph ${G=(V,E)}$ of ${Q}$ is the oriented graph defined by

$$(i,j)\in E\quad\mathrm{iff}\quad Q_{i,j}>0.$$

Let us assume that ${Q}$ is irreducible, which means that ${G}$ is connected. The Perron-Frobenius theorem states then that there exists a unique invariant probability measure, in other words ${\mathrm{ker}(Q^\top)}$ contains up to scaling a unique vector with positive coordinates. We will provide an explicit formula for it!

Since the sum of the columns of ${Q}$ is zero, it follows that for every ${i,j\in V}$,

$$(\mathrm{cof}(-Q))_{i,j}:=(-1)^{i+j}\det(-Q^{(i,j)})=\det(-Q^{(i,i)})=:\mu_i.$$

In other words the cofactors matrix of ${-Q}$ has constant rows (identical columns). Now by expanding the determinant along an arbitrary column ${j\in V}$ we get

$$0=\det(-Q)=-\sum_{i=1}^nQ_{i,j}(-1)^{i+j}\det(-Q^{(i,j)}) =-\sum_{i\in V}Q_{i,j}\mu_i$$

which shows that the vector ${{(\mu_i)}_{i\in V}}$ is invariant for ${Q}$. The fact that ${{(\mu_i)}_{i\in V}}$ has positive coordinates follows from the Kirchhoff formula

$$\mu_i:=\det(-Q^{(i,i)})=\sum_{T\in\mathcal{T}_i}\prod_{(j,k)\in T}Q_{j,k}$$

where the sum runs over the set ${\mathcal{T}_i}$ of spanning trees of ${G}$ rooted at ${i}$. Recall that a spanning tree or covering tree of ${G}$ rooted at ${i\in V}$ is a sub-graph of ${G}$ with edge set ${V}$ which is a tree rooted at ${i}$. Note that ${\mathcal{T}_i}$ is non-empty since ${G}$ is connected. Note that ${\mathcal{T}_1,\ldots,\mathcal{T}_n}$ do not have necessarily the same cardinal due to the fact that the edges are oriented: a covering tree rooted at ${i}$ contains any ${j}$ as a vertex but not necessarily as a possible root due to the arrows.

To prove the Kirchhoff formula, one can first label from ${1}$ to ${m=|E|}$ the edges of ${G}$, and define an ${n\times m}$ matrix ${L}$ called the incidence matrix as follows: if ${(i,j)}$ is the ${k}$-th edge of ${G}$ then ${L_{i,k}=Q_{i,j}^{1/2}}$, ${L_{j,k}=-Q_{i,j}^{1/2}}$, and ${L_{\cdot,k}=0}$ otherwise. Now

$$-Q=LL^\top.$$

We also have ${Q^{(i,i)}=L^{(i)}(L^{(i)})^\top}$. Next we use the Cauchy-Binet formula

$$\det(-Q^{(i,i)}) =\sum_{s}\det(L^{(i,s)})^2$$

where ${s}$ runs over the subsets of cardinality ${m-(n-1)}$. Every ${s}$ specifies ${n-1}$ edges of ${G}$. It can then be shown that these edges induce a spanning tree iif ${\det(L^{(i,s)})\neq0}$.

Random walk. Suppose now that ${Q_{i,j}\in\{0,1\}}$ for every ${i,j\in V}$ with ${i\neq j}$. Then ${X}$ is the nearest neighbors random walk on ${G}$, the diagonal of ${-Q}$ is formed by the degree sequence of ${G}$, and ${Q}$ is the Laplacian ${\Delta_G}$ of ${G}$. In this case ${Q_{j,k}=1}$ for every ${(j,k)\in G}$ and thus the Kirchhoff formula above boils down to

$$\forall i\in V,\quad \mu_i=|\mathcal{T}_i|.$$

Suppose now that ${Q}$ is additionally symmetric, meaning that ${G}$ is not oriented in the sense that ${(j,k)\in E}$ iff ${(k,j)\in E}$. In this case the invariant probability measure of ${Q}$ is then the uniform law on ${V}$. Due to the absence of orientation, the sets ${\mathcal{T}_1,\ldots,\mathcal{T}_n}$ have the same cardinal ${\kappa}$, which is the number of spanning trees of ${G}$ (without rooting). We have

$$\forall i,j\in V,\quad \mu_i=(\mathrm{cof}(-Q))_{i,j}=(-1)^{i+j}\det(-Q^{(i,j)}) =|\mathcal{T}|_i=\kappa.$$

In other words the cofactors matrix of the Laplacian of a non-oriented graph has constant entries equal to the number of spanning trees of the graph.

Let us connect ${\kappa}$ with the eigenvalues of the the symmetric matrix ${-Q}$, numbered as

$$0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_n.$$

Here ${\lambda_1}$ is simple since ${Q}$ is irreducible. The characteristic polynomial of ${-Q}$ is

$$P_{-Q}(x)=\det(xI_n+Q)=x(x-\lambda_2)\cdots(x-\lambda_n).$$

By looking at the coefficient of ${x}$ in this polynomial we get (Jacobi formula)

$$(-1)^{n-1}\lambda_2\cdots\lambda_n =(-1)^{n-1}\mathrm{Tr}(\mathrm{cof}(-Q))$$

which gives finally the remarkable Kirchhoff formula

$$\lambda_2\cdots\lambda_n=n\kappa.$$

(note that the left hand side is thus necessarily an integer!). Let us show how to recover from this formula the so-called Cayley formula which states that the complete graph ${K_n}$ possesses ${n^{n-2}}$ covering trees. In this case ${G=K_n}$ and ${-Q=nI-J}$ where ${J}$ is the ${n\times n}$ matrix full of ${1}$. The matrix ${-J}$ has rank ${1}$, its eigenvalues are ${0}$ with multiplicity ${n-1}$ and ${-n}$ with multiplicity ${1}$, and thus it follows that the eigenvalues of ${-Q}$ are ${0}$ with multiplicity ${1}$ and ${n}$ with multiplicity ${n-1}$. Hence ${\lambda_2=\cdots=\lambda_n=n}$ and finally ${\kappa=n^{n-2}}$.

Wilson algorithm. David Wilson invented an exact algorithm to generate a spanning tree of ${G}$ which follows the uniform distribution on the set of spanning trees of ${G}$. Starting from vertex ${1}$, the algorithm consists in setting ${A_1=\{1\}}$, and to simulate a path of the simple random walk on ${G}$ started from vertex ${2}$ until it reaches ${A_1}$. Then ${A_2}$ is the union of ${A_1}$ and of the loop erased version of this path. If ${A_2=V}$, the algorithm is stopped. If not, then we redo the same starting this time the path from smallest vertex not in ${A_2}$, stopping the path when it reaches ${A_2}$, and so on. The Wilson algorithm can be naturally related to the Green function of the random walk on ${G}$ with Dirichlet boundary conditions on a subset of ${V}$.

Markov matrix tree theorem. The Kirchhoff formula provides an exact and non-asymptotic formula for the invariant probability measure of a finite Markov chain (this is sometimes referred to as the Kirchhoff Markov matrix tree theorem). This is remarkable, and constitutes an alternative to the asymptotic formula

$$\forall i,j\in V,\quad \mu_j=\left(\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{k=0}^{m-1} e^{kQ}\right)_{i,j}.$$

Further reading.

• Lyons and Peres, Probability on trees and networks (chapter 4)
• Leighton and Rivest, Estimating a probability using finite memory
• Anantharam and Tsoucas, A proof of the Markov chain tree theorem
• Biane, Polynomials associated with finite Markov chains
• Biane and Chapuy, Laplacian Matrices and Spanning Trees of Tree Graphs
• Rosenthal - A note on Kirchhoff formula and Wilson algorithm
• Harris and Hirst and Mossinghoff, Combinatorics and graph theory