wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Throwing All Numbers From 2 to 12
        
(Message started by: ThudanBlunder on Jul 11^th, 2008, 7:35pm)

Title: Throwing All Numbers From 2 to 12
Post by ThudanBlunder on Jul 11^th, 2008, 7:35pm

What is the expected number of times one must throw two dice before all numbers from 2 to 12 have appeared?

Title: Re: Throwing All Numbers From 2 to 12
Post by towr on Jul 12^th, 2008, 4:44am

You could use the 2¹¹x2¹¹ transition matrix (http://en.wikipedia.org/wiki/Transition_matrix) to get the answer.
Hopefully there's an easier way, though.

Title: Re: Throwing All Numbers From 2 to 12
Post by Eigenray on Jul 12^th, 2008, 5:44am

I get [hide]769767316159/12574325400[/hide]:

[hideb]-36*Sum (-1)^|S|/sum(S)
over all nonempty (multi-)subsets S of {1,2,3,4,5,6,5,4,3,2,1}.[/hideb]

Can we evaluate this in polynomial time (in the number of faces)?

Title: Re: Throwing All Numbers From 2 to 12
Post by towr on Jul 12^th, 2008, 6:14am

on 07/12/08 at 05:44:13, Eigenray wrote:

I get [hide]769767316159/12574325400[/hide]

I get a lower number in simulation: about [hide]45[/hide]. And as these things go, I'd almost suspect it's a nice round number.

Title: Re: Throwing All Numbers From 2 to 12
Post by Eigenray on Jul 12^th, 2008, 7:30am

My simulation agrees with my answer:

Code:

int main () {
int got[11];
int i,t,n,g;

for(t=n=0; ; n++) {
for(i=0; i<11; i++) got[i]=0;
for(g=0; g<11; t++) {
i=rand()%6+rand()%6;
if(!got[i]) {
got[i]=1; g++;
}
}
printf("%f\n",1.*t/n);
}
}

Title: Re: Throwing All Numbers From 2 to 12
Post by ThudanBlunder on Jul 12^th, 2008, 8:00am

on 07/12/08 at 06:14:27, towr wrote:

I get a lower number in simulation: about [hide]45[/hide]. And as these things go, I'd almost suspect it's a nice round number.

But even with one die it is 14.7, not a very round number.

on 07/12/08 at 07:30:48, Eigenray wrote:

My simulation agrees with my answer:

Then your simulation must be correct. :D A few years ago, I chucked this to the piranhas on sci.math (http://mathforum.org/kb/message.jspa?messageID=543085&tstart=0).

Title: Re: Throwing All Numbers From 2 to 12
Post by Eigenray on Jul 12^th, 2008, 8:46am

I got my answer using [hide]inclusion-exclusion[/hide]. Actually, that sum can be computed in O(n³) time with dynamic programming.

If E(n) is the expected number of throws for a pair of n-dice, it looks like E(n)/n² converges to around 1.702955978958. What is this number?

What if we simplified it a bit: suppose the probability of rolling k is directly proportional to k, 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n. Show that the expected time E(n) to obtain all values from 1 through n satisfies

limit E(n)/n² = 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 - 3. ;D

Title: Re: Throwing All Numbers From 2 to 12
Post by towr on Jul 12^th, 2008, 10:10am

on 07/12/08 at 08:00:41, ThudanBlunder wrote:

But even with one die it is 14.7, not a very round number.

Well, it's not too bad; at least it's a finite decimal.

on 07/12/08 at 07:30:48, Eigenray wrote:

My simulation agrees with my answer:

Hmm :-/ I'll have to think about what was wrong with mine then (I did it in javascript and ran it in the location-bar, so I don't actually have the code anymore). But it was exactly the same approach.

Title: Re: Throwing All Numbers From 2 to 12
Post by mattian on Jul 23^rd, 2008, 8:12am

The answer to this could be useful in determining the worst case domain of the 100 prisoners/lightbulb problem.