Structures et algorithmes aleatoires

De
Publié par

Niveau: Supérieur
Ecole Normale Superieure Polycopie de cours Structures et algorithmes aleatoires Auteur: M. Lelarge Redacteur: The Info Team Version preliminaire, merci d'envoyer vos remarques a

  • comparaison des processus sur le graphe

  • limite de la loi binomiale

  • inegalite de chebychev

  • transition de phase des graphes d'erdo˝s-renyi

  • temps d'execution de quicksort

  • theorie des graphes

  • distribution geometrique

  • variables aleatoires


Publié le : mardi 29 mai 2012
Lecture(s) : 18
Source : di.ens.fr
Nombre de pages : 46
Voir plus Voir moins

´Ecole Normale Superieure
´Polycopie de cours
Structures et algorithmes al´eatoires
Auteur:
R´edacteur:
M. Lelarge
The Info Team
marc.lelarge@ens.fr
Version pr´eliminaire, merci d’envoyer vos remarques `a marc.lelarge@ens.fr2 CONTENTS
Contents
I Probabilit´es discr`etes 5
1 Ev´enements et probabilit´es 7
1.1 Application: v´erifier les identit´es polynomiales . . . . . . . . . . . . . . . . . . . . 7
1.2 Axiomes des probabilit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Application: V´erification d’un produit de matrice . . . . . . . . . . . . . . . . . . . 9
2 Variables al´eatoires discr`etes et esp´erance 10
2.1 Distribution de probabilit´e discr`ete . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Esp´erance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Distribution g´eom´etrique et le probl`eme du collecteur de coupons . . . . . . . . . . 11
2.4 Application : temps d’ex´ecution de Quicksort . . . . . . . . . . . . . . . . . . . . . 12
3 Moments et d´eviations 14
3.1 In´egalit´e de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Variance et moments d’une variables al´eatoire . . . . . . . . . . . . . . . . . . . . . 14
3.3 In´egalit´e de Chebychev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Application: un algorithme randomiz´e qui calcule la m´ediane . . . . . . . . . . . . 16
4 Fonction g´en´eratrice et borne de Chernoff 18
4.1 Fonction g´en´eratrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 D´eriv´ees successives et moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Borne de Chernoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Des boules et des urnes 22
5.1 Le paradoxe des anniversaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Des boules et des urnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Limite de la loi binomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4 Approximation de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Martingales 26
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 In´egalit´es pour des Martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.3.1 Boules et urnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7 La transition de phase des graphes d’Erd˝os-R´enyi 28
7.1 Trois processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Po7.2 Etude de T =T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28c
7.3 Le processus d’exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.4 Comparaison des processus sur le graphe et branchement de Poisson . . . . . . . . 29
7.5 Les r´egimes sous-critiques et sur-critiques . . . . . . . . . . . . . . . . . . . . . . . 30
II La m´ethode probabiliste 33
8 Introduction `a la m´ethode probabiliste 35
8.1 Un premier exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.2 Th´eorie des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8.3 Th´eorie des nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
8.4 Combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36CONTENTS 3
9 Lin´earit´e de l’esp´erance 38
9.1 Division de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
9.2 Equilibrage de vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
9.3 Alt´erations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
9.4 Alt´erations suite : Recoloriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
10 La m´ethode du second moment 42
10.1 Th´eorie des nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
10.2 Remarques faciles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
10.3 Graphes al´eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
11 Le lemme de Lov´asz 44
11.1 Le Lemme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
11.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 CONTENTSPart I
Probabilit´es discr`etes
57
1 Ev´enements et probabilit´es
1.1 Application: v´erifier les identit´es polynomiales
Question:
6 3(x+1)(x−2)(x+3)(x−4)(x+5)(x−6)≡x −7x +25?
Soient deux polynˆomes F(X) et G(X), F(X) =G(X) ?
P iEcrire les polynˆomes sous forme canonique a X .ii
Id´ee. Utiliser de l’al´ea.
Algorithme. d = degr´e de F et G.
Choisit un entier r∈{1···100d}, uniform´ement au hasard.
Calcul F(r) et G(r) en complexit´e O(d).
• Si F(r) =G(r), alors F =G.
• Si F(r) =G(r), alors F =G.
L’algo se trompe si r est racine de F(x)−G(x) qui est un polynˆome de degr´e inf´erieur `a d.
Donc la probabilit´e que r soit une racine de ce polynomˆ e (et donc que l’algorithme se trompe) est
d 1inf´erieure `a = .
100d 100
1.2 Axiomes des probabilit´es
D´efinition 1.
Un espace de probabilit´e a 3 composantes :
1) Espace d’´epreuves Ω
2) Famille d’ensembles F ⊂ Ω, tribu sur Ω, repr´esente les ´ev´enements.
3) Une probabilit´eP :F →R.
Exemple.
Mod´elisation de 2 lancers de pi`ece. Ω ={(0,0),(0,1),(1,0),(1,1)}. L’´ev´enement le premier lancer
1donne pile est: {(0,0),(0,1)} de probabilit´e: P({(0,0),(0,1)}) = .
2
1P(00) =P(01) =··· =
4
D´efinition 2.
Une tribu sur Ω est une famille F de sous-ensembles de Ω tel que
1) Ω et ∅ sont dans F.
¯2) A∈F ⇒A∈F
S∞N3) (A ) ∈F ⇒ A ∈Fn n∈N nn=1
D´efinition 3.
Une (fonction de) probabilit´eP :F →R satisfait
1) ∀E ∈F,P(E)∈ [0,1]
2) P(Ω) = 1
F P∞ ∞
3) (E ,n≥ 1)∈F deux `a deux disjoints ⇒P( E ) = P(A ).n n nn=1 n=1
66´ ´8 CHAPTER 1. EVENEMENTS ET PROBABILITES
Remarque. • Dans ce cours, on se placera dans le cas des probabilit´es discr`etes, c’est `a
dire Ω fini ou d´enombrable. F est alors l’ensemble des sous-ensembles de Ω.
• On identifie les ´ev´enements aux ensembles ainsi E ∩E =E et E se r´ealisent, E ∪E =1 2 1 2 1 2
E ou E se r´ealisent, E \E =E sans E .1 2 1 2 1 2
Lemme 1.
• P(E ∪E ) =P(E )+P(E )−P(E ∩E )1 2 1 2 1 2
S P∞ ∞
• (E ,n≥ 1) P( E )≤ P(E ).n n nn=1 n=1
On reprend l’exemple pr´ec´edent: Ω ={1···100d}
d 1On consid`ere l’´ev´enement E: l’algorithme se trompe. P(E)≤ = .
100d 100
Am´elioration de l’algorithme :
1• une solution consiste `a tirer r entre 1 et 1000 d dans ce cas,P(E)≤ .
1000
• une autre solution consiste a` it´erer l’algorithme avec 100d : On effectue un ´echantillonnage
avec ou sans remplacement.
1Dans le cas avec remplacement, si F =G,P( se planter apr`es k it´erations )≤ .k100
D´efinition 4 (Ev´enements ind´ependants).

• E et F sont id´ependants E F siP(E∩F) =P(E)P(F).
• (E ) sont mutuellement ind´ependants si ∀I ⊂ J1···kKi i∈N
T Q
• P E = P(E ).i ii∈I i∈I
Pour consid´erer le cas avec remplacement, nous avons besoin d’introduire la notion de proba-
bilit´e conditionnelle.
D´efinition 5.
P(E∩F)
La probabilit´e conditionnelle de l’´ev´enement E sachant F estP(E|F) = P(F)
SiP(F) = 0, alorsP(E∩F) = 0 et on prendP(E|F) = 0

Remarque. [E F etP(F) = 0]⇒P(E|F) =P(E).
Toujours dans l’exemple pr´ec´edent, on consid`ere maintenant le cas sans remplacement : soit
E l’´ev´enement: `a la i-`eme it´eration, r est racine de F(x)−G(x). On a alors pour k≤d+1:i i
P(E ∩E ···∩E ) = P(E )P(E |E )P(E |E ∩E )···P(E |E ∩E ···E )1 2 k 1 2 2 3 1 2 k 1 2 k−1
kY d−(j−1)

100d−(j−1)
j=1
d−(j−1)
carP(E |E ∩E ···E )≤ .j 1 2 j−1 100d−(j−1)
Que se passe-t-il pour k =d+1? Quelle est alors le temps d’ex´ecution de l’algorithme?
66´1.3. APPLICATION: VERIFICATION D’UN PRODUIT DE MATRICE 9
1.3 Application: V´erification d’un produit de matrice
On a 3 matrices n×n, A, B, et C dansZ . AB =C ?2
3On multiplie A et B. Le nombre d’op´erations requis est de O(n ) pour un algorithme naif et
2,37peut ˆetre am´elior´e a` O n .
n
Algorithme. On choisit al´eatoirement r¯ = (r ···r ) ∈ {0,1} de mani`ere uniforme. On1 n
2calcule A(Br¯) et Cr¯, ce qui n´ecessite O n op´erations.
Si ABr¯=Cr¯, alors on retourne AB =C sinon AB =C.
Proposition 1.
nSi AB =C et r¯ est choisi de mani`ere uniforme dans {0,1} , alors P(ABr¯=Cr¯)≤ 1/2.
D´emonstration.
On d´efinit la matrice D par: D = AB −C = 0. On a donc ABr¯ = Cr¯ ⇔ Dr¯ = 0 ⇒ r =1Pn d r1j jj=2−
d11
Th´eor`eme 1 (Loi des probabilit´es totales).
Fn
E ···E disjoints, E = Ω.1 n ii=1P Pn n
P(B) = P(B∩E ) = P(B|E )P(E ).i i ii=1 i=1
X
P(ABr¯=Cr¯) = P(Dr¯= 0,(r ···r ) = (x ···x ))2 n 2 n
n−1{x ···x }∈{0,1}2 n
!PnX d x1j jj=2
≤ P r =− ,(r ···r ) = (x ···x )1 2 n 2 n
d11n−1{x2···xn}∈{0,1}
!PnX d x1j jj=2
= P r =− P((r ···r ) = (x ···x ))1 2 n 2 n
d11n−1{x ···x }∈{0,1}2 n
1
=
2
6666´ ` ´10 CHAPTER 2. VARIABLES ALEATOIRES DISCRETES ET ESPERANCE
2 Variables al´eatoires discr`etes et esp´erance
2.1 Distribution de probabilit´e discr`ete
Soit (Ω,F,P) un espace de probabilit´es. X un ensemble d´enombrable.
D´efinition 6.
1) Une application X : Ω −→ X est appel´ee une variable al´eatoire (v.a.) `a valeurs
dans X si {X =x}∈F pour tout x∈X.
P
2) Une suite de r´eels (p(x),x ∈ X) telle que 0 ≤ p(x) ≤ 1, p(x) = 1 est ap-x
pel´ee distribution de probabilit´e sur X. Si la variable al´eatoire X est telle queP
P(X ∈A) = p(x) pour toutA⊂X. On dit que (p(x),x∈X) est la distributionx∈A
de probabilit´e de X.
D´efinition 7.
1) Deux variables al´eatoires X et Y sont ind´ependantes si et seulement si
P((X =x)∩(Y =y)) =P(X =x)P(Y =y)∀x,y
2) Lesvariablesal´eatoiresX ,X ,···X sontmutuellementind´ependantessietseulement1 2 k
si pour tout I ⊂ J1···kK et pour tout x .i
T Q
P {X =i} = P(X =x ).i i ii∈I i∈I
Exemple.

1 avec probabilit´e p
1) La variable al´eatoire de Bernoulli Y = p∈ [0,1]
0 avec probabilit´e 1−p
2) Distribution de Bernoulli d’ordre n et de param`etre p.
Pn n
h(x) = x ,x = (x ,··· ,x )∈{0,1} poids de Hamming.i 1 ni=1
n h(x) n−h(x)X ={0,1} p(x) =p (1−p) p∈ [0,1].
3) Distribution binomiale d’ordre n et de param`etre p.

k k n−kX ={1,··· ,n} p(k) = p (1−p) 0≤k≤n.
n
4) Distribution multinomiale (n,k,p) p = (p ,··· ,p ) distribution de probabilit´e sur {1,··· ,k}.1 kn oPk n! n n1 kX = (n ,··· ,n ) tel que n =n,n ≥ 0 . p(n ···n ) = p ···p1 k i i 1 ki=1 1 kn !···n !1 k
2.2 Esp´erance
D´efinition 8.
Soit X une variable al´eatoire a` valeurs dans X et de distribution (p(x),x∈X).
Soit f :X −→R. On d´efinit l’esp´erance de la variable al´eatoire f(X), not´eeE[f(X)]
par:
P
a) Si f ne prend que des valeurs non n´egativesE[f(X)] = f(x)p(x).x∈X
+ −b) Cas g´en´eral : f =f −f avec
+• f (x) = max(f(x),0)

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi