Introduction to Probability · Problem 11.2.33

Markov Chains — Grinstead & Snell

Mathematics — Probability · absorbing-markov-chains

Problem

Consider a random walker who moves on the integers

0, 1, \ldots, N

, moving one step to the right with probability

p

and one step to the left with probability

q = 1 - p

. If the walker ever reaches 0 or

N

he stays there. (This is the Gambler's Ruin problem of Exercise 23.) If

p = q

show that the function

f(i) = i

is a harmonic function (see Exercise 27), and if

p \neq q

then

f(i) = \left(\frac{q}{p}\right)^i

is a harmonic function. Use this and the result of Exercise 27 to show that the probability

b_{iN}

of being absorbed in state

N

starting in state

i

b_{iN} = \begin{cases} \dfrac{i}{N}, & \text{if } p = q, \\ \dfrac{\left(\frac{q}{p}\right)^i - 1}{\left(\frac{q}{p}\right)^N - 1}, & \text{if } p \neq q. \end{cases}