= Mean absorption time of a lazy symmetric random walk
{title2=$\mathbb E_k[T]=k(n-k)/(1-q)$}
Consider a <random walk> on $\{0,1,\ldots,n\}$ with <absorbing states> $0,n$. At each interior state it stays in place with <probability> $q$, and moves one position in either direction with <probability> $(1-q)/2$, where $0\leq q<1$. Its <mean> <absorption time> from $k$ is
$$
\boxed{\mathbb E_k[T]=\frac{k(n-k)}{1-q}.}
$$
\b[Proof.] A sequence of at most $n$ consecutive leftward moves ensures absorption, with <probability> at least $((1-q)/2)^n>0$. Dividing time into blocks of length $n$ gives a <geometric series> bound on the survival <probabilities>, so the <expected value> is finite. Let $e_k=\mathbb E_k[T]$. The <law of total expectation> and <first-step analysis> give
$$
e_k=1+qe_k+\frac{1-q}{2}(e_{k+1}+e_{k-1}),\qquad e_0=e_n=0.
$$
Thus $e_{k+1}-2e_k+e_{k-1}=-2/(1-q)$. A <particular solution> of this <linear recurrence relation> is $-k^2/(1-q)$; its homogeneous solutions are $A+Bk$. The two <boundary conditions> give $A=0$, $B=n/(1-q)$, proving both the formula and its uniqueness. Holding slows the usual symmetric <random walk> by the factor $1/(1-q)$.
Back to article page
