Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Local Limit Theorems

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

Consider a binomial probability value for a large value of the binomial parameter n. How would you approximate this probability value? Would you expect this approximation to be uniformly good for all values of k? Explain why or why not?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. This section gives two estimates of binomial probability values for a large value of the binomial parameter n in terms of the normal density. Each estimate is uniform in k. These estimates are two forms of the Local Limit Theorem.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. A local limit theorem describes how the probability mass function of a sum of independent discrete random variables at a particular value approaches the normal density.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Introduction

A local limit theorem describes how the probability mass function of a sum of independent discrete random variables approaches the normal density. We observe that the histogram of a sum of independent Bernoulli random variables resembles the normal density. From the Central Limit Theorem, we see that in standard units the area under the one bar of a binomial histogram may be approximated by the area under a standard normal. Theorems which compare the probability of a discrete random variable in terms of the area under a bar of a histogram to the area under a normal density are often called local limit theorems. This is illustrated in Figure 1


PIC

Figure 1: Comparison of the binomial distribution with n = 20, p = 610 with the normal distribution with mean np and variance np(1 p).

In a way, Pascal laid the foundation for the local limit theorem when he formulated the binomial probability distribution for a Bernoulli random variable with p = 12 = q. James Bernoulli generalized the distribution to the case where p12. De Moivre proved the first real local limit theorem for the case p = 12 = q in essentially the form of Lemma 9 in The de Moivre-Laplace Central Limit Theorem.. Laplace provided a correct proof for the case with p12. De Moivre then used the local limit theorem to add up the probabilities that Sn is in an interval of length of order n to prove the Central Limit Theorem. See Lemma 10 and following in The de Moivre-Laplace Central Limit Theorem.. Khintchine, Lyanpunov, and Lindeberg proved much more general versions of the Central Limit Theorem using characteristic functions and Fourier transform methods. Historically, the original Local Limit Theorem was overshadowed by the Central Limit Theorem, and forgotten until its revival by Gnedenko in 1948, [1].

First Form of Local Limit Theorem

Recall that Xk is a Bernoulli random variable taking on the value 1 or 0 with probability p or 1 p respectively. Then

Sn = k=1nX i

is a binomial random variable indicating the number of successes in a composite experiment.

In this section, we study the size of n Sn = k as n approaches infinity. We will give an estimate uniform in k that is a form of the local limit theorem.

Theorem 1 (Local Limit Theorem, First Form).

n Sn = k = 1 2πp(1 p)n exp (k np)2 2np(1 p) + o(1) .

uniformly for all k .

Remark. Note that this is stronger than Lemma 9, the de Moivre-Laplace Binomial Point Mass Limit in the section on the de Moivre-Laplace Central Limit Theorem.. It is stronger in that here the estimate is uniform for all k instead of just an interval of order n around the mean.

Proof.

  1. Take t = 7 12. Note that 1 2 < t < 2 3.

    1. Proposition 1 (the Optimization Extension of the Central Limit Theorem) in The Moderate Deviations Result., says
      n Sn = k = 1 2πp(1 p)n exp (k np)2 2np(1 p) 1 + δn(k) ,

      where

      lim n max |knp|<n712|δn(k)| = 0.

    2. Rewriting this, we have n Sn = k = 1 2πp(1 p)n exp (k np)2 2np(1 p) + 1 2πp(1 p) exp (k np)2 2np(1 p) δn(k) n ,

      where the last term is ou(n12) uniformly in k when |k np| < n712. Since

      1 2πp(1 p) exp (k np)2 2np(1 p) 1

      we can simplify this to

      n Sn = k = 1 2πp(1 p)n exp (k np)2 2np(1 p) + δn(k) n .
  2. Theorem 8.1 (the Moderate Deviations Theorem) says that if we take an = n112 p(1p), then lim nan = + and lim nann16 = 0. Thus, n Sn np + n712 = n Sn n p n512 = n Sn n p p(1 p) n112p(1 p) n12 p(1 p) n1122π exp n16 2p(1 p)

    where the last asymptotic limit comes from the Moderate Deviations Theorem on |k np| < n712.

  3. The asymptotic limit implies a weaker estimate:
    n Sn np + n712 = o n12 .

    To see this, note that

    n Sn np + n712 n12 = n Sn np + n712 p(1p) n1122π exp n16 2p(1p) p(1p) n1122π exp n16 2p(1p) n12 .

    Note that the first factor goes to 1 by step 2. So consider n512 exp n16 2p(1p) 0. This estimate is uniform in k for k np n712.

  4. Note that
    exp (k np)2 2np(1 p) exp n1412 2np(1 p) = exp n16 2p(1 p)

    so exp (knp)2 2np(1p) = o(1).

  5. Using step 4, we see that
    1 2πp(1 p)n exp (k np)2 2np(1 p) = o(n12)

    uniformly in k with k np n712.

  6. Make step 3 look the same as step 1b by putting step 5 into step 3 without disturbing the estimate:
    n Sn = k = 1 2πp(1 p)n exp (k np)2 2np(1 p) + o(n12).

    Finally, factor out 1 2πp(1p)n and the proof is finished

The Second Form of the Local Limit Theorem

Recall that Y i is a sequence of independent random variables which take values 1 with probability 12 and 1 with probability 12. This is a mathematical model of a fair coin flip game where a 1 results from “heads” on the ith coin toss and a 1 results from “tails”. Let Hn and Ln be the number of heads and tails respectively in n flips. Then Tn = i=1nY i = Hn Ln = 2Sn n counts the difference between the number of heads and tails, an excess of heads if positive. The second form of the local limit theorem is useful for estimating the probability that Tn takes a value close to its average (2p 1)n.

Remark. The following version of Stirling’s Formula.follows from the statement of the First Form of the Local Limit Theorem. However, note that the proof of the Local Limit Theorem uses the Moderate Deviations Theorem. The proof of the Moderate Deviations Theorem uses the Optimization Extension of the de Moivre-Laplace Central Limit Theorem. Step 1 of the proof of the Optimization Extension uses Stirling’s Formula. So this is not a new proof of Stirling’s Formula for binomial coefficients. It is a long way to derive the asymptotics for binomial coefficients from the usual Stirling Formula.

Corollary 1.

n k = 2 π 2n n exp 2 n(k n2)2 + o(1)

uniformly for k .

Proof. Use p = 12 in the First Form of the Local Limit Theorem. □

Theorem 2 ( Local Limit Theorem, Second Form). Set Tn = 2Sn n, then

n Tn = k = 2 π p 1 pk2 2p(1 p) n n exp k2 2n + o(1)

uniformly for k such that n + k is even.

Proof.

n Tn = k = n 2Sn n = k = n Sn = n + k 2 = n n+k 2 pn+k 2 (1 p)nk 2 Using the statement of the Corollary = 2 πpn+k 2 (1 p)nk 2 2n n exp 2 n n 2 + k 2 n 2 2 + o(1) = 2 π p 1 pk2 2p(1 p) n n exp k2 2n + o(1) .

Remark. Note that the First Form and the Second Form of the Local Limit Theorem say the same thing in the symmetric case p = 12.

Corollary 2. Let K be a fixed finite subset of that contains at least one even number and one odd number. Then

lim n1 n ln n Tn K = ln 2p(1 p) .

Proof. The Second Form of the Local Limit Theorem says that the probability that Tn is in a fixed finite subset of decreases exponentially as n approaches infinity. □

Discussion and Extensions

As the Second Form of the Local Limit Theorem indicates, to state a Local Limit Theorem for sums of random variables more general than Bernoulli random variables will take some care. For example, if the summands X1,X2, are all even valued, there is no way the sum X1 + + Xn can be odd so a Local Limit Theorem will require at least an additional hypothesis while the Central Limit Theorem will still hold.

Definition. We say that h is the maximal span of a density f if h is the largest integer such that the support of f is contained in the affine subset {b + kh : k = ,2,1, 0, 1, 2,} of for some b.

Let ϕ(x) = 1 2πex22 be the standard normal density.

Theorem 3 (Gnedenko’s Local Limit Theorem). Let X1,X2, be independent random variables with identical density f with finite mean μ and finite variance σ2 and maximal span equal to 1. Let Sn = X1 + + Xn. Then

(nσ2) S n = k 1 (nσ2)ϕ((x nμ)(nσ2)) 0

uniformly in k as n .

Proof. This was proved by B. V. Gnedenko in 1948, [1], using characteristic functions. □

McDonald, [3], has more technical local limit theorems and further references to other generalizations.

The following example shows that any extension of the Local Limit Theorem to nonidentical random variables illustrates is complicated by the same problem of periodicity that already appears in the Second Form of the Local Limit Theorem above.

Example. Suppose the densities fm are fm(0) = 12, fm(1) = 12m, fm(2) = 12 12m. The first random variable will be either 0 or 1, each with probability 12. For m > 1, the random variables will “essentially” differ by 2. That is, the maximal span is “essentially” 2, but Gnedenko’s theorem will not hold. In fact, consider the histogram of the convolution of the distributions f1,f20 in Figure 2. This histogram is the distribution of the sum of the first 20 of the random variables.


PIC
Figure 2: Distribution of the sum of the first 20 of the random variables with nonidentical independent distributions (12, 12m, 12 12m).

Note that the distribution overall resembles the normal distribution, as expected from the Lindeberg Central Limit Theorem. However closer inspection show that the value of the distribution at symmetric distances around the mean 20 differ. That is the value of the distribution at 21 is greater than the value of the distribution at 19. This suggests that at least the uniform approach to the normal distribution at integer values will not hold.

Sources

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 9, [2]. The historical remarks and the generalizations of the Local Limit Theorem are adapted from [3].

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

The experiment is flipping a coin n times, and repeat the experiment k times. Then check the probability of a specific value and compare to the normal probability density. Also compare the logarithmic rate of growth to the predicted rate.

Scripts

Scripts

R

R script for Local Limit Theorem..

< 0.5 
< 10000 
< 1000 
upperintvalue < 10 
lowerintvalue < 0 
winLose < 2  (array( 0+(runif(nk) <= p), dim=c(n,k)))  1 
# 0+ coerces Boolean to numeric 
totals < colSums(winLose) 
# n..2..n binomial rv sample, size k 
 
stddev < sqrt(p(1p)n) 
prob < sum( 0+(totals == upperintvalue) )/
 
f1 < (sqrt(2/pi)) 
f2 < (p/(1p))ˆ(upperintvalue/2) 
f3 < ((2sqrt(p(1p)))ˆn)/sqrt(n) 
f4 < exp(upperintvalueˆ2/(2n)) ) 
theoretical < f1f2f3f4 
cat(sprintf(”Empirical_probability:_%f_n”, prob )) 
cat(sprintf(”Local_Limit_Theorem_estimate:_%f_n”, theoretical)) 
 
set < (totals >= lowerintvalue) & (totals <= upperintvalue) 
logintervalprobrate < (1/n)logsum( 0+(set))/k ) 
theoreticallograte < log( 2sqrt(p(1p)) ) 
cat(sprintf(”Empirical_log_rate:_%f_n”, logintervalprobrate )) 
cat(sprintf(”Theoretical_log_rate:_%f_n”, theoreticallograte
Octave

Octave script for Local Limit Theorem..

p = 0.5; 
n = 10000; 
k = 1000; 
 
upperintvalue = 10; 
lowerintvalue = 0; 
 
winLose = 2  (rand(n,k) <= p)  1; 
headsTotal = sum(winLose); 
# 0..n binomial rv sample, size k 
 
stddev = sqrt(p(1p)n); 
prob = sum( headsTotal == upperintvalue)/k; 
 
f1 = (sqrt(2/pi)); 
f2 = (p/(1p))ˆ(upperintvalue/2); 
f3 = ((2sqrt(p(1p)))ˆn)/sqrt(n); 
f4 = exp(upperintvalueˆ2/(2n)) ); 
theoretical = f1f2f3f4; 
 
disp(”Empirical_probability:”), disp( prob ) 
disp(”Local_Limit_Theorem_estimate:”), disp( theoretical ) 
 
set = (headsTotal >= lowerintvalue) & (headsTotal <= upperintvalue); 
logintervalprobrate = (1/n)logsum(set)/k ); 
theoreticallograte = log( 2sqrt(p(1p)) ); 
 
disp(”Empirical_log_rate:”), disp( logintervalprobrate ) 
disp(”Theoretical_log_rate:”), disp( theoreticallograte )
Perl

Perl PDL script for Local Limit Theorem..

use PDL::NiceSlice; 
use PDL::Constants qw(PI); 
 
$p = 0.5; 
$n = 10000; 
$k = 1000; 
 
$upperintvalue = 10; 
$lowerintvalue = 0; 
 
#note order of dims!! 
$winLose = 2  ( random( $k, $n ) <= $p )  1; 
 
# n..2..n binomial r.v. sample, size k 
#note transpose, PDL likes x (row) direction for implicitly threaded operations 
$totals = $winLose>transpose>sumover; 
 
$stddev = sqrt( $p  ( 1  $p )  $n ); 
 
$prob = ( ( $totals == $upperintval )>sumover ) / $k; 
 
$f1          = ( sqrt( 2 / PI ) ); 
$f2          = ( $p / ( 1  $p ) )∗∗( $upperintvalue / 2 ); 
$f3          = ( ( 2  sqrt( $p  ( 1  $p ) ) )∗∗$n ) / sqrt($n); 
$f4          = exp( $upperintvalue∗∗2 / ( 2  $n ) ) ); 
$theoretical = $f1  $f2  $f3  $f4; 
print ”Empirical_probability:_”,       $prob,        ”n”; 
print ”Local_Limit_Theorem_estimate:”, $theoretical, ”n”; 
 
$set = ( $totals >= $lowerintvalue ) & ( $totals <= $upperintvalue ); 
$logintervalprobrate = ( 1 / $n )  log( sum($set) / $k ); 
$theoreticallograte = log( 2  sqrt( $p  ( 1  $p ) ) ); 
print ”Empirical_log_probability_rate:_”, $logintervalprobrate, ”n”; 
print ”Theoretical_log_rate:”,            $theoreticallograte,  ”n”;
SciPy

Scientific Python script for Local Limit Theorem. .

import scipy 
 
p = 0.5 
n = 10000 
k = 1000 
 
upperintvalue = 10 
lowerintvalue = 0 
 
winLose = 2  (scipy.random.random((n,k))<= p)  1 
# Note Booleans True for Heads and False for Tails 
totals = scipy.sum(winLose, axis = 0) 
# n..2..n binomial r.v. sample, size k 
# Note how Booleans act as 0 (False) and 1 (True) 
 
stddev = scipy.sqrt( p  ( 1p ) n ) 
 
prob = (scipy.sum( totals == upperintvalue )).astype(’float’)/k 
# Note the casting of integer type to float to get float 
 
f1          = ( scipy.sqrt( 2 / scipy.pi ) ); 
f2          = ( p / ( 1  p ) )∗∗( upperintvalue / 2 ); 
f3          = ( ( 2  scipy.sqrt( p  ( 1  p ) ) )∗∗n ) / scipy.sqrt(n); 
f4          = scipy.exp( ( upperintvalue∗∗2 / ( 2.0  n )) ); 
# Note the use of 2.0 to force integer arith to floating point 
theoretical = f1  f2  f3  f4; 
 
print ”Empirical_probability:_”, prob 
print ”Moderate_Deviations_Theorem_estimate:”, theoretical 
 
set = ( totals >= lowerintvalue ) & ( totals <= upperintvalue ); 
logintervalprobrate = ( 1 / n )  scipy.log( (scipy.sum(set)).astype(’float’) / k ); 
theoreticallograte = scipy.log( 2  scipy.sqrt( p  ( 1  p ) ) ); 
print ”Empirical_log_probability_rate:_”, logintervalprobrate 
print ”Theoretical_log_rate:”,            theoreticallograte

__________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Modify the value of p in a script, say to p = 0.51, and investigate the convergence and the rate of convergence to the normal density function.
  2. Modify the value of n in a script to a sequence of values and investigate the rate of convergence of the logarithmic rate.

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   B. V. Gnedenko. On the local limit theorem in the theory of probability. Uspekhi Mat. Nauk, 3:187–194, 1948.

[2]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

[3]   D. R. McDonald. The local limit theorem: A historical perspective. Journal of the Iranian Statistical Society, 4(2):73–86, 2005.

__________________________________________________________________________

Links

Outside Readings and Links:

  1. L. Breiman, Probability, 1968, Addison-Wesley Publishing, Section 10.4, page 224-227.
  2. D. R. McDonald, “The Local Limit Theorem: A Historical Perspective”, Journal of the Royal Statistical Society, Vol. 4, No. 2, pp. 73-86.
  3. Encyclopedia of Mathematics, Local Limit Theorems.

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable effort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on April 26, 2015