Mathematics — Probability · absorbing-markov-chains
Problem
We considered the two examples of the Drunkard's Walk corresponding to the cases n=4 and n=5 blocks (see Example 11.13). Verify that in these two examples the expected time to absorption, starting at x, is equal to x(n−x). See if you can prove that this is true in general. Hint: Show that if f(x) is the expected time to absorption then f(0)=f(n)=0 and
f(x)=(1/2)f(x−1)+(1/2)f(x+1)+1
for 0<x<n. Show that if f1(x) and f2(x) are two solutions, then their difference g(x) is a solution of the equation
g(x)=(1/2)g(x−1)+(1/2)g(x+1).
Also, g(0)=g(n)=0. Show that it is not possible for g(x) to have a strict maximum or a strict minimum at the point i, where 1≤i≤n−1. Use this to show that g(i)=0 for all i. This shows that there is at most one solution. Then verify that the function f(x)=x(n−x) is a solution.