Structures et algorithmes aleatoires

Description

ENS 2011-2012 Structures et algorithmes aleatoires 18 novembre 2011

• random algorithms


• probability


• notation concerning


• hoeffding's inequality


• proba- bility theory


• famous discrete probability


• used only

Sujets

• Probability
• Hoeffding's inequality

Informations

• Publié par: pefav
• Nombre de lectures: 17
• Langue: English

Extrait

ENS 20112012

Structures et algorithmes aléatoires

18 novembre 2011

2

Contents

1

2

3

4

5

6

7

Events and probability 1.1 Outcomes and events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Probability and independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Conditional probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Random variables 2.1 Distribution and expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Famous discrete probability distributions . . . . . . . . . . . . . . . . . . . . . . 2.3 Conditional expectation and martingales . . . . . . . . . . . . . . . . . . . . . . .

Generating functions 3.1 Definition, examples and main properties . . . . . . . . . . . . . . . . . . . . . . 3.2 A computational tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 The branching process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Inequalities and bounds 4.1 Jensen’s inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Markov’s inequality and Chernoff’s bounds . . . . . . . . . . . . . . . . . . . . . 4.3 Poisson bounding of multinomial events . . . . . . . . . . . . . . . . . . . . . . . 4.4 Hoeffding’s inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

The strong law of large numbers 5.1 Almostsure convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Limits of expectations, expectation of limits . . . . . . . . . . . . . . . . . . . . . 5.3 Kolmogorov’s strong law of large numbers . . . . . . . . . . . . . . . . . . . . . .

The probabilistic method 6.1 Existence proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Lovasz’s local lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 First and second moment methods . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Random algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Growth phenomena in random graphs 7.1 Percolation on the infinite grid . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

5 5 8 14

19 19 29 37

49 49 52 56

61 61 63 70 73

79 79 85 89

95 95 99 103 108

117 117

4

CONTENTS

Chapter

Events

1.1

1

and

probability

Outcomes and events

The study of random phenomena requires a clear and precise language. That of proba bility theory features familiar mathematical objects, such as points, sets and functions, which however receive a particular interpretation: points areoutcomes(of an experi ment), sets areevents, functions arerandom numbers. The meaning of these terms will be given just after we recall the notation concerning operations on sets,union,intersection, andcomplementation.

Samplespaceandevents

IfAandBare subsets of some set Ω,A∪Bdenotes their union andA∩Btheir intersection. In this book we shall denote byAthe complement ofAin Ω. The notation A+B(thesumofAandB) implies by convention thatAandBaredisjoint, in which P ∞ ∞ case it represents the unionA∪Bthe notation. Similarly, A k is used for∪A k k=1 k=1 only when theA k ’s are pairwise disjoint. The notationA−Bis used only ifB⊆A, and it stands forA∩Bparticular, if. In B⊆A, thenA=B+ (A−B). Theindicator functionof the subsetA⊆Ω is the function 1 A : Ω→ {0,1}defined by  1 ifω∈A , 1 A (ω) = 0 ifω6∈A.

Random phenomena are observed by means of experiments (performed either by man or nature). Each experiment results in anoutcome. The collection of all possible outcomes

5

6

CHAPTER 1.

EVENTS AND PROBABILITY

ωis called thesample spacesubsetΩ. Any Aof the sample space Ω can be regarded as a representation of someevent.

Example 1.1.1:Tossing a die, take 1.The experiment consists in tossing a die once. The possible outcomes areω= 1,2, . . . ,6 and the sample space is the set Ω = {1,2,3,4,5,6}subset. The A={1,3,5}is the event “result is odd.”

Example 1.1.2:Throwing a dart.The experiment consists in throwing a dart at a 2 wall. The sample space can be chosen to be the plane . An outcome is the position R 2 2 ω= (x, yThe subset) hit by the dart. A={(x, y);x+y >1}is an event that could be named “you missed the dartboard” if the dartboard is a disk centered at 0 and of radius 1.

Example 1.1.3:Heads and tails, take 1.The experiment is an infinite succession of coin tosses. One can take for sample space the collection of all sequencesω={x n } n≥1 , wherex n = 1 or 0, depending on whether thenTheth toss results in heads or tails. subsetA={ω;x k = 1 fork= 1 to 1,000}is a lucky event for anyone betting on heads!

The language of probabilists The probabilists have their own dialect. They say that outcomeωrealizesindexrealize eventAifω∈Ainstance, in the die model of Example 1.1.1, the outcome. For ω= 1 realizes the event “result is odd”, since 1∈A={1,3,5}. Obviously, ifωdoes not realize A, it realizesA. EventA∩Bis realized by outcomeωif and only ifωrealizes bothA andB. Similarly,A∪Bis realized byωif and only ifat leastone event amongAand BTwo eventsis realized (both can be realized). AandBare calledincompatiblewhen A∩B=∅other words, event. In A∩Bis impossible: no outcomeωcan realize bothA andBthis reason one refers to the empty set. For ∅as theimpossibleevent. Naturally, Ω is called thecertainevent. P ∞ ∞ Recall now tAis u hat the notation k=1 k sed for∪A k only when the subsetsA k are k=1 pairwise disjoint. In the terminology of sets, the setsA 1 ,A 2 , . . .form apartitionof Ω if

∞ X A k = Ω. k=0

The probabilists then say that the eventsA 1 ,A 2 , . . .aremutually exclusiveandexhaus tive. They are exhaustive in the sense that any outcomeωrealizes at least one among them. They are mutually exclusive in the sense that any two distinct events among them are incompatible. Therefore, anyωrealizesone and only oneof the eventsA 1 , . . . , A n .

1.1.

OUTCOMES AND EVENTS

7

IfB⊆A, eventBis said toimplyeventA, becauseωrealizesAwhenever it realizesB.

The sigmafield of events Probability theory assigns to each event a number, theprobabilityTheof the said event. collectionFof events to which a probability is assigned is not always identical to the collection of all subsets of Ω. The requirement onFis that it should be a sigmafield:

Definition 1.1.1LetFbe a collection of subsets ofΩ, such that 1. the certain eventΩis inF,

2. ifAbelongs toF, then so does its complementA, and ∞ 3. ifA 1 , A 2 , . . .belong toF, then so does their union∪A k . k=1 One then callsFasigmafieldonΩ, here the sigmafield ofevents.

Note that the impossible event∅being the complement of the certain event Ω is in ∞ F. Note also that ifA 1 , A 2 , . . .belong toF, then so does their intersection∩A k k=1 (Exercise??).

Example 1.1.4:Trivial sigmafield, gross sigmafield.These are respectively the collectionP(Ω) of all subsets of Ω, and the sigmafield with only two members: {Ω,∅}

If the sample space Ω is finite or countable, one usually (but not always and not neces sarily) considers any subset of Ω to be an event. That isF=P(Ω).

n n Example 1.1.5:Borel sigmafield.TheBorel sigmafielddenotedon , B, is by R n definition the smallest sigmafield on that contains all rectangles, that is, all sets of R Q n the formI j , where theI j sets in this sigmafield. The ’s are arbitrary intervals of j=1 R are calledBorel sets. The above definition is not constructive and therefore one may wonder if there exists sets that arenotBorel sets. The theory tells us that there are indeed such sets, but they are in a sense “pathological”: the proof of their existence involves the “axiom of choice”. In practice, it is enough to know that all the sets for which you had been able to compute the volume in your earlier life are Borel sets.

Example 1.1.6:Heads and tails, take 2.(Example 1.1.3 ct’d). Take in the quoted exampleFto be the smallest sigmafield that contains all the sets{ω;x k = 1},k≥1. This sigmafield also contains the sets{ω;x k = 0},k≥1 (pass to the complements), and therefore (take intersections) all the sets of the form{ω;x 1 =a 1 , . . . , x n =a n }for alln≥1, alla 1 , . . . , a n ∈ {0,1}.

8

1.2

CHAPTER 1.

EVENTS AND PROBABILITY

Probability and independence

The axioms of probability TheprobabilityP(A) of an eventA∈ FAs ameasures the likeliness of its occurrence. function defined onF, the probabilityPis required to satisfy a few properties, called theaxioms of probability.

Definition 1.2.1A probability on(Ω,F)is a mappingP:F → R

1.0≤P(A)≤1,

2.P(Ω) = 1, and P P ∞ ∞ =P(A). 3.P( k= A k ) k=1 k 1

such that

Property 3 is calledsigmaadditivity. The triple (Ω,F, P) is called aprobability space, orprobability model.

Example 1.2.1:Tossing a die, take 2.An event(Example 1.1.1 ct’d). Ais a subset of Ω ={1,2,3,4,5,6}. The formula

|A| P(A) =, 6

where|A|is thecardinalofA(the number of elements inA), defines a probabilityP.

Example 1.2.2:Heads and tails, take 3.(Examples 1.1.3 and 1.1.6 ct’d). Choose probabilityPsuch that for any event of the formA={x 1 =a 1 , . . . , x n =a n }, where a 1 , . . . , a n are arbitrary in{0,1}, 1 P(A) = n . 2 Note that this does not define the probability of any event ofFthe theory tells. But us that there does exist such a probability satisfying the above equirement an that this probability is unique.

Example 1.2.3:Random point on the square, take 1.The following is a possible 2 2 model of a random point inside the unit square [0,[01] = ,1]×[0,1]: Ω = [0,1] ,F 2 2 is the collection of sets in the Borel sigmafieldBthat are contained in [0,1] . The theory tells us that there exists indeed one and only one probabilityPsatisfying the requirement P([a, b]×[c, d]) = (b−a)×(d−c), 2 called the Lebesgue measure on [0,and that formalizes the intuitive notion of “area”.1] ,

1.2.

PROBABILITY AND INDEPENDENCE

9

The probability of Example 1.2.1 suggests an unbiased die, where each outcome 1, 2, 3, 4, 5, or 6 has the same probability. As we shall soon see, probabilityPof Example 1.2.2 implies anunbiasedcoin andindependenttosses (the emphasized terms will be defined later).

The axioms of probability are motivated by the heuristic interpretation ofP(A) as theempirical frequencyof occurrence of eventA. Ifn“independent” experiments are performed, among whichn A result in the realization ofA, then the empirical frequency n A F(A) = n should be close toP(A) ifnis “sufficiently large.” (This statement has to be made precise. It is in fact a loose expression of the law of large numbers that will be given later on.) Clearly, the empirical frequency functionFsatisfies the axioms.

Basic formulas of probability We shall now list the properties of probability that follow directly from the axioms: Theorem 1.2.1For any eventA∈ F

and

P(A) = 1−P(A),

P(∅) = 0.

Proof.For a proof of (1.1), use additivity:

1 =P(Ω) =P(A+A) =P(A) +P(A).

Applying (1.1) withA= Ω gives (1.2).

Theorem 1.2.2Probability ismonotone, that is,

A⊆B=⇒P(A)≤P(B). (Recall the interpretation of the set inclusionA⊆B: eventAimplies eventB.)

Proof.For a proof, observe that whenA⊆B,B=A+ (B−A), and therefore

P(B) =P(A) +P(B−A) ≥P(A).

(1.1)

(1.2)



(1.3)

10

CHAPTER 1.

EVENTS AND PROBABILITY

Theorem 1.2.3We have thesubsigmaadditivityproperty : P ∞ ∞ P(∪A k )≤P(A k ). k=1 k=1

Proof. Observe that

where

∞ X ∞ ′ , ∪ =1 A k =A k k k=1 n o ′ k−1 A∩ ∪ k =A k A i . i=1

Therefore,  ! ∞ X ∞ ′ P(∪A) =P A k=1 k k k=1 ∞ X ′ =P(A). k k=1 ′ ′ ButA⊆A k , and thereforeP(A)≤P(A k ). k k



(1.4)



Sequential continuity This property comes close to being a tautology and is of great use. Theorem 1.2.4Let{A n } n≥1 be anondecreasingsequence of events, that is, for all n≥1, A n+1 ⊇A n .

Then

Proof.Write

and

Therefore,

∞ ) = li P(∪ =1 A n m n↑∞ P(A n ). n

A n =A 1 + (A 2 −A 1 ) +∙ ∙ ∙+ (A n −A n−1 )

∞ ∪ k=1 A k =A 1 + (A 2 −A 1 ) + (A 3 −A 2 ) +∙ ∙ ∙.

∞ X ∞ P(∪ k=1 A k ) =P(A 1 ) +P(A j −A j−1 ) j=2     n X = limP(A 1 ) +P(A j −A j−1 ) = limP(A n ). n↑∞   n↑∞ j=2

(1.5)