Meaning of $2^n/\sum_{i=0}^k\binom{n}{i}$

98 Views Asked by At

I was thinking about this problem. Suppose there is a bag of $n$ balls, $k$ of them have unknown colors, and the rest are all red. One starts with \$1 (infinitely divisible) and places $n$ even money bets (for each bet, he can wager any amount between zero and the current stake) on the color of the next randomly picked ball, and he can only bet red. I found the winnings that one can guarantee to win as

\begin{equation} \frac{2^n}{\sum_{i=0}^k\binom{n}{i}}=\frac{2^n}{\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}}. \end{equation}

How to interpret this expectation?

1

There are 1 best solutions below

0
On BEST ANSWER

There is a nice explanation of this formula. Over the course of the $n$ draws, you will observe some sequence of length $n$, where each entry is either "red" or "not red". The number of possible sequences is $\binom n0+\binom n1+\dots+\binom nk$, since for each $i\in \{0,\dots,k\}$, the number of sequences with exactly $i$ non-red balls is $\binom ni$.

Let $s$ be a particular sequence with at most $k$ non-reds. Consider the following betting strategy; at the $i^\text{th}$ turn, for each $i\in \{1,\dots,n\}$, you will bet the entirety of your current wealth that the next ball is the $i^{th}$ element of $s$. If the sequence happens to be exactly $s$, then you will win huge, taking home $\$\,2^n$. However, with overwhelming probability, the true sequence will not match, and you will lose everything. The expected outcome of this strategy is therefore $$ 2^n\cdot P(\text{sequence is $s$})=\frac{2^n}{\binom n0 +\dots+\binom nk} $$ It is interesting that these seemingly stupid strategy performs as well as the optimal strategy, on average.

We can use these stupid strategies to derive the optimal strategy. Imagine dividing your dollar into $\binom n0+\dots+\binom nk$ equal pieces, one for each possible sequence. You will hire $\binom n0+\dots+\binom nk$ assistants, and give one of these shares to each assistant. Each assistant will take their stake and play the bet-it-all-on-$s$ strategy, with on assistant playing each possible sequence $s$. With this distributed strategy, exactly one assistant will win big, $2^n$ times their share, while all the others will lose. Therefore, this strategy guarantees taking home $2^n/(\binom n0+\dots+\binom nk)$.

This strategy can be performed without assistants; you just need to mentally subdivide your money and add up the contribution from each imaginary assistant. We can directly describe what this looks like. Suppose that $t$ rounds have already elapsed, during which you observed $h$ non-red balls and $t-h$ red balls. Then the fraction of your wealth you should bet on red for the next round is $$ \frac{\binom{n-t-1}{0}+\binom{n-t-1}1+\dots+\binom{n-t-1}{k-h}}{\binom{n-t}{0}+\binom{n-t}1+\dots+\binom{n-t}{k-h}} $$ The denominator is the number of valid sequences describing the next $n-t$ draws. In the many-assistant interpretation, it is the number of assistants who are still "alive." The numerator is the number of these sequences where the color of the next ball in the sequence is red; this is the number of assistants where the bet-it-all-on-$s$ strategy causes them to bet next turn.