Escape probabiliy

Escape probability §

Consider a random walk on a random network. Fis a state $a\in V$ and a subset $Z\subset V$ such that $a\notin Z$. An interesting question is what is the probability of escape from a, that is, starting from $a$, what is the probability of arriving in $Z$ before returning to $a$:

$$P_a[{\tau }_Z<{\tau }_a^{+}]$$

Computing this probability is not an obious task. Luckly, it turns out that the function:

$$v(x):=P_x[{\tau }_a<{\tau }_Z]$$

it’s harmonic, so that we can apply the theory developed for voltage functions in eletrical networks. The boundary values are $v(a)=1$ and $v(Z)=0$. Such function exists and is unique by the maximum principle for harmonic functions.

Let’s prove that it’s harmonic using first step analysis:

$$P_x[{\tau }_a<{\tau }_Z]=\sum _{y\sim x}{P}_x[{\tau }_a<{\tau }_Z|\text{first step to }y]P_x[\text{first step to }y]$$ $$=\sum _{y\sim x}{P}_y[{\tau }_a<{\tau }_Z]P(x,y)\square$$

To compute the escape probability from $a$

$$P_a[{\tau }_Z<{\tau }_a^{+}]=\sum _{x}p(a,x)[1-v(x)]=\sum _x\frac{c(a,x)}{c(a)}[v(a)-v(x)]$$ $$=\frac{1}{c(a)}\sum _{x}i(a,x)$$

where $c(a):={\sum }_{x\sim a}c(a,x)$ (recall that $c(x)$ is a stationary measure, i.e. detailed balance holds with respect to $c$).

Notice how the escape probability depends on the total current out of $a$, so that we may regard the entire circuit between $a$ and $Z$ as a single conductor with an effective conductance

$$C_{eff}:=c(a)P_a[{\tau }_Z<{\tau }_a^{+}]=:\mathcal{C}(a\leftrightarrow Z)$$

Thus the only computation required to answer our original question is computing $\mathcal{C}(a\leftrightarrow Z)$. To do this we can use the same reduction rules used when solving circuits!

Expected number of vists before escape §

It follows from the strong Markov property that the number of visits before escape is a geometric random variable

$$\sum _{n=0}^{{\tau }_Z-1}1(X_n=a)\sim Geom(P_a[{\tau }_Z<{\tau }_a^{+}])$$

and thus has an expected value of

$$\mathbb{E}\left[\sum _{n=0}^{{\tau }_Z-1}1(X_n=a)\right]=P_a[{\tau }_Z<{\tau }_a^{+}{]}^{-1}=c(a)C_{eff}^{-1}=c(a)R_{eff}$$

Probabilistic interpretetion of current §

A simple model for the flow of charge in a real circuit is to assume that positive charges enter the circuit at $a$, and then do random Brownian motion in the circuit till they reach $Z$. Then the current of an edge is the expected number of passages of a charge. This is indeed true in our mathematical model:

Proposition (Current as edge crossings) Let $G$ be a finite connected network. Start a random walk at $a$ and kill it at $Z$. For $x\sim y$, let $S_{xy}$ be the number of transitions from $x$ to $y$. Then

$$\mathbb{E}[S_{xy}]={\mathcal{G}}_Z(a,x)p(x,y),\mathbb{E}[S_{xy}-S_{yx}]=i(x,y)$$

where $i$ is the current in $G$ when the potential applied at $a$ $v(a)$ is such that the total current flow from $a$ is one. Proof

$$\mathbb{E}\left[\sum _{n=0}^{\infty }1(X_n=x,X_{n+1}=y)\right]=\sum _{n=0}^{\infty }P(X_n=x,X_{n+1}=y)$$ $$=\sum _{n=0}^{\infty }P(X_n=x)p(x,y)=\mathbb{E}\left[1(X_n=x)\right]p(x,y)={\mathcal{G}}_Z(a,x)p(x,y)$$

If the flow out of $a$ is one, then we can write the potential using the Green function

$$v(x)=\frac{{\mathcal{G}}_Z(a,x)}{c(x)}$$

so that we get

$$\mathbb{E}[S_{xy}-S_{yx}]={\mathcal{G}}_Z(a,x)p(x,y)-{\mathcal{G}}_Z(a,y)p(y,x)$$ $$=v(x)c(xy)-v(y)c(xy)=i(xy)\square$$