Computing event likelihood and sampling from probability distributions.
While most of the field of probability is well outside the scope of this reference, understanding of a few basic concepts (especially in combination with basic concepts of combinatorics) can go a long way towards preparing a programmer for tasks in computational probability.
If events $A$ and $B$ have no effect on each other—that is, if the probability that event $B$ occurs ($P(B)$) is not affected by the occurrence (or lack of same) of $A$, and vice versa, then the 2 events are independent. For example, if we toss a coin twice, the outcome of each toss has no effect on the outcome of the other.
If we have 2 or more independent events, then the probability that all of the events occur (their joint probability) is the product of their individual probabilities. That is, if
\[\begin{aligned} E_1, E_2, \ldots E_n \end{aligned}\]are independent events, then
\[\begin{aligned} P(E_1 \cap E_2 \ldots \cap E_n) &= \prod_{i=1}^{n}E_i \end{aligned}\]If events $A$ and $B$ are mutually exclusive—that is, if that fact that either 1 of them has occurred implies that the other cannot occur, then the 2 events are disjoint. For example, in a single roll of a 6-sided die, rolling a 1 implies that 2 is not rolled—at least, not in the same roll—and vice versa. Note that this does not imply that the 2 events are the only possible outcomes, but only that each one precludes the other.
If we have 2 disjoint events, then the probability that one or the other occur is the sum of their individual probability. This can be extended to more than 2 disjoint events as well. In symbolic terms, where
\[\begin{aligned} E_1, E_2, \ldots E_n \end{aligned}\]are disjoint events (that is, $P(E_i \cap E_j) = 0, \forall i, j \in \lbrace 1, 2, \ldots, n \rbrace$),
\[\begin{aligned} P(E_1 \cup E_2 \ldots \cup E_n) &= \sum_{i=1}^{n}E_i \end{aligned}\]Related to concept of disjoint events is that of naïve probability. If an experiment has a finite number of equally likely disjoint outcomes, and if there are $n$ possible outcomes, then each has a probability of $1/n$. Further, we can compute the probability the the outcome is a member of the set $E$ by dividing the cardinality of $E$ by the cardinality of $U$, the set of all possible outcomes (aka the universe of outcomes).
\[\begin{aligned} P(E) &= \dfrac{\left\vert E \right\vert}{\left\vert U \right\vert} \end{aligned}\]For an example of a naïve probability calculation, see the royal flush example.
A common task in game development, as well as quantitative and scientific computing, is that of sampling a random (or pseudorandom) value from a probability distribution. The java.util.Random class provides several methods for sampling from a subset of uniform discrete, uniform continuous, Bernoulli, and Gaussian (normal) distributions. Simple arithmetic transformations can expand these subsets significantly; beyond that, libraries such as Apache Commons RNG and Apache Commons Math can be important elements of an implementation approach.
For some random experiments, the outcomes may be characterized by numeric values, such that each possible outcome is a member of a specified finite set of values. If these values fall within a specified range, with a constant difference between each value and the value preceding and/or succeeding it, and if all of the values are equally likely, then we have a special (and very useful) case of the situation described in “Naïve probability”. This is a uniform discrete probability distribution.
An example of this type of distribution, and this type of random experiment, is found in the roll of a single fair die. In the case of a six-sided die, the possible outcomes are the values $1$ through $6$, each with a probability of $1/6$.
A Java method that samples a value from such a distribution could be written as follows:
double discreteUniform(
double lowerBound, double interval, int n, Random rng) {
return lowerBound + rng.nextInt(n) * interval;
}
In this method, lowerBound is a parameter specifying the outcome with the minimum possible value; interval is the spacing between possible outcome values; n is the number of possible outcomes; rng is an instance of the java.util.Random class (or a subclass of that), which can be used to generate general pseudorandom values.
We might invoke the discreteUniform method to simulate a roll of a six-sided die using code like the following:
Random rng = new Random();
int roll = discreteUniform(1, 1, 6, rng);
On the other hand, in this example, where the possible outcomes are all integral, it’s probably simpler just to use the Random.nextInt() method directly. In fact, one of the most important points to remember about sampling from uniform discrete probability distributions is that the Random.nextInt(int bound) method is a very useful building block. That method samples from the uniform discrete distribution over the values ${ 0, 1, \ldots (bound - 1) }$; the value returned can be transformed arithmetically to sample from virtually any uniform discrete distribution.
If the outcome values of some random experiment are not evenly spaced, or all such outcomes are not equally likely, but the set of values is finite, then we have a non-uniform discrete probability distribution. A detailed discussion of such distributions is beyond the scope of this document; however, it should be noted that some such distributions are actually combinations of uniform distributions.
For example, the sum obtained from a roll of 2 six-sided dice is non-uniform, because the possible values $ \left (2, 3, \ldots 12 \right)$ are not all equally likely; however, we can still fall back on the concept of naïve probability. For example, if we examine the values shown on the 2 dice, we see that there are a total of 36 possible rolls, all equally likely. 6 of those rolls give a sum of 7; thus, the probability of rolling a 7 is 6/36, or 1/6. On the other hand, there are only 2 possible rolls that give a sum of 3; the probability of rolling a 3 is therefore 2/36, or 1/18.
The sets of possible numerical outcomes for some random experiments are not finite; instead, the outcome might take any value within a continuous range. In such cases, it’s usually meaningless to talk about the probability of a specific single value as an outcome; instead, we might examine the probability of an outcome falling within a stated interval.
Typically, we express such a continuous probability distribution as a probability density function, $f(x)$, with these general constraints:
\[\begin{aligned} f(x) &\ge 0, &-\infty < x < \infty \\ \int_{-\infty}^{\infty} f(x) \: dx &= 1 \end{aligned}\]The probability of an outcome falling within some interval, $\left[ X_a, X_b \right]$, can be expressed using a definite integral:
\[\begin{aligned} p(X_a \le x \le X_b) &= \int_{X_a}^{X_b} f(x) \: dx \end{aligned}\]As is the case for discrete probability distributions, continuous distributions come in uniform and non-uniform varieties; however, the general mathematical statements above apply in both cases. In any event, an in-depth discussion of continuous probability distributions is beyond the scope of this introduction. However, we should note that just as Random.nextInt() is an important building block for sampling from uniform discrete distributions, Random.nextDouble() is a similarly useful building block for sampling from uniform or non-uniform continuous distributions; for the special case of the Gaussian distribution (aka normal distribution), Random.nextGaussian() is even more directly applicable.