3.5.5 Let fXng be a random walk for which zero is an absorbing state and such that from a positive state, the process is equally likely to go up or down one unit.

The transition probability matrix is given by (3.38) with r0 D 1 and pi D qi D 1 2

for i  1.

(a) Show that fXng is a nonnegative martingale.

(b) Use the maximal inequality in Chapter 2, (2.53) to limit the probability that the process ever gets as high as N > 0.