Basic Probability for Randomized Algorithms

$$\Pr[X = x, Y = y]$$

The probability that random variables $X$ and $Y$ have values $x$ and $y$, respectively.

$$\Pr[X = x\,|\,Y = y] = \frac{\Pr[X = x, Y = y]}{\Pr[Y = y]}$$

The probability that $X$ has value $x$ when $Y$ has value $y$

$$\Pr[X = x] = \sum_{y \in \Omega_Y} \Pr[X = x\,|\,Y = y]$$

Random variables $X$ and $Y$ are independent if for all $x \in \Omega_X$ and $y \in \Omega_Y$

$$\Pr[X = x] = \Pr[X = x\,|\,Y = y]$$

Let $S_1, S_2, \dots, S_k$ be a set of events occuring with probability $p_1, p_2, \dots, p_k.$

The probability that at least one of the events $S_1, S_2, \dots, S_k$ occurs is at most $p_1 + p_2 + \dots + p_k.$

The probability that none of the events $S_1, S_2, \dots, S_k$ occur is at least $1 - (p_1 + p_2 + \dots + p_k).$

Then,

$$\Pr[A \cup B] = \Pr[A] + \Pr[B] - \Pr[A \cap B].$$