AnnalesÉcoles d'ingénieurs

Mines-Ponts MP 2018 — Maths 1

Lemme de Fekete et théorème de Erdös-Szekeres · 6 pages

PDF hébergé hors du site officiel — source : archive officielle (ZIP)

Le sujet démontre le lemme de sous-additivité de Fekete après avoir étudié limites inférieure et supérieure d'une suite bornée, puis l'applique pour montrer que $P(Y_n \geqslant x)^{1/n}$ converge, où $Y_n$ est la moyenne empirique de variables i.i.d. Il prouve ensuite le théorème d'Erdös-Szekeres par un algorithme de rangement en piles, et l'utilise avec une majoration de $P(C_n \geqslant k)$ par $\binom{n}{k}/k!$ pour encadrer l'espérance de la longueur $C_n$ de la plus longue sous-suite croissante d'une permutation aléatoire uniforme : $\sqrt{n}/2 \leqslant \mathrm{E}(C_n)$ et $\limsup \mathrm{E}(C_n)/\sqrt{n} \leqslant e$ .

Le sujet, partie par partie

Partie A — Préliminaires p. 2

Espérance, variance, moments · Comparaison série-intégrale · Formule de Stirling — majoration d'une espérance, comparaison somme-intégrale, minoration de $n!$ , somme des $\ln(k)$

Partie B — Le lemme de sous-additivité de Fekete p. 2–3

Suites numériques — lemme de Fekete, suite sous-additive, limite inférieure, limite supérieure, suites adjacentes, division euclidienne

Partie C — Une application probabiliste p. 3–4

Grandes déviations · Conditionnement et indépendance · Suites numériques · Espaces probabilisés — moyenne empirique, variables indépendantes de même loi, probabilité de déviation, inclusion d'événements, sous-additivité

Partie D — Le théorème de Erdös-Szekeres p. 4–5

Dénombrement et combinatoire · Suites numériques — théorème d'Erdös-Szekeres, sous-suite monotone, suite extraite croissante, rangement en piles, raisonnement par récurrence

Partie E — Comportement asymptotique d'une suite aléatoire p. 5–6

Groupe symétrique · Espérance, variance, moments · Espaces probabilisés · Coefficients binomiaux · Conditionnement et indépendance — permutation aléatoire uniforme, plus longue sous-suite croissante, loi uniforme sur $S_n$ , $C_n$ et $D_n$ de même loi, majoration de $P(C_n \geqslant k)$ , limite supérieure de $\mathrm{E}(C_n)/\sqrt{n}$

Dans l'édifice

Espérance, variance et inégalités Intégrale de Riemann Suites réelles et limites Théorème de Bolzano-Weierstrass Complétude de ℝ Moments exponentiels et inégalité de Hoeffding Indépendance d'événements et de tribus Espaces probabilisés et probabilités conditionnelles Ensembles finis et principe des tiroirs Sommes, produits et puissances Groupe symétrique et signature