Probability Question?

Two players A & B roll a fair die simultaneously, say player A gets x & player B gets y. Only the player with greater number will move |x-y| steps ahead (in case of x=y, no one will move).Currently Player A is 6 steps ahead of player B but 18 steps away from the finishing point, find the probability of Player B wining the game.

Update:

Thanks for all the answer so far. I was out of town so could not communicate.

@Todd ,Mathman & Michael:

Yes your results are matching with mine. In fact I did this on Pari/GP & Mathematica and with about 10^9 run I got probability very close to 30% for B with average 19.98 rolls.

As Mathman rightly said I also thought it should take more rolls based on average advance. That's why I suspected my result and wanted to verify. With such clean answer (approaching 30%) I am sure analytical solution must exist, but not sure how to proceed.

Update 2:

Todd: I am not sure how Discrete Time Markov Chain can help in this question

Update 3:

@Todd: As a general remark, as far as I know Excel 2003 onward the rand() implementation has passed Diehard test & NIST test but It has not yet passed TestU01 Crush test. Thus it is much better now and will give reliable results for 10^13 random sequences.

Update 4:

Gianlino: If you notice my comment "With such clean answer (approaching 30%) I am sure analytical solution must exist, but not sure how to proceed." indicates that I would like to know analytical solution which only math section can give, sometimes bottom up approach works the best along with analytical thinking.

Here is the best example http://answers.yahoo.com/question/index?qid=200901...

Update 5:

Gianlino that's what I meant by combined approach. Thanks setting up markov chain

Vasek: Thanks for your programmatic implementation. (I made typo in my earlier comment where I noted 19.98 as avg rolls it was 18.98. I think noise in my answer was different due to excessive number of trials)

I doubted my answer more because , I could not believe that on an average Player B would require only additional 2 steps.

Update 6:

Great contributions so far, will keep this open for a day, just in case some one has something more to share.

9 Answers

Relevance
  • 9 years ago
    Best answer

    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 =)

  • Anonymous
    9 years ago

    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 .

  • Todd
    Lv 6
    9 years ago

    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!

  • 9 years ago

    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.

  • What do you think of the answers? You can sign in to give your opinion on the answer.
  • 9 years ago

    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.

  • 9 years ago

    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.

  • 9 years ago

    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.

  • 9 years ago

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

  • 9 years ago

    the ? is im possible

Still have questions? Get answers by asking now.