Discrete Distributions

Overview

Discrete distributions model random variables that take countable values. This topic covers the foundational tools (PMF, CDF) and the full catalog of classical discrete distributions organized by family — Bernoulli, waiting time, counting, and uniform. Each distribution is presented with its key formulas, MGF, and typical interview use cases.

1. General Discrete Random Variable

1.1 Definition & PMF

Definition

A random variable $X$ is discrete if it takes values in a countable set $\mathcal{X} \subseteq \mathbb{R}$ . Its distribution is characterized by its probability mass function (PMF):

\boxed{p_X(k) = P(X = k), \quad k \in \mathcal{X}}

satisfying $p_X(k) \geq 0$ for all $k$ and $\displaystyle\sum_{k \in \mathcal{X}} p_X(k) = 1$ .

1.2 Cumulative Distribution Function

Definition

The CDF of a discrete random variable $X$ is:

\boxed{F_X(x) = P(X \leq x) = \sum_{k \leq x} p_X(k)}

Remarque

For discrete RVs, $F_X$ is a right-continuous step function with jumps of size $p_X(k)$ at each value $k \in \mathcal{X}$ . In particular .

1.3 Expectation & Variance

Formula— Expectation

\boxed{E[X] = \sum_{k \in \mathcal{X}} k\, p_X(k)}

Formula— Variance

\boxed{\text{Var}(X) = E[X^2] - (E[X])^2 = \sum_{k \in \mathcal{X}} k^2\, p_X(k) - \left(\sum_{k \in \mathcal{X}} k\, p_X(k)\right)^2}

Formula— Tail Formula for non-negative integer-valued

X

\boxed{E[X] = \sum_{k=1}^{\infty} P(X \geq k) = \sum_{k=0}^{\infty} P(X > k)}

💡Tip

The tail formula is the fastest way to compute $E[X]$ for geometric and negative binomial distributions — avoid expanding the series directly.

2. Bernoulli Family

2.1 Bernoulli $(p)$

Definition

A Bernoulli random variable models a single trial with success probability $p \in [0,1]$ :

\boxed{X \sim \text{Bernoulli}(p) \iff P(X=1) = p, \quad P(X=0) = 1-p}

Properties

$E[X] = p$
$\text{Var}(X) = p(1-p)$
$F_{X} (x) = (1 - p) 1_{}$

2.2 Binomial $(n, p)$

Definition

A Binomial random variable counts the number of successes in $n$ independent Bernoulli $(p)$ trials:

\boxed{X \sim \text{Bin}(n,p) \iff P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}, \quad k = 0, 1, \ldots, n}

Properties

$E[X] = np$
$\text{Var}(X) = np(1-p)$
$F_{X} (k) =$

Remarque

$\text{Bernoulli}(p) = \text{Bin}(1, p)$ . The binomial is the sum of $n$ i.i.d. Bernoulli $(p)$ variables — this is the key structural fact used in most proofs.

💡Tip

Use Binomial when: fixed number of trials $n$ , each trial independent, same success probability $p$ . When $n$ is large and $p$ small with $np = \lambda$ fixed, approximate with Poisson $(\lambda)$ .

2.3 Multinomial $(n, p_1, \ldots, p_k)$

Definition

The Multinomial distribution generalizes the Binomial to $k$ possible outcomes. If $n$ independent trials each result in outcome $i$ with probability $p_i$ (with $\sum_{i=1}^k p_i = 1$ ), the joint PMF of is:

Properties

$E[X_i] = np_i$
$\text{Var}(X_i) = np_i(1-p_i)$

Remarque

The negative covariance $\text{Cov}(X_i, X_j) < 0$ makes sense: if category $i$ gets more counts, category must get fewer (the total is fixed at ).

3. Waiting Time Family

3.1 Geometric $(p)$

Definition

A Geometric random variable counts the number of trials until the first success in independent Bernoulli $(p)$ trials:

\boxed{X \sim \text{Geom}(p) \iff P(X=k) = (1-p)^{k-1}p, \quad k = 1, 2, 3, \ldots}

Properties

$E[X] = \dfrac{1}{p}$
$\text{Var}(X) = \dfrac{1-p}{p^2}$

Remarque

The memoryless property is unique to the geometric distribution among discrete distributions (and to the exponential among continuous). It states that past failures give no information about future trials.

💡Tip

Use Geometric for: "number of trials until first success", "number of coin flips until first head", coupon collector sub-problems. The memoryless property is the key to many elegant solutions.

3.2 Negative Binomial $(r, p)$

Definition

A Negative Binomial random variable counts the number of trials until the $r$ -th success:

\boxed{X \sim \text{NB}(r,p) \iff P(X=k) = \binom{k-1}{r-1} p^r (1-p)^{k-r}, \quad k = r, r+1, \ldots}

Properties

$E[X] = \dfrac{r}{p}$
$\text{Var}(X) = \dfrac{r(1-p)}{p^2}$

💡Tip

Use Negative Binomial when: waiting for the $r$ -th success, modeling overdispersed count data (variance $>$ mean). The decomposition as a sum of $r$ geometrics makes moment calculations immediate.

4. Counting Family

4.1 Poisson $(\lambda)$

Definition

A Poisson random variable counts the number of events occurring in a fixed interval, with average rate $\lambda > 0$ :

\boxed{X \sim \text{Poisson}(\lambda) \iff P(X=k) = e^{-\lambda}\frac{\lambda^k}{k!}, \quad k = 0, 1, 2, \ldots}

Properties

$E[X] = \lambda$
$\text{Var}(X) = \lambda$
$F_X(k) = e^{-\lambda}\displaystyle\sum_{j=0}^{k} \frac{\lambda^j}{j!}$

Remarque

The Poisson distribution has the unique property that mean = variance = $\lambda$ . In practice: if you observe count data with mean $\approx$ variance, Poisson is the natural model. If variance $>$ mean (overdispersion), use Negative Binomial.

💡Tip

Use Poisson for: number of rare events in a large population ( $n$ large, $p$ small, $np = \lambda$ ), arrivals in a time window, number of defaults in a portfolio. The stability under addition ( $\text{Poisson}(\lambda) + \text{Poisson}(\mu) = \text{Poisson}(\lambda+\mu)$ ) is the key property.

4.2 Hypergeometric $(N, K, n)$

Definition

A Hypergeometric random variable counts the number of successes when drawing $n$ items without replacement from a population of $N$ items containing $K$ successes:

X \sim Hyper (N, K, n) ⟺ P (X = k) = \frac{(\binom{K}{k}) (\binom{N - K}{n - k})}{(}

Properties

$E[X] = n\dfrac{K}{N}$
$\text{Var}(X) = n\dfrac{K}{N}\cdot\dfrac{N-K}{N}\cdot\dfrac{N-n}{N-1}$

Remarque

The factor $\dfrac{N-n}{N-1}$ is the finite population correction — it accounts for the dependence between draws. When $N \gg n$ , draws are nearly independent and Hypergeometric $\approx$ Binomial.

💡Tip

Use Hypergeometric whenever sampling is without replacement from a finite population — card games, quality control, drawing from an urn without replacement.

5. Discrete Uniform

5.1 Uniform $\{1, \ldots, n\}$

Definition

A Discrete Uniform random variable assigns equal probability to each value in $\{1, 2, \ldots, n\}$ :

\boxed{X \sim \text{Uniform}\{1,\ldots,n\} \iff P(X=k) = \frac{1}{n}, \quad k = 1, \ldots, n}

Properties

$E[X] = \dfrac{n+1}{2}$
$\text{Var}(X) = \dfrac{n^2-1}{12}$

6. Quick Reference

Full Summary Table

Distribution	Parameters	$P(X=k)$	$E[X]$	$\text{Var}(X)$	$M_X(t)$

Key Relationships

Relationship	Statement
Bernoulli → Binomial	Sum of $n$ i.i.d. Bernoulli $(p)$ $\sim$ Bin $(n,p)$
Geometric → Neg. Binomial	Sum of $r$ i.i.d. Geom $(p)$ NB

Bernoulli $(p)$	$p \in [0,1]$	$p^k(1-p)^{1-k}$ , $k\in\{0,1\}$	$p$	$p(1-p)$	$1-p+pe^t$	Single trial
Binomial $(n,p)$	$n \in \mathbb{N}$ , $p\in[0,1]$	$\binom{n}{k}p^k(1-p)^{n-k}$
Geometric $(p)$	$p \in (0,1]$	$(1-p)^{k-1}p$
Neg. Binom $(r,p)$	$r \in \mathbb{N}$ , $p\in(0,1]$	$\binom{k-1}{r-1}p^r(1-p)^{k-r}$
Poisson $(\lambda)$	$\lambda > 0$	$e^{-\lambda}\frac{\lambda^k}{k!}$
Hypergeometric $(N,K,n)$	$N,K,n \in \mathbb{N}$	$\frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$
Uniform $\{1,\ldots,n\}$	$n \in \mathbb{N}$	$\frac{1}{n}$	$\frac{}{}$

Discrete Distributions

1. General Discrete Random Variable

1.1 Definition & PMF

1.2 Cumulative Distribution Function

1.3 Expectation & Variance

2. Bernoulli Family

2.1 Bernoulli(p)(p)(p)

2.2 Binomial(n,p)(n, p)(n,p)

2.3 Multinomial(n,p1,…,pk)(n, p_1, \ldots, p_k)(n,p1​,…,pk​)

3. Waiting Time Family

3.1 Geometric(p)(p)(p)

3.2 Negative Binomial(r,p)(r, p)(r,p)

4. Counting Family

4.1 Poisson(λ)(\lambda)(λ)

4.2 Hypergeometric(N,K,n)(N, K, n)(N,K,n)

5. Discrete Uniform

5.1 Uniform{1,…,n}\{1, \ldots, n\}{1,…,n}

6. Quick Reference

Full Summary Table

Key Relationships

2.1 Bernoulli $(p)$

2.2 Binomial $(n, p)$

2.3 Multinomial $(n, p_1, \ldots, p_k)$

3.1 Geometric $(p)$

3.2 Negative Binomial $(r, p)$

4.1 Poisson $(\lambda)$

4.2 Hypergeometric $(N, K, n)$

5.1 Uniform $\{1, \ldots, n\}$