Chapter 22 of 30

Discrete Probability

Randomised quicksort, hash tables, load balancers, network retries, cryptographic keys and machine learning all rely on chance. To analyse them we need probability, and in computer science most of it is discrete probability: the experiment has finitely many (or countably many) outcomes, so probabilities are computed by counting and adding rather than by integrating.

This chapter builds on the counting tools from Counting Principles, Permutations & Combinations and Inclusion-Exclusion Principle. We cover sample spaces and events, the rules of probability, conditional probability and independence, Bayes' theorem, random variables, expectation and variance, and the three distributions that appear most in GATE and interviews: Bernoulli, binomial and geometric. Every number in this chapter was checked by exact enumeration with Python fractions.

A discrete probability space consists of a finite or countable sample space S together with a function p that gives each outcome s a probability p(s) ≥ 0, such that ∑s∈S p(s) = 1. The probability of an event E ⊆ S is P(E) = ∑s∈E p(s).


Experiments, Sample Spaces and Events

  • An experiment is a process with an uncertain result: tossing a coin, rolling two dice, choosing a random password.

  • The sample space S is the set of all possible outcomes.

  • An event is a subset of S. "The sum of two dice is 7" is the event {(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)}.

Because events are sets, the language of Sets & Set Operations carries over directly: E ∪ F means "E or F happens", E ∩ F means "both happen", and the complement Ē = S − E means "E does not happen". Events with E ∩ F = ∅ are mutually exclusive (they cannot happen together).

The classical (Laplace) definition

When all |S| outcomes are equally likely, each has probability 1/|S|, so

P(E) = |E| / |S| = (number of favourable outcomes) / (total number of outcomes).

Example. Two fair dice are rolled. S has 6 × 6 = 36 ordered outcomes. The event "sum is 7" has 6 outcomes, so P = 6/36 = 1/6.

Example. A fair coin is tossed 4 times. What is the probability of exactly 2 heads? There are 2⁴ = 16 equally likely sequences, and C(4, 2) = 6 of them have exactly two H's. P = 6/16 = 3/8.

The most common beginner mistake is to use a sample space whose outcomes are not equally likely. For two dice, the 11 possible sums 2, 3, …, 12 are not equally likely (sum 7 has six ways, sum 2 only one), so P(sum = 7) is not 1/11. Always count ordered outcomes for dice, coins and cards drawn one at a time, unless you are sure another space is uniform.


Rules of Probability

From the definition (non-negative weights that sum to 1) we get these rules. Each follows by adding up outcome weights.

Rule

Statement

Range

0 ≤ P(E) ≤ 1, P(∅) = 0, P(S) = 1

Complement

P(Ē) = 1 − P(E)

Monotonicity

If E ⊆ F then P(E) ≤ P(F)

Sum rule (mutually exclusive)

If E ∩ F = ∅ then P(E ∪ F) = P(E) + P(F)

General union (inclusion-exclusion)

P(E ∪ F) = P(E) + P(F) − P(E ∩ F)

Union bound

P(E1 ∪ ⋯ ∪ En) ≤ P(E1) + ⋯ + P(En)

Example (union). A card is drawn from a standard 52-card deck. P(ace or heart) = 4/52 + 13/52 − 1/52 = 16/52 = 4/13. The ace of hearts is subtracted once because it was counted in both events.

The complement trick

"At least one" problems are almost always easier through the complement. What is the probability of at least one six in 4 rolls of a die? The complement is "no six in 4 rolls", which has probability (5/6)⁴. So

P(at least one six) = 1 − (5/6)⁴ = 1 − 625/1296 = 671/1296 ≈ 0.5177

Worked example: the birthday problem

In a group of n people, what is the probability that at least two share a birthday? Assume 365 equally likely birthdays and ignore leap years.

Count the complement, "all birthdays different". The first person can have any of 365 days, the second any of the other 364, and so on:

P(all different) = (365 · 364 · ⋯ · (365 − n + 1)) / 365ⁿ
P(some shared)   = 1 − P(all different)

n

10

20

22

23

30

50

70

P(shared)

0.117

0.411

0.476

0.507

0.706

0.970

0.999

Only 23 people are needed to pass 50%. The intuition: what matters is the number of pairs, C(23, 2) = 253, and each pair has a 1/365 chance of matching. In computer science this is why hash collisions appear much sooner than you might expect: with m hash values, collisions become likely after roughly √m items. It is the basis of the "birthday attack" on hash functions.


Conditional Probability

Sometimes we learn something about the outcome before we ask our question. Knowing that F happened shrinks the sample space to F.

For events E and F with P(F) > 0, the conditional probability of E given F is P(E | F) = P(E ∩ F) / P(F).

Example. Two dice are rolled and at least one shows a 3. What is the probability that the sum is 7?

The outcomes with at least one 3 are the 6 with a 3 on the first die plus the 6 with a 3 on the second, minus (3,3) counted twice: 11 outcomes. Among them, the sum is 7 for (3,4) and (4,3). So P = 2/11, which is a little more than the unconditional 1/6.

Example (a classic trap). A family has two children, and at least one is a boy. What is the probability that both are boys? (Assume each child is independently a boy or a girl with probability 1/2.) The equally likely outcomes are BB, BG, GB, GG. "At least one boy" leaves BB, BG, GB, so the answer is 1/3, not 1/2.

Multiplication rule and total probability

Rearranging the definition gives the multiplication rule P(E ∩ F) = P(F) · P(E | F). It is how we compute probabilities of sequences: P(first two cards are aces) = (4/52) · (3/51) = 1/221.

If F1, …, Fk partition S (they are mutually exclusive and one of them must happen), then

Law of total probability: P(E) = P(E | F1)P(F1) + ⋯ + P(E | Fk)P(Fk).


Bayes' Theorem

Bayes' theorem reverses a conditional probability. We often know P(evidence | cause) but want P(cause | evidence).

P(F | E) = P(E | F) · P(F) / P(E), where P(E) = P(E | F)P(F) + P(E | F̄)P(F̄).

It follows in one line: both P(F | E)P(E) and P(E | F)P(F) equal P(E ∩ F).

Worked example: a medical test

A disease affects 1% of a population. A test detects it in 99% of sick people, but also gives a (false) positive for 5% of healthy people. Someone tests positive. How likely is it that they have the disease?

P(D) = 0.01        P(+ | D) = 0.99        P(+ | not D) = 0.05

P(+) = 0.99 × 0.01 + 0.05 × 0.99 = 0.0099 + 0.0495 = 0.0594

P(D | +) = 0.0099 / 0.0594 = 1/6 ≈ 0.167

Only about 16.7%, even though the test is "99% accurate". Why? Healthy people outnumber sick people 99 to 1, so the 5% of healthy people who test positive (4.95% of everyone) swamp the true positives (0.99% of everyone). Ignoring the prior P(D) is called the base-rate fallacy, and spam filters, fraud detectors and diagnostic systems must all account for it.

Worked example: Monty Hall

A prize is behind one of three doors. You pick door 1. The host, who knows where the prize is, always opens a different door with no prize behind it, and offers you a switch. Should you switch?

Yes. Your first pick is right with probability 1/3, and in that case switching loses. With probability 2/3 your first pick is wrong; then the host is forced to open the only other empty door, and switching wins. So switching wins with probability 2/3. Enumerating all 9 (prize door, first pick) pairs confirms it: switching wins in 6 of the 9.


Independence

Events E and F are independent if P(E ∩ F) = P(E) · P(F). Equivalently (when P(F) > 0), P(E | F) = P(E): knowing F tells you nothing about E.

Do not confuse independent with mutually exclusive. If E and F are mutually exclusive and both have positive probability, then P(E ∩ F) = 0 ≠ P(E)P(F), so they are dependent: knowing E happened tells you F did not.

Pairwise vs mutual independence

Events E1, …, En are mutually independent if the product rule holds for every sub-collection, not just every pair. These can differ. Toss two fair coins and let

  • A = first coin is heads, B = second coin is heads, C = both coins show the same face.

P(A) = P(B) = P(C) = 1/2
P(A ∩ B) = P(A ∩ C) = P(B ∩ C) = 1/4         (each pair is independent)
P(A ∩ B ∩ C) = P(HH) = 1/4  ≠  1/8 = P(A)P(B)P(C)

Every pair is independent, but the three are not mutually independent: if A and B both happen, C is certain.

Bernoulli trials and the binomial distribution

A Bernoulli trial is an experiment with two outcomes: success with probability p and failure with probability q = 1 − p. In n independent Bernoulli trials, a particular sequence with exactly k successes has probability pkqn−k, and there are C(n, k) such sequences (choose which trials succeed). So

Binomial distribution: P(exactly k successes in n trials) = C(n, k) pk (1 − p)n−k, for k = 0, 1, …, n.

Example. A student guesses all 10 questions of a multiple-choice quiz, each with 4 options (p = 1/4). The probability of at least 8 correct is

C(10,8)(1/4)⁸(3/4)² + C(10,9)(1/4)⁹(3/4) + C(10,10)(1/4)¹⁰
  = (405 + 30 + 1) / 4¹⁰ = 436 / 1048576 = 109/262144 ≈ 0.00042

Guessing is not a good strategy.


Random Variables and Expectation

A random variable is a function X : S → ℝ that assigns a number to each outcome. Its expected value (mean) is E[X] = ∑s∈S p(s) X(s) = ∑r r · P(X = r).

Despite the name, a random variable is neither random nor a variable: it is a function, as in Functions. "The sum of two dice" is the function (a, b) ↦ a + b.

Example. For one fair die, E[X] = (1 + 2 + 3 + 4 + 5 + 6)/6 = 7/2 = 3.5. The expected value need not be a possible outcome; it is the long-run average.

Linearity of expectation

For any random variables X and Y and constants a, b: E[aX + bY] = aE[X] + bE[Y]. This holds even when X and Y are dependent.

Proof. E[aX + bY] = ∑s p(s)(aX(s) + bY(s)) = a∑s p(s)X(s) + b∑s p(s)Y(s) = aE[X] + bE[Y]. No independence was used. ∎

So the expected sum of two dice is 3.5 + 3.5 = 7, with no need to list 36 outcomes.

The indicator-variable method

An indicator variable IA is 1 if event A happens and 0 otherwise. Its expectation is simply E[IA] = P(A). To find the expected number of times something happens, write the count as a sum of indicators and use linearity.

Example: fixed points of a random permutation. n students throw their ID cards in a box and each takes one back at random. What is the expected number of students who get their own card?

Let Xi = 1 if student i gets their own card. There are (n − 1)! permutations that fix position i out of n!, so P(Xi = 1) = 1/n. Then

E[X] = E[X₁] + ⋯ + E[Xₙ] = n · (1/n) = 1

The answer is 1 for every n, even though the Xi are dependent. By contrast, the probability that nobody gets their own card (a derangement, from Inclusion-Exclusion Principle) is 1/3 for n = 3, 3/8 for n = 4 and 11/30 for n = 5, and approaches 1/e ≈ 0.368.

Example: expected birthday matches. Among 28 people, the expected number of pairs sharing a birthday is C(28, 2) · (1/365) = 378/365 ≈ 1.04.


Variance

The mean tells us the centre; the variance tells us how spread out the values are.

Var(X) = E[(X − E[X])²] = E[X²] − (E[X])². The standard deviation is σ = √Var(X).

Example. For one die, E[X²] = (1 + 4 + 9 + 16 + 25 + 36)/6 = 91/6, so Var(X) = 91/6 − 49/4 = 35/12.

  • Var(aX + b) = a² Var(X). Adding a constant does not change the spread.

  • If X and Y are independent, Var(X + Y) = Var(X) + Var(Y). Unlike linearity of expectation, this needs independence. For two independent dice, Var(sum) = 35/12 + 35/12 = 35/6.


Standard Discrete Distributions

Distribution

Models

P(X = k)

E[X]

Var(X)

Bernoulli(p)

One trial, success = 1

p if k = 1, 1 − p if k = 0

p

p(1 − p)

Binomial(n, p)

Successes in n independent trials

C(n,k)pk(1 − p)n−k

np

np(1 − p)

Geometric(p)

Trials until the first success

(1 − p)k−1p, k ≥ 1

1/p

(1 − p)/p²

Uniform on {1, …, n}

Fair die, random index

1/n

(n + 1)/2

(n² − 1)/12

The binomial mean follows from linearity: X is a sum of n Bernoulli indicators, each with mean p. The binomial variance follows because those indicators are independent. For the guessing student: E = 10 · 1/4 = 2.5 correct answers, Var = 10 · (1/4)(3/4) = 15/8.

Why the geometric mean is 1/p

Let X be the number of trials up to and including the first success. Condition on the first trial: with probability p it succeeds (X = 1); with probability 1 − p it fails, and because trials are independent we are back where we started, having used one trial. So E[X] = p · 1 + (1 − p)(1 + E[X]), which gives p · E[X] = 1, i.e. E[X] = 1/p. A fair coin needs 2 tosses on average to show heads; a die needs 6 rolls on average to show a six.

Worked example: the coupon collector

How many rolls of a die, on average, until every face has appeared? Once you have seen i different faces, each roll shows a new face with probability (6 − i)/6, so the wait for the next new face is geometric with mean 6/(6 − i). By linearity,

E = 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 6(1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 14.7

In general, collecting all n coupons takes n · Hn ≈ n ln n draws on average, where Hn is the n-th harmonic number. The same analysis tells you how many random keys fill every bucket of a hash table.


Checking Answers by Enumeration

For small experiments you can list the whole sample space and count with exact fractions. This program checks several results from this chapter.

from fractions import Fraction
from itertools import product, permutations
from math import prod

def prob(event, space):
    """Exact probability of an event over equally likely outcomes."""
    hits = sum(1 for s in space if event(s))
    return Fraction(hits, len(space))

dice = list(product(range(1, 7), repeat=2))
print("P(sum = 7)            =", prob(lambda s: s[0] + s[1] == 7, dice))

# Conditional: P(sum = 7 | at least one die shows 3)
given = [s for s in dice if 3 in s]
print("P(sum=7 | a 3 shows)  =", prob(lambda s: sum(s) == 7, given))

# Expectation of the sum of two dice
print("E[sum of two dice]    =", Fraction(sum(a + b for a, b in dice), len(dice)))

# Expected number of fixed points of a random permutation of 5 items
perms = list(permutations(range(5)))
fixed = sum(sum(p[i] == i for i in range(5)) for p in perms)
print("E[fixed points], n=5  =", Fraction(fixed, len(perms)))

# Birthday problem: smallest group with P(shared birthday) > 1/2
n = 1
while 1 - prod(Fraction(365 - i, 365) for i in range(n)) <= Fraction(1, 2):
    n += 1
print("Birthday threshold    =", n)

Output:

P(sum = 7)            = 1/6
P(sum=7 | a 3 shows)  = 2/11
E[sum of two dice]    = 7
E[fixed points], n=5  = 1
Birthday threshold    = 23

Restricting the list to the outcomes in F and recounting is exactly what conditional probability means: F becomes the new sample space.


Common Mistakes

  • Non-uniform sample spaces. Using sums of dice, or "number of heads", as if they were equally likely outcomes.

  • Confusing P(A | B) with P(B | A). P(positive | disease) = 0.99 but P(disease | positive) ≈ 0.17.

  • Confusing independent with mutually exclusive. Two events with positive probability cannot be both.

  • Adding probabilities of overlapping events. P(A ∪ B) = P(A) + P(B) only when A ∩ B = ∅.

  • Assuming Var(X + Y) = Var(X) + Var(Y) without independence. Linearity of expectation needs no independence; additivity of variance does.

  • Checking only pairs when the question asks about mutual independence of three or more events.


Interview and GATE-Style Questions

Q1. Three fair dice are rolled. What is the probability that the sum is 10?

There are 6³ = 216 outcomes. The number of solutions of a + b + c = 10 with 1 ≤ a, b, c ≤ 6 is 27 (by inclusion-exclusion: C(9, 2) − 3 · C(3, 2) = 36 − 9 = 27). So P = 27/216 = 1/8.

Q2. A box has 4 red and 6 black balls. Three are drawn without replacement. Find P(exactly 2 red).

C(4, 2) · C(6, 1) / C(10, 3) = 6 · 6 / 120 = 3/10.

Q3. A fair coin is tossed until the first head appears. What is the expected number of tosses?

The number of tosses is geometric with p = 1/2, so the expectation is 1/p = 2.

Q4. P(A) = 0.5, P(B) = 0.4 and A, B are independent. Find P(A ∪ B).

P(A ∩ B) = 0.5 × 0.4 = 0.2, so P(A ∪ B) = 0.5 + 0.4 − 0.2 = 0.7.

Q5. n balls are thrown independently and uniformly into n bins. What is the expected number of empty bins?

Bin i is empty with probability (1 − 1/n)n. By linearity with indicators, the expected number of empty bins is n(1 − 1/n)n, which is about n/e ≈ 0.368n for large n.

Q6. Can two events be both independent and mutually exclusive?

Only if at least one of them has probability 0. Mutually exclusive means P(A ∩ B) = 0; independence then requires P(A)P(B) = 0.

Q7. In randomised quicksort, two elements of rank i < j are compared with probability 2/(j − i + 1). How is this used to get the expected number of comparisons?

Let Xij be the indicator that ranks i and j are ever compared. The total number of comparisons is ∑ Xij over all pairs, so by linearity its expectation is ∑i<j 2/(j − i + 1), which is O(n log n). This is the indicator-variable method again.


Summary

  • Probability on a discrete sample space: non-negative weights summing to 1; with equally likely outcomes, P(E) = |E|/|S|.

  • Complement, inclusion-exclusion and the union bound are the basic rules. "At least one" → use the complement.

  • P(E | F) = P(E ∩ F)/P(F). Bayes' theorem reverses conditionals; always account for the base rate.

  • Independence means P(E ∩ F) = P(E)P(F). Pairwise independence does not imply mutual independence.

  • Expectation is linear even for dependent variables; indicator variables turn "expected count" questions into sums of probabilities.

  • Binomial: mean np, variance np(1 − p). Geometric: mean 1/p.

This completes our study of counting. The next chapter, Graph Theory Basics, begins the study of graphs, the structures behind networks, maps and much of algorithm design.