Probability fundamentals

The sample space Ω is the set of all possible outcomes of a random experiment. With equally likely outcomes, a probability is a ratio of counts. Two fair dice have |Ω| = 36 outcomes; a random permutation of n items has n! outcomes.

Clearly defining Ω first prevents most counting mistakes.

An event is a subset of the sample space, and its probability is |event| / |Ω| for equally likely outcomes. P(A ∪ B) = P(A) + P(B) - P(A ∩ B) and P(not A) = 1 - P(A).

“The two dice sum to 7” contains 6 outcomes ((1,6), (2,5), (3,4), (4,3), (5,2), (6,1)), so its probability is 6/36 = 1/6.

1int hits = 0;
2for (int a = 1; a <= 6; a++) for (int b = 1; b <= 6; b++) if (a + b == 7) hits++;
3double p = hits / 36.0;   // 0.1666...

P(A | B) = P(A ∩ B) / P(B) is the probability of A once you know B happened; it restricts the sample space to B. Example: given that the first die shows 6, the probability that the sum is at least 10 is 3/6 = 1/2 (second die 4, 5 or 6).

Bayes' rule P(A | B) = P(B | A) · P(A) / P(B) reverses the conditioning and underlies spam filters.

Events A and B are independent if P(A ∩ B) = P(A) · P(B): knowing one tells nothing about the other. Two separate coin flips are independent; drawing two cards without replacement is not.

Randomised algorithms rely on independence, for example independent hash functions in a Bloom filter. Repeating an independent trial that succeeds with probability p until it succeeds takes 1/p tries on average.

The expected value E[X] = Σ x · P(X = x) is the average value of a random variable over many trials. A fair die has E = (1 + 2 + … + 6)/6 = 3.5. Average-case analysis computes the expected running time over a distribution of inputs.

If the target of a linear search is equally likely to be at any of n positions, the expected number of comparisons is (n + 1)/2. The animation shows the matching experiment: random permutations and the average count of fixed points.

1// X = number of cards that land in their own position after a random shuffle
2// X = X0 + X1 + ... + X(n-1), where Xi is 1 if card i is fixed, else 0   (indicator variables)
3double expected = 0;
4for (int[] p : allPermutations(n)) {                  // each equally likely
5    int fixed = 0;
6    for (int i = 0; i < n; i++) if (p[i] == i) fixed++;
7    expected += fixed;
8}
9expected /= factorial(n);                             // = 1.0 for every n

E[X + Y] = E[X] + E[Y] always, even when X and Y are dependent. That is what makes expectations easy to compute: split a complicated variable into simple parts and add their expectations.

A random permutation of n items has, on average, exactly one fixed point (an item in its original position) for every n ≥ 1, although the individual position events are dependent.

1// X = number of cards that land in their own position after a random shuffle
2// X = X0 + X1 + ... + X(n-1), where Xi is 1 if card i is fixed, else 0   (indicator variables)
3double expected = 0;
4for (int[] p : allPermutations(n)) {                  // each equally likely
5    int fixed = 0;
6    for (int i = 0; i < n; i++) if (p[i] == i) fixed++;
7    expected += fixed;
8}
9expected /= factorial(n);                             // = 1.0 for every n

An indicator variable Xᵢ is 1 if an event happens and 0 otherwise, so E[Xᵢ] = P(event). Write the quantity of interest as a sum of indicators and use linearity. For fixed points, Xᵢ = 1 when item i lands in position i, which has probability 1/n, so the expected total is n · (1/n) = 1.

The same method gives the expected number of comparisons in randomised quick sort, O(n log n), and the expected number of collisions in a hash table with n keys and m buckets, about n(n - 1)/(2m).

1Random rnd = new Random(1);
2int n = 10, trials = 100_000; long total = 0;
3for (int t = 0; t < trials; t++) {
4    List<Integer> p = new ArrayList<>();
5    for (int i = 0; i < n; i++) p.add(i);
6    Collections.shuffle(p, rnd);
7    for (int i = 0; i < n; i++) if (p.get(i) == i) total++;
8}
9double avg = (double) total / trials;   // close to 1.0

1// X = number of cards that land in their own position after a random shuffle
2// X = X0 + X1 + ... + X(n-1), where Xi is 1 if card i is fixed, else 0   (indicator variables)
3double expected = 0;
4for (int[] p : allPermutations(n)) {                  // each equally likely
5    int fixed = 0;
6    for (int i = 0; i < n; i++) if (p[i] == i) fixed++;
7    expected += fixed;
8}
9expected /= factorial(n);                             // = 1.0 for every n