Results 1 to 28 of 28

Thread: Help Me With A Probability Problem

  1. #1
    New Romantic
    Join Date
    May 2003
    Location
    Gone
    Posts
    7,068

    Help Me With A Probability Problem

    I have a probability problem I'm trying to sort out, but it's been a long time since I've done this kind of stuff, so I'm hoping someone here can steer me towards some simple answers for the following scenario.

    I have eight 8-sided dice in various colors. (The colors are irrelevant, but for the sake of this question, let's say they're red, yellow, blue, green, white, orange, purple and gray).

    In each round of the game, I take each die and roll it once. The goal of the game is to eventually roll a 1 with each die. If I roll a 1, that is considered a "hit" and the die is removed from the game.

    In each subsequent round, I roll all the remaining dice, again removing any that come up with a 1. Rounds continue in this manner until I've finally rolled a 1 with each die and there are no dice remaining.

    What I'm trying to sort out is how to calculate the probability of whatever result of I can think of. What are the odds the game ends in the first round? Or the fourth round, or eighth round? What are the odds the game lasts longer than 10 rounds? What are the odds I go 12 rounds and still have 4 dice left?

    I'm not so much looking for answers to the specific scenarios above, but the formula I'd use to calculate those odds. Help me, math wizards!

  2. #2
    How To Go
    Join Date
    May 2006
    Location
    Merriam, KS
    Posts
    10,703
    Since the number of variables changes every time a 1 comes up, you're looking at calculating probabilities of probabilities.

  3. #3
    Social Worker
    Join Date
    Apr 2009
    Location
    Sydney, Australia
    Posts
    3,398
    Your dice are stupid. They're eight-sided and apparently have both colours and numbers on the side. I'm going pretend your example has six sided dice.

    The math you need is all based off one number: the probabilty of the event occurring. In this case, the probability of rolling one particular side with a single dice is 1/6 aka 0.1666. Because I'm lazy, I'll just call this P(event), like P(roll a 1) or P(roll an even number).

    So here's the basic rule: the probability of a series of events happening is their probabilities multiplied together.

    What's the chance of rolling 1 on two dice at the same time? P(roll a 1) is 0.16 as above. 0.16 * 0.16 = 0.0256. So the chance is 2.5%.

    So we have the important number, the basic rule. Now here's the trick: as well as thinking about the probability of an event occurring, you often have to think about the probability of the event not occurring.

    So what's the chance you are rolling two dice, and in the second round you win? Well, there are three possibilities here:
    A) Both dice roll 1 in the second round.
    B) One dice rolls 1 in the first round.
    C) The other dice rolls 1 in the first round.

    A) P(don't roll a 1) is 5/6. So both dice not winning is 5/6 * 5/6 = 0.7 or 70%. And we already figured out the probability of rolling two 1's in a round is 2.5%. So we multiply these together: P(roll two not-1's) * P(roll two 1's). 0.7 * 0.025 = 0.0175 or 1.75%.
    B) So in the first round we need P(roll a 1 and a not-1). That's 1/6 * 5/6 = 0.138 or 13.8%. In the second round, we need the same again, except backwards. 5/6 * 1/6 = 0.138. Now the probabilty of getting both rounds in a row: 0.138 * 0.138 = 0.019 or 1.9%.
    C) Same as B.

    So now we have the probabilities of these three scenarios. Stop! You were going to multiply them together. Actually, we're not looking for the probability of these events in a row. We're looking for the probability of any of these scenarios occurring in one test. For this we simply add up the probabilities. 1.75 + 1.9 + 1.9 = 5.55% chance of the game ending on the second turn.


    Hopefully this explains a bit. There are shortcuts for dealing with probability 'chains' like these, but that's how you do it "by hand". I just noticed I forgot your condition "remove dice that win from the game". Oh well.

  4. #4
    New Romantic
    Join Date
    Aug 2009
    Posts
    7,956
    If you have N dice remaining, the odds of a particular combination of X dice rolling 1 is 7^(N-X) / 8^N. Since you don't care about order, the number of ways to get X dice rolling 1 is N choose X, or N! / (X! * (N-X)!). So for any given round, the odds of getting X hits is:

    N! * 7^(N-X) / (8^N * X! * (N-X)!)

    I don't know of any pretty way of giving the odds of a result on any given round. Rather, you have to do the messy business of working out the odds of each outcome for round 1, and then doing the same thing for round 2, given the scenarios left over from round 1. It's the sort of thing where a spreadsheet is handy.

  5. #5
    New Romantic
    Join Date
    Aug 2002
    Location
    Pennsylvania
    Posts
    6,301
    The probability of rolling 8 aces in one roll is (1/8)^8 = ~0.00000006

    Beyond that it gets harder :)

    Probabilities are generally multiplicative though. The probability of rolling an ace and 7 non-aces is (1/8)*(7/8)*(7/8)*(7/8)*(7/8)*(7/8)*(7/8)*(7/8)= ~0.05

    I think.

    Also check this out:

    http://demonstrations.wolfram.com/DiceProbabilities/

  6. #6
    New Romantic
    Join Date
    Nov 2003
    Location
    Seattle and Charlotte
    Posts
    6,293
    Quote Originally Posted by Gus_Smedstad View Post
    I don't know of any pretty way of giving the odds of a result on any given round.
    At a certain point it's easier and faster to test things empirically than it is to work out the odds -- in fact, working out the odds is often significantly slower than just doing 10000 tests and seeing what happens. There's a free/open source program that does dice roll simulations for RPGs and will also try to work out the odds. I think it had a very remarkable name, like "roll", and it was written in ML or M4 or some other exotic language. Maybe OCaml.

  7. #7
    How To Go
    Join Date
    May 2006
    Location
    Merriam, KS
    Posts
    10,703
    Super-simple extrapolation of probabilities, given 8 count of 8-sided dies:

    First round, 8 dies in play, odds of a 1 being rolled is 1:1.
    Last round, 1 die in play, odds of 1 being rolled is 1:8.

    Therefore, an "average" game will take 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 rounds.

    DISCLAIMER: Above is almost certainly wrong.

    EDIT: Okay, 22 rounds is looking more likely now as a typical duration.
    Last edited by Zylon; 09-04-2011 at 06:07 PM.

  8. #8
    Account closed New Romantic
    Join Date
    Jun 2002
    Location
    Austin, TX
    Posts
    9,901
    What are the odds the game ends in the first round?
    ~0.000006%, or (1/8)^8. You could probably figure that out.

    What are the odds the game ends in the fourth round?
    These types of questions are more difficult. There's only one way the game can end in the first round: you roll all ones. There's several different ways the game can end in the nth round, for instance there's the probability you roll zero ones in the first round, (7/8)^8, and then all ones in the second, which is (7/8)^8 * (1/8)^8. Or you can roll one in the first and seven in the second, or seven in the first and one in the second, and so on.

    If you roll one in the first and seven in the second, it's actually a summation of eight different probabilities: the probability that the first die rolled one in the first round * the probability seven dice roll one in the second round + the probability that the second die rolled one in the first round * that same probability that seven dice roll one in the second round + etc. You may note that the probability for each of those eight scenarios is the same, so the summation is just 8x.

    Each scenario is a general case like that, but there's no single formula per se, especially when you start asking questions like the probability of having x dice left in the yth round. It's a summation of summations.

    You have to start from the beginning: the probability of a single result from a single die is 1/8, the probability of a single result from n dice is (1/8)^n. The probability of the game ending in a given round is a summation of the probabilities of the different scenarios.

    You can use the probabilities the game ends in a given round as the base for the probability that the game ends in the next round. Remember when calculating that you also have to consider the probabilities that the game has already ended in previous rounds. In other words, the probability the game ends in the second round does not include the probability that the game ended in the first round.

  9. #9
    Social Worker
    Join Date
    Jun 2006
    Location
    Ohio
    Posts
    2,839
    Quote Originally Posted by BaconTastesGood View Post
    At a certain point it's easier and faster to test things empirically than it is to work out the odds -- in fact, working out the odds is often significantly slower than just doing 10000 tests and seeing what happens. There's a free/open source program that does dice roll simulations for RPGs and will also try to work out the odds. I think it had a very remarkable name, like "roll", and it was written in ML or M4 or some other exotic language. Maybe OCaml.
    See, this is the difference between people who are actually interested in math, and statisticians. There is a right answer, and it is possible to be right to any digit after zero, why would you settle for a program telling you something merely close?

    That being said, this is a hard problem to do without heavy lifting software, and especially without knowing exactly what you are after.

    So, I will try to answer one possible question:

    What are the odds that the game ends before Round 5?

    For any given dice on any given roll, there is a 1/8 chance that a 1 will come up and thus remove itself from the game. So, the question becomes what are the odds that a 1 will come for a given die in 4 rolls? Then, what are the odds a 1 will come for all 8 die?

    The odds a 1 will come up in four rounds is the exact opposite of not getting a 1 in four rounds, or (7/8)^4=~.586. Thus, to get a 1 in 4 rolls for a given die is 1-(7/8)^4=~.414.

    Now, its a simple matter to calculate the odds of all 8 dice getting a 1 in four rounds: (1-(7/8)^4)^8=~.001.

    This problem was relatively easy, but problems that seem similar might be a lot harder to figure out. Problems demanding exact odds about endings might be the most problematic.

  10. #10
    New Romantic
    Join Date
    Nov 2003
    Location
    Seattle and Charlotte
    Posts
    6,293
    Quote Originally Posted by Greatatlantic View Post
    There is a right answer, and it is possible to be right to any digit after zero, why would you settle for a program telling you something merely close?
    Because it's computationally too expensive to tell you something exact? Now, granted, I haven't looked at these types of issues in probably 7 years, but at that time there were some relatively basic RPG mechanics that were still fairly difficult to answer analytically in a reasonable frame of time on, say, a P3/1000. Again, it could have been the software, but that was my understanding at the time. This is exacerbated by RPGs that had rather ad hoc mechanics such as conditionals (open ended die rolls).

  11. #11
    Account closed How To Go
    Join Date
    Sep 2006
    Posts
    10,012
    Gus already mostly solved it for you, but nobody seems to have read his reminder about N choose K. ^_^

  12. #12
    New Romantic
    Join Date
    May 2003
    Location
    Gone
    Posts
    7,068
    Thanks for all the responses so far!

    I was initially going to try and brute force this with a spreadsheet, but my general approach to problems is, if there's a smarter and quicker way to do something, I'd like to learn it. Hence my asking here. :)

  13. #13
    New Romantic Miramon's Avatar
    Join Date
    Aug 2002
    Location
    Massachusetts
    Posts
    9,417
    Quote Originally Posted by sluggo View Post
    Thanks for all the responses so far!

    I was initially going to try and brute force this with a spreadsheet, but my general approach to problems is, if there's a smarter and quicker way to do something, I'd like to learn it. Hence my asking here. :)
    There is a smarter and quicker way. Monte-carlo for a problem like this is an admission of defeat. Rather than asking people who either never learned or have long forgotten the appropriate combinatorics, post it to a math department forum or just ask a professor.

  14. #14
    Broad Band
    Join Date
    Oct 2004
    Location
    IL
    Posts
    156
    I agree with Greatatlantic's answer. To state the explicit formula, the probability of winning on or before the kth round with N dice is

    [1-(7/8)^k]^N.

    The probability of winning on the kth round exactly with N dice is therefore

    [1-(7/8)^k]^N - [1-(7/8)^{k-1}]^N,

    since the outcomes are nicely nested.

    The probability that, after the kth round, M out of N dice have not rolled a 1 yet should be

    [N!/M!(N-M)!] [1-(7/8)^k]^(N-M) [7/8]^Mk,

    which we get by picking the M dice that fail, computing the probability of the M failures, and the probability of the N-M successes.

  15. #15
    New Romantic
    Join Date
    Nov 2003
    Location
    Seattle and Charlotte
    Posts
    6,293
    Ah, the program was called Roll, and the newer version is Troll.

    Again, maybe there's math that can provide analytical solutions faster than doing simulations, but in non-trivial RPG mechanics computing the actual odds can be extremely time consuming to derive. Maybe Torben just doesn't know his shit though, I'm not a statistician by any leap of the imagination.

    He specifically provides a sampling mode in (T)roll to deal with the cross over when exhaustive computation is too time consuming.

  16. #16
    Account closed How To Go
    Join Date
    Sep 2006
    Posts
    10,012
    Quote Originally Posted by BaconTastesGood View Post
    Ah, the program was called Roll, and the newer version is Troll.

    Again, maybe there's math that can provide analytical solutions faster than doing simulations, but in non-trivial RPG mechanics computing the actual odds can be extremely time consuming to derive. Maybe Torben just doesn't know his shit though, I'm not a statistician by any leap of the imagination.

    He specifically provides a sampling mode in (T)roll to deal with the cross over when exhaustive computation is too time consuming.


    Dude, it's just math, weird though that may seem. Computing something like this takes ... well, not linear time, but computing it isn't doing an exhaustive search through a binary tree.

    Running through logic trees brute-force on a computer takes forever for even moderate N. Doing math takes almost zilch; x^n can compute in O(n) and 2n space, but brute-forcing the probability space is exponential time and hideous on space if you do it naively (which you're talking about).

    Someone who had a good understanding of statistics could sit down for thirty seconds and come up with the right equation for the problem, and terpiscorei's answer seems right to me.

  17. #17
    New Romantic
    Join Date
    Nov 2003
    Location
    Seattle and Charlotte
    Posts
    6,293
    Quote Originally Posted by AaronSofaer View Post
    Someone who had a good understanding of statistics could sit down for thirty seconds and come up with the right equation for the problem, and terpiscorei's answer seems right to me.
    I'm not actually talking about OP's original post, I'm talking about the notion that you can solve everything analytically. Again, I'm totally willing to concede that I'm wrong on this issue since this isn't my forte, but when someone like Torben backs off to using sampling I assume* that it's for a good reason.

    I can't even remember what some of the examples I ran into a long time ago which seemed hard to me, but I think they involved open ended dice pools, something like:

    - given two opponents, one rolling M and and the other rolling N d10, what percentage of time does M beat N, where 'beat' is defined as "larger sum of dice"
    - then, given the above, assume that any roll of a '10' allows a reroll+add, and that this can continue infinitely
    - then given that, assume it's actually MdX vs. NdY -- when would more d6 be a benefit over fewer d10
    - etc. etc.

    Clearly there isn't an exhaustive solution, so an analytical one (i.e. involving limits) is going to be the only way to get a true answer, but this seemed like the perfect blend of discrete + integral math to scare me away =)

    * Appeal to authority and all that

  18. #18
    Account closed How To Go
    Join Date
    Sep 2006
    Posts
    10,012
    Quote Originally Posted by BaconTastesGood View Post
    I can't even remember what some of the examples I ran into a long time ago which seemed hard to me, but I think they involved open ended dice pools, something like:

    - given two opponents, one rolling M and and the other rolling N d10, what percentage of time does M beat N, where 'beat' is defined as "larger sum of dice"
    - then, given the above, assume that any roll of a '10' allows a reroll+add, and that this can continue infinitely
    - then given that, assume it's actually MdX vs. NdY -- when would more d6 be a benefit over fewer d10
    - etc. etc.

    Clearly there isn't an exhaustive solution, so an analytical one (i.e. involving limits) is going to be the only way to get a true answer, but this seemed like the perfect blend of discrete + integral math to scare me away =)

    * Appeal to authority and all that

    It depends on how you approach the problem. Are you a beastly programmer with the right tools (Matlab, huzzah!) to deal with the situation, a statistician, or someone with a very strong formal logic background? Then all you have to do is convert the rules of the game into formal logic, and essentially run the numbers.

    That's specifically for the kind of problem you're talking about. None of those three rules is particularly difficult to model, because the probability space is, if you will accept a completely incorrect metaphor, narrow but deep.

    Chess is wide-ish and deep-ish, and is a fun challenge. Go is ... well, heh. And then there's that game that was written specifically to be nigh-impossible for a computer to play...

  19. #19
    New Romantic Miramon's Avatar
    Join Date
    Aug 2002
    Location
    Massachusetts
    Posts
    9,417
    Quote Originally Posted by AaronSofaer View Post
    And then there's that game that was written specifically to be nigh-impossible for a computer to play...
    You mean Civ 5?

  20. #20
    Social Worker
    Join Date
    Nov 2006
    Location
    Australia
    Posts
    4,259
    Quote Originally Posted by sluggo View Post
    Thanks for all the responses so far!

    I was initially going to try and brute force this with a spreadsheet, but my general approach to problems is, if there's a smarter and quicker way to do something, I'd like to learn it. Hence my asking here. :)
    Brute force it with R.

    Trust me, I'm a statistician.

  21. #21
    Spinning Toe
    Join Date
    Jul 2006
    Location
    Spain
    Posts
    975
    Markov Chains. You have 9 states (8 dice, 7 dice,... 1 die, 0 dice). You represent in a 9x9 stochastic matrix the probabilities of every state transition and then a couple of simple matrix operations give you all the probabilities you want. It's quite easy to follow the example solution in section 1.2.6 of this paper: http://arxiv.org/pdf/math/0001057v1
    Use octave or mathwhatever to do the calculations, 9x9 matrix manipulation sucks by hand.

  22. #22
    New Romantic
    Join Date
    Jul 2008
    Posts
    6,395
    Quote Originally Posted by AaronSofaer View Post
    (Matlab, huzzah!)
    Aw yiss. He is right though 90% of the stuff I do with MATLAB is close approximation using millions of iterations. Real calculations are fucking hard, millions of simple calculations are easy.

  23. #23
    Neo Acoustic
    Join Date
    Jul 2004
    Location
    Queensland, Australia
    Posts
    1,997
    Why is everyone ignoring terp's lovely solutions?

  24. #24
    Social Worker
    Join Date
    Dec 2006
    Posts
    3,313

    ...

    Quote Originally Posted by AaronSofaer View Post
    ...And then there's that game that was written specifically to be nigh-impossible for a computer to play...
    Arimaa. Civ 5 is a good answer, though... I would also accept Ascendancy or Emperor of the Fading Suns. ;)

  25. #25
    Social Worker
    Join Date
    Jul 2007
    Location
    Not a koalafish
    Posts
    2,277
    Obligatory Python simulation:

    Code:
    def qtdice1(sides,die,games):
        import random
        results=[]
        for g in range(games):
            dice=die
            turns=0
            while (dice>0):
                turns=turns+1
                for r in range(dice):
                    roll=random.randint(1,sides)
                    if roll==1: dice = dice-1
            results.append(turns)
        return results


    Notices the accuracy of the formulas derived by Greatatlantic and terpiscorei.

    Okay, back to work.
    Last edited by jellyfish; 09-05-2011 at 11:56 PM.

  26. #26
    World's End Supernova
    Join Date
    Jul 2003
    Location
    Louisville
    Posts
    15,289
    This will be dead simple for the mathy folks, but I can't work it out. How would I calculated the probability of NOT getting a certain result over a series? If there's a 1 in 3 chance of something happening, and you run it 25 times, what are the overall odds of never hitting over the entire series?

  27. #27
    New Romantic
    Join Date
    Dec 2008
    Location
    Wheeljack on Playdek.
    Posts
    9,780
    (2/3)^25

  28. #28
    Social Worker
    Join Date
    May 2003
    Location
    in the land of the ice and snow
    Posts
    2,285
    Quote Originally Posted by Houngan View Post
    This will be dead simple for the mathy folks, but I can't work it out. How would I calculated the probability of NOT getting a certain result over a series? If there's a 1 in 3 chance of something happening, and you run it 25 times, what are the overall odds of never hitting over the entire series?
    The probability of it not happening raised by the number of runs?

    In your case ( 2 / 3 ) ^ 25 which is really small. 0.000039 in 1.0

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •