Grinstead-Snell-Probability · Problem 10

Random Walks

Mathematics · random-walks-card-game

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.

Related theory

Browse the problem library