= Random walk on a multigraph
For a loopless undirected <multigraph>, let $m_{xy}=m_{yx}$ be the number of parallel <graph edges> between distinct <graph vertices> $x,y$. Assume $0<d(x)=\sum_y m_{xy}<\infty$. Choosing an incident <edge> uniformly gives the <transition probabilities>
$$
P(x,y)=\frac{m_{xy}}{d(x)}.
$$
The <measure> $d$ is reversible since $d(x)P(x,y)=m_{xy}=d(y)P(y,x)$. It becomes a <stationary distribution> $\pi(x)=d(x)/\sum_zd(z)$ only when the total <vertex degree> is finite. On a finite <graph> this holds; on an infinite <locally finite graph>, a reversible <measure> need not be a normalizable <probability measure>. Self-loops need a stated incidence-counting convention and are excluded from the formula here.
For example, two parallel <edges> from $a$ to $b$ and one <edge> from $b$ to $c$ give <vertex degree>[degrees] $(2,3,1)$, <stationary distribution>[stationary probabilities] $(1/3,1/2,1/6)$, and $P(b,a)=2/3$. Collapsing the parallel <edges> to a single unweighted <edge> would change the <random walk>.
Back to article page