Table des matières
1 Pile, face, coupons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Jeu de pile ou face . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Approximation binomiale-gaussienne . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Distance en variation totale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Approximation binomiale-Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Problème du collectionneur de coupons . . . . . . . . . . . . . . . . . . . . . 9
1.6 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Marches aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Marche aléatoire simple sur la droite . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Marche aléatoire simple symétrique dans l’espace . . . . . . . . . . . . 26
2.3 Problème de Dirichlet et champ libre gaussien . . . . . . . . . . . . . . . 30
2.4 Marche aléatoire sur le groupe symétrique . . . . . . . . . . . . . . . . . . 34
2.5 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Branchement et processus de Galton-Watson . . . . . . . . . . . . . . 39
3.1 Extinction et phénomène de seuil . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Étude des trois cas possibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Taille de l’arbre en régimes critique et sous-critique . . . . . . . . . . 49
3.4 Immigration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4 Permutations, partitions, et graphes . . . . . . . . . . . . . . . . . . . . . . . 57
4.1 Algorithme basique pour les lois discrètes . . . . . . . . . . . . . . . . . . . 57
4.2 Permutations aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 Partitions aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4 Graphes aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5 Arbres aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1 Pile, face, coupons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Jeu de pile ou face . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Approximation binomiale-gaussienne . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Distance en variation totale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Approximation binomiale-Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Problème du collectionneur de coupons . . . . . . . . . . . . . . . . . . . . . 9
1.6 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Marches aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Marche aléatoire simple sur la droite . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Marche aléatoire simple symétrique dans l’espace . . . . . . . . . . . . 26
2.3 Problème de Dirichlet et champ libre gaussien . . . . . . . . . . . . . . . 30
2.4 Marche aléatoire sur le groupe symétrique . . . . . . . . . . . . . . . . . . 34
2.5 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Branchement et processus de Galton-Watson . . . . . . . . . . . . . . 39
3.1 Extinction et phénomène de seuil . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Étude des trois cas possibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Taille de l’arbre en régimes critique et sous-critique . . . . . . . . . . 49
3.4 Immigration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4 Permutations, partitions, et graphes . . . . . . . . . . . . . . . . . . . . . . . 57
4.1 Algorithme basique pour les lois discrètes . . . . . . . . . . . . . . . . . . . 57
4.2 Permutations aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 Partitions aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4 Graphes aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5 Arbres aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66