Problème de la plus longue sous suite croissante

Voici le sujet d'examen du cours de master modèles stochastiques du mercredi 16 mars 2011. Le contenu est tiré du livre de Steele Probability Theory and Combinatorial Optimization.

Convergence par sous additivité

Nous nous proposons d'établir que si ${{(u_n)}_{n\geq1}}$ est une suite de nombres réels sous additive, c'est-à-dire telle que ${u_{n+m}\leq u_n+u_m}$ pour tous ${n,m\geq1}$, alors

$$\lim_{n\rightarrow\infty}\frac{u_n}{n}=\inf_{n\geq1}\frac{u_n}{n}.$$

Il s'agit du Lemme de sous additivité de Fekete, qui date de 1923. Fekete était un mathématicien hongrois puis israélien (1886--1957), élève de Fejér, et mentor de Erdős, Turán, von Neumann, Pólya, et Dvoretsky.

1. Supposons pour l'instant que ${\gamma:=\inf_{n\geq1}\frac{u_n}{n}>-\infty}$. Montrer que pour tout ${\varepsilon>0}$ il existe ${k_\varepsilon}$ tel que ${u_{k_\varepsilon}\leq (\gamma+\varepsilon)k_\varepsilon}$, et que ${u_{mk}\leq mu_k}$ pour tous ${m,k\geq1}$
2. En déduire que pour tout ${n\geq1}$, en posant ${n=mk_\varepsilon+j}$ avec ${0\leq j<k_\varepsilon}$, on a

   $$u_n\leq m(\gamma+\varepsilon)k_\varepsilon+\max_{1\leq j<k_\varepsilon}u_j$$

3. En déduire le résultat attendu en montrant que

   $$\varlimsup_{n\rightarrow\infty}\frac{u_n}{n} \leq\gamma+\varepsilon \leq\varliminf_{n\rightarrow\infty}\frac{u_n}{n}+\varepsilon$$

4. Traiter le cas où ${\gamma=-\infty}$
5. Montrer que si une fonction continue ${f:\mathbb{R}_+\rightarrow\mathbb{R}}$ est sous additive, c'est-à-dire que ${f(s+t)\leq f(s)+f(t)}$ pour tous ${s,t\geq0}$, alors

   $$\lim_{t\rightarrow\infty}\frac{f(t)}{t}=\inf_{t>0}\frac{f(t)}{t}.$$

6. Traduire les résultats pour les suites et fonctions sur additives

Problème de la sous suite croissante

On se propose d'établir le résultat suivant qui remonte à Erdős et Szekeres vers 1935 : si ${a_1,\ldots,a_{nm+1}}$ est une suite de ${nm+1}$ nombres réels deux à deux distincts alors elle contient au moins une sous suite croissante de longueur ${n+1}$ ou une sous suite décroissante de longueur ${m+1}$.

Pour ce faire, on procède par la méthode des tiroirs, une idée proposée par Hammersley vers 1972 : on fabrique ${nm+1}$ jetons portant la valeur des ${a_1,\ldots,a_{nm+1}}$ qu'on range en piles de gauche à droite : ${a_1}$ débute la première pile. Si ${a_2>a_1}$ alors on le pose sur ${a_1}$ (la pile a alors une hauteur ${2}$) tandis que si ${a_2<a_1}$ alors on créé une nouvelle pile à droite de la première (de hauteur ${1}$). On procède ainsi avec chacun des ${a_3,\ldots,a_{nm+1}}$ en le posant au sommet de la première pile (de gauche à droite) qu'il majore ou en créant une nouvelle pile à droite des piles existantes s'il ne majore aucune pile existante.

1. Montrer que les jetons au sommet des piles forment une sous suite décroissante
2. Conclure en observant que chacune des piles donne une sous suite croissante

Étude d'une version stochastique

Soit ${X_1,\ldots,X_n}$ des v.a.r. i.i.d. de loi uniforme sur ${[0,1]}$. On s'intéresse à la longueur de la plus grande sous suite croissante :

$$I_n=I_n(X_1,\ldots,X_n) =\max\{k:X_{i_1}<\cdots<X_{i_k},1\leq i_1<\cdots<i_k\leq n\}.$$

On définit également la longueur de la plus grande sous suite décroissante :

$$I'_n=I'_n(X_1,\ldots,X_n) =\max\{k:X_{i_1}>\cdots>X_{i_k},1\leq i_1<\cdots<i_k\leq n\}.$$

Minoration de l'espérance

1. Montrer que les ${X_1,\ldots,X_n}$ sont deux à deux distincts avec probabilité ${1}$
2. Montrer que ${\max(I_n,I_n')\geq\sqrt{n}}$ (et donc ${I_n+I_n'\geq\sqrt{n}}$)
3. Monter que ${\mathbb{E}(I_n)=\mathbb{E}(I_n')}$ et en déduire que

   $$\mathbb{E}(I_n)\geq\frac{1}{2}\sqrt{n}$$

Majoration de l'espérance

1. Montrer que si ${1\leq k\leq n}$ et ${1\leq i_1<\cdots<i_k\leq n}$ alors la suite ${X_{i_1},\ldots,X_{i_k}}$ est croissante avec probabilité ${1/k!}$ (on pourra se ramener à une intégrale multiple)
2. En déduire que ${\mathbb{P}(I_n\geq k)\leq \binom{n}{k}/k!}$ pour tout ${1\leq k\leq n}$
3. En déduire que ${\mathbb{P}(I_n\geq 2e\sqrt{n})< e^{-2e\sqrt{n}}}$ (on rappelle que ${k!\geq (k/e)^k}$)
4. En déduire une constante ${C>0}$ telle que ${\mathbb{E}(I_n)\leq C\sqrt{n}}$ pour ${n}$ assez grand
   Nous allons préciser cette estimation en procédant différemment :
5. Montrer que ${\mathbb{E}(I_n)\leq k+n\mathbb{P}(I_n\geq k)}$ pour tout ${1\leq k\leq n}$
6. En déduire que pour tout ${c>e}$ il existe ${n_c}$ tel que pour tout ${n>n_c}$,

   $$\mathbb{E}(I_n)\leq c\sqrt{n}.$$

   (on pourra utiliser la formule de Stirling ${m!\sim\sqrt{2\pi m}\,m^me^{-m}}$)

Convergence de l'espérance par poissonisation

Nous avons établi que ${a_n:=\mathbb{E}(I_n)}$ est de l'ordre de ${\sqrt{n}}$ et il est naturel de se demander si ${n^{-1/2}a_n}$ converge quand ${n\rightarrow\infty}$. Ce comportement non linéaire semble empêcher l'usage direct de la sous additivité à la Fekete. Il est cependant possible de linéariser le problème par poissonisation puis dépoissonisation. L'heuristique est la suivante : si par exemple ${N}$ est une v.a.r. entière alors ${\mathbb{E}(a_N)\approx\mathbb{E}(\sqrt{N})\approx\sqrt{\mathbb{E}(N)}}$ qui est linéaire en ${t}$ lorsque ${N\sim\mathrm{Poi}(t^2)}$. D'autre part, si ${N\sim\mathrm{Poi}(n)}$ alors ${a_n\approx\mathbb{E}(a_N)}$.

Soit ${P}$ un processus ponctuel de Poisson sur ${\mathbb{R}^2}$ dont la mesure d'intensité est la mesure de Lebesgue. On identifie la mesure atomique aléatoire ${P}$ à ses atomes de sorte que ${P\cap B}$ désigne l'ensemble des atomes de ${P}$ contenus dans le borélien ${B}$ de ${\mathbb{R}^2}$. Le nombre d'atomes dans ${B}$ est ${P(B)=\mathrm{Card}(P\cap B)}$. Si ${B}$ a pour mesure de Lebesgue ${|B|}$ alors ${P(B)}$ suit la loi de Poisson ${\mathrm{Poi}(|B|)}$ de moyenne ${|B|}$. De plus, pour tout ${n\geq0}$ et conditionnellement à ${\{P(B)=n\}}$ les atomes de ${P}$ dans ${B}$ sont i.i.d. de loi uniforme sur ${B}$ (lorsque ${|B|>0}$).

On dit que la suite de ${n}$ points ${(x_1,y_1),\ldots,(x_n,y_n)}$ dans ${\mathbb{R}^2}$ est croissante lorsque ${x_1<\cdots<x_n}$ et ${y_1<\cdots<y_n}$. Pour tout réel ${t>0}$, soit ${I(t)}$ la longueur de la plus grande sous suite croissante dans l'ensemble de points aléatoire ${P\cap[0,t]^2}$.

1. Montrer que ${I_n\overset{d}{=}\mathcal{L}(I(t)\,|\,P([0,t]^2)=n)}$ pour tout ${n\geq1}$ et ${t>0}$
2. En déduire que ${\mathbb{E}(I(t))=e^{-t^2}\sum_{k=0}^\infty\frac{t^{2k}}{k!}a_k}$ où ${a_n:=\mathbb{E}(I_n)}$. En d'autre termes, si ${N}$ est une v.a.r. de loi de Poisson ${\mathrm{Poi}(t^2)}$ alors ${\mathbb{E}(I(t))=\mathbb{E}(a_N)}$
3. Si ${I(s,t)}$ désigne la longueur de la plus grande sous suite croissante de ${P\cap\,]s,t]^2}$, montrer que pour tous ${0<s<t}$

   $$I(0,s)+I(s,s+t)\leq I(0,s+t)$$

4. En déduire qu'en notant ${f(t):=\mathbb{E}(I(0,t))}$ on obtient, pour tous ${0<s<t}$,

   $$f(s)+f(t)\leq f(s+t)$$

5. En déduire que

   $$\lim_{t\rightarrow\infty}\frac{\mathbb{E}(I(t))}{t} =\sup_{t}\frac{\mathbb{E}(I(t))}{t} =:\gamma.$$

6. En déduire que

   $$e^{-\lambda}\sum_{k=0}^\infty a_k\frac{\lambda^k}{k!}\sim_{\lambda\rightarrow\infty}\gamma\sqrt{\lambda}.$$

7. Montrer que ${a_{n+m}\leq a_n+a_m}$ pour tout ${n,m\geq1}$
8. En déduire que ${|a_n-a_k|\leq C\sqrt{n-k}}$ pour tous ${1\leq k\leq n}$ et une constante ${C}$
9. En déduire que si ${N}$ est une v.a.r. de Poisson de moyenne ${\mathbb{E}(N)=n}$ alors

   $$|a_n-\mathbb{E}(a_{N})|\leq C\sum_{k=0}^\infty\sqrt{|n-k|}\,e^{-n}\frac{n^k}{k!}$$

10. Toujours avec ce ${N}$, en déduire via l'inégalité de Jensen et ${\mathrm{Var}(N)=n}$ que

    $$|a_n-\mathbb{E}(a_{N})|\leq Cn^{1/4}$$

11. En déduire que

    $$\mathbb{E}(I_n)=:a_n\sim_{n\rightarrow\infty}\gamma\sqrt{n}$$

12. Montrer que ${\gamma}$ est fini

Convergence presque sûre

1. Montrer que ${I_n}$ ne change que d'au plus ${1}$ si on change l'un des ${X_i}$
2. En déduire grâce à l'inégalité d'Azuma-Hoeffding que pour tous ${n\geq1}$ et ${t\geq0}$,

   $$\mathbb{P}(|I_n-\mathbb{E}(I_n)|\geq t)\leq 2e^{-\frac{t^2}{2n}}.$$

3. Quel résultat p.s. peut-on en déduire sur la suite ${{(I_n)}_{n\geq1}}$ quand ${n\rightarrow\infty}$?