Mines Maths 2 MP 2020

Thème de l'épreuve Nombre de sites visités par une marche aléatoire
Principaux outils utilisés probabilités, série entière, série numérique, combinatoire, intégration
Mots clefs marche aléatoire, théorème d'Erdös-Dvoretzky, Stirling, Bernoulli

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


A2020 --- MATH II MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS. MINES PARISTECH.
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH.

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

CONCOURS 2020
DEUXIÈME ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : 4 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 II - 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'énontcé, il le
signale sur sa copie et poursuit sa composition en expliquant les raisons des 
initiatives qu'il est
amené à prendre.

Les sujets sont la propriété du GIP CCMEP. Ils sont publiés les termes de la 
licence
Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de 
Modification 3.0 France.
Tout autre usage est soumis à une autorisation préalable du Concours commun 
Mines Ponts.

Nombre de sites visités par une marche aléatoire

Dans tout le texte, d est un élément de N°. On note 0, le d-uplet dont toutes 
les
coordonnées valent 0, c'est-à-dire le vecteur nul de R.

On considère une variable aléatoire X à valeurs dans Z4, (Xz)genw+ une suite
de variables aléatoires mutuellement indépendantes suivant chacune la loi de X 
et
définies sur un même espace probabilisé. La suite de variables aléatoires (S, 
),en est
définie par So = Og et

Vn EUR N°, Sn = D Xk.
k=1

La suite (S, }hen est une marche aléatoire de pas X, à valeurs dans Z.

On note R la variable aléatoire à valeurs dans N*U {+} définie par

n=| min{n E N*, Sy --=0Og} si {n E N*, Sy = Où} £V,

OO sinon.

Autrement dit, À est égal à +oo si la marche aléatoire (S;),en ne revient 
jamais en
04, au premier instant auquel cette marche aléatoire revient en 0, sinon.

Pour n dans N, soit N,, le cardinal du sous-ensemble

{5}, kEUR {0,...,n}}

de Z4. Le nombre N, est donc le nombre de points de Z% visités par la marche
aléatoire (Sh)neN après n pas.

Le but du problème est d'étudier asymptotiquement l'espérance E(N,) de la
variable aléatoire N,.

La partie D est indépendante des parties précédentes.

A. Préliminaires

Les cinq questions de cette partie sont indépendantes et utilisées dans les 
parties
Cet E.

1. Soit n EUR N. En utilisant la factorisation
(X +1) = (X +1)" (X +1)",

montrer que
2. Rappeler la formule de Stirling, puis déterminer un nombre réel c > 0 tel que

on 47
PJ C ----=:
nm } n---+0c0 nn

3. Si a est un élément de [0, 1{, montrer, par exemple en utilisant une 
comparaison

série-intégrale, que

n 1 na

2 ka n--+oo 1 -- &

Si à est un élément de |1,+oc|, montrer de même que

EL
nt KA n--+00 (a -- 1) n4--1

4. Pour x EUR [2,+æ{, on pose

Établir par ailleurs la relation

T dt
l (6 200 © UM).

En déduire finalement un équivalent de (x) lorsque x tend vers +00.

5. Pour & EUR KR, rappeler, sans donner de démonstration, le développement en
série entière de (1+ x)" sur | --1,1|.

Justifier la formule :

Vx EUR] ---1,1|,

B. Marches aléatoires, récurrence

On considère les fonctions F° et G définies par les formules

+00
Vr e]-1,1,  F(x) = ÿ P(S, = Oa) x";
n--=0

Vxæ EUR [-1,1|} G(x) = s P(R=n) x".
10.

11.

Montrer que les séries entières définissant F et G ont un rayon de convergence
supérieur ou égal à 1. Justifier alors que les fonctions F et G sont définies et
de classe C® sur | --1,1|.

Montrer que G est définie et continue sur |[--1,1] et que

G(1) = P(R Z +0).

Si k et n sont des entiers naturels non nuls tels que # < n, montrer que P((Sn = 04)N(R=Rk)) = P(R=Rk) P(S,_x = 0g). En déduire que VnEN",  P(S;=04) = P(R=Kk) P(Sh_x = Ua). Montrer que Vx EUR] --1,1|, F(x) =1+F(x) G(x). Déterminer la limite de F(x) lorsque x tend vers 17, en discutant selon la valeur de P(R Æ +c). Soit (cy)ren une suite d'éléments de RT telle que la série entière > ca" ait

un rayon de convergence 1 et que la série > cx diverge. Montrer que

+00
Sd _cR ae -- +OO.
k--0 x--1--

L'élément À de RT* étant fixé, on montrera qu'il existe à EUR]0, 1[ tel que

+00
Vx El -- a,1|, Y cr" > A.
k=--0

Montrer que la série > P(Sn = 04) est divergente si et seulement si
P(R £ +) = 1.

Pour à EUR N°, soit Y; la variable de Bernoulli indicatrice de l'événement

(Si & {Sk. O à).
12. Conclure que

E(Nn) --> P(R = +c).

n n-- +00

On pourra admettre et utiliser le théorème de Cesàro : si (uy)new* est une
suite réelle convergeant vers le nombre réel £, alors

1 nm

-- > Uk --> {.
n k--] n-- +00

C. Les marches de Bernoulli sur Z

Dans cette question, d est égal à 1 et on note donc simplement 07 = 0. Par
ailleurs, p est un élément de |0,1}, 4 = 1--pet la loi de X est donnée par

P(X =1)=p et PIX = -1)= a.

13. Pour n EUR N, déterminer P(S2,+1 = 0) et justifier l'égalité :

T

P(San = 0) -- fr) (pq).

14. Pour x EUR] -- 1,1}, donner une expression simple de G(x).
Exprimer P(R = +) en fonction de |p -- q|.
Déterminer la loi de À.

15. On suppose que
1

2

q --=
Donner un équivalent simple de P(R = 2n) lorsque n tend vers +oco. En
déduire un équivalent simple de E(N,) lorsque n tend vers +co.

D --

D. Un résultat asymptotique

Soient (an }nen et (bn)nen deux suites d'éléments de RT*. On suppose que (ay 
}nen
est décroissante et que

Vn EN, dar bn-r = 1.
k=--0

On pose, pour n EUR N.

Br = D x.
k=--0
16. Soient m et n deux entiers naturels tels que m > n. Montrer que

1

 % 1< an Bm-n + 00 (Bm -- Bm-n). An < 17. On suppose dans cette question qu'il existe une suite (my )nen vérifiant my > n
pour n assez grand et

Bin © Bn et Bm, -- Bmirn -- 0.

n-- +00 n-- +oo

Montrer que
1

a TV ------ *
° n-- +00 BP

18. On suppose dans cette question qu'il existe C' > 0 tel que

, EUR

MN
n--+oo 7

En utilisant la question 17 pour une suite (m,)nen bien choisie, montrer que

1
nt C mn)

E. La marche aléatoire simple sur Z° : un théorème d'Erdôs et
Dvoretzky

19. Soit n EUR N*. Montrer que

Dans les questions 20 et 21, on suppose que d = 2 et que la loi de X est donnée 
par

PIX = (0,1)) = P(X = (D,--1)) = P(X = (1,0)) = P(X = (-1,0)) = 2

20. Soit n EUR N. Établir l'égalité

P(S2n = 02) -- (io)

21. Donner un équivalent simple de E(N,) lorsque n tend vers +co.

FIN DU PROBLÈME

9

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Maths 2 MP 2020 -- Corrigé
Ce corrigé est proposé par Rémi Pellerin (ENS Lyon) ; il a été relu par Quentin
Guilmant (doctorant en informatique) et Florian Metzger (professeur en CPGE).

Ce sujet propose l'étude du nombre de sites visités par une marche aléatoire
dans Zd . Il est composé de cinq parties.
· Dans la partie A, on établit des résultats qui seront utilisés dans les 
parties C
et E. Il s'agit de raisonnements combinatoires élémentaires ainsi que 
d'équivalents de sommes de séries numériques. Les résultats et les méthodes sont
proches du cours et doivent être maîtrisés.
· La partie B propose de montrer quelques résultats généraux sur les marches
aléatoires dans Zd . Elle est plutôt difficile mais les résultats qui sont 
utiles
pour les parties C et E sont donnés.
· La partie C est consacrée à l'étude du cas d = 1 avec des pas de longueur 1.
On y montre qu'il n'y a que lorsque les déplacements sont équiprobables que
l'on revient presque sûrement à l'origine en temps fini. On termine en donnant
un équivalent du nombre d'entiers visités.
· Dans la partie D, on démontre un résultat sur les suites numériques qui sera
exploité à la dernière question.
· Enfin, la dernière partie propose l'étude de la marche aléatoire isotrope 
(c'està-dire lorsque tous les déplacements donnés par la base canonique sont 
équiprobables) à pas de longueur 1 dans Z2 . On y fait la synthèse des 
résultats précédents. On termine en donnant un bel équivalent du nombre de 
sites visités !
C'est le théorème d'Erdös-Dvoretzky. Cette partie est un peu plus technique
que les autres.
Ce sujet est bien construit et très intéressant. On y montre des résultats 
puissants et même surprenants ! Il est d'une difficulté et d'une longueur 
raisonnables comprenant quelques questions assez astucieuses. Il s'agit d'un 
très bon problème pour
s'entraîner en temps limité. Il permet de réviser une grande partie du programme
d'analyse, notamment les séries numériques, les séries entières et les 
probabilités.

Indications
Partie A
1 Quel est le coefficient de Xn dans (X + 1)2n ?
4 Justifier que 1/ ln et 1/ ln2 ne sont pas intégrables sur [ 2 ; + [ et 
utiliser le
théorème d'intégration des relations de comparaison.
5 On rappelle que
  R

(1 + x) = 1 +

x  ] -1 ; 1 [

+
X
 ( - 1) · · · ( - n + 1)

n!

n=1

xn

Partie B
7 Remarquer que
2

(n, k)  (N )

k>n

(Sn = 0d )  (R = k) =

=

 P
n

Xi = 0d  (R = k)

i=k+1

8 Utiliser un produit de Cauchy.
11 Penser à renverser le temps.
Partie C
14 Montrer, en utilisant le résultat de la question 5, que
1
F(x) = p
1 - 4 p q x2

x  ] -1 ; 1 [

Pour déterminer la loi de R, effectuer un développement en série entière de G.
+
P
15 On pourra chercher un équivalent du reste
P(R = 2k).
k=n+1

Partie D
n  N

16 Montrer que

an Bn 6 1

18 Prendre mn = bn ln(n)c pour n > 1 et justifier que
Bmn - Bmn -n

n+

C×

m
Pn

1
k=mn -n+1 k

Partie E
19 Montrer que la suite de terme général suivant est constante :
an =

n
P

P(Sk = 0d ) P(R > n - k)

k=0

20 Dans un chemin dans Z2 qui termine à son point de départ (0, 0), considérer 
les
pas qui sont parallèles aux abscisses et ceux parallèles aux ordonnées.
21 Utiliser le résultat de la question 18 afin d'obtenir un équivalent de P(R > 
n)
et en déduire un équivalent de E(Nn ) en utilisant le théorème de sommation des
relations de comparaison ainsi que le résultat de la question 4.

Publié dans les Annales des Concours

A. Préliminaires
1 Procédons comme le suggère l'énoncé et considérons le polynôme P = (X + 1)2n .
La formule du binôme de Newton dans l'anneau commutatif R[X] donne

2n 
X
2n
2n
P = (X + 1) =
Xk
k
k=0
 
2n
De ce fait, le coefficient de Xn dans P est
.
n
Une autre façon de calculer le coefficient de Xn dans P est de considérer P sous
la forme du produit de polynômes
P = (X + 1)n (X + 1)n
X
 X

n  
n  
n
n
k
i
P=
X ×
X
k
i
i=0
k=0
n X
n   
X
n
n
=
Xk+i
k
i
k=0 i=0
n   
X
n
n
P=
Xk+i
k
i

On a donc

i,k=0

Par unicité des coefficients d'un polynôme, le coefficient de Xn dans P est 
donc obtenu
pour les indices i, k tels que k + i = n. Il vaut ainsi

n  
X
n
n
k
n-k
k=0

n 
X

d'où,

k=0

n  N

Or,

n
k

k  [[ 0 ; n ]]

n  N

ce qui prouve

n
n-k

2n
=
n

n
n
=
n-k
k

n  2
X
n
k=0

k

=

2n
n

2 La formule de Stirling est un équivalent de n ! en +. D'après le cours,
 n n

n! 
2n
n+
e
Soit n  N. Si an

n+

bn alors a2n

n+

2n
n

=

(2n) !

n ! × n ! n+

b2n donc

2 n
2n
e
 n 2n
2n
e

4n

4n

n+
n

En posant c = 1/  > 0, il vient que
 
4n
2n
 c
n n+
n

Publié dans les Annales des Concours

3 Soit   ] 0 ; 1 [. La fonction t 7 1/t est continue et décroissante sur [ 1 ; 
+ [.
De ce fait, une comparaison série-intégrale fournit
Z k+2
Z k+1
1
1
1
dt 6
6
dt
k > 1

(k + 1)
t
k+1 t
k
Sommons de 1 à n - 1 pour obtenir, avec la relation de Chasles,
Z n
Z n+1
n-1
n
X
X
1
1
1
1
dt
6
=
6
dt

t
(k + 1)
k
1 t
2
k=1

d'où,

t1-
1-

k=2

n+1
+16
2

n
X
k=1

 1- n
t
1
6
+1

k
1- 1

(car  6= 1)

n

puis

an =

X 1
21-
n1-
1
(n + 1)1-
-
+16
6
-
+ 1 = bn

1-
1-
k
1- 1-
k=1

Comme (n + 1)

1-

n+

an

n

1-

----- + car 1 -  > 0, il vient que
n+

n1-
n+ 1 - 

bn

et

n1-
n+ 1 - 

n

1- X 1
----- 1
n1-
k  n+

Par encadrement,

k=1

n
X
1
k

  ] 0 ; 1 [

soit

k=1

n1-
n+ 1 - 

P
On retrouve que
1/k  est divergente pour   ] 0 ; 1 [ ce que l'on sait
d'après le critère de Riemann.
Au passage, on voit l'équivalence entre la
P
convergence de la série
1/k  et l'intégrabilité de t 7 1/t sur [ 1 ; + ].
Notons que les inégalités de comparaison série-intégrale établies plus haut 
restent
valables pour  > 1 car la fonction t 7 1/t est décroissante et continue sur [ 1 
; + [ :
Z k+2
Z k+1
1
1
1
dt
6
6
dt
k  N

(k + 1)
t
k+1 t
k
Puisque  > 1,P
le critère de Riemann assure que t 7 1/t est intégrable sur [ 1 ; + ]
et que la série
1/k  converge. Par conséquent, en sommant de n à +,
Z +
Z +
+
X
1
1
1
dt 6
6
dt

t
(k
+
1)
t
n+1
n
k=n

1-

-(n + 1)
1-

d'où
Puis, comme (n + 1)

1-

n+

n

+
X
1
-n1-
6
6
k
1-

k=n+1

1-

, il vient, toujours par théorème d'encadrement,

+
-1 X 1
----- 1
n-1
k  n+

k=n+1

+

d'où

1

k
k=n+1
P

n+

1
( - 1) n-1