Introduction to Probability · Problem 12.1.9

Random Walks — Grinstead & Snell

Mathematics — Probability · random-walks-maximum

Problem

In Feller, one finds the following theorem: Let

M_n

be the random variable which gives the maximum value of

S_k

, for

1 \leq k \leq n

. Define

p_{n,r} = \binom{n}{\frac{n+r}{2}} 2^{-n}.

r \geq 0

, then

P(M_n = r) = \begin{cases} p_{n,r}, & \text{if } r \equiv n \pmod{2}, \\ p_{n,r+1}, & \text{if } r \not\equiv n \pmod{2}. \end{cases}

(a) Using this theorem, show that

E(M_{2m}) = \frac{1}{2^{2m}} \sum_{k=1}^{m} (4k-1) \binom{2m}{m+k},

and if

n = 2m+1

, then

E(M_{2m+1}) = \frac{1}{2^{2m+1}} \sum_{k=0}^{m} (4k+1) \binom{2m+1}{m+k+1}.

(b) For

m \geq 1

, define

r_m = \sum_{k=1}^{m} k \binom{2m}{m+k}

and

s_m = \sum_{k=1}^{m} k \binom{2m+1}{m+k+1}.

By using the identity

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k},

show that

s_m = 2r_m - \frac{1}{2}\left(2^{2m} - \binom{2m}{m}\right)

and

r_m = 2s_{m-1} + \frac{1}{2} 2^{2m-1},

m \geq 2

. (c) Define the generating functions

R(x) = \sum_{k=1}^{\infty} r_k x^k

and

S(x) = \sum_{k=1}^{\infty} s_k x^k.

Show that

S(x) = 2R(x) - \frac{1}{2}\left(\frac{1}{1-4x}\right) + \frac{1}{2}\sqrt{1-4x}

and

R(x) = 2xS(x) + x\left(\frac{1}{1-4x}\right).

(d) Show that

R(x) = \frac{x}{(1-4x)^{3/2}},

and

S(x) = \frac{1}{2}\left(\frac{1}{(1-4x)^{3/2}}\right) - \frac{1}{2}\left(\frac{1}{1-4x}\right).

(e) Show that

r_m = m \binom{2m-1}{m-1},

and

s_m = \frac{1}{2}(m+1)\binom{2m+1}{m} - \frac{1}{2}(2^{2m}).

(f) Show that

E(M_{2m}) = \frac{m}{2^{2m-1}} \binom{2m}{m} + \frac{1}{2^{2m+1}} \binom{2m}{m} - \frac{1}{2},

and

E(M_{2m+1}) = \frac{m+1}{2^{2m+1}} \binom{2m+2}{m+1} - \frac{1}{2}.

The reader should compare these formulas with the expression for

g_{2m}/2^{(2m)}

in Example 12.3.