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?

7 comments:

Daniel said...

Hi Yisong,

That's a cute puzzle. Here's a related one due to Terry Tao:
http://www.google.com/buzz/114134834346472219368/8ppicXTgo3r/Suppose-one-needs-to-accomplish-n-tasks-These

Daniel

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:
x=(1+x)/3+(2+x)/3+2/9+(2+x)/9
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:
x=(1+x)/3+(2+x)/9+4/9+2/3
so
x=3

Yisong said...

That is correct =)