The Mathematics of Predicting the Future

Question

I'm predicting the future of a deck of cards. Specifically, I have a deck of $2n$ cards: $n$ are red, and $n$ are black. The deck is shuffled uniformly randomly.

I'm dealing out the cards one by one, and trying to predict what color each card will be, before I see it.

I don't have any special powers, so I guess at the cards as follows: I count how many cards of each color have been dealt, and I pick the color I've seen less often so far.

With this strategy, and $n=100$, I guess $108.37$ cards correctly, on average. The first 100 correct cards are nothing to get excited about: I could do that with my eyes closed. The next 8.37 correct cards are more exciting: That's my bonus for using a good strategy. Let's call the number of correct predictions, above $n$, my "bonus cards".

For larger and larger $n$, the number of bonus cards grows roughly like $\sqrt{n}$. For instance, for $n=10^4,$ the average number of bonus cards is $88.12$.

Question: As $n \to \infty$, what is the limiting value of the average number of bonus cards, divided by $\sqrt{n}$? How do you know?

Answer 1

The limiting ratio is

$$ \frac {\sqrt\pi} 2 \approx 0.886$$

Reasoning:

First observe that every time the numbers of black and red cards seen so far

are equal

offers a fifty-fifty chance to earn a bonus card simply by

guessing the next card right.

Indeed,

between consecutive ties the majority---once it is picked by the first card---does not change. Also, the numbers of black and red cards dealt between ties are equal. And because the majority does not change our policy will guess the same colour all the time and hence put us exactly at chance level. Except for the very first card which gives us a 50% chance of doing better.

We therefore need to count the expected number of times a tie will be seen.

The probability to be tied after $2k$ cards is

$$ p_k := \frac {\begin{pmatrix}2k \\ k\end{pmatrix}\begin{pmatrix}2(N-k) \\ N-k \end{pmatrix}} {\begin{pmatrix}2N \\ N\end{pmatrix}}$$

Using the asymptotic expression

$$\begin{pmatrix}2n \\ n\end{pmatrix}\simeq \frac{2^{2n}}{\sqrt{\pi n}}$$

for the binomial coefficient we get for the expected number of ties $T_N$ to be

$$T_N = \sum_{k=1}^{N-1} \sqrt{\frac N {\pi k(N-k)}} = \sqrt{N} \sum_{k=1}^{N-1} \frac{1}{N} \frac{1}{\sqrt{\pi (k/N)(1-k/N)}}$$

Note that strictly speaking we should also count one of the endpoints, and also that the approximation is not good for small $k$. As we are, however, only interested in asymptotics this matters not.

Take the limit to get

$$T_N / \sqrt{N} \to \frac 1 {\sqrt {\pi}} \int_0^1 \frac{1}{\sqrt{h(1-h)}}dh = \sqrt {\pi}$$

and half that for the expected number of bonus cards divided by $\sqrt{N}$.

Answer 2

I considered this problem a long ago and it caused interesting calculations, see here.

The average number of bonus cards should be

$$n\int_0^1 x^n(2-x)^{n-1} dx=$$

$$\frac{\sqrt{\pi}}{2} n^{1/2} - \frac{1}{2} + \frac{\sqrt{\pi}}{16} n^{-1/2} + \frac{\sqrt{\pi}}{256} n^{-3/2} - \frac{5 \sqrt{\pi}}{2048} n^{-5/2} + \cdots.$$