Rolling dice « Rod Carvalho's web notebook

Rolling dice

By Rod Carvalho

Via Nuclear Phynance, here’s a cute brain teaser:

You and I play a game. We each have 1 die. I win if I roll a 4. You win if you roll a 5. If I go first, what is the probability that I win?

Some quick remarks:

the game is over when I roll a 4 or when you roll a 5. Until that happens, the game is played ad infinitum.

the game is played in rounds. At each round, I roll the die, and only then you roll the die. If I get a 4, I win the game and you don’t get to roll your die.

the probability that I win is the same as the probability that you lose. And vice-versa.

if you go first, the probability that I win is different (of course).

note that there are two dice! However, since we roll the dice in a non-simultaneous manner, we actually only need one die. I can borrow yours, or lend you mine.

Tags: Brain Teasers, Games, Nuclear Phynance

This entry was posted on February 28, 2008 at 10:45 am and is filed under Brain Teasers, Games, Recreational Math. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

9 Responses to “Rolling dice”

Shubhendu Trivedi Says:
February 28, 2008 at 4:25 pm | Reply
Ok first of all apologies for not using LaTeX for typesetting.

We can define the following events:
E = you winning (person A) by getting a 4;
F = i winning (person B) by getting a 5.
Therefore:
P(E)=1/6,
P(F)= 1/6,
P(Ebar)= 5/6,
P(Fbar)= 5/6.

You win if you throw a four in 1st, or 3rd or 5th throws..
Your probability of throwing a 4 in 1st throw: = P(E)= 1/6.
You get the third throw if you fail in your first and i fail in the second throw respectively.
Therefore,
Probability of you winning in the third throw = P(Ebar. intersection. Fbar. intersection. E)
=P(Ebar)P(Fbar)P(E)= 5/6 x 5/6 x 1/6 = (5/6)^2 x 1/6.

Similarly Probability of you winning in the Fifth throw.
=P(Ebar. intersection. Fbar. intersection. Ebar. intersection. Fbar. intersection. E )
=P(Ebar)P(Fbar)P(Ebar)P(Fbar)P(E)
=5/6 x 5/6 x 5/6 x 5/6 x 1/6.
=(5/6)^4 x 1/6.
and so on.
Hence probability of you (A) winning
= P[E. union (Ebar.intersection. Fbar. intersection. E). union (Ebar. intersection. Fbar. intersection. Ebar. intersection. Fbar. intersection. E ) union.....]

=P(E) + P(Ebar. intersection. Fbar. intersection. E) + P(Ebar. intersection. Fbar. intersection. Ebar. intersection. Fbar. intersection. E ).

= 1/6 + (5/6)^2 x 1/6 + (5/6)^4 x 1/6 + . . .

%This is a GP with a= 1/6 and common ratio r= (5/6)^2

= (1/6)/{1-(5/6)^2}
=6/11

Probability of you winning is 6/11?
mja Says:
February 28, 2008 at 5:31 pm | Reply
Here’s another solution that also gives 6/11 as the answer:

Let’s solve for probability p, the chance that “I” (first player) win. Since all games eventually produce a winner (a.s.), the probability that the second player wins is then 1-p.

I have a 1/6 chance of winning on the first toss. Otherwise (5/6 chance), we are playing the same game but now I am player 2, so I have 1-p chance of winning. Algebraically,

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

I remember solving problems like this when playing Axis and Allies, a favorite strategy game during my middle and high school years. (Very similar situations would occur with e.g. submarine battles, for those who know the game; obviously you didn’t have to solve them algebraically to enjoy the game, but I was kind of obsessed.) At first I used brute force approaches, but eventually I hit on the fact that all you need to do is compute the relative probabilities of you winning and me winning before you get back to square one. So, just taking one iteration, you find that the probability player 1 wins is 1/6 or 6/36. The probability that player 2 wins is 5/36. And the probability that you find yourself in the same situation that you started in is 25/36… but you can ignore that and just look at the relative odds (6 to 5 in favor of player 1).

This approach generalizes to the case of more than two outcomes (e.g. allowing ties). The proof for any given outcome A works like this:

Let p(A) be the probability that you eventually end up in outcome A.
Let p(A1) be the probability that you end up in outcome A on the first “iteration”, defined as the minimum number of rolls after which the game has either terminated or you are in an equivalent situation as you were at the beginning.
Let q be the probability that the game didn’t terminate on the first iteration. Then q = 1 – p(A1) – p(B1) – p(C1) – … for all the possible outcomes.
Following the above outline, you get an equation that looks like this:

p(A) = p(A1) + p(A)q
p(A) = p(A1) / (1-q)
p(A) = p(A1) / (p(A1) + p(B1) + p(C1) + …) or in other words, once you know the relative chance of a given outcome on the first iteration, you know the odds of that outcome overall.

Anyway thanks for reminding me of all the fun I had in those days.
rod. Says:
February 29, 2008 at 4:40 am | Reply
@ Shubhendu

Yup, the answer is 6/11. I solved the problem pretty much the same way you did. First, I drew a binary tree with all the events, and then started multiplying conditional probabilities like there’s no tomorrow, LOL.

@ mja

Your solution is indeed incredibly elegant!
Thank you very much for sharing it :-)
The Dice Brain Teaser: A Technical Interview Question that Can Help You Solve Problems Better - Mind Your Decisions Says:
May 20, 2008 at 5:06 am | Reply
[...] Like the others, this is a technical question sometimes asked during job interviews (hat tip: Reasonable Deviations). [...]
Badal Joshi Says:
May 17, 2009 at 8:06 pm | Reply
Co-problems:
1) I roll the die first. You roll second. We keep going till someone wins. I win if “A happens” and you win if “B happens”. What are all possible events A and B, such that the game is fair (both of us win with equal probability)?
2) What are the expected lengths of the games in each case?
3) Can you come up with a game with expected length infinity but such that it ends almost surely?
- Rod Carvalho Says:
  May 18, 2009 at 2:17 am | Reply
  I like your ideas.
  
  1) For starters, let us say that players A and B perform each some sort of Bernoulli experiment where the probabilities of “success” are $p, q \in [0,1]$ , respectively. This is more general than throwing dice, and this abstraction helps us focus on the essential. The probablity that player A wins is
  
  $\mathbb{P}[\text{A wins}] = p + (1-p) (1-q) p + (1-p)^2 (1-q)^2 p + \ldots$
  
  which is a geometric series with ratio $r = (1-p) (1-q)$ , and hence we obtain
  
  $\mathbb{P}[\text{A wins}] = \displaystyle \sum_{k=0}^{\infty} p r^k = \displaystyle \frac{p}{1- (1-p)(1-q)}$ ,
  
  and $\mathbb{P}[\text{B wins}] = 1 - \mathbb{P}[\text{A wins}]$ , or course. We would like the game to be fair, i.e., $\mathbb{P}[\text{A wins}] = \mathbb{P}[\text{B wins}]$ , which leads to
  
  $\displaystyle\frac{p}{1-p} = q$ .
  
  If $p = \frac{1}{6}$ , we obtain that $q = \frac{1}{5}$ for the game to be fair. This probability is not translated into “events” involving tossing dice. However, if $p = \frac{1}{3}$ , we obtain that $q = \frac{1}{2}$ , and now the events are easy to devise: A will toss the die and win if he gets a 4 or a 5, while B will win if he gets a 4, 5, or 6 (for instance).
  
  I will continue my reply tomorrow. I am kind of sleepy right now…
Badal Joshi Says:
May 18, 2009 at 7:26 pm | Reply
Great, I didn’t expect such a quick response. I should add that the first two are trivial even if interesting. I have no idea if the third question even has a solution.

Would you mind if I continued this thread of problems on my blog?
- Rod Carvalho Says:
  May 18, 2009 at 8:25 pm | Reply
  Yeah, 1) and 2) are easy, high-school kind of problems. 3) sounds much more challenging indeed. I will think about it when I find some time.
  
  I don’t own the “patent” of this problem! Hence, feel free to blog about it if you want. I have subscribed your RSS feed, so I will be informed if you write any post about it. I might write a new post on the problem you proposed. As soon as I am done with finals…
Badal Joshi Says:
May 20, 2009 at 6:56 pm | Reply
Hi, I did end up posting yesterday.

http://thesquaredcircle.wordpress.com/2009/05/20/are-you-game-part-i-fair-game/

I referred to this page a couple of times, I don’t know if there should be an echo in the comments here or a pingback, but I couldn’t see it.

Rod Carvalho's web notebook

Rolling dice

9 Responses to “Rolling dice”

Leave a Reply