LeoMath

Foundations of probability · Section 3 of 3

Random variables

Turning outcomes into numbers; the Poisson law as a limit of binomials.

about 20 min

Start from a problem

Problem

A call centre has 1000 customers. Each of them calls within a given hour with probability 0.3%, independently of the others. How many calls arrive in that hour? The number is random, of course; the real question is what the probability of 0,1,2,… calls is. With only 5 lines open, how likely is it that they are not enough?

Doing it honestly involves numbers like (1000k), frighteningly large. Yet people noticed long ago that whenever you count how often a rare event happens (misprints on a page, calls in an hour, photons hitting a detector in a second), the distribution has nearly the same shape, and it depends only on the average count. Why?

To answer that, we first have to turn "the outcome of an experiment" into "a number". That is what a random variable does.

Observe

Play first, read later. The bars show how many of n independent trials succeed, each with probability λ/n; the dots show another distribution that depends only on the average count λ. Keep λ=3 and drag n from 10 to 1000. How do the bars and dots end up related? Then press "Sample": the row of cells in the middle is the complete outcome of one run, and the number of red cells is the number counted in that run.

Interactive experimentFrom binomial to Poisson
  • binomial B(n, p)(nk)pk(1−p)n−k
  • Poisson(λ)e−λλkk!
samples 0sample mean —theoretical mean λ 3.0
Try
success probability p = λ/n 0.3most likely value 3 (n+1)p = 3.3
d=12∑k|P(X=k)−P(Y=k)|distance d between them 0.086bound λ²/n 0.90

Peak analysis idea from: github.com/huzhuofan1020-svg/EXFB

Counting simulation idea from: github.com/huzhuofan1020-svg/PoissonDist

What did you observe?Play first, then answer. Read the explanation only after you have thought it through.

  1. 1.Keep λ = 3 and set n to 10, then 100, then 1000. How do the bars and dots come together? By what factor does the distance d shrink each time?
  2. 2.Fix n = 20 and compare λ = 1 with λ = 10. The n is the same; why is one approximation good and the other poor?
  3. 3.Press “tied peak” (n = 9, λ = 4.5). How many bars are tallest? In general, where is the most likely value?
Conjecture

The larger n and the smaller the success probability p=λ/n, the closer the bars come to the dots, until only λ seems to matter; the plot below them suggests the gap shrinks roughly like 1/n. The dots follow e−λλk/k!, which suggests

(nk)(λn)k(1−λn)n−k ⟶ e−λλkk!(n→∞).

Before we can say what it means for one distribution to approach another, we must say what "a number" and "a distribution" are.

Definitions

Definition 3.1Random variable

Let (Ω,P) be a probability space. A function X:Ω→ℝ is called a random variable. If X takes only finitely or countably many values, it is discrete.

A random variable is neither random nor a variable: it is a perfectly definite function, and all the randomness lives in the outcome ω. In the experiment, the row of cells is one outcome ω (each of the n trials a success or a failure), and X(ω) is the number of red cells. For every real x, {X=x}={ω∈Ω: X(ω)=x} is an event, so we may ask for its probability.

Definition 3.2Probability mass function

The probability mass function of a discrete random variable X is the function x↦P(X=x), where x ranges over the possible values of X.

Its values are non-negative and add up to 1: the events {X=x} for different x are pairwise disjoint and together make up Ω, so countable additivity gives ∑xP(X=x)=P(Ω)=1. Conversely, as long as we only ask about probabilities involving X, the mass function is all we use; what Ω looks like no longer matters. That is why two distributions can be compared on their own, away from any particular experiment, and the experiment compares exactly two mass functions.

To write down the distribution of a number of successes, we extend independence from two events to many: A1,…,An are mutually independent if for every choice of some of them, the probability that all the chosen ones occur equals the product of their probabilities.

Definition 3.3Binomial distribution

Run n trials whose successes are mutually independent, each succeeding with probability p. The number of successes X has the binomial distribution, written X∼B(n,p).

Proposition 3.1The binomial mass function

If X∼B(n,p), then

P(X=k)=(nk)pk(1−p)n−k,k=0,1,…,n.
Proof

Take one particular outcome: successes exactly at trials i1,…,ik and failures at the other n−k. By independence (replacing some independent events by their complements keeps them independent), its probability is pk(1−p)n−k, whichever trials the successes fall on. Different outcomes are disjoint, and there are (nk) ways to choose which k trials succeed; add them up. By the binomial theorem ∑k(nk)pk(1−p)n−k=(p+1−p)n=1, which is where the name comes from.

Where is the tallest bar? Compare neighbouring terms.

Proposition 3.2The most likely value

Let 0<p<1 and X∼B(n,p). Then P(X=k) is largest at k=⌊(n+1)p⌋; if (n+1)p is a whole number, k=(n+1)p and k=(n+1)p−1 are tied for the maximum.

Proof

For 1≤k≤n, since (nk)/(nk−1)=n−k+1k,

P(X=k)P(X=k−1)=(n−k+1)pk(1−p).

The ratio exceeds 1 exactly when (n−k+1)p>k(1−p), that is, when k<(n+1)p. So the mass function rises while k<(n+1)p, falls once k>(n+1)p, and two neighbours are equal where k=(n+1)p. Write m=(n+1)p∈(0,n+1). If m is not a whole number, the peak is at ⌊m⌋; if it is, then 1≤m≤n and m−1 and m share the peak.

Since (n+1)p=np+p, the most likely value is within 1 of np, but it need not equal np; indeed np need not be a whole number, while X only takes whole values. The small triangle in the experiment marks (n+1)p, and "tied peak" shows two equally tall bars.

Definition 3.4Poisson distribution

Let λ>0. A random variable Y with values 0,1,2,… and

P(Y=k)=e−λλkk!,k=0,1,2,…,

has the Poisson distribution with parameter λ, written Y∼Poisson(λ).

It is a genuine mass function: by the Taylor expansion of eλ, ∑k≥0e−λλkk!=e−λeλ=1. Comparing neighbours again, P(Y=k)/P(Y=k−1)=λ/k, so the peak is at ⌊λ⌋, shared by λ−1 and λ when λ is a whole number.

Theorems and proofs

Theorem 3.3Poisson limit theorem

Let λ>0 and pn=λ/n (for n≥λ). For each fixed k=0,1,2,…,

limn→∞⁡(nk)pnk(1−pn)n−k=e−λλkk!.
Proof

Split the expression into three factors:

(nk)(λn)k(1−λn)n−k=λkk!⋅∏j=0k−1(1−jn)⋅(1−λn)n(1−λn)−k,

using (nk)1nk=1k!⋅n(n−1)⋯(n−k+1)nk. With k fixed the product has only k factors, each tending to 1, so it tends to 1; likewise (1−λ/n)−k→1. Take the logarithm of what remains:

ln⁡(1−λn)n=−λ⋅ln⁡(1−λ/n)−λ/n ⟶ −λ,

because ln⁡(1+x)x→1 as x→0, which is just the derivative of ln⁡ at 1. Since ex is continuous, (1−λ/n)n→e−λ. Multiplying the three limits gives the result.

Every step uses "k fixed": if k grew with n, ∏(1−j/n) need not tend to 1. So the theorem says that each bar converges separately. The d below the experiment measures the gap between the whole mass functions, and there is a stronger, more useful version for it.

Remark

The quantity in the experiment,

d=12∑k|P(X=k)−P(Y=k)|,

is the total variation distance between the two distributions. One can show that it equals the largest possible difference between P(X∈A) and P(Y∈A) over all sets A. In other words, if you answer any question about the count with the Poisson law instead of the binomial one, you are off by at most d. In 1960 Le Cam proved

d≤np2=λ2n,

and the trials need not share one success probability: with probabilities pi, still d≤∑ipi2. On the log–log plot this bound is a line of slope −1 (the dashed line in the experiment), and the true d runs parallel to it: ten times as many trials, a tenth of the error.

Common mistake

Large n alone is not enough; p must be small. Keep n=20: with λ=1 (p=0.05) the distance is about 0.014, with λ=10 (p=0.5) about 0.17. B(20,12) can never exceed 20 and is much narrower than Poisson(10). The next section shows that the binomial variance is np(1−p) and the Poisson variance is λ=np: they differ by the factor 1−p. The Poisson approximation is about rare events: each unlikely on its own, but with many chances.

Common mistake

Same distribution does not mean equal. Toss a fair coin 10 times. The number of heads X and the number of tails 10−X both follow B(10,12), exactly the same distribution, yet unless the split is exactly 5 to 5 they are never equal. A distribution records the probability of each value, not which ω produced it. Likewise X=3 is not a number but an event, {ω:X(ω)=3}.

Applications

ApplicationBack to the start: how many lines

The number of calls is X∼B(1000,0.003), with λ=np=3. With the Poisson law,

P(X≥6)=1−∑k=05e−33kk!≈0.084,

against the exact 0.0836. With only 5 lines, roughly one hour in twelve runs short; with 7, P(X≥8)≈0.012, about one hour in eighty. Neither 1000 nor 0.003 appears in the calculation, only their product 3: double the customers and halve each one's chance of calling, and the answer barely moves.

ApplicationThe birthday problem once more

n people form (n2) pairs, and each pair shares a birthday with probability 1365. The number of pairs that share is a count of many rare events, approximately Poisson(λ) with λ=(n2)/365. Hence

P(no shared birthday)≈e−λ=exp⁡(−n(n−1)730),

exactly the exponential that the probability spaces section obtained from 1−x≤e−x. At n=23, λ=253365≈0.693≈ln⁡2: the approximation gives 0.500, the exact value is 0.493. The pairs are not quite independent (if A and B share a day and B and C do, then so do A and C), but the dependence is weak. "The number of many nearly independent rare events is approximately Poisson" is a principle far wider than this section's theorem.

ApplicationMissed photons: total probability as a sum over a distribution

The number of photons reaching a detector in one second is N∼Poisson(λ), and each photon is recorded with probability q, independently. What is the distribution of the number recorded, M? Split by the value of N. This is the law of total probability, with the sum now running over a distribution:

P(M=m)=∑n≥m(nm)qm(1−q)n−m⋅e−λλnn!=e−λ(λq)mm!∑j≥0(λ(1−q))jj!=e−λq(λq)mm!.

(The second step puts j=n−m.) So M∼Poisson(λq): losing a random share of a Poisson count leaves a Poisson count with a discounted mean. Asking the reverse question with Bayes' theorem, "given m recorded, how many arrived?", gives P(N=n|M=m)=e−λ(1−q)(λ(1−q))n−m(n−m)!: the number missed, N−m, is Poisson(λ(1−q)) whatever m is.

Try it in the plotter →

In the plotter, draw (1−3/x)x and the constant exp⁡(−3)≈0.0498. At x=10 the first is only 0.028, at x=100 it is 0.0476, at x=1000 it is 0.0496: the key step in the proof of the Poisson limit theorem is this curve approaching this horizontal line.

Further: waiting times and densities

The same idea answers another question: how long until the next call? Let calls arrive at an average rate of λ per hour. Cut [0,t] into n short pieces; each contains a call with probability about λt/n, so by the Poisson limit theorem the number of calls in [0,t] is approximately Poisson(λt). The waiting time T exceeds t exactly when no call arrives in [0,t]:

P(T>t)=e−λt,t≥0.

T can be any real number in [0,∞), and P(T=t)=0 for every particular t, so a mass function is useless here. We need another description.

Definition 3.5Distribution function and density

The distribution function of a random variable X is F(x)=P(X≤x). If there is a non-negative function f such that for every real x

F(x)=∫−∞xf(t)dt,

then X is called continuous and f is its probability density.

Then P(a<X≤b)=F(b)−F(a)=∫abf(t)dt: probability is area under the density curve. Where f is continuous, the fundamental theorem of calculus gives F′(x)=f(x). The waiting time has distribution function F(t)=1−e−λt; differentiating gives the density f(t)=λe−λt for t≥0, the exponential distribution. A density is not a probability and can exceed 1; it is f(x)Δx that approximates the probability of landing in (x,x+Δx]. Draw aexp⁡(−ax) in the plotter and drag the parameter a: the larger a, the taller and narrower the curve, and the area under it is always 1. The p(w|D) in the previous section's Bayesian neural networks is a density of exactly this kind.

Remark

The probability spaces section assumed Ω finite or countable, where every subset can be an event. A random variable with continuous values such as T needs an uncountable Ω, and then not every subset can sensibly be given a probability: P is defined only on a large enough family of sets, one that contains all intervals. The rigorous treatment is measure theory, which this path does not go into; this section only needs probabilities of intervals, where the issue never arises.

Remark

The binomial peak sits near np, the Poisson peak near λ. The precise version of this "centre" is the mean, and of the "width" the variance: the subject of the next section, mean and variance (in progress). There we will also see that the covariance of two random variables is an inner product, so the Cauchy–Schwarz inequality gives |ρ|≤1 at once.

Binomial peak analysis idea from: github.com/huzhuofan1020-svg/EXFB

Poisson counting simulation idea from: github.com/huzhuofan1020-svg/PoissonDist

Exercises

0 of 4 done

1
Toss a fair coin 10 times. What is the probability of exactly 3 heads? (Four decimals, or a fraction.)

Decimals or fractions; anything within 0.00006 of the answer counts as correct.

2
A book has 500 pages and 250 misprints, each landing independently on a page chosen uniformly at random. Using the Poisson approximation, find the probability that a given page has no misprints. (Three decimals.)

Decimals or fractions; anything within 0.0006 of the answer counts as correct.

3
Let X∼B(11,12). Which value is X most likely to take?
Answer to exercise 3
4
B(10,0.5) and B(1000,0.005) both have mean 5. Which is closer to Poisson(5)?
Answer to exercise 4

Discussion

Found a mistake, have a question or a suggestion? You can also write to 620026600@qq.com

No comments yet. Share your understanding, ask a question, or point out an error on this page.

Log in to join the discussion