Appel W. Mathematics for Physics and Physicists

Подождите немного. Документ загружается.

Bienaymé-Tchebychev inequality 547

Irénée Jules Bienaymé (1796—1876), studied in Bruges and then at

the lycée Louis-le -Grand, and took par t in the defense of Paris

in 1814. After going to the École Polytechnique, his scholarly life

was perturbed by political turbulence (the school closed for some

time). He obtained a position at the mili tary school of Saint-Cyr

and then became a general inspector in the Ministry for Finance.

After the 1848 revolution, he became professor of probability at

the Sorbonne and a member of the Académie des Sciences in 1852.

He had a knack for language and translated in French the works

of his friend Tchebychev. He also had a knack for disputing with

others, suc h as Cauchy or Poisson.

20.9.c Example: Poisson distribution

The following is easy to check:

THEOREM 20.68 Let X be an r.v. w ith a Poisson distribution with parameter λ.

Then the characteristic function of X is

(ν) = E



iνX



= exp



λ(e

iν

−1)



Let X

and X

be two independent r.v. with Poisson distributions with parameters

and λ

, respectively. Then the r.v. X = X

+ X

has a Poisson distribution with

parameter λ = λ

+ λ

20.10

Bienaym

e-Tchebychev inequality

20.10.a Statement

Given a random variable X , its standard deviation mesaures the average

(quadratic) dist ance to th e mean, that is, the probability that the actual value

of X be far from th e expectation of X . The Bienaymé-Tchebychev inequality

is a way to quantify this idea, giv ing an upper bound for the probability that

X differs from its expectat ion by a given a mount.

THEOREM 20.69 (Bienaym

e-Tchebychev inequality) Let (Ω, Σ, P) be a proba-

bility space and let X be a real-valued random variable on Ω such that E(X

) < +∞.

Let m = E(X ) be the expectation of X and let σ

be its variance. Then, for any

ǫ > 0, we have



|X −m| ¾ ǫ



, or equivalently P



|X −m| ¾ ǫσ



548 Random variables

Pafnouti Tchebychev (1821—1894) entered Moscow University in

1837, and Saint Petersburg University in 1847. He studied prime

numbers (proving in particular that there always exists a prime

number p such that n < p ¶ 2n for all n ¾ 1, and giving the

ﬁrst correct estimate for th e o rder of magnitude of the number of

primes less a large quantity X , which was reﬁned into the prime

number theorem in 1896 by Hadamard and de la Vallée Poussin).

He was also interested i n mechanics, in quadratic forms (Tcheby-

chev polynomials), and in probability theory, where he published

four important p apers. His works were described very clearly by

Andrei Markov. He died while drinking tea, like Euler, which is

rigorous proof that mathematicians should drink coffee.

In the other direction, knowing the actual value of X for some experience

ω, this inequality g ives an estimate of the error in assuming that this value is

equal to the average value m.

Example 20.70 Let X be a random variable with expectation m and standard deviation σ. The

probability that the result X (ω) of an experiment dif fer from m by more than 4σ is at most

6, 25 %.

To prove the inequality, we start with the following lemma:

LEMMA 20.71 (Ma rkov inequality) Let (Ω, Σ, P) be a probability space and let X

be a non-negative random variable such that E(X ) < +∞ (i.e., in the terminology of

analysis, w e consider a measure space and a non-negative integrable function). For any

t ∈ R

+∗

, we have



{X ¾ t}



Ω

X (ω) dP(ω).

Proof. This is clear by looking at the following picture:

t P({X ¾ t})

Ω

X (ω) dP(ω)

X (ω)

The dark region is a rectangle with height t and width P



{X ¾ t}



. Of course, it

may well be something else than a rectangle (for instance many rectangles, depending

on the structure of the event {X ¾ t}), but in any case the dark region has measure

t P



{X ¾ t}



. It is clear that this measure is smaller than or equal to

Ω

X (ω) dP(ω),

since X ¾ 0.

“Mathematicians are machines for turning coffee into theorems”, Paul Erdös (or Alf red

Rényi).

Bienaymé-Tchebychev inequality 549

More rigorously, we can write

0 ¶ t χ

{X ¾t}

(ω) ¶ X (ω)

(since t χ

{X ¾t}

(ω) is equal to t or 0). Integrating over Ω with respect to the probability

measure dP, the inequality follows.

Applying this lemma to



X − E(X )



/σ

and t = ǫ

, we derive the

Bienaymé-Tchebychev inequality.

20.10.b Application: Buffon’s needle

Buffon

computed in 1777 that when throwing a needle of length a onto a

ﬂoor with ﬂoorboards of width b ¾ a, the probability t hat the needle will

cross a line between two boards is equal to

πb

. Take a = b to simplify, and

let p = 2/π denote the resulting probability.

Suppose the needle is thrown N times, where N is very large. If we

let X denote the random variable corresponding to the number of times

the needle ha s crossed a line between two planks, it follows that X has a

binomial distribution B(N , p). Thus the average number of needles crossing

a line is given by t he e xpectation E(X ) = p N , and the standard deviation

of X is σ

= N p(1 − p). We can expect than when N is ver y large, the

ratio X /N should be close to p = 2/π, given an “experimental” numerical

approximation of π (this experiment has been performed a number of times,

and many simulations can be found on the Web).

The question that may be asked is then: to obtain a approximation of π

with a given precision, how many t imes should the needle be thrown? For

instance, suppose I want to obtain the value of π with an error of at most

1/1000, how many times should I throw the needle to be certain that the

resulting value will b e correct with a probability of 99%?

The simplest estimate for such a question can be obtained simply from the

Bienaymé-Tchebychev inequality, which we recall for convenience:



|X − N p| ¾ ǫσ



In order for the probability that X satisﬁes the inequality to be at most 1%,

we must take 1/ǫ

= 1/100; hence we take ǫ =

100 = 10. Let π

′

be the

value of π obtained experiment ally, namely π

′

= 2N /X . We want π

′

satisfy π −10

−3

¶ π

′

¶ π + 10

−3

, and therefore for the number X of needles

crossing a line to sat isfy

π + 10

−3

¶ X ¶

π −10

−3

Georges Leclerc, comte de Buffon (170 7—1788), famous naturalist, author of the monu-

mental Histoire naturelle, was also interested in the theo ry of probability.

550 Random variables

Writ ing |X − N p| = ǫσ with values

X =

π ±10

−3

(both signs “+” and “−” lead to the same result), we ﬁnd

N =

2 ·10

−3

N p(1 − p), hence N =

4 · 10

−6

p(1 − p)

in other words, N = 560 million, more or less. It is not very reasonable to

expect that π can be computed in this manner.

However, this is a very coarse estimate, since the Bienaymé-Tchebychev

inequality holds w ith no assumptions on the distribution of the random

variable being considered. If we t ake into account the precise distribution of

X , a more precise result can be derived. But th is remains of the same order of

magnitude, and does not really affect the discussion. For instance, s ince the

binomial d istribution may be approximated by a gaussian distribution for N

such that N p(1 − p) is very large, we can ﬁnd numerically (using tables or

computations of the function erf(x)) a value N ≈ 150 million th rows, which

is only better by a factor of 3.

20.11

Independance, correlation, causality

It is very important to distinguish b etween independance, correlation, a nd

causality. In Example 20.47, we saw that two dependent events ca n be uncorre-

lated.

Two events are causally linked if one is the cause of the other. For instance,

statistics show that road accidents are more frequent on Saturdays t han other

days of the week (t hus they are correlated). There is causality here: usually

more alcohol is consumed on Saturday, leading to a higher rate of accidents.

However, events may be correlated without causa lit y. An example is given

by Henri Broch [15]: in villages in Alsace, statistics show t hat the number of

births per year is highly correlated with th e number of storks (the correlation

is close to 1). Should we conclude that storks carry babies h ome (which would

mean caus ality)?

David Ruelle, in his excellent book [77], mentions events which are causally

linked but uncorrelated, which is more surprising. Consider, on the one h and,

the position of the planet Venus in the sky, and on the other hand the weather

There is in fact a hidden “causal” explanation: the more families in a village, the more

houses, hence the more c h imneys, and the more room for storks. This causality is not because

of the two events discussed, but because of a third, linked independently with both.

Independance, correlation, causality 551

one month after the date of observation. We know very well tha t weather [86]

is a highly chaotic system, and hence is very sensitive to initial conditions. The

position of Venus on a given day is therefore highly likely to inﬂuence the

weather one month later. There is therefore strong causality (and dependence)

between the position of Venus and the weather. However, no correlation can

be observed. Indeed, other factors (the day of the year, the weather in previous

months, the solar activity, the posit ion of other planets, etc.) are equally or

more crucial in the evolution of th e weather than the position of Venus.

Looking only at Venus and “averaging” over all other variables, no t race of the

inﬂuence of this fair planet will be noticeable. Ca us ality without correlation.

552 Random variables

Sidebar 8 (Riemann-Stieltjes integral) Let α : R → R be a n increasing func-

tion (not necessarily continuous). A measure µ

is deﬁned on open intervals b y



]a, b[



= α( b

−

)−α(a

) (where α(b

−

) denotes the limit of α(x) as x tends

to b on the left, and α(a

), similarly, is the limit as x tends to a on the right; both

are well deﬁned because α is increasing). This measure may be extended to Borel sets

in R uniquely, by deﬁning





)

if B

∩ B

= ∅ for i 6= j. This yields a Borel measure, that is, a measure on

(X , B), with the property that



[a, b]



= α(b

) −α(a

−

), µ



[a, b[



= α( b

−

) −α(a

−

), etc.

The integral of a function f with respect to this measure is deﬁned as described in

this chapter, and is denoted

f dµ

f dα, and called the Riemann-Stieltjes

integral of f with respect to α. It satisﬁes the properties stated in Theorem 2.28 on

page 65. There are associated spaces L



R, dα



and L



[a, b] , dα



, which are

complete by the Riesz-Fischer theorem.

Finally, if α is of C

class, one can show that

f dα =

f (x) α

′

(x) dx =

f (x)

dα

for any func tion f integrable with respect to µ

This construction is interesting in part because it gives a deﬁnition of certain

integrals or “generalized functions” without requiring the theory of distributions.

Example 20.72 Let α(x) = 1 for x ¾ 0 and α(x) = 0 otherwise. This is an increasing

function. The assoc iated measure µ

is called the Dirac measure; it has th e property

that any Dirac-measurable functio n is integrable and

f dα = f (0) for any f . Note that

functions in L

(R, dα) are always deﬁned up to equality almost everywhere, but t h ere {0}

is of measure 1 for µ

, so it is not a negligible set.

Let P =



x ∈ R ; µ



{x}



6= 0



(the set of discontinuities of α). One can

deﬁne a measure µ

by µ

(X ) = µ

(P ∩ X ), and moreover µ

= µ

− µ

also a Borel measure.

Chapter

Convergence of

random variables:

central limit theorem

Guildenstern (Flips a coin): The law of averages, if I have got this

right, means that if six monkeys were thrown up in the air for

long enough they would land on their tails about as often as they

would land on their —

Rosencrantz: Heads. (He picks up the coin.)

Tom Stoppard, Rosencrantz & Guildenstern are dead [87]

21.1

Various types of convergence

We are going to deﬁne three types of convergence of a sequence (X

)

n∈N

of random variables to a limit X .

The ﬁrst two are parallel to well-known concepts in the theory of integra-

tion.

Let (X , T , µ) be a measure space (for instance, X = R, T = B, the Borel

σ-algebra, and µ the Lebesgue measure). A sequence ( f

)

n∈N

of measurable

functions on X converges almost everywhere to a measurable function f

if there e xists a measurable subset N ⊂ X such that µ(N) = 0 and, for

all x /∈ N , the s equence



(x)



n∈N

converges to f (x). In other words,

554 Central limit theorem

the sequence ( f

)

n∈N

converges simply to f for almost all x. In probability

language, we have the following a nalogous deﬁnition:

DEFINITION 21.1 (Almost sure convergence) Let (Ω, Σ, P) be a probability

space, (X

)

n∈N

a sequence of random variables, and X a random variable.

Then (X

)

n∈NN

converges almost surely to X, denoted X

c.a.s.

−−→ X, if there

exists a subset N ⊂ Ω with probability zero such that, for any ω /∈ N , the

sequence



(ω)



n∈N

converges to X .

In integration theory, a nother notion is convergence in measure: a sequence

( f

)

n∈N

of measurable functions converges in measure to a measurable func-

tion f if

∀ǫ > 0 lim

n→∞



x ∈ X ;



f (x) − f

(x)



¾ ǫ



= 0.

In other words, with a margin of error ǫ > 0, the subset of those points where

is “too far” from f shrinks down to nothingness as n becomes larger and

larger.

Similarly, we have the probabilistic a nalogue:

DEFINITION 21.2 (Convergence in probability) Let (X

)

n∈N

be a sequence of

r.v. and let X b e a r.v. The sequence (X

)

n∈NN

converges in probability to X,

denoted X

c.p.

−→ X, if

∀ǫ > 0 lim

n→∞



ω ∈ Ω ;



X (ω) − X

(ω)



¾ ǫ



= 0.

In general, almost everywhere convergence does not imply convergence in

measure. However, when the measure space has ﬁnite total measure (µ(X ) <

+∞), this is the case (for instance, this follows from Egorov’s theorem, stated

on page 69). The case of probability spaces is of this type, since P(Ω) = 1, so

we deduce:

THEOREM 21.3 Almost sure convergence implies convergence in probability.

The third t ype of convergence, which is very importa nt in probability, is

the following:

DEFINITION 21.4 (Convergence in distribution) A sequence (X

)

n∈N

of r.v.

with d istribution functions (F

)

n∈N

converges in distribution if there exists

a distribution function F such that the sequence (F

)

n∈N

converges simply

to F at any point of continuity of F . This function determines the limit

distribution of the sequence (X

)

n∈N

If X is an r.v. with distribution function F , then we say that (X

)

n∈NN

converges in distribution to X, and we denote X

c.d.

−→ X.

The law of large numbers 555

Note that if X

c.d.

−→ F , then we have

P(X

¶ x) −−−→

n→∞

P(X ¶ x)

for any x ∈ R which is a point of continuity of F .

Convergence in distribution is t he weakest of the three types of conver-

gence introduced. In particular, we have the implications:

c.a.s.

−−→ X ) =⇒ (X

c.p.

−→ X ) =⇒ (X

c.d.

−→ X ).

Certainly, convergence in distribution does not imply convergence in proba-

bility or almost sure, since the random variables X

and X may have nothing to

do with each other; in fact, they may even be deﬁned on different probab ility

spaces, since only the distribution function matters! It is perfectly possible to

have two r.v. X and Y with the same distribution, but which are never equal

(see page 524).

21.2

The law of large numbers

Consider a game of dce. I roll the die, and you must announce the result

in advance (with money at stake). If I only roll the die once, there is nothing

interesting you can really say (except if my die was false, but I would not say

so in advance). However, if I roll the die ten times, and you must guess the

sum of the results of the ten throws, t here is much more you can say. More

precisely, you may resonably think that the sum will be close to 35, maybe

33 or 38, but most certainly not 6 (there is only one chance in 6

, that is,

one in six ty million to obtain a 1 ten times in a row; you may as well play

the lottery). And as I roll the die more and more times, you will be able to

bet with increasing conﬁdence that the sum will be roughly n ×3.5. This, in

effect, is what the weak law of large numbers makes precise

THEOREM 21.5 (Weak law of large numbers) Let (Ω, Σ, P) be a probability

space and let (X

)

n∈N

∗

be a sequence of square integrable independent r.v. with the

same expectation m (i.e., for all n, we have E(X

) = m) and the same variance σ

Deﬁne

+ ···+ X

This theorem was proved (rigorously) for the ﬁrst time by the Swiss mathematician James

(Jakob) Bernoulli (1654—170 5) (who also disc overed the famous Bernoulli numbers), in his

treatise Ars Conjectandi, published in 1713. His nephew Daniel Bernoulli (1700—1782) also

studied probability theory, as well as hydrodynamics. A generalization of Be rnoulli ’s result was

given by the marquis de Laplace , in his Théorie analytique des probabilités.

556 Central limit t heo rem

Then the sequence (Y

)

n∈N

∗

converges in probability to the constant random variable

equal to m (i.e, Y (ω) = m for all ω ∈ Ω). In other words, we have

∀ǫ > 0 P



−m| ¾ ǫ



−−−→

n→∞

Proof. The simplest proof uses the Bienaymé-Tche bychev inequality: notice that

E(Y

) = m and then write



−m| ¾ ǫ



)

Since the random variables X

, . . . , X

are independent, th e Bienaymé identity 20.65

yields the formula

(n Y

) = σ

+ ···+ X

) = n σ

hence σ

) =

nσ

from whi ch we derive P



−m| ¾ ǫ



nǫ

−−→

n→∞

Remark 21.6 It is possible to show that this result is still valid without assuming that the vari-

ables are square integrable (but they are always integrable). The proof is much more involved,

however.

There is a stronger version of the law of large numbers, due to Kolmogorov

and Khintchine (see, e.g., [33]):

THEOREM 21.7 (Str ong la w of large numbers) Let (X

)

n∈N

be a sequence of in-

dependent identically distributed r.v. Assume that the X

are integrable, and let m

denote their common expectation. Then the sequence of Cesàro means converges almost

surely to m: we have

+ ···+ X

c.a.s.

−−→ m.

21.3

Central limit theorem

Let us come back to our game of dice. We know, according to t he law of

large numbers, that we must bet that the sum is close to the average. It would

be interesting to know how the sequence (Y

)

n∈N

∗

of Cesàro means converges

to the constant random variable m. And more precisely, wha t should we expect

if we bet on a value other than t he average?

He showed in particular that it is possible to cut a cake into 65, 537 equal pieces with

straightedge, compass, and knife. A very useful trick if you plan a large wedding.