Saturday, March 13, 2010

Dice Rolling Question

I've been spending a lot of time traveling and interviewing these days. While this has prevented me from dedicating sufficient time to writing random ponderings or research blog posts, it has exposed me to a bunch of fun and interesting math problems. So I thought I'd share another one that I encountered recently.

Suppose you had two three-sided dice D1 and D2 (they do exist), and suppose that rolling such a die gives a uniform probability of resulting in 1, 2 or 3. Our rolling procedure proceeds as follows.
Step 1. ROLL D1

Step 2. IF D1=3 GOTO Step 1

Step 3. ROLL D2

Step 4. IF D1=2 AND D2=3 GOTO Step 1

Step 5. STOP
Steps are taken in sequential order unless a GOTO command is invoked. How many total dice rolls are performed in expectation?


Daniel said...

Hi Yisong,

That's a cute puzzle. Here's a related one due to Terry Tao:


Nikos said...

The process will never terminate. To exit the first loop D1 must be 3. To exit the outer loop D1 must be 2.

Yisong said...

What if D1=1 and D2=1?

Nikos said...

Excuse my previous comment, I was somehow reading "not equals" instead of "equals".

Let x be the number of rolls you need in expectation. with probability 1/3 you roll a 3 and have to perform 1+x rolls. with probability 1/3 you roll a 1 and have to perform 2+x rolls. with probability 1/9 you roll a 2 and a 3 and you had to perform 2 rolls. Finally with probability 2/9 you don't roll a 2 and either 1 or 2 and you have to perform 2+x rolls. So:
or x=13/2

Yisong said...

I don't agree with "with probability 1/3 you roll a 1 and have to perform 2+x rolls".

Nikos said...

You are right. I keep making the same mistake of confusing when the loop happens.

A similar calculation to the one I posted before yields:

Yisong said...

That is correct =)