An Adventure in Coin Flipping

Ying Nian Wu UCLA Department of Statistics Fall 2008

For all its simplicity, a study of coin flipping reveals many of the deep results and useful intuitions in probability theory. In particular, we shall see the following things in our adventure in coin flipping:

(1) Weak and strong laws of large number.

(2) Central limit theorem.

(3) Large deviation.

(4) Probability distributions: Bernoulli, Binomial, Poisson, Normal and Exponential.

(5) Expectation and variance.

(6) Stochastic processes: random walk, Brownian motion, Poisson process.

(7) Coding and complexity: entropy, Kullback-Leibler divergence, equipartition.

The emphasis is on how to think about various concepts. Of course, we are also going to do some calculations.

1 Sample space and events

Suppose we flip a coin n times. Let Ω be the set of all possible sequences. Ω is called sample space. |Ω| = 2^{n}, where |Ω| denotes the number of elements in Ω.

An event is a statement about the outcome. The event is represented by the subset of all the outcomes that satisfy this statement. For instance, let A be the event that the number of heads is k, where k is an integer from 0 to n. Then A is the set of all the sequences that have k heads.

2 Random variables

For each sequence ω ∈ Ω, we can represent it by a sequence of 0s and 1s, Z_{1}(ω), ..., Z_{n}(ω), where Z_{i}(ω) = 1 if the i-th flip of ω is head, and Z_{i}(ω) = 0 otherwise. Let X(ω) be the number of heads in sequence ω. Then X(ω) = Z_{1}(ω) + ... + Z_{n}(ω).

For a random sequence ω, the corresponding Z_{i}(ω) is a binary random number for each i, and X(ω) is a random number whose value is between 0 and n. We call Z_{i} and X random variables.

The random variables are actually functions. For example, the random variable X is a function that maps Ω to a set of numbers {0, 1, ..., n}, so that each outcome ω is labeled by a number X(ω) ∈ {0, 1, ..., n}.

Let A be the event that the number of heads is k, then A = {ω : X(ω) = k}, i.e., the set of all the sequences whose numbers of heads are exactly k. In general, an event can be expressed as an equation or an inequality in terms of the random variables. So the introduction of random variables is mostly a matter of language. Instead of using English, we use equations and inequalities to describe the outcome.

3 Equally likely setting

If the coin is fair and the flips are independent, then all the 2^{n} sequences in Ω are equally likely. So we can imagine that instead of flip the fair coin independently n times to get the sequence, we simply randomly pick a sequence from the population of these 2^{n} sequences.

4 Number of heads

Now let us study the random variable X, which is the number of heads if we flip the fair coin n times independently. We want to calculate P (X = k) for k = 0, 1, ..., n.

Based on the consideration in Section 3, we only need to know how many sequences have exactly k heads. Let A_{k} be the set of sequences with k heads. Then P (X = K) = P (A_{k}) = |A_{k}|/|Ω| = |A_{k}|/2^{n}, where |A_{k}| is the size of A_{k}, i.e., the number of sequences in A_{k}.

5 Population and classes

We can imagine that Ω is a population, which can be partitioned into n + 1 classes, A_{0}, A_{1}, ..., A_{n}. All the members in the same class share the same number of heads, i.e., if ω ∈ A_{k}, then X(ω) = k.

6 The size of a class

Now we want to measure the size of A_{k}. We can show that |A_{k}| = \binom{n}{k}.

The reason is as follows. In order to produce a sequence with k heads, we only need to choose k flips from the total of n flips, and let these k flips be heads, and the rest of the n − k flips be tails. The number of different ways of choosing k flips from the n flips is \binom{n}{k}, and this is the number of sequences in A.

\binom{n}{k} is given by

\binom{n}{k} = \frac{n!}{k!(n − k)!}.

7 How large is \binom{n}{k}

For large n, we want to have a simpler expression for |A_{k}| = \binom{n}{k}. In order to do that, we need the Stirling formula, which says that

n! ∼ \sqrt{2πn}n^{n}e^{−n}.

The meaning of this formula is that the ratio between the left hand side and the right hand side goes to 1 as n goes to infinity.

Let α = k/n, which is the frequency of heads, then for large n,

\binom{n}{k} = \frac{n!}{(nα)!(n(1 − α))!}
∼ \frac{\sqrt{2πn}n^{n}e^{−n}}{[\sqrt{2πnα}(nα)^{nα}e^{−nα}][\sqrt{2πn(1 − α)}(n(1 − α))^{n(1−α)}e^{−n(1−α)}]}
= \frac{1}{\sqrt{2πnα(1 − α)}α^{nα}(1 − α)^{n(1−α)}}
= C(n, α)2^{nh(α)},

where

C(n, α) = \frac{1}{\sqrt{2πnα(1 − α)}},

h(α) = −[α log_{2} α + (1 − α) log_{2}(1 − α)].

We write the above result as \binom{n}{k} ∼ C(n, α)2^{nh(α)}, meaning that the ratio between the left hand side the the right hand side goes to 1 as n goes to infinity. In taking the limit, we hold α fixed.

8 Entropy function

The function h(α) is a measure of entropy. Later we will make this clear. But for now, we only need to see what this function looks like.

h(α) is defined for α ∈ (0, 1). h′(α) = − log α + log(1 − α), and h′′(α) = −1/α − 1/(1 − α) < 0. So h(α) is a concave function, and it achieves its maximum at α = 1/2, where h(1/2) = 1, and h′(1/2) = 0.

9 Class sizes for large n

The results in Sections 7 and 45 have deep implications. If α is away from 1/2, say, |α − 1/2| > ϵ for ϵ > 0, then the size of the class A_{k} or A_{nα}, which is \binom{n}{k} ∼ C(n, α)2^{nh(α)}, will becomes smaller and smaller relative to the size of the whole population |Ω| = 2^{n}. In other words, the proportion of the class A_{nα}, which is C(n, α)2^{nh(α)}/2^{n}, goes to 0 at an exponential rate.

Because of the shape of the entropy function h(α), if |α − 1/2| > ϵ, then h(α) < h(1/2 + ϵ) = h(1/2 − ϵ) = r < 1. So the size of class A_{nα} is smaller than C(n, α)2^{nr}, and the proportion of class A_{nα} is smaller than C(n, α)2^{−n(1−r)}, which is exponentially small.

10 Sum of exponentials

Even if we put together all those classes A_{k} with |k/n − 1/2| > ϵ, their total size is still just something like C2^{−n(1−r)}, where C is a number that changes slowly compared to the exponential term.

To see this fact, consider a simpler example. Suppose we have one term 2^{−.5n}, and we have another term 2^{−.3n}. If we put them together, the sum behaves like 2^{−.3n}, because 2^{−.5n} is negligibly small compared to 2^{−.3n} when n is large. That is, if we sum up a limited number of terms that goes to 0 exponentially fast, the sum behaves like the largest term.

So the total proportion of those classes A_{k} with |k/n − 1/2| > ϵ goes to 0 at an exponential rate. Or in other words, the total proportion of those classes A_{k} with |k/n − 1/2| ≤ ϵ goes to 1, no matter how small ϵ is.

So as far as frequency of heads is concerned, 1/2 is the typical value, in the sense that nearly all of the 2^{n} sequences share this value (with small deviations no more than ϵ).

11 Weak law of large number

Let A = {ω : |X(ω)/n − 1/2| > ϵ}. Then A is the union of those classes A_{k} with |k/n − 1/2| > ϵ, and |A|/|Ω| goes to 0 at an exponential rate.

Translating this into probability, P (A) = |A|/|Ω| goes to 0, i.e.,

P (|\frac{X}{n} − \frac{1}{2}| > ϵ) → 0.

This is the so called weak law of large number. It says that if we flip a fair coin a large number of times, then the frequency of heads is close to 1/2.

12 Large deviation

More precisely, because the proportion of A is C2^{−n(1−r)} according to Section 9,

\frac{1}{n} log_{2} P (|\frac{X}{n} − \frac{1}{2}| > ϵ) → −(1 − r) < 0.

Such a result is called a large deviation result, because if |X/n − 1/2| > ϵ, |X − n/2| > ϵn, i.e., we look at those sequences ω whose number of heads X(ω) deviates from n/2 by at least ϵn. No matter how small ϵ is, as we increase n, this deviation will become large.

13 Population histogram, probability distribution, and tail probability

For all the 2^{n} numbers {X(ω), ω ∈ Ω}, we can make a histogram with bins 0, 1, ..., n, where bin k collects those ω whose X(ω) = k. We can imagine each ω is a small ball. Then the hight of the pile of balls in the k-th bin is proportional to \binom{n}{k}/2^{n}.

This population histogram is also the probability distribution of the random variable X, which is a random sample from the 2^{n} numbers {X(ω), ω ∈ Ω}.

The center of this distribution is n/2. The large deviation result is about the tails of this distribution, i.e., what is the probability that X deviates from its center n/2 by at least ϵn?

14 Small deviation

The large deviation result tells us about the probability that X deviates from n/2 by at least ϵn. For large n, this probability is extremely small, so the whole bulk of the histogram of {X(ω), ω ∈ Ω} lies within this deviation. We want to zoom in to study smaller deviation.

Let k = n/2 + z\sqrt{n}/2, or z = (k − n/2)/(\sqrt{n}/2), let us calculate P (X = k) = g(z). Here the deviation is proportional to \sqrt{n} instead of n.

First, we calculate p(0) = P (X = n/2). Using the fact that \binom{n}{nα} ∼ C(n, α)2^{nh(α)} that we derived in Section 7, we have

g(0) ∼ \frac{1}{\sqrt{2π}} \frac{2}{\sqrt{n}}.

Next, we calculate g(z)/g(0). Let d = z\sqrt{n}/2 be the deviation,

\frac{g(z)}{g(0)} = \binom{n}{n/2 + d}/\binom{n}{n/2}
= \frac{(n/2)!(n/2)!}{(n/2 + d)!(n/2 − d)!}
= \frac{n/2(n/2 − 1)...(n/2 − d + 1)}{(n/2 + 1)(n/2 + 2)...(n/2 + d)}
= \frac{(1 − Δ)(1 − 2Δ)...(1 − (d − 1)Δ)}{(1 + Δ)(1 + 2Δ)...(1 + dΔ)}

where Δ = 2/n.

15 1 + δ ≈ e^{δ}

According to Taylor expansion, e^{δ} = 1 + δ + O(δ^{2}), we can simply write 1 + δ as e^{δ} in calculating the limit, thus

\frac{g(z)}{g(0)} ≈ exp\{− ∑_{i=1}^{d−1}(iΔ) − ∑_{i=1}^{d}(iΔ)\}
= exp{−Δ[(d(d − 1))/2 + (d(d + 1))/2]} = e^{−z^{2}/2}.

In the limit, the ≈ sign becomes = sign. So for any z, we have

g(z) ∼ \frac{1}{\sqrt{2π}} e^{−z^{2}/2} \frac{2}{\sqrt{n}}.

16 From sum to integral

This approximation can be quite useful for calculating some probabilities. For example, if we flip a fair coin 100 times, what is the probability that the number of heads is between 40 and 60, or what is the probability that the number of heads is greater than 60? In general, suppose we want to compute P (a ≤ X ≤ b), where a and b are two integers, we need to calculate the sum

P (a ≤ X ≤ b) = ∑_{k=a}^{b} P (X = k) = ∑_{k=a}^{b} \binom{n}{k}/2^{n},

which can be quite difficult to calculate. But if we use the limiting result in Section 15, we can calculate

P (a ≤ X ≤ b) ∼ ∑_{k=a}^{b} g(z) = ∑_{k=a}^{b} \frac{1}{\sqrt{2π}} e^{−z^{2}/2} \frac{2}{\sqrt{n}},

where z = (k − n/2)/(\sqrt{n}/2). When k runs from a to b, z runs from a′ to b′, where a′ = (a − n/2)/(\sqrt{n}/2) and b′ = (b − n/2)/(\sqrt{n}/2), and every two consecutive values of z are apart by 2/\sqrt{n}. Therefore, as n → ∞,

P (a ≤ X ≤ b) → ∫_{a′}^{b′} \frac{1}{\sqrt{2π}} e^{−z^{2}/2}dz.

Let Z = (X − n/2)/(\sqrt{n}/2), that means

P (a ≤ X ≤ b) = P (a′ ≤ Z ≤ b′) → ∫_{a′}^{b′} \frac{1}{\sqrt{2π}} e^{−z^{2}/2}dz.

Although Z is discrete, for large n, we may treat Z as a continuous random variable, whose probability density function f(z) = \frac{1}{\sqrt{2π}} e^{−z^{2}/2}. This distribution is called normal distribution or Gaussian distribution.

17 Continuous distribution: sampling from area under curve

A very intuitive way to understand the probability density function f(z) = \frac{1}{\sqrt{2π}} e^{−z^{2}/2} is through the following thought experiment. We call the area under the curve f(z) the area S. We randomly throw a point into S, and then we return the horizontal coordinate of this random point. This coordinate is a realization of Z. Clearly, the higher the f(z) is, the more likely that Z is around z.

18 Continuous distribution: histogram of a population

To understand f(z), we can also consider the population of Z-score, \{Z(ω) = (X(ω)−n/2)/(\sqrt{n}/2), ω ∈ Ω}, that is, for each sequence ω, we can calculate its Z-score. So we have 2^{n} scores. We may consider plotting a histogram of these scores, so that the area of each bin is the proportion of the scores that fall into this bin. If we let n → ∞, and at the same time, let the bin size goes to 0, then the tops of the bins form a continuous curve, and this curve is f(z).

19 Continuous distribution: population density

For a small interval around z, say, [z, z + Δz], we can count the number of those Z(ω) that live in this neighborhood [z, z + Δz]. Let this number be n(z), then the population density is n(z)/Δz, that is, the number of people divided by the size of the neighborhood. It tells us how densely a local neighborhood is populated. For example, the density of Los Angeles is much greater than the density of Alaska.

It is better that we normalize the size of the population N = 2^{n}, that is, we use [n(z)/N]/Δ as the measure of density. As Δz → 0, it becomes the density curve f(z).

If we randomly sample Z from the population {Z(ω)}, then the population proportion n(z)/N becomes the probability P (Z ∈ [z, z + Δz]), and f(z) = P (Z ∈ [z, z + Δz])/Δz is the probability density. We use the notation Z ∼ f(z) to denote that Z is sampled from f(z).

20 Central limit theorem

The fact that the limiting distribution of Z = (X −n/2)/(\sqrt{n}/2) is a Gaussian distribution is called the central limit theorem.

One may wonder why we have k = n/2 + z\sqrt{n}/2 in our study of the central limit theorem? Why \sqrt{n}/2? Why not n^{1/3}? Why not \sqrt{n}/3? This is because \sqrt{n}/2 is the average deviation or standard deviation.

21 Expectation

For the population {X(ω), ω ∈ Ω}. If we randomly sample an ω from Ω, then X(ω) is a random number. Let us define

μ = E[X] = ⟨X⟩ = \frac{1}{N} ∑_{ω=1}^{N} X(ω),

where N = 2^{n} is the size of the population, and we label the sequences ω from 1 to N.

We can interpret the expectation as the population average, or as the center of the fluctuation of the random variable X. E[X] is also the center of the histogram of {X(ω), ω ∈ Ω}.

22 Variance

Let us also define

σ^{2} = Var[X] = E[(X − μ)^{2}] = \frac{1}{N} ∑_{ω=1}^{N}(X(ω) − μ)^{2},

which is another population average. But it is not the average of X(ω), but the average of the squared deviation (X(ω) − μ)^{2}. We call this average the variance. It can be interpreted as the population variance, or the magnitude of the fluctuation of the random variable X. It measures the spread of the histogram of {X(ω), ω ∈ Ω}.

Note that the variance is defined as average squared deviation. So its unit is the square of the unit of X. The square root of the variance, σ, is in the same unit as X, and is called standard deviation.

23 Expectation and variance in coin flipping

We shall show that E[X] = n/2 and Var[X] = n/4, then the standard deviation is σ = \sqrt{n}/2, which is the average deviation. That is why we let k = n/2 − z\sqrt{n}/2, that is, we measure the deviation of k from n/2 in terms of the average deviation \sqrt{n}/2.

The results that E[X] = n/2 and Var[X] = n/4 follow from the recursive relationship: μ_{n+1} = μ_{n} + 1/2, and σ_{n+1}^{2} = σ_{n}^{2} + 1/4, where μ_{n} and σ_{n}^{2} are the expectation and variance of X in n flips.

The proof of the recursive relationship is simple. For each ω of n flips, the next flip can either be 1 or 0. That is, each ω spawns two sequences (ω, 0) and (ω, 1). So each X(ω) spawns two numbers X(ω) and X(ω) + 1. Therefore,

μ_{n+1} = \frac{1}{2N} ∑_{ω=1}^{N}[X(ω) + (X(ω) + 1)]

= \frac{1}{N} ∑_{ω=1}^{N} X(ω) + 1/2 = μ_{n} + 1/2.

σ_{n+1}^{2} = \frac{1}{2N} ∑_{ω=1}^{N}[(X(ω) − (μ_{n} + 1/2)]^{2} + [(X(ω) + 1) − (μ_{n} + 1/2)]^{2}

= \frac{1}{N} ∑_{ω=1}^{N}[X(ω) − μ_{n}]^{2} + 1/4 = σ_{n}^{2} + 1/4.

24 Law of large number reaffirmed

An important implication is that E[X/n] = 1/2, and Var[X/n] = 1/4n → 0. That is, the frequency of heads X/n fluctuates around 1/2, but the magnitude of fluctuation diminishes as n → 0. This reaffirms the weak law of large number.

25 Quincunx

Figure 1 displays a device called quincunx. The small balls go through such a device and end up in one of the bins at the bottom. At each step, the small ball makes either a left turn or a right turn. Suppose the ball goes through n steps. If we number the locations at which the ball exists the quincunx as 0, 1, 2, ..., n, from left to right. Let X be the exit location of a ball. Then X is the number of heads if we flip a fair coin n times. So this device is essentially the same as coin flipping. For each exit location k, we count the number of paths that end up in k, and this number is \binom{n}{k}. We can also calculate this number using Pascal triangle, where each number is the sum of the two numbers on its shoulder.

If we drop a large number of balls into these bins through the quincunx, then according to the central limit theorem, the balls in these bins are in the shape of the normal distribution.

Figure 1: Quincunx.

26 A population on the move

Now consider a random walk on integers. At each step, the random walker either goes left or right with 1/2 probability. This is essentially the same as the quincunx. The only difference is how we label the final location. Let Z_{i} = 1 if the i-th coin flip is head, and Z_{i} = −1 otherwise. Let X(n) = Z_{1} + ... + Z_{n}. Then X(n) is the destination of the random walk after n steps. Let X̃(n) be the number of heads after n flips of the fair coin. Then X(n) = X̃(n) − (n − X̃(n)) = 2X̃(n) − n. Therefore, E[X(n)] = 0 and Var[X(n)] = n.

We can imagine that each integer is a state. Imagine that a population of 1 million people start from state 0. At each step, within each state, half of the people goes to the left neighbor, and the other half goes to the right neighbor. Then we can imagine that this population gradually diffuses from state 0 to other states.

27 Brownian motion

If we put a drop of milk into a cup of coffee, then the drop of milk diffuses. In the idealized and simplified one-dimensional situation, so that there is no gravity and no interactions between the particles of the milk, we can imagine that each particle of the drop of milk follows a random walk caused by the bombardments of the tiny water molecules. At each moment, the density of the drop of milk is described by the normal distribution. Imagine that we can videotape this process, so that we have a movie.

The motion of a particle caused by the bombardment of the tiny water molecules is called Brownian motion. It was first discovered by Botanist Brown and was later analyzed by Einstein.

28 Making a movie

We can also model this process, as if we are making a movie by simulating from the model instead of videotaping the actual process.

We all know that a movie is made up of a finite number of frames, even though we perceive an apparent continuous motion. We can also build our model this way. We divide the time domain into small periods: (0, Δt), (Δt, 2Δt), ... Within each period, the particle moves either to the right or to the left by Δx.

At time t, we have gone through n = t/Δt flips. Let X(t) be the location of a particle at time t. According to the calculation in Section 26, E[X(t)] = 0, and Var[X(t)] = nΔx^{2} = tΔx^{2}/Δt.

If we want our model to give a definitive answer as Δt → 0, then we need to have Δx^{2}/Δt goes to a constant that is independent of Δt or Δx. Let D be this limit, then for small Δt, we have Δx^{2} = DΔt, or Δx = \sqrt{DΔt}.

From the point of view of making a movie, we want to see the same scene, i.e., the distribution of the particles, at any fixed time t no matter how many frames we show in a second, or no matter what Δt is. Then at least we want Var[X(t)] to be the same for different Δt. Therefore, we want Δx^{2}/Δt to be a constant.

According to the central limit theorem, X(t) follows a normal distribution with expectation 0 and variance Dt. The D is the diffusion constant, which depends on the size of the water molecules and some other physical constants.

29 Velocity not defined

Suppose you want to make a movie of a particle moving at velocity v, then you want to have Δx = vΔt. But in Brownian motion, we have Δx^{2} = DΔt, or Δx = \sqrt{D}\sqrt{Δt}, so Δx/Δt = \sqrt{D}/\sqrt{Δt} → ∞ as Δt → 0. That is, the velocity of the particle is not defined in Brownian motion, and we see a zigzag path.

Later we shall see that the relationship Δx^{2} = DΔt plays a fundamental role in stochastic differential equations.

30 Flip a biased coin

Now we are ready to consider the more general situation where the probability of getting a head is p, which is not necessarily 1/2. For a sequence ω ∈ Ω, we still have X(ω) = Z_{1}(ω) + ... + Z_{n}(ω). We use the notation Z_{i} ∼ Bernoulli(p) to denote the fact that Z_{i} is a binary random variable, and P (Z_{i} = 1) = p = 1 − P (Z_{i} = 0). We write X ∼ Binomial(n, p).

We can show that P (X = k) = \binom{n}{k}p^{k}(1 − p)^{n−k}. The reason is that for each sequence ω with exactly k heads, the probability of this sequence, P (ω) = p^{k}(1 − p)^{n−k}. So this time, the probability is not uniform. The number of sequences with k heads is \binom{n}{k}. So the total probability is \binom{n}{k}p^{k}(1 − p)^{n−k}.

31 What is independence

The reason that P (ω) = p^{k}(1 − p)^{n−k} is because we assume that the n flips are independent, so that we can multiply their probabilities.

Figure 2: A and B are independent.

Figure 2 illustrates the concept of independence. Suppose we generate two uniform random variables (X, Y) from [0, 1] independently. Then (X, Y) is a random point in the unit square [0, 1]^{2}. Let A ⊂ [0, 1] be an interval on the x-axis, and B ⊂ [0, 1] be an interval on the y-axis. So P (A) = P (X ∈ A) = |A|, and P (B) = P (Y ∈ B) = |B|, where |A| and |B| are the lengths of A and B. With a little abuse of notation, we can also think of A and B as the corresponding vertical and horizontal strips respectively. Then A ∩ B is the rectangular intersection between the vertical strip A and the horizontal strip B. P (A ∩ B) = P ((X, Y) ∈ A ∩ B) = |A ∩ B| = |A||B| = P (A)P (B).

So the geometrical meaning that two events are independent is that they are perpendicular to each other.

32 Map to equal likely setting: survey sampling

In the experiment of flipping a biased coin, the outcomes are not equally likely, because if a sequence ω has k heads, then P (ω) = p^{k}(1 − p)^{n−k}.

But we can map this experiment to another experiment where the outcomes are still equally likely. Consider sampling a population of M people, where r of them are red, and b of them are blue, and r + b = M. If we randomly sample a person, then the probability we get a red person is p = r/M.

If we sequentially sample n people independently and with replacement, that is, after we sample a person, we put the person back to the population, so that the person can still be sampled later on. In this scenario, the sample space Ω consists of all the sequences of people that we sampled. The number of all the possible sequences is M^{n}, because each time, we have M different choices. All these sequences are equally likely.

The number of sequences with k red people is \binom{n}{k}r^{k}b^{n−k}. The reason is as follows. In the sequence of n people, we can choose k of them to be red, and then the rest of n − k of them to be blue. The number of choices is \binom{n}{k}. Then for each red person, we have r choices in random sampling, and for each blue person, we have b choices.

Let B_{k} be the subset of all the sequences with k red people. Then P (B_{k}) = |B_{k}|/|Ω| = \binom{n}{k}r^{k}b^{n−k}/M^{n} = \binom{n}{k}p^{k}(1 − p)^{n−k}. This is the same formula as we derived for coin flipping experiment.

33 How large is P (A_{k})?

Now let us go back to the coin flipping experiment. Again let A_{k} = {ω : X(ω) = k}, i.e., the set of sequences with k heads. According to Section 30, P (A_{k}) = \binom{n}{k}p^{k}(1 − p)^{n−k}.

In Section 7, we have shown that for k = nα,

\binom{n}{k} ∼ C(n, α)2^{nh(α)},

where

C(n, α) = \frac{1}{\sqrt{2πnα(1 − α)}},

h(α) = −[α log_{2} α + (1 − α) log_{2}(1 − α)].

So

P (A_{k}) = \binom{n}{k}p^{k}(1 − p)^{n−k} ∼ C(n, α)2^{nh(α)}p^{nα}(1 − p)^{n(1−α)}
= C(n, α)2^{nh(α)}2^{n(α log_{2} p+(1−α) log_{2}(1−p))}
= C(n, α)2^{−nD(α)}

where

D(α) = [α log_{2} \frac{α}{p} + (1 − α) log_{2} \frac{1 − α}{1 − p}].

34 Kullback-Leibler divergence

D(α) can be written as D((α, 1 − α)||(p, 1 − p)), which is the Kullback-Leibler divergence of the probability distribution (α, 1−α) from the probability distribution (p, 1−p). Later, we shall define a more general form of the Kullback-Leibler divergence.

As a function of α, D(α) ≥ 0, and D(α) = 0 only when α = p. This is because D′(α) = log_{2}(α/p) − log_{2}((1 − α)/(1 − p)), and D′′(α) = 1/α + 1/(1 − α). For α ∈ (0, 1), D′′ > 0, so the function is convex, and the minimum is achieved as α = p, where D′(α) = 0, and D(α) = 0.

35 Concentration of probability

Because P (A_{k}) ∼ C(n, α)2^{−nD(α)}, and D(α) achieves its minimum 0 at α = p, the probability will eventually concentrate on those classes A_{k} where k/n = α ≈ p. Because if k/n = α is deviate from p by a constant ϵ > 0, then P (A_{k}) ∼ C(n, α)2^{−nD(α)} goes to 0 at an exponential rate no matter how small ϵ is.

36 Weak law of large number

Because P (A_{k}) = P (X = k), we have the following weak law of large number

P (|\frac{X}{n} − p| > ϵ) → 0.

37 Probability and long run frequency

The weak law of large number says that the long run frequency converges to probability. In other words, we can interpret probability as long run frequency.

But bear in mind that we never define probability as long run frequency. In fact, such a definition is untenable. If we define p = lim_{n→∞} X/n, we will face the question whether this limit exists at all. In fact, it is possible for X/n to be as small as 0 and as large as 1. You may argue that the probability for X/n to be 0 or 1 is extremely small. But then you have not define probability yet, how can you talk about probability being extremely small? As a matter of fact, the fact that X/n → p has to be expressed in terms of probability, as in the weal law of large number.

So the fact that probability manifests itself as long run frequency is a logical consequence, not a logical starting point.

In the equally likely setting, we can indeed define probability P (A) = |A|/|Ω|. For instance, in the survey sampling situation, all the M^{n} sequences are equally likely. The weak law of large number corresponds to the following mathematical fact: among all these M^{n} sequences, if we look at the frequency of red people in each sequence, then almost all of M^{n} sequences produce frequencies that are close to p = r/M.

38 Mean and variance of Binomial

For each sequence ω, we can calculate X(ω), which is the number of heads. If X(ω) = k, the probability of this sequence is P (ω) = p^{k}(1 − p)^{k}.

We can define the expectation

μ = E[X] = ∑_{ω=1}^{N} X(ω)P (ω),

where again we number the sequences from 1 to N = 2^{n}. This time, E[X] is a weighted average, where the weight of ω is its probability.

We can also define the variance

σ^{2} = Var[X] = ∑_{ω=1}^{N}(X(ω) − μ)^{2}P (ω).

Variance is the average of the squared deviation.

Because X = Z_{1} + ... + Z_{n}, where Z_{i} ∼ Bernoulli(p) independently, we have

E[X] = ∑_{i=1}^{n} E[Z_{i}] = np,

Var[X] = ∑_{i=1}^{n} Var[Z_{i}] = np(1 − p).

The above results follow from the following two facts. The first fact is that for a random variable Z ∼ Bernoulli(p), E[Z] = 0 × (1 − p) + 1 × p = p, and Var[Z] = (0 − p)^{2} × (1 − p) + (1 − p)^{2} × p = p(1 − p). The second fact is that when we calculate the expectation and variance of the sum of some independent random variables, we can simply add up the expectations and variances of these random variables.

39 Sum of two random variables

Suppose we have two sample spaces, e.g., two boxes. In one box, we have N black ball, and we number them 1, 2, ..., N. Each black ball carries a number, and let the number of black ball i be X(i). Suppose when we sample from this box, the probability of getting the black ball i is p(i). In the other box, we have M white balls, and we number them 1, 2, ..., M. Each red ball carried a number too, and let the number of white ball j be Y (j). Suppose when we sample from this box, the probability of getting the white ball j is q(j).

Suppose we sample a black ball from the first box, and independently, we sample a white ball from the second box. Then we sum the number carried by the black ball and the number carried by the white ball. Let the sum be Z. We want to study the behavior of this random variable Z.

The joint sample space is Ω = {1, 2, ..., N} × {1, 2, ..., M}, i.e., a N × M table of pairs. For each pair ω = (i, j) ∈ Ω, we get two numbers X(i) and Y (j), and their sum is Z(ω) = X(i) + Y (j). Because of the independence, the probability of getting a pair ω = (i, j) is P (ω) = p(i)q(j).

μ_{Z} = E[Z] = ∑_{ω∈Ω} Z(ω)P (ω)

= ∑_{i=1}^{N} ∑_{j=1}^{M}[X(i) + Y (j)]p(i)q(j)

= ∑_{i=1}^{N} X(i)p(i) + ∑_{j=1}^{M} Y (j)q(j)
= E[X] + E[Y] = μ_{X} + μ_{Y} .

σ_{Z}^{2} = Var[Z] = ∑_{ω∈Ω}(Z(ω) − μ_{Z})^{2}P (ω)

= ∑_{i=1}^{N} ∑_{j=1}^{M}[(X(i) + Y (j)) − (μ_{X} + μ_{Y})]^{2}p(i)q(j)

= ∑_{i=1}^{N} ∑_{j=1}^{M}[(X(i) − μ_{X})^{2} + (Y (j) − μ_{Y})^{2} + 2(X(i) − μ_{X})(Y (j) − μ_{Y})]p(i)q(j)
= Var[X] + Var[Y].

40 Law of large number

According to the results in Section 38, E[X/n] = E[X]/n = p and Var[X/n] = Var[X]/n^{2} = p(1 − p)/n → 0 as n → ∞. Therefore, X/n → p. This reaffirms the law of large number.

41 Central limit theorem

For Z = (X − np)/\sqrt{np(1 − p)}, E[Z] = 0 and Var[Z] = 1. We can show that the distribution of Z goes to the Gaussian distribution, using the same method as in Sections 14 and 15.

For k = np + z\sqrt{np(1 − p)}, let g(z) = P (X = k). Then according to the result in Section 33

g(0) = P (X = np) ∼ C(n, p)2^{−nD(p)} = \frac{1}{\sqrt{2πnp(1 − p)}},

because D(p) = 0. Let d = z\sqrt{np(1 − p)}, and let q = 1 − p,

\frac{g(z)}{g(0)} = (\binom{n}{np + d}p^{d}) / (\binom{n}{np}q^{d})
= \frac{(np)!(nq)!p^{d}}{(np + d)!(nq − d)!q^{d}}
= \frac{nq(nq − 1)...(nq − d + 1)p^{d}}{(np + 1)(np + 2)...(np + d)q^{d}}
= \frac{(1 − Δ_{0})(1 − 2Δ_{0})...(1 − (d − 1)Δ_{0})}{(1 + Δ_{1})(1 + 2Δ_{1})...(1 + dΔ_{1})}

where Δ_{0} = 1/(nq) and Δ_{1} = 1/(np). Using 1 + δ ≈ e^{δ},

\frac{g(z)}{g(0)} ≈ exp\{− ∑_{i=1}^{d−1}(iΔ_{0}) − ∑_{i=1}^{d}(iΔ_{1})\}
≈ exp{−Δ_{0}d^{2}/2 − Δ_{1}d^{2}/2} = e^{−z^{2}/2}.

So for any z, we have

p(z) ∼ \frac{1}{\sqrt{2πnp(1 − p)}}e^{−z^{2}/2}.

42 Geometric waiting time

Let T be the number of flips until we get the first head, then T ∼ Geometric(p), P (T = k) = (1 − p)^{k−1}p, where k = 1, 2, ... Let q = 1 − p, then

E[T] = ∑_{k=1}^{∞} kP (X = k) = ∑_{k=1}^{∞} kq^{k−1}p = p ∑_{k=1}^{∞} \frac{d}{dq} q^{k} = p\frac{d}{dq} ∑_{k=1}^{∞} q^{k}
= p\frac{d}{dq} (\frac{1}{1 − q} − 1) = p\frac{1}{(1 − q)^{2}} = \frac{1}{p}.

43 Poisson process

Suppose we divide the time axis into small periods (0, Δt), (Δt, 2Δt), ... Within each period, we flip a coin independently. The probability of getting a head is λΔt.

Suppose t is a multiple of Δt. Let X be the number of heads within the interval [0, t]. Then X ∼ Binomial(n = t/Δt, p = λΔt). E[X] = np = λt. So λ = E[X]/t, and it can be interpreted as the number of occurrences (in this case, heads) per unit time.

For k = 0, 1, ...,

P (X = k) = \binom{n}{k}p^{k}(1 − p)^{n−k}
= \frac{n(n − 1)...(n − (k − 1))}{k!}p^{k}(1 − p)^{n−k}
= \frac{t/Δt(t/Δt − 1)...(t/Δt − (k − 1))}{k!}(λΔt)^{k}(1 − λΔt)^{t/Δt−k}
= \frac{t(t − Δt)...(t − (k − 1)/Δt)}{k!}λ^{k}(1 − λΔt)^{t/Δt}(1 − λΔt)^{−k}
→ \frac{(λt)^{k}}{k!} e^{−λt},

as Δt → 0. In the above derivation, we use the result that (1 − λΔt)^{t/Δt} ≈ (e^{−λΔt})^{t/Δt} = e^{−λt}.

44 Exponential waiting time

Let T be the waiting time until the first head, then

P (T ∈ (t, t + Δt)) = (1 − λΔ)^{t/Δt}λΔt,

so

P (T ∈ (t, t + Δt))/Δt = (1 − λΔ)^{t/Δt}λ → λe^{−λt}.

This gives us the probability density function of T.

P (T > t) = (1 − λΔ)^{t/Δt} → e^{−λt}.

This is because T > t means that all the flips up to t give us tails.

The expected number of flips until the first head is 1/p = 1/(λΔt). Each flip takes a duration of Δt. So E[T] = 1/(λΔt) × Δt = 1/λ.

We can model the time until a particle decays by the exponential model. The half live t is such that P (T < t) = 1/2.

45 Randomness and entropy

Consider the following distribution on an alphabet of four letters,

\begin{matrix}x & A & B & C & D \\ p(x) & 1/2 & 1/4 & 1/8 & 1/8 \end{matrix}

We can generate a letter from the above distribution by flipping a fair coin. The scheme is as follows. We flip the coin, if it is head, then we return A. If it is tail, we flip the coin again. If it is head, we return B. If it is tail, we flip the coin a third time. If it is head, we return C. Otherwise, we return D. Figure 3 illustrates this scheme.

Figure 3: Simulating a random letter by coin flipping

The number of coin flips for each letter is

\begin{matrix}x & A & B & C & D \\ l(x) & 1 & 2 & 3 & 3 \end{matrix}

So the average number of coin flips is 1×1/2+2×1/4+3×1/8+3×1/8 = 7/4. This is a measure of randomness in the distribution p(x). In general, we define entropy(p) = ∑_{x}[− log_{2} p(x)]p(x) as the randomness in a distribution p(x).

46 Coding

What is interesting is that the above scheme leads to a coding scheme for the alphabet:

x A B C D ; code 1 01 001 000

where we use 1 for head and 0 for tail. The coding scheme has the important property that the code of any letter is not the beginning part of the code of any other letter. So if we have a sequence of letters such as AABDCA, we can code it by 11010000011, from which we can get back the original sequence without ambiguity. The average coding length is just the average number of coin flips, 7/4. So the entropy can be interpreted as the coding length.

47 Coding sequence and random sequence

If we generate a sequence of letters according to p(x) in Section 45, and we code the sequence of letters using the code book in Section 46, then we have a binary sequence, which is also a sequence obtained by flipping a fair coin independently, because the coding scheme in Section 46 comes from the scheme in 45 for generating the letter.

48 Random sequence is not compressible

In general, a long sequence of random coin flipping is not compressible. We can argue this point by contradiction.

A random sequence is a random draw from the population of 2^{n} sequences. Suppose a tiny proportion of it is compressible, say, 1% of it can be compressed by ρn bits, where ρ < 1. Then 1% × 2^{n} ≤ 2^{ρn}. But for large n, this is impossible because the ratio between the left hand side and the right hand side goes to infinity.

Therefore, the coding scheme in Section 46 is optimal, in the sense that for a long sequence of letters generated by the distribution p(x), the corresponding binary code is the shortest, in the sense that it cannot be further compressed.

49 Kolmogorov complexity

We can understand randomness from the perspective of coding. We may ask ourselves: why a long sequence 111...1, i.e., the sequence of n 1s, is not randomness? One argument is that this sequence can be produced by a simple computer program:

for i = 1 to n
   write 1
end

In computer, the above code can be stored by a short binary sequence. So the original sequence can be compressed into a much shorter sequence.

In general, for any long sequence, we can imagine the shortest code that reproduces this sequence. The length of this shortest code is the Kolmogorov complexity.

50 Randomness = incompressibility

For some long sequences, the shortest codes may simply be the original sequences themselves, that is, the sequence is not compressible. Such sequences are random sequences, because they have all the statistical properties of the random sequence. For instance, we know that a random sequence has its frequency of heads very close to 1/2. If a sequence is not compressible, then its frequency of heads must be close to 1/2.

We can argue this point by contradiction. Suppose the frequency of heads in this sequence is 1/3. Then this sequence belongs to class A_{n/3}, and we know that |A_{n/3}| ∼ C(n, 1/3)2^{nh(1/3)}, where h(1/3) < 1. Therefore, we can reproduce this sequence by the following program: “write the i-th sequence in A_{n/3},” where in A_{n/3}, we can sort the sequences from smallest to largest. Clearly, i ≤ |A_{n/3}|, and we can code i by log_{2} |A_{n/3}| bits, and log_{2} |A_{n/3}|/n → h(1/3) < 1, so we can code this sequence using less than n bits.

51 Randomness in flipping a biased coin

Suppose we flip a biased coin n times independently, where the probability of head is p. According to the law of large number, the probability concentrates on those classes A_{k} where k is close to np. The size of A_{np} ∼ C(n, p)2^{nh(p)}. In order to generate a random member in A_{k} where k is close to np, we only need to flip a fair coin nh(p) times. Therefore, the randomness in flipping a biased coin n times amounts to the randomness of flipping a fair coin nh(p) times. So the randomness in flipping a biased coin with probability p is h(p).

52 Equipartition

Another way to think about the above issue is that for a sequence Z_{1}, Z_{2}, ..., Z_{n}, where Z_{i} = 1 with probability p and Z_{i} = 0 with probability 1 − p, the probability of this sequence Z_{1}, Z_{2}, ..., Z_{n} is p^{X}(1 − p)^{n−X}, where X = ∑_{i} Z_{i}. According to the law of large number X/n → p. Therefore, Pr(Z_{1}, ..., Z_{n}) ≈ p^{np}(1 − p)^{n(1−p)} = 2^{−nh(p)}, which does not depend on Z_{1}, ..., Z_{n}. That means that Z_{1}, ..., Z_{n} is almost like a uniform random sample, whose probability is the same as the probability of a random sequence generated by flipping a fair coin nh(p) times.

The fact that Z_{1}, ..., Z_{n} behaves like a uniform random sample is called equipartition property.

53 Strong law of large number

The weak law of large number takes the form P (|X/n − p| > ϵ) → 0. The statement or the event |X/n − p| > ϵ only concerns the first n flips, where Ω is the set of all the 2^{n} sequences. After calculating its probability, we let n goes to infinity.

The strong low is like saying P (X/n → p) = 1. The statement or the event X/n → p concerns the infinite sequence. In this case, Ω is the set of all the infinite binary sequences, i.e., Ω = {0, 1}^{∞}. So a more precise way of saying P (X/n → p) = 1 is P ({ω : X_{n}(ω)/n → p}) = 1, where X_{n}(ω) is the number of heads in the first n flips of ω.

The statement X/n → p means that for any ϵ > 0, there exists an N, so that for any n ≥ N, |X_{n}(ω)/n − p| ≤ ϵ. Let A_{n} = {ω : |X_{n}(ω)/n − p| ≤ ϵ be the set of all sequences such that |X_{n}(ω)/n − p| ≤ ϵ is true. Then the statement X/n → p can be expressed by ∪_{N=1}^{∞} ∩_{n=N}^{∞} A_{n}, and the strong law means that P (∪_{N=1}^{∞} ∩_{n=N}^{∞} A_{n}) = 1.

54 σ-algebra and meaningful statements

For a sample space Ω as big as {0, 1}^{∞}, not all its subsets are meaningful. In fact, probability is only defined on those meaningful events or statements. The set of all the meaningful statements is called a σ-algebra.

We can construct a σ-algebra as follows. We start from elementary or basic meaningful statements, such as statements about the first n flips, where n is finite. Then we can combine the basic meaningful statements by AND, OR, and NOT, or equivalent, by intersection, union, and complement. For AND and OR, we are allowed to combine infinity but countably many basic statements. For instance, ∪_{N=1}^{∞} ∩_{n=N}^{∞} A_{n} is a meaningful statement constructed from the basic statements A_{n}.

55 Measure

Although ∪_{N=1}^{∞} ∩_{n=N}^{∞} A_{n} is only a subset of Ω, its probability is 1, which is the same as the probability of Ω. This is possible, because the complement of ∪_{N=1}^{∞} ∩_{n=N}^{∞} A_{n}, although not empty, may have probability 0.

Probability is like a measure, such as length, area, or volume. It measures the size of the subsets or events. It is possible that a non-empty set has measure 0.

For instance, the length of the interval [0, 1] is 1. But the length of the subset {.5} is 0, because {.5} is just a point. Similarly, the length of all the rational numbers in [0, 1] is also zero, because the set of all the rational numbers is a countable list of points.