{"id":1416,"date":"2011-03-16T15:31:39","date_gmt":"2011-03-16T13:31:39","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=1416"},"modified":"2014-03-24T20:09:55","modified_gmt":"2014-03-24T19:09:55","slug":"probleme-de-la-plus-longue-sous-suite-croissante","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2011\/03\/16\/probleme-de-la-plus-longue-sous-suite-croissante\/","title":{"rendered":"Probl\u00e8me de la plus longue sous suite croissante"},"content":{"rendered":"

Voici le sujet d'examen du cours de master mod\u00e8les stochastiques<\/a> du mercredi 16 mars 2011. Le contenu est tir\u00e9 du livre de Steele<\/a> Probability Theory and Combinatorial Optimization<\/a><\/em>.<\/p>\n

Convergence par sous additivit\u00e9<\/strong><\/p>\n

Nous nous proposons d'\u00e9tablir que si \\( {{(u_n)}_{n\\geq1}} \\) est une suite de nombres r\u00e9els sous additive<\/em>, c'est-\u00e0-dire telle que \\( {u_{n+m}\\leq u_n+u_m} \\) pour tous \\( {n,m\\geq1} \\), alors<\/p>\n

\\[ \\lim_{n\\rightarrow\\infty}\\frac{u_n}{n}=\\inf_{n\\geq1}\\frac{u_n}{n}. \\]<\/p>\n

Il s'agit du Lemme de sous additivit\u00e9 de Fekete<\/em>, qui date de 1923. Fekete<\/a> \u00e9tait un math\u00e9maticien hongrois puis isra\u00e9lien (1886--1957), \u00e9l\u00e8ve de Fej\u00e9r, et mentor de Erd\u0151s, Tur\u00e1n, von Neumann, P\u00f3lya, et Dvoretsky.<\/p>\n

    \n
  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} \\)<\/li>\n
  2. En d\u00e9duire que pour tout \\( {n\\geq1} \\), en posant \\( {n=mk_\\varepsilon+j} \\) avec \\( {0\\leq j<k_\\varepsilon} \\), on a\n

    \\[ u_n\\leq m(\\gamma+\\varepsilon)k_\\varepsilon+\\max_{1\\leq j<k_\\varepsilon}u_j \\]<\/p>\n<\/li>\n

  3. En d\u00e9duire le r\u00e9sultat attendu en montrant que\n

    \\[ \\varlimsup_{n\\rightarrow\\infty}\\frac{u_n}{n} \\leq\\gamma+\\varepsilon \\leq\\varliminf_{n\\rightarrow\\infty}\\frac{u_n}{n}+\\varepsilon \\]<\/p>\n<\/li>\n

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

    \\[ \\lim_{t\\rightarrow\\infty}\\frac{f(t)}{t}=\\inf_{t>0}\\frac{f(t)}{t}. \\]<\/p>\n<\/li>\n

  6. Traduire les r\u00e9sultats pour les suites et fonctions sur additives<\/li>\n<\/ol>\n

    Probl\u00e8me de la sous suite croissante<\/strong><\/p>\n

    On se propose d'\u00e9tablir le r\u00e9sultat suivant qui remonte \u00e0 Erd\u0151s et Szekeres vers 1935 : si \\( {a_1,\\ldots,a_{nm+1}} \\) est une suite de \\( {nm+1} \\) nombres r\u00e9els deux \u00e0 deux distincts alors elle contient au moins une sous suite croissante de longueur \\( {n+1} \\) ou une sous suite d\u00e9croissante de longueur \\( {m+1} \\).<\/p>\n

    Pour ce faire, on proc\u00e8de par la m\u00e9thode des tiroirs, une id\u00e9e propos\u00e9e par Hammersley<\/a> vers 1972 : on fabrique \\( {nm+1} \\) jetons portant la valeur des \\( {a_1,\\ldots,a_{nm+1}} \\) qu'on range en piles de gauche \u00e0 droite : \\( {a_1} \\) d\u00e9bute la premi\u00e8re 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\u00e9\u00e9 une nouvelle pile \u00e0 droite de la premi\u00e8re (de hauteur \\( {1} \\)). On proc\u00e8de ainsi avec chacun des \\( {a_3,\\ldots,a_{nm+1}} \\) en le posant au sommet de la premi\u00e8re pile (de gauche \u00e0 droite) qu'il majore ou en cr\u00e9ant une nouvelle pile \u00e0 droite des piles existantes s'il ne majore aucune pile existante.<\/p>\n

      \n
    1. Montrer que les jetons au sommet des piles forment une sous suite d\u00e9croissante<\/li>\n
    2. Conclure en observant que chacune des piles donne une sous suite croissante<\/li>\n<\/ol>\n

      \u00c9tude d'une version stochastique<\/strong><\/p>\n

      Soit \\( {X_1,\\ldots,X_n} \\) des v.a.r. i.i.d. de loi uniforme sur \\( {[0,1]} \\). On s'int\u00e9resse \u00e0 la longueur de la plus grande sous suite croissante :<\/p>\n

      \\[ 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\\}. \\]<\/p>\n

      On d\u00e9finit \u00e9galement la longueur de la plus grande sous suite d\u00e9croissante :<\/p>\n

      \\[ 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\\}. \\]<\/p>\n

      Minoration de l'esp\u00e9rance<\/strong><\/p>\n

        \n
      1. Montrer que les \\( {X_1,\\ldots,X_n} \\) sont deux \u00e0 deux distincts avec probabilit\u00e9 \\( {1} \\)<\/li>\n
      2. Montrer que \\( {\\max(I_n,I_n')\\geq\\sqrt{n}} \\) (et donc \\( {I_n+I_n'\\geq\\sqrt{n}} \\))<\/li>\n
      3. Monter que \\( {\\mathbb{E}(I_n)=\\mathbb{E}(I_n')} \\) et en d\u00e9duire que\n

        \\[ \\mathbb{E}(I_n)\\geq\\frac{1}{2}\\sqrt{n} \\]<\/p>\n<\/li>\n<\/ol>\n

        Majoration de l'esp\u00e9rance<\/strong><\/p>\n

          \n
        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\u00e9 \\( {1\/k!} \\) (on pourra se ramener \u00e0 une int\u00e9grale multiple)<\/li>\n
        2. En d\u00e9duire que \\( {\\mathbb{P}(I_n\\geq k)\\leq \\binom{n}{k}\/k!} \\) pour tout \\( {1\\leq k\\leq n} \\)<\/li>\n
        3. En d\u00e9duire que \\( {\\mathbb{P}(I_n\\geq 2e\\sqrt{n})< e^{-2e\\sqrt{n}}} \\) (on rappelle que \\( {k!\\geq (k\/e)^k} \\))<\/li>\n
        4. En d\u00e9duire une constante \\( {C>0} \\) telle que \\( {\\mathbb{E}(I_n)\\leq C\\sqrt{n}} \\) pour \\( {n} \\) assez grand
          \nNous allons pr\u00e9ciser cette estimation en proc\u00e9dant diff\u00e9remment :<\/li>\n
        5. Montrer que \\( {\\mathbb{E}(I_n)\\leq k+n\\mathbb{P}(I_n\\geq k)} \\) pour tout \\( {1\\leq k\\leq n} \\)<\/li>\n
        6. En d\u00e9duire que pour tout \\( {c>e} \\) il existe \\( {n_c} \\) tel que pour tout \\( {n>n_c} \\),\n

          \\[ \\mathbb{E}(I_n)\\leq c\\sqrt{n}. \\]<\/p>\n

          (on pourra utiliser la formule de Stirling \\( {m!\\sim\\sqrt{2\\pi m}\\,m^me^{-m}} \\))<\/li>\n<\/ol>\n

          Convergence de l'esp\u00e9rance par poissonisation<\/strong><\/p>\n

          Nous avons \u00e9tabli 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\u00e9aire semble emp\u00eacher l'usage direct de la sous additivit\u00e9 \u00e0 la Fekete. Il est cependant possible de lin\u00e9ariser le probl\u00e8me par poissonisation puis d\u00e9poissonisation. L'heuristique est la suivante : si par exemple \\( {N} \\) est une v.a.r. enti\u00e8re alors \\( {\\mathbb{E}(a_N)\\approx\\mathbb{E}(\\sqrt{N})\\approx\\sqrt{\\mathbb{E}(N)}} \\) qui est lin\u00e9aire 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)} \\).<\/p>\n

          Soit \\( {P} \\) un processus ponctuel de Poisson sur \\( {\\mathbb{R}^2} \\) dont la mesure d'intensit\u00e9 est la mesure de Lebesgue. On identifie la mesure atomique al\u00e9atoire \\( {P} \\) \u00e0 ses atomes de sorte que \\( {P\\cap B} \\) d\u00e9signe l'ensemble des atomes de \\( {P} \\) contenus dans le bor\u00e9lien \\( {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 \u00e0 \\( {\\{P(B)=n\\}} \\) les atomes de \\( {P} \\) dans \\( {B} \\) sont i.i.d. de loi uniforme sur \\( {B} \\) (lorsque \\( {|B|>0} \\)).<\/p>\n

          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\u00e9el \\( {t>0} \\), soit \\( {I(t)} \\) la longueur de la plus grande sous suite croissante dans l'ensemble de points al\u00e9atoire \\( {P\\cap[0,t]^2} \\).<\/p>\n

            \n
          1. Montrer que \\( {I_n\\overset{d}{=}\\mathcal{L}(I(t)\\,|\\,P([0,t]^2)=n)} \\) pour tout \\( {n\\geq1} \\) et \\( {t>0} \\)<\/li>\n
          2. En d\u00e9duire que \\( {\\mathbb{E}(I(t))=e^{-t^2}\\sum_{k=0}^\\infty\\frac{t^{2k}}{k!}a_k} \\) o\u00f9 \\( {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)} \\)<\/li>\n
          3. Si \\( {I(s,t)} \\) d\u00e9signe la longueur de la plus grande sous suite croissante de \\( {P\\cap\\,]s,t]^2} \\), montrer que pour tous \\( {0<s<t} \\)\n

            \\[ I(0,s)+I(s,s+t)\\leq I(0,s+t) \\]<\/p>\n<\/li>\n

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

            \\[ f(s)+f(t)\\leq f(s+t) \\]<\/p>\n<\/li>\n

          5. En d\u00e9duire que\n

            \\[ \\lim_{t\\rightarrow\\infty}\\frac{\\mathbb{E}(I(t))}{t} =\\sup_{t}\\frac{\\mathbb{E}(I(t))}{t} =:\\gamma. \\]<\/p>\n<\/li>\n

          6. En d\u00e9duire que\n

            \\[ e^{-\\lambda}\\sum_{k=0}^\\infty a_k\\frac{\\lambda^k}{k!}\\sim_{\\lambda\\rightarrow\\infty}\\gamma\\sqrt{\\lambda}. \\]<\/p>\n<\/li>\n

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

            \\[ |a_n-\\mathbb{E}(a_{N})|\\leq C\\sum_{k=0}^\\infty\\sqrt{|n-k|}\\,e^{-n}\\frac{n^k}{k!} \\]<\/p>\n<\/li>\n

          10. Toujours avec ce \\( {N} \\), en d\u00e9duire via l'in\u00e9galit\u00e9 de Jensen et \\( {\\mathrm{Var}(N)=n} \\) que\n

            \\[ |a_n-\\mathbb{E}(a_{N})|\\leq Cn^{1\/4} \\]<\/p>\n<\/li>\n

          11. En d\u00e9duire que\n

            \\[ \\mathbb{E}(I_n)=:a_n\\sim_{n\\rightarrow\\infty}\\gamma\\sqrt{n} \\]<\/p>\n<\/li>\n

          12. Montrer que \\( {\\gamma} \\) est fini<\/li>\n<\/ol>\n

            Convergence presque s\u00fbre<\/strong><\/p>\n

              \n
            1. Montrer que \\( {I_n} \\) ne change que d'au plus \\( {1} \\) si on change l'un des \\( {X_i} \\)<\/li>\n
            2. En d\u00e9duire gr\u00e2ce \u00e0 l'in\u00e9galit\u00e9 d'Azuma-Hoeffding que pour tous \\( {n\\geq1} \\) et \\( {t\\geq0} \\),\n

              \\[ \\mathbb{P}(|I_n-\\mathbb{E}(I_n)|\\geq t)\\leq 2e^{-\\frac{t^2}{2n}}. \\]<\/p>\n<\/li>\n

            3. Quel r\u00e9sultat p.s. peut-on en d\u00e9duire sur la suite \\( {{(I_n)}_{n\\geq1}} \\) quand \\( {n\\rightarrow\\infty} \\)?<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

              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…<\/p>\n

              Continue readingProbl\u00e8me de la plus longue sous suite croissante<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":125},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1416"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=1416"}],"version-history":[{"count":13,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1416\/revisions"}],"predecessor-version":[{"id":6962,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1416\/revisions\/6962"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=1416"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=1416"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=1416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}