3
$\begingroup$

We have 3 black and 2 red balls in an urn. If we pick a black ball, we lose 1 USD. If we pick a red ball we win 1 USD. We can chose to start the game or not. If we start the game we can stop after every pick. I don't know how to calculate the value of the game.

$\endgroup$
  • $\begingroup$ We can maximize the expected value by walking away. And as a bonus we get some exercise. $\endgroup$ – André Nicolas Mar 21 '14 at 20:30
  • $\begingroup$ Which color wins and which loses? You have "black ball" in both winning and losing cases. $\endgroup$ – JiK Mar 21 '14 at 20:31
  • $\begingroup$ Sorry, edited. Red ball wins. $\endgroup$ – kanbhold Mar 21 '14 at 20:32
  • $\begingroup$ I assume value is the expected value of winnings to the player? $\endgroup$ – Patrick Mar 21 '14 at 20:36
  • $\begingroup$ Yes, it is the expected value. $\endgroup$ – kanbhold Mar 21 '14 at 20:46
3
$\begingroup$

Here is a computational approach using dynamic programming.

Consider a function $V : \mathbb{N}^2 \to \mathbb{Q}$ such that $V(b, r)$ is the value of a game with $b$ black balls and $r$ red ones. What do we know about $V$?

  • $V(0, r) = r$.
  • $V(b, 0) = 0$, since if there are no red balls left we should walk away.
  • For $b, r > 0$, we consider what will happen if we draw at least one more ball. If on our next draw we draw a black ball, we lose $1$ and are left with $b-1$ black balls and $r$ red ones, so we expect to gain $-1 + V(b-1, r)$ in total. If we draw a red ball, our total is $1 + V(b, r-1)$ by similar reasoning. We weight these cases according to their probability to get the expected value, $\frac{b}{b+r}\left(-1 + V(b-1,r)\right) + \frac{r}{b+r}\left(1 + V(b, r-1)\right)$. However, if this expression is negative, we should quit without drawing another ball. Thus we get $$V(b, r) = \max\left(0, \frac{b}{b+r}\left(-1 + V(b-1,r)\right) + \frac{r}{b+r}\left(1 + V(b, r-1)\right)\right)$$

We can use the above facts to fill in a table of values of $V(b, r)$ for $b \in \{0, 1, 2, 3\}$ and $r \in \{0, 1, 2\}$.

$$ \begin{array}{c|c|c|c} & b=0 & b=1 & b=2 & b=3 \\ \hline r=0 & 0 & 0 & 0 & 0 \\ \hline r=1 & 1 & 1/2 & 0 & 0 \\ \hline r=2 & 2 & 4/3 & 2/3 & 1/5 \\ \end{array} $$

So with $3$ black balls and $2$ red ones, the game is worth $1/5$.

$\endgroup$
  • $\begingroup$ Can you elaborate a bit more on the recursion part? $\endgroup$ – kanbhold Mar 21 '14 at 22:34
  • $\begingroup$ @kanbhold Yes, see my edited answer. $\endgroup$ – augurar Mar 21 '14 at 22:45
  • 1
    $\begingroup$ Nice that you took the time to fill the table :). Wow, it is a bit counterintuitive that the game is actually profitable even if $r<b$; no wonder I couldn't find the simple proof that it can't be profitable! $\endgroup$ – JiK Mar 21 '14 at 23:24

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.