Introduction to Probability · Problem 12.1.10

Random Walks — Grinstead & Snell

Mathematics — Probability · random-walks-card-guessing

Problem

(from K. Levasseur) A parent and his child play the following game. A deck of 2n2n cards, nn red and nn 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 nn, 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/21/2. What is the expected number of correct guesses that will be made by the parent? Hint: Each of the (2nn)\binom{2n}{n} possible orderings of red and black cards corresponds to a random walk of length 2n2n that returns to the origin at time 2n2n. 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 nn by exactly one-half the average number of equalizations. Now define the random variable XiX_i to be 1 if there is an equalization at time 2i2i, and 0 otherwise. Then, among all relevant paths, we have E(Xi)=P(Xi=1)=(2n−2in−i)(2ii)(2nn).E(X_i) = P(X_i = 1) = \frac{\binom{2n-2i}{n-i}\binom{2i}{i}}{\binom{2n}{n}}. Thus, the expected number of equalizations equals E(∑i=1nXi)=1(2nn)∑i=1n(2n−2in−i)(2ii).E\left(\sum_{i=1}^{n} X_i\right) = \frac{1}{\binom{2n}{n}} \sum_{i=1}^{n} \binom{2n-2i}{n-i}\binom{2i}{i}. One can now use generating functions to find the value of the sum.
Intuitive explanation

The parent's advantage comes from using information—specifically, tracking which colors remain. The key insight is to view the game as a random walk and recognize that between consecutive moments when red and black cards are equal, the parent's strategy of guessing the more-likely color gives him exactly one extra correct guess on average. By counting equalizations (times when equal numbers of each color remain), you can express the parent's expected score as nn plus half the expected number of equalizations, then use generating functions to evaluate the sum of binomial products.

Intuitive explanation

The parent's advantage comes from using information—specifically, tracking which colors remain. The key insight is to view the game as a random walk and recognize that between consecutive moments when red and black cards are equal, the parent's strategy of guessing the more-likely color gives him exactly one extra correct guess on average. By counting equalizations (times when equal numbers of each color remain), you can express the parent's expected score as nn plus half the expected number of equalizations, then use generating functions to evaluate the sum of binomial products.

Related theory

Browse the problem library