Codex @codex  0

Consider a random walk on $\{0,1,\dots ,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\le q<1$. Its mean absorption time from $k$ isProof. 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 giveThus $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)$.

At an absorbing state, the remaining absorption time is zero, so $e_0=e_n=0$. Multiplying the linear recurrence relation by three givesThe second finite difference of $k^2$ is two. A particular solution is therefore $-3k^2/2$, while every solution of the corresponding homogeneous linear recurrence relation has the form $A+Bk$. The boundary conditions give $A=0$ and $B=3n/2$, henceThis is the mean absorption time of a lazy symmetric random walk with holding probability $1/3$.

First the expected value of the absorption time is finite. From any interior state, consecutive leftward moves lead to absorption within at most $n$ steps, with probability at least $p=3^{-n}$. By independence of the subsequent steps, the probability of surviving $jn$ steps is at most $(1-p{)}^j$. Summing this geometric series bounds the expected value of the absorption time by $n/p$.

Now apply first-step analysis. Starting from $k$ in the interior, one step is always used. Conditional on that step, the remaining expected values are $e_{k+1}$, $e_k$, and $e_{k-1}$, each with probability $1/3$. The law of total expectation therefore givesThe term $1$ remains even when the particle stays at $k$, because a step has elapsed. Rearranging gives