Discrete Random Variables and Their Distributions

Motivation: from outcomes to numbers

A limitation of the event-level view of probability-foundations motivates this chapter: we usually care about a number, not the outcome. Rolling two dice, we care that the sum is 7, not which of $(1,6),(2,5),\dots$ occurred. Flipping coins, we care how many heads, not the exact sequence. A random variable packages an experiment’s outcome into a number, and its probability mass function packages the outcome’s probability.

IntuitionThe central questions

How do we summarize an experiment by a numerical quantity and its distribution, what are the summary statistics (mean, variance) of that distribution, and — for the workhorse model of repeated independent trials — what are the resulting named distributions of counts and waiting times, and how do they show up in reliability engineering?

Tool	Packages	Summary statistics / rules
random variable + pmf	outcome → number; probability → pmf	mean, variance
Bernoulli trial family	counts and waits in independent trials	Bernoulli, binomial, geometric, negative binomial
reliability	independent component/link failures	union bound, network outage, hazard functions

NoteConditioning and independence live in a companion note

Conditional probability, independence of events, independent random variables, the law of total probability, and Bayes’ formula are covered in conditional-probability-and-independence — split out from this note because they apply to events in general, not just to the distributions covered here.

Random variables and probability mass functions

DefinitionRandom variable (Hajek Def. 2.1.1)

A random variable is a real-valued function $X : \Omega\to\mathbb R$ . When the experiment selects $\omega$ , the realized value is $X(\omega)$ . For $A\subseteq\mathbb R$ , $\{X\in A\} = \{\omega : X(\omega)\in A\}$ is an event, and we write $P\{X\in A\}$ .

IntuitionAn event is a binary random variable

An event either occurs or it doesn’t, which is a 0/1 quantity. A random variable generalizes this to many values. The indicator of $A$ is $I_A(\omega) = 1$ if $\omega\in A$ and $0$ otherwise.

DefinitionDiscrete type, pmf, support

$X$ is discrete-type if there is a finite or countably infinite set $\{u_1,u_2,\dots\}$ with $P\{X\in\{u_1,u_2,\dots\}\} = 1$ . Its probability mass function is $p_X(u) = P\{X = u\},\qquad \sum_ip_X(u_i) = 1. \tag{2.1}$ The support is $\{u : p_X(u) > 0\}$ . The pmf determines every event about $X$ : $P\{X\in A\} = \sum_{i:\,u_i\in A}p_X(u_i)$ .

Component	Detail
Signature	$p_X : \mathbb R\to[0,1]$
Domain	a candidate value $u$ of $X$
Codomain	the probability that $X$ takes exactly that value
Not an input	the outcome $\omega$ ; the pmf forgets which outcomes produced $u$

DefinitionCumulative distribution function (Ross)

$F(x) = P\{X\le x\} = \sum_{u\le x}p(u),\qquad -\infty < x < \infty.$ $F$ is nondecreasing: if $a\le b$ , then $\{X\le a\}\subset\{X\le b\}$ . For discrete $X$ , $F$ is a step function that jumps by $p(x_i)$ at each $x_i$ and is constant in between.

ExampleA pmf and its cdf

$p(1) = \frac14$ , $p(2) = \frac12$ , $p(3) = p(4) = \frac18$ gives

F(a) = \begin{cases}0 & a < 1\\ \frac14 & 1\le a < 2\\ \frac34 & 2\le a < 3\\ \frac78 & 3\le a < 4\\ 1 & a\ge 4.\end{cases}

The step at each value equals its probability mass.

The running example: dice

Random variable (two fair dice, 36 equally likely outcomes)	pmf
one die $X$	$p_X(i) = \frac16$ , $i = 1..6$
sum $S$	$p_S(k) = \frac{6 - \lvert k-7\rvert}{36}$ , $k = 2..12$ (peak $\frac16$ at 7)
maximum $Y = \max\{i,j\}$	$p_Y(k) = \frac{2k-1}{36}$ : $\frac1{36},\frac3{36},\dots,\frac{11}{36}$
product $X_1X_2$	read off the $6\times6$ multiplication table

DerivationWhere the closed forms come from

Sum. The outcomes with $i + j = k$ lie on an anti-diagonal of the $6\times6$ grid. Its length is $k - 1$ for $k\le7$ and $13 - k$ for $k\ge7$ , i.e. $6 - |k-7|$ .

Maximum. $\{Y\le k\}$ is a $k\times k$ square, so $P\{Y = k\} = \frac{k^2 - (k-1)^2}{36} = \frac{2k-1}{36}$ .

(The chapter shows these as figures. The closed forms are mine.)

ExampleMore pmfs from counting (Ross)

Heads in 3 fair coins: $\frac18,\frac38,\frac38,\frac18$ for $0,1,2,3$ .
Two insured clients dying independently with probabilities .05 and .10 (payout units of $100k): $P\{X = 0\} = .95\cdot.9 = .855$ , $P\{X = 1\} = .05\cdot.9 + .95\cdot.1 = .140$ , $P\{X = 2\} = .005$ .
Largest of 4 balls drawn from 1..20: $P\{X = i\} = \binom{i-1}3/\binom{20}4$ for $i = 4..20$ . More directly, $P\{X > 10\} = 1 - \binom{10}4/\binom{20}4 = 1 - \frac{210}{4845}\approx 0.957$ .
Flip until a head or $n$ flips: $P\{X = i\} = (1-p)^{i-1}p$ for $i < n$ , and $P\{X = n\} = (1-p)^{n-1}$ . The masses sum to 1 via the geometric series.
Normalizing a pmf: $p(i) = c\lambda^i/i!$ forces $c = e^{-\lambda}$ (the Poisson form). Then $P\{X > 2\} = 1 - e^{-\lambda}(1 + \lambda + \lambda^2/2)$ .

ExampleCoupon collecting (Ross)

There are $r$ equally likely coupon types. Let $T$ be the number of draws until every type has appeared. With $A_j$ = “type $j$ missing from the first $n$ draws”, $P(A_{j_1}\cdots A_{j_k}) = \big(\frac{r-k}r\big)^n$ , so by inclusion–exclusion

P\{T > n\} = \sum_{i=1}^{r-1}\binom ri\Big(\frac{r-i}r\Big)^n(-1)^{i+1}, \qquad P\{T = n\} = P\{T > n-1\} - P\{T > n\}. \tag{1.1}

Boole bound: $P\{T > n\}\le r(1 - \frac1r)^n\le re^{-n/r}$ , using $e^{-x}\ge1 - x$ .

Distinct types among $n$ draws, $D_n$ : choose which $k$ types appear ( $\binom rk$ ), require all $n$ draws to land in them ( $(k/r)^n$ ), and require all $k$ to be represented (use (1.1) with $k$ types):

P\{D_n = k\} = \binom rk\Big(\frac kr\Big)^n\Big[1 - \sum_{i=1}^{k-1} \binom ki\Big(\frac{k-i}k\Big)^n(-1)^{i+1}\Big].

The mean and variance of a random variable

Expectation

DefinitionMean (expectation, first moment)

$E[X] = \sum_iu_i\,p_X(u_i).$ This is a weighted average of the possible values, weighted by their probabilities.

IntuitionTwo readings

Frequency: over many independent plays, a value $x_i$ occurs a fraction $p(x_i)$ of the time, so the average winnings per game converge to $\sum x_ip(x_i)$ .
Mechanics: put mass $p(x_i)$ at position $x_i$ on a weightless rod. $E[X]$ is the balance point, because $\sum_i(x_i - E[X])p(x_i) = 0$ means the torques cancel.

ExampleFirst computations

Fair die: $E[X] = \frac{1+\cdots+6}6 = \frac72$ .
Indicator of $A$ : $E[I_A] = 1\cdot P(A) + 0\cdot P(A^c) = P(A)$ . The expectation of an indicator is a probability. This is a workhorse identity.
Distinct numbers $Y$ on three dice (Hajek): $|\{Y = 1\}| = 6$ , $|\{Y = 2\}| = 6\cdot5\cdot3 = 90$ , $|\{Y = 3\}| = 6\cdot5\cdot4 = 120$ . These sum to 216, as a check. So $E[Y] = 1\cdot\tfrac1{36} + 2\cdot\tfrac{15}{36} + 3\cdot\tfrac{20}{36} = \tfrac{91}{36}\approx2.53.$

WarningThe mean is not the average of the possible values

$E[Y]\ne\frac{1+2+3}3$ for the three-dice example, because the values are not equally likely.

ExampleThe bus paradox — size-biased sampling (Ross)

120 students ride buses of 36, 40 and 44 students. Pick a student at random and let $X$ be the size of their bus:

E[X] = 36\cdot\tfrac{36}{120} + 40\cdot\tfrac{40}{120} + 44\cdot \tfrac{44}{120}\approx40.27 > 40 = \text{average bus size}.

Bigger buses contain more students, so a random student is more likely to be on one.

ExampleWhich question first? (Ross)

Answering question $i$ correctly pays $V_i$ and happens with probability $P_i$ (independently). You may attempt the second question only if the first is right. Starting with question 1 is better iff $\frac{V_1P_1}{1-P_1}\ge\frac{V_2P_2}{1-P_2}.$ With $(V_1,P_1) = (200, .6)$ and $(V_2,P_2) = (100, .8)$ : $300 < 400$ , so start with the cheaper, surer question.

DerivationThe comparison

Question 1 first earns $V_1P_1(1-P_2) + (V_1+V_2)P_1P_2$ . Question 2 first earns $V_2P_2(1-P_1) + (V_1+V_2)P_1P_2$ . The shared term cancels, leaving $V_1P_1(1-P_2)$ vs $V_2P_2(1-P_1)$ . Divide by $(1-P_1)(1-P_2)$ .

The law of the unconscious statistician

The problem. To find $E[g(X)]$ by definition, you’d first compute the pmf of $Y = g(X)$ by merging values of $X$ that map to the same $y$ . That is tedious.

TheoremLOTUS (Hajek eq. 2.2; Ross Prop. 4.1)

$E[g(X)] = \sum_ig(u_i)\,p_X(u_i).$ Similarly $E[g(X,Y)] = \sum_{i,j}g(u_i,v_j)P\{X = u_i, Y = v_j\}$ .

ProofGroup terms with equal

g

-values

Let $y_1, y_2, \dots$ be the distinct values of $g(x_i)$ . Then

\sum_ig(x_i)p(x_i) = \sum_j\sum_{i:\,g(x_i) = y_j}y_jp(x_i) = \sum_jy_j\,P\{g(X) = y_j\} = E[g(X)].

The key step: summing over $x$ and then grouping by $y$ is exactly how one would have built the pmf of $g(X)$ . LOTUS just skips writing that pmf down.

∎

ExampleLOTUS in action

$X$ uniform on $\{-2,\dots,5\}$ , $Y = X^2$ (Hajek): via the pmf of $Y$ , or directly, $E[Y] = \frac18\sum_{u=-2}^5u^2 = \frac{60}8 = 7.5$ .
Product of two dice: $E[X_1X_2] = \frac1{36}\sum_{i,j}ij = \frac1{36}\big(\sum_ii\big)^2 = \big(\frac72\big)^2 = \frac{49}4$ .
$E[X^2]$ vs $(E[X])^2$ (Ross): with $P\{X = -1\} = .2$ , $P\{X = 0\} = .5$ , $P\{X = 1\} = .3$ , $E[X^2] = .5$ but $(E[X])^2 = .01$ .

Warning $E[g(X)]\ne g(E[X])$ in general

Squaring after averaging is not averaging after squaring. The product example $E[X_1X_2] = E[X_1]E[X_2]$ works only because the dice are independent (conditional-probability-and-independence).

TheoremLinearity of expectation

$E[ag(X) + bh(X) + c] = aE[g(X)] + bE[h(X)] + c, \tag{2.3}$ and for random variables on a common space, $E[ag(X,Y) + bh(X,Y) + c] = aE[g(X,Y)] + bE[h(X,Y)] + c$ . In particular:

$E[aX + b] = aE[X] + b$ ;
$E[X + Y] = E[X] + E[Y]$ , with no independence needed.

ProofLinearity is linearity of a weighted sum

By LOTUS, $\sum_i(ag(u_i) + bh(u_i) + c)p(u_i)$ splits into three sums, and $\sum_ip(u_i) = 1$ handles the constant. For example, $E[X^2 + 3X] = E[X^2] + 3E[X]$ .

∎

TheoremExpectation as a sum over outcomes (Ross Prop. 9.1)

If $\Omega$ is finite or countable, with $p(\omega) = P\{\omega\}$ , $E[X] = \sum_{\omega\in\Omega}X(\omega)\,p(\omega).$

ProofGroup outcomes by the value of

X

Let $S_i = \{\omega : X(\omega) = x_i\}$ . Then

\sum_ix_iP\{X = x_i\} = \sum_ix_i\sum_{\omega\in S_i}p(\omega) = \sum_i \sum_{\omega\in S_i}X(\omega)p(\omega) = \sum_\omega X(\omega)p(\omega),

since the $S_i$ partition $\Omega$ .

∎

CorollaryExpectation of a sum (Ross Cor. 9.2)

$E\big[\sum_{i=1}^nX_i\big] = \sum_{i=1}^nE[X_i]$ , because $\sum_\omega\big(\sum_iX_i(\omega)\big)p(\omega)$ splits into $n$ sums. Ross notes that the result holds without the countability assumption too.

ExampleLinearity without independence (Ross)

Two flips with heads probability $p$ : by the pmf, $E[X] = 0\cdot q^2 + 1\cdot2pq + 2p^2 = 2p$ . By outcomes, $2p^2 + pq + qp = 2p$ .
Sum of $n$ dice: $E = 3.5n$ .
Successes in dependent trials: if trial $i$ succeeds with probability $p_i$ , the expected number of successes is $\sum_ip_i$ , whatever the dependence. For example, it gives the hypergeometric mean (Sampling without replacement: the hypergeometric distribution).

ExampleNewsvendor: how much to stock (Ross)

Each unit sold earns $b$ , and each unsold unit loses $\ell$ . Demand $X$ has pmf $p$ . Stocking $s$ gives

E[P(s)] = sb + (b+\ell)\sum_{i=0}^s(i - s)p(i),\qquad E[P(s+1)] - E[P(s)] = b - (b+\ell)\sum_{i=0}^sp(i).

The increment is positive iff $\sum_{i\le s}p(i) < \frac b{b+\ell}$ . The left side increases in $s$ , so if $s^*$ is the largest such $s$ , the expected profit rises up to $s^*+1$ and falls afterwards. Stock $s^* + 1$ . In words: stock until the demand cdf first reaches the critical ratio $b/(b+\ell)$ .

ExampleExpected utility (Ross)

To compare actions over consequences $C_1..C_n$ : give the worst consequence value 0 and the best value 1. Give each other $C_i$ the probability $u(C_i)$ at which you’d be indifferent between $C_i$ for sure and a lottery “best with probability $u$ , worst otherwise.” An action yielding $C_i$ with probability $p_i$ is then equivalent to getting the best consequence with probability $\sum_ip_iu(C_i)$ . So choose the action with the largest expected utility.

Variance

ExampleSame mean, very different risk (Hajek)

$X = 100$ surely, versus $Y = 100{,}000$ with probability $\frac1{1000}$ and 0 otherwise. Both have mean 100. Would you be equally happy with either? The mean alone can’t tell them apart.

DefinitionVariance and standard deviation

With $\mu_X = E[X]$ ,

\mathrm{Var}(X) = E[(X - \mu_X)^2],\qquad \sigma_X = \sqrt{ \mathrm{Var}(X)}. \tag{2.4}

$X - \mu_X$ is the deviation, the error in predicting $X$ by its mean. It has mean zero. $\sigma_X$ has the same units as $X$ , and the variance has squared units.

NoteWhy the square?

$E[|X - \mu|]$ and $E[(X - \mu)^4]$ also measure spread. The square wins because it is mathematically convenient: expansions, the scaling rule and additivity for independent sums all work cleanly. In mechanics it is the moment of inertia, just as the mean is the center of gravity.

TheoremShift and scale

\mathrm{Var}(X + b) = \mathrm{Var}(X),\qquad \mathrm{Var}(aX) = a^2\mathrm{Var}(X),\qquad \mathrm{Var}(aX + b) = a^2\mathrm{Var}(X).

ProofFrom linearity

$X + b - E[X+b] = X - E[X]$ , so shifting leaves the deviation unchanged. $aX - E[aX] = a(X - E[X])$ , so the squared deviation scales by $a^2$ .

∎

DefinitionStandardized random variable

$\dfrac{X - \mu_X}{\sigma_X}$ has mean 0 and variance 1, and is dimensionless.

FormulaComputational formula

$\mathrm{Var}(X) = E[X^2] - \mu_X^2. \tag{2.5}$ Variance is the second moment minus the square of the first. (The $i$ -th moment is $E[X^i]$ .)

DerivationExpand and use linearity

$E[X^2 - 2\mu X + \mu^2] = E[X^2] - 2\mu E[X] + \mu^2 = E[X^2] - \mu^2$ . Use (2.4) for meaning and scaling, and (2.5) for computation.

ExampleVariances

Fair die: $E[X^2] = \frac{91}6$ , so $\mathrm{Var}(X) = \frac{91}6 - \frac{49}4 = \frac{35}{12}$ .
The payments above: $\mathrm{Var}(X) = 0$ . For $Y$ , $E[Y^2] = 10^{10}/10^3 = 10^7$ , so $\mathrm{Var}(Y) = 10^7 - 10^4\approx10^7$ and $\sigma_Y\approx3160$ . (This computation is mine.)
$W\equiv0$ , $Y = \pm1$ and $Z = \pm100$ , each sign with probability $\frac12$ , all have mean 0. Their variances are 0, 1 and $10^4$ .

Corollary $E[X^2]\ge(E[X])^2$

Variance is a sum of nonnegative terms, so $\mathrm{Var}(X)\ge0$ . Equality holds iff $X$ is constant.

ExampleThe friendship paradox (Ross)

In a friendship graph on $n$ people, person $i$ has $f(i)$ friends, and $f = \sum_if(i)$ .

A random person $X$ (uniform) has on average $E[f(X)] = f/n$ friends.
A random friend $Y$ : everyone writes each friend’s name on a separate sheet, and we draw a sheet. Then $P(Y = i) = f(i)/f$ and $E[f(Y)] = \frac{\sum_if(i)^2}f = \frac{E[f(X)^2]}{E[f(X)]}\ge E[f(X)].$

On average, your friends have at least as many friends as you do. Equality holds only if everyone has the same number of friends.

IntuitionSize bias again

$Y$ is chosen with probability proportional to popularity, exactly as a random student lands on a big bus. Any average taken over a reweighted population is biased toward whatever drove the weights. (This matters for network sampling; compare cascading-behavior-in-networks.)

ExampleShared birthdays make more sharing likely (Ross)

Birthdays fall on day $r$ with probability $p_r$ . Let $A_{i,j}$ = ” $i$ and $j$ share a birthday.” Then $P(A_{1,3}) = \sum_rp_r^2$ and $P(A_{1,3}\mid A_{1,2}) = \sum_rp_r^3/\sum_rp_r^2$ . So $P(A_{1,3}\mid A_{1,2})\ge P(A_{1,3})$ iff $\sum p_r^3\ge(\sum p_r^2)^2$ . This is $E[X^2]\ge(E[X])^2$ for $X = p_r$ with probability $p_r$ . Intuition: knowing 1 and 2 match makes it likelier that their shared day is a popular one.

The Bernoulli trial family

The workhorse model of discrete probability is a sequence of independent trials, each a success with probability $p$ . Coin flips, defective screws, voters, detected bits and working links are all instances. Different questions about the same sequence produce different named distributions.

Question about the trials	Distribution	Mean	Variance
did trial 1 succeed?	Bernoulli $(p)$	$p$	$p(1-p)$
how many successes in $n$ trials?	binomial $(n,p)$	$np$	$np(1-p)$
how many trials until the first success?	geometric $(p)$	$1/p$	$(1-p)/p^2$
how many trials until the $r$ -th success?	negative binomial $(r,p)$	$r/p$	$r(1-p)/p^2$

Reliability reuses the same model with the labels swapped. Each component fails independently with a small probability. The system’s structure (series, parallel, bridge, parity checks, backups) decides which combinations of failures matter.

Bernoulli distribution

DefinitionBernoulli $(p)$

$X$ is Bernoulli with parameter $p\in[0,1]$ if $P\{X = 1\} = p,\qquad P\{X = 0\} = 1 - p. \tag{6.1}$ It is the indicator of a single “success.” Named after Jacques (James, Jakob) Bernoulli.

FormulaMean and variance

$E[X] = p,\qquad \mathrm{Var}(X) = p(1-p).$

Derivation

X^2 = X

A 0/1 variable equals its square, so $E[X^2] = E[X] = p$ . Then $\mathrm{Var}(X) = p - p^2$ .

RemarkMaximum uncertainty at a fair coin

$p(1-p)$ is symmetric about $\tfrac12$ , where it reaches its maximum $\tfrac14$ . The bound $p(1-p)\le\tfrac14$ is what makes polling error bars computable without knowing $p$ .

Binomial distribution

DefinitionBinomial $(n,p)$

$X$ is the number of successes in $n$ independent Bernoulli $(p)$ trials: $p_X(k) = \binom nkp^k(1-p)^{n-k},\qquad k = 0,1,\dots,n. \tag{6.2}$ Bernoulli $(p)$ is binomial $(1,p)$ .

DerivationWhy the pmf has this form, and why it sums to one

Each arrangement: a particular sequence with $k$ successes, such as 11010101 with $n = 8$ , $k = 5$ , has probability $p^k(1-p)^{n-k}$ by independence.

How many arrangements: choose which $k$ of the $n$ trials succeed, which gives $\binom nk$ disjoint sequences. For example, $n = 4$ , $k = 2$ has 6: ssff, sfsf, sffs, fssf, fsfs, ffss.

Normalization: by the binomial theorem, $\sum_k\binom nkp^k(1-p)^{n-k} = (p + (1-p))^n = 1$ . Hajek substitutes $x = p/(1-p)$ into the Maclaurin series of $(1+x)^n$ to get the same result.

Mean and variance

TheoremMoments of the binomial

$E[X] = np,\qquad \mathrm{Var}(X) = np(1-p).$

ProofThree derivations

1. Indicators and linearity (Ross §4.9). Write $X = \sum_{i=1}^nX_i$ with $X_i$ the indicator that trial $i$ succeeds. Then $E[X] = \sum_iE[X_i] = np$ . This needs no independence. For the variance, expand $E[X^2] = \sum_iE[X_i^2] + \sum_{i\ne j}E[X_iX_j]$ with $E[X_i^2] = p_i$ and $E[X_iX_j] = p_{i,j} = P(\text{trials }i,j\text{ both succeed})$ :

\mathrm{Var}(X) = \sum_ip_i + \sum_i\sum_{j\ne i}p_{i,j} - \Big(\sum_ip_i \Big)^2. \tag{9.1}

Independent trials with $p_i = p$ have $p_{i,j} = p^2$ , which gives $np + n(n-1)p^2 - n^2p^2 = np(1-p)$ .

2. Moment recursion (Ross). Using $i\binom ni = n\binom{n-1}{i-1}$ and shifting the index,

E[X^k] = np\,E\big[(Y + 1)^{k-1}\big],\qquad Y\sim\text{binomial}(n-1, p).

$k = 1$ gives $np$ . $k = 2$ gives $np[(n-1)p + 1]$ , so $\mathrm{Var}(X) = np[(n-1)p + 1] - (np)^2 = np(1-p)$ .

3. Directly (Hajek, eq. 2.7): the same index shift inside $\sum_kk\binom nkp^k(1-p)^{n-k}$ .

∎

ImportantFormula (9.1) is more general than the binomial

(9.1) holds for any sum of indicators, dependent or not. Only the pairwise probabilities $p_{i,j}$ are needed. For example, sampling without replacement has $p_i = m/N$ and $p_{i,j} = \frac mN\frac{m-1}{N-1}$ .

Shape: mode, median, recursion

PropositionUnimodality (Ross Prop. 6.1)

For $0 < p < 1$ , $p(k)$ increases up to $k^* = \lfloor(n+1)p\rfloor$ and decreases afterwards. If $(n+1)p$ is an integer, $p(k^*-1) = p(k^*)$ tie.

ProofRatio of consecutive terms

$\frac{p(k)}{p(k-1)} = \frac{(n-k+1)p}{k(1-p)}\ge1\iff k\le(n+1)p.$

∎

ExampleWhere the peak is

$n = 24$ , $p = 1/3$ : $(n+1)p = 8.33$ , so the mode is $k^* = 8$ , close to $np = 8$ . $n = 10$ , $p = \tfrac12$ : the mode is 5.

NoteThe median is also near the mean

Every median $m$ satisfies $|m - np|\le\max\{p,1-p\}$ (Kaas–Buhrman, cited without proof).

FormulaRecursion for computing the pmf and cdf

$P\{X = k+1\} = \frac p{1-p}\cdot\frac{n-k}{k+1}\,P\{X = k\}. \tag{6.3}$ Start from $P\{X = 0\} = (1-p)^n$ and accumulate to get $P\{X\le i\}$ . For example, $n = 6$ , $p = .4$ :

$k$	0	1	2	3	4	5	6
$P\{X = k\}$	.0467	.1866	.3110	.2765	.1382	.0369	.0041

ExampleStandardizing a binomial (Hajek)

Binomial $(4,\tfrac12)$ has mean 2 and variance 1. So the standardized version is simply $X - 2$ , a shift with no rescaling. A fair die needs both a shift (3.5) and a rescale ( $\sigma\approx1.708$ ).

Applications

ExampleCounting successes (Ross)

Five fair coins: $P\{X = k\} = \binom5k/32$ , i.e. $\frac1{32},\frac5{32},\frac{10}{32},\frac{10}{32},\frac5{32}, \frac1{32}$ .
Money-back screws: each screw is defective with probability .01, and a pack of 10 is replaced if more than one is defective: $1 - .99^{10} - 10(.01)(.99)^9\approx.004$ .
Mendel: two hybrid parents have a child showing the dominant trait with probability $\tfrac34$ . So $P(3\text{ of }4) = \binom43(\tfrac34)^3\tfrac14 = \tfrac{27}{64}$ .

ExampleChuck-a-luck is unfair (Ross)

Bet on a number, roll three dice, win $i$ units if it appears $i$ times and lose 1 otherwise. The count is binomial $(3,\tfrac16)$ :

E[\text{winnings}] = \frac{-125 + 1\cdot75 + 2\cdot15 + 3\cdot1}{216} = -\frac{17}{216}\approx-0.079.

ExampleA jury needs a model of guilt (Ross)

8 of 12 votes convict, and each juror is independently right with probability $\theta$ . An innocent defendant is correctly acquitted iff at least 5 jurors vote correctly. A guilty one is correctly convicted iff at least 8 do. With prior guilt probability $\alpha$ :

P(\text{correct}) = \alpha\sum_{i=8}^{12}\binom{12}i\theta^i(1-\theta)^{ 12-i} + (1-\alpha)\sum_{i=5}^{12}\binom{12}i\theta^i(1-\theta)^{12-i}.

This is the law of total probability over the hidden truth.

ExampleMore components help only if each is better than a coin (Ross)

A system works if at least half its components work (independently, each with probability $p$ ). A $(2k+1)$ -component system beats a $(2k-1)$ -component one iff $p > \tfrac12$ . For $k = 2$ the condition is $3(p-1)^2(2p-1) > 0$ .

ProofCondition on the first

2k-1

components

Let $X$ count working components among the first $2k-1$ . The larger system works if $X\ge k+1$ ; if $X = k$ and at least one of the 2 extras works; or if $X = k-1$ and both extras work. The smaller system works iff $X\ge k$ . So

P_{2k+1} - P_{2k-1} = P\{X = k-1\}p^2 - P\{X = k\}(1-p)^2 = \binom{2k-1}kp^k(1-p)^k(2p - 1),

using $\binom{2k-1}{k-1} = \binom{2k-1}k$ .

∎

ExampleVoters in big states have more power (Ross)

A voter in a state of $n = 2k+1$ voters is decisive iff the other $2k$ split evenly. In a close election each votes independently 50/50, and by Stirling $\binom{2k}k2^{-2k}\sim\frac1{\sqrt{\pi k}}.$ The state carries about $nc$ electoral votes, so

\text{average power}\approx nc\sqrt{\frac2{\pi n}} = c\sqrt{\frac{2n}\pi} \;\propto\;\sqrt n.

IntuitionWhy $\sqrt n$

The chance of being pivotal shrinks like $1/\sqrt n$ (a binomial’s spread is $\sqrt n$ ), but the prize grows like $n$ . The prize wins.

ExampleLength of a best-of-seven series (Hajek)

Games are independent and $A$ wins each with probability $p$ . The series ends at game $n$ with $A$ winning iff $A$ wins 3 of the first $n-1$ and then game $n$ :

p_Y(n) = \binom{n-1}3\big[p^4(1-p)^{n-4} + (1-p)^4p^{n-4}\big],\qquad 4\le n\le7.

With $p = \tfrac12$ : $(p_Y(4),\dots,p_Y(7)) = (\tfrac18,\tfrac14, \tfrac5{16},\tfrac5{16})$ .

Geometric distribution

DefinitionGeometric $(p)$

$L$ is the number of trials up to and including the first success, with $0 < p\le1$ : $p_L(k) = (1-p)^{k-1}p,\qquad k\ge1. \tag{8.1}$

Component	Detail
Support	$\{1,2,3,\dots\}$ : the count includes the success itself
Tail	$P\{L > k\} = (1-p)^k$ (2.8): the first $k$ trials all fail
Normalization	geometric series; a success occurs with probability 1

WarningTwo conventions

Some texts count failures before the first success (support $\{0,1,\dots\}$ , mean $(1-p)/p$ ). Both sources here count trials.

ExampleDrawing with replacement until black (Ross)

$M$ black and $N$ white balls, so $p = \frac M{M+N}$ :

P\{X = n\} = \frac{MN^{n-1}}{(M+N)^n},\qquad P\{X\ge k\} = \Big(\frac N {M+N}\Big)^{k-1}.

TheoremMean and variance

E[L] = \frac1p,\qquad E[L^2] = \frac{2-p}{p^2},\qquad \mathrm{Var}(L) = \frac{1-p}{p^2},\qquad \sigma_L = \frac{\sqrt{1-p}}p.

ProofFirst-step analysis (Hajek)

Condition on trial 1. With probability $p$ , $L = 1$ . Otherwise $L = 1 + \tilde L$ , where $\tilde L$ (the remaining wait) has the same distribution as $L$ , because the trials start afresh. Conditional expectations obey total probability, $E[X] = \sum_jE[X\mid E_j]P(E_j)$ , so $E[L] = p\cdot1 + (1-p)(1 + E[L])\;\Rightarrow\;E[L] = \frac1p.$

Second moment. $E[L^2] = p + (1-p)E[(1+L)^2] = p + (1-p)(1 + 2E[L] + E[L^2])$ . Solving gives $E[L^2] = (2-p)/p^2$ , and subtracting $1/p^2$ gives the variance.

Ross gets the same result by splitting $i = (i-1) + 1$ inside the sums. That’s the same argument written algebraically. His form $E[X^2] = (q+1)/p^2$ agrees because $q + 1 = 2 - p$ .

∎

ImportantRare successes: mean and spread are both large

If $p$ is small, $E[L] = 1/p$ is huge and $\sigma_L$ is nearly as big, smaller only by the factor $\sqrt{1-p}$ . For $p = .01$ , the mean is 100 and $\sigma\approx99.5$ . Waits for rare events are both long and very unpredictable.

ExampleCoupon collector’s mean (Hajek)

Roll a die until all six faces appear. Split the total $R$ into $R_1 + \cdots + R_6$ , where $R_i$ is the wait for the $i$ -th new face. Each $R_i$ is geometric with $p = \frac{6-i+1}6$ . By linearity, $E[R] = 6\Big(1 + \tfrac12 + \cdots + \tfrac16\Big) = 14.7.$ With $n$ types, $E = nH_n\approx n\ln n$ . (Compare the tail bound $P\{T > n\}\le re^{-n/r}$ in Random variables and probability mass functions above.)

Memorylessness

TheoremMemoryless property (discrete time)

For integers $n, k\ge0$ : $P(L > k + n\mid L > n) = P\{L > k\}.$

ProofRatio of tails

$\{L > k+n\}\subseteq\{L > n\}$ , so the conditional probability is $\frac{(1-p)^{k+n}}{(1-p)^n} = (1-p)^k.$

∎

IntuitionWaiting doesn’t make it more likely soon

An observer who has already waited $n$ steps faces exactly the same future wait as one just starting. Past failures carry no information because the trials are independent. This is the discrete version of “constant failure rate” (Failure rate functions).

Bernoulli process and the negative binomial distribution

DefinitionBernoulli process

An infinite sequence $X_1, X_2, \dots$ of independent Bernoulli $(p)$ random variables. For each outcome $\omega$ , the function $k\mapsto X_k(\omega)$ is the sample path. For example, $P\{X_5 = 1, X_6 = 1, X_7 = 0, X_{12} = 1\} = p^3(1-p)$ .

TheoremFour equivalent descriptions

Each of these determines the others:

Description	Definition	Distribution
trials $(X_k)$	outcome of trial $k$	i.i.d. Bernoulli $(p)$
gaps $(L_j)$	extra trials from the $(j-1)$ -th to the $j$ -th success	i.i.d. geometric $(p)$
counting sequence $(C_k)$	$C_k = X_1 + \cdots + X_k$ , $C_0 = 0$	$C_l - C_k\sim$ binomial $(l-k,p)$ , with independent increments over disjoint intervals
arrival times $(S_r)$	$S_r = L_1 + \cdots + L_r$ , $S_0 = 0$	negative binomial $(r,p)$

The conversions are $X_k = C_k - C_{k-1}$ and $L_j = S_j - S_{j-1}$ .

graph LR
  X["Trials X1 X2 X3 ... i.i.d. Bernoulli"] -->|"partial sums"| C["Counts C_k binomial"]
  X -->|"gaps between ones"| L["Gaps L_j i.i.d. geometric"]
  L -->|"partial sums"| S["Arrival times S_r negative binomial"]
  C -->|"first time count reaches r"| S

IntuitionCounting vs waiting

“At least $r$ successes in $n$ trials” and “the $r$ -th success arrives by trial $n$ ” are the same event: $\{C_n\ge r\} = \{S_r\le n\}.$ So every binomial statement has a negative binomial twin.

Negative binomial distribution

DefinitionNegative binomial $(r,p)$

$S_r$ , the trial on which the $r$ -th success occurs, has pmf $P\{S_r = n\} = \binom{n-1}{r-1}p^r(1-p)^{n-r},\qquad n\ge r. \tag{8.2}$ $r = 1$ gives the geometric distribution.

DerivationThe pmf and the name

pmf: $S_r = n$ iff the first $n-1$ trials contain exactly $r-1$ successes (probability $\binom{n-1}{r-1}p^{r-1}(1-p)^{n-r}$ ) and trial $n$ succeeds ( $p$ ). The two conditions concern disjoint trials, so they are independent.

Normalization: use the negative binomial series $(1-x)^{-r} = \sum_{k\ge0}\binom{k+r-1}{r-1}x^k$ with $x = 1-p$ , $k = n-r$ : $\sum_{n\ge r}\binom{n-1}{r-1}p^r(1-p)^{n-r} = p^r\cdot p^{-r} = 1.$ This parallels the binomial pmf’s use of $(1+x)^n$ , hence the name.

Probabilistic check (Ross): $S_r = L_1 + \cdots + L_r$ is a sum of finite geometric waits, so it is finite with probability 1.

TheoremMean and variance

$E[S_r] = \frac rp,\qquad \mathrm{Var}(S_r) = \frac{r(1-p)}{p^2}.$

ProofSum of geometrics, or moment recursion

Mean: linearity over $L_1..L_r$ , each with mean $1/p$ .

Variance (Hajek): $\mathrm{Var}(S_r) = r\,\mathrm{Var}(L_1)$ , because variances of independent summands add. That result is proved later (Hajek Ex. 4.8.1).

Moment recursion (Ross): using $n\binom{n-1}{r-1} = r\binom nr$ , $E[S_r^k] = \frac rpE\big[(Y - 1)^{k-1}\big],\qquad Y\sim\text{NB}(r+1,p).$ $k = 1$ gives $r/p$ . $k = 2$ gives $\frac rp\big(\frac{r+1}p - 1\big)$ , and subtracting $(r/p)^2$ gives $r(1-p)/p^2$ .

∎

ExampleFour ones on a die (Ross)

$r = 4$ , $p = \tfrac16$ : $E = 24$ rolls, $\mathrm{Var} = \frac{4\cdot5/6} {1/36} = 120$ .

ExampleProblem of the points, a third way (Ross)

$r$ successes come before $s$ failures iff the $r$ -th success arrives by trial $r + s - 1$ : $P = \sum_{n=r}^{r+s-1}\binom{n-1}{r-1}p^r(1-p)^{n-r}.$ Compare the Pascal (recursion) and Fermat (binomial) solutions in conditional-probability-and-independence.

ExampleBanach’s matchboxes (Ross)

Two boxes of $N$ matches, each use equally likely from either box. When the smoker first finds a box empty, the other holds $k$ matches with probability

2\binom{2N-k}N\Big(\frac12\Big)^{2N-k+1} = \binom{2N-k}N\Big(\frac12\Big)^{ 2N-k},\qquad k = 0..N.

Why: “the right box is found empty with $k$ left in the left box” means the $(N+1)$ -th choice of the right box happens on trial $2N - k + 1$ . That is a negative binomial with $r = N+1$ , $p = \tfrac12$ . Double it for the symmetric case.

ExampleWaiting for successes or failures (Ross)

Let $X$ be the wait for $r$ successes and $Y$ the wait for $s$ failures. $Y$ is NB $(s, 1-p)$ . For the first of the two, $V = \min(X,Y)$ satisfies $V < r+s$ , and at time $n$ only one of the two can have just completed:

P(V = n) = \binom{n-1}{r-1}p^r(1-p)^{n-r} + \binom{n-1}{s-1}(1-p)^sp^{n-s}, \qquad n < r+s.

For the last of the two, $Z = \max(X,Y)\ge r+s$ , and the same two-term formula holds for $n\ge r+s$ , because the other event must already have happened.

Sampling without replacement: the hypergeometric distribution

DefinitionHypergeometric $(n, N, m)$

Draw $n$ balls without replacement from an urn of $N$ , of which $m$ are white. The number $X$ of white balls drawn has

P\{X = i\} = \frac{\binom mi\binom{N-m}{n-i}}{\binom Nn},\qquad i = 0,1,\dots,n. \tag{8.4}

The pmf is 0 unless $n - (N - m)\le i\le\min(n,m)$ , which the convention $\binom rk = 0$ for $k < 0$ or $k > r$ handles automatically.

TheoremMean and variance

With $p = m/N$ :

E[X] = np,\qquad \mathrm{Var}(X) = np(1-p)\Big(1 - \frac{n-1}{N-1}\Big) = \frac{N-n}{N-1}\,np(1-p).

ProofIndicators with dependent trials (Ross Ex. 9d–9e)

Let $X_i$ indicate that the $i$ -th ball drawn is white. Each ball drawn is equally likely to be any of the $N$ , so $p_i = m/N = p$ , and $E[X] = np$ by linearity, although the draws are dependent. For $i\ne j$ , $p_{i,j} = P(X_i = 1)P(X_j = 1\mid X_i = 1) = \frac mN\cdot\frac{m-1}{N-1}.$ Formula (9.1) (Binomial distribution) gives $\mathrm{Var}(X) = np + n(n-1)\frac mN\frac{m-1}{N-1} - (np)^2$ . Substitute $\frac{m-1}{N-1} = p - \frac{1-p}{N-1}$ and simplify.

Ross also derives both moments from $E[X^k] = \frac{nm}NE[(Y+1)^{k-1}]$ , where $Y$ is hypergeometric $(n-1, N-1, m-1)$ .

∎

IntuitionThe finite-population correction

The mean is exactly the with-replacement (binomial) mean. The variance is smaller by the factor $\frac{N-n}{N-1}$ : drawing without replacement exhausts the urn and removes some randomness. Sampling the whole urn ( $n = N$ ) leaves no randomness at all.

TheoremBinomial approximation

If $m$ and $N$ are large compared with $n$ and $i$ , then $P\{X = i\}\approx\binom nip^i(1-p)^{n-i},\qquad p = \frac mN.$

ProofEach draw barely changes the urn

Writing out the factorials,

P\{X = i\} = \binom ni\frac mN\frac{m-1}{N-1}\cdots\frac{m-i+1}{N-i+1}\cdot \frac{N-m}{N-i}\cdots\frac{N-m-(n-i-1)}{N-i-(n-i-1)}.

When $m, N\gg n$ , each of the $i$ “white” factors is about $p$ and each of the $n - i$ “black” factors is about $1-p$ .

∎

ExampleCapture–recapture: estimating a population (Ross)

Catch, mark and release $m$ animals. Later catch $n$ , of which $i$ are marked. With $N$ animals in total, the likelihood of seeing $i$ marked is $P_i(N) = \binom mi\binom{N-m}{n-i}/\binom Nn$ . Then

\frac{P_i(N)}{P_i(N-1)} = \frac{(N-m)(N-n)}{N(N-m-n+i)}\ge1\iff N\le \frac{mn}i,

so the maximum likelihood estimate is $\hat N = \lfloor mn/i\rfloor$ . For $m = 50$ , $n = 40$ , $i = 4$ : $\hat N = 500$ . This matches the proportion argument $m/N\approx i/n$ . (See estimation-and-hypothesis-testing.)

ExampleAcceptance sampling (Ross)

Lots of 10 are accepted only if 3 randomly inspected items are all good. 30% of lots have 4 defectives and 70% have 1. By total probability,

P(\text{accept}) = \frac{\binom63}{\binom{10}3}(.3) + \frac{\binom93} {\binom{10}3}(.7) = \frac{20}{120}(.3) + \frac{84}{120}(.7) = .54,

so 46% of lots are rejected.

The zeta (Zipf) distribution

DefinitionZeta distribution with parameter $\alpha > 0$

P\{X = k\} = \frac C{k^{\alpha+1}},\qquad k = 1,2,\dots,\qquad C = \Big[\sum_{k\ge1}\Big(\frac1k\Big)^{\alpha+1}\Big]^{-1}.

The name comes from the Riemann zeta function $\zeta(s) = 1 + 2^{-s} + 3^{-s} + \cdots$ , so $C = 1/\zeta(\alpha+1)$ .

RemarkA discrete power law

Pareto used it for the distribution of family incomes, and Zipf applied it to many other areas. The probabilities decay like a power of $k$ , not geometrically, so very large values are far likelier than under a geometric or Poisson model. The continuous counterpart is the Pareto distribution (continuous-random-variables-and-distributions).

Union bound

TheoremUnion bound

P(A\cup B)\le P(A) + P(B),\qquad P(A_1\cup\cdots\cup A_m)\le\sum_{i=1}^m P(A_i). \tag{2.18}

This is Boole’s inequality, the first Bonferroni bound in probability-foundations. The $m$ -event version follows by induction.

ProofThe gap is the overlap

$P(A) + P(B) - P(A\cup B) = P(AB)\ge0$ .

∎

ImportantWhen the bound is tight

Equality holds for mutually exclusive events.
Never off by more than a factor of 2 for two events, since $P(AB)\le\min\{P(A),P(B)\}$ .
Nearly exact for rare independent events: $P(A) = P(B) = .001$ gives $P(A\cup B) = .002 - .000001$ , versus the bound .002.
Useless for likely events: the sum can exceed 1.

Reliability deals almost entirely with rare, independent failures, which is exactly the regime where the bound is sharp.

Network outage probability

Definition $s$ – $t$ network and outage

Nodes include a source $s$ and a terminal $t$ , joined by links. Link $i$ fails (event $F_i$ ) with probability $p_i$ , independently, and $q_i = 1 - p_i$ . An $s$ – $t$ path is a set of links connecting $s$ to $t$ . Outage $F$ occurs if every $s$ – $t$ path has at least one failed link.

Component	Detail
Input	the network topology and failure probabilities $p_1,\dots,p_m$
Output	$P(F)$ , a number in $[0,1]$
Assumed	independent link failures
Not modeled	capacities (see Distribution of the capacity of a flow network) and time

graph LR
  subgraph NetA["A: parallel"]
    sA["s"] ---|"1"| tA["t"]
    sA ---|"2"| tA
  end
  subgraph NetB["B: series"]
    sB["s"] ---|"1"| mB["m"]
    mB ---|"2"| tB["t"]
  end

graph LR
  subgraph NetE["E: bridge; drop link 5 to get C, merge a and b to get D"]
    s["s"] ---|"1"| a["a"]
    a ---|"2"| t["t"]
    s ---|"3"| b["b"]
    b ---|"4"| t
    a ---|"5"| b
  end

Network C is the two series paths 1–2 and 3–4 in parallel (E without link 5). Network D is two stages in series: stage 1 is links 1 and 3 in parallel, stage 2 is links 2 and 4 in parallel (E with link 5 never failing).

TheoremExact outage probabilities

Network	Outage event	$P(F)$	$p_i = .001$
A (parallel)	$F_1F_2$	$p_1p_2$	$10^{-6}$
B (series)	$F_1\cup F_2$	$p_1 + p_2 - p_1p_2$	$.001999$
C (parallel of series)	$(F_1\cup F_2)(F_3\cup F_4)$	$(p_1+p_2-p_1p_2)(p_3+p_4-p_3p_4)$	$\approx4\times10^{-6}$
D (series of parallel)	$F_1F_3\cup F_2F_4$	$p_1p_3 + p_2p_4 - p_1p_2p_3p_4$	$\approx2\times10^{-6}$
E (bridge)	see below	$P_D + p_1q_2q_3p_4p_5 + q_1p_2p_3q_4p_5$	$\approx2.002\times10^{-6}$

ProofSeries, parallel, and the bridge

Parallel: outage needs every branch to fail. The branches use disjoint links, so the branch failures are independent and multiply.

Series: outage needs some link to fail, which is a union (inclusion–exclusion).

C: each branch is a series (union), and the two branches combine in parallel (product).

D: each stage is a parallel pair (product), and the stages combine in series (union of two independent events).

E by conditioning on link 5 (total probability): $P(F_E) = p_5P(F_C) + (1-p_5)P(F_D).$ If link 5 fails, delete it and get C. If link 5 works, it merges $a$ and $b$ and gives D.

E by comparison with D: any D-outage is an E-outage. E fails but D doesn’t only when exactly links $\{1,4,5\}$ or exactly $\{2,3,5\}$ fail. These are the two diagonal cuts.

∎

ExampleExhaustive state listing, network C (Hajek Table 2.3)

Write the state as 4 bits, with bit $i$ = 1 if link $i$ fails. C fails iff (bit 1 or bit 2) and (bit 3 or bit 4). Of the 16 states, 9 fail: 0101, 0110, 0111, 1001, 1010, 1011, 1101, 1110, 1111. Each state’s probability is a product of $p$ ‘s and $q$ ‘s, e.g. state 0110 has probability $q_1p_2p_3q_4$ , and $P(F)$ is their sum. This is reliable for small networks and useless for large ones. Hajek notes that exact network reliability is computationally intractable in general.

TheoremUnion bounds via cut sets

Write $F$ as a union of “all links in a cut fail” events and bound:

Network	Cuts	Union bound	$p_i = .001$
B	$\{1\},\{2\}$	$p_1 + p_2$	$.002$
C	$\{1,3\},\{1,4\},\{2,3\},\{2,4\}$	$(p_1+p_2)(p_3+p_4)$	$4\times10^{-6}$
D	$\{1,3\},\{2,4\}$	$p_1p_3 + p_2p_4$	$2\times10^{-6}$
E	$\{1,3\},\{2,4\},\{1,4,5\},\{2,3,5\}$	$p_1p_3 + p_2p_4 + p_1p_4p_5 + p_2p_3p_5$	$2.002\times10^{-6}$

In every case the bound nearly equals the exact value.

IntuitionRare failures are dominated by the smallest cuts

With all $p_i = p$ small, a cut of size $c$ contributes about $p^c$ . So $P(F)\approx(\text{number of minimum-size cuts})\times p^{c_{\min}}$ .

Series adds: B’s single-link cuts give about $2p$ .
Parallel multiplies: A’s two-link cut gives $p^2$ .
C has 4 two-link cuts ( $4p^2$ ), D only 2 ( $2p^2$ ), so D is twice as reliable as C with the same four links.
E’s extra link 5 adds only three-link cuts ( $\sim p^3$ ), so it barely helps over D.

Distribution of the capacity of a flow network

DefinitionRandom flow network capacity

Each link carries flow (in either direction, splittable across paths) up to its capacity. It carries nothing if it fails. The network capacity is the maximum $s$ – $t$ flow rate. Because links fail at random, the capacity is a discrete random variable.

Component	Detail
Signature	capacity: (state of the links) → max-flow value
Domain	the $2^m$ up/down states, with probabilities $\prod p_iq_j$
Codomain	a finite set of flow values
pmf	add up the probabilities of all states with each capacity

ExampleNetwork F: two parallel links, capacities 10 and 20

p_X(0) = p_1p_2,\quad p_X(10) = q_1p_2,\quad p_X(20) = p_1q_2,\quad p_X(30) = q_1q_2.

graph LR
  s["s"] ---|"link 1, cap 10"| a["a"]
  a ---|"link 2, cap 20"| t["t"]
  s ---|"link 3, cap 20"| b["b"]
  b ---|"link 4, cap 10"| t
  b ---|"link 5, cap 10"| a

ExampleNetwork G: a capacitated bridge

Capacity 30 needs every link: send 10 along 1, 20 along 3, then 10 on along 4 and 10 up link 5, so that 20 leaves through link 2. Any failure cuts either the 30 leaving $s$ , the 30 entering $t$ , or (link 5) the crossover. So $p_Y(30) = q_1q_2q_3q_4q_5$ .

Capacity 0 is exactly outage of the bridge, so $p_Y(0) = P(F_E)$ .

Capacity 20 needs links 2 and 3 (the only 20-capacity exits from $s$ and entries to $t$ ). Then either link 5 is down and links 1 and 4 both work, or link 5 is up and exactly one of links 1, 4 is down: $p_Y(20) = q_2q_3\big[p_5q_1q_4 + q_5(p_1q_4 + q_1p_4)\big].$

Capacity 10: $p_Y(10) = 1 - p_Y(0) - p_Y(20) - p_Y(30)$ .

WarningIf links 1 and 4 both fail with 5 up, the capacity is 10, not 20

The only remaining route is $s\to3\to5\to2\to t$ , limited to 10 by link 5. Hajek writes the link-5-up term as $q_5(p_1 + p_4 - p_1p_4)$ (“at least one fails”), which wrongly counts this state as capacity 20. The expression above uses “exactly one.”

ExampleState enumeration for G (Hajek Table 2.4, first rows)

State (bit $i$ = link $i$ failed)	Capacity	Probability
00000	30	$q_1q_2q_3q_4q_5$
00001	20	$q_1q_2q_3q_4p_5$
00010	20	$q_1q_2q_3p_4q_5$
00011	10	$q_1q_2q_3p_4p_5$
00100	10	$q_1q_2p_3q_4q_5$
00101–00111	10	…
11111	0	$p_1p_2p_3p_4p_5$

Analysis of an array code

DefinitionTwo-dimensional parity code

A $7\times7$ block of 49 data bits gets an extra parity column, parity row and overall parity bit, making an $8\times8$ array in which every row and column has even parity. An error pattern marks flipped bits. The reader checks all 16 parities, and any odd parity means the error is detected.

TheoremWhich error patterns go undetected

Every pattern of 1, 2 or 3 errors is detected.
An undetected pattern needs every row and column to have even parity. So its total weight is even, and odd weights are always detected.
A 4-error pattern is undetected iff it sits on the four corners of a rectangle (two rows × two columns). There are $\binom82^2 = 28^2 = 784$ such patterns.

ProofTwo errors are always caught

Two flipped bits lie in different rows or different columns (or both). Different rows means those two rows have odd parity. Different columns means those two columns do.

∎

TheoremUndetected-error probability ( $p = 10^{-3}$ per bit, independent)

Crude: the number of errors $Y$ is binomial $(64,p)$ . Undetected errors need $Y\ge4$ , and by the union bound over 4-subsets, $P\{Y\ge4\}\le\binom{64}4p^4 = 635{,}376\,p^4\approx0.64\times10^{-6}.$ (Compare the exact $P\{Y = 4\} = \binom{64}4p^4(1-p)^{60}$ .)

Sharp: only the 784 rectangle patterns can fail at weight 4, weight 5 is impossible, and weight $\ge6$ is union-bounded:

P(\text{undetected})\le784p^4 + \binom{64}6p^6 = (784 + 74.97)\times 10^{-12}\approx0.859\times10^{-9}.

IntuitionStructure beats counting

The crude bound treats all $\binom{64}4$ four-bit patterns as dangerous. Only 784 of them are. Knowing which failure patterns actually matter improves the bound by a factor of about 740, the same “minimal cuts” lesson as the networks.

Reliability of a single backup

ExampleTwo machines backing each other up (Hajek)

Each machine, when up (or just repaired, or on day 1), goes down on a given day with probability .001, independently. It then stays down for 5 days of repair. How long until both are down on the same day? Answer: roughly 274 years.

DerivationTwo nested geometric waits

Step 1: Wait for the first failure. With both machines up, some machine fails on a given day with probability about $.002$ . So the wait is roughly geometric $(.002)$ , with mean about 500 days.

Step 2: Does the backup fail during the repair? The other machine fails within the 5-day repair with probability about $5\times.001 = \frac1{200}$ (union bound over the 5 days).

Step 3: Count repair cycles. Each cycle independently ends in a double outage with probability about $\frac1{200}$ , so the number of cycles is roughly geometric with mean 200.

Step 4: Multiply. $500\times200 = 100{,}000$ days, or about 274 years. Hajek poses bracketing this between 200 and 400 years as a challenge. The approximations in steps 1–2 are each accurate to well under a factor of 2.

ImportantRedundancy turns $p$ into roughly $p\times(\text{repair time})\times p$

A single machine fails every 1000 days on average. The pair fails about 100 times less often, because a double outage needs a second rare event inside a short window. Shortening repairs improves reliability proportionally.

Failure rate functions

NoteSource coverage

Neither Chapter 2 source covers failure rates. This section gives the discrete version, which follows directly from the geometric results above. The continuous version, with proofs, is in continuous-random-variables-and-distributions.

DefinitionDiscrete failure rate (hazard)

For a lifetime $L$ on $\{1,2,\dots\}$ , $h(k) = P(L = k\mid L\ge k) = \frac{p_L(k)}{P\{L\ge k\}}.$ It is the chance of failing now, given survival so far.

Component	Detail
Signature	$h : \{1,2,\dots\}\to[0,1]$
Domain	an age $k$
Codomain	the conditional failure probability at that age
Not the same as	$p_L(k)$ , which is unconditional and so small for large $k$ even when the item is fragile at that age

TheoremHazard determines the lifetime

$P\{L > k\} = \prod_{j=1}^k\big(1 - h(j)\big).$

ProofChain rule

$\{L > k\}$ means surviving each of ages $1,\dots,k$ in turn. By the multiplication rule, its probability is $\prod_jP(L > j\mid L > j-1) = \prod_j(1 - h(j))$ .

∎

TheoremConstant hazard ⟺ geometric ⟺ memoryless

$h(k)\equiv p$ iff $L$ is geometric $(p)$ : the product gives $P\{L > k\} = (1-p)^k$ , which is (2.8). Constant hazard is exactly the memoryless property: age carries no information about the remaining life.

RemarkContinuous analogue

For a continuous lifetime the hazard is $\lambda(t) = f(t)/(1 - F(t))$ , survival is $\exp\{-\int_0^t\lambda\}$ , and a constant hazard gives exactly the exponential distribution. Proofs are in continuous-random-variables-and-distributions.

IntuitionReading a hazard curve

Decreasing $h$ : infant mortality (defective units fail early).
Constant $h$ : random shocks, as in the backup model’s .001 per day.
Increasing $h$ : wear-out.

The classic “bathtub” curve combines all three. The geometric model, and everything built on it above, assumes the flat middle.

The Poisson distribution and Poisson processes

DefinitionPoisson $(\lambda)$

$X$ is Poisson with parameter $\lambda > 0$ if

p(i) = P\{X = i\} = e^{-\lambda}\frac{\lambda^i}{i!},\qquad i = 0,1,2,\dots \tag{7.1}

It sums to 1 because $\sum_i\lambda^i/i! = e^\lambda$ . Introduced by Poisson (1837) in a book on the probability of verdicts in criminal and civil trials.

Component	Detail
Parameter	$\lambda$ , the mean number of occurrences
Support	$\{0,1,2,\dots\}$
Typical use	the count of many rare, (nearly) independent events

The Poisson distribution as a limit of binomial distributions

TheoremBinomial $(n,\lambda/n)\to$ Poisson $(\lambda)$

Fix $\lambda > 0$ and $k\ge0$ . With $p = \lambda/n$ ,

\binom nkp^k(1-p)^{n-k}\;\longrightarrow\;e^{-\lambda}\frac{\lambda^k}{k!} \qquad(n\to\infty). \tag{2.9–2.10}

So when $n$ is large and $p$ is small, with $np$ moderate, the number of successes is approximately Poisson with $\lambda = np$ .

ProofMass at 0, then the remaining factors (Hajek)

Step 1: $k = 0$ . $\ln p_b(0) = n\ln(1 - \lambda/n) = n\big(-\lambda/n + o(1/n)\big)\to-\lambda$ , using $\ln(1+u) = u + o(u)$ . So $p_b(0) = (1 - \lambda/n)^n\to e^{-\lambda}$ .

Step 2: general $k$ . Rearranging,

p_b(k) = \frac{\lambda^kp_b(0)}{k!}\cdot\underbrace{\frac{n(n-1)\cdots (n-k+1)}{n^k}}_{\to1}\cdot\underbrace{\Big(1 - \frac\lambda n\Big)^{-k}}_{ \to1}\;\to\;\frac{\lambda^ke^{-\lambda}}{k!}.

∎

IntuitionWhy so many counts are Poisson

Each of a huge number of opportunities has a tiny chance of producing an event: each letter on a page might be a misprint, each person might reach age 100, each atom might emit an α-particle this second, each phone owner near a base station might call this minute. The count is binomial with large $n$ and small $p$ , hence nearly Poisson. Only one parameter, $\lambda = np$ , survives the limit, and it is usually estimated from data.

TheoremMean and variance

E[X] = \lambda,\qquad E[X^2] = \lambda(\lambda + 1),\qquad \mathrm{Var}(X) = \lambda.

ProofShift the index (Ross)

E[X] = \sum_{i\ge1}i\frac{e^{-\lambda}\lambda^i}{i!} = \lambda\sum_{j\ge0} \frac{e^{-\lambda}\lambda^j}{j!} = \lambda,

with $j = i - 1$ . The same shift gives $E[X^2] = \lambda\sum_j(j + 1) e^{-\lambda}\lambda^j/j! = \lambda(E[X] + 1) = \lambda^2 + \lambda$ .

Consistency check: the approximating binomial has mean $np = \lambda$ and variance $np(1-p) = \lambda(1 - p)\to\lambda$ .

∎

FormulaRecursion

P\{X = i+1\} = \frac\lambda{i+1}P\{X = i\},\qquad P\{X = 0\} = e^{-\lambda}. \tag{7.6}

This is how calculators compute Poisson tails (e.g. $P\{X\le90\}\approx .171$ for $\lambda = 100$ , and $P\{X\le1075\}\approx.991$ for $\lambda = 1000$ ).

ExamplePoisson computations (Ross)

Typos: $\lambda = \frac12$ per page gives $P(\text{at least one}) = 1 - e^{-1/2}\approx.393$ .
Defectives: each of 10 items is defective with probability .1. $P(\le1\text{ defective})$ is exactly $.9^{10} + 10(.1)(.9)^9 = .7361$ , and the Poisson(1) approximation gives $2e^{-1}\approx.7358$ .
α-particles: 3.2 per second on average, so $P\{X\le2\} = e^{-3.2}(1 + 3.2 + 3.2^2/2)\approx.3799$ .

The Poisson paradigm

TheoremPoisson paradigm (Ross)

Let $n$ events have probabilities $p_1,\dots,p_n$ . If every $p_i$ is small and the events are independent or only weakly dependent, the number that occur is approximately Poisson with mean $\sum_ip_i$ .

NoteA heuristic, not a theorem

“Small” and “weakly dependent” are not made precise in the source. The examples below show both a success of the heuristic and a failure that needs a fix.

ExampleMatches in the hat problem

Let $E_i$ = person $i$ gets their own hat. $P(E_i) = \frac1n$ and $P(E_i\mid E_j) = \frac1{n-1}$ : dependent, but only barely. The paradigm predicts Poisson(1) matches, and indeed $P(\text{exactly }k)\approx e^{-1}/k!$ (conditional-probability-and-independence).

ExampleBirthdays, pairs and triples (Ross)

Pairs. Make a trial for each of the $\binom n2$ pairs, a success if the pair shares a birthday, with probability $\frac1{365}$ . These events are even pairwise independent. So $P(\text{no shared birthday})\approx\exp\Big\{-\frac{n(n-1)}{730}\Big\},$ which is below $\frac12$ iff $n(n-1)\ge730\ln2\approx506$ , i.e. $n\ge23$ . That matches the exact answer in probability-foundations.

Triples. The exact combinatorics are hard, but the paradigm is easy. Each of the $\binom n3$ triples shares a birthday with probability $1/365^2$ , so

P(\text{no three share a birthday})\approx\exp\Big\{-\frac{n(n-1)(n-2)} {799{,}350}\Big\},

which drops below $\frac12$ once $n(n-1)(n-2)\ge554{,}067$ , i.e. $n\ge84$ .

ExampleThe longest run of heads (Ross)

Flip a coin with heads probability $p$ $n$ times. What is the chance of a run of $k$ consecutive heads?

The naive events fail. Let $H_i$ = flips $i,\dots,i+k-1$ are all heads. Each has small probability $p^k$ , but $P(H_2\mid H_1) = p$ , which is far larger. The dependence is too strong.

The fix: count runs by their ends. Let $E_i$ = flips $i..i+k-1$ are heads and flip $i+k$ is a tail ( $i\le n-k$ ), plus $E_{n-k+1}$ = the last $k$ flips are heads. Overlapping $E_i$ are now mutually exclusive, and non-overlapping ones are independent. So the count $N$ is approximately Poisson with mean $(n-k)p^k(1-p) + p^k$ , and with $L_n$ the longest run, $P\{L_n < k\} = P\{N = 0\}\approx\exp\big\{-(n-k)p^k(1-p) - p^k\big\}.$

Fair coin. $P\{L_n < k\}\approx\exp\{-n/2^{k+1}\}$ . With $j = \log_2n$ (an integer), $P\{L_n < j + i\}\approx\exp\{-(1/2)^{i+1}\}$ :

$L_n$	$<j-3$	$j-3$	$j-2$	$j-1$	$j$	$j+1$	$j+2$	$j+3$	$\ge j+4$
prob.	.0183	.1170	.2325	.2387	.1723	.1037	.0569	.0298	.0308

However large $n$ is, the longest run is within 2 of $\log_2n - 1$ with probability about .86.

DerivationThe longest run exactly: inclusion–exclusion and a recursion (Ross)

Inclusion–exclusion. An intersection of $E$ ‘s is 0 if their flip sets overlap. Otherwise it is $p^{rk}(1-p)^r$ (without the last event) or $p^{rk}(1-p)^{r-1}$ (with it). Counting non-overlapping placements as arrangements of blocks and free flips gives

P\{L_n\ge k\} = \sum_{r=1}^{n-k+1}(-1)^{r+1}\Big[\binom{n-rk}r + \frac1p\binom{n-rk}{r-1}\Big]p^{kr}(1-p)^r.

A faster recursion. Let $P_n = P(\text{a run of }k\text{ in }n \text{ flips})$ . Condition on when the first tail appears (flip $j\le k$ ), or on the first $k$ flips all being heads:

P_n = \sum_{j=1}^kP_{n-j}\,p^{j-1}(1-p) + p^k,\qquad P_j = 0\ (j < k),\ \ P_k = p^k.

For $k = 2$ and a fair coin: $P_3 = \frac38$ and $P_4 = \frac12$ . Check: 8 of the 16 sequences of 4 flips contain HH.

The Poisson process

DefinitionPoisson process with rate $\lambda$ (Ross §4.7)

Events occur at random times, with:

$P(\text{exactly one event in an interval of length }h) = \lambda h + o(h)$ ;
$P(\text{two or more events in an interval of length }h) = o(h)$ ;
counts in non-overlapping intervals are independent.

Here $o(h)$ means any $f$ with $f(h)/h\to0$ .

TheoremCounts are Poisson

Under 1–3, the number $N(t)$ of events in any interval of length $t$ satisfies

P\{N(t) = k\} = e^{-\lambda t}\frac{(\lambda t)^k}{k!},\qquad k\ge0. \tag{7.5}

$\lambda$ is the long-run rate of events per unit time.

ProofChop

[0,t]

into

n

tiny intervals

Step 1: Split. $\{N(t) = k\} = A\cup B$ (disjoint), where $A$ = ” $k$ subintervals contain exactly one event, the rest none” and $B$ = ” $N(t) = k$ and some subinterval contains two or more.”

Step 2: $B$ is negligible. By Boole’s inequality and assumption 2, $P(B)\le n\,o(t/n) = t\cdot\frac{o(t/n)}{t/n}\to0.$

Step 3: $A$ is binomial. By assumptions 1 and 3,

P(A) = \binom nk\Big[\frac{\lambda t}n + o\Big(\frac tn\Big)\Big]^k\Big[1 - \frac{\lambda t}n - o\Big(\frac tn\Big)\Big]^{n-k}.

Since $n[\lambda t/n + o(t/n)]\to\lambda t$ , the binomial-to-Poisson limit gives $P(A)\to e^{-\lambda t}(\lambda t)^k/k!$ .

∎

IntuitionA Bernoulli process in continuous time

Each subinterval is one Bernoulli trial with success probability about $\lambda t/n$ . Letting $n\to\infty$ turns binomial counts into Poisson counts, just as scaled geometric waits become exponential (continuous-random-variables-and-distributions).

NoteTODO — Hajek’s time-scaled Bernoulli process

Hajek’s own rescaling construction (bridging §2.6’s Bernoulli process to a Poisson process) is not yet in sources/. The Ross derivation above covers the same idea.

ExampleEarthquakes (Ross)

Earthquakes follow a Poisson process with rate 2 per week.

At least 3 in the next 2 weeks: $N(2)\sim$ Poisson(4), so $P = 1 - e^{-4}(1 + 4 + 8) = 1 - 13e^{-4}\approx.762$ .
Time $X$ to the next one: $X > t$ iff there are no events in $[0,t]$ , so $P\{X > t\} = e^{-2t}$ . The waiting time is exponential (continuous-random-variables-and-distributions).

ExampleWhere Poisson processes show up (Ross)

The number of earthquakes in a time span, wars per year, electrons emitted from a heated cathode, and deaths among a life insurer’s policyholders are all well modeled this way, for the same reason as the binomial limit.

The Erlang distribution

TheoremArrival times are Erlang (Ross §5.6.1)

Let $T_n$ be the time of the $n$ -th event of a Poisson process with rate $\lambda$ . Then

f_{T_n}(t) = \frac{\lambda e^{-\lambda t}(\lambda t)^{n-1}}{(n-1)!},\qquad t\ge0.

This is the gamma $(n,\lambda)$ or $n$ -Erlang distribution. For $n = 1$ it is the exponential.

ProofArrival by

t

iff at least

n

counts by

t

Step 1: Swap waiting for counting. $\{T_n\le t\} = \{N(t)\ge n\}$ , so $P\{T_n\le t\} = \sum_{j\ge n}e^{-\lambda t}\frac{(\lambda t)^j}{j!}.$

Step 2: Differentiate term by term.

f(t) = \sum_{j\ge n}\frac{\lambda e^{-\lambda t}(\lambda t)^{j-1}}{(j-1)!} - \sum_{j\ge n}\frac{\lambda e^{-\lambda t}(\lambda t)^j}{j!}.

The sums telescope, leaving only the $j = n$ term of the first.

∎

ImportantDiscrete and continuous twins

Bernoulli process (discrete time)	Poisson process (continuous time)
binomial count in $n$ trials	Poisson count in time $t$
geometric gap between successes	exponential gap between events
negative binomial time of the $r$ -th success	Erlang time of the $n$ -th event
$\{C_n\ge r\} = \{S_r\le n\}$	$\{N(t)\ge n\} = \{T_n\le t\}$

The general gamma family, with non-integer shape, is in continuous-random-variables-and-distributions.

Quick reference

Object	Statement	Note
Random variable	$X : \Omega\to\mathbb R$ ; $\{X\in A\}$ is an event	indicator $I_A$ for events
pmf	$p_X(u) = P\{X = u\}$ , $\sum p_X = 1$	determines all $P\{X\in A\}$
cdf	$F(x) = P\{X\le x\}$	nondecreasing step function
Dice	sum $\frac{6-\lvert k-7\rvert}{36}$ ; max $\frac{2k-1}{36}$
Coupons	$P\{T > n\} = \sum_{i=1}^{r-1}(-1)^{i+1}\binom ri(1 - i/r)^n\le re^{-n/r}$	inclusion–exclusion
Mean	$E[X] = \sum u\,p_X(u)$	balance point
Indicator	$E[I_A] = P(A)$
LOTUS	$E[g(X)] = \sum g(u)p_X(u)$	group by value of $g$
Linearity	$E[aX + bY + c] = aE[X] + bE[Y] + c$	no independence needed
Newsvendor	stock until the cdf reaches $b/(b+\ell)$
Variance	$E[(X-\mu)^2] = E[X^2] - \mu^2$	die: $35/12$
Scaling	$\mathrm{Var}(aX + b) = a^2\mathrm{Var}(X)$	standardize: $(X-\mu)/\sigma$
Jensen-type	$E[X^2]\ge(E[X])^2$	friendship paradox
Size bias	random student / friend ⇒ larger average	$E[f(Y)] = E[f^2]/E[f]$
Bernoulli $(p)$	$P\{1\} = p$ ; mean $p$ ; variance $p(1-p)\le\frac14$	$X^2 = X$
Binomial $(n,p)$	$\binom nkp^k(1-p)^{n-k}$ ; mean $np$ ; variance $np(1-p)$	sum of $n$ Bernoullis
Sum of indicators (9.1)	$\mathrm{Var} = \sum p_i + \sum_{i\ne j}p_{i,j} - (\sum p_i)^2$	no independence needed
Binomial mode	$\lfloor(n+1)p\rfloor$	ratio $\frac{(n-k+1)p}{k(1-p)}$
Recursion (6.3)	$p(k+1) = \frac p{1-p}\frac{n-k}{k+1}p(k)$	compute the cdf
Majority systems	$2k+1$ beats $2k-1$ iff $p > \frac12$	factor $(2p-1)$
Voter power	$\approx c\sqrt{2n/\pi}$	pivotal chance $\sim1/\sqrt{\pi k}$
Chuck-a-luck	$E = -17/216$
Best of seven	$\binom{n-1}3[p^4q^{n-4} + q^4p^{n-4}]$	$\frac18,\frac14,\frac5{16},\frac5{16}$ at $p = \frac12$
Geometric $(p)$	$(1-p)^{k-1}p$ ; tail $(1-p)^k$	counts trials, $k\ge1$
Geometric moments	mean $1/p$ ; variance $(1-p)/p^2$	first-step analysis
Memoryless	$P(L > k+n\mid L > n) = P(L > k)$	constant hazard
Coupon collector	$E = nH_n\approx n\ln n$	sum of geometrics
Bernoulli process	$X$ , $L$ , $C$ , $S$ determine each other	$\{C_n\ge r\} = \{S_r\le n\}$
Negative binomial $(r,p)$	$\binom{n-1}{r-1}p^r(1-p)^{n-r}$ , $n\ge r$	sum of $r$ geometrics
NB moments	mean $r/p$ ; variance $r(1-p)/p^2$	4 ones on a die: 24, 120
Banach matches	$\binom{2N-k}N2^{-(2N-k)}$	NB with $r = N+1$
Union bound	$P(\cup A_i)\le\sum P(A_i)$	gap $= P(AB)$ ; tight for rare events
Parallel / series	$\prod p_i$ / $1 - \prod q_i\approx\sum p_i$
Networks C vs D	$\approx4p^2$ vs $\approx2p^2$	count minimum cuts
Bridge E	$p_5P_C + q_5P_D$	condition on the bridge link
Flow capacity	pmf by enumerating states	$p_Y(0)$ = outage
Array code	$\le784p^4 + \binom{64}6p^6\approx0.86\times10^{-9}$	rectangles of 4 errors
Single backup	$\approx500\times200$ days $\approx274$ years	nested geometrics
Hazard	$h(k) = P(L = k\mid L\ge k)$ ; $P(L > k) = \prod(1 - h)$	constant ⇒ geometric/exponential
Poisson $(\lambda)$	$e^{-\lambda}\lambda^i/i!$ ; mean = variance = $\lambda$	limit of binomial $(n,\lambda/n)$
Poisson recursion	$p(i+1) = \frac\lambda{i+1}p(i)$
Poisson paradigm	many rare, weakly dependent events ⇒ Poisson $(\sum p_i)$	birthdays: 23 for pairs, 84 for triples
Longest run	$P\{L_n < k\}\approx e^{-n/2^{k+1}}$ (fair coin)	$\approx\log_2n$
Poisson process	$N(t)\sim$ Poisson $(\lambda t)$ , independent increments	exponential gaps
Erlang	$f(t) = \lambda e^{-\lambda t}(\lambda t)^{n-1}/(n-1)!$	$\{N(t)\ge n\} = \{T_n\le t\}$
Sum over outcomes	$E[X] = \sum_\omega X(\omega)p(\omega)$	gives $E[\sum X_i] = \sum E[X_i]$
Hypergeometric	$\binom mi\binom{N-m}{n-i}/\binom Nn$ ; mean $np$ ; variance $\frac{N-n}{N-1}np(1-p)$	≈ binomial when $N\gg n$
Capture–recapture	$\hat N = \lfloor mn/i\rfloor$	ML estimate
Zeta	$C/k^{\alpha+1}$	discrete power law

Facts to keep to hand

A random variable forgets the outcome, keeps the number. The pmf is all you need for events about $X$ alone, but joint questions need joint information. Independence is precisely the condition that the joint pmf is the product of the marginals.
Expectation is linear, always. $E[X + Y] = E[X] + E[Y]$ with no independence. Combined with $E[I_A] = P(A)$ , this turns counting questions into sums of probabilities. Products are different: $E[XY] = E[X]E[Y]$ needs independence, and $E[g(X)]\ne g(E[X])$ in general.
Variance is the price of squaring. It is invariant under shifts and scales by $a^2$ . It is computed as $E[X^2] - \mu^2$ , and it is nonnegative, which is exactly $E[X^2]\ge(E[X])^2$ . That one inequality powers the friendship paradox and the “shared birthday” example.
Size-biased sampling inflates averages. A random student’s bus, or a random friend’s friend count, is weighted by the very quantity being measured, so it exceeds the plain average. Whenever sampling is proportional to something, expect this bias.
One experiment, four views. Trials, gaps, counts and arrival times of a Bernoulli process are interchangeable descriptions. Binomial and negative binomial questions are the same question asked from different sides: $\{C_n\ge r\} = \{S_r\le n\}$ .
Linearity plus indicators does most of the work. The means of the binomial ( $np$ ), negative binomial ( $r/p$ ) and coupon collector ( $nH_n$ ) come from splitting into simple pieces. Variances add only when the pieces are independent, or (9.1) handles the covariance terms.
First-step analysis is how geometric facts are derived. “Condition on trial 1; the rest looks like the start” gives the mean, variance and memorylessness in a few lines. It works because independent trials restart the process.
Rare waits are long and noisy. A geometric with small $p$ has $\sigma\approx\mu = 1/p$ . Averages alone badly understate the risk of very long waits.
In reliability, series adds and parallel multiplies. For small failure probabilities, outage $\approx$ (number of minimum-size cuts) × $p^{\text{cut size}}$ . Structure (which cuts exist) matters more than the number of components: D beats C with the same four links, and the bridge link in E adds almost nothing.
The union bound is the reliability engineer’s approximation. It is loose for likely events but nearly exact for rare, weakly overlapping ones, which is exactly the regime of well-designed systems. Sharpening it means identifying which failure patterns actually cause system failure (784 rectangles, not 635,376 quadruples).
Redundancy squares the failure rate, up to a window factor. A backup converts a single rare failure into two rare failures within a repair window, roughly $p\cdot(\text{window})\cdot p$ . Fast repair is worth as much as reliable parts.
Memorylessness means constant hazard. The geometric (and later the exponential) is the unique lifetime model in which age tells you nothing. Any model with wear-out or infant mortality must abandon it.
Poisson is the law of rare events. Many opportunities, each unlikely and nearly independent, give a Poisson count with one parameter, its mean, which also equals its variance. When dependence is strong (overlapping runs), redefine the events so that it becomes weak.
The Poisson process is the Bernoulli process in continuous time. Poisson counts, exponential gaps and Erlang arrival times replace binomial counts, geometric gaps and negative binomial arrival times, and the counting–waiting duality carries over.
Sampling without replacement keeps the mean and shrinks the variance. The hypergeometric has the binomial mean and the binomial variance times $\frac{N-n}{N-1}$ . For small samples from large populations the difference disappears.

References

Hajek, Probability with Engineering Applications (ECE 313 notes) — chapter 2, §§2.1–2.2, 2.4.3–2.7, 2.10 (total expectation), 2.12
Ross, A First Course in Probability — chapter 4, §§4.1–4.9; §5.6.1 (Erlang)

Related

Discrete Random Variables and Their Distributions

Motivation: from outcomes to numbers

Random variables and probability mass functions

The running example: dice

The mean and variance of a random variable

Expectation

The law of the unconscious statistician

Variance

The Bernoulli trial family

Bernoulli distribution

Binomial distribution

Mean and variance

Shape: mode, median, recursion

Applications

Geometric distribution

Memorylessness

Bernoulli process and the negative binomial distribution

Negative binomial distribution

Sampling without replacement: the hypergeometric distribution

The zeta (Zipf) distribution

Union bound

Network outage probability

Distribution of the capacity of a flow network

Analysis of an array code

Reliability of a single backup

Failure rate functions

The Poisson distribution and Poisson processes

The Poisson distribution as a limit of binomial distributions

The Poisson paradigm

The Poisson process

The Erlang distribution

Quick reference

References

Mentioned in