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