COMP4804: Algorithms II
Review of Basic Probability

Here are my original hand-written notes on this topic.

Probability function

In general $\Pr\{A\cup B\} = \Pr\{A\} + \Pr\{B\} - \Pr\{A\cap B\}$ because the first two terms count $\Pr\{A\cap B\}$ twice

Venn Diagram

this is called the inclusion-exclusion formula. We immediately get Boole's Inequality: \[ \Pr\{A \cup B\} \le \Pr\{A\} + \Pr\{B\} \enspace. \] Boole's Inequality is also called the union bound.

Some terminology


Calculating some probabilities

Expectation and Random Variables

Linearity of Expectation

If you're interested in a proof of linearity of expectation, here it is: \begin{align*} \E[X+Y] & = \sum_{x}\sum_y (x+y)\Pr\{\text{$X=x$ and $Y=y$}\} \\ & = \sum_{x}\sum_y x\Pr\{\text{$X=x$ and $Y=y$}\} + \sum_{x}\sum_y y\Pr\{\text{$X=x$ and $Y=y$}\} \\ & = \sum_{x}\sum_y x\Pr\{\text{$X=x$ and $Y=y$}\} + \sum_y\sum_{x} y\Pr\{\text{$X=x$ and $Y=y$}\} \\ & = \sum_{x}x\sum_y \Pr\{\text{$X=x$ and $Y=y$}\} + \sum_y y\sum_{x} \Pr\{\text{$X=x$ and $Y=y$}\} \\ & = \sum_{x} x\Pr\{\text{$X=x$}\} + \sum_y y\Pr\{\text{$Y=y$}\} \notag \\ & = \E[X] + \E[Y] \notag \end{align*} Not very enlightening. The key step is where the number of summation symbols goes from 4 down to 2. This is possible, because when we sum, over all $y$, $\Pr\{\text{$X=x$ and $Y=y$}\}$ we get $\Pr\{X=x\}$. The Venn diagram below shows an example of this. Here the event $X=x$ is shown as a pink circle. The different possible values of $Y$ are shown as blobs and they have to cover the pink circle because they cover all of $U$.

the key step in proving linear of expectation

More Indicator Variable Examples

Indicator variables, along with linearity of expectation are an extremely efficient way of computing expected values.

Balls in Urns

Throw $n$ balls into $m$ urns in such a way that each ball is equally likely to land in any urn. (Exercise: Check, using the definition of a probability function, that this implies $\Pr\{\text{ball $i$ lands in urn 1}\}=1/m$). What is the expected number of balls in the first urn?

Define \[ I_i = \begin{cases} 1 & \text{if ball $i$ lands in urn 1} \\ 0 & \text{otherwise} \end{cases} \] Then \[ \E[I_i] = \Pr\{\text{ball $i$ lands in urn 1}\}\times 1 = 1/m \] So \[ \E[I_1+\cdots I_n] = \E[I_1] + \cdots \E[I_n] = n/m \] Done.


Take a random permutation $x_1,\ldots,x_n$ of $1,\ldots, n$. Call $x_i$ a record if $x_i=\max\{x_1,\ldots,x_i\}$. What is the expected number of records?

Define \[ I_i = \begin{cases} 1 & \text{if $x_i=\max\{x_1,\ldots,x_i\}$} \\ 0 & \text{otherwise} \end{cases} \] The largest value among $x_1,\ldots,x_i$ is equally likely to be any of $x_1,\ldots,x_i$, so $\Pr\{x_i=\max\{x_1,\ldots,x_i\}\} = 1/i$. So, \[ \E[I_i] = 1/i \] So, the expected number of records is \[ \E[I_1+\cdots+I_n] = \E[I_1] + \cdots \E[I_n] = 1 + 1/2 + 1/3+\cdots 1/n \] The sum $1+1/2+\cdots 1/n$ is called the $n$th harmonic number, $H_n$. Using the fact that $\int_1^n 1/x\,dx = \ln n$, We can easily show that $\ln n \le H_n \le \ln n+1$:

Harmonic upper bound Harmonic lower bound