From a Graph to a Probability Calculation
On a finite graph, several descriptions of a random walk fit together: transition probabilities give first-step equations, those equations are discrete boundary-value problems, and the expected number of visits before reaching the boundary is encoded by a Green matrix. Conductances also let us interpret the boundary-value solution as an electrical voltage.
This workshop develops those connections by solving concrete problems. The main discipline is to keep three objects distinct: the graph’s conductances, the transition probabilities obtained by normalizing them, and the boundary conditions that specify the event or occupation quantity of interest.
Finite Weighted Graphs and Their Walks
Let \((X_n)_{n\ge 0}\) denote this walk, and let \(\mathbb P_x\) and \(\mathbb E_x\) denote probability and expectation when \(X_0=x\). For a nonempty set \(B\subseteq V\), define its first hitting time by
The time convention matters: if \(x\in B\), then \(\tau_B=0\). In particular, a walk started on the boundary has already hit it.
For \(A\subseteq B\), the function \(h(x)=\mathbb P_x(X_{\tau_B}\in A)\) is prescribed to equal \(1\) on \(A\) and \(0\) on \(B\setminus A\). At an interior vertex, conditioning on the first step gives
This is a discrete Dirichlet problem: the boundary values are fixed, and the function is harmonic at every vertex outside the boundary.
Worked Example: A Path with Two Boundary Vertices
Worked Example: A Path with Two Boundary Vertices
Take the path \(0-1-2-3\), with conductances \(c_{01}=2\), \(c_{12}=1\), and \(c_{23}=3\). Let \(B=\{0,3\}\), and ask for the probability of hitting \(3\) before \(0\). Put \(h(0)=0\) and \(h(3)=1\). The total conductances at vertices \(1\) and \(2\) are \(3\) and \(4\), respectively, so the first-step equations are
Substitute the first equation into the second: \(h(2)=\bigl(h(2)/3+3\bigr)/4\), hence \(4h(2)=h(2)/3+3\), so \(11h(2)/3=3\) and \(h(2)=9/11\). Thus \(h(1)=3/11\). Starting at \(1\), the probability of hitting \(3\) before \(0\) is \(3/11\).
There is also an electrical check. The edge resistances are \(1/2,1,1/3\), so their series resistance is \(11/6\). With voltage \(0\) at \(0\) and \(1\) at \(3\), the voltage at \(1\) is the fraction \((1/2)/(11/6)=3/11\) of the total voltage, and at \(2\) it is \((1/2+1)/(11/6)=9/11\). These agree with the hitting probabilities.
Why the Boundary-Value Solution Is the Hitting Probability
Proof. First, the walk hits \(B\) almost surely. If \(V\) has one vertex, nonemptiness forces \(B=V\), and \(\tau_B=0\). Otherwise, for each \(x\notin B\), connectedness gives a path from \(x\) to \(B\) of length at most \(|V|-1\). The probability of following that particular path is positive, since every edge transition has positive probability. Taking the minimum of these probabilities over the finite set \(V\setminus B\) gives some \(\varepsilon_0>0\). Set \(m=\max(1,|V|-1)\). From any vertex outside \(B\), the probability of hitting \(B\) within the next \(m\) steps is at least \(\varepsilon_0\). The Markov property then gives \(\mathbb P_x(\tau_B>km)\le (1-\varepsilon_0)^k\) for every \(k\in\mathbb N\). Therefore \(\tau_B<\infty\) almost surely.
Now define \(h(x)=\mathbb P_x(X_{\tau_B}\in A)\). On \(B\), it has the required values. For \(x\notin B\), conditioning on \(X_1\) gives \(h(x)=\sum_yP(x,y)h(y)\).
For uniqueness, suppose \(f\) is harmonic on \(V\setminus B\) and zero on \(B\). If \(f\) has a positive maximum, it is attained at an interior vertex \(x\). Since \(f(x)\) is a weighted average of its neighboring values, all neighbors must have that same maximum value. Repeating along a path from \(x\) to \(B\) forces a boundary vertex to have a positive value, a contradiction. Applying the same argument to \(-f\) rules out a negative minimum. Thus \(f=0\), proving uniqueness. The difference of any two solutions has these properties, so the solution is unique. \(\square\)
The maximum argument also explains why checking the equations at every interior vertex is decisive: on a finite connected graph, boundary values cannot be supplemented by a different harmonic solution.
Killed Green Functions Count Visits
The hitting probability records where the walk first reaches \(B\). A different question asks how often it visits each interior vertex before that time. Write \(D=V\setminus B\), and define the killed Green function by
The sum counts visits at times \(0,1,\ldots,\tau_B-1\), excluding the boundary hit itself. Let \(Q\) be the matrix indexed by \(D\) with entries \(Q(x,y)=P(x,y)\). It records transitions that remain in the interior; its row sums can be less than one because a step may enter \(B\).
Proof. The geometric bound in the preceding proof implies that \(\tau_B\) has finite expectation: grouping its tail into blocks of length \(m\) bounds the tail probabilities by a geometric sequence. Hence each expected visit count is finite. For \(x,y\in D\), the Markov property gives \((Q^n)(x,y)=\mathbb P_x(X_n=y,\ n<\tau_B)\), by induction on \(n\). Summing over \(n\ge0\) therefore gives \(G_B(x,y)\). The same geometric tail bound shows that the entries of \(Q^n\) tend to zero. For every \(N\), $$ (I-Q)\sum_{n=0}^{N}Q^n=I-Q^{N+1}. $$ Taking \(N\) to infinity yields \((I-Q)G_B=I\). Since these are finite square matrices, a right inverse is also an inverse, so \(G_B=(I-Q)^{-1}\), and the series also gives \(G_B=I+QG_B\). \(\square\)
Worked Example: Occupation Counts Before Either Endpoint
Worked Example: Occupation Counts Before Either Endpoint
Use the path \(0-1-2-3\) with conductances \(2,1,3\), and stop on \(B=\{0,3\}\). On \(D=\{1,2\}\), the transition from \(1\) goes to \(2\) with probability \(1/3\), while the transition from \(2\) goes to \(1\) with probability \(1/4\). Thus
The determinant of \(I-Q\) is \(1-1/12=11/12\), giving
For verification, the first row of \((I-Q)G_B\) is \((12/11-1/11,\ 4/11-4/11)=(1,0)\). The second row is \((-12/44+3/11,\ -4/44+12/11)=(0,1)\). Thus the matrix is indeed the inverse. Starting at \(2\), the expected number of visits to \(1\) before hitting \(B\) is \(G_B(2,1)=3/11\), and the expected number of visits to \(2\), including the initial visit, is \(G_B(2,2)=12/11\). The expected number of steps before hitting \(B\) is their sum, \(15/11\), because every pre-hit step begins at one of the two interior vertices.
Worked Example: A Two-Route Network
Worked Example: A Two-Route Network
Consider vertices \(s,a,b,t\) with edges and conductances \(c_{sa}=2\), \(c_{at}=1\), \(c_{sb}=1\), \(c_{bt}=2\), and \(c_{ab}=1\). Let \(B=\{s,t\}\), and set \(h(s)=0\), \(h(t)=1\). Both \(a\) and \(b\) have total conductance \(4\). Their first-step equations are
The first equation gives \(h(b)=4h(a)-1\). Substitution in the second gives \(4(4h(a)-1)=h(a)+2\), so \(15h(a)=6\), \(h(a)=2/5\), and \(h(b)=3/5\). Direct substitution verifies both equations: \(4(2/5)=3/5+1\) and \(4(3/5)=2/5+2\). Therefore, starting at \(a\), the probability of hitting \(t\) before \(s\) is \(2/5\).
To find the effective resistance, impose voltage \(0\) at \(s\) and \(1\) at \(t\); the harmonic voltages at \(a,b\) are exactly \(2/5,3/5\). The current entering the network at \(s\) is \(2(2/5)+1(3/5)=7/5\). A unit voltage difference therefore produces effective conductance \(7/5\), and the effective resistance is \(5/7\). The energy provides an independent check: the sum of \(c_{xy}(h(x)-h(y))^2\) over the five edges is \(8/25+9/25+9/25+8/25+1/25=35/25=7/5\), equal to the effective conductance.
Reading the Calculations Carefully
These examples illustrate a useful workflow. First specify the stopping boundary and the quantity being asked for. For hitting probabilities, assign the appropriate boundary values and solve the harmonic equations. For occupation counts, restrict the transition matrix to the interior and solve the Green-matrix equation. When the graph is viewed electrically, use the same harmonic function as the voltage with the chosen boundary values.
A common error is to confuse conductances with transition probabilities. At vertex \(x\), the probability of moving to \(y\) is \(c_{xy}/c(x)\), not \(c_{xy}\) itself. Another is to include a visit at time \(\tau_B\) in the killed Green function; its definition counts only times strictly before the boundary hit. Finally, the Green matrix is indexed by starting vertex in its row and visited vertex in its column. Checking one row or column against the first-step equation is a simple way to catch an indexing or multiplication mistake.
Check Your Understanding
Try to answer each question by writing the relevant equation before calculating.
- Why does the first-step equation at an interior vertex use transition probabilities rather than raw conductances?
- For the path in the first example, what are the boundary values if the desired event is hitting \(0\) before \(3\)?
- What does the entry \(G_B(x,y)\) count, and why does it include a visit at time \(0\) when \(x=y\)?
- For a finite graph with nonempty boundary, why does the killed Green matrix have finite entries?
- In the two-route example, how would the boundary equations change if the boundary voltage at \(t\) were \(0\) instead of \(1\), while the voltage at \(s\) remained \(0\)?