= Weighted graph
{wiki}
An edge-weighted <graph> assigns a numerical weight to each <graph edge>. The meaning depends on the model: a weight can be a length, a cost, or an <electrical conductance>. Arbitrary weights do not automatically define <transition probabilities>.
For the <random walk> convention used here, take a locally finite undirected <graph> with symmetric nonnegative <electrical conductances> $c_{xy}=c_{yx}$, and optional nonnegative killing weights $\kappa_x$. Assume
$$
0<\mu_x=\kappa_x+\sum_y c_{xy}<\infty.
$$
The <Markov chain> moves from $x$ to $y$ with <probability> $c_{xy}/\mu_x$ and goes to a cemetery state with <probability> $\kappa_x/\mu_x$. These <probabilities> sum to one. With no killing, <detailed balance> holds with respect to the <measure> $\mu$; normalization gives a <stationary distribution> when its total mass is finite.
For example, <electrical conductances> $1$ and $3$ on the two <edges> incident to an <graph vertex> give outgoing <probabilities> $1/4$ and $3/4$. Treating the same weights as <electrical resistances> would require reciprocal <electrical conductances> and reverse these preferences. The distinction is essential in the <electrical network> interpretation.
Back to article page
