Thread: difference equation

For the random walk problem, let(k) be the expected duration of the game
(until ruin) then:

x(k) = px(k+1) + (1-p)x(k-1) +1 .... with x(0) = 0, and x(N) = 0
Solve for x(k). Note the special case p= .5

Try a solution of the form x(k) = A t^k + Bk . You find that At^k +Bk = pAt^{k+1} + pB(k+1) + (1-p)At^{k-1} + (1-p)B(k-1) + 1. Collecting terms, At^{k-1}(t - pt^2 - (1-p)) = pB - (1-p)B + 1. Since the two sides are independent, they must both be zero. This gives a quadratic equation for t, with roots t_1 and t_2, and an equation for B, so that the general solution is A_1t_1^k + A_2t_2^k + Bk, where B is now fixed and A_1 and A_2 are determined by the end conditions. If p=1/2 the equation for t has a repeated root and you introduce a trial solution of the form (A+Ck)t^k + Bk.