[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

We considered the two examples of the Drunkard's Walk corresponding to the cases [math]n = 4[/math] and [math]n =5[/math] blocks (see Example). Verify that in these two examples the expected time to absorption, starting at [math]x[/math], is equal to [math]x(n - x)[/math]. See if you can prove that this is true in general. Hint:

Show that if [math]f(x)[/math] is the expected time to absorption then [math]f(0) = f(n) = 0[/math] and

[[math]] f(x) = (1/2)f(x - 1) + (1/2)f(x + 1) + 1 [[/math]]

for [math]0 \lt x \lt n[/math]. Show that if [math]f_1(x)[/math] and [math]f_2(x)[/math] are two solutions, then their difference [math]g(x)[/math] is a solution of the equation

[[math]] g(x) = (1/2)g(x - 1) + (1/2)g(x + 1)\ . [[/math]]

Also, [math]g(0) = g(n) = 0[/math]. Show that it is not possible for [math]g(x)[/math] to have a strict maximum or a strict minimum at the point [math]i[/math], where [math]1 \le i \le n-1[/math]. Use this to show that [math]g(i) = 0[/math] for all i. This shows that there is at most one solution. Then verify that the function [math]f(x) = x(n-x)[/math] is a solution.