Math.

55 The Law of Large Numbers May 29, 1999 7:10 am

The Law of Large Numbers says roughly this:

The probability distribution of practically any random variable can be determined to any
desired degree of accuracy as nearly certainly as desired by sampling that random variable
independently and often enough.

First this note applies Chebyshev’s Inequality to justify the Law of Large Numbers in a
typical special case. Next comes a description of the Central Limit Theorem, which is proved
valid in a very special case. Sometimes this Theorem is confused with the Law of Large
Numbers; both ideas are important for most practical applications of probability.

Consider a random variable x distributed over a given finite population of individuals i or

sample space of “outcomes” i . Actually x is a function that takes the value xi at i , which
will occur or be chosen at random with probability prob(i) . The simplest nontrivial random
variable is just xi := prob(i) . Often prob(i) is the same for all individuals i but we shall not
assume this; we do take for granted, as usual, that every prob(i) ≥ 0 and that ∑i prob(i) = 1 .
More generally, the probability that any preassigned subset $ of the population will include a
not-yet-specified individual chosen at random from the whole population is ∑i in $ prob(i) .

The Mean, Average or Expected value of x over the whole space is denoted in this note by
Æ(x) := ∑i prob(i)·xi = ∑X Probability(x = X)·X .
The last sum is over all values X = xi that x takes in the given population. This note concerns
the estimation of Æ(x) , given function x , without knowing those probabilities in advance.

To know the probability distribution of x is to know Probability(x = X) for every number X

or, more usefully, to know Probability(X ≤ x ≤ X+∆) for every X and ∆ ≥ 0 . A way to
estimate this latter probability, given X and ∆ , is to define another random variable y thus:
yi := 1 if X ≤ xi ≤ X+∆ ; otherwise yi := 0 .
Then Æ(y) = Probability(X ≤ x ≤ X+∆) ; can you see why? This is why we wish to know how
to estimate Æ(…) in general, not merely for one random variable x . In other words, Æ(…)
is a functional, a function whose explicit argument is a function ( and whose implicit argument
is a population or sample space ); Æ maps functions ( defined over populations ) to numbers.

Æ is a linear functional in the following sense: If x and y are two random variables over a
population, and if µ and ß are constants ( each taking just one value over the population ),
then Æ(µ·x + ß·y) = µ·Æ(x) + ß·Æ(y) ; can you see why? More generally, however, for an
arbitrary function ƒ(x, y) we almost always find that Æ(ƒ(x, y)) ≠ ƒ(Æ(x), Æ(y)) . This is why
the estimation of Æ can be technically challenging.

Random variables x and y are called “ Statistically Independent ” ( or just “Independent” ) if

Probability(x = X and y = Y) = Probability(x = X)·Probability(y = Y)
for all constants X and Y , in which case Æ(x·y) = Æ(x)·Æ(y) ; can you see why? But when
x and y are not independent, Æ(x·y) – Æ(x)·Æ(y) equals something called the covariance
of x and y , as we shall see later. Thus, multiplication of random variables is quite different
from addition because Æ(x+y) = Æ(x)+Æ(y) regardless of independence. Whether random
variables are independent is always important though sometimes difficult to ascertain.

Prof. W. Kahan Page 1

This document was created with FrameMaker 4 0 4

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

Random Sampling
Suppose we plan to select ( but not remove ) an individual, to be called I , from the given
population. This I will be a Random Sample if Probability(I = i) = prob(i) . Similarly for
another random sample J . Then the two samples will be regarded as statistically independent if
Probability( I = i and J = j ) = prob(i)·prob(j) .
The future tense is used here because the word “random” may be inappropriate to describe a
sample J after it has been selected. Moreover, nobody knows how to choose samples that are
perfectly random and independent although some pretty good approximations are known; the
art of systematic random sampling is a topic discussed in Statistics courses, especially courses
about the Design of Experiments. The generation of good pseudo-random numbers is treated
in vol. II of D.E. Knuth’s The Art of Computer Programming (Addison-Wesley).

For example, tossing a coin has two outcomes, heads and tails, that are sampled ostensibly at
random every time the coin is tossed; however, the outcomes can be both biased and correlated
if the tosser repeats too accurately his motions for each toss. A casting director chooses extras
for a movie’s crowd scene not by sampling them at random from whoever is available, but
rather by correlating her selections to ensure that the crowd looks more nearly “representative”
of the population intended by the script-writer. Japanese flower arrangements look random
only if some artistry goes into their placement.

So, random sampling is hypothetical if not mythical. And to the extent that individuals can be
sampled at random, so can a random variable x ; we shall let X := xI denote the sample-value
of x obtained from individual I sampled at random. We shall contemplate large numbers n
of random samples X1, X2, X3, …, Xn of random variable x corresponding respectively to
individuals I1, I2, I3, …, In to be selected ( but not removed ) at random and independently
from a population. And then we shall compare several statistics :
x := Æ(x) = the mean of x over the population, with
Æ(X) where X := (X1 + X2 + X3 + … + Xn)/n = the samples’ mean; and
σ2 := Æ((x – x)2) = the variance of x over the population, with
Æ(S2) where S2 := ((X1–X)2 + (X2–X)2 + … + (Xn–X)2)/n = the samples’ variance.

Note that, at least until the samples have been drawn, each of X1, X2, X3, …, Xn is a random
variable distributed the same way as x is. Consequently X and S2 are random variables too,
but over a population of n-tuples (I1, I2, I3, …, In) composed from the n-fold Cartesian
product of the given population with itself. Until the samples have been drawn,
Probability((I1, I2, I3, …, In)) = prob(I1)·prob(I2)·prob(I3)·…·prob(In)
because the samples are independent. It follows that each of X1, X2, X3, …, Xn is independent
of all others (why?) so Æ(Xk·Xm) = Æ(Xk)·Æ(Xm) = Æ(x)·Æ(x) = x 2 for 1 ≤ k < m ≤ n .
But every Æ(Xk2) = Æ(x2) generally differs from x 2 , as we shall see. Moreover, random
variables X and S2 are not generally independent of each other nor of the samples-to-be Xk .

Let’s digress for a moment to consider two random variables x and y that are not necessarily
independent. Analogous to x and σ2 are the statistics

Prof. W. Kahan Page 2

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

y := Æ(y) = the mean of y over the given population, and

τ2 := Æ((y – y)2) = the variance of y over the population.
To these we add the statistic
γ := Æ((x–x)·(y–y)) = the covariance of x and y over the given population.
In the very special case that x and y are independent we find that
γ = Æ(x·y – x·y – x·y + x·y) = x·y – x·y – x·y + x·y = 0 .
In general γ ≠ 0 except by accident; and it is possible to find γ = 0 even though x and y are
not independent. In all cases, Æ(x·y) = x·y + γ ; can you see why? Moreover γ2 ≤ σ2·τ2 ; to
see why, consider the discriminant of a quadratic Æ((µ·(y–y) – (x–x))2) ≥ 0 for all real µ .

About terminology: Variances σ2 and τ2 are the squares respectively of standard deviations
σ and τ which are nonnegative by convention. And here “independent” can mean “Pairwise
Independent” because this note allows for ostensibly bizarre situations like when, of three
random variables x, y and z , every two are independent though those two determine the third.

Now the expected values of a few sample statistics can be computed for comparison with
population statistics:
Æ(X) = Æ(∑k Xk)/n = ∑k Æ(Xk)/n = ∑k Æ(x)/n = n·x/n = x , and
Æ((X–Æ(X))2) = Æ((∑k (Xk – x)/n)2) = Æ(∑k ∑m (Xk–x)·(Xm–x))/n2
= ( n·σ2 + 0 )/n2 ( since Xk and Xm are independent if k ≠ m )
= σ2/n .
Therefore, as a random variable, the samples’ mean X has the same mean x as has x over
the whole population. But X has a variance σ2/n smaller than the population’s variance σ2 ,
which is NOT the same as the samples’ variance S2 though they are close enough to justify
the Law of Large Numbers, as we shall see later. First we digress to …

Chebyshev’s Inequality: If a random variable x has mean x and standard deviation σ , then
Probability( |x – x| ≥ σ/λ ) ≤ λ2 for every positive λ < 1 .

Proof: Let $ be that subset of the population’s individuals i for which |xi – x| ≥ σ/λ . Then
σ2 = ∑all i prob(i)·(xi - x)2
≥ ∑i in $ prob(i)·(xi - x)2 ≥ ∑i in $ prob(i)·(σ/λ)2
= (σ2/λ2) ·Probability( |x – x| ≥ σ/λ ) . Divide by σ2/λ2 to finish the proof.

Chebyshev’s Inequality tends to be extremely pessimistic because Probability( |x – x| ≥ σ/λ )

is almost always very much tinier than λ2 . Without additional information about x this λ2
cannot be replaced by something smaller because there are random variables x that satisfy
Probability( |x – x| ≥ σ/λ ) = λ2 for at least one λ > 0 . For example suppose x takes only
three values, namely x = ±1 each with probability λ2/2 , and x = 0 with probability 1 – λ2 ;
then x = 0 , σ = λ , and Probability( |x – x| ≥ σ/λ ) = λ2 exactly. Later we shall see how
pessimistic Chebyshev’s Inequality is; for now it is adequate to prove …

Prof. W. Kahan Page 3

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

The Law of Large Numbers: If a random variable x has mean x and standard deviation σ
then, given any two tiny positive tolerances µ and ß , choosing a big n > (σ/µ)2/ß will
ensure that the samples’ mean X , of n independent random samples of x , differs
from the population’s mean x by less than µ except with probability smaller than ß .

Proof: For any n > (σ/µ)2/ß set λ := σ/(µ·√n) < √ß to infer that Probability( |X–x| ≥ µ) < ß
from Chebyshev’s inequality because the standard deviation of X is σ/√n . End of proof.

The Law of Large Numbers is often misapplied. For example consider a large number n of
fair tosses of a fair coin just as likely to come up Heads as Tails. The expected number of
each is n/2 , from which some people wrongly infer that the difference between the numbers
of Heads and Tails is likely to be small, and more likely as n increases. If the coin has come
up Heads rather more often then Tails for a while, these people would bet that Tails are
more likely to appear in the next several tosses. Not so! Even if the tosses are perfectly fair,
that difference can be proved almost certainly bigger than any big number chosen in advance,
while the ratio of the numbers of Heads and Tails is almost certain to differ from 1 by less
than any tiny positive number chosen in advance, provided the number n of tosses is chosen
big enough in advance. Choosing n in advance is obligatory lest the Law of Large Numbers,
as stated above, be violated. It is violated when n is chosen by drawing ever more samples
until a tolerance is exceeded, and stopping then. No matter how unlikely this stopping event
may be, unless it is impossible it will surely occur at least once if Fate is tempted often enough.

Any application of the foregoing Law of Large Numbers to estimate the mean x of x uses an
estimate of the variance σ2 of x to decide how big the sample size n should be; but if x is
not yet known where can an estimate of σ2 come from? From the samples’ variance S2 ? Not
exactly. First, until the samples have been drawn, S2 is a random variable. Second, it is
likely to somewhat underestimate σ2 ; in other words, S2 is a statistically biased estimator
of σ2 . More precisely, as shall be proved next,
Æ(S2) = (1 – 1/n)·σ2 .

Lemma: If independent random variables yj all have mean Æ(yj) = 0 and respective
variances Æ(yj2) = τj2 , then Æ((∑j yj)2) = ∑j τj2 .
Proof: Æ((∑j yj)2) = Æ(∑k ∑j yk·yj) = ∑k ∑j Æ(yk·yj) = ∑j Æ(yj2) + ∑k ∑j≠k 0 = ∑j τj2 .

Now set every yj := –(Xj–x) except yk := (n–1)·(Xk–x) for any positive k ≤ n to find that
Æ((n·Xk – n·X)2) = Æ((yk + ∑j≠k yj)2) = (n–1)2·σ2 + (n–1)·σ2 = n·(n–1)·σ2 .
Consequently
n3·Æ(S2) = Æ( ∑k (n·Xk – n·X)2 ) = ∑k Æ((n·Xk – n·X)2) = n2·(n–1)·σ2 .
Divide by n3 to conclude that Æ(S2) = (1 – 1/n)·σ2 as claimed above. End of proof.

An initial batch of n samples could be drawn to provide an estimate S2/(1 – 1/n) of σ2 after
which at least (σ/µ)2/ß new samples would very likely estimate x adequately; but these are
almost always far too many new samples because Chebyshev’s inequality is so pessimistic.

Prof. W. Kahan Page 4

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

The Central Limit Theorem Summarized

Its proof is difficult, not for everybody. It says something astonishing, roughly this:
Practically regardless of how the random variable x is distributed, there is one universal
Normal Distribution by which the probability distribution of the samples’ mean X comes to
be approximated ever better as the number n of samples increases.

This Normal Distribution is characterized by a function Φ(z) that increases smoothly from
Φ(–∞) := 0 through Φ(0) = 1/2 to Φ(+∞) = 1 with a derivative Φ'(z) := exp(–z2/2)/√(2π) .
The graph of Φ(z) is its own reflection in its midpoint; Φ(–z) + Φ(z) = 1 . And as z → +∞ ,
Φ(±z) approaches its limits Φ(±∞) extremely rapidly; for every z > 0 it can be proved that
0 < Φ'(z)/(z + 1/z) < Φ(–z) = 1 – Φ(z) < Φ'(z)/z .

Tables of values of Φ(z) are available widely, especially in Statistics texts. Physicists more often use the Error
Function erf(z) = 2Φ(z√2)–1 . Computer programs based upon continued fractions or other formulas can compute
Φ(z) as accurately as need be though not so quickly as we would like; but it has been proved that no formula that
invokes algebraic operations ( +, –, ·, /, √ ) and elementary transcendental functions like exp, ln, tan, arctan, …
only finitely often can compute Φ(z) exactly. Φ(z) and its derivative Φ'(z) are plotted on the next page.

We say a random variable u is Distributed Normally with mean u and variance v2 just when
Probability( u ≤ U ) = Φ((U–u)/v) for all real U or, equivalently,
Probability( Ü < u ≤ Û ) = Φ((Û–u)/v) – Φ((Ü–u)/v) whenever Ü < Û .
It turns out that X is distributed approximately Normally with mean x and variance σ2/n ;
Probability( X ≤ U ) ≈ Φ((U–x)/(σ/√n)) ,
and this approximation improves as n increases. However, out on the tails of the distribution
where |X–x|/(σ/√n) exceeds 3 or 4 , the approximation improves so slowly that its use to
estimate tiny probabilities of extreme departures from the mean is imprudent. An appropriate
use for the Central Limit Theorem is to estimate where the values of X are most likely to be
found; this estimate depends upon n, x and σ but is otherwise affected little by the way x is
distributed.

For example let us estimate p3 := Probability( |X–x| < 3·σ/√n ) . Chebyshev’s inequality
implies p3 > 1 – 1/32 = 0.8888… , but this underestimates p3 substantially when n is big, in
which case the Central Limit Theorem implies that p3 ≈ Φ(3) – Φ(–3) = 0.9973… .

More generally, for k = 1, 2, 3, … let yk be mutually independent random variables ( the

probability of each is unaffected by whatever may be known about all others ) with respective
means yk and standard deviations τk , and let y := y1 + y2 + y3 + … + yn for some large n .
This y has mean y := y1 + y2 + y3 + … + yn and variance τ2 := τ12 + τ22 + τ32 + … + τn2
according to the Lemma above. Provided max1≤k≤n τk2/τ2 → 0 as n → +∞ , the Central
Limit Theorem says that (y–y)/τ is distributed ever more nearly Normally with mean 0 and
variance 1 as n increases. Again, the approximation is best for central tendencies but remains
relatively inaccurate out on the tails.

For proofs see W. Feller’s An Introduction to Probability Theory and its Applications vol. II 2d ed. (1971,
Wiley); it is heavy reading. A comparatively elementary treatment of a special case appears in the following pages.

Prof. W. Kahan Page 5

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

Graph of the Normal Distribution: Φ(z) and its Derivative Φ'(z) .

The Normal Distribution: Phi(z) and its Derivative Phi'(z)

1

0.9

0.8 Phi
Phi'

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-4 -3 -2 -1 0 1 2 3 4
Z

The Demoivre-Laplace Limit Theorem

Now we shall demonstrate the Central Limit Theorem’s validity in the special case of a huge
number n of fair and independent tosses of a fair coin. This is definitely not for everybody!

This case was discussed in 1718 by Abraham DeMoivre, a Huguenot who had fled to England from France
because Louis XIV revoked in 1685 the religious tolerance promulgated by Henri IV’s Edict of Nantes in 1598.
In 1812 DeMoivre’s discussion was refined by Pierre Simon Laplace, whose name too is now attached to this
demonstration. Many texts and notes exhibit flawed versions of this demonstration; I hope this one isn’t flawed too.

Let random variable hn count how many heads will appear after n independent and fair tosses of
a fair coin as likely ( probability = 1/2 ) to come up heads as tails. We already know that
Probability( hn = k ) = nCk/2n
( where combinatorial coefficient nCk = n!/(k!·(n–k)!) ) for all integers k provided we accept the
convention that nCk = 0 whenever k < 0 or k > n . Also known is that hn has mean
hn := Æ(hn) = n/2 and standard deviation vn := √Æ((hn–hn)2) = √n/2 ; see our text’s Example
22 on pp. 281-2. To confirm the Central Limit Theorem we must prove that, as n tends

Prof. W. Kahan Page 6

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

towards +∞ , the random variable un := (hn – hn)/vn becomes distributed ever more nearly like a
normal random variable with mean 0 and variance 1 , which means the approximation
Probability( Ü < un ≤ Û ) ≈ Φ(Û) – Φ(Ü) whenever Ü < Û
becomes ever more accurate as n increases provided Ü and Û are fixed first.

The function
Fn(U) := Probability( un ≤ U ) = Probability( hn ≤ hn + vn·U ) … but hn is an integer
= Probability( hn ≤ hn + vn·U ) = Probability( un ≤ (hn + vn·U – hn)/vn )
= Fn( (hn + vn·U – hn)/vn ) .
In other words, Fn(U) is for each n > 0 a nondecreasing step-function of U determined by its
values at regularly spaced discrete arguments U = Un,k := (k – hn)/vn for all integers k . Since
Fn(U) = 0 for all U < –√n ( do you see why?), the set of all differences
Fn(U) – Fn(U – 1/vn) = Probability( U – 1/vn < un ≤ U )
= Probability( hn + vn·U – 1 < hn ≤ hn + vn·U )
= Probability( hn = hn + vn·U )
= nCk/2n where integer k = hn + vn·U
determines Fn too by a telescoping sum: Fn(U) = ∑j≥0 ( Fn(U – j/vn) – Fn(U – (j+1)/vn) ) .

Thus our strategy is to deduce the approximation Fn(U) ≈ Φ(U) from a proof that the differenced
approximation Fn(U) – Fn(U – 1/vn) ≈ Φ(U) – Φ(U – 1/vn) has high relative accuracy if n is
big enough. But as n → +∞ these differences tend to zero since 1/vn = 2/√n → 0 ; to remedy
that we divide by 1/vn and find that ( Φ(U) – Φ(U – 1/vn) )/(1/vn) → Φ'(U) > 0 as n → +∞ .
This simplifies our strategy, reducing our task to the proof that also, for any fixed U ,
( Fn(U) – Fn(U – 1/vn) )/(1/vn) → Φ'(U) as n → +∞ .

Recall that Fn(U) – Fn(U – 1/vn) = nCk/2n where integer k = hn + vn·U . For any fixed U
this integer k = hn + vn·U = (n + U·√n)/2 increases somewhat irregularly as n increases.
To attenuate that irregularity we define u := (k – hn)/vn = 2((n + U·√n)/2 – n/2)/√n , which is
designed to satisfy k = (n + u·√n)/2 = (n + U·√n)/2 with U – 2/√n < u ≤ U . Clearly u → U as
n → +∞ , and now
( Fn(U) – Fn(U – 1/vn) )/(1/vn) = nCk·√n/2n+1 = n!·√n/(k!·(n–k)!·2n+1)
= n!·√n/(((n + u·√n)/2)!·((n – u·√n)/2)!·2n+1) .

Now is the time to invoke Stirling’s Approximation n! ≈ √2π·n ·(n/e)n ( proved in the class
notes on Some Inequalities ) at three places; after a lot of algebraic simplification we find
( Fn(U) – Fn(U – 1/vn) )/(1/vn) ≈ (1 – u/√n)u√n/2/(√2π·(1 – u2/n)(n+1)/2·(1 + u/√n)u√n/2) .

Calculus classes teach that if t → T as K → ±∞ then (1 + t/K)K → exp(T) = eT , which implies

here that, as n → +∞ ,
(1 – u/√n)u√n/2 → exp(–U2/2) , (1 – u2/n)(n+1)/2 → exp(–U2/2) , (1 + u/√n)u√n/2 → exp(U2/2) ,
and consequently, as claimed above, for any U fixed in advance, …

Prof. W. Kahan Page 7

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

( Fn(U) – Fn(U – 1/vn) )/(1/vn) = nCk·√n/2n+1 → exp(–U2/2)/√2π = Φ'(U) .

Thus the differenced approximation Fn(U) – Fn(U – 1/vn) ≈ Φ(U) – Φ(U – 1/vn) has now been
proved for each U to have arbitrarily high relative accuracy if n is big enough; in other words,
(Fn(U) – Fn(U – 1/vn))/(Φ(U) – Φ(U – 1/vn)) → 1 as n → +∞
even though numerator and denominator of the ratio (…)/(…) both approach 0 . Convergence
to 1 has been proved on the assumption that U is fixed before n → +∞ ; the proof and its
conclusion are invalid if U is allowed to vary too wildly with n . Still, theorems about Uniform
Convergence taught in Real Analysis classes say that, given any finite interval Ü ≤ U ≤ Û in
advance, we can keep |(Fn(U) – Fn(U – 1/vn))/(Φ(U) – Φ(U – 1/vn)) – 1| as tiny as we like for
all values U in that interval simultaneously by taking n big enough. This fact and one more will
be needed to complete the proof of the validity of the Central Limit Theorem for fair coin tosses.

Because Fn(U) is a nondecreasing step-function of U , we find whenever 0 < Û–Ü < 1/vn that
0 ≤ Fn(Û) – Fn(Ü) ≤ Fn(Û) – Fn(Û – 1/vn) ≤ maxk nCk/2n ≈ Φ'(0)/vn → 0 as n → +∞
and similarly 0 < Φ(Û) – Φ(Ü) < Φ'(0)/vn → 0 .

Now choose any finite interval Ü ≤ U ≤ Û , and set integer J := (Û–Ü)·vn = (Û–Ü)·√n/2 .
This J grows with √n , but always 0 ≤ Û – J/vn – Ü < 1/vn , so Fn(Û–J/vn) – Fn(Ü) → 0 and
Φ(Û–J/vn) – Φ(Ü) → 0 as n → +∞ . Meanwhile, because the relative error in every sum of
positive terms is no worse than the worst relative error in any term, the approximation
Fn(Û) – Fn(Û–J/vn) = ∑0≤j<J ( Fn(Û – j/vn) – Fn(Û – (j+1)/vn) )
≈ ∑0≤j<J ( Φ(Û – j/vn) – Φ(Û – (j+1)/vn) ) = Φ(Û) – Φ(Û–J/vn)
can be made as accurate as we please by taking n big enough. Add to both sides their respective
vanishing differences Fn(Û–J/vn) – Fn(Ü) and Φ(Û–J/vn) – Φ(Ü) to finish the proof that
Fn(Û) – Fn(Ü) → Φ(Û) – Φ(Ü) as n → +∞ .

Appendix: To estimate how quickly Φ(u) decays as u → –∞ , we compute

0 < ∫–∞u Φ(v)·dv = ∫–∞u ∫–∞v Φ'(t)·dt·dv = ∫–∞u ∫tu Φ'(t)·dv·dt = ∫–∞u (u–t)·Φ'(t)·dt
= u·Φ(u) + Φ'(u) ) ( because dΦ'(t)/dt = –t·Φ'(t) and Φ'(–∞) = Φ(–∞) = 0 ),
and infer that 0 < Φ(u) < Φ'(u)/(–u) = exp(–u2/2)/(–u·√2π) so long as –u > 0 . An analogous
estimate can be obtained for Fn(U) by observing that n–1Ck – n–1Ck–1 = (1 – 2k/n)·nCk and then
0 ≤ 2∑i<k ∑0≤j≤i nCj = (2k – n)·∑j<k nCj + k·nCk , whence ∑j<k nCj ≤ (k/(n – 2k))·nCk so long
as k < n/2 . ( Can you carry out the algebra?) Consequently, so long as √n >> –u > 0 ,
Fn(u – 1/vn) ≤ ((1 + u/√n)/(–u))·( Fn(u) – Fn(u – 1/vn) )/(1/vn) ≈ (1 + u/√n)·Φ(u)/(–u) .
This means that Fn(u) decays on its tail faster than Φ(u) does until n becomes big compared
with (–u)2 . Still, Φ(u) decays rapidly enough as u → –∞ that a rather large number n of
samples are generally needed before the Central Limit Theorem can approximate the tail of the
Normal Distribution with a tolerably tiny relative error. It is a topic treated only in advanced
texts on Probability and/or Statistics.

Prof. W. Kahan Page 8

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

Graphs of Φ(u) vs. Fn(u) for n = 4, 9 and 100 .

Prof. W. Kahan Page 9

Math. 55 The Law of Large Numbers May 29, 1999 7:10 am

Prof. W. Kahan Page 10