Lagmental Vicfred

Simple Random Walk Is Reversible with Degree Weights by Vicfred

tags: mathematics, spectral graph theory, random walks, electrical networks

On a finite undirected graph, stationary probability is proportional to vertex degree. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

Notation

The graph Laplacian \(L=D-A\) is positive semidefinite and turns combinatorial connectivity into linear algebra. A random walk uses \(P=D^{-1}A\) when degrees are positive.

$$ P_{uv}=\begin{cases}1/d_u,&\{u,v\}\in E,\\0,&\text{otherwise},\end{cases} $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ \pi_v=\frac{d_v}{2|E|},\qquad\pi_uP_{uv}=\pi_vP_{vu} $$

Stress the formula

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ \frac{d_u}{2|E|}\frac1{d_u}=\frac1{2|E|}=\frac{d_v}{2|E|}\frac1{d_v} $$

Interpretation

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad P_{uv}=\begin{cases}1/d_u,&\{u,v\}\in E,\\0,&\text{otherwise},\end{cases},\\[5pt] \mathsf{C}\;&:\quad \pi_v=\frac{d_v}{2|E|},\qquad\pi_uP_{uv}=\pi_vP_{vu}. \end{aligned} $$

Limit of the argument

Normalized and unnormalized Laplacians have different eigenvalues and orthogonality measures. Formulas must state which one is being used.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \pi_v=\frac{d_v}{2|E|},\qquad\pi_uP_{uv}=\pi_vP_{vu} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Tue 27 June 2023. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.