Probability

• RandInt(m): 1, 2, 3, … m with $p=\frac{1}{m}$
• Bernoulli(p): 1 with $p=p$

outcome: A leaf in probability tree

Sample Space: Set of all outcomes

Event: A subset of outcomes

Law of Total Probability: $p[b] = p[a] p[b|a] + p[a^c] p[b|a^c]$

Independence of Multiple Events: for all subsets, for all size.

Random Variable: function from sample space to reals.

Indicator: R.V. x which is 1 when event A occurs, 0 otherwise.