To solve the Riddler without messy calculations, visit the Red Ball Casino

Posted May 4, 2017

FiveThirtyEight's Riddler this week is a puzzle about colorful balls in a box. Here's the puzzle:

You play a game with four balls: One ball is red, one is blue, one is green and one is yellow. They are placed in a box. You draw a ball out of the box at random and note its color. Without replacing the first ball, you draw a second ball and then paint it to match the color of the first. Replace both balls, and repeat the process. The game ends when all four balls have become the same color. What is the expected number of turns to finish the game?

Extra credit: What if there are more balls and more colors?

I first solved this puzzle through a messy calculation with some nasty numbers. But then the answer turned out to be a nice, round number. Even the answer to the extra credit puzzle with \(n\) balls of \(n\) different colors is nice.

What follows is my attempt at a solution where the calculations are as simple as the final answer. The goal isn't necessarily a short solution, but one with no complicated steps.

Welcome to the Red Ball Casino

At the Red Ball Casino, you can bet on the red balls in the colorful box game. Before any turn, you can place a bet by paying $1 for each red ball in the box. When the turn is over, you can cash out and get back $1 for each red ball that is now in the box, or you can roll your money over to bet on the next turn.

We'll solve the Riddler by answering a series of questions about the Red Ball Casino. You can construct the solution for yourself by answering each of the questions, or you can keep reading to see my solution.

We'll skip the four-ball case and think about the extra credit right away. Let \(n\) be the total number of balls in the box. Each ball starts out a different color; one ball is red. Let \(k\) be a whole number with \(1 \leq k \leq n-1\).

Question 1: At the Red Ball Casino, does the house have an advantage, does the player have an advantage, or is the game fair?

Question 2: The value of your bet is currently \(v\) dollars (\(0 \lt v \lt k\)), and you decide to keep betting until you either win \(k\) dollars or go broke trying. What's the probability that you succeed?

Question 3: You place a bet when there are \(k\) red balls, which costs you \(k\) dollars. The next ball that's drawn is not red. This is bad for you. What fraction of your money will you lose, in expected value?

Question 4: You place a bet when there are \(k\) red balls, and leave your money in until the game ends. The next ball that's drawn is not red. What's the probability that you never again have \(k\) dollars?

Question 5: You place a bet when there are \(k\) red balls, and the next ball that's drawn is red. What's the probability that you never again have \(k\) dollars?

Question 6: The box reaches \(k\) red balls, and the casino gives you a free drink. On every subsequent turn that starts with \(k\) red balls, you get another free drink. What's your expected number of free drinks?

Question 7: Someone gives you a hot tip that this game will end with all red balls. How does that affect your answer to Question 6?

Question 8: Conditioned on the game ending with all red balls, what is the expected number of turns?

Question 9: What is the answer to the Riddler?

Answers

Question 1: At the Red Ball Casino, does the house have an advantage, does the player have an advantage, or is the game fair?

Answer 1: If you draw a red ball then a non-red ball, you gain a dollar, while if you draw the same balls in the opposite order, you lose a dollar. You're equally likely to gain a dollar or lose a dollar, so the game is fair. (The number of red balls in the box over time is a martingale.)

Question 2: The value of your bet is currently \(v\) dollars (\(0 \lt v \lt k\)), and you decide to keep betting until you either win \(k\) dollars or go broke trying. What's the probability that you succeed?

Answer 2: Since the game is fair, you can never win or lose money on average. That means that on average, you'll win \(v\) dollars. So, there is a \(\frac{v}{k}\) probability that you win \(k\) dollars. (Formally, this is an application of the optional stopping theorem.)

Question 3: You place a bet when there are \(k\) red balls, which costs you \(k\) dollars. The next ball that's drawn is not red. This is bad for you. What fraction of your money will you lose, in expected value?

Answer 3: Each of the \(n - 1\) balls left in the box has a \(\frac{1}{n-1}\) probability of getting painted over not-red. So, each dollar that you invested has a \(\frac{1}{n-1}\) probability of getting painted into oblivion. Your expected loss is a \(\frac{1}{n-1}\) fraction of your money.

Question 4: You place a bet when there are \(k\) red balls, and leave your money in until the game ends. The next ball that's drawn is not red. What's the probability that you never again have \(k\) dollars?

Answer 4: Putting together Answers 2 and 3, there's a \(\frac{1}{n-1}\) probability that you lose all your money before you get back to \(k\) dollars.

Question 5: You place a bet when there are \(k\) red balls, and the next ball that's drawn is red. What's the probability that you never again have \(k\) dollars?

Answer 5: To answer this question, we'll take the complimentary (or perhaps, complementary) shuttle over to the Non-red Ball Casino. Here, the each non-red ball is worth $1 and the red balls are worth nothing. Answers 1-4 all still apply here if we swap the words "red" and "non-red." Applying the Non-red-Ball-Casino version of Answer 4 (also replaceing \(k\) with \(n-k\)), we find that the answer to this question is also \(\frac{1}{n-1}\).

Question 6: The box reaches \(k\) red balls, and the casino gives you a free drink. On every subsequent turn that starts with \(k\) red balls, you get another free drink. What's your expected number of free drinks?

Answer 6: Let \(d\) be the expected number of drinks. After your receive your first drink, there's a \(\frac{1}{n-1}\) probability (from Answers 4 and 5) that you never receive another, and otherwise you expect to receive another \(d\) drinks. So, $$d = 1 + \left(1 - \frac{1}{n-1}\right)d,$$ so \(d = n - 1\).

Question 7: Someone gives you a hot tip that this game will end with all red balls. How does that affect your answer to Question 6?

Answer 7: After you get a free drink, one of three things happens: (1) you eventually get another free drink, (2) all the balls turn red before you can get another free drink, or (3) all the balls turn non-red before you can get another free drink. The probability of each of these is independent of how many free drinks you've already received. So, the number of free drinks you get is independent of whether the game ends with all red balls or no red balls. The answer to Question 6 is unaffected.

Question 8: Conditioned on the game ending with all red balls, what is the expected number of turns?

Answer 8: For each \(k\) with \(1 \leq k \leq n - 1\), there will at some point be \(k\) red balls, because eventually all the balls are red. From there, the expected number of turns with \(k\) red balls is \(n - 1\). That is, there will be an expected \(n-1\) turns with 1 red ball, \(n-1\) turns with 2 red balls, and so on, up to \(n-1\) turns with \(n-1\) red balls. That's \((n-1)^2\) turns in total.

Question 9: What is the answer to the Riddler?

Answer 9: There is nothing special about the color red; no matter which color all the balls end up, the expected number of turns is \((n-1)^2\). Specifically, when there are \(n = 4\) balls in the box, the expected number of turns is 9.