Game Theory Tuesday: The Dice Brain Teaser: A Technical Interview Question that Can Help You Solve Problems Better

Today’s puzzle is special. I like it even more than previous brain teasers I’ve discussed, like the monk problem and the hat puzzle.

Like the others, this is a technical question sometimes asked during job interviews (hat tip: Reasonable Deviations).

But unlike the others, this problem serves as an introduction to some powerful problem solving techniques. This puzzle can be solved by four methods, each providing a different angle to the problem.

The first method is particularly important for anyone that wants to manage risk and understand randomness. It’s a simulation technique simple enough for spreadsheets but powerful enough that it’s used by virtually all technical people, including traders, financial planners, statisticians, and engineers.

The second and third methods are clever ways to look at the problem and provide insight into solving other puzzles. The fourth method uses an infinite sum, so it could be used as an example for anyone teaching math.

The Problem

You and I play a game where we take turns rolling a die. I win if I roll a 4. You win if you roll a 5.

If I go first, what’s the probability that I win?

Here are some clarifying notes about the game:

–If I don’t get a 4, and you don’t get a 5, we keep rolling until one of us does get a winning number.

–The order of play matters. If I roll a 4, I win and the game ends. You roll only if I fail to get a 4.

–Someone will ultimately win the game (there is no draw). This means the probability I win is the same as the probability that you lose.

Intuition

Before going into the calculations, let’s get some intuition.

Because all rolls of a die are equally likely, both players have an equal chance of rolling a winning number. So at first glance, the odds of winning should be roughly equal.

The factor that tips the odds is the playing order. That is because if the first player rolls a 4, he wins and the game ends. The second player does not have a chance to respond.

So this game is all about estimating the size of the first-mover advantage.

If this problem were given to a math class, many students would start by drawing out a tree diagram and realize it involves an infinite series. Such precision is not required.

We can get a good idea by the brute force of simulation.

Method 1: Monte Carlo Simulation

The simplest approach is to actually play some games and count how many times the first player wins. It would be cumbersome and time-consuming to actually roll the dice hundreds of times, so let’s instead do this on spreadsheet.

This simulation technique is one example of Monte Carlo simulation, which is a method of simulating random events to get a sense of the distribution of outcomes. While this dice problem can be solved by pencil and paper, many real-world problems cannot. That is why simulating can provide answers and is more powerful in many practical problems, like planning for retirement or pricing stock options.

The dice problem requires simulating two random rolls of a die and assigning an outcome to the rolls.

Here is how I set up one round in a spreadsheet:

To simulate more trials, all that’s needed is to copy the formulas and then keep track of how may times each player wins.

How many trials are needed? This is a question that doesn’t have a precise answer because many problems sent to simulation typically have an unknown variance. Since more trials usually lead to more accurate outcomes, it usually does not hurt to simulate a very large number. In one project, I ran 10 million trials of a Monte Carlo model to estimate the price of a structured finance deal.

For this problem, the only randomness comes from the rolls of a die, which are relatively stable. Accordingly, I performed a simulation with 100,000 rounds to be safe. The result was that the first player won about 54 percent of the time.

I can be pretty sure the real answer is near this estimate. If all I cared about was an answer, this number would probably be good enough for government work.

The unsatisfying part is that the estimate gives no clue as to why the answer is correct. It’s that insight that could help in solving similar problems.

This is why I present more solutions. The next three methods arrive at the same answer and they also illustrate why the solution works.

Method 2: Backwards Induction

This dice problem is mentally tricky because many rounds end without a winner. It would seem necessary to keep track of an infinite series to arrive at an answer.

But that’s not the case. The trick is seeing that each round is really an independent sub-game. The fact that the previous round ended without a winner does not affect the winner of the current round or any future round. This means we can safely ignore outcomes without winners.

The probability of winning depends only on the features of a single round.

This simplifies the problem to a more tractable one. So now, assume that one of the players did win in a round, and then calculate the relative winning percentages.

In other words, calculate the probability the first player wins given the round definitely produced a winner.

To do that, we look at the distribution of outcomes. In any given round, the first player can roll six outcomes, as can the second player. How many of those thirty-six outcomes produce a winner, and how many are from the first player?

This diagram illustrates the answer:

There are exactly 11 outcomes where somebody wins, of which 6 belong to the first player. Therefore, the first player wins with a 6/11 chance, or about 54.5 percent of the time.

This is the same numerical answer as Monte Carlo, but we get an explanation why it works.

The first-mover advantage is caused by the fact the first player wins even if both were to roll winning numbers.

But there are other ways to think about the problem too. The next method is especially interesting.

Method 3: Symmetric Thinking

This method is about using a mental trick. I particularly find it satisfying, though I can honestly say I would not have come up with this on my own.

Here is the solution from a comment by Mja at Reasonable Deviations:

Let p denote the probability that “I” (the first player) win. Since all games ultimately produce a winner, the second player wins with the complementary probability 1 – p.

Let’s figure out the chance that I win. On my roll, I have a 1/6 chance of winning the game. What happens in the 5/6 of cases when I don’t win?

If I don’t win, the second player gets a chance to roll. Now, it’s the other person that gets to roll first and I have to wait.

This means if I do not win on my first roll, the game is the same but I take on the role of the player that rolls second.

Hence, if I do not win on my first roll, my winning chances become 1 - p.

Algebraically, this can be written as:

p = Pr(win 1^st roll) + Pr(not win 1^st roll) Pr(win | not win on 1^st roll)

p = Pr(roll 4) + Pr(not roll 4) Pr(second person rolling wins)

p = 1/6 + 5/6 (1 - p)

p = 1 – 5p / 6

11p / 6 = 1

p = 6/11, or about a 54.5 percent chance

I can’t think of immediate applications besides puzzles, but the symmetry is beautiful. This is one of those solutions seeking problems.

Method 4: Infinite Series

This is the conventional solution method for math classes. It works, but I certainly find the other methods to be more interesting.

To start, we draw an infinite the game tree illustrating the outcomes for each round of the game:

The first player’s winning percentage is the sum of all branches that lead to a win. These are all the odd-numbered branches in this diagram.

The first branch is reached with probability 1/6, the third branch is reached with probability 1/6 times 5/6 squared, and each subsequent odd-branch has an extra factor of 5/6 squared.

The task is solving the following infinite series:

Using the formula for geometric series, the solution is:

So we again arrive at 6/11, or about 54.5 percent.