wilmott.com

a regular dice with equal probability 1/6 for each side, throw it repeatly and accumulate the results. Game stops when accumulated number reaches 15 or above... what is the probability of the accumulated number is 17anyone can suggest a analytic solution for thisthanks

MC simulation returns something like 19.11% ... will think about a formula.

YES.... That's what i got as well0.19121458.......

denote s as the accumulated sum, and p(s) as the probability reaching s. we have the following recurrence relation:p(s)=[p(s-1)+p(s-2)+p(s-3)+p(s-4)+p(s-5)+p(s-6)]/6this is easy to prove by considering the result of the last toss. the initial condition is p(0)=1, p(-1)=p(-2)=p(-3)=p(-4)=p(-5)=0, since you start with 0 for definite.what we want is p( s=17 | last toss>=3 ) = [p(11)+p(12)+p(13)+p(14)]/6.one standard way is to set p(s)=x^s. one ends up with 6x^6-(x^5+x^4+x^3+x^2+x+1)=0. denote x1,x2,...,x6 as the 6 roots of this equation (apparently one root is 1; there is another real root ~-0.67, and four complex roots, but there is no closed-form for that real root. this is due to the fact that the degree of the polynomial is above 4)so p(s)=a1(x1^s)+a2(x2^s)+...+a6(x6^s), where a1,a2,...,a6 are constants determined by the initial condition. i think it is doable via Viete's formulas, but not sure.for this problem, since the number is small, you might just follow the recursion. i used mathematica, and got 89885748289/6^15~0.191171

From MC I get P(Sum=17) = 0.19122I also get E(# of throws to exceed 14) = 4.7606

QuoteOriginally posted by: wileyswdenote s as the accumulated sum, and p(s) as the probability reaching s. we have the following recurrence relation:p(s)=[p(s-1)+p(s-2)+p(s-3)+p(s-4)+p(s-5)+p(s-6)]/6this is easy to prove by considering the result of the last toss. the initial condition is p(0)=1, p(-1)=p(-2)=p(-3)=p(-4)=p(-5)=0, since you start with 0 for definite.what we want is p( s=17 | last toss>=3 ) = [p(11)+p(12)+p(13)+p(14)]/6.one standard way is to set p(s)=x^s. one ends up with 6x^6-(x^5+x^4+x^3+x^2+x+1)=0. denote x1,x2,...,x6 as the 6 roots of this equation (apparently one root is 1; there is another real root ~-0.67, and four complex roots, but there is no closed-form for that real root. this is due to the fact that the degree of the polynomial is above 4)so p(s)=a1(x1^s)+a2(x2^s)+...+a6(x6^s), where a1,a2,...,a6 are constants determined by the initial condition. i think it is doable via Viete's formulas, but not sure.for this problem, since the number is small, you might just follow the recursion. i used mathematica, and got 89885748289/6^15~0.191171Just thought I might mention that there is another standard method to doing this sort of linear recursion problems. And that is we form a matrix equation of the form X(s)=A*X(s-1) as follows:Let a(s)=p(s), b(s)=p(s-1)=a(s-1), c(s)=p(s-2)=b(s-1), d(s)=p(s-3)=c(s-1), e(s)=p(s-4)=d(s-1), f(s)=p(s-5)=e(s-1).Now let X(s)=[a(s) b(s) c(s) d(s) e(s) f(s)]`, where ` denotes transpose.And let the matrix A be defined as follows:A=[1/6 1/6 1/6 1/6 1/6 1/6 1 0 0 0 0 00 1 0 0 0 00 0 1 0 0 00 0 0 1 0 00 0 0 0 1 0].Then X(s)=A*X(s-1). So, X(s)=(A^s)*X(0)where X(0)=[1 0 0 0 0 0]`.

I have an aproximation to the dice problem that its aproximate to result of doing a MC (0.19..... )If you play infinite times the expected value of sum of four tosses is close to 14. Now you are down to one more toss. To get 17 you can only toss a 3 because if you toss less than that (1 or 2) you get 15 o 16 and the game is over, and if you toss higher the game is also over so you need exactly 3. the probability of tossing a 3 is (1/6) which is 16.666%. 16.66% its not so far from 19.0....% of the MC.HOPE TO HEAR ANSWERS

You can also solve the probability of the Markov chain explicitly using matrix notation. We can define an initial distribution m, and a transition probability to matrix P to represent the evolution of the sum from dice roll to dice roll. The problem's state space is the values {0,1,2,...,20}.Define the initial distribution m as a row vector with weight 1 at the state 0.Define the transition matrix P as follows: = 1/6 if i < 14 and 0 < j - i < 6 = 1 if 15 <= i = j <= 20 = 0 otherwise.p = m* is a measure where defines the probability of being in state i after the n^th roll, i.e. the sum of the rolls is i after n rolls, with probability .Since the chain is guaranteed to stop in 20 steps, m* gives the distribution of final states of the Markov process.This seems a bit inefficient since you're powering a 21x21 matrix, but since it's sparse and diagonalizable, you can solve this pretty efficiently. I haven't crunched the numbers explicitly, but that's the general idea.

This can actually be very easy if you simply count all the possibilities. At any point in the game, if the accumulated number is 9, there is only one way for the game to stop and that is when the next toss returns 6. If the present accumulated number is 10, there are only two ways for the game to stop at the next throw (when the die returns 5 or 6). Likewise, if at any point the sum of dice rolls is 11, 12, 13 or 14, there are three, four, five and six ways for the game to stop at the next stage. Then the total number of possible ways by which the game will stop is 1+2+..+6=21. But, of these, only four cases result in the accumulated value 17. They are specifically 11+6, 12+5, 13+4, 14+3. So I believe the answer is 4/21 = 0.19047619, which is most likely the exact answer.

How do you guarantee your 21 ways are equally likely? The answer may happen to be right, although unlikely.

Doesn't each of the 21 ways depend on a single roll? Aren't these equally likely by assumption?

for the last single roll, yes, they are equally likely, but the probability of reaching different accumulated sums earlier, e.g., 11 and 12, are different.falsepositive's answer in formula is: [p(11)*1/6+p(12)*1/6+p(13)*1/6+p(14)*1/6]/[p(9)*1/6+p(10)*2/6+p(11)*3/6+p(12)*4/6+p(13)*5/6+p(14)*6/6].(note the denominator is simply 1 given the recurrence relation)if p(9)=p(10)=...=p(14) then it reduces to 4/21, which is indeed the probability to reach N+2 as the game ends when the accumulated sum >=N (with N->infty). however, when N is finite (15 in the original problem), these probabilities are not equal.the exact answer is given above: 89885748289/6^15, but i guess for an interview, ~4/21 should be the best answer.