Trees and Forests for Nonequilibrium Purposes: An Introduction to Graphical Representations

Abstract

Using local detailed balance we rewrite the Kirchhoff formula for stationary distributions of Markov jump processes in terms of a physically interpretable tree-ensemble. We use that arborification of path-space integration to derive a McLennan-tree characterization close to equilibrium, as well as to obtain response formula for the stationary distribution in the asymptotic regime of large driving. Graphical expressions of currents and of traffic are obtained, allowing the study of various asymptotic regimes. Finally, we present how the matrix-forest theorem gives a representation of quasi-potentials, as used e.g. for computing excess work and heat in nonequilibrium thermal physics. A variety of examples illustrate and explain the graph elements and constructions.

Appendices

Appendix A: More on Deriving the McLennan Formula

The first point is that by expanding w(x) up to linear order in $\varepsilon$,

$$\begin{aligned} \dfrac{\rho _{\varepsilon }^s(x)}{\rho ^s_0(x)}=1+\frac{\varepsilon }{2} \left( \dfrac{\sum _{{\mathcal {T}}}\omega _{0}({\mathcal {T}}_x) S^{1}({\mathcal {T}}_x)}{w_0(x)}-\dfrac{\sum _y\sum _{{\mathcal {T}}} \omega _{0}({\mathcal {T}}_y)S^{1}({\mathcal {T}}_y)}{\sum _y w_0(y)}\right) + O(\varepsilon ^2) \end{aligned}$$

(A.1)

and using  2.5,

$$\begin{aligned} \dfrac{\sum _y\sum _{{\mathcal {T}}}\omega _{0}({\mathcal {T}}_y) S^{1}({\mathcal {T}}_y)}{\sum _y w_0(y)}&=\dfrac{\sum _y\sum _{{\mathcal {T}}} \frac{k_{\mathrm{eq}}(x,y)}{k_{\mathrm{eq}}(y,x)}\omega _{0}({\mathcal {T}}_x) S^1({\mathcal {T}}_x)}{\sum _y \frac{k_{\mathrm{eq}}(x,y)}{k_{\mathrm{eq}}(y,x)}w_0(x)} +2\dfrac{\sum _y\sum _{{\mathcal {T}}}\omega _{0}({\mathcal {T}}_y) S^1_{{\mathcal {T}}}(y\rightarrow x)}{W_0}\\&=\dfrac{\sum _{{\mathcal {T}}}\omega _{0}({\mathcal {T}}_x) S^1({\mathcal {T}}_x)}{w_0(x)} +2\sum _y\frac{w_0(y)}{W_0} \sum _{{\mathcal {T}}}\dfrac{\omega _{0}({\mathcal {T}}_y) S^1_{{\mathcal {T}}}(y\rightarrow x)}{w_0(y)} \end{aligned}$$

We now get

$$\begin{aligned} L_{\mathrm{eq}}\left( \frac{\rho ^s_\varepsilon }{\rho ^s_0}-1 \right) =\varepsilon \,\left( \sum _z k_{\mathrm{eq}}(x,z)\dfrac{\sum _{{\mathcal {T}}} \omega _{\mathrm{eq}}({\mathcal {T}}_{x})S^1_{{\mathcal {T}}} (x\rightarrow z))}{w_{\mathrm{eq}}(x)}\right) \end{aligned}$$

for the action of the equilibrium backward generator $L_{\mathrm{eq}}$.

Appendix B: Proof of the Current Formulas

We need two lemmas.

Lemma B.1

Let ${\mathcal {T}}^G$ as a set of all spanning trees in graph ${\mathcal {G}}$ which is a loop and hairs,and ${\mathcal {T}}^{\ell }$ as a set of all spanning trees on the loop $\ell$. Then for every vertex x on the loop

$$\begin{aligned} \forall \tau ^G\in {\mathcal {T}}^G; \quad \exists ! \tau ^{\ell } \in {\mathcal {T}}^{\ell } ; \quad w(\tau ^G_x)=w(\tau ^{\ell }_x)W(H_{\ell }) \end{aligned}$$

Where $\tau ^G_x$ is a spanning tree on the graph ${\mathcal {G}}$ towards x, $\tau ^{\ell }_x$ is a spanning tree in the loop $\ell$ towards x and $W(H_{\ell })$is the weight of all hairs towards the loop.

The point of that lemma is that the weights of spanning trees (toward x located on the loop) have a common term W(H) which does not depend on x.

Proof

Let $\tau ^G$ be a spanning tree in the graph ${\mathcal {G}}$. It contains all vertices of ${\mathcal {G}}$, on hairs and loop. The hairs themselves are trees, so that the set of edges of $\tau ^G$ includes all edges on the hairs E(H) and

$$\begin{aligned} E(\tau ^{\ell })=E(\tau ^G)\setminus E(H) \end{aligned}$$

with, for every $x\in {\mathcal {V}}(\ell )$,

$$\begin{aligned} w(\tau _x^{\ell })=\dfrac{w(\tau _x ^G)}{W(H)} \end{aligned}$$

$\square$

Lemma B.2

For every x and $y\in {\mathcal {V}}(\ell )$,

$$\begin{aligned} \sum _{\tau ^{\ell }}\left( w(\tau ^{\ell }_x)k(x,y)-w(\tau ^{\ell }_y)k(y,x)\right) =w(\ell ^{x\rightarrow y})-w(\ell ^{y\rightarrow x}) \end{aligned}$$

Proof

Let ${\mathcal {T}}^{\ell }_x$ be the set of all spanning trees on the loop $\ell$ toward x. ${\mathcal {T}}^{\ell }_x = A_1 \cup A_2$ can be split into two subsets

$$\begin{aligned} \quad A_1:=\{\tau ^{\ell } _x; (y,x)\in \tau ^{\ell } _x\}, \qquad A_2:=\{\tau ^{\ell }_x; (y,x)\notin \tau ^{\ell } _x\} \end{aligned}$$

where $\tau ^{\ell }_x\in {\mathcal {T}}^{\ell }_x$. Similarly, ${\mathcal {T}}^{\ell }_y$ is the set of all spanning trees toward y on the loop and

$$\begin{aligned} {\mathcal {T}}^{\ell }_y = B_1 \cup B_2; \quad B_1:=\{\tau ^{\ell } _y; (x,y)\in \tau ^{\ell } _y\}; \quad B_2:=\{\tau ^{\ell }_y; (x,y)\notin \tau ^{\ell } _y\} \end{aligned}$$

$\tau _x$ is a tree towards x so it does not have the edge (x, y) which is leaving the vertex x. $\tau _y$ also does not have the edge (y, x). So then

$$\begin{aligned} \forall \tau ^{\ell }_x \in A_1 \quad \tau ^{\ell }_x\setminus (y,x) \cup (x,y)\in B_1 \end{aligned}$$

so that

$$\begin{aligned} \exists \tau ^{\ell }_y\in B_1; \quad \tau ^{\ell }_y =\tau ^{\ell }_x\setminus (y,x) \cup (x,y) \end{aligned}$$

In other words

$$\begin{aligned} w(\tau ^{\ell }_x\setminus (y,x) \cup (x,y))=w(\tau ^{\ell }_x) \times \frac{k(x,y)}{k(y,x)}=w(\tau ^{\ell }_y) \end{aligned}$$

and

$$\begin{aligned} \forall \tau ^{\ell }_y \in B_1 \quad \tau ^{\ell }_y\setminus (x,y) \cup (y,x)\in A_1 \end{aligned}$$

so that

$$\begin{aligned} \exists \tau ^{\ell }_x\in A_1; \quad \tau ^{\ell }_x =\tau ^{\ell }_y\setminus (x,y) \cup (y,x) \end{aligned}$$

which means

$$\begin{aligned} w(\tau ^{\ell }_y\setminus (x,y) \cup (y,x))=w(\tau ^{\ell }_y) \times \frac{k(y,x)}{k(x,y)}=w(\tau ^{\ell }_x) \end{aligned}$$

Hence

$$\begin{aligned} \sum _{\tau \in A_1}w(\tau _x)k(x,y)=\sum _{\tau \in B_1} w(\tau _y)k(y,x) \end{aligned}$$

(B.1)

On the other hand

$$\begin{aligned}&\forall \tau ^{\ell }_x \in A_2 \quad \tau ^{\ell }_x\cup (x,y)= \ell ^{x\rightarrow y}\\&\forall \tau ^{\ell }_y \in B_2 \quad \tau ^{\ell }_y\cup (y,x)= \ell ^{y\rightarrow x} \end{aligned}$$

so then

$$\begin{aligned} w(A_2)k(x,y)=w(\ell ^{x\rightarrow y}); \quad w(B_2)k(y,x) =w(\ell ^{y\rightarrow x}) \end{aligned}$$

(B.2)

Now for every x and y on the loop

$$\begin{aligned} \sum _{\tau ^{\ell }}\left( w(\tau ^{\ell }_x)k(x,y)-w(\tau ^{\ell }_y)k(y,x)\right)&= \sum _{\tau ^{\ell }}w(\tau ^{\ell }_x)k(x,y)-\sum _{\tau ^{\ell }}w(\tau ^{\ell }_y)k(y,x)\\&=\left( \sum _{\tau ^{\ell }\in A_1}w(\tau ^{\ell }_x)k(x,y)-\sum _{\tau ^{\ell }\in B_1} w(\tau ^{\ell }_y)k(y,x)\right) \\&\quad +\left( \sum _{\tau ^{\ell }\in A_2}w(\tau ^{\ell }_x)k(x,y) -\sum _{\tau ^{\ell }\in B_2}w(\tau ^{\ell }_y)k(y,x)\right) \\&=w(\ell ^{x\rightarrow y})-w(\ell ^{y\rightarrow x}) \end{aligned}$$

Where in the second line we used B.1 and in the last line we used B.2. $\square$

Next we prove formula 4.3.

Proof

Consider on the graph ${\mathcal {G}}$ for every x and y on the loop

$$\begin{aligned} j(x,y)&=\rho ^s(x)k(x,y)-\rho ^s(y)k(y,x)\\&=\frac{w(x)}{W}k(x,y) -\frac{w(y)}{W}k(y,x) \end{aligned}$$

where

$$\begin{aligned} w(x)=\sum _{\tau ^G}\prod _{(z,z')\in \tau ^G_x}k(z,z')=\sum _{\tau ^G}w(\tau ^G_x) \end{aligned}$$

From Lemma B.1

$$\begin{aligned} w(x)= W(H)\sum _{\tau ^{\ell }}w(\tau ^{\ell }_x) \end{aligned}$$

In the same way

$$\begin{aligned} w(y)= W(H)\sum _{\tau ^{\ell }}w(\tau ^{\ell }_y) \end{aligned}$$

so then

$$\begin{aligned} j(x,y)&=\frac{W(H)}{W}\sum _{\tau ^{\ell }}\left( w(\tau ^{\ell }_x) k(x,y)-w(\tau ^{\ell }_y)k(y,x)\right) \end{aligned}$$

From the Lemma B.2 the relation (4.3) has been proved. $\square$

We need another lemma to prove the general formula (4.7).

Lemma B.3

Consider a spanning tree ${\mathcal {T}}$ in the connected graph ${\mathcal {G}}$. If the edge $\{x,y\}$ is in the graph but is not in the spanning tree, then by adding the edge $\{x,y\}$ to the spanning tree one loop is created.

Proof

There is a path between x and y in the spanning tree ${\mathcal {T}}$. The edge $\{x,y\}$ is a second path between vertices x and y. If we have more than one path between two vertices in a graph then we have a loop.

Imagine a general connected graph ${\mathcal {G}}$ in which the edge $\{x,y\}$ belongs to more than one loop. Corresponding to the edge $\{x,y\}$, the set of all spanning trees ${\mathcal {T}} ^{G}$ can be split into two sets. The set denoted by $T^{xy}$ is a set of trees including the edge $\{x,y\}$, while the set denoted by $T^{c}$ is not including the edge $\{x,y\}$. In (B.1) it is shown that

$$\begin{aligned} \sum _{{\mathcal {T}}\in T^{xy}} \big (w({\mathcal {T}}_x)k(x,y) -w({\mathcal {T}}_y)k(y,x)\big )=0 \end{aligned}$$

Notice that in the lemma we considered all spanning trees on a loop but the result of (B.1) is the same for every spanning tree.

We focus on the set which does not include the edge $\{x,y\}$. By adding the edge $\{x,y\}$ to the set $T^{c}$, a loop including this edge is created (Lemma B.3). For every tree of $T^{c}$, by adding this edge, a loop with a structure of hairs appears. In other words,

$$\begin{aligned} w(x)k(x,y)=\sum _{{\mathcal {T}}\in T^{c}}w({\mathcal {T}}_x)k(x,y) =\sum _{\ell _{xy}}\sum _{H_{\ell _{xy}}}w(\ell _{xy})w(H_{\ell _{xy}}) \end{aligned}$$

where $\ell _{xy}$ is a loop in the graph ${\mathcal {G}}$ including the edge $\{x,y\}$ and $H_{\ell _{xy}}$ is one possible structure of hairs connected to the loop $\ell _{xy}$. From here and the relation (4.3), the general formula (4.7) is proved. $\square$