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

(from K. Levasseur) A parent and his child play the following game. A deck of [math]2n[/math] cards, [math]n[/math] red and [math]n[/math] black, is shuffled. The cards are turned up one at a time. Before each card is turned up, the parent and the child guess whether it will be red or black. Whoever makes more correct guesses wins the game. The child is assumed to guess each color with the same probability, so she will have a score of [math]n[/math], on average. The parent keeps track of how many cards of each color have already been turned up. If more black cards, say, than red cards remain in the deck, then the parent will guess black, while if an equal number of each color remain, then the parent guesses each color with probability 1/2. What is the expected number of correct guesses that will be made by the parent? Hint: Each of the [math]{{2n}\choose n}[/math] possible orderings of red and black cards corresponds to a random walk of length [math]2n[/math] that returns to the origin at time [math]2n[/math]. Show that between each pair of successive equalizations, the parent will be right exactly once more than he will be wrong. Explain why this means that the average number of correct guesses by the parent is greater than [math]n[/math] by exactly one-half the average number of equalizations. Now define the random variable [math]X_i[/math] to be 1 if there is an equalization at time [math]2i[/math], and 0 otherwise. Then, among all relevant paths, we have

[[math]] E(X_i) = P(X_i = 1) = \frac{{{2n-2i}\choose{n-i}}{{2i}\choose{i}}}{{{2n}\choose{n}}}\ . [[/math]]

Thus, the expected number of equalizations equals

[[math]] E\biggl(\sum_{i = 1}^n X_i\biggr) = \frac 1{{{2n}\choose{n}}}\sum_{i = 1}^n {{2n-2i}\choose{n-i}}{{2i}\choose{i}}\ . [[/math]]

One can now use generating functions to find the value of the sum.

It should be noted that in a game such as this, a more interesting question than the one asked above is what is the probability that the parent wins the game? For this game, this question was answered by D. Zagier. He showed that the probability of winning is asymptotic (for large [math]n[/math]) to the quantity

[[math]] \frac 12 + \frac 1{2\sqrt 2}\ . [[/math]]

\item Prove that

[[math]] u^{(2)}_{2n} = \frac 1{4^{2n}} \sum_{k = 0}^n \frac {(2n)!}{k!k!(n-k)!(n-k)!}\ , [[/math]]

and

[[math]] u^{(3)}_{2n} = \frac 1{6^{2n}} \sum_{j,k} \frac {(2n)!}{j!j!k!k!(n-j-k)!(n-j-k)!}\ , [[/math]]

where the last sum extends over all non-negative [math]j[/math] and [math]k[/math] with [math]j+k \le n[/math]. Also show that this last expression may be rewritten as

[[math]] \frac 1{2^{2n}}{{2n}\choose n} \sum_{j,k} \biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr)^2\ . [[/math]]

\item Prove that if [math]n \ge 0[/math], then

[[math]] \sum_{k = 0}^n {n \choose k}^2 = {{2n} \choose n}\ . [[/math]]

Hint: Write the sum as

[[math]] \sum_{k = 0}^n {n \choose k}{n \choose {n-k}} [[/math]]

and explain why this is a coefficient in the product

[[math]] (1 + x)^n (1 + x)^n\ . [[/math]]

Use this, together with Exercise, to show that

[[math]] u^{(2)}_{2n} = \frac 1{4^{2n}}{{2n}\choose n}\sum_{k = 0}^n {n \choose k}^2 = \frac 1 {4^{2n}} {{2n}\choose n}^2\ . [[/math]]

\item Using Stirling's Formula, prove that

[[math]] {{2n}\choose n} \sim \frac {2^{2n}}{\sqrt {\pi n}}\ . [[/math]]

\item Prove that

[[math]] \sum_{j,k} \biggl(\frac 1{3^n}\frac{n!}{j!k!(n-j-k)!}\biggr) = 1\ , [[/math]]

where the sum extends over all non-negative [math]j[/math] and [math]k[/math] such that [math]j + k \le n[/math]. Hint: Count how many ways one can place [math]n[/math] labelled balls in 3 labelled urns. \item Using the result proved for the random walk in [math]{\mathbf R}^3[/math] in Example, explain why the probability of an eventual return in [math]{\mathbf R}^n[/math] is strictly less than one, for all [math]n \ge 3[/math]. Hint: Consider a random walk in [math]{\mathbf R}^n[/math] and disregard all but the first three coordinates of the particle's position.

Notes