CSCI 328 - Formulas & Identities Cheatsheet

This cheatsheet captures all major formulas and identities from the course, organized by topic for quick reference during problem-solving and exam preparation.

PART I: BASIC PROBABILITY & EXPECTATION

Complement Rule

\Pr(A^c) = 1 - \Pr(A)

Independence of Events

Two events $A$ and $B$ are independent if:

\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)

Linearity of Expectation

For any random variables $X_1, X_2, \ldots, X_n$ (with or without independence):

E\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n E[X_i]

Union Bound

\Pr(A_1 \cup A_2 \cup \cdots \cup A_n) \leq \sum_{i=1}^n \Pr(A_i)

PART II: RANDOM VARIABLES & DISTRIBUTIONS

Indicator Random Variable

For an event $A$ :

X_A = \begin{cases} 1 & \text{if } A \text{ occurs} \\ 0 & \text{otherwise} \end{cases}, \quad E[X_A] = \Pr(A)

Bernoulli Distribution

$X \sim \text{Bernoulli}(p)$ :

E[X] = p, \quad \text{Var}(X) = p(1-p) = p \cdot q \quad \text{(where } q = 1-p\text{)}

Binomial Distribution

$X \sim \text{Binomial}(n, p)$ (sum of $n$ independent Bernoulli trials):

E[X] = np, \quad \text{Var}(X) = np(1-p) = npq

\Pr(X = k) = \binom{n}{k} p^k (1-p)^{n-k}

Geometric Distribution

$X \sim \text{Geometric}(p)$ (number of trials until first success):

E[X] = \frac{1}{p}, \quad \text{Var}(X) = \frac{1-p}{p^2}

Coupon Collector Problem

Expected number of items needed to collect all $n$ distinct types (with uniform sampling):

E[\text{\# items}] = n \left(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\right) = n H_n \approx n \ln n

where $H_n$ is the $n$ -th harmonic number.

PART III: VARIANCE & COVARIANCE

Variance Formula

\text{Var}(X) = E[X^2] - (E[X])^2

Variance of Sum (Independent Variables)

If $X_1, X_2, \ldots, X_n$ are independent:

\text{Var}\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n \text{Var}(X_i)

Standard Deviation

\sigma = \sqrt{\text{Var}(X)}

PART IV: CONCENTRATION INEQUALITIES

Markov’s Inequality

For any non-negative random variable $X$ and $t > 0$ :

\Pr(X \geq t) \leq \frac{E[X]}{t}

Intuition: Probability of extreme deviation is bounded by expected value ratio.

Chebyshev’s Inequality

For any random variable $X$ and $t > 0$ :

\Pr(|X - E[X]| \geq t) \leq \frac{\text{Var}(X)}{t^2}

Alternatively:

\Pr(X \geq t) \leq \frac{\text{Var}(X)}{t^2}

Intuition: Values far from the mean are unlikely if variance is small.

Chernoff Bounds

For $X = \sum_{i=1}^n X_i$ where $X_i$ are independent Bernoulli random variables, and $\mu = E[X]$ :

(1) General Form — For any $\delta > 0$ :

\Pr(X \geq (1+\delta)\mu) \leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu

(2) Simplified Form — For $0 < \delta \leq 1$ :

\Pr(X \geq (1+\delta)\mu) \leq e^{-\mu\delta^2/3}

(3) For Large Deviations — For $R \geq 6\mu$ :

\Pr(X \geq R) \leq 2^{-R}

Intuition: Exponential bounds for sums of independent Bernoulli variables.

PART VI: BIRTHDAY PARADOX & COLLISION PROBABILITY

Exact Collision Probability

Probability that $m$ balls thrown into $n$ bins have no collisions:

\Pr(\text{no collision}) = \frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{n-m+1}{n}

This can be written as:

\Pr(\text{no collision}) = \prod_{i=0}^{m-1} \left(1 - \frac{i}{n}\right)

Approximate Collision Probability (for $m^2 \ll n$ )

\Pr(\text{collision}) \approx 1 - e^{-m^2/(2n)}

Birthday Paradox (specific case: $n = 365$ , $m = 23$ )

Probability that 23 people have a shared birthday exceeds 50%.

PART VII: BALLS AND BINS

Probability a Bin Remains Empty

When $n$ balls are thrown into $n$ bins:

\Pr(\text{bin is empty}) = (1 - 1/n)^n \approx e^{-1}

Expected Number of Empty Bins

E[\text{\# empty bins}] = n \cdot e^{-1} \approx 0.368n

Expected Maximum Load