Probability Question?

Let U(x,y) denote the probability that A wins if A is x steps away from finishing point and B is y steps away from finishing point.

The induction relation between the U(x,y)'s can be obtained using the probabilities given by Michael. One gets

U(x,y) = (1/30) * (U(x-5,y) + U(x,y-5) + 2U(x-4,y)+2U(x,y-4)

+ 3 U(x-3,y) + 3U(x,y-3) + 4U(x-2,y) + 4U(x,y-2)

+5U(x-1,y)+5U(x,y-1) ) .

You have the boundary conditions U(x,y) = 1 if x <= 0, meaning A has won if he reached the finishing point first and U(x,y) = 1 if y <= 0. In general U(x,y) + U(y,x) = 1.

You want to compute U(18,24). The only analytical way to do this is to use the induction relation to compute U(x,y) for all x, y such that x<=18, y<= 24 and of course (x,y) not (18,24).

So you can compute U(1,y) for all y less than 24, by induction on y, then U(2,y) for y <= 24, all the way till U(18,y) for y <= 24.

Nothing a computer can't do =)

I wonder if the game is isomorphic to another with only one player so that the player wining corresponds to B winning. For example, if x > y, the player moves backward x - y and otherwise moves forward y - x, or simply he moves forward y - x where a negative number means backwards.

If he moves backward 18 steps, in total, he loses. If he moves moves forward 24 steps, in total, he wins.

Just a thought; i could very likely be going nowhere.

EDIT:

Roll two dice obtaining (x, y). The sample space is of size 36. Let A_n be the event that y - x is n where n = -5, . . ., 5. Then P[A_n] = (6-|n|)/36. (This is like what Michael did). This is the only information we can get for just one turn (I think), so move on.

Suppose a game takes N turns. Can you find the probability that he won in these N turns? If you can find it as a nice function, the infinite series of the function should win us the game since all the possible wins are mutually exclusive .

We could set this up as a DTMC with the possible states being (a,b), where a = 6, 7, ..., 24 and b = 0, 1, ..., 24. That's a total of 19*25 = 475 different possible states. This would yield a probability matrix with dimension 475x475. While we have the necessary probabilities to set this up, that's rather large... I don't want to go through the effort of putting that together.

Edit: I ran a simulation in Excel with over 54000 runs of the game. If you accept the rand() function as being sufficiently random (which in Excel is questionable), I get a probability of .296 that player B wins. That seems about right, I'd still like to see a more analytic strategy!

Probability that a fixed player moves n steps:

1 steps: 6-5,5-4,...,2-1 ; 5/36

2 steps: 6-4,...,3-1 : 4/36 = 1/9

3 steps: 3/36 = 1/12

4 steps: 2/36 = 1/18

5 steps: 1/36

But i am stuck now, too many possibilities and can't think of a shortcut :\

@J Kariya: well the problem is that there are so many possibilities ...

Edit:

So for fun I ran a simulation as well, after 10mio games I get

A : win in about 69.99% and an average of 17.66 rolls

B : win 30.01% and 19.79 rolls.

Edit2:

I try to explain why we need fewer rolls then expected.

We only count the rolls when A wins. But if he wins it is reasonable to expect that he probably "had a bit of luck" and thus did better then the expected value.

Let's look at an extreme example.

Each player get's points per throw and they throw at the same time.

A has 14 points

B has 0 points.

18 to win.

the only way to win for B is throwing 3 sixes and A only getting ones.

thus B will have an average of 6.

I also did a simulation and got similar results.

I used Perl and I have found that its random number function is very good.

A won 70.6% of the time and on average it took 16.7 rolls

B won 29.4% of the time and on average it took 18.8 rolls

I thought it would take more rolls, based on calculating the

average advance (for either player) to be

(5*1 + 4*2 + 3*3 + 2*4 + 1*5) / 36 = 35/36 spaces.

Why don't calculate the probabilities directly in a single run? That's MUCH more reliable than simulating an excessive number of random examples.

By the way, from your results you can guess the number of unique possible games is to be the order of 36^20. Even if you do 10^9 simulations, you can't possibly explore any significant part of this database!

[C]

int main() {

double fld[2][18][24];

double pa, pb;

double ava, avb;

int n,i,j,k;

fld[0][0][0] = 1;

pa = pb = 0;

ava = avb = 0;

for(n = 1; n < 42; n++) {

memset(fld[1], 0, sizeof(fld[1]));

for(i = 0; i < 18; i++)

for(j = 0; j < 24; j++) {

for(k = 1; k <= 5; k++) {

if(i+k >= 18) {

pa += (6-k)/30.0*fld[0][i][j];

ava += (6-k)/30.0*fld[0][i][j]*n;

}

else fld[1][i+k][j] += (6-k)/30.0*fld[0][i][j];

if(j+k >= 24) {

pb += (6-k)/30.0*fld[0][i][j];

avb += (6-k)/30.0*fld[0][i][j]*n;

}

else fld[1][i][j+k] += (6-k)/30.0*fld[0][i][j];

}

}

memcpy(fld[0], fld[1], sizeof(fld[0]));

printf("%f : %f\t[%f]\n", pa, pb, pa+pb);

}

printf("Average number of rolls: %f : %f\n", ava/pa, avb/pb);

return 0;

}

There's probably some typo in my program as I get quite different numbers than you:

0.703865 : 0.296135[1.000000]

Average number of rolls: 13.942861 : 15.716435

If anyone finds it, please tell me.

Edit: The average number of rolls in my output is different than yours as I threw away the cases where both players stay and renormalized the probabilities. Multiplying by 6/5, we get corresponding results in the original game as follows:

Average number of rolls: 16.731433 : 18.859722

Edit2: gianlino's method gets the probability in an even more elegant way and (as far as I can tell) confirms my result of 0.296135 for B. A function similar to U can be found to compute the average number of rolls, too.

Thanks Michael. Now cut those prob in half and assign them to each person.

Now use those probabilities to setup all the scenarios of when player B moves 24 or more and player A moves 17 or less steps. Add them together and there you go.

Player A's a craps shark, and has a rigged die. There-fore, player B has no chane of winning

the ? is im possible