Imagine you are playing the following die game against 1 player: He gives you N dollars, and you throw a die 6 times. If you get all the six numbers you win the N$. Otherwise, you have to pay the player 7$ then throw the die. You continue till having all the six numbers, and at every step k you have to paye k$ to continue (if you have thrown the die 11 times and you dont have all the six numbers, you pay him 12 to continue) How many $ you will ask to play this game?

rollthe6[runs_] := Module[{k, unlist}, Table[k = 0; unlist = {}; While[unlist != Range[6], k++; unlist = Union[unlist, {RandomInteger[{1, 6}]}]]; k, {runs}]];Timing[rolls = rollthe6[100000];]{13.656, Null}N[{Mean[rolls], Min[rolls], Max[rolls]}]{14.7, 6., 91.}N=14.7

I dont think so14.7 is the average number of throws to get all the six numbersHere you pay 7 at the seventh level, 8 at the eighth tevel....N at the Nth levelIntuitively, this numer must be about (7+8+9+10+11+12+13+14) which is much more greater than 14.7

i get around 72

I dont think so daveangelLet N be the number of throws to get all six numbers. The probleme is about calculating (E(N(N+1)/2)-21) which is greater than ((E(N)²+E(N)/2)-21)MCarreira reminds that E(N)=14.7, so what we are calculating must be greater than 94.395I find (using a closed formula) 113.89

Sorry, you are correct. The correct function is:rollthe6[runs_] := Module[{k, unlist}, Table[k = 0; unlist = {}; While[unlist != Range[6], k++; unlist = Union[unlist, {RandomInteger[{1, 6}]}]]; If[k > 6, Total[Range[7, k]], 0], {runs}]];N[{Mean[rolls], Min[rolls], Max[rolls]}]{113.617, 0., 2754.}

Or:trmat={{1/6, 5/6, 0, 0, 0, 0}, {0, 1/3, 2/3, 0, 0, 0}, {0, 0, 1/2, 1/2, 0, 0}, {0, 0, 0, 2/3, 1/3, 0}, {0, 0, 0, 0, 5/6, 1/6}, {0, 0, 0, 0, 0, 1}};T = Transpose[Most[Transpose[Most[trmat]]]]{{1/6, 5/6, 0, 0, 0}, {0, 1/3, 2/3, 0, 0}, {0, 0, 1/2, 1/2, 0}, {0, 0, 0, 2/3, 1/3}, {0, 0, 0, 0, 5/6}}initvec = {1,0,0,0,0,0};Tau = Most[initvec]{1, 0, 0, 0, 0}exptime = 1 + Tau.Inverse[IdentityMatrix[5] - T].ConstantArray[1, 5]147/10T0 = ConstantArray[1, 5] - T.ConstantArray[1, 5]{0, 0, 0, 0, 1/6}f[k_] := Tau.MatrixPower[T, ((k-1) - 1)].T0; (distribution of expected time, adjusted for initial state = 1 round)f[6] = 5/324 = 6!/(6^6)sumap[k_] := (k + 1 - 7) (7 + k)/2;answer = Sum[sumap[k] f[k], {k, 7, Infinity}]11389/100N[answer]113.89

QuoteOriginally posted by: montecristoI dont think so daveangelLet N be the number of throws to get all six numbers. The probleme is about calculating (E(N(N+1)/2)-21) which is greater than ((E(N)²+E(N)/2)-21)MCarreira reminds that E(N)=14.7, so what we are calculating must be greater than 94.395I find (using a closed formula) 113.89Any chance you can explain how you got E(N(N+1)/2 - 21) a bit further? (or point me to a reference?) Thanks!

basically one needs to exploit the linearity of expectation:http://en.wikipedia.org/wiki/Coupon_collector's_problem

ynotredrum:To see why do we have to calculate E(N(N+1)/2 - 21) , think about a Monte Carlo estimation: On every path i, you need N(i) throws to get all the six numbers. After N(i) throws, you pay (7+8+...+N(i))$, which is equal to N(i)(N(i)+1)/2 - 21 . Taking the average, you get the expectation below.

A harder questionCan anyone generelize the probleme to n dimension? i.e. : you are playing a lotery where the result is a random number between 1 and n (uniform distribution). You play without paying n times, but you have to continue untill you have all the n numbers, and at every step k you pay k$. How much are you going to pay in average?

For k dimensional problem, the momentum generation function can be given by hence, we can have the E(n) and E(n^2).

this is to generalize what we got from quantyst's other problem:(to include the case of an unfair dice, and all the higher moments of the waiting time)consider arbitrary m distinct faces (indexed by i=1, 2, ..., m) of an "M-face dice" (m<=M). the probability of each face coming up is p_i. denote N the average number of rolls till all these m faces show up. we have:for any non-negative integer n.for the special case of a fair dice and m=M (so p_1=p_2=...=p_m=1/m):

Being T the r.v of the time end of game and N the value requested with a 6-face dice,p=1/6,The probability of the game to end an roll t=y is probability of pick up 5 six in y-1 rolls (binomial) and 1 six at roll y.E(T)=36,E(N)=735