Probability Toolkit

Events, conditioning, expectation and counting.

Probability Toolkit

The basic language of probability, from events and conditioning to expectation and the standard tricks for computing it.

Events and probability

Sample space – The set of all possible outcomes of an experiment, written SS. For one roll of a die, S={1,2,3,4,5,6}S = \{1, 2, 3, 4, 5, 6\}.

Event – Any subset EE of the sample space. The event "roll an even number" is E={2,4,6}E = \{2, 4, 6\}. We say EE occurred if the outcome lies in EE.

Axioms of probability – A probability PP assigns each event a number with three properties: 0≤P(E)≤10 \le P(E) \le 1, P(S)=1P(S) = 1, and for mutually exclusive events E1,…,EnE_1, \dots, E_n (no two can happen together)

P(⋃i=1nEi)=∑i=1nP(Ei)P\Big(\bigcup_{i=1}^n E_i\Big) = \sum_{i=1}^n P(E_i)

Complement – The event "EE does not happen", written EcE^c, has P(Ec)=1−P(E)P(E^c) = 1 - P(E).

"At least one" is usually easiest as 1−P(none)1 - P(\text{none}).

Inclusion–exclusion – For any two events,

P(A∪B)=P(A)+P(B)−P(A∩B)P(A \cup B) = P(A) + P(B) - P(A \cap B)

Counting

When all outcomes are equally likely, P(E)=number of outcomes in Enumber of outcomes in SP(E) = \dfrac{\text{number of outcomes in } E}{\text{number of outcomes in } S}, so probability reduces to counting. Here n!=n(n−1)⋯1n! = n(n-1)\cdots 1.

Choosing rr items from nnOrder mattersOrder doesn't matter
Without replacementn!(n−r)!\dfrac{n!}{(n-r)!} (permutations)(nr)=n!r! (n−r)!\dbinom{n}{r} = \dfrac{n!}{r!\,(n-r)!} (combinations)
With replacementnrn^r(n+r−1r)\dbinom{n+r-1}{r}

Derangement – A permutation in which no item stays in its original place. There are about n!/en!/e of them.

Example (birthday problem): among nn people, P(no shared birthday)=∏k=0n−1365−k365P(\text{no shared birthday}) = \prod_{k=0}^{n-1}\frac{365-k}{365}, which first drops below 1/21/2 at n=23n = 23 because there are already (232)=253\binom{23}{2} = 253 pairs.

Conditional probability

Conditional probability – The probability of AA given that BB happened, for P(B)>0P(B) > 0:

P(A∣B)=P(A∩B)P(B)P(A \mid B) = \frac{P(A \cap B)}{P(B)}

Rearranged, P(A∩B)=P(A∣B) P(B)P(A \cap B) = P(A \mid B)\,P(B).

Independence – AA and BB are independent if knowing one tells you nothing about the other:

P(A∩B)=P(A) P(B)P(A \cap B) = P(A)\,P(B)

Partition – Events B1,…,BnB_1, \dots, B_n form a partition if they are mutually exclusive and together cover SS.

Law of total probability – For a partition B1,…,BnB_1, \dots, B_n,

P(A)=∑i=1nP(A∣Bi) P(Bi)P(A) = \sum_{i=1}^n P(A \mid B_i)\,P(B_i)

Bayes' rule – Reverses the direction of conditioning:

P(B∣A)=P(A∣B) P(B)P(A)P(B \mid A) = \frac{P(A \mid B)\,P(B)}{P(A)}

P(B)P(B) is the prior (belief before seeing AA) and P(B∣A)P(B \mid A) the posterior (belief after).

Odds form of Bayes – The odds of HH are P(H)/P(not H)P(H)/P(\text{not } H). Then posterior odds = prior odds × likelihood ratio P(E∣H)/P(E∣not H)P(E \mid H)/P(E \mid \text{not } H).

Example: a disease has prevalence 1/1000 and a test is 99% accurate either way. Prior odds 1:9991{:}999 times likelihood ratio 9999 gives 99:99999{:}999, so a positive test means only about a 9% chance of disease. Rare conditions produce mostly false positives.

Random variables and expectation

Random variable – A function XX that maps each outcome to a number, e.g. the number of heads in 10 flips.

Expectation – The probability-weighted average value of XX, written E[X]\mathbb{E}[X]. For a discrete XX taking values xix_i,

E[X]=∑ixi P(X=xi)\mathbb{E}[X] = \sum_i x_i\,P(X = x_i)

Linearity of expectation – For any random variables, independent or not,

E[aX+bY]=a E[X]+b E[Y]\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]

Indicator – 1A\mathbf{1}_A equals 11 if event AA happens and 00 otherwise, so E[1A]=P(A)\mathbb{E}[\mathbf{1}_A] = P(A). Writing a count as a sum of indicators, X=∑i1AiX = \sum_i \mathbf{1}_{A_i}, gives E[X]=∑iP(Ai)\mathbb{E}[X] = \sum_i P(A_i).

Example: nn hats are handed back at random. Person ii gets their own with probability 1/n1/n, so the expected number of matches is n⋅1/n=1n \cdot 1/n = 1, for every nn.

Tail sum – For XX taking values 0,1,2,…0, 1, 2, \dots:

E[X]=∑k≥0P(X>k)\mathbb{E}[X] = \sum_{k \ge 0} P(X > k)

Variance – How spread out XX is around its mean μ=E[X]\mu = \mathbb{E}[X]. The standard deviation is σ=Var⁡(X)\sigma = \sqrt{\operatorname{Var}(X)}, in the same units as XX.

Var⁡(X)=E[(X−μ)2]=E[X2]−μ2,Var⁡(aX+b)=a2Var⁡(X)\operatorname{Var}(X) = \mathbb{E}\big[(X - \mu)^2\big] = \mathbb{E}[X^2] - \mu^2, \qquad \operatorname{Var}(aX + b) = a^2\operatorname{Var}(X)

Covariance and correlation – How two variables move together. Correlation ρ\rho rescales covariance into [−1,1][-1, 1].

Cov⁡(X,Y)=E[XY]−E[X] E[Y],ρXY=Cov⁡(X,Y)σX σY\operatorname{Cov}(X, Y) = \mathbb{E}[XY] - \mathbb{E}[X]\,\mathbb{E}[Y], \qquad \rho_{XY} = \frac{\operatorname{Cov}(X, Y)}{\sigma_X\,\sigma_Y} Var⁡(∑iXi)=∑iVar⁡(Xi)+2∑i<jCov⁡(Xi,Xj)\operatorname{Var}\Big(\sum_i X_i\Big) = \sum_i \operatorname{Var}(X_i) + 2\sum_{i<j}\operatorname{Cov}(X_i, X_j)

Independent variables have zero covariance, but not conversely: XX uniform on [−1,1][-1, 1] and Y=X2Y = X^2 are uncorrelated yet dependent.

Conditional expectation – E[X∣Y]\mathbb{E}[X \mid Y] is the average of XX once YY is known; it is itself a random variable (a function of YY).

Law of total expectation and variance –

E[X]=E[E[X∣Y]],Var⁡(X)=E[Var⁡(X∣Y)]+Var⁡(E[X∣Y])\mathbb{E}[X] = \mathbb{E}\big[\mathbb{E}[X \mid Y]\big], \qquad \operatorname{Var}(X) = \mathbb{E}\big[\operatorname{Var}(X \mid Y)\big] + \operatorname{Var}\big(\mathbb{E}[X \mid Y]\big)

Problem-solving techniques

First-step analysis – Condition on what happens first and write equations for the unknown quantities. For the expected number of fair-coin flips until two heads in a row, let aa be the expected flips from scratch and bb the expected flips remaining after one head:

a=1+12b+12a,b=1+12a⇒a=6a = 1 + \tfrac12 b + \tfrac12 a, \qquad b = 1 + \tfrac12 a \quad\Rightarrow\quad a = 6

Geometric waiting time – If each independent trial succeeds with probability pp, the expected number of trials to the first success is 1/p1/p. Chaining these gives the coupon collector result: about nln⁡nn \ln n draws to see all nn equally likely types.

Symmetry – Interchangeable objects have equal expectations. The 4 aces split the other 48 cards into 5 gaps of equal expected size 48/548/5, so the first ace sits at position 48/5+1=10.648/5 + 1 = 10.6 on average.

Recursion on the state – Two players alternate rolling a die; the first to roll a 6 wins. If pp is the first player's chance, then p=16+56(1−p)p = \tfrac16 + \tfrac56(1 - p), so p=6/11p = 6/11.