= Solution
Use <simple random walk> on the loopless undirected unweighted <graph>, with transition <probability> $1/\deg(x)$ to each <graph neighbour>, and take $a\ne z$. Set $T_z=\inf\{t\geq0:X_t=z\}$. Returns to $a$ before visiting $z$ do not end the commute. After its first visit to $z$, stop at the subsequent first visit to $a$, so $\tau=T_z+T_a\circ\vartheta_{T_z}$. Count transitions with departure times $0\leq t<\tau$, including the final step arriving at $a$. The <expected hitting times> are finite: in a finite <connected graph> there is a uniformly positive <probability> to reach any fixed target within a fixed number of steps, giving a geometric tail bound.
We prove the needed <killed-walk occupation voltage> identity from its visit balance equation. Define
$$
g_{az}(x)=\mathbb E_a\sum_{t=0}^{T_z-1}\mathbf1_{\{X_t=x\}},\qquad v(x)=\frac{g_{az}(x)}{\deg(x)},\qquad v(z)=0.
$$
For $x\ne z$, counting arrivals before absorption gives
$$
g_{az}(x)=\mathbf1_{\{x=a\}}+\sum_{y\sim x}\frac{g_{az}(y)}{\deg(y)}.
$$
Hence, for the <graph Laplacian> $Lv(x)=\deg(x)v(x)-\sum_{y\sim x}v(y)$, we have $Lv(x)=\mathbf1_{\{x=a\}}$ away from $z$. Since the sum of all Laplacian coordinates is zero, $Lv(z)=-1$. Thus $v$ is the electrical <voltage> of a <unit flow> from $a$ to $z$, grounded at $z$, and $v(a)=R_{\mathrm{eff}}(a,z)$.
Construct $w(x)=g_{za}(x)/\deg(x)$ for the opposite killed leg. It satisfies $Lw=\delta_z-\delta_a$ and $w(a)=0$. Therefore $L(v+w)=0$. The <harmonic maximum principle on a finite graph> makes $v+w$ constant: at a maximum its value equals the average over its <graph neighbours>, forcing all of them to share that value, and connectedness propagates it. At $a$ the constant equals $R_{\mathrm{eff}}(a,z)$.
For any oriented <edge> $(x,y)$, each visit to $x$ before the target hit produces a transition to $y$ with conditional <probability> $1/\deg(x)$. The expected traversals during the first killed leg are therefore $v(x)$, and those during the second leg are $w(x)$ by the <Strong Markov property> at $T_z$. This proves <directed edge occupation in a random-walk commute>:
$$
\boxed{\mathbb E_a S(x,y)=v(x)+w(x)=R_{\mathrm{eff}}(a,z).}
$$
In particular, both directions of every unoriented <edge> have this same <expected value>, although their counts on an individual commute need not coincide. Summing over the $2|E|$ directed <edges> also recovers the <commute time identity> $\mathbb E_a\tau=2|E|R_{\mathrm{eff}}(a,z)$.
The distinct-terminal convention is necessary for the printed “returns” interpretation. If $a=z$ and $\tau$ is the first positive return, a <graph> with two <graph vertices> and one <edge> gives $S(a,y)=1$ while $R_{\mathrm{eff}}(a,a)=0$. Thus either take $a\ne z$, as intended, or explicitly define the degenerate commute as $\tau=0$. A general nonuniform <random walk> is not covered by the unweighted simple-walk formula.
Back to article page
