[proofplan] We verify reversibility by checking the detailed balance equations directly for the unnormalised candidate measure $\lambda_i = d_i$, where $d_i$ is the degree of vertex $i$. For non-adjacent vertices both sides vanish; for adjacent vertices the transition probabilities $p_{i,j} = 1/d_i$ cause both sides to equal $1$. The [Detailed Balance Implies Unique Invariance](/theorems/2228) theorem then gives that $\lambda$ is the unique invariant measure up to normalisation. Normalising using the handshaking lemma $\sum_{i \in V} d_i = 2|E|$ yields $\pi_i = d_i / (2|E|)$. [/proofplan] [step:Verify the detailed balance equations for $\lambda_i = d_i$] Define the candidate measure $\lambda_i = d_i$ for each $i \in V$. We verify the detailed balance equations $\lambda_i p_{i,j} = \lambda_j p_{j,i}$ for all pairs $i, j \in V$ by considering two cases. **Case 1: $\{i,j\} \notin E$.** Then $p_{i,j} = 0$ and $p_{j,i} = 0$ by the definition of the simple random walk, so $\lambda_i p_{i,j} = 0 = \lambda_j p_{j,i}$. **Case 2: $\{i,j\} \in E$.** Then $p_{i,j} = 1/d_i$ and $p_{j,i} = 1/d_j$, so \begin{align*} \lambda_i p_{i,j} = d_i \cdot \frac{1}{d_i} = 1 = d_j \cdot \frac{1}{d_j} = \lambda_j p_{j,i}. \end{align*} In both cases, $\lambda_i p_{i,j} = \lambda_j p_{j,i}$. Hence $(P, \lambda)$ is in detailed balance. [guided] The detailed balance equations require $\lambda_i p_{i,j} = \lambda_j p_{j,i}$ for every pair of states $i, j$. The candidate $\lambda_i = d_i$ is motivated by the structure of the transition matrix: since $p_{i,j} = 1/d_i$ for neighbours, the product $\lambda_i p_{i,j} = d_i \cdot (1/d_i)$ eliminates the degree entirely, leaving $1$ on both sides. This is the key observation that makes the degree measure natural for the simple random walk. We check both cases systematically. **Case 1: $\{i,j\} \notin E$.** By the definition of the simple random walk on a graph, $p_{i,j} = 0$ when $\{i,j\}$ is not an edge, and similarly $p_{j,i} = 0$. Therefore $\lambda_i p_{i,j} = d_i \cdot 0 = 0 = d_j \cdot 0 = \lambda_j p_{j,i}$. **Case 2: $\{i,j\} \in E$.** In this case, $p_{i,j} = 1/d_i$ (the walk moves to each neighbour with equal probability $1/d_i$) and $p_{j,i} = 1/d_j$. Computing each side: \begin{align*} \lambda_i p_{i,j} = d_i \cdot \frac{1}{d_i} = 1, \qquad \lambda_j p_{j,i} = d_j \cdot \frac{1}{d_j} = 1. \end{align*} Both sides equal $1$, so the equation holds. Why does this argument depend on the graph being undirected? Because we used the fact that $\{i,j\} \in E$ implies both $p_{i,j} > 0$ and $p_{j,i} > 0$ with the specific values $1/d_i$ and $1/d_j$. In a directed graph, having an edge from $i$ to $j$ does not guarantee an edge from $j$ to $i$, so $p_{i,j}$ and $p_{j,i}$ may differ in structure, and the degree-based cancellation breaks down. [/guided] [/step] [step:Apply the detailed balance theorem to obtain uniqueness and reversibility] The simple random walk on a connected finite graph $G = (V, E)$ is irreducible: for any $i, j \in V$, connectivity of $G$ provides a path $i = v_0, v_1, \ldots, v_m = j$ with $\{v_{k-1}, v_k\} \in E$ for each $k$, so $p_{i,j}(m) \geq \prod_{k=1}^{m} p_{v_{k-1}, v_k} > 0$, whence $i \to j$. Since $\lambda_i = d_i > 0$ for all $i \in V$ (every vertex in a connected graph has at least one neighbour) and $(P, \lambda)$ is in detailed balance, the [Detailed Balance Implies Unique Invariance](/theorems/2228) theorem applies: $\lambda$ is the unique invariant measure up to normalisation, and the chain is reversible. [guided] Before applying the [Detailed Balance Implies Unique Invariance](/theorems/2228) theorem, we must verify its hypotheses: (i) $P$ is the transition matrix of an irreducible Markov chain, and (ii) $(P, \lambda)$ is in detailed balance for some distribution $\lambda$. For (i): the state space is $V$, which is finite. The chain is irreducible because $G$ is connected. To see this, take any $i, j \in V$. Connectivity of $G$ guarantees a path of edges $i = v_0, v_1, \ldots, v_m = j$, and along this path each transition has positive probability: $p_{v_{k-1}, v_k} = 1/d_{v_{k-1}} > 0$. By the [Chapman--Kolmogorov Equations](/theorems/2207), $p_{i,j}(m) \geq \prod_{k=1}^{m} p_{v_{k-1}, v_k} > 0$, so $i \to j$. Since this holds for all $i, j$, the chain is irreducible. For (ii): we verified in the previous step that $\lambda_i p_{i,j} = \lambda_j p_{j,i}$ for all $i, j \in V$, with $\lambda_i = d_i$. Note that $\lambda_i = d_i \geq 1 > 0$ for every $i \in V$ since every vertex in a connected graph has at least one neighbour (if some vertex had degree $0$, it would be isolated, contradicting connectivity). Both hypotheses are satisfied, so the theorem gives: $\lambda$ is the unique invariant measure (up to scalar multiples), and the chain is reversible when started in the corresponding normalised distribution. Since $V$ is finite and the chain is irreducible, finiteness automatically gives positive recurrence by the [Recurrence in Finite State Spaces](/theorems/2215) theorem. The detailed balance theorem provides uniqueness and reversibility in one step. [/guided] [/step] [step:Normalise the degree measure to obtain $\pi_i = d_i / (2|E|)$] The invariant measure $\lambda_i = d_i$ must be normalised to a probability distribution. Compute the total mass: \begin{align*} \sum_{i \in V} d_i = 2|E|, \end{align*} since each edge $\{i,j\} \in E$ contributes exactly $1$ to $d_i$ and exactly $1$ to $d_j$, so the sum counts each edge twice. The unique invariant distribution is therefore \begin{align*} \pi_i = \frac{\lambda_i}{\sum_{j \in V} \lambda_j} = \frac{d_i}{2|E|} \quad \text{for each } i \in V. \end{align*} [guided] The measure $\lambda_i = d_i$ satisfies detailed balance, but it is not yet a probability distribution: $\sum_{i \in V} \lambda_i$ need not equal $1$. To normalise, we must compute $\sum_{i \in V} d_i$. Each edge $\{i,j\} \in E$ is an unordered pair. In the sum $\sum_{i \in V} d_i$, the edge $\{i,j\}$ is counted once in $d_i$ (as a neighbour of $i$) and once in $d_j$ (as a neighbour of $j$), for a total contribution of $2$. Summing over all $|E|$ edges gives \begin{align*} \sum_{i \in V} d_i = 2|E|. \end{align*} This identity is the handshaking lemma from graph theory. Dividing each $\lambda_i$ by the total mass $2|E|$ yields the invariant distribution: \begin{align*} \pi_i = \frac{d_i}{2|E|} \quad \text{for each } i \in V. \end{align*} We verify that this is indeed a probability distribution: each $\pi_i = d_i / (2|E|) > 0$ (since $d_i \geq 1$ in a connected graph), and $\sum_{i \in V} \pi_i = \sum_{i \in V} d_i / (2|E|) = 2|E| / (2|E|) = 1$. The result has an appealing interpretation: in equilibrium, the fraction of time the random walk spends at vertex $i$ is proportional to its degree. Vertices with more neighbours are visited more frequently, with the precise weight given by the degree divided by twice the number of edges. [/guided] [/step]