All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
'Snake-Eyes ' Joe (Posted on 2008-07-28) Difficulty: 3 of 5
"Snake-Eyes" Joe introduced a die of his own into a game of chance.

He was subsequently challenged that the die was biased.

Very rigorously test to see if there are grounds to substantiate this claim; don't accept just two or three trial runs. Are you able to offer a theoretical model consistent with your findings?

Test "Snake-Eyes" Joe's Die with this simulator which has a run of 60,000 at a time:

Scores 0 0 0 0 0 0 0

Note: the data changes with each subsequent mouse-over visitation to the link.

See The Solution Submitted by brianjn    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
re: Let there be No Random | Comment 12 of 13 |
(In reply to Let there be No Random by brianjn)

To explain a little bit more, we consider 11 different states, based on the value of the counter tn. The transition matrix A is given by A(i,j) = probability of moving from state j to state i in one roll. This is convenient because then the probability of moving from state j to state i after n rolls is just the (i,j)-th entry of A^n, and we can take powers of matrices fairly easily.

For all i, we stay at state i when we roll any number other than a 1, so A(i,i) = 5/6. For i<10, we move from state i to state i+1 when we roll a 1, so A(i+1,i) = 1/6. If we're in state 10, however, there are three possibilities:
roll non-1, stay in state 10: A(10,10)=5/6.
roll 1, then a non-1, go to state 0: A(0,10)=5/36.
roll two 1s, go to state 1: A(1,10)=1/36.

Now initially, we are in state 0, so the probability P_n(i) of being in state i after n rolls is the i-th entry of A^n * P_0, where P_0 is the initial probability vector P_0 = (1,0,0,0,0,0,0,0,0,0,0).

Finally, we record a 1 whenever we roll a 1, except for when we are in state 10, and we roll a 1 then a non-1, which happens with probability 5/36 times the probability that we were in state 10. So E_{n+1} = E_n + 1/6 - 5/36*P_n(10). Letting D_n = E_n - n/6, we can write this as
D_{n+1} = D_n - 5/36*P_n(10).
So if we expand our 11x11 matrix A to be 12x12 by adding:
A(11,10) = -5/36
A(11,11) = 1,
then D_n is the last entry of A^n * P_0.

A^n can be computed with O(log n) matrix multiplications, so we can easily calculate D_n now. Closed form is trickier. Powers of A can be computed in 'closed form' by putting A into Jordan normal form, since then powers are easy. The eigenvalues of A are distinct except that 1 has multiplicity 2. So the entries of A^n are all linear combinations (with constant coefficients) of 1, n, and r_i^n, where r_1,...,r_10 are the non-1 eigenvalues of A.

So in particular, we have that
D_n = a*n + b + sum c_i r_i^n,
for some constants a,b,c_1,...,c_10. Now, since E_n = D_n + n/6 ~ 2n/13, we have that a = 2/13-1/6 = -1/78. We also know that D_n=0 for n=0..10. Therefore we have the following system of 11 equations with 11 unknowns:

b + sum c_i * r_i^n = n/78, n = 0..10.

I'm pretty sure b = 66/169 (no proof, but it agrees to 1000 digits). So we have that E(n) - 2n/13 converges exponentially to 66/169. Does anyone have an explanation for this 66/169 term?

For a numerical example, we have
E(100) = 15.778181...,
compared to the approximation
E(100) ~ 2*100/13 + 66/169 = 15.775148...,
and simulations should bear this out (it should only take on the order of 10^5 runs to get 2 decimal places of accuracy).
Edited on August 2, 2008, 5:13 am
  Posted by Eigenray on 2008-08-02 05:07:29

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information