Année 2023-24 - Equipe PEIPS (CMAP)
¶

Groupe de Travail Discrete Random Objects: Limits and EStimates¶

Résumé de la séance 5 - Méthodes des premier et deuxième moments et applications ¶

Orateur : Maxime Marivain (résumé par Emmanuel Kammerer)¶

Sommaire¶

  • Premier et deuxième moments
  • Applications
  • Références

Premier et deuxième moments¶

Méthode du premier moment¶

Théorème Soit $X$ une v.a. à valeurs dans $\mathbb{N}$ telle que $\mathbb{E}[X] <\infty$. Alors $$ \mathbb{P}(X=0) \ge 1-\mathbb{E} [X]. $$

Méthode du deuxième moment¶

Théorème ([MU05] Theorem 6.7) Soit $X$ une v.a. à valeurs dans $\mathbb{N}$ telle que $\mathbb{E}[X^2] <\infty$. Alors $$ \mathbb{P}(X=0) \le \frac{\mathrm{Var}(X)}{\mathbb{E} [X]^2}. $$

Applications¶

Cliques de taille $4$ pour Erdős-Rényi¶

Une clique d'un graphe est un sous-ensemble de sommets dont le sous-graphe induit est complet.

Théorème ([MU05] Theorem 6.8) Soit $\varepsilon >0$.
  • Si $p=o(n^{-2/3})$, alors pour $n$ assez grand la probabilité pour que $\mathcal{G}(n,p)$ ait une clique de taille $4$ ou plus est inférieure ou égale à $\varepsilon$.
  • Si $p=\omega(n^{-2/3})$, alors pour $n$ assez grand la probabilité pour que $\mathcal{G}(n,p)$ n'ait pas de clique de taille $4$ ou plus est inférieure ou égale à $\varepsilon$.

idées de démonstration

  • Le cas où $p=o(n^{-2/3})$ se traite par la méthode du premier moment, en remarquant qu'un sous-ensemble de sommets fixé de taille $4$ forme une clique avec probabilité $p^6$. L'espérance du nombre de cliques de taille $4$ est donc $\binom{n}{4} p^6$.
  • Le cas où $p=\omega(n^{-2/3})$ se traite à l'aide de la méthode du second moment, en majorant la variance grâce au lemme suivant :
Lemme Soient $Y_1, \ldots, Y_n$ des v.a. de Bernoulli et soit $Y= \sum_{i=1}^n Y_i$. Alors $$ \mathrm{Var}(Y) \le \mathbb{E}[Y]+ \sum_{\substack{1 \le i,j \le n \\ i\neq j}} \mathrm{Cov} (Y_i,Y_j). $$

Le résultat du lemme vient du fait que $\mathrm{Var}(Y_i) \le \mathbb{E}[Y_i^2]=\mathbb{E}[Y_i]$ pour tout $1\le i \le n$.

Pour appliquer ce lemme, notons $C_1, \ldots C_{\binom{n}{4}}$ l'ensembles des parties de taille $4$ de $\{1,\ldots, n \}$. Pour tout $1 \le i \le \binom{n}{4}$, notons $ X_i = {\bf 1}_{C_i \text{ est une clique dans } \mathcal{G}(n,p)} $ et notons $X=\sum_{i=1}^n X_i$.

Pour tous $1 \le i\neq j \le \binom{n}{4}$, on a

  • Si $\vert C_i \cap C_j\vert \le 1$, alors $\mathrm{Cov}(X_i,X_j)=0$.
  • Si $\vert C_i \cap C_j\vert =2$, alors $\mathrm{Cov}(X_i,X_j)\le \mathbb{E}[X_i X_j] = p^{11}$ puisqu'il y a $11$ arêtes à considérer.
  • Si $\vert C_i \cap C_j\vert =3$, alors $\mathrm{Cov}(X_i,X_j)\le \mathbb{E}[X_i X_j] = p^{9}$ puisqu'il y a $9$ arêtes à considérer.

Ainsi, par le lemme, $$ \mathrm{Var} (X) \le \mathbb{E}[X] + \binom{n}{6} \binom{6}{2,2,2} p^{11} + \binom{n}{5} \binom{5}{2}p^9 = o(n^8 p^{12}), $$ ce qui conclut.

Plus longue sous-suite croissante¶

Proposition ([Fer23] Proposition 2.4) Soit $\sigma_n$ une permutation aléatoire uniforme de taille $n$. Notons $\ell_n$ la longueur de sa plus longue sous-suite croissante. Alors $$ \mathbb{P}\left(\ell_n \ge 3 \sqrt{n}\right) \mathop{\longrightarrow}\limits_{n\to \infty} 0. $$

idée de démonstration Soit $X_n$ le nombre de sous-suites croissantes (différentes) de taille $\lfloor 3 \sqrt{n} \rfloor$ dans $\sigma_n$. Remarquons que si $I$ est une partie à $\lfloor 3 \sqrt{n} \rfloor$ éléments de $\{1, \ldots, n\}$, alors la probabilité que $\sigma_{\vert I}$ soit croissante est $$ \frac{1}{n !} \binom{n}{\lfloor 3 \sqrt{n} \rfloor} (n-\lfloor 3 \sqrt{n} \rfloor)! = \frac{1}{\lfloor 3 \sqrt{n} \rfloor!} $$ puisqu'il y a $\binom{n}{\lfloor 3 \sqrt{n} \rfloor}$ choix pour les termes de la sous-suite croissante (et leur ordre est imposé) et puisqu'il y a $(n- \lfloor 3 \sqrt{n} \rfloor)!$ choix pour le reste de la permutation. Ainsi, $$ \mathbb{E} [X_n] = \binom{n}{\lfloor 3 \sqrt{n} \rfloor} \frac{1}{\lfloor 3 \sqrt{n} \rfloor!}, $$ et l'espérance tend vers zéro grâce à Stirling.

Références¶

[Fer23] V. Féray. Processus stochastiques discrets – Méthode de moments et marche aléatoire (2023). Disponible sur ce lien.
[MU05] M. Mitzenmacher, E. Upfal. Probability and Computing (2005). Cambridge University Press.

In [ ]: