J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Mines Mathématiques 1 MP 2018

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

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Probabilités finies, discrètes et dénombrementFonctions (limites, continuité, dérivabilité, intégration)
Logo mines
🔗 Explorer
Banque
Mines
Année
2018
Filière
MP
Matière
Maths
Mines MPMines 2018MP MathsMaths 2018
2025_08_29_9f32be7790e34e98fd66g

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International), Concours Mines-Télécom, Concours Commun TPE/EIVP.

CONCOURS 2018

PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

MATHÉMATIQUES I - MP

L'énoncé de cette épreuve comporte 5 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Le but de ce problème est d'étudier quelques applications probabilistes du lemme de sous-additivité de Fekete et du théorème de Erdös-Szekeres.
Dans tout le problème, ( ) désigne un espace probabilisé. On note la probabilité d'un événement et on note l'espérance (si elle existe) d'une variable aléatoire réelle discrète définie sur ( ).

A. Préliminaires

Les deux questions de cette partie sont indépendantes.
Soit un entier naturel non nul.
  1. Montrer que pour toute variable aléatoire réelle à valeurs dans et pour tout ,
  1. À l'aide d'une comparaison entre une somme et une intégrale, montrer que
En déduire l'inégalité

B. Le lemme de sous-additivité de Fekete

Soit une suite réelle bornée. Pour tout , on note . On définit les suites et par les formules
  1. Justifier que et sont bien définies. Montrer qu'elles sont monotones puis qu'elles convergent.
Pour toutes suites réelles et , on dit que est plus petite que , et on note , si pour tout , on a . De façon équivalente, on dit aussi que est plus grande que .
4) Montrer que est la plus petite suite (au sens de ) qui est décroissante et plus grande que . Montrer de même que est la plus grande suite (au sens de qui est croissante et plus petite que .
Dans toute la suite du problème, on appelle limite inférieure lim et limite supérieure les limites suivantes:
  1. Si est une autre suite réelle bornée plus grande que , comparer les limites de et de .
  2. Montrer que et sont adjacentes si et seulement si converge. En ce cas, que peut-on dire des limites des trois suites et ?
    On dit qu'une suite réelle est sous-additive si pour tous dans , on a .
    Dans le reste de cette partie on ne suppose plus que la suite u est bornée, mais on suppose que u est positive et sous-additive.
  3. Soit et deux entiers naturels non nuls tels que . On note le quotient et le reste de la division euclidienne de par . Montrer que
et en déduire l'inégalité
  1. En déduire que la suite est bornée, puis que pour tout ,
  1. En conclure que la suite converge.

C. Une application probabiliste

Soit un nombre réel et une suite de variables aléatoires réelles mutuellement indépendantes et de même loi. Pour tout on note la variable aléatoire réelle définie par
  1. Montrer que si , alors pour tout et que si , alors pour tout .
  2. Soit et deux entiers naturels non nuls. Montrer l'inclusion d'événements suivante :
et en déduire l'inégalité
  1. Démontrer la convergence de la suite

D. Le théorème de Erdös-Szekeres

Si est un entier naturel non nul, on note une liste de nombres réels de longueur ; cette liste est croissante si , décroissante si . Une liste de longueur est extraite de s'il existe indices strictement croissants dans tels que .
Soit et deux entiers naturels non nuls et une liste de longueur de nombres réels deux-à-deux distincts qui représentent les valeurs de jetons numérotés .
On range successivement les jetons en piles de gauche à droite par le procédé suivant:
  • le jeton de valeur débute la première pile;
  • si , alors on pose le jeton de valeur sur le jeton ; sinon on crée une nouvelle pile avec ce jeton , située à droite de la première pile;
  • lors des étapes suivantes, disposant du jeton de valeur , on le dépose sur la première pile en partant de la gauche telle que est supérieur à la valeur du jeton au sommet de la pile, si une telle pile existe; sinon on crée une nouvelle pile avec ce jeton, située à droite des précédentes.
En suivant ce procédé avec tous les jetons, on obtient plusieurs piles de jetons, chaque pile ayant des valeurs rangées dans l'ordre croissant du bas vers le haut.
Par exemple, avec la liste
dans cet ordre, on obtient de gauche à droite les trois piles suivantes :
10
9 8
7 6
4 3
1 2 5
  1. À l'aide d'un raisonnement par récurrence sur le nombre de piles, montrer qu'à l'issue du processus, pour tout jeton de valeur de la dernière pile, il existe une liste de réels extraite de la liste vérifiant:
  • est décroissante et de longueur ;
  • pour tout le jeton de valeur est dans la -ème pile en partant de la gauche;
  • .
Par exemple, avec la liste on a une liste extraite .
14) En déduire que la liste admet au moins une liste extraite croissante de longueur ou une liste extraite décroissante de longueur .

E. Comportement asymptotique d'une suite aléatoire

Soit un entier naturel supérieur ou égal à 2 . On note l'ensemble des permutations de . Chaque élément est noté par la liste de ses images ( ).
Soit une variable aléatoire à valeurs dans de loi uniforme, c'est-à-dire que pour tout , on a . On définit la variable aléatoire à valeurs dans en posant, pour tout ,
On note également, pour tout . Enfin, on considère les variables aléatoires réelles et définies par:
  • est la longueur de la plus longue liste croissante extraite de ;
  • est la longueur de la plus longue liste décroissante extraite de .
  1. Les variables aléatoires réelles sont-elles mutuellement indépendantes?
  2. Soit et une liste croissante de longueur d'éléments de . On note l'événement: «la liste ( ) est croissante ». Montrer que .
  3. Démontrer que et ont la même loi. Démontrer alors, à l'aide du résultat de la question 14 , que :
  1. Démontrer que pour tout ,
  1. Soit un entier naturel non nul et un réel strictement supérieur à 1 . Justifier qu'il existe un entier naturel non nul tel que . À l'aide du résultat de la question 2, déduire de la question précédente que
  1. En déduire qu'il existe une suite tendant vers 0 telle que, pour tout ,
En conclure que existe et que .

Fin du problème

Mines Mathématiques 1 MP 2018 - Version Web LaTeX | WikiPrépa | WikiPrépa