There are 4 balls, two red and the two blue. You choose a color each time and a random ball is picked from the sample (w/o replacement). If your choice and the random pick matches, you gain one dollar. Repeat this four times. How much would you pay to play this game

My Answer: We have a probability of 0.5 of getting the first guess right, and the second given we go for the one we didnt choose in the first trial is 2/3 and from there we would have 0.5 + 1 expected value, so my answer is $1(0.5) + 1(2/3) + 1(0.5) + 1 = 8/3$

Is this correct?

  • $\begingroup$ Catalan numbers are involved. $\endgroup$ – Brian Tung Jan 15 '16 at 19:02

The optimum strategy is to pick the color with more balls or pick a random (you can also arbitrarily) color if they are the same number. Without loss of generality we can assume the first ball is red. So there are three outcomes with probability 1/3 each and expected winnings: \begin{align} \text{Outcome},&\quad\text{Winning}\\ RRBB, &\quad1/2+0+1+1 = 5/2\\ RBRB, &\quad1/2+1+1/2+1 = 3 \\ RBBR, &\quad1/2+1+1/2+1 = 3\\ \end{align} So the expected gain is (3+3+5/2)/3=17/6.


Update. I originally misread the problem: I assumed we win $\$1$ for a correct guess and lose $\$1$ for an incorrect guess. I have fixed this somewhat hastily in what follows, which accounts for the rather clumsy manner in which the actual schedule (win $\$1$ for a correct guess and lose nothing for an incorrect guess) is addressed. If I get a chance, I will "smooth it out" a bit.

Under my original, incorrect interpretation, the expected earnings are just $R_N$ itself (see below).

Original answer, edited. We solve this problem for $2N$ balls, $N$ red, $N$ blue. We begin by observing that the guessing strategy is trivially obvious. We know from past draws how many balls of each color remain in the urn (or wherever), and we simply guess whichever color there are more of. If there are equal numbers of red and blue balls, we can guess either color (it doesn't affect the expected winnings).

Let $r_t$ and $b_t$ be the number of red and blue balls, respectively, drawn after $t$ draws. That is,

$$ r_t+b_t = t $$

Further, let

$$ d_t = r_t-b_t $$

The process $\{d_t\}$ appears at first glance to be a stepwise random walk with independent steps, but it is not, because we know that $d_{2N} = 0$.

A move of $\{d_t\}$ toward $0$ represents a gain of one dollar (which we can think of as a wage of half a dollar plus winnings of half a dollar), and a move away from $0$ represents a loss of one dollar (which we can think of as a wage of half a dollar less a loss of half a dollar), with one exception. When $d_t = 0$, the next move must obviously be away from $0$. But since our guess is correct with probability $1/2$, the expected gain on this draw is just half a dollar (which we can think of as just the wage).

Now, $d_0 = 0$. Suppose that $d_t$ is next equal to $0$ at $t = t^*$. Between $t = 0$ and $t = t^*$, the winnings and losses balance each other out, except that the initial zero win/loss at $t = 0$ is matched with a final winnings of half a dollar. Therefore, the gain from $t = 0$ to $t = t^*$ is simply half a dollar plus the wages $t^*/2$. The expected gain for the entire game is then equal to $1/2$ times the number of returns to $0$ of $\{d_t\}$, plus the wages $2N/2 = N$.

It is now our task to compute this value. We define a balanced string to be a string of draws containing equal numbers of red and blue balls. We define an atomic balanced string to be a balanced string that does not contain a balanced string as a proper prefix. The initial urn is therefore a balanced string, but it is not necessarily an atomic balanced string. The expected gain for this game is the expected number of atomic balanced strings.

Let $A_n$ be the number of all atomic balanced strings of length $2n$. Let $x$ be such a string. Suppose the first ball of $x$ is red. Then the last ball of $x$ must be blue. (Otherwise, $x$ would not be atomic.) What comes in between is a series of atomic balanced strings all beginning with a red ball. The number of such series is the Catalan number

$$ C_{n-1} = \frac{\binom{2n-2}{n-1}}{n} $$

Since the first ball of $x$ can in fact be either red or blue,

$$ A_n = 2C_{n-1} = 2\frac{\binom{2n-2}{n-1}}{n} $$

Now consider the entire urn. Let $K_{n,N}$ be the probability that the first atomic balanced string (in an urn with $2N$ balls) has length $2n$. By inspection, we can write

$$ K_{n,N} = A_n \frac{\binom{2N-2n}{N-n}}{\binom{2N}{N}} = \frac{\left[\binom{N}{n}\right]^2}{(2n-1)\binom{2N}{2n}} $$

Then define $R_N$ to be the expected number of returns to $0$ by $\{d_t\}$ in an urn of size $2N$

$$ R_N = \sum_{n=1}^{N-1} K_{n,N} R_{N-n} $$

Solving this recursively for $R_N$ yields

$$ R_N = \frac{2^{2N}}{\binom{2N}{N}}-1 $$

and then the expected earnings are

$$ E(\text{earnings}) = \frac{R_N}{2}+N = \frac{2^{2N-1}}{\binom{2N}{N}}+\frac{2N-1}{2} $$

For the present case $N = 2$, this yields $E(\text{earnings}) = \frac{17}{6}$.


According to me it should be 8.25÷3 !! There are two possibilities one 0.5 ×1+ (1÷3)×1+1+1=8.5÷3 and 2nd is 0.5×1+(2÷3 ) ×1 + .5 +1= 8÷3 so avg of both cases is 8.25÷ 3

  • $\begingroup$ What are your two possibilities? $\endgroup$ – Sean English Jan 15 '16 at 19:45

If you know whether the ball picked on a given trial matches your guess, there is an optimal strategy to proceeding. There is $\dfrac{1}{2}$ probability of getting the first guess right.
Whether or not I got it right, I'm gonna guess the color that wasn't picked in the first trial for the second trial. There is a $\dfrac{2}{3}$ probability of this being correct.
If it is correct, then the minimum payout over the next $2$ games is $3/2$.
If the second guess was not correct, the minimum payout is 2.
Therefore the EV is: $\dfrac{1}{2} + \dfrac{2}{3} + \dfrac{2}{3}*(1+\dfrac{1}{2}) + \dfrac{1}{3}*(1+1) = \dfrac{17}{6}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.