Dice

EamonnKeane

Imagine a game where players roll three dice, scoring one point whenever they get 2 matching numbers. First to 10 points wins; if all three dice show the same number a player wins instantly. How many turns should it take, on average, to win?

hivizman

I'm not entirely convinced by this, but I'd calculate the expected number of turns as follows:

There are 6*6*6 = 216 possible outcomes of throwing three dice. 120 of these (6*5*4) give all three numbers different, 90 of these (6*5*3 - the "odd" dice can be the first, second or third dice thrown) show a pair of matching numbers, and 6 show all three numbers the same. If you throw three different dice, you score 0 points, for a pair you score 1 point and for three the same you score 10 points. Your expected score in a single turn is thus (120*0 + 90*1 +6*10)/216 = 0.69444. So you get a score of 10 you would need on average 10/0.69444 turns, that is, 14.4 turns.

I don't think this is correct because, if you change the number of points allocated to a three-of-a-kind throw, you change the expected number of points per turn and hence the expected number of turns to get to 10 points. However, the game stops when you throw three-of-a-kind, however many points you allocate to this (equal to or greater than 10). So the solution should be invariant.

Anyone out there with a better grasp of probability?

hivizman

I've now done a tedious calculation of the probabilities of all the different paths that the game can take in getting to the end, and this shows that the expected number of turns is 17.11942. By the way, the original poster did not specify the number of players in the game, so I've assumed a single player.

Fremen

I was thinking about this too, I couldn't think of a decent way to do it other than grinding it out.

You can often use martingale theory to solve problems like this. I wonder if there's an application here. Maybe I'll ask the guys at wilmott.com...

niallo1

Got answer of

most likely : 19 turns
average turns: ~ 50

by combining two neg binomials p1 = 17/36, p2=1/36 done by simulation

a bit doubtful about it tho

hivizman

p1 should be 15/36. There are 6 ways of selecting the "paired" number and that leaves 5 ways of selecting the "unpaired" number. However, the "unpaired" dice can be the first, second or third of the three dice, so there are 6*5*3 = 90 possible combinations out of 6*6*6 = 216 with a pair of numbers the same. 90/216 = 15/36.

I calculated that the most likely number of turns is 20, but that doesn't mean much, because the probability that the game ends on the 20th turn is only 0.0528. An average number of turns of about 50 doesn't make intuitive sense, because if we ignore the fact that the game ends when three of a kind are rolled, and just treat this as a throw of a pair scoring one point, the expected number of points in each round is 15/36 + 1/36 = 16/36 = 4/9, so we would expect to get 10 points after 10/(4/9) = 22.5 rounds. Hence, as the treatment of three-of-a-kind rolls means that it is possible to win more quickly than under this scenario, the expected number of rounds must be less than 22.5.

I reran my Excel spreadsheet on the basis that a pair and three-of-a-kind both score 1 point and it yielded an expected number of rounds of 22.5. So this makes me more confident of my earlier calculations.

MathsManiac

I got 4705751134359/274877906944, which is approximately 17.11942290, in agreement with hivizman.

I treated it as a Markov process with 11 states, one of which is absorbing. The right transition matrix has 5/9 on the diagonal, (except the 1 at the end), 5/12 immediately above the diagonal (except in the last column) and the last column has 1/36 for the fist nine entries, followed by 4/9 and 1.

Taking the sub-matrix of the transient states as Q, you can calculate the inverse of (I-Q) and multiply it by a column of 1's to get the average time to absorbtion from any state. In particular, the first entry gives time to absorption from the initial state, which yielded the above result.

(I did the matrix-crunching in Maple).

And, like others above, I couldn't see a neater way to do it.

niallo1

Hivizman, Maths maniac:

just wondering if your methods take into account the probability that the game could be over after 1 'turn'?


Hivizman:

I agree "An average number of turns of about 50 doesn't make intuitive sense" and hence my doubt about the answer. Also agree with your logic "the expected number of rounds must be less than 22.5"

As regards p1

I got p1 = 6*(1/36)+6*(1/36)+6*(1/36) -6*1/(6*6*6)

i.e. 3 ways of getting two matches minus prob of matching 3

Retried it with your suggestion of 15/36 and got answer of 22 (for most likely with prob 0.087)

hivizman

MathsManiac wrote: »

I got 4705751134359/274877906944, which is approximately 17.11942290, in agreement with hivizman.

I treated it as a Markov process with 11 states, one of which is absorbing. The right transition matrix has 5/9 on the diagonal, (except the 1 at the end), 5/12 immediately above the diagonal (except in the last column) and the last column has 1/36 for the fist nine entries, followed by 4/9 and 1.

Taking the sub-matrix of the transient states as Q, you can calculate the inverse of (I-Q) and multiply it by a column of 1's to get the average time to absorbtion from any state. In particular, the first entry gives time to absorption from the initial state, which yielded the above result.

(I did the matrix-crunching in Maple).

And, like others above, I couldn't see a neater way to do it.

I suspected that you could treat it as a Markov process, but I didn't do these when I studied probability many years ago. Mathematically, though, this is basically isomorphic to my tedious number-crunching on Excel, but much more elegant!

For niallo1, yes, both my Excel spreadsheet and MathsManiac's Markov transition matrix take into account the fact that the game can finish on any turn if a three-of-a-kind is thrown, and, from turn 10 onwards, if the score at the end of the previous round was 9 and a pair is thrown. I'm attaching, all being well, my Excel spreadsheet.

Fremen

Elegant solution by the scarily talented "quantyst" at wilmott.com:

it would be much clearer and easier to answer the following question, instead the one posed:

How many turns, on average, does player P (either the first or the second player) take before the game ends assuming player P wins the game?

Let’s answer the preceding question:

Let each die be a d-sided die. Let X(i), Y(i), Z(i) denote three independent and identical random variables uniformly distributed over the set {1,2, …,d}, as i runs through the set of natural numbers. So X(i), Y(i), Z(i) represent, respectively, the rolled numbers on the first, second, and third die on the i-th turn.

Dropping the index i, we’d like to find the probability P{X=Y=Z} on a turn. There are a total of d^3 triplets (x,y,z) in the set (1,2, …,d}^3, of which there are precisely d triplets in each one of which x=y=z. So, P{X=Y=Z} = d/(d^3) = 1/(d^2).

Now let’s find P{(X=Y or X=Z or Y=Z) & !(X=Y=Z))} = P{(X=Y!=Z) or (X=Z!=Y) or (Y=Z!=X)}. But the three events (X=Y!=Z), (X=Z!=Y) and (Y=Z!=X) are mutually exclusive and equally likely. So,

P{(X=Y!=Z) or (X=Z!=Y) or (Y=Z!=X)} = P{X=Y!=Z} + P{ X=Z!=Y } + P{ Y=Z!=X } = 3*{(d-1)/(d^2)}.

Let s denote the score to reach in order to win the game, and let E(s) denote the expectation of the number of turns player P takes before s/he wins. It is clear that if s=0, then E(s)=E(0)=0. So, assume s>0. So, player P rolls the three dice in his/her first turn. Exactly one of the following will happen:

(1) A={ X=Y=Z} with P{A}=1/(d^2),

(2) B={(X=Y!=Z) or (X=Z!=Y) or (Y=Z!=X)} with P{B}=3*{(d-1)/(d^2)},

(3) C=!{A or B} with P{C}=1 - (P{A} + P{B}) = 1 - {1/(d^2) + 3*{(d-1)/(d^2)}}.

So,

E(s) = 1 + (A: game ends)*P{A} + (B: 1 point is gained)*P{B} + (C: player P tries anew)*P{C}.

So,

E(s) = 1 +(0)*P{A} + (E(s-1))*( 3*{(d-1)/(d^2)}) + (1 - {1/(d^2) + 3*{(d-1)/(d^2)}})*E(s).

Simplifying the preceding, we get:

E(s) = {(d^2)/(3d-2)} + {3(d-1)/(3d-2)}*E(s-1).

Solving the preceding, we get:

E(s) = (d^2)*{1 - {(3d-3)/(3d-2)}^s}.

So, letting d=6 and s=10, we get:

E(10) = 17.119422.

So, player P takes about 17 turns on average to win the game assuming s/he wins.

Doubling this number will give the average number of turns in the game before it ends.

MathsManiac

Indeed, and 'twould be more elegant if not couched in such user-unfriendly language!

This is precisely the kind of elegant solution I suspected should exist, involving a recurrence relation, but I was unsure of the territory involved in the step:

E(s) = 1 + (A: game ends)*P{A} + (B: 1 point is gained)*P{B} + (C: player P tries anew)*P{C}.

I also wonder whether there's some legitimate way of combining the expected time to finish if the game consisted only of the "doubles" rule (i.e. 22.5) with the expected time if only the triples rule existed (i.e. 36) to get the answer, but I can't see it.

hivizman

MathsManiac wrote: »

Indeed, and 'twould be more elegant if not couched in such user-unfriendly language!

This is precisely the kind of elegant solution I suspected should exist, involving a recurrence relation.

Also good that it's a general solution for dice with any number of faces and for any required points score to win.

By the way, the discussion on Wilmott.com, which also includes the Markov transition matrix, is here.

MathsManiac wrote: »

I also wonder whether there's some legitimate way of combining the expected time to finish if the game consisted only of the "doubles" rule (i.e. 22.5) with the expected time if only the triples rule existed (i.e. 36) to get the answer, but I can't see it.

I don't see it either. I think that it's the fact that a triple wins the game whatever the previous score was that complicates things - this was what threw out my original calculation of 14.4 turns.

EamonnKeane

thanks everyone; i had guessed it was about 21