[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]

In Feller, one finds the

following theorem: Let [math]M_n[/math] be the random variable which gives the maximum value of [math]S_k[/math], for [math]1 \le k \le n[/math]. Define

[[math]] p_{n, r} = {n\choose {{n+r}\over{2}}}2^{-n}\ . [[/math]]

If [math]r \ge 0[/math], then

[[math]] P(M_n = r) = \left \{ \begin{array}{ll} p_{n, r}\,,&\mbox{if $r \equiv n\, (\mbox{mod}\ 2)$}, \\ p_{n, r+1}\,,&\mbox{if $r \not\equiv n\,(\mbox{mod}\ 2)$}. \end{array} \right. [[/math]]

• Using this theorem, show that
  [[math]] E(M_{2m}) = {1\over{2^{2m}}}\sum_{k = 1}^m (4k-1){2m \choose m+k}\ , [[/math]]
  and if [math]n = 2m+1[/math], then
  [[math]] E(M_{2m+1}) = {1\over {2^{2m+1}}} \sum_{k = 0}^m (4k+1){2m+1\choose m+k+1}\ . [[/math]]
• For [math]m \ge 1[/math], define
  [[math]] r_m = \sum_{k = 1}^m k {2m\choose m+k} [[/math]]
  and
  [[math]] s_m = \sum_{k = 1}^m k {2m+1\choose m+k+1}\ . [[/math]]
  By using the identity
  [[math]] {n\choose k} = {n-1\choose k-1} + {n-1\choose k}\ , [[/math]]
  show that
  [[math]] s_m = 2r_m - {1\over 2}\biggl(2^{2m} - {2m \choose m}\biggr) [[/math]]
  and
  [[math]] r_m = 2s_{m-1} + {1\over 2}2^{2m-1}\ , [[/math]]
  if [math]m \ge 2[/math].
• Define the generating functions
  [[math]] R(x) = \sum_{k = 1}^\infty r_k x^k [[/math]]
  and
  [[math]] S(x) = \sum_{k = 1}^\infty s_k x^k\ . [[/math]]
  Show that
  [[math]] S(x) = 2 R(x) - {1\over 2}\biggl({1\over{1- 4x}}\biggr) + {1\over 2}\biggl(\sqrt{1-4x}\biggr) [[/math]]
  and
  [[math]] R(x) = 2xS(x) + x\biggl({1\over{1-4x}}\biggr)\ . [[/math]]
• Show that
  [[math]] R(x) = {x\over{(1-4x)^{3/2}}}\ , [[/math]]
  and
  [[math]] S(x) = {1\over 2}\biggl({1\over{(1- 4x)^{3/2}}}\biggr) - {1\over 2}\biggl({1\over{1- 4x}}\biggr)\ . [[/math]]
• Show that
  [[math]] r_m = m{2m-1\choose m-1}\ , [[/math]]
  and
  [[math]] s_m = {1\over 2}(m+1){2m+1\choose m} - {1\over 2}(2^{2m})\ . [[/math]]
• Show that
  [[math]] E(M_{2m}) = {m\over{2^{2m-1}}}{2m\choose m} + {1\over{2^{2m+1}}}{2m\choose m} - {1\over 2}\ , [[/math]]
  and
  [[math]] E(M_{2m+1}) = {{m+1}\over{2^{2m+1}}}{2m+2\choose m+1} - {1\over 2}\ . [[/math]]
  The reader should compare these formulas with the expression for \linebreak [math]g_{2m}/2^{(2m)}[/math] in Example \ref{exam 12.1.1}.

Notes