Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar


QuestionofDay

Question of the Day


Key Concepts

Key Concepts

  1. Markov’s Inequality: Let X be a random variable taking only non-negative values. Then for each a > 0
    P[X > a] < E[X]/a;
  2. Chebyshev’s Inequality: Let X be a random variable. Then for a > 0
    P[|X - E[X] | > a] < Var[X]- a2
  3. Weak Law of Large Numbers For e > 0
     [ ||S || ] Pn ||-n-- p|| > e --> 0 as n --> oo n

    and the convergence is uniform in p .

  4. Let f be a real function that is defined and continuous on the interval [0, 1] . Then
     || sum n ( ) ( ) || sup ||f(x) - f k- n xk(1- x)n-k||--> 0 0<x <1| n k | k=0

    as n --> oo .


Vocabulary

Vocabulary

  1. The family of polynomials
     ( ) n k n-k Bn,k(t) = x (1 - x) k

    are called the Bernstein polynomials.


Mathematical Ideas

Mathematical Ideas

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 5

Proof of the Weak Law Using Chebyshev’s Inequality

Proposition 1 (Markov’s Inequality) Let X be a random variable taking only non-negative values. Then for each a > 0

P[X > a] < E[X]/a;

Proof 1

P[X > a] = E[IX >a] integral = dP integral X >a x- < a dP 1 < --E[X] a
Q.E.D.

Proposition 2 (Chebyshev’s Inequality) Let X be a random variable. Then for a > 0

 Var[X] P[|X - E[X] | > a] < ----2-- a

Proof 2

This immediately follows from Markov’s inequality applied to the non-negative random variable (XE[X])2 . Q.E.D.

Theorem 1 (Weak Law of Large Numbers) For e > 0
 [ | | ] P ||Sn-- p|| > e --> 0 as n --> oo n |n |

and the convergence is uniform in p .

Proof 3

The variance of the random variable Sn is np(1 - p) . Rewrite the probability as the equivalent event:

 [|| ||] [|| ||] Pn |Sn- - p| = Pn |Sn-- p| . | n | | n |

By Chebyshev’s inequality

Pn [| Sn - np |> ne] < Var[Sn]-= p(1---p) 1- (ne)2 e2 n

Since p(1- p) < 1/4 , the proof is complete. Q.E.D.

Note that the proof demonstrates that

 [||S || ] Pn ||--n- p||> e = O(1/n) n

uniformly in p .

Bernstein’s Proof of the Weierstrass Approximation Theorem

Theorem 2 Let f be a real function that is defined and continuous on the interval [0,1] . Then

 | | | sum n ( ) ( ) | sup ||f(x) - f k- n xk(1- x)n-k||--> 0 0<x <1| k=0 n k |

as n --> oo .

Proof 4

  1. Fix e > 0 . Since f continuous on the compact interval [0, 1] it is uniformly continuous on [0,1] . Therefore there is an j > 0 such that |f (x)- f(y)|< epsilon if |x- y|< j .
  2. The expectation E[f (Sn/n)] can be expressed as a polynomial in p :
     [ ( )] sum ( ) sum ( ) ( ) En f Sn- = nf k- Pn[Sn = k] = nf k- n pk(1 - p)n-k. n k=0 n k=0 n k
  3. By the Weak Law of Large Numbers, for the given e > 0 , there is an n0 such that
     [| | ] P ||Sn-- p|| > j < e. n |n |
  4. | [ ( ) ]| | ( ( ) ) | | Sn | || sum n k || ||En f --- - f(p) ||= || f -- - f(p) Pn[Sn = k]|| n k=0 n
  5. Apply the triangle inequality to the right hand side and express in terms of two summations:
     sum ( ( ) ) sum ( ( ) ) < f k- - f (p) P [S = k]+ |f k- |+ |f (p)| P [S = k] k n n n k n n n |n-p|<j |n-p|>j

    Not the second application of the triangle inequality on the second summation.

  6. Now estimate the terms:
     sum sum < ePn[Sn = k] + 2 sup |f (x) |Pn[Sn = k] |k-p|<j |k-p|>j 0<x<1 n n
  7. Finally, do the addition over the individual values of the probabilities over single values to re-write them as probabilities over events:
     ||S || ||S || = ePn[||-n-- p|| < j] + 2 sup |f (x)| Pn[||--n - p||> j] n 0<x<1 n
  8. Now apply the Weak Law to the second term to see that:
    || [ ( ) ]|| |En f Sn- - f (p) |< e + 2e sup |f(x)|. | n | 0<x <1

    This shows that ||E [f (Sn-)- f(p)]|| n n can be made arbitrarily small, uniformly with respect to p , by picking n sufficiently large.

Remark 1 The family of polynomials

 ( ) B (t) = n xk(1 - x)n-k n,k k

are called the Bernstein polynomials. The Bernstein polynomials have several useful properties:

  1. Bi,n(t) = Bn -i,n(1 - t)
  2. Bi,n(t) > 0
  3.  sum ni=0Bi,n(t) = 1 for 0 < t < 1 .

Corollary 1 The polynomial uniformly approximating the continuous function f(x) on the interval [a,b] is

 sum n ( ) ( ) ( )k ( )n- k f a + (b - a)k n x---a- b---x- k=0 n k b - a b - a


Problems to Work for Understanding


Reading Suggestion:

  1. Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Sections 1.2 and Chapter 4.
  2. An Introduction to Probability Theory and Its Applications, Volume 1, William Feller, John Wiley and Sons, 1968, ISBN-13: 978-0471257080, pages 228-247.
  3. Probability, by Leo Breiman, SIAM: Society for Industrial and Applied Mathematics; Reprint edition (May 1, 1992), Philadelphia, 1992, ISBN-13: 978-0898712964.


Outside Readings and Links:

  1. Virtual Laboratories in Probability and Statistics ¿ Binomial
  2. Weisstein, Eric W. ”Weak Law of Large Numbers.” From MathWorld-A Wolfram Web Resource. Weak Law of Large Numbers.
  3. Wikipedia, Weak Law of Large numbers


Last modified: [an error occurred while processing this directive]