Probability Basics

Probability measures how likely an uncertain outcome is, on a scale from 0 to 1. Impossible events have probability 0 and the certain event has probability 1; in general these values mean almost never/almost surely, not necessarily an empty/full event. In computer science it is used to analyse randomised algorithms (expected running time of quicksort with a random pivot), hashing (collision probability), networks (packet loss, collision in shared media), reliability of systems, and machine learning. The topics set up the language: experiments, sample spaces, events, the axioms, and the rules that follow from them, including the difference between mutually exclusive and independent events. Conditional probability and random variables build directly on it.

A probability assigns to each event $A$ a number $P(A)$ such that:

Everything else is derived from these three axioms (Kolmogorov).

The three-event rule is inclusion-exclusion; the sums run over the three events and the three pairs.

If $S$ is finite and every outcome is equally likely,

The equally likely assumption must be justified by the set-up (fair coin, fair die, random selection). Sums of two dice are not equally likely: $P(\text{sum} = 7) = 6/36$ but $P(\text{sum} = 2) = 1/36$. Choose the sample space so that its outcomes are equally likely (ordered pairs of dice), then count.

When outcomes are not equally likely, $P(A)$ is the sum of the probabilities of the outcomes in $A$.

Drawing $k$ items from $N$, of which $K$ are "special":

Events $A$ and $B$ are independent if

Intuitively, knowing that $B$ occurred does not change the probability of $A$ (made precise with conditional probability). Facts:

These are different ideas; keep them apart.

If $P(A) > 0$ and $P(B) > 0$ and $A, B$ are mutually exclusive, then $P(A \cap B) = 0 \ne P(A)P(B)$: such events are dependent (if one happens, the other cannot).

When an outcome is a point chosen uniformly from a region (an interval, a square), probability is a ratio of lengths or areas:

For two independent numbers $X, Y$, each uniform on $[0, 1]$, the pair $(X, Y)$ is uniform on the unit square, so every event about $X$ and $Y$ is a region of that square and its probability is the region's area. Points and lines have area 0, so $P(X = Y) = 0$ and it does not matter whether an inequality is strict.

Two fair dice. $A$ = "sum is 7", $B$ = "first die is 1", $C$ = "sum is 8". $P(A) = 6/36 = 1/6$, $P(B) = 1/6$, $P(A \cap B) = 1/36 = P(A)P(B)$: independent. $P(C) = 5/36$, $P(B \cap C) = 0$ (the second die would need 7): $B$ and $C$ are mutually exclusive, hence dependent.

A system has 4 independent components, each failing with probability 0.1 during a day. $P(\text{at least one fails}) = 1 - 0.9^4 = 1 - 0.6561 = 0.3439$.

$k$ people, birthdays independent and uniform over 365 days (ignore leap years). $P(\text{all distinct}) = \dfrac{365 \cdot 364 \cdots (365 - k + 1)}{365^k}$. For $k = 23$, $P(\text{some shared birthday}) \approx 0.5073$, just above $1/2$. The same calculation bounds hash collisions: inserting $k$ keys into $m$ slots gives a collision with probability about $1 - e^{-k(k-1)/(2m)}$.

Two cards drawn without replacement from a standard 52-card deck. $P(\text{both aces}) = \binom{4}{2}/\binom{52}{2} = 6/1326 = 1/221$. With replacement: $(4/52)^2 = 1/169$.

Toss two fair coins. $A$ = "first is H", $B$ = "second is H", $C$ = "the two coins differ". Each has probability $1/2$, and each pair intersects in one outcome of probability $1/4$: pairwise independent. But $A \cap B \cap C = \emptyset$, so $P(A \cap B \cap C) = 0 \ne 1/8$: not mutually independent.

$P(A) = 0.5$, $P(B) = 0.4$, $P(A \cup B) = 0.7$. Then $P(A \cap B) = 0.5 + 0.4 - 0.7 = 0.2 = P(A)P(B)$, so $A, B$ are independent, and $P(\text{exactly one}) = 0.5 + 0.4 - 0.4 = 0.5$.

Two friends arrive independently at uniformly random times between 5:00 and 6:00, and each waits 15 minutes for the other. Measure time in hours after 5:00, so $X, Y$ are uniform on $[0, 1]$ and they meet if $|X - Y| \le 1/4$. The complement is two corner triangles of the unit square with legs $3/4$, of total area $(3/4)^2 = 9/16$. So $P(\text{meet}) = 1 - 9/16 = 7/16 = 0.4375$. With a waiting time $w$ (as a fraction of the window), $P(\text{meet}) = 1 - (1 - w)^2$. In the same square, $P(X + Y \le 1) = 1/2$ (a half-square triangle).

A number is drawn uniformly from $\{1, \ldots, 1000\}$. Let $A_d$ be "divisible by $d$"; the count of multiples of $d$ is $\lfloor 1000/d \rfloor$. Then $|A_2| = 500$, $|A_3| = 333$, $|A_5| = 200$, $|A_2 \cap A_3| = |A_6| = 166$, $|A_{10}| = 100$, $|A_{15}| = 66$, $|A_{30}| = 33$, and

The events are not independent here: $P(A_2)P(A_3)=0.1665\ne P(A_2\cap A_3)=0.166$. Always test independence by $P(A\cap B)=P(A)P(B)$. For divisibility events with pairwise coprime divisors, a uniform consecutive-integer range whose length is divisible by their product is a sufficient, not necessary, shortcut for independence.

$A$ and $B$ toss a fair coin alternately, $A$ first, and the first head wins. $A$ wins on toss 1, 3, 5, and so on:

The game ends with probability 1, so $P(B\text{ wins})=1/3$. In general, independent trials with common success probability $0<p\le1$, and $q=1-p$, give first-player win probability $p/(1-q^2)=1/(2-p)$. For a die and “first six wins”, this is $6/11$. At $p=0$, both win probabilities are zero and nontermination has probability one.

$n$ letters go into $n$ addressed envelopes at random. Let $A_i$ be "letter $i$ is in its own envelope". Any $k$ of these events occur together with probability $(n - k)!/n!$, and there are $\binom{n}{k}$ such groups, so inclusion-exclusion gives

For $n = 4$: $1 - 1 + \frac12 - \frac16 + \frac1{24} = \frac{9}{24} = \frac38$ (9 of the 24 permutations are derangements), so at least one letter is correct with probability $5/8$. The limit $1 - e^{-1} \approx 0.632$ is reached quickly: already for $n = 6$ the value is $0.6319$.