Formula & theorem reference

This isn't really a theorem to prove so much as a fact to see. Lay the first choice's m options down the rows of a grid and the second choice's n options across the columns. Every cell of that grid is exactly one valid pairing — one option from the first choice matched with one option from the second — and every valid pairing lands in exactly one cell. A grid with m rows and n columns has m \times n cells. Counting the pairings and counting the cells are the same question, so they have the same answer. Chaining a third independent choice onto the pair just replaces each cell of that grid with a fresh n_3-row stack, and multiplication absorbs each new stage the same way.

This is just the counting principle, run r times in a row. The first position in the arrangement can be filled by any of the n items. The second position can be filled by any of the n - 1 items that remain (one has been used). The third by any of the n-2 remaining, and so on, down to the rth position, which has n - (r-1) = n - r + 1 choices left. Multiply across all r positions: P(n,r) = n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1). That product has exactly r factors, starting at n and counting down. To see it equals \frac{n!}{(n-r)!}, write n! in full and notice the tail end cancels: n! = \bigl[n(n-1)\cdots(n-r+1)\bigr] \cdot (n-r)!, so dividing both sides by (n-r)! leaves exactly the product above.

Start from P(n,r), which counts every arrangement of r chosen items. Each unordered group of r items corresponds to many of those arrangements — specifically, every one of the r! ways to reorder that same group is a different permutation but the exact same combination. So P(n,r) overcounts each combination by a factor of r!, and dividing it out gives the true count: C(n,r) = \frac{P(n,r)}{r!} = \frac{n!/(n-r)!}{r!} = \frac{n!}{r!\,(n-r)!}.

A and \overline{A} are mutually exclusive and their union is the whole sample space S. Additivity (axiom 3) gives P(A) + P(\overline{A}) = P(A \cup \overline{A}) = P(S), and normalization (axiom 2) gives P(S) = 1. So P(A) + P(\overline{A}) = 1, which rearranges to P(\overline{A}) = 1 - P(A).

A \cup B splits into three mutually exclusive pieces: A \setminus B, A \cap B, and B \setminus A. Additivity gives P(A \cup B) = P(A \setminus B) + P(A \cap B) + P(B \setminus A). Separately, A splits into A \setminus B and A \cap B, so P(A) = P(A \setminus B) + P(A \cap B), and likewise P(B) = P(B \setminus A) + P(A \cap B). Adding P(A) + P(B) therefore counts P(A \cap B) twice; subtracting it once leaves exactly P(A \cup B).

Apply the two-event addition rule to A \cup (B \cup C): P(A \cup B \cup C) = P(A) + P(B \cup C) - P\big(A \cap (B \cup C)\big). Expand P(B \cup C) = P(B) + P(C) - P(B \cap C) by the addition rule again. For the last term, A \cap (B \cup C) = (A \cap B) \cup (A \cap C) by the distributive law, so a third application of the addition rule gives P\big(A \cap (B \cup C)\big) = P(A \cap B) + P(A \cap C) - P(A \cap B \cap C). Substituting both expansions back in and collecting terms gives the stated formula. Each pairwise overlap is subtracted once and the triple overlap, removed three times by the pairwise subtractions, is added back once to restore it to being counted exactly once.

Both are proved by double inclusion, checking an arbitrary element x \in U against each side.

First law. x \in \overline{A \cup B} means x \notin A \cup B, which means x \notin A and x \notin B (an element outside a union is outside both pieces). That is exactly x \in \overline{A} and x \in \overline{B}, i.e. x \in \overline{A} \cap \overline{B}. Every step above reverses, so the two sets have identical elements.

Second law. x \in \overline{A \cap B} means x \notin A \cap B, which means x \notin A or x \notin B (an element outside an intersection is missing from at least one piece). That is exactly x \in \overline{A} or x \in \overline{B}, i.e. x \in \overline{A} \cup \overline{B}. Again every step reverses.

Both arguments are the exact set-theoretic translation of propositional De Morgan's laws, with \cup standing in for \vee, \cap for \wedge, and complement for negation.

Start from n!, the count if every one of the n objects were secretly distinct (as if each carried its own invisible label). Within that count, every group of n_1 identical objects can be relabeled among themselves in n_1! ways without changing the arrangement anyone can actually see — so n! overcounts the first repeated group by a factor of n_1!. The same overcounting happens independently for the second group (factor n_2!), the third, and so on. Dividing n! by n_1!\, n_2! \cdots n_k! removes every one of those redundant relabelings at once, since the groups' internal shufflings are independent of each other.

Line the n items up in a row first: there are n! such arrangements. Bending any one row into a circle produces exactly n different rows that land on the same circular arrangement — one for each rotation of which item is "first." So every circular arrangement is counted n times among the n! linear ones, and dividing removes the overcount: \frac{n!}{n} = (n-1)!. Equivalently: fix one item's seat to remove rotational symmetry, then arrange the other n-1 items in the remaining seats in any order.

Choose the first group of k_1 items from all n: \binom{n}{k_1} ways. From the n - k_1 that remain, choose the second group of k_2: \binom{n-k_1}{k_2} ways. Continue until every item is placed. By the product rule, the total count is \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots = \frac{n!}{k_1!(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!(n-k_1-k_2)!}\cdots. Every factorial in a denominator cancels the matching factorial in the next numerator except the very last, leaving \dfrac{n!}{k_1!\,k_2!\,\cdots\,k_m!}. Setting m=2 recovers the ordinary binomial coefficient \binom{n}{k_1,\,n-k_1} = \binom{n}{k_1}.

Represent the n items as n stars in a row. Splitting them into k bins is the same as choosing where to place k-1 dividing bars among the stars — everything before the first bar goes in bin 1, everything between the first and second bar goes in bin 2, and so on. The row now has n stars and k-1 bars, n+k-1 symbols in total, and a distribution is completely determined by which k-1 of those n+k-1 positions hold bars. That is exactly \binom{n+k-1}{k-1} choices.

The conditional probability formula defines P(B \mid A) = \dfrac{P(A \cap B)}{P(A)} whenever P(A) \neq 0. Multiplying both sides by P(A) isolates P(A \cap B) directly: P(A)\,P(B \mid A) = P(A) \cdot \frac{P(A \cap B)}{P(A)} = P(A \cap B). The same rearrangement starting from P(A \mid B) gives the symmetric form P(A \cap B) = P(B)\,P(A \mid B) whenever P(B) \neq 0 instead.

Because the B_i partition the sample space, A itself splits into the pairwise mutually exclusive pieces A \cap B_1, A \cap B_2, \ldots, A \cap B_n — every outcome in A lands in exactly one B_i, so it lands in exactly one A \cap B_i. The third probability axiom (additivity) then gives P(A) = P(A \cap B_1) + P(A \cap B_2) + \cdots + P(A \cap B_n). The multiplication rule rewrites each term as P(A \cap B_i) = P(A \mid B_i)\,P(B_i), which is exactly the sum above.

The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.

Apply Bayes' theorem to A and to its complement separately: P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)}, \qquad P(\text{not } A \mid B) = \frac{P(B \mid \text{not } A)\,P(\text{not } A)}{P(B)}. Dividing the first equation by the second cancels the shared denominator P(B) entirely: \frac{P(A \mid B)}{P(\text{not } A \mid B)} = \frac{P(B \mid A)}{P(B \mid \text{not } A)} \cdot \frac{P(A)}{P(\text{not } A)}. The left side is \operatorname{odds}(A \mid B) and the rightmost factor is \operatorname{odds}(A), giving exactly the stated form. Never needing P(B) is the whole appeal: the odds form updates a prior directly by a likelihood ratio, with no separate normalization step.

The multiplication rule gives P(A \cap B) = P(A)\,P(B \mid A) whenever P(A) \neq 0. Substituting P(A \cap B) = P(A)P(B) and dividing both sides by P(A) shows this is equivalent to P(B \mid A) = P(B) — conditioning on A leaves B's probability completely unchanged, which is the intuitive meaning independence is meant to capture. The same substitution starting from P(A\mid B) shows P(A\mid B) = P(A) whenever P(B)\ne 0, confirming the relationship is symmetric.

The four equally likely outcomes are HH, HT, TH, TT. A = \{HH, HT\}, B = \{HH, TH\}, C = \{HT, TH\}, each with probability \tfrac12. Every pairwise intersection is a single outcome: A \cap B = \{HH\}, A \cap C = \{HT\}, B \cap C = \{TH\}, each with probability \tfrac14 = \tfrac12\cdot\tfrac12 — so all three pairs pass the independence test. But A \cap B = \{HH\} already forces the outcome to be HH whenever both A and B hold — and HH fails C (the two coins agree, they don't differ). So A \cap B \cap C = \varnothing, giving P(A\cap B\cap C) = 0, while P(A)P(B)P(C) = \tfrac18 \neq 0. Mutual independence genuinely asks more than every pair checking out.

Nothing here is a new kind of object — X is an ordinary function, with domain S (the outcomes) and range the set of values X actually takes. Different outcomes can share a value (the function need not be one-to-one), which is exactly why a random variable's range is almost always smaller than its domain: many outcomes routinely collapse onto one number. The probability distribution of X records, for every value x in its range, the probability P(X=x) of the event \{s \in S : X(s)=x\} — the set of every outcome mapping to that value.

Both conditions are the probability axioms restated for a random variable's own values rather than for arbitrary events. Each p(x) is really P(X=x), the probability of the event \{s \in S : X(s)=x\}, so nonnegativity of probability forces p(x)\ge 0. The events "X=x" for every possible x are pairwise mutually exclusive (a single outcome can't map to two different values) and their union is the entire sample space, so additivity plus normalization force \sum_x p(x) = P(S) = 1.

For a discrete random variable with pmf p, F(x) sums p over every value at or below x: F(x) = \sum_{t \leq x} p(t). Because the events "X=t" for different t are pairwise mutually exclusive, this sum is exactly P(X \leq x) by additivity. F is defined at every real x (not only X's own possible values) because the question "P(X \leq x)" makes sense no matter what number x is asked about — between two consecutive values X can take, F simply stays flat, since no additional probability mass has been crossed.

This is a weighted average, and the weighting is what makes it meaningful over the long run. Imagine repeating the underlying random process N times, for very large N: outcome x_i will occur approximately N p_i times (that's what "probability p_i" means in the long run). The total payout across all N trials is then approximately \sum_i x_i \cdot (N p_i), and dividing by N trials to get the average payout per trial leaves exactly \sum_i x_i p_i — the probabilities' role as relative frequencies is what turns a plain average into a probability-weighted one.

Group the sample space by X's own value: every outcome s with X(s)=x contributes g(X(s)) = g(x) to the sum defining E[g(X)] over outcomes, and there are exactly p(x) worth of probability mass among those outcomes. Summing g(x) once per value x, weighted by how much probability mass maps to that x, is precisely \sum_x g(x)p(x), the same regrouping-by-value argument that turns "sum over outcomes" into "sum over X's own values" for E[X] itself, applied here to g(X) instead of X.

Let the sample space be S = \{s_1, s_2, \ldots, s_n\} with P(s_i) = p_i. By definition, a random variable's expected value is a sum taken directly over the sample space: E(aX+bY) = \sum_{i=1}^{n} \big(aX(s_i) + bY(s_i)\big)\,p_i. Distribute p_i across the sum inside each term, then split the single sum into two sums, since addition of finitely many numbers can always be regrouped this way: \sum_{i=1}^{n} \big(aX(s_i)p_i + bY(s_i)p_i\big) = a\sum_{i=1}^{n} X(s_i)p_i + b\sum_{i=1}^{n} Y(s_i)p_i. The two resulting sums are exactly E(X) and E(Y) by definition, so E(aX+bY) = a\,E(X) + b\,E(Y). Nowhere did this argument use P(X=x, Y=y) = P(X=x)P(Y=y) — the independence condition — which is exactly why the result holds regardless of whether X and Y are independent.

(X-\mu) is itself a random variable — how far a draw of X lands from the mean — and squaring it makes every deviation contribute positively regardless of direction, so a symmetric spread above and below the mean doesn't cancel to zero the way E(X-\mu) itself always does (by linearity, E(X-\mu) = E(X)-\mu = 0 for every distribution, which is exactly why "average deviation" isn't a useful measure of spread on its own). \operatorname{Var}(X) is LOTUS applied to g(x) = (x-\mu)^2, which is why it's expressed as a weighted sum over X's own pmf rather than needing a separate distribution for the squared deviation.

Expand the squared deviation inside the definition of variance: \operatorname{Var}(X) = E\big[(X-\mu)^2\big] = E\big[X^2 - 2\mu X + \mu^2\big]. Linearity of expectation splits this into three separate terms, treating \mu (a constant, not a random variable) as it would any constant multiplier: E(X^2) - 2\mu\,E(X) + \mu^2. Since E(X) = \mu by definition, the middle term is -2\mu \cdot \mu = -2\mu^2, leaving E(X^2) - 2\mu^2 + \mu^2 = E(X^2) - \mu^2. This form is almost always faster to compute by hand than the definition directly, since it needs only two separate expected-value sums (of X and of X^2) rather than one sum over every deviation.

Let \mu = E(X), so E(aX+b) = a\mu+b by linearity. Then \operatorname{Var}(aX+b) = E\big[(aX+b-(a\mu+b))^2\big] = E\big[(aX-a\mu)^2\big] = E\big[a^2(X-\mu)^2\big]. Linearity pulls the constant a^2 back out of the expectation: a^2 E\big[(X-\mu)^2\big] = a^2\operatorname{Var}(X). The shift b cancelled entirely inside the subtraction, which is exactly why adding a constant to every outcome moves the mean but never changes how spread out the outcomes are around it.

Let \mu_X = E(X), \mu_Y = E(Y). Expand the squared deviation of the sum: \operatorname{Var}(X+Y) = E\big[((X-\mu_X)+(Y-\mu_Y))^2\big] = E\big[(X-\mu_X)^2\big] + E\big[(Y-\mu_Y)^2\big] + 2E\big[(X-\mu_X)(Y-\mu_Y)\big]. The first two terms are \operatorname{Var}(X) and \operatorname{Var}(Y) directly. The cross term is the covariance of X and Y; independence makes E[(X-\mu_X)(Y-\mu_Y)] = E(X-\mu_X)\,E(Y-\mu_Y) = 0 \cdot 0 = 0 (the expectation of a product of independent quantities is the product of their expectations, and each factor's own expectation is zero by linearity). With the cross term gone, \operatorname{Var}(X+Y) = \operatorname{Var}(X) + \operatorname{Var}(Y) exactly. Without independence, that cross term need not vanish, which is why this result — unlike linearity of expectation — genuinely needs the hypothesis.

A Bernoulli random variable is exactly an indicator random variable for its own success event, so its mean and variance follow directly from the indicator-variable results already established: E(X) = 1\cdot p + 0\cdot(1-p) = p, and E(X^2) = 1^2\cdot p + 0^2\cdot(1-p) = p, so \operatorname{Var}(X) = E(X^2)-\mu^2 = p - p^2 = p(1-p).

Write X = I_1 + I_2 + \cdots + I_n, one indicator per trial (the indicator trick). Linearity gives E(X) = \sum_i E(I_i) = np immediately, with no independence required. The variance DOES need independence: since the trials are independent, \operatorname{Var}(X) = \sum_i \operatorname{Var}(I_i) = n\,p(1-p), applying the sum-of- independent-variables rule to n terms instead of just two. The pmf counts the \binom{n}{k} orderings of k successes and n-k failures, each with probability p^k(1-p)^{n-k}.

p(k) is exactly k-1 failures then one success, each trial independent: (1-p)^{k-1}\cdot p. The mean and variance both follow from differentiating the geometric series \sum_{k\ge1}(1-p)^{k-1} = 1/p with respect to p -- the details are a calculus exercise, not a probability one, and are not re-derived here.

P(X>s) = (1-p)^s (the first s trials all fail). So P(X>s+t \mid X>s) = \frac{P(X>s+t)}{P(X>s)} = \frac{(1-p)^{s+t}}{(1-p)^s} = (1-p)^t = P(X>t). The past failures carry no information about the future -- the process has no memory of how long it has already run.

X = Y_1+Y_2+\cdots+Y_r, a sum of r INDEPENDENT Geometric(p) variables -- Y_1 is the wait for the 1st success, Y_2 the additional wait for the 2nd after the 1st, and so on, each fresh wait having the same distribution by the memoryless property. Linearity gives E(X) = r\cdot(1/p) = r/p; independence lets variances add, giving \operatorname{Var}(X) = r\cdot(1-p)/p^2. The pmf counts orderings of r-1 successes among the first k-1 trials, times the fixed r-th trial itself landing on a success.

The pmf is a direct ratio of counts: choose k of the K successes and n-k of the N-K failures, over all \binom{N}{n} equally likely samples. The mean matches the binomial mean n\cdot(K/N) exactly (by symmetry, each of the n draws is marginally a success with probability K/N, and linearity of expectation never needed independence). The variance carries an extra factor \tfrac{N-n}{N-1}, the finite population correction, versus the binomial's np(1-p) -- it shrinks toward 0 as n\to N (drawing the whole population removes all randomness) and toward 1 as N\to\infty (sampling without replacement from a huge population behaves like sampling with replacement).

The mean and variance both equal \lambda -- a distinctive fingerprint of this family, unlike the binomial where mean np and variance np(1-p) differ whenever p\ne 0. The pmf itself is most easily justified as the limit of a binomial pmf as n\to\infty with np held fixed at \lambda, which the next section derives directly.

Expand the binomial pmf and separate the pieces that have a clean limit: \binom{n}{k}\left(\frac{\lambda}{n}\right)^k\left(1-\frac{\lambda}{n}\right)^{n-k} = \frac{n(n-1)\cdots(n-k+1)}{n^k}\cdot\frac{\lambda^k}{k!}\cdot\left(1-\frac{\lambda}{n}\right)^{n-k}. The first factor is a product of k terms each of the form \tfrac{n-j}{n}\to 1 as n\to\infty, for fixed k. The last factor is \left(1-\tfrac{\lambda}{n}\right)^{n-k} \to e^{-\lambda}, a standard limit (the same one that defines e^x). What remains is exactly \tfrac{\lambda^k}{k!}e^{-\lambda}, the Poisson(\lambda) pmf. This is why the Poisson distribution models "rare events over many opportunities" -- a large number of trials n, each individually unlikely (p small), with the product np held at a moderate rate \lambda.

The mean is the midpoint of the range, by symmetry -- every value is equally likely, so the weighted average is the plain average of the two endpoints. The variance formula follows from summing (k-\mu)^2 evenly across all b-a+1 values (a sum of squares of an evenly spaced sequence centered at 0), and is not re-derived here.

The two conditions are exactly the continuous analogue of a discrete probability distribution: individual probabilities can't be negative, which forces f(x)\ge 0, and the probabilities of all possible outcomes must add to 1, which becomes \int_a^b f(x)\,dx=1 once "adding over all outcomes" is replaced by integrating over the continuum from a to b. The same reasoning that turns a sum into an integral for area turns "sum the probability over every outcome in [c,d]" into \int_c^d f(x)\,dx — each infinitesimal width dx near x carries "probability density f(x) times width dx" worth of probability, and those slivers are added by the integral exactly as area slivers are.

P(X\le x) is the probability mass to the left of x, which for a continuous variable is exactly the area under f from -\infty to x -- the same "area equals probability" fact probability-as-area already established, applied to a growing interval instead of a fixed one. F is non-decreasing since extending the interval of integration can only add nonnegative area. F has no jumps because a jump of size P(X=x) would require P(X=x)>0, which is false for every continuous X.

Fix x in (a,b) and form the difference quotient defining A'(x): \frac{A(x+h)-A(x)}{h} = \frac{1}{h}\left[\int_a^{x+h}f(t)\,dt -\int_a^x f(t)\,dt\right] = \frac{1}{h}\int_x^{x+h} f(t)\,dt, the last step by additivity of the definite integral over adjacent intervals. The remaining integral is f's net signed area over a sliver of width h -- and by the Mean Value Theorem for Integrals (f continuous on [x,x+h]), that sliver equals f(c)\cdot h for SOME c between x and x+h, so \frac{A(x+h)-A(x)}{h} = f(c) \quad\text{for some $c$ strictly between $x$ and $x+h$.} As h\to0, c is squeezed between x and x+h and is forced to x too, and f's continuity at x then forces f(c)\to f(x). Taking the limit, A'(x) = \lim_{h\to0}\frac{A(x+h)-A(x)}{h} = \lim_{h\to0} f(c) = f(x).

The same conclusion falls out of the Riemann-sum definition directly, without invoking the Mean Value Theorem for Integrals: for small h, \int_x^{x+h} f(t)\,dt is itself approximated by a single thin rectangle of width h and height approximately f(x) (since f barely changes over an interval that short, by continuity), so \frac{1}{h}\int_x^{x+h}f(t)\,dt\approx f(x), with the approximation becoming exact in the limit h\to0 -- the same "thin slice, height \approx f(x)" idea Chapter 7 built Riemann sums from in the first place, just run over a single infinitesimally short interval instead of the whole [a,b].

Continuity of f is load-bearing in both arguments: it is what supplies the Mean Value Theorem for Integrals' own hypothesis, and it is what forces f(c)\to f(x) as the squeezed point c\to x -- a discontinuous f can make A fail to be differentiable exactly at the discontinuity, even though A itself (an accumulated area) still exists there.

Since a continuous CDF F is non-decreasing and takes every value in [0,1] continuously (no jumps), F^{-1}(p) is well-defined for every p strictly between 0 and 1 -- exactly one x_p satisfies F(x_p)=p. This is the continuous counterpart of "reading a CDF graph backwards": instead of finding F(x) from x, a quantile finds x from a target probability p.

This is the continuous version of the discrete weighted average E(X)=\sum_i x_i p_i. Partition [a,b] into thin slivers of width \Delta x; the sliver at x carries approximately f(x)\Delta x worth of probability (by the definition of a density), so it contributes x\cdot f(x)\Delta x to the weighted sum, the same way a discrete outcome x_i contributes x_i p_i. Summing every sliver's contribution gives a Riemann sum \sum x\,f(x)\Delta x, and letting the slivers shrink turns that sum into \int_a^b x f(x)\,dx.

f integrates to 1 over [a,b] automatically: \int_a^b \frac{1}{b-a}\,dx = \frac{b-a}{b-a} = 1. The mean is the midpoint by the same symmetry argument the discrete uniform distribution used -- no value is weighted more than any other. The variance formula matches the discrete uniform's own \big((b-a+1)^2-1\big)/12 in the limit of infinitely many equally spaced values collapsing to a continuum, simplifying to (b-a)^2/12.

The exponential is the continuous counterpart of the geometric distribution: where geometric counts discrete TRIALS until the first success, exponential measures continuous TIME until the first Poisson event, at the same underlying rate \lambda. Its CDF F(x)=1-e^{-\lambda x} comes directly from a Poisson-process fact: no events occurring in [0,x] has probability e^{-\lambda x} (the Poisson pmf at 0, with mean \lambda x), so at least one event by time x has probability 1-e^{-\lambda x}.

P(X>s) = e^{-\lambda s} (no events in [0,s]). So P(X>s+t\mid X>s) = \frac{P(X>s+t)}{P(X>s)} = \frac{e^{-\lambda(s+t)}}{e^{-\lambda s}} = e^{-\lambda t} = P(X>t). This is the exact continuous-time analog of the geometric distribution's own memoryless property, and the exponential is in fact the ONLY continuous distribution with this property, the same way geometric is the only memoryless discrete one.

The curve is symmetric about \mu (replacing x with 2\mu-x leaves f unchanged), which is why the mean and the median coincide for every normal distribution. It's bell-shaped because f is maximized exactly at x=\mu and decays toward 0 in both directions. That decay is faster as |x-\mu| grows relative to \sigma: \sigma itself controls exactly how fast it happens, wider for larger \sigma.

Standardizing is a linear transformation, Z=aX+b with a=1/\sigma, b=-\mu/\sigma. By the linear-transformation rules already established, E(Z) = E(X)/\sigma - \mu/\sigma = \mu/\sigma-\mu/\sigma=0 and \operatorname{Var}(Z) = \operatorname{Var}(X)/\sigma^2 = \sigma^2/\sigma^2=1 -- mean 0, variance 1, exactly the standard normal's own parameters. Every normal distribution reduces to the SAME standard normal after standardizing, which is exactly why one single \Phi table (or function) answers a probability question for any \mu,\sigma at all.

Each bound follows from \Phi(k)-\Phi(-k) at k=1,2,3, using the standard normal CDF: \Phi(1)-\Phi(-1)\approx0.6827, \Phi(2)-\Phi(-2)\approx0.9545, \Phi(3)-\Phi(-3)\approx0.9973. Since standardizing reduces every normal distribution to the same standard normal, these three numbers are universal -- they hold for every \mu and \sigma, not just a particular pair.

This is a special case of the central limit theorem: X is itself a sum of n independent Bernoulli(p) trials, and a sum of enough independent, identically distributed pieces is approximately normal regardless of the pieces' own shape (a fact this course's own limit- theorems chapter develops in full generality). X's own mean np and variance np(1-p) carry over unchanged into the approximating normal distribution's parameters.

A discrete bar at k occupies the WHOLE interval [k-0.5,k+0.5] once placed on a continuous axis, not just the single point k. Approximating P(X\le k) with the normal CDF evaluated exactly at k (no correction) cuts that bar in half, systematically excluding roughly P(X=k)/2 worth of area. Evaluating instead at k+0.5 includes the bar's ENTIRE width, which is why the correction consistently improves the approximation's accuracy, especially for small or moderate n.

Every outcome with X=x falls into exactly one value of Y, so the events \{X=x, Y=y\} over every y partition the event \{X=x\} completely, with no overlap. Summing their disjoint probabilities recovers P(X=x) exactly, which is the definition of p_X(x). The continuous case replaces this partition-and-sum with the same argument carried out via an integral over y instead of a sum.

This is exactly the conditional-probability formula P(B\mid A)=P(A\cap B)/P(A) applied to the events A=\{X=x\} and B=\{Y=y\}. Nothing new is required beyond that definition; a joint pmf is just an organized table of such events, one cell per (x,y) pair.

This restates event-independence, P(A\cap B)=P(A)P(B), applied simultaneously to every event pair A=\{X=x\}, B=\{Y=y\}. A single pair failing to factor is enough to break independence entirely, which is why the definition demands the product rule hold for EVERY pair, not merely on average across them.

Expand the product inside the definition: E[(X-\mu_X)(Y-\mu_Y)] = E[XY - \mu_X Y - \mu_Y X + \mu_X\mu_Y]. Linearity splits this into four separate expectations. The middle two collapse to -\mu_X\mu_Y each, since E(Y)=\mu_Y and E(X)=\mu_X by definition, leaving E(XY) - \mu_X\mu_Y - \mu_Y\mu_X + \mu_X\mu_Y = E(XY) - \mu_X\mu_Y. That is the same computational shortcut the variance formula uses, generalized from one variable to two.

Let the sample space be S = \{s_1, s_2, \ldots, s_n\} with P(s_i) = p_i. By definition, a random variable's expected value is a sum taken directly over the sample space: E(aX+bY) = \sum_{i=1}^{n} \big(aX(s_i) + bY(s_i)\big)\,p_i. Distribute p_i across the sum inside each term, then split the single sum into two sums, since addition of finitely many numbers can always be regrouped this way: \sum_{i=1}^{n} \big(aX(s_i)p_i + bY(s_i)p_i\big) = a\sum_{i=1}^{n} X(s_i)p_i + b\sum_{i=1}^{n} Y(s_i)p_i. The two resulting sums are exactly E(X) and E(Y) by definition, so E(aX+bY) = a\,E(X) + b\,E(Y). Nowhere did this argument use P(X=x, Y=y) = P(X=x)P(Y=y) — the independence condition — which is exactly why the result holds regardless of whether X and Y are independent.

Let \mu = E(X), so E(aX+b) = a\mu+b by linearity. Then \operatorname{Var}(aX+b) = E\big[(aX+b-(a\mu+b))^2\big] = E\big[(aX-a\mu)^2\big] = E\big[a^2(X-\mu)^2\big]. Linearity pulls the constant a^2 back out of the expectation: a^2 E\big[(X-\mu)^2\big] = a^2\operatorname{Var}(X). The shift b cancelled entirely inside the subtraction, which is exactly why adding a constant to every outcome moves the mean but never changes how spread out the outcomes are around it.

Standardizing is a linear transformation, Z=aX+b with a=1/\sigma, b=-\mu/\sigma. By the linear-transformation rules already established, E(Z) = E(X)/\sigma - \mu/\sigma = \mu/\sigma-\mu/\sigma=0 and \operatorname{Var}(Z) = \operatorname{Var}(X)/\sigma^2 = \sigma^2/\sigma^2=1 -- mean 0, variance 1, exactly the standard normal's own parameters. Every normal distribution reduces to the SAME standard normal after standardizing, which is exactly why one single \Phi table (or function) answers a probability question for any \mu,\sigma at all.

Y\le y and g(X)\le y are literally the same event, since Y is defined to equal g(X). Rewriting \{g(X)\le y\} as a set of x-values (inverting g where it is monotonic, or unioning several such sets where it is not) turns a question about the new variable Y into a question already answerable from X's own CDF or pdf, with no new machinery required.

Let the sample space be S = \{s_1, s_2, \ldots, s_n\} with P(s_i) = p_i. By definition, a random variable's expected value is a sum taken directly over the sample space: E(aX+bY) = \sum_{i=1}^{n} \big(aX(s_i) + bY(s_i)\big)\,p_i. Distribute p_i across the sum inside each term, then split the single sum into two sums, since addition of finitely many numbers can always be regrouped this way: \sum_{i=1}^{n} \big(aX(s_i)p_i + bY(s_i)p_i\big) = a\sum_{i=1}^{n} X(s_i)p_i + b\sum_{i=1}^{n} Y(s_i)p_i. The two resulting sums are exactly E(X) and E(Y) by definition, so E(aX+bY) = a\,E(X) + b\,E(Y). Nowhere did this argument use P(X=x, Y=y) = P(X=x)P(Y=y) — the independence condition — which is exactly why the result holds regardless of whether X and Y are independent.

Let \mu_X = E(X), \mu_Y = E(Y). Expand the squared deviation of the sum: \operatorname{Var}(X+Y) = E\big[((X-\mu_X)+(Y-\mu_Y))^2\big] = E\big[(X-\mu_X)^2\big] + E\big[(Y-\mu_Y)^2\big] + 2E\big[(X-\mu_X)(Y-\mu_Y)\big]. The first two terms are \operatorname{Var}(X) and \operatorname{Var}(Y) directly. The cross term is the covariance of X and Y; independence makes E[(X-\mu_X)(Y-\mu_Y)] = E(X-\mu_X)\,E(Y-\mu_Y) = 0 \cdot 0 = 0 (the expectation of a product of independent quantities is the product of their expectations, and each factor's own expectation is zero by linearity). With the cross term gone, \operatorname{Var}(X+Y) = \operatorname{Var}(X) + \operatorname{Var}(Y) exactly. Without independence, that cross term need not vanish, which is why this result — unlike linearity of expectation — genuinely needs the hypothesis.

Let Y=(X-\mu)^2, a nonnegative random variable with E(Y)=\operatorname{Var}(X)=\sigma^2. Markov's inequality (a bound for any nonnegative random variable, P(Y\ge a)\le E(Y)/a) applied with a=k^2\sigma^2 gives P\big((X-\mu)^2\ge k^2\sigma^2\big) \le \frac{\sigma^2}{k^2\sigma^2} = \frac{1}{k^2}. The event (X-\mu)^2\ge k^2\sigma^2 is exactly the event |X-\mu|\ge k\sigma, so the bound transfers directly.

\bar X_n has mean \mu and, since the X_i are independent, variance \sigma^2/n (chapter 10's own sum-of-independent-variables rule, applied n times). Applying Chebyshev's inequality to \bar X_n with k=\varepsilon\sqrt n/\sigma gives P\big(|\bar X_n-\mu|\ge\varepsilon\big) \le \frac{\sigma^2}{n\varepsilon^2}. The right side shrinks to 0 as n\to\infty, for any fixed \varepsilon>0, which is exactly the convergence the law claims.

Each of the n observations in a sample is an independent draw with variance \sigma^2. The sample mean \bar x = \frac{1}{n}\sum x_i rescales that sum by 1/n, and variance scales by the square of a constant multiplier, so \operatorname{Var}(\bar x) = \operatorname{Var}\left(\frac{1}{n}\sum x_i\right) = \frac{1}{n^2}\sum \operatorname{Var}(x_i) = \frac{n\sigma^2}{n^2} = \frac{\sigma^2}{n}. Taking a square root gives the standard deviation of \bar x, which is exactly what "standard error" names: SE = \sigma/\sqrt n.

A full proof needs moment generating functions or characteristic functions, beyond this course's own scope. The intuition: \bar X_n is itself a sum of n independent pieces (each X_i/n), and summing many independent pieces smooths out any one piece's own irregular shape -- the same mechanism this course's own sums-of-independent-variables material already builds toward, pushed to its limit as n grows without bound.

Sampling with replacement draws n genuinely independent observations, giving \operatorname{Var}(\bar X)=\sigma^2/n directly. Sampling without replacement introduces a small NEGATIVE covariance between any two draws (choosing one unit makes every other unit slightly more likely among the remaining ones), which shrinks the sum's own variance below the independent case by exactly the factor (N-n)/(N-1) -- a standard finite-population covariance calculation. Taking a square root carries that same factor, as a square root, into the standard error.

Let X_i=1 if the i-th draw has the property of interest, X_i=0 otherwise. Each X_i is Bernoulli(p), with mean p and variance p(1-p). The sample proportion \hat p=\frac{1}{n}\sum X_i is exactly the sample MEAN of these n indicators, so every result already established for the sampling distribution of a mean -- its own mean p, its own standard error \sqrt{p(1-p)/n}, and its own approximate normality for large n -- transfers directly, with no new machinery required.

A full proof needs moment generating functions or characteristic functions, beyond this course's own scope. The intuition: \bar X_n is itself a sum of n independent pieces (each X_i/n), and summing many independent pieces smooths out any one piece's own irregular shape -- the same mechanism this course's own sums-of-independent-variables material already builds toward, pushed to its limit as n grows without bound.

The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.

It is easier to compute the COMPLEMENT, no collision at all. The first person's birthday can be anything (365/365). The second must avoid the first's day (364/365). The third must avoid both earlier days (363/365), and so on, down to the n-th person avoiding n-1 already-taken days ((365-n+1)/365). Multiplying these n independent fractions gives the no-collision probability; subtracting from 1 gives the stated formula.

Conditioning on the first round's outcome gives a recurrence, P_i = p\,P_{i+1} + q\,P_{i-1}, with boundary conditions P_0=0 and P_N=1. For p=0.5 this recurrence forces P_i to be linear in i, giving P_i=i/N directly from the boundary conditions. For p\ne0.5, solving the same recurrence (a standard linear difference equation) produces the ratio-of-powers form stated above, which reduces to the p=0.5 case as a limit when q/p \to 1.

Conditioning on the first round's outcome gives a recurrence, P_i = p\,P_{i+1} + q\,P_{i-1}, with boundary conditions P_0=0 and P_N=1. For p=0.5 this recurrence forces P_i to be linear in i, giving P_i=i/N directly from the boundary conditions. For p\ne0.5, solving the same recurrence (a standard linear difference equation) produces the ratio-of-powers form stated above, which reduces to the p=0.5 case as a limit when q/p \to 1.

Series: the system is up only if EVERY component is up, and independence lets the individual probabilities multiply directly, p\cdot p\cdots p = p^n. Parallel: the system is down only if EVERY component is down, an event with probability (1-p)^n by the same independence argument, so the system is up with the complementary probability. k-of-n generalizes both: the number of working components is Binomial(n,p), and the system is up exactly when that count is at least k, which is the binomial tail sum shown. Setting k=n recovers series, and k=1 recovers parallel.

\rho is the fraction of time the server is busy, arrivals must be served at least as fast as they show up on average, so \rho\ge1 makes the queue grow without bound. Modeling the number in the system as a birth-death Markov chain with constant birth rate \lambda and death rate \mu gives a geometric stationary distribution with ratio \rho, whose mean is L=\rho/(1-\rho). Little's law, L=\lambda W, then gives W = L/\lambda = 1/(\mu-\lambda) directly.

The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.

Let X_i=1 if the i-th draw has the property of interest, X_i=0 otherwise. Each X_i is Bernoulli(p), with mean p and variance p(1-p). The sample proportion \hat p=\frac{1}{n}\sum X_i is exactly the sample MEAN of these n indicators, so every result already established for the sampling distribution of a mean -- its own mean p, its own standard error \sqrt{p(1-p)/n}, and its own approximate normality for large n -- transfers directly, with no new machinery required.

\bar X_n has mean \mu and, since the X_i are independent, variance \sigma^2/n (chapter 10's own sum-of-independent-variables rule, applied n times). Applying Chebyshev's inequality to \bar X_n with k=\varepsilon\sqrt n/\sigma gives P\big(|\bar X_n-\mu|\ge\varepsilon\big) \le \frac{\sigma^2}{n\varepsilon^2}. The right side shrinks to 0 as n\to\infty, for any fixed \varepsilon>0, which is exactly the convergence the law claims.