basic probability calculation

[jedidia]

I'm making a new concept for stellar generation in Orbiter Galaxy that should speed things up a bit for the generator, and I have to do some basic probability calculations for it. I remember vaguely having heard of it in elementary school, but forgott pretty much everything about it. So of course I googled and learned, but I'm not sure wheather I got it, so I'm just putting the most basic example comming to my mind up here. Just tell me wheather I got this right or not (especially the second one, I'm pretty confident about the first):


The probability to roll a six with a D6 is 1/6 = 0.16666.

If I roll it ten times, I have a (1-0.16666)^10 probability that NONE of the rolls are a six, resulting in a 0.83849 probability that I'll roll at least one six with ten rolls. Is that correct so far?

going on, the probability of rolling 2 sixes with two dicerolls is 1/6 * 1/6 = 0.02777. The probability to NOT roll 2 sixes with ten dicerolls should ergo be (1-0.02777)^5, resulting in a 0.1318 probability that I will indeed roll two sixes with ten rolls.

I'm pretty confident that I got the first one right, but have no idea about the second one. Please someone have a look at it and tell me wheather or not I got the concept, or my new stellar distributions might end up somewhat... interesting.

 

[Wishbone]

Both answers are OK. Would you please tell what you are trying to accomplish? Sometimes discrete distributions are not optimal for the task at hand, and there are some quirks related to use of pseudo-RNGs for large-scale generation of "die rolls" that I may be able to point out if I know a bit more about your design.

EDIT: :facepalm: :facepalm:

 

[jedidia]

I'm not going to roll dice, but the concept stays the same...

The stellar generation currently works with probabilities according to the initial mass functions of stars. I.e. I have a range that is divided in several places to indicate probabilities of a star with a certain mass being formed. That range is 406.78215 (this value is derived by normalising the values of the initial mass function for different stellar masses). A random number between zero and 406.78215 is generated and then evaluated (for example, the threshold value for a star of 90 SM is 406.7696. These thresholds are also derived from the inital mass function). If the random number is above that value, a star with 90+ SM is created (depending on the exact value of the random number). This process is repeated for every star in that region. Their number is derived from stellar density that is calculated by taking the grayscale value of a bitmap for the according region (pretty arbitrary, I know.)

This works very nice, but is completely unpredictable, so that a region of space has to be fully generated to evaluate it even superficially. So I will try to make it in a manner that would first generate a rough overview of the region:

Going from the values I already derived from the initial mass function, I can calculate the probability of a star of that mass occuring in a given stellar density. So I'll work down from the top of the mass classes: generating a random number between 0 and 1 for the highest mass class: if the number is lower than the calculated probability for a star of this mass to occur, one star with that mass (with some more randomness and probability going on to determine the exact mass) will be generated. If the random number is lower than the chances of 2 such stars occuring in this region, two will be generated, if it's lower than the probability of 3 Stars occuring 3, etc. Working the way down the mass classes this way I can get a rough (initial) overview of stellar masses in a given region of space without having to generate too much. Stelar Evolution will still play with the masses of course, so it's still (very) possible that a Star with 100 solar masses gets reduced to a black hole of only a few solar masses, but it's a good start and will allow me to just generate the stars of interest for closer examination.

It seems like a sound concept, but maybe I'm forgetting something...

 

[Wishbone]

My head slightly hurts. I suppose this is the situation where you could use continuous distributions. What is the mass function you've got (I reckon it is the main algo input)? What is the expected output for the overview?

 

[jedidia]

I used the parameters from here to distribute the masses in a normalised range. It seems to work fairly accurate, judging by the mass distribution in Orbiter Galaxy as it is currently, just very unpredictable. The aim is not to make an overview to look at, but to make things easier for the FTL pathfinding, which must find stars of certain masses as quickly as possible.

 

[Wishbone]

Ahh, I see, it should be an heuristic to be used in A* while pathfinding. The solution, then, will be to
a) Specify the range of stellar masses you're interested in [M_lower;M_upper)
b) use power law CDF: Prob(M belongs to the range) = CDF(M_upper) - CDF(M_lower)

c) ... then you multiply the probability by the number of stars in the segment and get the expectation of the number of stars in the range. Which is fed into pathfinding...

 

[jedidia]

Actually I was intending to feed the stuff to the generator, So I'd have a good means of quickly seeing if there really IS a star with that mass present in that region. The trouble with a procedural generator is that the computer itself has no idea where what is, and would have to generate the entire galaxy to find a specific star (in the ultimate worst case). By having the generator first determine how many stars of aproximately what mass there are before generating anything else I can make a superficial scan of a region and generate only the stars of interest for the pathfinding, to see if they check out. It means I don't have to bother with 99% of the stars while looking for a sensible jump route. Calculating the probabilities makes sure that the mass distribution of stellar masses stays realistic.

 

[jedidia]

I'm still having trouble deriving a generic equation to calculate the probability of an event occuring z times during n "rolls". I think I have the probability for ONE occurence pretty much nailed down by now:

Given:
n = number of rolls;
x = total possibilities per roll;
y = number of possibilities per roll that the event occurs;

Now the first thing I have to know is the total possibilites that can occur during n rolls, which should be:
x^n;

for the total number of possibilities that the event occurs during n rolls I first have to calculate the total possibilities of it NOT occuring during n rolls, which should be:
(x-y)^n;
It follows that the total number of possibilities the event can occur is:
x^n - (x-y)^n;

The probability of the event is the possibilities it can occur divided by the total possibilities, leading to:
(x^n - (x-y)^n) / x^n;

However, as mentioned this only tells me the probability of the event occuring ONCE per n rolls, while I want to know the probability for z occurances per n rolls. And I can't for the live of me see a way to expand the equation accordingly...

 

[Wishbone]

Look up Binomial formula... and BTW welcome to the bright new world that was discovered when Blaise Pascal went gambling...

EDIT: the code to use for binomial p.d.f. is in the AlgLib I have previously mentioned. Don't try (yet) to implement the formula manually, there are computational issues (integer overflow and loss of accuracy) that are handled in math libraries.

 

[TJohns]

I think your second calc is wrong - you're finding the chance of a pair of sixes in 5 rolls of 2 dice...you'll miss all the cases of a single six in 2 different rolls!

Here's a nice explanation of permutations & combinations...look at the last section "Combinations with Repetition"

http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Trevor

 

[Wishbone]

Trevor, Mea culpa... Guess that's what happens when one is not concentrating enough. Indeed, the probability of two sixes (non-consecutive) in 10 dice rolls is 0.29071... Now, where was that emoticon :facepalm: :facepalm:

 

[jedidia]

Thanks for the link... looks like what I need is the most complicated of the lot. Just my luck...

---------- Post added 01-14-11 at 08:24 AM ---------- Previous post was 01-13-11 at 11:53 AM ----------

I'm making a bit of progress here, however, there's one question left...

First off I realized that I had to bother with permutations, although thankfully not too much. What I am looking for is the probability of the event occuring at least z times during n rolls, not exactly z times, which simplifies things a lot.

n = number of rolls;
x = total possibilities per roll;
y = number of possibilities per roll that the event occurs;
p = probability of event occuring per roll
z = minimal number of times the event should occur;

Under these circumstances the probability for a permutation to occur is always p^z. If I have for example 5 dice and I want at least two sixes, a possible permutation would look like this:

(1/6) * (1/6) * (6/6) * (6/6) * (6/6);

Since, if the first two rolls are right, all other dice won't matter, i.e. have a probability of 1 to show the right result. Ergo, the probability is p^z.

However, there are several permutations allowing for this, like e.g.
(1/6) * (6/6) * (6/6) * (6/6) * (1/6);

If I didn't completely misunderstand something, the probability of a valid permutation occuring is the probabilities of all valid permutations added together. Since in this case the product of all valid permutations are the same, that is equal to the probability of any one permutation times the number of valid permutations.

The number of valid permutations should be the good old number of total permutations minus non-valid permutations, which I already know how to derive:
(1-p)^n * x^n;

It follows that the total number of valid permutations is:
x^n - ((1-p)^n * x^n);

The whole thing together should result in:
(p^z) * (x^n - ((1-p)^n * x^n)) = probability of event occuring at least z times in n rolls;

However,This returns complete bollocks. I'm pretty sure my mistake is adding the probabilities of the permutations together, since it's pretty clear that this can easily result in a probability higher than one. But all I read so far told me to add the probabilities of the valid permutations together, so I probably haven't understood what "adding" means in this context. Can someone give me another hint?

 

[TJohns]

If you can calculate the probability of EXACTLY 'r' results in 'n' trials (say 3 heads in 10 coin tosses), the way to calculate AT LEAST 'r' results (3 or more heads) is to start at 100% chance and count backwards

prob(at least 3) = 1.0 - prob(0) - prob(1) - prob(2)

Remember that the sum of all the individual probabilities MUST be 1.0

prob(0) + prob(1) + ... + prob(9) + prob(10) = 1

P.S. and I hope you mean combinations rather than permutations, since the order of when the heads come out is irrelevent

Trevor

 

[jedidia]

I meant permutations alright, as I found the problem solved somewhere adding up the probabilities of all permutations that show the desired result, which is what I'm trying to do above. It seems I got something wrong about the adding up of the probabilities, though (see here)

If you can calculate the probability of EXACTLY 'r' results in 'n' trials (say 3 heads in 10 coin tosses),

I haven't managed to do that yet, either...