Probability Toolkit
Events, conditioning, expectation and counting.
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 . For one roll of a die, .
Event – Any subset of the sample space. The event "roll an even number" is . We say occurred if the outcome lies in .
Axioms of probability – A probability assigns each event a number with three properties: , , and for mutually exclusive events (no two can happen together)
Complement – The event " does not happen", written , has .
"At least one" is usually easiest as .
Inclusion–exclusion – For any two events,
Counting
When all outcomes are equally likely, , so probability reduces to counting. Here .
| Choosing items from | Order matters | Order doesn't matter |
|---|---|---|
| Without replacement | (permutations) | (combinations) |
| With replacement |
Derangement – A permutation in which no item stays in its original place. There are about of them.
Example (birthday problem): among people, , which first drops below at because there are already pairs.
Conditional probability
Conditional probability – The probability of given that happened, for :
Rearranged, .
Independence – and are independent if knowing one tells you nothing about the other:
Partition – Events form a partition if they are mutually exclusive and together cover .
Law of total probability – For a partition ,
Bayes' rule – Reverses the direction of conditioning:
is the prior (belief before seeing ) and the posterior (belief after).
Odds form of Bayes – The odds of are . Then posterior odds = prior odds × likelihood ratio .
Example: a disease has prevalence 1/1000 and a test is 99% accurate either way. Prior odds times likelihood ratio gives , 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 that maps each outcome to a number, e.g. the number of heads in 10 flips.
Expectation – The probability-weighted average value of , written . For a discrete taking values ,
Linearity of expectation – For any random variables, independent or not,
Indicator – equals if event happens and otherwise, so . Writing a count as a sum of indicators, , gives .
Example: hats are handed back at random. Person gets their own with probability , so the expected number of matches is , for every .
Tail sum – For taking values :
Variance – How spread out is around its mean . The standard deviation is , in the same units as .
Covariance and correlation – How two variables move together. Correlation rescales covariance into .
Independent variables have zero covariance, but not conversely: uniform on and are uncorrelated yet dependent.
Conditional expectation – is the average of once is known; it is itself a random variable (a function of ).
Law of total expectation and variance –
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 be the expected flips from scratch and the expected flips remaining after one head:
Geometric waiting time – If each independent trial succeeds with probability , the expected number of trials to the first success is . Chaining these gives the coupon collector result: about draws to see all equally likely types.
Symmetry – Interchangeable objects have equal expectations. The 4 aces split the other 48 cards into 5 gaps of equal expected size , so the first ace sits at position on average.
Recursion on the state – Two players alternate rolling a die; the first to roll a 6 wins. If is the first player's chance, then , so .