Notons que $H_0^N = H_1^N = 0$. De plus, pour tous $0 \le y \le x \le 1$,

$$ \mathrm{Cov}(H_y^N, H_x^N) = y(1-x) $$

puisque $\mathrm{Cov}(1_{\{U_k \le y\}}, 1_{\{U_k \le x\}}) = y(1-x)$. Ce calcul s'étend aisément à la convergence d'une marginale quelconque ($H_{x_1}^N, \dots, H_{x_k}^N$). On obtient alors le résultat suivant.

**Théorème 27.17 (Pont brownien).** La suite de processus $(H^N)_{N \ge 1}$ converge vers le processus gaussien $(M_x)_{x \in [0,1]}$ qui est centré et de covariance

$$ \mathrm{Cov}(M_y, M_x) = y(1-x) $$

pour $0 \le y \le x \le 1$. *Ce processus est appelé le pont brownien.*

Ce résultat de convergence en loi du processus empirique, couplé avec des propriétés de continuité des normes du supremum et $L^2$ sur un espace de processus permet de retrouver les théorèmes de Kolmogorov-Smirnov et Cramér-Von Mises.

**Corollaire 27.18 (Kolmogorov-Smirnov et Cramér-Von Mises).**

$$ \sup_{x \in [0,1]} |H_x^N| \xrightarrow{\text{loi}} \sup_{x \in [0,1]} |M_x| \quad \text{et} \quad \int_0^1 (H_x^N)^2 dx \xrightarrow{\text{loi}} \int_0^1 M_x^2 dx. $$

Les propriétés remarquables du mouvement brownien permettent de déterminer les lois des variables aléatoires intervenant dans le corollaire ci-dessus.

**Remarque 27.19 (Définitions alternatives).** Le pont brownien peut être défini de plusieurs autres façons :

- le mouvement brownien standard sur l'intervalle de temps $[0, 1]$ conditionné à être nul aux instants 0 et 1;

- le processus $(M_t)_{t \in [0,1]}$ donné par $M_t = B_t - tB_1$ où $(B_t)_{t \ge 0}$ est un mouvement brownien standard;

- la solution de l'équation différentielle stochastique inhomogène

$$ dM_t = dB_t - \frac{M_t}{1-t} dt. $$

La dernière formulation, contrairement à la deuxième, montre que le pont brownien est un processus de Markov.

## 27.6 Schéma d'Euler

Considérons le processus de diffusion $(X_t)_{t \ge 0}$ solution de l'équation différentielle stochastique suivante :

$$ dX_t = \sigma(X_t) dB_t + b(X_t) dt. $$
Sauf cas particulier, cette équation n'admet pas de solution explicite. On cherche donc à l'approcher par une chaîne de Markov facile à simuler. L'idée la plus simple, et la plus robuste en pratique, est de procéder comme pour les équations différentielles ordinaires en introduisant le schéma d'Euler associé à une discrétisation du temps. Soit $\alpha > 0$, le schéma d'Euler de pas $\alpha$ est la chaîne de Markov $(Y_n^\alpha)_{n\ge 0}$ à valeurs dans $\mathbb{R}$ associée au noyau

$$ \mathbf{P}_{\alpha}(x, \cdot) = \mathcal{N}\left(x + \alpha b(x), \alpha \frac{\sigma(x)^2}{2}\right). $$

On peut l'étendre à un processus de diffusion $(X_t^\alpha)_{t\in\mathbb{R}_+}$ dont les coefficients sont constants entre des temps multiples de $\alpha$: pour $t \in [\alpha n, \alpha(n+1)]$,

$$ \begin{aligned} X_t^\alpha &= X_{n\alpha}^\alpha + \int_{n\alpha}^{t} b(X_{n\alpha}^\alpha) ds + \int_{t_\alpha}^{t} \sigma(X_{n\alpha}^\alpha) dB_s \\ &= X_{n\alpha}^\alpha + (t - n\alpha)b(X_{n\alpha}^\alpha) + \sigma(X_{n\alpha}^\alpha)(B_t - B_{n\alpha}). \end{aligned} $$

On a alors $Y_n^\alpha = X_{n\alpha}^\alpha$ pour tout $n \in \mathbb{N}$.

**Théorème 27.20 (Érreur faible).** Si les coefficients $b$ et $\sigma$ sont des fonctions de classe $C^4$ à dérivées bornées, alors, pour toute fonction $f$ mesurable bornée et tout $t > 0$, il existe $C > 0$ tel que

$$ |\mathrm{E}_x f(X_t) - \mathrm{E}_x f(X_t^\alpha)| \le C\alpha. $$

*Démonstration.* Esquissons ici une idée de la preuve. Notons $(P_t)_{t\ge 0}$ le semi-groupe associé à $(X_t)_{t\ge 0}$ et $L$ son générateur infinitésimal. On écrit

$$ \mathbf{P}_{\alpha}^{n} f - P_{\alpha n} f = \sum_{k=1}^{n} \mathbf{P}_{\alpha}^{k-1} (\mathbf{P}_{\alpha} - P_{\alpha}) P_{\alpha(n-k)} f. $$

Or les développements limités des deux noyaux de probabilité $P_\alpha$ et $\mathbf{P}_\alpha$ coïncident jusqu'à l'ordre 2. En effet, puisque $\partial_t P_t = LP_t$,

$$ P_{\alpha} g(x) = g(x) + \alpha L g(x) + \mathcal{O}(\alpha^2) $$

Soit $Y$ de loi $\mathcal{N}(0, 1)$. En posant $\delta(x) = \sqrt{\alpha\sigma(x)}Y + \alpha b(x)$, on a

$$ \begin{aligned} \mathbf{P}_{\alpha} g(x) &= \mathrm{E}g(x + \alpha b(x) + \sqrt{\alpha\sigma(x)}Y) \\ &= \mathrm{E}\left(g(x) + \delta(x)g'(x) + \frac{\delta(x)^2}{2}g''(x) + \frac{\delta(x)^3}{6}g'''(x) + \mathcal{O}(\delta(x)^3)\right) \\ &= g(x) + \alpha L g(x) + \mathcal{O}(\alpha^2) \end{aligned} $$

puisque les moments d'ordres 1 et 3 de $Y$ sont nuls. L'erreur entre diffusion et schéma d'Euler sur un pas de temps $\alpha$ est donc de l'ordre de $\alpha^2$. Au bout de $n$ itérations, l'erreur sera donc d'ordre $\alpha$ (puisque $\alpha n$ est de l'ordre de
t). Reste une difficulté de taille : montrer que l'on contrôle les dérivées de $P_{\alpha(n-k)}f$ pour que le développement limité ci-dessus soit valide. Ceci découle de propriétés de régularité de la solution de l'équation aux dérivées partielles parabolique $\partial_t u = Lu$. $\square$

Il est également possible de contrôler l'écart trajectoriel entre les processus $X$ et $X^\alpha$ supposés être construits avec le même mouvement brownien.

**Théorème 27.21 (Erreur forte).** S'il existe $C > 0$ tel que pour tous $x, y \in \mathbb{R}$,

$$|b(x) - b(y)| + |\sigma(x) - \sigma(y)| \le C|x - y|,$$

alors, pour tout $p \ge 1$ et tout $T > 0$, il existe $K_p(T)$ tel que

$$\mathbb{E} \left( \sup_{0 \le t \le T} |X_t - X_t^\alpha|^p \right) \le K_p(T) \alpha^{p/2}.$$

La démonstration de ce résultat est technique mais assez directe. Elle repose essentiellement sur la formule d'Itô, le lemme de Grönwall et l'inégalité de Burkholder-Davis-Gundy.

## 27.7 Pour aller plus loin

De nombreux ouvrages sont consacrés au calcul stochastique et aux processus de diffusion. On trouvera notamment dans le livre d'Iosif Gikhman et Anatoliy Skorokhod [GS72] l'étude des diffusions sur un intervalle de $\mathbb{R}$ et leurs comportements aux bords du domaine. Les différentes variantes et subtilités des résultats de convergence de processus sont rassemblées dans le livre [EK86] de Stewart Ethier et Thomas Kurtz. La section 7.4 de cet ouvrage très dense concerne notamment l'approximation diffusive et propose une démonstration du théorème 27.3.

Citons encore deux exemples classiques de convergence pour des processus de Markov à temps continu et espaces d'états discrets vers une diffusion.

Pour $N \in \mathbb{N}^*$, soit $Z^{N,\lambda,\mu}$ la file d'attente $M/M/\infty$, étudiée dans le chapitre 11, de taux d'arrivée $N\lambda$ et de taux de service $\mu$. Pour tous $N \ge 1$ et $t \ge 0$, posons

$$X_t^N = \sqrt{N} \left( \frac{Z_t^{N,\lambda,\mu}}{N} - \frac{\lambda}{\mu} \right) \quad \text{avec} \quad Z_0^{N,\lambda,\mu} = \lfloor N\lambda/\mu + \sqrt{N}x \rfloor.$$

La suite $(X_{\lfloor N \cdot \rfloor})_{N \ge 1}$ converge en loi vers le processus d'Ornstein-Uhlenbeck solution de

$$dX_t = \sqrt{2\lambda} dB_t - \mu X_t dt \quad \text{avec} \quad X_0 = x,$$

Cette approximation d'une file d'attente par une diffusion est très utilisée en pratique. On nomme ce modèle une file fluide. On pourra consulter à ce propos le livre de Philippe Robert [Rob00].
De même, soit une suite $(Y^N)_{N \ge 1}$ de processus de naissance et mort de taux respectifs $(\lambda_N n)_{n \in \mathbb{N}}$ et $(\mu_N n)_{n \in \mathbb{N}}$. On suppose que

$$N(\lambda_N - \mu_N) = b + \mathcal{O}(1/N) \quad \text{et} \quad \lambda_N + \mu_N = 2a + \mathcal{O}(1/N).$$

Alors la suite de processus $(Y^N_{[N \cdot ]}/N)_{N \ge 1}$ converge vers la diffusion $X$ solution de l'équation différentielle suivante :

$$dX_t = \sqrt{2aX_t} dB_t + bX_t dt.$$

Les schémas d'Euler associés à des processus de diffusion ont été très largement étudiés. Citons les ouvrages de synthèse de Peter Kloeden et Eckhard Platen [KP95], Nicolas Bouleau et Dominique Lépingle [BL94] pour la preuve du théorème 27.21. Ajoutons également le livre de Carl Graham et Denis Talay [GT13]. Il est possible d'améliorer le théorème 27.20 en obtenant un développement limité de l'erreur faible en puissances de $\alpha$. Ceci permet d'accélérer la convergence : en combinant des schémas de pas $2\alpha$ et $\alpha$ on obtient une erreur de l'ordre de $\alpha^2$ ! Cette méthode, appelée extrapolation de Romberg, est également utilisée en analyse numérique des équations différentielles ordinaires. Les deux travaux fondateurs dans cette direction sont dus à Denis Talay et Luciano Tubaro [TT90], qui supposent que la fonction test est très régulière, puis à Vlad Bally et Denis Talay [BT95] qui, grâce au calcul de Malliavin, obtiennent le résultat pour des fonctions mesurables bornées si les coefficients $\sigma$ et $b$ sont réguliers. La contribution de Denis Talay [Tal96] propose également une synthèse sur les estimations de l'erreur faible.
## Suggestions bibliographiques

Ce bref chapitre fournit quelques suggestions de lecture, nécessairement incomplètes et subjectives, concernant les probabilités de niveau master. Parmi les ouvrages les plus accessibles, on peut citer notamment le livre classique et incontournable de William Feller [Fel68, Fel71], celui plus récent d'Alan Gut [Gut13], ainsi que les livres de Philippe Barbe et Michel Ledoux [BL98], Jean Jacod et Philip Protter [JP02, JP03], Daniel Revuz [Rev97], Vivek Borkar [Bor95], Paul Toulouse [Tou99], David Williams [Wil91], Rick Durrett [Dur10a], Pierre Brémaud [Bré99], et Albert Shiryaev [Shi96]. Signalons enfin le traité monumental de Claude Dellacherie et Paul-André Meyer [DM80].

Les martingales à temps discret constituent le sujet principal des livres de Jacques Neveu [Nev72, Nev75], Peter Hall et Christopher Heyde [HH80] ou encore David Williams [Wil91].

Les chaînes de Markov à temps et espace discrets constituent le sujet principal des livres de Paoli Baldi, Laurent Mazliak, et Pierre Priouret [BMP08], Olle Häggström [Häg02], et David Levin, Yuval Peres, et Elizabeth Wilmer [LPW09]. Celui de James Norris [Nor98b] aborde également les processus de Markov à temps continu et espace d'états dénombrable ainsi que les martingales. Citons aussi les ouvrages de Michel Benaïm et Nicole El Karoui [BEK05], Jean-François Delmas et Benjamin Jourdain [DJ06], Étienne Pardoux [Par07], et Thierry Bodineau [Bod14] qui présentent également des applications importantes ou classiques (physique, biologie, mathématiques financières, etc). Dans cette veine, avec également un pont vers l'épreuve de modélisation de l'agrégation de mathématiques, on pourra consulter [BC07].

L'ouvrage de Christiane Cocozza-Thivent [CT97] présente des applications des probabilités à la fiabilité. La théorie des valeurs extrêmes est abordée par exemple dans le livre de Paul Embrechts, Claudia Klüppelberg, et Thomas Mikosch [EKM97], tandis que la théorie des principes de grandes déviations est abordée par exemple dans le livre de Amir Dembo et Ofer Zeitouni [DZ10].

Le calcul stochastique est abordé par exemple dans les livres de Jean-François Le Gall [LG13], Bert Øksendal [Øks03], Daniel Revuz et Marc Yor [RY99], Kai Lai Chung et David Williams [CW14], David Williams et Chris
Rogers [RW00], et Ioannis Karatzas et Steven Shreve [KS91]. Citons enfin
le livre de Carl Graham et Denis Talay [GT13] qui présente également des
résultats d'approximation des diffusions par les schémas d'Euler.
Littérature

AB99. R. ALBERT et A.-L. BARABÁSI – « Emergence of scaling in random networks », *Science* (1999), no. 286, p. 509–512. 214

AB02. —, « Statistical mechanics of complex networks », *Rev. Modern Phys.* **74** (2002), no. 1, p. 47–97. 214

ABC<sup>+00</sup>. C. ANÉ, S. BLACHÈRE, D. CHAFAÏ, P. FOUGÈRES, I. GENTIL, F. MALRIEU, C. ROBERTO et G. SCHEFFER – *Sur les inégalités de Sobolev logarithmiques*, Panoramas et Synthèses [Panoramas and Syntheses], vol. 10, Société Mathématique de France, Paris, 2000, With a preface by Dominique Bakry and Michel Ledoux. 344

ABR08. L. ADDARIO-BERRY et B. A. REED – « Ballot theorems, old and new », Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Springer, Berlin, 2008, p. 9–35. 55

ABT03. R. ARRATIA, A. D. BARBOUR et S. TAVARÉ – *Logarithmic combinatorial structures : a probabilistic approach*, EMS Monographs in Mathematics, European Mathematical Society (EMS), Zürich, 2003. 199

ACG<sup>+99</sup>. G. AUSIELLO, P. CRESCENZI, G. GAMBOSI, V. KANN, A. MARCHETTI-SPACCAMELA et M. PROTASI – *Complexity and approximation*, Springer-Verlag, Berlin, 1999, Combinatorial optimization problems and their approximability properties, With 1 CD-ROM (Windows and UNIX). 278

AF01. D. J. ALDOUS et J. A. FILL – « Reversible Markov Chains and Random Walks on Graphs », cours non publié disponible sous forme électronique sur Internet, 1994-2001. 17, 38

AG13a. A. ASSELAH et A. GAUDILLIÈRE – « From logarithmic to subdiffusive polynomial fluctuations for internal dla and related growth models », *The Annals of Probability* **41** (2013), no. 3A, p. 1115–1159. 91

AG13b. —, « Sublogarithmic fluctuations for internal dla », *The Annals of Probability* **41** (2013), no. 3A, p. 1160–1179. 91

AGZ10. G. W. ANDERSON, A. GUIONNET et O. ZEITOUNI – *An introduction to random matrices*, Cambridge Studies in Advanced Mathematics, vol. 118, Cambridge University Press, Cambridge, 2010. 296
AHU75. A. V. AHO, J. E. HOPCROFT et J. D. ULLMAN – *The design and analysis of computer algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975, Second printing, Addison-Wesley Series in Computer Science and Information Processing. 278

AK90. D. ALDOUS et W. B. KREBS – « The “birth-and-assassination” process », *Statist. Probab. Lett.* **10** (1990), no. 5, p. 427-430. 303

Ald85. D. J. ALDOUS – « Exchangeability and related topics », École d'été de probabilités de Saint-Flour, XIII–1983, Lecture Notes in Math., vol. 1117, Springer, Berlin, 1985, p. 1–198. 199

Ald91. –, « Threshold limits for cover times », *J. Theoret. Probab.* **4** (1991), no. 1, p. 197–211. 16

AN04. K. B. ATHREYA et P. E. NEY – *Branching processes*, Dover Publications Inc., Mineola, NY, 2004, Reprint of the 1972 original [Springer, New York; MR0373040]. 54, 243

And87. D. ANDRÉ – « Solution directe du problème résolu par M. Bertrand », *Comptes Rendus Acad. Sci. Paris* **105** (1887), p. 436–437. 37

AS80. D. B. ARNOLD et M. R. SLEEP – « Uniform random generation of balanced parenthesis strings », *ACM Trans. Program. Lang. Syst.* **2** (1980), p. 122–128. 68

Asm00. S. ASMUSSEN – *Ruin probabilities*, Advanced Series on Statistical Science & Applied Probability, vol. 2, World Scientific Publishing Co. Inc., River Edge, NJ, 2000. 252

Bak94. D. BAKRY – « L'hypercontractivité et son utilisation en théorie des sémigroupes », Lectures on probability theory (Saint-Flour, 1992), Lecture Notes in Math., vol. 1581, Springer, Berlin, 1994, p. 1–114. 343

Bas95. R. F. BASS – *Probabilistic techniques in analysis*, Probability and its Applications (New York), Springer-Verlag, New York, 1995. 325

Bax82. R. J. BAXTER – *Exactly solved models in statistical mechanics*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1982. 81

BB03. F. BACCELLI et P. BRÉMAUD – *Elements of queueing theory*, second éd., Applications of Mathematics (New York), vol. 26, Springer-Verlag, Berlin, 2003, Palm martingale calculus and stochastic recurrences, Stochastic Modelling and Applied Probability. 155

BC03. C. BIERNACKI et S. CHRÉTIEN – « Degeneracy in the maximum likelihood estimation of univariate Gaussian mixtures with EM », *Statist. Probab. Lett.* **61** (2003), no. 4, p. 373–382. 112

BC07. B. BERCU et D. CHAFAÏ – *Modélisation stochastique et simulation, cours et applications*, Collection Sciences Sup, Dunod, 2007, Mathématiques appliquées/SMAI. 81, 91, 103, 375

BD02. P. J. BROCKWELL et R. A. DAVIS – *Introduction to time series and forecasting*, second éd., Springer Texts in Statistics, Springer-Verlag, New York, 2002, With 1 CD-ROM (Windows). 103

BDMT11. V. BANSAYE, J.-F. DELMAS, L. MARSALLE et V. C. TRAN – « Limit theorems for Markov processes indexed by continuous time Galton-Watson trees », *Ann. Appl. Probab.* **21** (2011), no. 6, p. 2263–2314. 243
BÉ85. D. BAKRY et M. ÉMERY – « Diffusions hypercontractives », Séminaire de probabilités, XIX, 1983/84, Lecture Notes in Math., vol. 1123, Springer, Berlin, 1985, p. 177–206. 344

BEK05. M. BENAÏM et N. EL KAROUI – *Promenade aléatoire : chaînes de markov et simulations* ; martingales et stratégies, Mathématiques appliquées, Les éd. de l'École polytechnique, 2005. 215, 375

Ber76. C. BERGE – *Graphs and hypergraphs*, revised éd., North-Holland Publishing Co., Amsterdam-London ; American Elsevier Publishing Co., Inc., New York, 1976, Translated from the French by Edward Minieka, North-Holland Mathematical Library, Vol. 6. 67

Ber06. J. BERTOIN – *Random fragmentation and coagulation processes*, Cambridge Studies in Advanced Mathematics, vol. 102, Cambridge University Press, Cambridge, 2006. 185, 199, 243

Ber09. N. BERESTYCKI – *Recent progress in coalescent theory*, Ensaios Matemáticos [Mathematical Surveys], vol. 16, Sociedade Brasileira de Matemática, Rio de Janeiro, 2009. 185, 199

BGL14. D. BAKRY, I. GENTIL et M. LEDOUX – *Analysis and geometry of Markov diffusion operators*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 348, Springer, Cham, 2014. 344

Bha97. R. BHATIA – *Matrix analysis*, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. 296

BHJ92. A. D. BARBOUR, L. HOLST et S. JANSON – *Poisson approximation*, Oxford Studies in Probability, vol. 2, The Clarendon Press Oxford University Press, New York, 1992, Oxford Science Publications. 15

BL94. N. BOULEAU et D. LÉPINGLE – *Numerical methods for stochastic processes*, Wiley Series in Probability and Mathematical Statistics : Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1994, A Wiley-Interscience Publication. 374

BL98. P. BARBE et M. LEDOUX – *Probabilités*, De la licence à l'agrégation, Belin, 1998. 375

BMP08. P. BALDI, L. MAZLIAK et P. PRIOURET – *Martingales et chaînes de Markov. Théorie élémentaire et exercices corrigés*, Hermann, 2008. 375

BMR14. S. BUBECK, E. MOSSEL et M. Z. RÁCZ – « On the influence of the seed graph in the preferential attachment model », arXiv :1401.4849, 2014. 215

Bod14. T. BODINEAU – « Promenade aléatoire : chaînes de Markov et martingales », Cours de l'École Polytechnique, Palaiseau, France, 2014. 81, 215, 375

Bol80. B. BOLLOBÁS – « A probabilistic proof of an asymptotic formula for the number of labelled regular graphs », *European J. Combin.* **1** (1980), no. 4, p. 311–316. 67

Bol89. E. BOLTHAUSEN – « A note on the diffusion of directed polymers in a random environment », *Comm. Math. Phys.* **123** (1989), no. 4, p. 529–534. 265
Bor95. V. S. BORKAR – *Probability theory*, Universitext, Springer-Verlag, New York, 1995, An advanced course. 375

Bor08. C. BORDENAVE – « On the birth-and-assassination process, with an application to scotching a rumor in a network », *Electron. J. Probab.* **13** (2008), p. no. 66, 2014–2030. 303, 304

Bor14a. C. BORDENAVE – « Lecture notes on random graphs and probabilistic combinatorial optimization », Disponible sur la page Internet de l'auteur, 2014. 67, 229, 278

Bor14b. —, « A short course on random matrices », Disponible sur la page Internet de l'auteur, 2014. 296

BPPC99. C. BOUZITAT, G. PAGÈS, F. PETIT et F. CARRANCE – *En passant par hasard. . . les probabilités de tous les jours*, Vuibert, 1999. 16

BR11. M. BENAÏM et O. RAIMOND – « Self-interacting diffusions IV : Rate of convergence », *Electron. J. Probab.* **16** (2011), p. no. 66, 1815–1843. 215

Bré99. P. BRÉMAUD – *Markov chains*, Texts in Applied Mathematics, vol. 31, Springer-Verlag, New York, 1999, Gibbs fields, Monte Carlo simulation, and queues. 375

BRST01. B. BOLLOBÁS, O. RIORDAN, J. SPENCER et G. TUSNÁDY – « The degree sequence of a scale-free random graph process », *Random Structures Algorithms* **18** (2001), no. 3, p. 279–290. 215

BS10. Z. BAI et J. W. SILVERSTEIN – *Spectral analysis of large dimensional random matrices*, second éd., Springer Series in Statistics, Springer, New York, 2010. 296

BSZ11. N. BERESTYCKI, O. SCHRAMM et O. ZEITOUNI – « Mixing times for random k-cycles and coalescence-fragmentation chains », *Ann. Probab.* **39** (2011), no. 5, p. 1815–1843. 67

BT95. V. BALLY et D. TALAY – « The Euler scheme for stochastic differential equations : error analysis with Malliavin calculus », *Math. Comput. Simulation* **38** (1995), no. 1-3, p. 35–41, Probabilités numériques (Paris, 1992). 374

Cap12. M. CAPITAINE – « Introduction aux grandes matrices aléatoires », Disponible sur la page Internet de l'auteur, 2012. 296

Cat99. O. CATONI – « Simulated annealing algorithms and Markov chains with rare transitions », Séminaire de Probabilités, XXXIII, Lecture Notes in Math., vol. 1709, Springer, Berlin, 1999, p. 69–119. 81

CD04. A. CHARPENTIER et M. DENUIT – *Mathématiques de l'assurance non-vie - concepts fondamentaux de théorie du risque, tome 1*, Economica, 2004. 252

CDKM14. N. CURIEN, T. DUQUESNE, I. KORTCHEMSKI et I. MANOLESCU – « Scaling limits and influence of the seed graph in preferential attachment trees », prépublication arXiv:1406.1758, 2014. 215

CDM13. D. CHAFAÏ, Y. DOUMERC et F. MALRIEU – « Processus des restaurants chinois et loi d'ewens », *RMS* **123** (2013), no. 3, p. 56–74. 198
CDPP09. P. CAPUTO, P. DAI PRA et G. POSTA – « Convex entropy decay via the Bochner-Bakry-Emery approach », *Ann. Inst. Henri Poincaré Probab. Stat.* **45** (2009), no. 3, p. 734-753. 155

CF51. K. L. CHUNG et W. H. J. FUCHS – « On the distribution of values of sums of random variables », *Mem. Amer. Math. Soc.* **1951** (1951), no. 6, p. 12. 37

CH02. P. CARMONA et Y. HU – « On the partition function of a directed polymer in a Gaussian random environment », *Probab. Theory Related Fields* **124** (2002), no. 3, p. 431-457. 265

Cha06. D. CHAFAÏ – « Binomial-Poisson entropic inequalities and the $M/M/\infty$ queue », *ESAIM Probab. Stat.* **10** (2006), p. 317-339 (electronic). 155

Cha13. –, « Introduction aux matrices aléatoires », Aléatoire, Ed. Éc. Polytech., Palaiseau, 2013, p. 87-122. 296

Clo13. B. CLOEZ – « Comportement asymptotique de processus avec sauts et applications pour des modèles avec branchement », Thèse, Université Paris-Est, 2013. 243

CMP10. D. CHAFAÏ, F. MALRIEU et K. PAROUX – « On the long time behavior of the TCP window size process », *Stochastic Processes and their Applications* **8** (2010), no. 120, p. 1518-1534. 242

CSY03. F. COMETS, T. SHIGA et N. YOSHIDA – « Directed polymers in a random environment : path localization and strong disorder », *Bernoulli* **9** (2003), no. 4, p. 705-723. 265

CT97. C. COCOZZA-THIVENT – *Processus stochastiques et fiabilité des systèmes*, Mathématiques et Applications, Springer, 1997. 252, 375

CV06. F. COMETS et V. VARGAS – « Majorizing multiplicative cascades for directed polymers in random media », *ALEA Lat. Am. J. Probab. Math. Stat.* **2** (2006), p. 267-277. 265

CW14. K. L. CHUNG et R. J. WILLIAMS – *Introduction to stochastic integration*, second éd., Modern Birkhäuser Classics, Birkhäuser/Springer, New York, 2014. 375

CY06. F. COMETS et N. YOSHIDA – « Directed polymers in random environment are diffusive at weak disorder », *Ann. Probab.* **34** (2006), no. 5, p. 1746-1770. 265

Dav90. B. DAVIS – « Reinforced random walk », *Probab. Theory Related Fields* **84** (1990), no. 2, p. 203-229. 215

DCD83. D. DACUNHA-CASTELLE et M. DUFLO – *Probabilités et statistiques. Tome 2*, Collection Mathématiques Appliquées pour la Maîtrise. [Collection of Applied Mathematics for the Master’s Degree], Masson, Paris, 1983, Problèmes à temps mobile. [Movable-time problems]. 102

DCS12. H. DUMINIL-COPIN et S. SMIRNOV – « The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt{2}}$ », *Ann. of Math. (2)* **175** (2012), no. 3, p. 1653-1665. 229

Dem05. A. DEMBO – « Favorite points, cover times and fractals », Lectures on probability theory and statistics, Lecture Notes in Math., vol. 1869, Springer, Berlin, 2005, p. 1-101. 17
Dev12. L. DEVROYE – « Simulating size-constrained Galton-Watson trees », *SIAM J. Comput.* **41** (2012), no. 1, p. 1–11. 68

DF91. P. DIACONIS et W. FULTON – « A growth model, a game, an algebra, Lagrange inversion, and characteristic classes », *Rend. Sem. Mat. Univ. Politec. Torino* **49** (1991), no. 1, p. 95–119 (1993), Commutative algebra and algebraic geometry, II (Italian) (Turin, 1990). 91

DGR02. V. DUMAS, F. GUILLEMIN et P. ROBERT – « A Markovian analysis of additive-increase multiplicative-decrease algorithms », *Adv. in Appl. Probab.* **34** (2002), no. 1, p. 85–111. 242

DJ06. J.-F. DELMAS et B. JOURDAIN – *Modèles aléatoires*, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 57, Springer-Verlag, Berlin, 2006, Applications aux sciences de l'ingénieur et du vivant. [Applications to engineering and the life sciences]. 54, 102, 172, 185, 375

DLM99. B. DELYON, M. LAVIELLE et E. MOULINES – « Convergence of a stochastic approximation version of the EM algorithm », *Ann. Statist.* **27** (1999), no. 1, p. 94–128. 112

DLR77. A. P. DEMPSTER, N. M. LAIRD et D. B. RUBIN – « Maximum likelihood from incomplete data via the EM algorithm », *J. Roy. Statist. Soc. Ser. B* **39** (1977), no. 1, p. 1–38, With discussion. 112

DM47. A. DVORETZKY et T. MOTZKIN – « A problem of arrangements », *Duke Math. J.* **14** (1947), p. 305–313. 54

DM80. C. DELLACHERIE et P.-A. MEYER – *Probabilités et potentiel. Chaptres V à VIII*, revised éd., Actualités Scientifiques et Industrielles [Current Scientific and Industrial Topics], vol. 1385, Hermann, Paris, 1980, Théorie des martingales. [Martingale theory]. 375

DMWZZ04. P. DIACONIS, E. MAYER-WOLF, O. ZEITOUNI et M. P. W. ZERNER – « The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transformations », *Ann. Probab.* **32** (2004), no. 1B, p. 915–938. 67

DP13. A. V. DOUMAS et V. G. PAPANICOLΑOU – « Asymptotics of the rising moments for the coupon collector's problem », *Electron. J. Probab.* **18** (2013), p. no. 41, 15. 16

Drm09. M. DRMOTA – *Random trees*, SpringerWienNewYork, Vienna, 2009, An interplay between combinatorics and probability. 68

DS81. P. DIACONIS et M. SHAHSHAHANI – « Generating a random permutation with random transpositions », *Z. Wahrsch. Verw. Gebiete* **57** (1981), no. 2, p. 159–179. 67

DS84. P. G. DOYLE et J. L. SNELL – *Random walks and electric networks*, Carus Mathematical Monographs, vol. 22, Mathematical Association of America, Washington, DC, 1984. 37

DS87. P. DIACONIS et M. SHAHSHAHANI – « Time to reach stationarity in the Bernoulli-Laplace diffusion model », *SIAM J. Math. Anal.* **18** (1987), no. 1, p. 208–218. 127

DST14. M. DISERTORI, C. SABOT et P. TARRÈS – « Transience of Edge-Reinforced Random Walk », arXiv:1403.6079, 2014. 215
Duf97. M. DUFLO – *Random iterative models*, Applications of Mathematics (New York), vol. 34, Springer-Verlag, Berlin, 1997, Translated from the 1990 French original by Stephen S. Wilson and revised by the author. 112

Dur64. R. DURSTENFELD – « Algorithm 235 : Random permutation », *Communications of the ACM* **7** (1964), no. 7, p. 420. 66

Dur08. R. DURRETT – *Probability models for DNA sequence evolution*, second éd., Probability and its Applications (New York), Springer, New York, 2008. 172, 185, 199

Dur10a. R. DURRETT – *Probability : theory and examples*, fourth éd., Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2010. 375

Dur10b. –, *Random graph dynamics*, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2010. 215

Dwa69. M. DWASS – « The total progeny in a branching process and a related random walk. », *J. Appl. Probability* **6** (1969), p. 682–686. 55

DZ10. A. DEMBO et O. ZEITOUNI – *Large deviations techniques and applications*, Stochastic Modelling and Applied Probability, vol. 38, Springer-Verlag, Berlin, 2010, Corrected reprint of the second (1998) edition. 303, 375

EG60. P. ERDŐS et T. GALLAI – « Gráfok előírt fokszámú pontokkal », *Matematikai Lapok* (1960), no. 11, p. 264–274. 67

EK86. S. N. ETHIER et T. G. KURTZ – *Markov processes*, Wiley Series in Probability and Mathematical Statistics : Probability and Mathematical Statistics, John Wiley & Sons Inc., New York, 1986, Characterization and convergence. 373

EKM97. P. EMBRECHTS, C. KLÜPPELBERG et T. MIKOSCH – *Modelling extremal events*, Applications of Mathematics (New York), vol. 33, Springer-Verlag, Berlin, 1997, For insurance and finance. 375

EO05. R. ERBAN et H. G. OTHMER – « From individual to collective behavior in bacterial chemotaxis », *SIAM J. Appl. Math.* **65** (2004/05), no. 2, p. 361–391 (electronic). 313

ER59. P. ERDŐS et A. RÉNYI – « On random graphs. I », *Publ. Math. Debrecen* **6** (1959), p. 290–297. 229

ER61a. –, « On a classical problem of probability theory », *Magyar Tud. Akad. Mat. Kutató Int. Közl.* **6** (1961), p. 215–220. 16

ER61b. –, « On the evolution of random graphs », *Bull. Inst. Internat. Statist.* **38** (1961), p. 343–347. 229

Ewe04. W. J. EWENS – *Mathematical population genetics. I*, second éd., Interdisciplinary Applied Mathematics, vol. 27, Springer-Verlag, New York, 2004, Theoretical introduction. 172, 185, 199

Fel68. W. FELLER – *An introduction to probability theory and its applications. Vol. I*, Third edition, John Wiley & Sons Inc., New York, 1968. 15, 16, 37, 137, 375
Fel71. —, *An introduction to probability theory and its applications. Vol. II.*, Second edition, John Wiley & Sons Inc., New York, 1971. 15, 16, 375

Fer89. T. S. FERGUSON – « Who solved the secretary problem? », *Statist. Sci.* **4** (1989), no. 3, p. 282–296, With comments and a rejoinder by the author. 138

FF04. D. FOATA et A. FUCHS – *Processus stochastiques : processus de poisson, chaînes de markov et martingales*, Collection Sciences Sup, Dunod, 2004. 252

Fil98. J. A. FILL – « An interruptible algorithm for perfect sampling via Markov chains », *Ann. Appl. Probab.* **8** (1998), no. 1, p. 131–162. 81

FKG71. C. M. FORTUIN, P. W. KASTELEYN et J. GINIBRE – « Correlation inequalities on some partially ordered sets », *Comm. Math. Phys.* **22** (1971), p. 89–103. 265

Fre65. D. A. FREEDMAN – « Bernard Friedman’s urn », *Ann. Math. Statist* **36** (1965), p. 956–970. 91

FY48. R. A. FISHER et F. YATES – *Statistical Tables for Biological, Agricultural and Medical Research*, Oliver and Boyd, London, 1948, 3d ed. 66

Gil59. E. N. GILBERT – « Random graphs », *Ann. Math. Statist.* **30** (1959), p. 1141–1144. 229

GJ87. J. GLIMM et A. JAFFE – *Quantum physics*, second éd., Springer-Verlag, New York, 1987, A functional integral point of view. 37

GR10. C. GRAHAM et P. ROBERT – « A multi-class mean-field model with graph structure for TCP flows », *Progress in industrial mathematics at ECMI 2008, Math. Ind.*, vol. 15, Springer, Heidelberg, 2010, p. 125–131. 242

Gri99. G. GRIMMETT – *Percolation*, second éd., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 321, Springer-Verlag, Berlin, 1999. 229

Gri10. —, *Probability on graphs*, Institute of Mathematical Statistics Textbooks, vol. 1, Cambridge University Press, Cambridge, 2010, Random processes on graphs and lattices. 229

GRZ04. F. GUILLEMIN, P. ROBERT et B. ZWART – « AIMD algorithms and exponential functionals », *Ann. Appl. Probab.* **14** (2004), no. 1, p. 90–117. 242

GS72. Ī. Ī. GĪHMAN et A. V. SKOROHOD – *Stochastic differential equations*, Springer-Verlag, New York, 1972, Translated from the Russian by Kenneth Wickwire, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 72. 373

GS84. C. R. GIVENS et R. M. SHORTT – « A class of Wasserstein metrics for probability distributions », *Michigan Math. J.* **31** (1984), no. 2, p. 231–240. 343

GS01. G. R. GRIMMETT et D. R. STIRZAKER – *Probability and random processes*, third éd., Oxford University Press, New York, 2001. 155
GT13. C. GRAHAM et D. TALAY – *Stochastic simulation and Monte Carlo methods*, Stochastic Modelling and Applied Probability, vol. 68, Springer, Heidelberg, 2013, Mathematical foundations of stochastic simulation. 374, 376

Gut13. A. GUT – *Probability : a graduate course*, second éd., Springer Texts in Statistics, Springer, New York, 2013. 375

Häg02. O. HÄGGSTRÖM – *Finite markov chains and algorithmic applications*, London Mathematical Society student texts, Cambridge University Press, 2002. 81, 375

Har60. T. E. HARRIS – « A lower bound for the critical probability in a certain percolation process », *Proc. Cambridge Philos. Soc.* **56** (1960), p. 13–20. 229

Har02. —, *The theory of branching processes*, Dover Phoenix Editions, Dover Publications Inc., Mineola, NY, 2002, Corrected reprint of the 1963 original [Springer, Berlin; MR0163361 (29 #664)]. 54, 243

Has70. W. K. HASTINGS – « Monte Carlo sampling methods using Markov chains and their applications », *Biometrika* (1970), no. 57, p. 97–109. 81

HH80. P. HALL et C. C. HEYDE – *Martingale limit theory and its application*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980, Probability and Mathematical Statistics. 91, 375

HJ06. O. HÄGGSTRÖM et J. JONASSON – « Uniqueness and non-uniqueness in percolation theory », *Probab. Surv.* **3** (2006), p. 289–344. 229

HJ13. R. A. HORN et C. R. JOHNSON – *Matrix analysis*, second éd., Cambridge University Press, Cambridge, 2013. 296

HJV07. P. HACCOU, P. JAGERS et V. A. VATUTIN – *Branching processes : variation, growth, and extinction of populations*, Cambridge Studies in Adaptive Dynamics, Cambridge University Press, Cambridge, 2007. 54

Hol01. L. HOLST – « Extreme value distributions for random coupon collector and birthday problems », *Extremes* **4** (2001), no. 2, p. 129–145 (2002). 16

Hop84. F. M. HOPPE – « Pólya-like urns and the Ewens’ sampling formula », *J. Math. Biol.* **20** (1984), no. 1, p. 91–94. 199

Hör67. L. HÖRMANDER – « Hypoelliptic second order differential equations », *Acta Math.* **119** (1967), p. 147–171. 356

HV10. S. HERRMANN et P. VALLOIS – « From persistent random walk to the telegraph noise », *Stoch. Dyn.* **10** (2010), no. 2, p. 161–196. 313

IS88. J. Z. IMBRIE et T. SPENCER – « Diffusion of directed polymers in a random environment », *J. Statist. Phys.* **52** (1988), no. 3-4, p. 609–626. 265

JK77. N. L. JOHNSON et S. KOTZ – *Urn models and their application*, John Wiley & Sons, New York-London-Sydney, 1977, An approach to modern discrete probability theory, Wiley Series in Probability and Mathematical Statistics. 214
JKB97. N. L. JOHNSON, S. KOTZ et N. BALAKRISHNAN – *Discrete multivariate distributions*, Wiley Series in Probability and Statistics : Applied Probability and Statistics, John Wiley & Sons Inc., New York, 1997, A Wiley-Interscience Publication. 199

JLS12. D. JERISON, L. LEVINE et S. SHEFFIELD – « Logarithmic fluctuations for internal DLA », *J. Amer. Math. Soc.* **25** (2012), no. 1, p. 271–301. 91

JLS13. D. JERISON, L. LEVINE et S. SHEFFIELD – « Internal dla in higher dimensions », *Electron. J. Probab.* **18** (2013), p. no. 98, 1–14. 91

JP02. J. JACOD et P. PROTTER – *L'essentiel en théorie des probabilités*, Enseignement des mathématiques, Cassini, 2002. 375

JP03. —, *Probability essentials*, second éd., Universitext, Springer-Verlag, Berlin, 2003. 375

Kac47. M. KAC – « Random walk and the theory of Brownian motion », *Amer. Math. Monthly* **54** (1947), p. 369–391. 127

Kac74. —, « A stochastic model related to the telegrapher's equation », *Rocky Mountain J. Math.* **4** (1974), p. 497–509, Reprinting of an article published in 1956, Papers arising from a Conference on Stochastic Differential Equations (Univ. Alberta, Edmonton, Alta., 1972). 313

KB97. S. KOTZ et N. BALAKRISHNAN – « Advances in urn models during the past two decades », Advances in combinatorial methods and applications to probability and statistics, Stat. Ind. Technol., Birkhäuser Boston, Boston, MA, 1997, p. 203–257. 214

Kes80. H. KESTEN – « The critical probability of bond percolation on the square lattice equals $\frac{1}{2}$ », *Comm. Math. Phys.* **74** (1980), no. 1, p. 41–59. 229

Kin80. J. F. C. KINGMAN – *Mathematics of genetic diversity*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 34, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. 199

Kin93. —, *Poisson processes*, Oxford Studies in Probability, vol. 3, The Clarendon Press Oxford University Press, New York, 1993, Oxford Science Publications. 185, 199

KL04. E. KUHN et M. LAVIELLE – « Coupling a stochastic approximation version of EM with an MCMC procedure », *ESAIM Probab. Stat.* **8** (2004), p. 115–131 (electronic). 112

Knu05. D. E. KNUTH – *The art of computer programming. Vol. 1-4*, Addison-Wesley, 2005. 66, 67, 68

Kor15. I. KORTCHEMSKI – « Predator-Prey Dynamics on Infinite Trees : A Branching Random Walk Approach », Prépublication arXiv:1312.4933 à paraître dans *Journal of Theoretical Probability*, DOI 10.1007/s10959-015-0603-2, 2015. 303

KP95. P. E. KLOEDEN et E. PLATEN – « Numerical methods for stochastic differential equations », Nonlinear dynamics and stochastic mechanics, CRC Math. Model. Ser., CRC, Boca Raton, FL, 1995, p. 437–461. 374
KPSC08. A. M. KRIEGER, M. POLLAK et E. SAMUEL-CAHN – « Beat the mean : sequential selection by better than average rules », *J. Appl. Probab.* **45** (2008), no. 1, p. 244–259. 137

KS66. H. KESTEN et B. P. STIGUM – « A limit theorem for multidimensional Galton-Watson processes », *Ann. Math. Statist.* **37** (1966), p. 1211–1223. 54

KS76. J. G. KEMENY et J. L. SNELL – *Finite Markov chains*, Springer-Verlag, New York, 1976, Reprinting of the 1960 original, Undergraduate Texts in Mathematics. 127

KS91. I. KARATZAS et S. E. SHREVE – *Brownian motion and stochastic calculus*, second éd., Graduate Texts in Mathematics, vol. 113, Springer-Verlag, New York, 1991. 376

Lac10. H. LACOIN – « New bounds for the free energy of directed polymers in dimension 1 + 1 and 1 + 2 », *Comm. Math. Phys.* **294** (2010), no. 2, p. 471–503. 265

Law13. G. F. LAWLER – *Intersections of random walks*, Modern Birkhäuser Classics, Birkhäuser/Springer, New York, 2013, Reprint of the 1996 edition. 37

LBG92. G. F. LAWLER, M. BRAMSON et D. GRIFFEATH – « Internal diffusion limited aggregation », *Ann. Probab.* **20** (1992), no. 4, p. 2117–2140. 91

LG13. J.-F. LE GALL – *Mouvement brownien, martingales et calcul stochastique*, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 71, Springer, Heidelberg, 2013. 375

Lig85. T. M. LIGGETT – *Interacting particle systems*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. 265

LL10. G. F. LAWLER et V. LIMIC – *Random walk : a modern introduction*, Cambridge Studies in Advanced Mathematics, vol. 123, Cambridge University Press, Cambridge, 2010. 37

LP15. R. LYONS et Y. PERES – *Probability on trees and networks*, Cambridge University Press, 2015. 68

LPW09. D. A. LEVIN, Y. PERES et E. L. WILMER – *Markov chains and mixing times*, American Mathematical Society, Providence, RI, 2009, With a chapter by James G. Propp and David B. Wilson. 17, 38, 81, 127, 375

LW09. Q. LIU et F. WATBLED – « Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment », *Stochastic Process. Appl.* **119** (2009), no. 10, p. 3101–3132. 265

Lé08. T. LÉVY – « Probabilistic methods in statistical physics », Lecture notes - Tsinghua University, October 2008. 229

Mah09. H. M. MAHMOUD – *Pólya urn models*, Texts in Statistical Science Series, CRC Press, Boca Raton, FL, 2009. 214

Mar04. J.-F. MARCKERT – « Structures arborescentes, algorithmes », Habilitation à diriger des recherches, 2004. 55
Mau03. A. MAURER – « A bound on the deviation probability for sums of non-negative random variables », JIPAM. J. Inequal. Pure Appl. Math. 4 (2003), no. 1, p. Article 15, 6 pp. (electronic). 138

McD89. C. MCDIARMID – « On the method of bounded differences », Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, p. 148–188. 277

McD98. –, « Concentration », Probabilistic methods for algorithmic discrete mathematics, Algorithms Combin., vol. 16, Springer, Berlin, 1998, p. 195–248. 277

Mik09. T. MIKOSCH – *Non-life insurance mathematics*, second éd., Universi-text, Springer-Verlag, Berlin, 2009, An introduction with the Poisson process. 252

MM09. M. MÉZARD et A. MONTANARI – *Information, physics, and computation*, Oxford Graduate Texts, Oxford University Press, Oxford, 2009. 277

MP10. P. MÖRTERS et Y. PERES – *Brownian motion*, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2010, With an appendix by Oded Schramm and Wendelin Werner. 325

MR95. R. MOTWANI et P. RAGHAVAN – *Randomized algorithms*, Cambridge University Press, Cambridge, 1995. 16, 66

MRR¹⁵³. N. METROPOLIS, A. ROSENBLUTH, M. ROSENBLUTH, A. TELLER et E. TELLER – « Equations of State Calculations by Fast Computing Machines », *Journal of Chemical Physics* (1953), no. 21, p. 1087–1092. 81

MV12. S. MÉLÉARD et D. VILLEMONAIS – « Quasi-stationary distributions and population processes », *Probab. Surv.* 9 (2012), p. 340–410. 54

MW90. B. D. MCKAY et N. C. WORMALD – « Uniform generation of random regular graphs of moderate degree », *J. Algorithms* 11 (1990), no. 1, p. 52–67. 67

Mé13. S. MÉLÉARD – « Modèles aléatoires en écologie et évolution », Cours de l'École Polytechnique, 2013. 172, 185, 199

Nel67. E. NELSON – *Dynamical theories of Brownian motion*, Princeton University Press, Princeton, N.J., 1967. 356

Nev72. J. NEVEU – *Martingales à temps discret*, Masson et Cie, éditeurs, Paris, 1972. 375

Nev75. J. NEVEU – *Discrete-parameter martingales*, revised éd., North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1975, Translated from the French by T. P. Speed, North-Holland Mathematical Library, Vol. 10. 375

Nor98a. J. R. NORRIS – *Markov chains*, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 2, Cambridge University Press, Cambridge, 1998, Reprint of 1997 original. 37, 127, 155, 252

Nor98b. J. R. NORRIS – *Markov chains*, Cambridge University Press, 1998. 375
NS60. D. J. NEWMAN et L. SHEPP – « The double dixie cup problem », Amer. Math. Monthly **67** (1960), p. 58–61. 16

ODA88. H. G. OTHMER, S. R. DUNBAR et W. ALT – « Models of dispersal in biological systems », J. Math. Biol. **26** (1988), no. 3, p. 263–298. 313

OK08. T. J. OTT et J. H. B. KEMPERMAN – « Transient behavior of processes in the TCP paradigm », Probab. Engrg. Inform. Sci. **22** (2008), no. 3, p. 431–471. 242

Øks03. B. ØKSENDAL – *Stochastic differential equations*, sixth éd., Universi-text, Springer-Verlag, Berlin, 2003, An introduction with applications. 375

Par07. E. PARDOUX – *Processus de Markov et applications*, Collection Sciences Sup, Dunod, 2007, Mathématiques appliquées/SMAI. 81, 102, 375

Pem07. R. PEMANTLE – « A survey of random processes with reinforcement », Probab. Surv. **4** (2007), p. 1–79. 214, 215

Per07. B. PERTHAME – *Transport equations in biology*, Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2007. 243

Pit06. J. PITMAN – *Combinatorial stochastic processes*, Lecture Notes in Mathematics, vol. 1875, Springer-Verlag, Berlin, 2006, Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002, With a foreword by Jean Picard. 185, 199

Pre00. J. PREATER – « Sequential selection with a better-than-average rule », Statist. Probab. Lett. **50** (2000), no. 2, p. 187–191. 137

PW96. J. D. PROPP et D. B. WILSON – « Exact sampling with coupled Markov chains and applications to statistical mechanics », Random Structures Algorithms **9** (1996), no. 1-2, p. 223–252. 81

PW98. –, « Coupling from the past : a user’s guide », Microsurveys in discrete probability (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 41, Amer. Math. Soc., Providence, RI, 1998, p. 181–192. 81

RC04. C. P. ROBERT et G. CASELLA – *Monte Carlo statistical methods*, second éd., Springer Texts in Statistics, Springer-Verlag, New York, 2004. 81

Rev97. D. REVUZ – *Probabilités*, Hermann, 1997. 375

Rob00. P. ROBERT – *Réseaux et files d’attente : méthodes probabilistes*, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 35, Springer-Verlag, Berlin, 2000. 155, 373

Rob05. –, « Réseaux de communication, algorithmes et probabilités », Cours de l’École Polytechnique, Palaiseau, France, 2005. 242

Rob10. –, « Mathématiques et réseau de communication », Dossiers pour la science (2010) hal:inria-00472217, 2010. 242

Roy99. G. ROYER – *Une initiation aux inégalités de Sobolev logarithmiques*, Cours Spécialisés [Specialized Courses], vol. 5, Société Mathématique de France, Paris, 1999. 344

RRS05. S. ROBIN, F. RODOLPHE et S. SCHBATH – *DNA, words and models*, Cambridge University Press, Cambridge, 2005, Translated from the 2003 French original. 102
Rud87. W. RUDIN – *Real and complex analysis*, third éd., McGraw-Hill Book Co., New York, 1987. 325

Rug01. C. RUGET (éd.) – *Mathématiques en situation*, SCOPOS, vol. 11, Springer-Verlag, Berlin, 2001, Issues de l'épreuve de modélisation de l'agrégation. [From the Examination in Modelling for the Agrégation]. 54

RW00. L. C. G. ROGERS et D. WILLIAMS – *Diffusions, Markov processes, and martingales*. Vol. 1, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2000, Foundations, Reprint of the second (1994) edition. 376

RY99. D. REVUZ et M. YOR – *Continuous martingales and Brownian motion*, third éd., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 293, Springer-Verlag, Berlin, 1999. 375

Ré85. J.-L. RÉMY – « Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire », *R.A.I.R.O. Informationique Théorique* **19** (1985), no. 2, p. 179–195. 68

She07. S. SHEFFIELD – « Gaussian free fields for mathematicians », *Probab. Theory Related Fields* **139** (2007), no. 3-4, p. 521–541. 37

Shi96. A. N. SHIRYAEV – *Probability*, second éd., Graduate Texts in Mathematics, vol. 95, Springer-Verlag, New York, 1996, Translated from the first (1980) Russian edition by R. P. Boas. 375

SM02. J. SILTANEVA et E. MÄKINEN – « A comparison of random binary tree generators », *The Computer Journal* **45** (2002), no. 6, p. 653–660. 68

Spi70. F. SPITZER – *Principes des cheminements aléatoires*, Traduit de l'anglais par E. Baverez et J.-L. Guignard. Centre Interarmés de Recherche Opérationnelle, vol. 2, Dunod, Paris, 1970. 37

Sta83. A. J. STAM – « Generation of a random partition of a finite set by an urn model », *J. Combin. Theory Ser. A* **35** (1983), no. 2, p. 231–240. 67

Ste94. J. M. STEELE – « Le Cam's inequality and Poisson approximations », *Amer. Math. Monthly* **101** (1994), no. 1, p. 48–54. 15

Ste97. –, *Probability theory and combinatorial optimization*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 69, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. 15, 277

Tal96. D. TALAY – « Probabilistic numerical methods for partial differential equations : elements of analysis », Probabilistic models for nonlinear partial differential equations (Montecatini Terme, 1995), Lecture Notes in Math., vol. 1627. Springer, Berlin, 1996, p. 148–196. 374

Tal02. –, « Stochastic Hamiltonian systems : exponential convergence to the invariant measure, and discretization by the implicit Euler scheme », *Markov Process. Related Fields* **8** (2002), no. 2, p. 163–198, Inhomogeneous random systems (Cergy-Pontoise, 2001). 356

Tar11. P. TARRÈS – « Localization of reinforced random walks », arXiv:1103.5536, 2011. 215
Tav04. S. TAVARÉ – « Ancestral inference in population genetics », Lectures on probability theory and statistics, Lecture Notes in Math., vol. 1837, Springer, Berlin, 2004, p. 1–188. 172, 185, 199

Tou99. P. TOULOUSE – *Thèmes de probabilités et statistique*, Dunod, 1999. 375

TPH86. J. N. TSITSIKLIS, C. H. PAPADIMITRIOU et P. HUMBLET – « The performance of a precedence-based queueing discipline », *J. Assoc. Comput. Mach.* **33** (1986), no. 3, p. 593–602. 303

TT90. D. TALAY et L. TUBARO – « Expansion of the global error for numerical schemes solving stochastic differential equations », *Stochastic Anal. Appl.* **8** (1990), no. 4, p. 483–509 (1991). 374

TVW10. A. TRIPATHI, S. VENUGOPALAN et D. B. WEST – « A short constructive proof of the Erdős-Gallai characterization of graphic lists », *Discrete Math.* **310** (2010), no. 4, p. 843–844. 67

vdH14. R. VAN DER HOFSTAD – « Random Graphs and Complex Networks », Lecture notes available on Internet, 2014. 67, 215, 229

Vil03. C. VILLANI – *Topics in optimal transportation*, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. 243

Vil06. –, « Hypocercive diffusion operators », International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, p. 473–498. 356

Vil08. –, « H-theorem and beyond : Boltzmann’s entropy in today’s mathematics », Boltzmann’s legacy, ESI Lect. Math. Phys., Eur. Math. Soc., Zürich, 2008, p. 129–143. 357

Vil09. –, « Hypocoercivity », *Mem. Amer. Math. Soc.* **202** (2009), no. 950, p. iv+141. 356

Wil91. D. WILLIAMS – *Probability with martingales*, Cambridge Mathematical Textbooks, Cambridge University Press, Cambridge, 1991. 102, 375

Wil96. D. B. WILSON – « Generating random spanning trees more quickly than the cover time », In Proceedings of the 28'th annual ACM symposium on Theory of computing pages 296–303, 1996. 68

WL01. F. WANG et D. P. LANDAU – « Efficient, Multiple-Range Random Walk Algorithm to Calculate the Density of States », *Physical Review Letters* **86** (2001), p. 2050. 81

Yca02. B. YCART – *Modèles et algorithmes markoviens*, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 39, Springer-Verlag, Berlin, 2002. 325

Yuk98. J. E. YUKICH – *Probability theory of classical Euclidean optimization problems*, Lecture Notes in Mathematics, vol. 1675, Springer-Verlag, Berlin, 1998. 277
<figure><img src="image_86.png" /></figure>
Index

absence de mémoire, 143, 182, 214, 240

actuariat, 252

ADN, 93, 180

agrégation limitée par diffusion interne,
84, 91

algorithme
de Stam, 62
BFS, 227
d'Arnold-Sleep, 65
de Fisher-Yates-Knuth, 59, 190
de Kiefer-Wolfowitz, 112
de Metropolis-Hastings, 72, 112
de Propp-Wilson, 77
de Rémy, 68
de segmentation, 102
de tri rapide, 58
de tri rapide randomisé, 66
des configurations, 64
du parcours en largeur, 227
du recuit simulé, 75, 268, 269
du rejet, 60
EM, 109
progressif-rétrograde, 95
Robbins-Monro, 112

ancêtre commun le plus récent, 174

appariement, 60, 64
euclidien minimal, 267

apériodique, voir chaîne de Markov
arbre, 218
binaire, 64
couvrant de loi uniforme, 68
couvrant minimal, 267
de Galton-Watson, 40, 220, 227

conditionné à taille fixe, 68

enraciné, 64

planaire, 64

régulier, 220

Arnold-Sleep, voir algorithme de
attachement préférentiel, 205

Avogadro, voir nombre de

Azuma-Hoeffding, voir inégalité de,
voir inégalité de

Barabási-Albert, voir graphe aléatoire
de

Barbour-Eagleson, voir inégalité de
battage de cartes, 34

Bearwood-Halton-Hammersley, voir
théorème de

Bell, voir nombres de, voir nombres de

Berry-Esseen, voir théorème limite
central de, voir théorème de, voir
théorème limite central de

Birkhoff, voir théorème de
bistochastique, voir doublement
stochastique

bits, 3

Bollobás, voir algorithme des confi-
gurations, voir modèle des
configurations

Boltzmann, voir entropie de

Boltzmann, voir entropie de, voir
théorie cinétique des gaz

Borell-Cantelli, voir lemme de
boucle auto-évitante, 224

branchement, voir propriété de
Burkholder-Davis-Gundy, voir inégalité
de

Cannings, voir modèle de
Carleman, voir condition de
Catalan, voir nombres de, voir nombres
de, voir nombres de

Cauchy, voir loi de

Cayley, voir graphe de

Cesàro, voir lemme de

champ libre gaussien, 33, 70

Chapman-Kolmogorov, voir équation
de, voir équation de

chaîne de Markov

apériodique, 34, 35, 72, 94, 115, 166

cachée, 93

incluse, 237

paresseuse, 115, 359

échantillonnée, 360

chemin auto-évitant, 218

Chen-Stein, voir méthode de

Chernoff, voir inégalité de, voir
théorème de

circuit hamiltonien, 267

Clopper-Pearson, voir intervalle de
confiance de

coalescence des trajectoires, 78

coalescent de Kingman, 183

collectionneur de coupons, 1, 9, 27, 35,
115

comparaison série-intégrale, 89, 133,
193

composante connexe géante, 227

condition

de Carleman, 296

de Doeblin, 72

de Lindeberg, 131

de Lyapunov, 87, 88

configurations, voir modèle de

constante

d'Euler, 10

de connectivité, 223

convergence abrupte, 36, 121

couplage, voir méthode de, voir
méthode de, voir méthode de

Courant-Fischer, voir formule varia-
tionnelle de

courbe de Jordan, 224

covariance, 279, 328

empirique, 279, 295

Cramér-Lundberg, voir modèle de
Cramér-Von Mises, voir théorème de
crible de Poincaré, 12, 60

de Moivre-Laplace, voir théorème limite
central de

demi-cercle, voir loi du

Dirichlet, voir problème de, voir
problème de

distance

de Wasserstein, 236

de couplage, 243

de Fréchet, 243

de Kolmogorov-Smirnov, 285

de Mallows, 243

de Wasserstein, 16, 152, 284, 338,
339, 352, 354

en variation totale, 5, 152

divergence de Kullback-Leibler, 342

Dobinski, voir formule de

Doeblin, voir condition de

Donsker, voir théorème de

Doob, voir théorème d'arrêt

doublement stochastique, 35, 114

Dunford, voir décomposition de
décomposition

de Dunford, 355

dépoissonisation, 274

dérangement, 60

Désiré André, voir formule de
désordre, 256

Ehrenfest, voir modèle de, voir urne de
EM, voir algorithme

entropie, 113, 264

de Boltzmann, 70, 161

de Shannon, 161

relative, 110, 342, 352

environnement aléatoire, 254, 256

Erdős-Gallai, voir théorème de

Erdős-Rényi, voir graphe aléatoire, voir
graphe aléatoire de

erreur

faible, 372

forte, 373

estimateur de maximum de vraisem-
blance, 101, 107

Euler, voir constante de, voir schéma d'
Ewens, voir formule d'échantillonnage,
voir loi de
excursion, 310

famille exponentielle, 71

Fekete, voir lemme de, voir lemme de
file

d'attente, 142, 373

fluide, 373

filtre de Kalman, 99

Fisher-Yates, voir algorithme de, voir
algorithme de

fixation, 159, 162

FKG, voir inégalité

Fokker-Planck, voir équation de, voir
équation de

fonction

Beta, 203

caractéristique, 14, 177, 247, 322

contractante, 77

d'acceptation-rejet, 73, 75

d'échelle, 364

de Green discrète, 32

de partition, 69, 254

de renforcement, 209

Gamma, 203

génératrice, 23, 41, 149, 220, 222,
241, 322

harmonique, 24, 30, 315

formule

d'Isserlis, 61

d'Itô, 318, 328, 331, 365, 373

d'Itô discrète, 24

d'échantillonnage d'Ewens, 183

de Bayes, 100

de Dobinski, 62

de Désiré André, 25

de Hadamard, 289

de Kantorovich-Rubinstein, 153

de la moyenne, 315

de Mehler, 329

de Placherel, 334

variationnelle de Courant-Fischer,
285

Fourier, voir transformée de
Friedman, voir urne de
Frobenius, voir norme de
Fréchet, voir distance de

Galton-Watson, voir arbre de, voir
processus de

Gibbs, voir mesure de, voir échantillon-
neur de

graphe

d-régulier, 63

aléatoire, 70, 218

aléatoire de Barabási-Albert, 205

aléatoire de Erdős-Rényi, 63, 226

complet, 226

de Bethe, 220

de Cayley, 190

dual, 224

fini, 62

régulier, 74

à attachement préférentiel, 205

Green, voir fonction de

groupe symétrique, 34, 58, 59, 70, 187,
267

Grönwall, voir lemme de

Gumbel, voir loi de

générateur infinitésimal, 151, 154, 232,
240, 252, 330

Hadamard, voir formule de

hamiltonien, 69, voir circuit hamiltonien

Hardy-Weinberg, voir loi de

harmonique, voir fonction, voir mesure

Hermite, voir polynôme d'

Hilbert-Schmidt, voir norme de

Hoffman-Wielandt, voir inégalité de

Hoppe, voir urne de

horloges exponentielles en compétition,
143

hypoellipticité, 349

Hörmander, 349

identité de Vandermonde, 28

immigration, voir processus de
Galton-Watson

intervalle

de confiance de Clopper-Pearson, 3

de confiance de Wald, 3

de prédiction, 12, 13

inégalité

de Jensen, 110

de Le Cam, 15

d'Azuma-Hoeffding, 89, 137, 215,
270, 272, 286
de Barbour-Eagleson, 15

de Burkholder-Davis-Gundy, 373

de Chernoff, 124, 270

de Hoffman-Wielandt, 284

de Jensen, 71, 257, 262, 337, 338, 342

de Le Cam, 9, 195

de Markov, 12, 147, 193, 228, 271, 288

de Poincaré, 336, 337, 356

de Schwarz, 118, 288, 337, 340

de Sobolev logarithmique, 340-343, 356

de Tchebychev, 123, 270, 286

FKG, 256, 259

fonctionnelle, 356

Maurer, 138

irréversibilité, 113, 352

Ising, voir modèle de

Isserlis, voir formule de

Itô, voir formule de

Jensen, voir inégalité de, voir inégalité de, voir inégalité de

jeu de dé, 9

jeu de pile ou face, 1, 40, 163, 193, 197, 205, 218

Jordan, voir courbe de

Kalman, voir filtre de

Kantorovich-Rubinstein, voir formule de

Kingman, voir coalescent de

Knuth, voir algorithme de, voir algorithme de

Kolmogorov, voir loi du zéro-un, voir processus de diffusion

Kolmogorov-Smirnov, voir distance de, voir théorème de

Kullback-Leibler, voir divergence de

Langevin, voir processus de

Laplace, voir transformée de, voir principe de, voir transformée de

laplacien discret, 30

Le Cam, voir inégalité de, voir inégalité de

lemme

de Borel-Cantelli, 3, 13, 77, 147, 193, 197, 277, 287

de Cesàro, 88

de Fekete, 223, 262

de Grönwall, 343, 373

de Rényi, 144

de Scheffé, 48

de Slutsky, 195

de Wald, 247

loi

Beta, 3, 167, 199, 203, 369

Beta-binomiale, 3, 203

binomiale, 2

binomiale-négative, 2

d'Ewens, 70, 183, 189

de Bernoulli, 1

de Cauchy, 322, 323

de Gumbel, 13, 120, 133, 135, 179

de Hardy-Weinberg, 157, 158

de Mendel, 157

de Pareto, 136, 215

de Pascal, 2

de Poisson, 8, 58

de Rademacher, 19, 306

de reproduction, 39

de Zipf, 215

des grands nombres, 3, 23, 247, 248, 279, 281-283, 370

chaînes de Markov, 98, 166

martingales, 102, 103, 131

des petits nombres, 9, 155, 226, 231, 361

des événements rares, 155

du quart-de-cercle, 295

du demi-cercle, 24, 282

du logarithme itéré de Strassen, 211, 248

du zéro-un

de Kolmogorov, 225, 258

pour les lois exponentielles, 145, 214

pour les polymères, 258

géométrique, 2

invariante, 34-36, 72, 73, 79, 81, 97, 98, 114, 115, 117, 119, 122, 125, 127, 151-155, 166-168, 234, 235, 306, 313, 331, 337, 342-344, 350, 352, 353, 356, 357, 361, 367, 369, 370

multinomiale, 26, 42, 173

réversible, 73, 114, 152, 331, 352

uniforme
appariements, 61

arbre couvrant, 68

arbres binaires enracinés planaires,
65

graphes finis, 63

groupe symétrique, 59, 190

partitions d'un ensemble fini, 62

Malliavin, 349

Mallows, voir distance de

marche aléatoire, 20, 26, 27, 50, 227,
248, 254, 321

persistante, 313

renforcée par sites, 210

sur le cube discret, 114

sur le groupe symétrique, 34

Marchenko-Pastur, voir théorème de

Markov, voir inégalité de, voir propriété de, voir propriété de, voir inégalité de, voir semi-groupe de

martingale, 3, 24, 31, 44, 88, 101, 131,
161, 162, 170, 202, 270, 318, 331,
350, 365, 368

bornée, 45, 161, 319, 324

bornée dans $L^2$, 48, 134, 180, 194,
241, 261

positive, 44, 45, 137, 161, 227, 249,
258

matrice

aléatoire, 280

d'adjacence, 62

de covariance, 279

de covariance empirique, 279, 295

de remise, 205

de Vandermonde, 171

Maurer, voir inégalité de

maximum de vraisemblance, 101, 107

Mendel, voir loi de

mesure

de Gibbs, 69, 254, 337

de vitesse, 364

harmonique, 31

spectrale empirique, 280

Metropolis-Hastings, voir algorithme de
modèle

des configurations, 64

d'Ehrenfest, 113

d'Erdős-Rényi, voir graphe aléatoire
de

d'Ising, 70, 81

de Cannings, 169

de Cramér-Lundberg, 252

de Moran, 158

de Wright-Fisher, 21, 42, 130, 157,
161, 174, 366

des configurations, 64

moment, voir méthode du

moments, voir méthode des

caractérisation, 289

exponentiels, 270

monotonie, 78

Monte-Carlo, voir méthode de

Moran, voir modèle de

mouvement brownien, 317, 327, 356,
363, 365

multigraphe, 63

mélange

de lois, 106, 203

de lois gaussiennes, 108

méthode

de couplage, 237

de Chen-Stein, 15

de couplage, 8, 16, 21, 85, 86, 115,
152, 163, 219, 224, 227, 236, 284,
339, 355

coalescent, 78

de couplage par le passé, 78

de Monte-Carlo, 112, 269

de simulation par inversion, 57

de simulation par rejet, 60

des moments, 87, 235, 287, 289

du second moment, 12, 193

naissance et mort, voir processus de
nombre d'Avogadro, 121

nombres

de Bell, 61, 197

de Catalan, 24, 26, 37, 66, 290

de Stirling de première espèce, 198

de Stirling de seconde espèce, 10, 176,
197, 198

norme

de Frobenius, 284

de Hilbert-Schmidt, 284

de Schur, 284

noyau

de Poisson, 318, 319, 323

de Poisson discret, 31
de proposition ou d'exploration, 73

optimisation combinatoire randomisée,
267

Ornstein-Uhlenbeck, voir processus de,
voir semi-groupe d'
oscillation, 270

PDMP, voir processus de Markov
déterministe par morceaux, voir
processus de Markov déterministe
par morceaux

percolation, 218

phylogénie, 185

phénomène
de seuil, 15, 41, 121, 220, 255, 256

Plancherel, voir formule de

Pochhammer, voir polynôme de

Poincaré, voir crible de, voir crible de,
voir inégalité de

Poisson, voir processus de, voir noyau
de

poissonisation, 195, 274

polymère, 70, 253, 255

polynôme
d'Hermite, 333
de Pochhammer, 198

pont brownien, 371

principe
d'inclusion-exclusion, 12, 60, 198
d'invariance de Donsker, 346, 363
de Laplace, 74
de rotation, 51, 303
des tiroirs, 273
du maximum, 318

probabilité
critique, 219
d'extinction, 43
de percolation, 218

problème
d'arrêt optimal, 138
de contrôle stochastique, 138
de Dirichlet, 316
de Dirichlet discret, 30
de la ruine du joueur, 21, 30, 85
des secrétaires, 138
du mariage, 138
du voyageur de commerce, 75, 267
processus

de Poisson, 181
autorégressif, 19, 99, 237, 332
d'Ornstein-Uhlenbeck, 127, 155, 327,
347, 364

de Bernoulli, 2

de diffusion de Kolmogorov, 344

de Galton-Watson, 174, 227, 239, 302,
304

de Galton-Watson avec immigration,
52

de Langevin confiné, 347
de Markov déterministe par
morceaux, 232, 246

de Markov à temps continu, 154

de mort pur, voir processus de Yule

de naissance et de mort, 154, 176

de Poisson, 3, 119, 142, 231, 245, 297,
306

de Poisson aminci, 145

de Poisson composé, 247

de taille de fenêtre TCP, 232

de Wiener, 356

de Yule, 144, 146, 154, 239

des restaurants chinois, 130, 181, 183,
187

gaussien, 328

ponctuel de Poisson, 274

Prohorov, voir théorème de, voir
théorème de

Propp-Wilson, voir algorithme de
propriété

de branchement, 40, 48

de Markov, 48, 258, 260, 262, 306,
318

Pólya, voir urne de

Rademacher, voir loi de
recuit simulé, voir algorithme du

renforcement, 201
géométrique, 210
linéaire, 210

restaurants chinois, voir processus des
ruine du joueur, voir problème de la
Rémy, voir algorithme de
Rényi, voir lemme de

réseau, 228

réversibilité, 113

réversible, voir loi
Scheffé, voir lemme de

Schur, voir norme de

Schwarz, voir inégalité de, voir inégalité
de, voir inégalité de, voir inégalité
de

schéma

d'Euler, 372

schéma d'Euler, 371

scrutin, voir théorème du

second principe de la thérnodynamique,
113

semi-groupe

d'Ornstein-Uhlenbeck, 329
de Markov, 233, 360

Shakespeare, 3

Shannon, voir entropie de

simulation exacte, 81

Slutsky, voir lemme de

Sobolev, voir inégalité de

sous-additivité, 223, 262, 274, 275

sous-martingale

bornée dans L¹, 53

spectre

de matrice de covariance empirique,
295

de matrice de transition, 117, 170,
171, 235, 333
trou, 335

spin, 33, 70

Stam, voir algorithme de

statistique d'ordre, 129, 144

Stirling, voir nombres de

Strassen, voir loi du logarithme itéré,
voir loi du logarithme itéré

sur-martingale, 250

symbole de Pochhammer, 198

série génératrice, 333

Tchebychev, voir inégalité de, voir
inégalité de

temps

d'arrêt borné, 250

d'atteinte, 30, 50, 85, 159

d'explosion, 239

de coalescence, 78, 116, 119, 120

de contraction, 77

de couplage, 78

de fixation, 159, 162

de recouvrement, 17

de relaxation, 347

de retour, 125

de sortie, 21, 318

température inverse, 69, 254

tension, 283

théorie

cinétique de gaz de Boltzmann, 113

de Mendel, 157

des probabilités libres, 296

du transport optimal de la mesure,
243

théorème

d'arrêt, 24, 31, 161, 227

d'Erdős-Gallai, 63

de Bearwood-Halton-Hammersley,
268

de Berry-Esseen, 15, 195

de Birkhoff, 313

de Chernoff, 302, 303

de Cramér-Von Mises, 371

de Donsker, 346, 363

de Kolmogorov-Smirnov, 371

de Marchenko-Pastur, 294

de Prohorov, 283, 288

de Weierstrass, 289

de Wigner, 281, 282

de Wigner simplifié, 283

de Yaglom, 45

des séries centrées, 131, 133, 194

du scrutin, 25

ergodique

chaînes de Markov, 98, 166

chaînes de Markov (fluctuation), 98

processus de Markov, 313

limite central, 3, 4, 23, 37, 124, 195,
346, 363, 370

chaînes de Markov, 98

de Berry-Esseen, 4, 15

de Lindeberg-Lévy, 131, 195

de Moivre-Laplace, 4

martingales, 87, 91, 102, 103, 131,
195

transformée

de Laplace, 48

de Fourier, 296

de Laplace, 135, 227, 228, 241, 250,
270, 310, 333

transition de phase, 256

trou spectral, 335
urne
d'Ehrenfest, 113
de Friedman, 91
de Hoppe, 199
de Pólya, 91, 201
de Pólya généralisée, 205, 210, 213

valeurs singulières, 295

Vandermonde, voir identité de, voir
matrice de

variation totale, voir distance de
vecteur gaussien, 99, 328

vie et mort, voir processus de naissance
et de mort

von Neumann, 3

voyageur de commerce, voir problème
du, voir problème du

vraisemblance, 101, 107

Wald, voir intervalle de confiance de,
voir lemme de

Wasserstein, voir distance de, voir
distance de, voir distance de, voir
distance de

Weierstrass, voir théorème de

Wiener, voir processus de

Wigner, voir théorème de

théorème de, 282

théorème simplifié de, 283

Wright-Fisher, voir modèle de

Yaglom, voir théorème de

Yule, voir processus de, voir processus
de

: échangeabilité, 171, 203

échantillonneur de Gibbs, 74

égalité en loi, 50

: énergie, 69

libre, 255

équation

aux dérivées partielles, 306, 330

de Chapman-Kolmogorov, 149, 234,
241

de Fokker-Planck, 333

de Fokker-Planck cinétique, 352

de la chaleur, 310, 324

de la chaleur avec dérive, 330

des ondes, 310

différentielle stochastique, 165, 167,
327, 328, 344, 355, 364, 366, 368,
371

du télégraphe, 306, 310, 313

maîtresse, 207
A
Principales notations et abréviations

$d_{VT}(\mu, \nu)$ distance en variation totale

$W_p(\mu, \nu)$ distance de Wasserstein d'ordre $p$

$L^p(\mu)$ espace de fonctions $f$ t.q. $|f|^p$ est $\mu$-intégrable

$L^p(E)$ espace de fonctions $f$ t.q. $|f|^p$ est Lebesgue intégrable sur $E$

$L^p_{\text{loc}}$ espace de fonctions $f$ t.q. $|f|^p$ est localement intégrable

$\|f\|_p$ norme $L^p(\mu)$ de la fonction $f$

$\|M\|_{\text{HS}}$ norme de Hilbert-Schmidt $\sqrt{\text{Tr}(MM^*)}$ de la matrice $M$

$\text{Tr}(M)$ trace de la matrice $M$

$|x|$ norme, module, ou valeur absolue de $x$

$S_n$ groupe symétrique

$[x]$ plus grand entier inférieur ou égal à $x$ (partie entière)

$\overline{x}$ plus petit entier supérieur ou égal à $x$

log logarithme naturel

$X \stackrel{\text{loi}}{=} Y$ égalité en loi

$X \sim \mu$ la variable aléatoire $X$ suit la loi $\mu$

$x := a$ $x$ est défini par $a$

$a := x$ $x$ est défini par $a$

$a \wedge b$ $\min(a, b)$

$a \vee b$ $\max(a, b)$

$\nu \ll \mu$ $\nu$ est absolument continue par rapport à $\mu$

$\text{Ber}(p)$ loi de Bernoulli $n \mapsto p\mathbf{1}_{n=1} + (1-p)\mathbf{1}_{n=0}$

$\text{Bin}(n, p)$ loi binomiale $k \mapsto \binom{n}{k}p^k(1-p)^{n-k}\mathbf{1}_{k \in \mathbb{N} \cap [0, n]}$

$\text{Geo}(p)$ loi géométrique $n \mapsto (1-p)^{n-1}p\mathbf{1}_{n \in \mathbb{N}^*}$

$\text{Geo}_N(p)$ loi géométrique $n \mapsto (1-p)^n p\mathbf{1}_{n \in \mathbb{N}}$

$\text{Exp}(\lambda)$ loi exponentielle $x \mapsto \lambda e^{-\lambda x}\mathbf{1}_{x \ge 0}$

$\text{Gamma}(a, \lambda)$ loi Gamma $x \mapsto \lambda^a \Gamma(a)^{-1} x^{a-1} e^{-\lambda x} \mathbf{1}_{x \ge 0}$

$\text{Cauchy}$ loi de Cauchy $x \in \mathbb{R} \mapsto \frac{1}{\pi(1+x^2)}$

$\text{Mul}(n, p)$ loi multinomiale $k \mapsto \binom{n}{k}p_1^{k_1} \cdots p_d^{k_d} \mathbf{1}_{k \in \mathbb{N}^n: k_1 + \cdots + k_d = n}$

$\text{Poi}(\lambda)$ loi de Poisson $n \mapsto e^{-\lambda} \frac{\lambda^{\lambda}}{n!} \mathbf{1}_{n \in \mathbb{N}}$

$\text{Unif}(I)$ loi uniforme sur l'ensemble $I$

$\mathcal{N}(m, \sigma^2)$ loi gaussienne $x \mapsto (2\pi\sigma^2)^{-1/2}e^{-\frac{1}{2\sigma^2}(x-m)^2}$

$\mathcal{N}(m, \Sigma)$ loi gaussienne $x \mapsto (2\pi)^{-n/2} \det(\Sigma)^{-1/2} e^{-\frac{1}{2} \langle \Sigma^{-1}(x-m), (x-m) \rangle}$

$\chi^2(n)$ loi du chi-deux à $n$ degrés de liberté $= \text{Gamma}(n/2, 1/2)$

$t(n)$ loi de Student à $n$ degrés de liberté $= \mathcal{N}(0, 1)/\sqrt{\chi^2(n)/n}$
$x_n = o_{n \to \infty}(y_n)$ $x_n/y_n \to 0$ quand $n \to \infty$

$x = \mathcal{O}(y)$ $|x| \le C|y|$ pour une constante $C > 0$

$a_n \sim b_n$ $a_n/b_n \to 1$ quand $n \to \infty$

i.i.d. indépendantes et identiquement distribuées

p.s. presque sûrement

ssi si et seulement si

v.a. variable(s) aléatoire(s)

v.a.r. variable(s) aléatoire(s) réelle(s)

t.q. telle(s) que

LGN Loi des Grands Nombres

TLC Théorème Limite Central