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 D1Steps are taken in sequential order unless a GOTO command is invoked. How many total dice rolls are performed in expectation?

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

## 7 comments:

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

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

What if D1=1 and D2=1?

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

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

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

That is correct =)

Post a Comment