absorption probability

Given a markov chain (viewed as a graph) with two absorbing states $A, B$ (ie. there are no outedges to another vertex, just to themselves). Now suppose we are performing a random walk on this graph starting at vertex $v$ . What is the probability that the walk ends at $A$ versus $B$ ?
More generally, we may take a weighted graph with weight $x_{e}$ for each edge, and set the probability of walking along that edge is $\frac{x_{e}}{x_{1} + \dots + x_{d}}$ where the denominator is a sum over all edges outgoing from the current vertex.

Let us write $p (A) = 1$ and $p (B) = 1$ and we would like to find what $p (i)$ is for $i \in V$ .

Interpretation as electrical network

We note that for an arbitrary vertex,

p (v) = \sum_{i = 1}^{d} \frac{x_{e_{i}}}{x_{e_{1}} + \dots + x_{e_{d}}} p (v_{i})

where each $e_{i}$ is an edge that goes out from $v$ . Multiplying across the denominator and moving it all to one side, we have

(x_{e_{1}} + \dots + x_{e_{d}}) p (v) - \sum_{i = 1}^{d} x_{e_{i}} p (v_{i}) = 0

for all $v$ . Notice that the LHS is exactly what the Kirchoff's matrix of an electrical network is, applied to the vector of probabilities. We may then model these equations with the matrix multiplication:

K \cdot (\begin{matrix} p (1) \\ ⋮ \\ p (n) \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ ⋮ \\ 0 \\ 1 \end{matrix})

after we set $p (1) = 1$ and $p (n) = 0$ .

Recall this is exactly solving for the potential function of an electrical network, and so $p (i) = U_{i}$

Example

Suppose there is a straight line with vertices $0$ through $n$ and edges between $i$ and $i + 1$ and $i - 1$ , with equal probability of transitioning to either of these states. Let $A = 0$ and $B = n$ .

We have the following governing equations for $p (i)$ :

\begin{aligned} p (n) & = 1 \\ p (0) & = 0 \\ p (i) & = \frac{1}{2} p (i + 1) + \frac{1}{2} p (i - 1) \end{aligned}

Solving these relations yield $p (i) = \frac{i}{n}$