Transition Operators for Random Walks on Graphs

From a Graph to a Random Walk

A graph specifies which moves are possible; transition probabilities specify how likely each move is. Once both are given, the walk can be studied through an operator that averages a function over the possible next positions. Iterating this operator records the effect of taking several steps.

Local finiteness is useful here: each vertex has only finitely many neighbors, so the one-step average is a finite sum. We will define the operator first for general transition probabilities, then see how edge weights give a standard family of examples.

Transition Probabilities and the Operator

Let $G=(V,E)$ be a countable, undirected, locally finite graph. Thus every vertex $x\in V$ has finitely many neighbors, denoted by $N(x)$. A transition kernel $q$ assigns a number $q(x,y)$ to every ordered pair $x,y\in V$, with each row giving a probability distribution and with transitions restricted to the graph.

Definition: A transition kernel on $G$ satisfies $q(x,y)\geq 0$, $\sum_{y\in V}q(x,y)=1$ for every $x\in V$, and $q(x,y)=0$ unless $y=x$ or $y\in N(x)$. A random walk with transition kernel $q$, started at $x$, has one-step transition probabilities $q(x,y)$.

The option $y=x$ permits a holding step. If holding is not part of the model, set $q(x,x)=0$. For a function $f:V\to\mathbb R$, the transition operator averages its values at the possible next vertices.

Definition: The transition operator $P$ acts on $f:V\to\mathbb R$ by $$ (Pf)(x)=\sum_{y\in V}q(x,y)f(y). $$ The sum is finite because transitions from $x$ are possible only to $x$ and its finitely many neighbors.

In particular, $Pf(x)$ is the one-step conditional average of $f$ when the current vertex is $x$. The operator is linear: for functions $f,g$ and scalars $a,b$, finite-sum algebra gives $P(af+bg)=aPf+bPg$. Also $P\mathbf 1=\mathbf 1$, where $\mathbf 1(x)=1$, because each row of $q$ sums to one.

When $f$ is bounded, the operator preserves boundedness and cannot increase the supremum norm $\|f\|_\infty=\sup_{x\in V}|f(x)|$.

Theorem: If $f$ is bounded, then $Pf$ is bounded and $\|Pf\|_\infty\leq \|f\|_\infty$.

Proof. For every $x$, nonnegativity and the row-sum condition give $$ |(Pf)(x)| \leq \sum_{y\in V}q(x,y)|f(y)| \leq \|f\|_\infty\sum_{y\in V}q(x,y) =\|f\|_\infty. $$ Taking the supremum over $x$ proves both boundedness and the claimed inequality. $\square$

Weighted and Unweighted Walks

A common way to choose transition probabilities is to assign positive weights to edges. For each undirected edge $\{x,y\}\in E$, let $c_{xy}=c_{yx}>0$ be its conductance. Define the weighted degree $c(x)=\sum_{y\in N(x)}c_{xy}$. At a vertex with at least one neighbor, choose the next vertex with probability proportional to the conductance of the connecting edge.

Definition: The conductance random walk has $$ q(x,y)=\frac{c_{xy}}{c(x)} \quad (y\in N(x)),\qquad q(x,y)=0 \quad (y\notin N(x)). $$ If the graph has an isolated vertex $x$, take $q(x,x)=1$ there.

For an unweighted graph, take $c_{xy}=1$ on every edge. Then $c(x)=|N(x)|$, the degree of $x$, and the walk chooses each neighbor with probability $1/|N(x)|$. In either case, the operator is an average over neighbors, but the weights in that average depend on the transition rule.

Worked Example: An Unweighted Path

Consider the path with vertices $0,1,2$ and edges $\{0,1\}$ and $\{1,2\}$. In the unweighted walk, the endpoints have only one possible next vertex, while the middle vertex chooses between its two neighbors. Thus $$ (Pf)(0)=f(1),\qquad (Pf)(1)=\frac{f(0)+f(2)}{2},\qquad (Pf)(2)=f(1). $$ For $f(0)=2,\ f(1)=5,\ f(2)=-1$, this gives $Pf(0)=5$, $Pf(1)=(2-1)/2=1/2$, and $Pf(2)=5$. The endpoint values are not averages over two neighbors: each endpoint has just one possible move.

Worked Example: A Weighted Path

Use the same path, but assign conductance $2$ to $\{0,1\}$ and conductance $1$ to $\{1,2\}$. The weighted degrees are $c(0)=2$, $c(1)=3$, and $c(2)=1$. Consequently, $$ q(0,1)=1,\qquad q(1,0)=\frac{2}{3},\qquad q(1,2)=\frac{1}{3},\qquad q(2,1)=1. $$ For any $f$, $$ (Pf)(0)=f(1),\qquad (Pf)(1)=\frac{2}{3}f(0)+\frac{1}{3}f(2),\qquad (Pf)(2)=f(1). $$ With $f(0)=1,\ f(1)=4,\ f(2)=7$, we obtain $Pf(0)=4$, $Pf(1)=2/3+7/3=3$, and $Pf(2)=4$. The middle value gives twice as much weight to vertex $0$ as to vertex $2$, exactly reflecting the conductances.

Operator Powers and Multi-Step Probabilities

Write $P^0f=f$ and $P^{n+1}f=P(P^nf)$ for integers $n\geq 0$. The $n$-step transition probability $q_n(x,y)$ is the probability that a walk started at $x$ is at $y$ after $n$ steps; $q_0(x,y)$ is $1$ when $x=y$ and $0$ otherwise. The relation between these probabilities and the operator powers follows from the one-step transition rule.

Theorem: For every bounded $f:V\to\mathbb R$, every $x\in V$, and every integer $n\geq 0$, $$ (P^nf)(x)=\sum_{y\in V}q_n(x,y)f(y). $$ In particular, $q_n(x,y)=(P^n\mathbf 1_{\{y\}})(x)$, where $\mathbf 1_{\{y\}}$ is $1$ at $y$ and $0$ elsewhere.

Proof. We use induction on $n$. When $n=0$, the right-hand side is $f(x)$, by the definition of $q_0$, and this equals $(P^0f)(x)$. Suppose the formula holds for $n$. Applying the one-step operator and then the induction hypothesis gives $$ (P^{n+1}f)(x) =\sum_{z\in V}q(x,z)(P^nf)(z) =\sum_{z\in V}q(x,z)\sum_{y\in V}q_n(z,y)f(y). $$ For fixed $x$, only finitely many $z$ have $q(x,z)>0$. For each such $z$, only finitely many $y$ are reachable in $n$ steps, since the graph is locally finite. We may therefore rearrange these finite sums: $$ (P^{n+1}f)(x) =\sum_{y\in V}\left(\sum_{z\in V}q(x,z)q_n(z,y)\right)f(y). $$ Conditioning on the first step shows that the parenthesized sum is $q_{n+1}(x,y)$. This proves the formula at $n+1$, completing the induction. Taking $f=\mathbf 1_{\{y\}}$ gives the stated identity for $q_n(x,y)$. $\square$

Equivalently, the multi-step transition probabilities obey the Chapman–Kolmogorov recursion $q_{n+1}(x,y)=\sum_z q(x,z)q_n(z,y)$. For any fixed starting vertex and finite $n$, only finitely many vertices can be reached in $n$ steps, so these sums are finite. The recursion composes one-step probabilities; it does not say that the probability of a particular $n$-step route is the whole $n$-step probability. One must sum over all routes that reach the destination.

Worked Example: Two Steps on the Weighted Path

Return to the path with conductances $2$ and $1$. From vertex $0$, the first step must go to $1$. From $1$, the next step goes to $0$ with probability $2/3$ and to $2$ with probability $1/3$. Therefore, $$ q_2(0,0)=\frac{2}{3},\qquad q_2(0,1)=0,\qquad q_2(0,2)=\frac{1}{3}. $$ From $1$, the first step goes to $0$ or $2$, and either of those vertices must then return to $1$. Hence $q_2(1,1)=1$, with $q_2(1,0)=q_2(1,2)=0$. By the same reasoning as for a walk started at $0$, $q_2(2,0)=2/3$ and $q_2(2,2)=1/3$. In vertex order $0,1,2$, the two-step matrix is $$ \begin{pmatrix} 2/3&0&1/3\\ 0&1&0\\ 2/3&0&1/3 \end{pmatrix}. $$ Each row sums to $1$, as required for a transition probability distribution. For example, $P^2f(0)=\frac23 f(0)+\frac13 f(2)$, which agrees with the two-step distribution just computed.

Worked Example: Two Steps on an Unweighted Triangle

Let the vertices of a triangle be $0,1,2$, with every pair joined by an edge. Each vertex has two neighbors, so from any vertex the walk moves to either other vertex with probability $1/2$. From $0$, a two-step return requires moving first to $1$ or $2$, then back to $0$. Each route has probability $(1/2)(1/2)=1/4$, so $q_2(0,0)=1/2$. To end at $1$, the walk must use either route $0\to2\to1$ or $0\to1\to1$; the latter is impossible because there is no holding step. Thus $q_2(0,1)=1/4$. Similarly $q_2(0,2)=1/4$. Symmetry gives the same pattern from each starting vertex: $$ q_2(x,x)=\frac12,\qquad q_2(x,y)=\frac14\quad (y\ne x). $$ For a check using an operator, take $f(0)=1,\ f(1)=2,\ f(2)=4$. The two-step average from $0$ is $(1/2)f(0)+(1/4)f(1)+(1/4)f(2)=2$. Directly, $Pf(1)=5/2$ and $Pf(2)=3/2$, so $P^2f(0)=(Pf(1)+Pf(2))/2=2$ as well.

What the Operator Makes Visible

The operator viewpoint separates the rule for one move from the particular quantity being tracked. To find expected values after $n$ steps, apply $P^n$ to the function of interest. To find the probability of being at a specified vertex $y$, apply $P^n$ to its indicator function. This is often more efficient than listing paths individually, especially when the same transition rule must be applied repeatedly.

A common mistake is to treat the transition matrix as symmetric merely because the underlying graph is undirected. In the weighted path above, the probability of moving from $0$ to $1$ is $1$, but the probability of moving from $1$ to $0$ is $2/3$. The edge has the same conductance in both directions, yet transition probabilities are normalized by the weighted degree of the starting vertex. The transition matrix is therefore generally not symmetric.

Another useful check is that every row of a transition matrix sums to one, and every row of its $n$-step transition matrix also sums to one. This follows because each row describes a probability distribution. In computations, a row sum different from one can signal a missing route, an incorrect normalization, or an arithmetic error.

Check Your Understanding

Use the definitions and computations above to answer these questions.

Why does local finiteness ensure that $Pf(x)$ is a finite sum?
On an unweighted graph, what is the transition probability from a vertex $x$ to a particular neighbor $y$?
For the weighted path with conductances $2$ and $1$, calculate $P^2f(1)$ for an arbitrary function $f$.
How can $q_n(x,y)$ be obtained by applying an operator power to a function?
Why can an undirected graph have a transition matrix that is not symmetric?