Introduction to Probability · Problem 11.2.11

Markov Chains — Grinstead & Snell

Mathematics — Probability · absorbing-markov-chains

Problem

Let bkb_k denote the expected number of steps to reach nn from n−kn - k, in the process described in Exercise 9. (a) Define b0=0b_0 = 0. Show that for k>0k > 0, we have bk=1+1k(bk−1+bk−2+⋯+b0).b_k = 1 + \frac{1}{k}\bigl(b_{k-1} + b_{k-2} + \cdots + b_0\bigr). (b) Let f(x)=b0+b1x+b2x2+⋯ .f(x) = b_0 + b_1 x + b_2 x^2 + \cdots. Using the recursion in part (a), show that f(x)f(x) satisfies the differential equation (1−x)2y′−(1−x)y−1=0.(1 - x)^2 y' - (1 - x)y - 1 = 0. (c) Show that the general solution of the differential equation in part (b) is y=−log⁡(1−x)1−x+c1−x,y = \frac{-\log(1 - x)}{1 - x} + \frac{c}{1 - x}, where cc is a constant. (d) Use part (c) to show that bk=1+12+13+⋯+1k.b_k = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k}.

Related theory

Browse the problem library