Optimal Stopping in a Blue-Red Ball Draw

Game Theory · Medium · Free problem

A box contains 4 blue balls and 3 red balls. You draw balls one at a time without replacement. Each blue ball earns you $\$1$ and each red ball costs you $\$1$. After each draw you see the ball's color, collect (or pay) the dollar, and then decide: stop and keep your running total, or draw again.

You may stop at any point -- including before drawing at all (locking in $\$0$). What is the optimal stopping strategy, and what is the expected profit under that strategy?

Hints

  1. Think about the state of the game as $(b, r)$ -- the number of blue and red balls remaining. Your decision to stop or draw depends only on this state, not on your running total.
  2. Let $V(b, r)$ be the optimal expected future profit from state $(b, r)$. The value satisfies $V(b, r) = \max(0,\; \frac{b}{b+r}(1 + V(b-1, r)) + \frac{r}{b+r}(-1 + V(b, r-1)))$, with base cases $V(b, 0) = b$ and $V(0, r) = 0$.
  3. Build the DP table bottom-up starting from the smallest states. Note that $V(1, r) = 0$ for all $r \geq 2$ (one blue against two or more reds is a break-even or worse draw), while $V(1,1) = 1/2$, and use this to fill in $V(2, \cdot)$, then $V(3, \cdot)$, then $V(4, 3)$.

Worked Solution

How to Think About It: This is a classic optimal-stopping problem on a finite urn. The key feature is that you draw *without* replacement, so seeing a red ball is actually informative -- it shifts the remaining composition in your favor. The obvious wrong instinct is "stop when I'm ahead." The right instinct is "stop only when drawing next has negative expected continuation value." Because the urn composition changes with each draw, you track the state as $(b, r)$ -- blues and reds remaining -- and compute the value of the game from each state via backward induction.

Quick gut check before the math: you have 4 blues and 3 reds. If you drew every ball you would net $4 - 3 = +1$. You can do strictly better by stopping early in the rare states where the future is bad, so the answer should exceed $1$.

Quick Estimate: Think about the boundary states. If you ever exhaust all reds, the remaining blues are free money. If only reds remain, you stop immediately and collect $0$ more. The crucial -- and easy to get wrong -- observation is that the stopping boundary is NOT "stop when reds $\ge$ blues." Even when you are behind, one more draw is often worth it because a red draw *improves* the remaining mix. In fact, for this urn the continuation value is positive in almost every reachable state; you only refuse to draw from states with no blue left or from $(1,3)$. So the value sits a bit above the drew-everything baseline of $+1$, landing near $1.6$.

Approach: Backward induction. Let $V(b, r)$ be the optimal expected *additional* profit when $b$ blue and $r$ red balls remain. At each state you choose to stop (lock in $\$0$ more) or draw one ball and play optimally from the resulting state. Importantly, the base case for an all-blue state is $V(b,0)=b$ (you draw every remaining blue), so after drawing the *last* red out of a state you must still credit the blues that remain.

Formal Solution:

Base cases: $$V(b, 0) = b \quad \text{(only blues left -- draw them all)}$$ $$V(0, r) = 0 \quad \text{(only reds left -- stop immediately)}$$

Recurrence: at state $(b, r)$ with $n=b+r$, drawing yields blue w.p. $b/n$ and red w.p. $r/n$: $$V(b, r) = \max\!\left(0,\; \frac{b}{n}\bigl(1 + V(b-1, r)\bigr) + \frac{r}{n}\bigl(-1 + V(b, r-1)\bigr)\right)$$

Build the table from small states. The subtle step is $V(1,1)$: drawing a red from $(1,1)$ moves you to $(1,0)$, where one blue remains, so $V(1,0)=1$, NOT $0$.

  • $V(1, 1) = \max\!\big(0,\; \tfrac12(1+V(0,1)) + \tfrac12(-1+V(1,0))\big) = \max\!\big(0,\; \tfrac12(1) + \tfrac12(0)\big) = \tfrac12$
  • $V(1, 2) = \max\!\big(0,\; \tfrac13(1+0) + \tfrac23(-1+V(1,1))\big) = \max\!\big(0,\; \tfrac13 + \tfrac23(-\tfrac12)\big) = \max(0,0) = 0$
  • $V(1, 3) = \max\!\big(0,\; \tfrac14(1+0) + \tfrac34(-1+V(1,2))\big) = \max\!\big(0,\; \tfrac14 - \tfrac34\big) = 0$
  • $V(2, 1) = \max\!\big(0,\; \tfrac23(1+V(1,1)) + \tfrac13(-1+V(2,0))\big) = \tfrac23\cdot\tfrac32 + \tfrac13\cdot 1 = \tfrac43$
  • $V(2, 2) = \max\!\big(0,\; \tfrac12(1+V(1,2)) + \tfrac12(-1+V(2,1))\big) = \tfrac12(1) + \tfrac12\big(\tfrac13\big) = \tfrac23$
  • $V(2, 3) = \max\!\big(0,\; \tfrac25(1+V(1,3)) + \tfrac35(-1+V(2,2))\big) = \tfrac25 + \tfrac35\big(-\tfrac13\big) = \tfrac15$
  • $V(3, 1) = \max\!\big(0,\; \tfrac34(1+V(2,1)) + \tfrac14(-1+V(3,0))\big) = \tfrac34\cdot\tfrac73 + \tfrac14\cdot 2 = \tfrac{9}{4}$
  • $V(3, 2) = \max\!\big(0,\; \tfrac35(1+V(2,2)) + \tfrac25(-1+V(3,1))\big) = \tfrac35\cdot\tfrac53 + \tfrac25\cdot\tfrac54 = 1 + \tfrac12 = \tfrac32$
  • $V(3, 3) = \max\!\big(0,\; \tfrac12(1+V(2,3)) + \tfrac12(-1+V(3,2))\big) = \tfrac12\cdot\tfrac65 + \tfrac12\cdot\tfrac12 = \tfrac{17}{20}$
  • $V(4, 1) = \max\!\big(0,\; \tfrac45(1+V(3,1)) + \tfrac15(-1+V(4,0))\big) = \tfrac45\cdot\tfrac{13}{4} + \tfrac15\cdot 3 = \tfrac{16}{5}$
  • $V(4, 2) = \max\!\big(0,\; \tfrac46(1+V(3,2)) + \tfrac26(-1+V(4,1))\big) = \tfrac23\cdot\tfrac52 + \tfrac13\cdot\tfrac{11}{5} = \tfrac53 + \tfrac{11}{15} = \tfrac{12}{5}$
  • $V(4, 3) = \max\!\big(0,\; \tfrac47(1+V(3,3)) + \tfrac37(-1+V(4,2))\big) = \tfrac47\cdot\tfrac{37}{20} + \tfrac37\cdot\tfrac75 = \tfrac{37}{35} + \tfrac{3}{5} = \tfrac{58}{35}$

Since the continuation value is positive in every reachable state except the all-red states and $(1,3)$ (with $(1,2)$ exactly indifferent), the optimal rule is: keep drawing as long as at least one blue remains, except stop at $(1,3)$ -- equivalently, stop only when continuation value $\le 0$.

Answer: The optimal expected profit is $V(4,3) = \dfrac{58}{35} \approx 1.657$. The optimal policy is to keep drawing whenever the DP continuation value is positive; the only states where you stop are those with no blue left and the state $(1,3)$ (state $(1,2)$ is a knife-edge where continuing is exactly break-even).

Intuition

The key structural insight is that sampling without replacement makes this problem tractable and, in a precise sense, more favorable than sampling with replacement. Each red ball you draw is gone -- it can no longer hurt you. So observing a red actually improves the urn's composition for future draws. This is why even a state like $(2, 3)$ -- where reds outnumber blues 3-to-2 -- still has positive option value ($V(2,3) = 1/5$): there is a real chance of drawing both blues before the reds overwhelm you, and you can always bail out.

This problem is a prototype for a much broader class of stopping problems in trading and risk management: whenever you hold an option to exit a position (stop-loss triggers, callable bonds, American options), the right framework is backward induction on the remaining state space. The common mistake is to frame it as a rule over cumulative P&L ("stop if I am up $X$") rather than over the residual distribution of future outcomes. P&L is irrelevant -- what matters is the forward-looking continuation value. The DP makes this precise: you stop when the expected value of drawing next, integrated over all possible future paths from the new state, is negative.

Related problems

Open the full interactive solver →