Mines MP1 2018

Un corrigé

1 Préliminaires
1. On a
n
X
E(X) = kP(X = k)
k=1
m−1
X n
X
= kP(X = k) + kP(X = k)
k=1 k=m
m−1
X n
X
≤ (m − 1) P(X = k) + n P(X = k)
k=1 k=m

La première somme est ≤ 1 (la somme de TOUS les P(X = k) vaut 1, celle-ci est inférieure
puisqu’elle a moins de termes et que les termes enlevés sont ≥ 0). La seconde somme vaut
P(X ≥ m).

Si X(Ω) ⊂ {1, . . . , n} et m ∈ {1, . . . , n}, E(X) ≤ m − 1 + nP(X ≥ m)

2. La fonction x 7→ ln(x) étant croissante sur R+∗ on a

∀k ≥ 2, ∀x ∈ [k − 1, k], ln(x) ≤ ln(k)
En intégrant ces inégalités, on a donc
Z k
∀k ≥ 2, ln(x) dx ≤ ln(k)
k−1

En sommant ces inégalités (et comme ln(1) = 0)

Z n n
X
∀n ≥ 2, ln(x) dx ≤ ln(k)
1 k=1

Comme x 7→ x ln(x) − x est une primitive de ln, on a ainsi

n
X
∀n ≥ 2, [x ln(x) − x]n1 ≤ ln(k)
k=1

On en déduit (on vérifie que c’est encore vrai si n = 1) que

n
X
n ln(n) − n + 1 ≤ ln(k)
k=1

Par propriété de morphisme du logarithme, ceci s’écrit

ln(nn ) − n + 1 ≤ ln(n!)
Par croissance de l’exponentielle, on a donc
nn e−n e ≤ n!
Et enfin, comme 1 ≤ e, on conclut que
 n n
≤ n!
e

1
2 Le lemme de sous-additivité de Fekete
3. Comme u est bornée, il existe M tel que ∀n ∈ N∗ , |un | ≤ M . Ainsi, Un est une partie non vide
et bornée (incluse dans [−M, M ]). Elle admet des bornes supérieure et inférieure et u et u sont
bien définies.
Comme Un+1 ⊂ Un , inf(Un ) ≤ inf(Un+1 ) ≤ sup(Un+1 ) ≤ sup(Un ). Ainsi u croı̂t et u décroı̂t.
Ces suites étant bornées (incluses dans [−M, M ]) elles convergent par théorème de limite mo-
notone.
u et u sont monotones et convergentes
4. On a u qui est décroissante et plus grande que u (un = sup(Un ) ≥ un car un ∈ Un ).
Soit v une suite ayant ces deux propriétés. On a alors
∀n ∈ N∗ , ∀k ≥ n, uk ≤ vk ≤ vn
Par passage au sup (sur k), on a donc
∀n ∈ N∗ , un ≤ vn
et ainsi u  v. On a alors montré que
u est la plus petite suite (au sens de ) qui est décroissante et plus grande que u
On a u qui est croissante et plus petite que u (un = inf(Un ) ≤ un car un ∈ Un ).
Soit v une suite ayant ces deux propriétés. On a alors
∀n ∈ N∗ , ∀k ≥ n, vn ≤ vk ≤ uk
Par passage à la borne inférieure (sur k), on a donc
∀n ∈ N∗ , vn ≤ un
et ainsi v  u. On a alors montré que
u est la plus grande suite (au sens de ) qui est croissante et plus petite que u
5. Si u  v alors
∀n ∈ N∗ , ∀k ≥ n, uk ≤ vk ≤ v n
et en passant à la borne supérieure (en k)
∀n ∈ N∗ , un ≤ v n
Par théorème de comparaison, on a donc
lim u ≤ lim v
6. Avec les inégalités de la question 3, les suites u et u sont adjacentes ssi leur différence tend vers
0, c’est-à-dire si elles ont même limite.
Remarquons que
∀n ∈ N∗ , un ≤ un ≤ un
Si les suites u et u ont même limite, alors par théorème d’encadrement, la suite u converge et a
même limite que u et u.
Réciproquement, supposons que u converge et notons ` sa limite. Soit ε > 0 ; il existe un rang p
tel que
∀k ≥ p, ` − ε ≤ uk ≤ ` + ε
En passant à la borne supérieure ou inférieure pour k ≥ n (n donné plus grand que p) on a donc
∀n ≥ p, ` − ε ≤ un ≤ un ≤ ` + ε
Ainsi, u et u sont convergentes de limite `.

2
 u et u sont adjacentes si et seulement si u converge

Dans ce cas, avec ce qui précède

lim u = lim u = lim u

7. On montre par récurrence sur k que la propriété

∀n ∈ N∗ , ukn ≤ kun

est vraie pour tout k ∈ N∗ .

- Initialisation : c’est immédiatement vrai si k = 1 (on a même égalité).
- Hérédité : supposons le résultat vrai à un rang k ≥ 1. Avec la sous-additivité,

u(k+1)n = ukn+n = ukn + un

et avec le résultat au rang k, u(k+1)n ≤ kun + un = (k + 1)un ce qui prouve le résultat au

rang k + 1.
Ici, on a m = qn + r avec q ≥ 2 (car m ≥ 2n) et r ∈ {0, . . . , n − 1}. On écrit alors m =
(q − 1)n + r + n et comme q − 1 ≥ 1, on va pouvoir utiliser le premier résultat. En effet, avec la
sous-additivité
um ≤ u(q−1)n + un+r ≤ (q − 1)un + un+r
On en déduit que
um q−1 un+r
≤ un +
m m m
n(q − 1) un max{un , . . . , u2n−1 }
≤ +
m n m
On remarque alors que m − n − r = (q − 1)n pour conclure que

um m − n − r un max{un , un+1 , . . . , u2n−1 }

≤ · +
m m n m

8. La question précédente avec n = 1 donne (touts les uk sont positifs et on peut multiplier les
inégalités)
um m−1−r u1
∀m ≥ 2, ≤ u1 + ≤ 2u1
m m m
En particulier, la suite (un /n) est majorée. Mais comme u est positive, cette suite (un /n) est
aussi minorée (par 0). C’est donc une suite bornée .
Soit n ∈ N∗ . Notons vm le terme du membre de droite dans la question précédente. On a
um
∀m ≥ 2n, ≤ vm
m
Avec la question 5 (il suffit d’en reprendre la preuve pour voir qu’il n’est pas gênant que l’on ait
une suite plus grande que l’autre seulement à partir d’un certain rang) on en déduit que
um
lim ≤ lim vm
m→+∞ m m→+∞

,...,u2n−1 }
n étant fixé, le terme max{un ,un+1
m est de limite nulle quand m → +∞.
n+r
Comme |n − r| ≤ 2n, on a m → 0 quand m → +∞.
Ainsi, (vm ) est convergente de limite un /n. Avec la question 6, lim vm = un /n.
m→+∞
On a donc finalement

3
 um un
∀n ∈ N∗ , lim ≤
m→+∞ m n

9. Posons wn = un /n et ` = lim wn . La question précédente donne

n→+∞

∀n ∈ N∗ , ` ≤ wn

On en déduit comme en question 5 que

` ≤ lim wn
n→+∞

On a donc
lim wn ≤ lim wn
n→+∞ n→+∞

Comme on sait que l’inégalité inverse est toujours vraie (voir question 3), on a une égalité. Avec
la question 6,

La suite unn n∈N∗ converge

3 Une application probabiliste

10. Quand on fait la moyenne de quantités < x, on obtient un nombre < x. Ainsi
n
\
(Xk < x) ⊂ (Yn < x)
k=1

En passant aux probabilités et par indépendance des Xk ,

n
Y
P(Xk < x) ≤ P(Yn < x)
k=1

Si P(X1 < x) = 1 alors comme les Xk ont toutes même loi, P(Xk < x) = 1 pour tout k et donc
P(Yn < x) ≥ 1. Et comme P est à valeurs dans [0, 1], cette inégalité est une égalité.

Si P(X1 < x) = 1, alors pour tout n ∈ N∗ , P(Yn < x) = 1

Quand on fait la moyenne de quantités ≥ x, on obtient un nombre ≥ x. Ainsi

n
\
(Xk ≥ x) ⊂ (Yn ≥ x)
k=1

En passant aux probabilités et par indépendance des Xk ,

n
Y
P(Xk ≥ x) ≤ P(Yn ≥ x)
k=1

Si P(X1 ≥ x) > 0 alors comme les Xk ont toutes même loi, P(Xk ≥ x) > 0 pour tout k et donc
P(Yn ≥ x) > 0.

Si P(X1 ≥ x) > 0 alors pour tout n ∈ N∗ , P(Yn ≥ x) > 0.

11. Soit ω ∈ Ω tel que Ym (ω) ≥ x et m+n ≥ nx. La première hypothèse donne m
P P
k=m+1 Xk (ω)P k=1 Xk (ω) ≥
m+n
mx. En sommant avec la seconde, on a alors k=1 Xk (ω) ≥ (n + m)x et donc Yn+m (ω) ≥ x.
On a donc montré que

4
 m+n
( )!
1 X
{Ym ≥ x} ∩ Xk ≥ x ⊂ {Ym+n ≥ x)
n
k=m+1

En passant aux probabilités, et comme Ym et Xm+1 + · · · + Xm+n sont indépendantes (lemme

des coalitions)
m+n
!
1 X
P(Ym ≥ x)P Xk ≥ x ≤ P(Yn+m ≥ x)
n
k=m+1

Ecrivons que
m+n n
!
1 X [ \
Xk ≥ x = (Xm+k = xk )
n
k=m+1 x1 ,...,xn ∈X1 (Ω) k=1
x1 +···+xn ≥nx

La réunion est disjointe et les Xi sont mutuellement indépendants. Ainsi

m+n n
!
1 X X Y
P Xk ≥ x = P(Xm+k = xk )
n
k=m+1 x ,...,x ∈X (Ω)1 n 1 k=1
x1 +···+xn ≥nx

Comme les Xi ont tous même on a aussi

m+n n
!
1 X X Y
P Xk ≥ x = P(Xk = xk )
n
k=m+1 x1 ,...,xn ∈X1 (Ω) k=1
x1 +···+xn ≥nx

et en remontant le calcul
m+n n
! !
1 X 1X
P Xk ≥ x =P Xk ≥ x = P(Yn ≥ x)
n n
k=m+1 k=1

On en conclut que

P(Yn+m ≥ x) ≥ P(Ym ≥ x)P(Yn ≥ x)

12. On aimerait passer au logarithme dans la relation ci-dessus. Il faut pour cela que les quantités
soient > 0.
Si P(X1 ≥ x) > 0, la question 10 donne ce caractère strictement positif. Le passage à l’inverse
(opération décroissante sur R+∗ ) puis au logarithme donne le caractère sous-additif de la suite
de terme général un = ln(1/P(Yn ≥ x)). Comme cette suite est positive (une probabilité est
plus petite que 1), le lemme de Fekete donne la convergence de (un /n). En notant ` sa limite, la
1
composition par exp donne (P(Yn ≥ x)) n → e−` .
Si P(X1 ≥ x) = 0 alors P(X1 < x) = 1. La question 10 donne ∀n, P(Yn < x) = 1 et donc
P(Yn ≥ x) = 0. La suite considérée est cette fois nulle (on prolonge naturellement t 7→ t1/n en 0
par la valeur 0, ce que l’énoncé semble supposer) et converge.
 1

(P(Yn ≥ x)) n converge
n∈N∗

4 Le théorème de Erdös-Szekeres
13. L’énoncé donne un processus algorithmique. On demande en fait de justifier une sorte d’invariant
de boucle qui s’énonce de la façon suivante : “au début de l’étape numéro k (en numérotant les
étapes à partir de 2 puisque l’élément a1 est ajouté dans une phase d’initialisation) et en notant
s le nombre de piles à cet instant, il existe une liste b comme dans l’énoncé”.

5
 - Initialisation : au début du processus, on a une seule pile (s = 1). La suite (a1 ) convient.
- Hérédité : supposons le résultat vrai jusqu’au rang k.
- Si le nombre de pile n’est pas modifié par l’étape k et l’élément ak+1 est ajouté à une
autre pile que la dernière. La suite (b1 , . . . , bs ) de l’étape k convient encore.
- Si le nombre de pile n’est pas modifié par l’étape k et l’élément ak+1 est ajouté à la
dernière pile. On a alors ak+1 > bs mais aussi ak+1 qui est strictement plus petit que le
sommets de la pile s − 1 et ce sommet est un ai avec i ≤ k. Par hypothèse de récurrence
au rang i, on construit une une suite (b1 , . . . , bs−1 = ai ). La suite (b1 , . . . , bs−1 , ak+1 )
convient au rang k + 1.
- Sinon, ak+1 est placé sur une nouvelle pile de numéro s + 1. Comme ci-dessus, le
sommet ai de la pile s est strictement plus grand que ak+1 . L’hypothèse au rang i
donne (b1 , . . . , bs = ai ) et la suite (b1 , . . . , bs , ak+1 ) convient au rang k + 1.
14. Si le nombre de piles à l’issue du processus est plus grand que q + 1, on a alors une extraite
décroissante de taille q + 1 avec la question précédente.
Sinon, il y a au maximum q pile et l’une d’entre elle doit avoir p + 1 éléments (puisque l’on
ajoute pq + 1 éléments en tout). La suite des éléments de cette pile est extraite de la suite de
départ et croı̂t.

a admet au moins une extraite croissante de longueur p + 1

ou une extraite décroissante de longueur q + 1

5 Comportement asymptotique d’une suite aléatoire

15. L’événement (A1 = 1) ∩ · · · ∩ (An = 1) est vide et donc de probabilité nulle.
Les événement (Ai = 1) ne sont pas de probabilité nulle (il existe au moins une permutation σ
telle que σ(i) = 1).
La probabilité de l’intersection est différente du produit des probabilités et ainsi

Les variables aléatoires A1 , A2 , . . . , An ne sont pas mutuellement indépendantes

16. Si on choisit k = 2 et s1 = s2 = 1 alors As1 = As2 et la liste (As1 , As2 ) est toujours croissante.
As est ainsi de probabilité 1 6= 1/2. Il faut sans doute modifier l’énoncé et supposer que

s = (s1 , . . . , sk ) est strictement croissante

On cherche les permutations σ telles que σ(s1 ) ≤ σ(s2 ) ≤ · · · ≤ σ(sk ) (ce qui revient à
σ(s1 ) < · · · < σ(sk ) puisque s est une bijection et les si deux à deux distincts). Choisir une
telle permutation revient à choisir k éléments de {1, . . . , n} qui seront les σ(si ) (l’ordre est im-
posé par ce que
l’on veut) et à répartir les n − k autres images sur les n − k éléments différents
des si . Il y a nk choix de parties et (n − k)! façon de répartir. Comme Sn est de cardinal n et
que les permutations sont équiprobables,
n


s k (n − k)! 1
P(A ) = =
n! k!

17. Si σ ∈ Sn , on note σ 0 : k 7→ n + 1 − k. σ 7→ σ 0 est une bijection de Sn dans lui même.

Notons alors B 0 la variable aléatoire telle ∀ω ∈ Ω, si B(ω) = σ alors B 0 (ω) = σ 0 .
B 0 suit alors aussi une loi uniforme et on peut lui associer A0 et Cn0 , Dn0 .
Une extraite de σ ∈ Sn (considéré comme liste de n éléments) est croissante ssi la même extraite
de σ 0 est décroissante.
Ainsi, Cn et Dn0 ont même loi. Et comme Dn0 et Dn ont même loi,

6
 Cn et Dn ont le même loi

D’après la question 14, Cn + Dn ne peut pas être trop petit. Notons p le plus grand entier tel
que n ≥ 1 + p2 . Notons A0 la liste A tronquée aux 1 + p2 premiers éléments et Cn0 (resp. Dn0 )
la longueur de la plus longue liste croissante (resp. décroissante) extraite de A0 . La question 14
indique que Cn0 + Dn0 ≥ p + 1. Comme Cn ≥ Cn0 et Dn ≥ Dn0 , on a donc Cn + Dn ≥ p + 1. Ainsi,

E(Cn + Dn ) ≥ p + 1

Par linéarité de l’espérance, et comme Cn et Dn ont même loi,

2E(Cn ) ≥ p + 1

Je choisis de noter dxe le plus petit entier plus grand que x (partie entière “supérieure”).
√ √ √ √ √
Soit q = d ne − 1. On a q 2 + 1 = d ne2 − 2d ne = d ne(d ne − 2).
√ √ √ √
Remarquons que d ne ≤ n + 1 et donc d ne − 2 ≤ n − 1.
√ √ √ √
Ainsi (on multiplie la seconde inégalité par un terme positif) d ne(d ne − 2) ≤ d ne( n − 1).
√ √ √
Mais aussi (on multiplie la première inégalité par un terme positif) d ne( n − 1) ≤ ( n +
√
1)( n − 1) = n − 1.
Tout ceci se combine pour donner q 2 + 1 ≤ n − 1 ≤ n et donc q ≤ p. On conclut que
√ √
2E(Cn ) ≥ q + 1 = d ne ≥ n
√
n
E(Cn ) ≥
2
18. Si Cn ≥ k, il y a une extraite croissante de taille k et ainsi
[
(Cn ≥ k) ⊂ As
s∈Ek

où Ek est l’ensemble des listes croissantes de k éléments de {1, . . . , n}. Ainsi,
X 1
P(Cn ≥ k) ≤ P(As ) = Card(Ek )
k!
s∈Ek

Une liste croissante de
k éléments de {1, . . . , n} est caractérisée par une partie de k éléments de
{1, . . . , n} et il y a nk telles parties. Ainsi

n


k
P(Cn ≥ k) ≤
k!
√ √
19. On a αe n ≥ e ≥ 2 et donc (avec les notation choisies en question 18), l’entier k = dαe ne est
plus grand que 2 et vérifie
√
k − 1 < αe n ≤ k

Pour x réel, dxe existe puisque l’ensemble des entiers plus grand que x est non vide, minoré par
x et admet donc un minimum).
√
Comme Cn est à valeurs entières, on a (Cn ≥ αe n) ⊂ (Cn ≥ k) et donc (k ≥ 1 et on peut
utiliser la question 18)
n
1 2


√
 
k n!
P(Cn ≥ αe n) ≤ P(Cn ≥ k) ≤ =
k! (n − k)! (k)!

7
 Avec la question 2,
1  e 2k
≤
(k!)2 k
Par ailleurs,
n! √ 2k
= n(n − 1) ≤ (n − k + 1) ≤ nk = n
(n − k)!
Ainsi  √ 2k
√ e n
P(Cn ≥ αe n) ≤
k
√
Comme e k n ≤ 1, plus on élève ce nombre à une grande puissance, plus il devient petit. Comme
√
2k ≥ 2αe n, on a donc
 √ 2αe√n
√ e n
P(Cn ≥ αe n) ≤
k
√
1 e n
Comme α ≥ k , on conclut finalement que
 2αe√n
√ 1
P(Cn ≥ αe n) ≤
α

20. En utilisant la question 1 avec m = k, on obtient

E(Cn ) ≤ k − 1 + nP(Cn ≥ k)
√
Comme indiqué plus haut, (Cn ≥ k) = (Cn ≥ αe n) (car Cn est à valeurs entières). Avec la
√
question précédente (et comme k − 1 ≤ αe n),
 2αe√n
√ 1
E(Cn ) ≤ αe n + n
α
On choisit α = 1 + n−1/4 (possible car c’est > 1) :
2(1+n−1/4 )e√n
√

E(Cn ) 1
√ ≤ (1 + n−1/4 )e + εn avec εn = n
n 1 + n−1/4
Remarquons que
ln(1 + n−1/4 ) ∼ n−1/4
et donc √
− ln(1 + n−1/4 )2(1 + n−1/4 )e n ∼ −2en1/4
puis
1 √
εn = ln(vn ) avec vn = ln(n) − ln(1 + n−1/4 )2(1 + n−1/4 )e n ∼ −2en1/4 → −∞
2
et donc εn → 0.
E(Cn )
√ ≤ (1 + n−1/4 )e + εn avec εn → 0
n
 
E(Cn )
Ci-dessus, le majorant est convergent (de limite e) et donc borné. La suite √
n
est donc
)
majorée et on a existence de lim E(C
√n
n
avec de plus (avec la question 5)
n→+∞

E(Cn )
lim √ ≤e
n→+∞ n