Centrale Maths 1 PSI 2019

Thème de l'épreuve Analyse combinatoire de différents modèles d'urne
Principaux outils utilisés Séries entières, probabilités, dénombrement
Mots clefs Polya, Flajolet, Urne

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


Mathématiques 1 O)
qi

Ps! ©

4 heures Calculatrices autorisées ON

Analyse combinatoire de différents modèles d'urne

En 1923, le mathématicien George Pélya introduit une expérience d'urne 
aléatoire pour modéliser la propagation
d'épidémies. Ce modèle, à base de tirages de boules colorées dans une urne, et 
ses généralisations ont donné
naissance à un grand nombre d'études qui ont conduit à des applications 
variées, notamment en économie et en
finance.

Au milieu des années 2000, le chercheur français Philippe Flajolet propose une 
nouvelle approche de ces modèles,

à base de combinatoire et de séries génératrices. Sa méthode s'applique à la 
totalité des modèles d'urne dite

« équilibrée », là où les techniques de résolution antérieures étaient 
spécifiques de chaque protocole de tirage.

Cette épreuve est organisée en cinq parties dans une large mesure indépendantes 
:

-- dans la partie I, il est demandé de démontrer un résultat du cours qui est 
utilisé dans la partie IV ; le résultat
de la question 6 sert dans la partie V ;

-- la partie IT traite un cas particulier qui est généralisé dans la partie IV ;

-- la partie IIT introduit la méthode de Philippe Flajolet ;

-- les parties IV et V étudient deux protocoles différents de tirage ; la 
partie V permet également d'établir un
lien avec certaines permutations d'un ensemble fini.

Notations

Dans tout le problème, on définit la famille de polynômes (L;)ren par

Lo=1
LR DR D Vk EUR N*

On appelle fonction polynomiale de deux variables réelles u et v, toute 
combinaison linéaire d'applications de
la forme (u,v) -- ufu/ où (i,j) EUR N?.

I Résultats préliminaires

IA - Soit à un réel. On note f,:xH (1--x) *.
Q 1. Préciser le domaine de définition D de f,. Justifier que f, est de classe 
C1 sur D et donner une
équation différentielle linéaire du premier ordre vérifiée par f, sur D.

Q 2. Énoncer le théorème de Cauchy pour une équation différentielle scalaire 
linéaire du premier ordre et
démontrer que, pour tout x EUR |-1,1|,

+00 x"
n=0
Q 3. Rappeler la définition du produit de Cauchy de deux séries entières et 
énoncer le théorème qui s'y
rapporte.
Q 4. En déduire que, pour tout entier n et tous réels a et B,
fn
k=0
I.B -
+00
Q 5. Pour x EUR |---1,1/, donner la valeur de la somme de la série entière ÿ x? 
ainsi que celle de sa dérivée.
p=l
Q 6. Démontrer par récurrence que, pour tout entier n EUR N*, il existe un 
unique polynôme R, EUR R,[X] tel

que, pour tout x EUR |---1,1|,

+00
R, (x)
np -- n
22? ä (x

2019-02-15 09:54:50 Page 1/5 (©) sY-Nc-sA
IT Un modèle particulier d'urne de Pôlya

On dispose d'un stock infini de boules noires et blanches. Une urne contient 
initialement une boule noire et une
boule blanche. On effectue une suite de tirages selon le protocole suivant :

-- on tire au hasard une boule de l'urne :
-- on replace dans l'urne la boule tirée ;
-- on ajoute dans l'urne une boule de la même couleur que la boule tirée.

On définit la suite (X,,),en de variables aléatoires par X, = 1 et, pour tout 
entier n > 1, X,, donne le nombre
de boules blanches dans l'urne après n tirages. On note g, la fonction 
génératrice de la variable X,. On rappelle

+00
que 9,(0) = D PIX, = R)U
k=0

Q 7. Déterminer les lois de X,, À, et X, puis les fonctions g,, go et g3.
Q 8. Soient n et k deux entiers supérieurs ou égaux à L. Établir que
k-- 1 n+l--k
P(X, = k) = PIX, =k-1 -- PIX, =k).
( n ) n+l ( n--1 ) + n+l ( n--1 )
Q 9. En déduire que, pour tout entier n supérieur ou égal à 1 et tout réel #,
ES
Intt) = n+I 9 _1(t) + ÿn-1():
Q 10.  Démontrer que, pour tout entier n EUR N° et tout réel #,
1 n+1l
t) = ff.
Q 11. Identifier la loi de X,, et donner son espérance.

IIT Modèle général d'urne équilibrée
Dans cette partie, on généralise le modèle de la partie précédente.

Soient &p, Up, @, b, cet d six entiers naturels. On dispose à nouveau d'un 
stock infini de boules noires et blanches,
mais celles-ci sont cette fois numérotées, à partir de zéro, de manière à 
pouvoir les différencier. L'urne contient
initialement a, boules blanches et d, boules noires. On effectue une suite de 
tirages selon le protocole suivant :

-- on tire au hasard une boule dans l'urne ;

-- on replace cette boule dans l'urne ;

-- si la boule tirée est blanche, on ajoute dans l'urne a boules blanches et db 
boules noires ;

-- si la boule tirée est noire, on ajoute dans l'urne c boules blanches et d 
boules noires.

On suppose que a + b = c + d, on dit alors que l'urne est équilibrée et on note 
s=a+b=c+d.

Pour n > 1, une issue résultant de n tirages successifs est modélisée par le 
n-uple indiquant la couleur et le
numéro des boules successivement obtenues. On note (,, l'ensemble des issues 
possibles de ces n tirages.

La figure 1 donne deux exemples de 3 tirages (n = 3), pour ay = by = 1, a = d = 
1 et b = c = 0 (modèle de la
partie précédente). La boule au dessus de chaque flèche représente celle qui a 
été tirée.

©.) ©.k)e
OL: (1 Q

(@
Figure 1 Deux exemples de 3 tirages
La première suite de trois tirages est modélisée par l'issue w, = (B,,B,,N,) 
EUR (2 : la deuxième suite est

modélisée par l'issue w = (Bo, No, B;,) EUR 3. On note que ces deux issues 
différentes aboutissent à la même
composition de l'urne.

2019-02-15 09:54:50 (Cc)EATET:

Page 2/5
Pour w EUR (,, on note b(w) (respectivement n(w)), le nombre de boules blanches 
(respectivement noires) présentes
dans l'urne à la fin des n tirages modélisés par w.

Pour tous réels u et v, on pose P,(u, vu) = uv et P,(u,v) -- > ab) pre),

WE},
Pour n > 1, on note à nouveau À,, le nombre de boules blanches présentes dans 
l'urne après n tirages et g, sa
fonction génératrice.

Dans les deux questions suivantes, on suppose ay = 1, db =0,a=d--=0etb=c-- TI. 
En d'autres termes, l'urne
contient, au départ, une boule blanche et, à chaque tirage, on ajoute une boule 
de la couleur opposée à celle qui
a été tirée.

Q 12. En dressant la liste de toutes les issues possibles, donner la loi de X,.

Q 13. Vérifier que P,(u, v) = uv° + Auv° + u°v.

On revient désormais au cas général d'une urne équilibrée.

Q 14. En examinant le nombre de boules dans l'urne juste avant chaque tirage, 
justifier que, pour n > 1.

card(Q,,) = (ag + bo) X + X ((ao + bo + sfn --1)) = 8"LZ, (un)

Q 15. Montrer que, pour tout n EUR N° ct tout k EUR N.

_ card({w EUR Q,,;b(w) = kÿ)

P(X, = k) =
An = À) card Q,,
Q 16.  Justifier les égalités
(= PE D):
BRUT card(Q,) "7°
1 OP

EX) = os Ge 1)

Q 17.  Démontrer que, pour tout entier n.

OP OP
P,itu,v) = uv (u, v) + utvtti So (u, v). (IIL.1)

Pour tous réel x, u et v, on pose, sous réserve d'existence,

+00 n
H(x,u,v) = D _P,(u,v) --.
n!
n=Û0

Soit p > 0. On pose D, = ]-p,p| x ]0,2[ = {(x,u,u) E R° ; [x] < p, 0  0 tel 
que D, EUR U et, pour tout
(æ,u,v) EUR D,,

où Q,, est une fonction polynomiale de deux variables à préciser.

Q 23. Justifier que G admet une dérivée partielle d'ordre 1 par rapport à x sur 
le domaine D,, obtenue par
dérivation terme à terme par rapport à x de l'expression de A.

Q 24.  Démontrer que G admet une dérivée partielle d'ordre 1 par rapport à u 
sur le domaine D,, obtenue
par dérivation terme à terme par rapport à w de l'expression de A.

On admet qu'il en est de même pour la variable vw.

Q 25. En déduire que, pour tout entier n, P, = Q,, puis que A et G coïncident 
sur D,, où H et (P,, )nen ont
été définis dans la partie III.

Q 26.  Conclure que, pour tout entier n et pour tout k EUR [0, nl,

P(X, = ap + ka) = (.) On

Q 27. À l'aide du résultat précédent, retrouver celui de la question 10.

Q 28. À l'aide des résultats des questions 16 et 19, déterminer l'espérance de 
X,.

V Urne de Friedman et montées de permutations
Dans cette partie, on suppose que & = l, db =0,a=d=0,b=c= TI, ce qui correspond 
au protocole utilisé
dans les questions 12 et 13 (modèle introduit par Friedman en 1945).

V.A -

On conserve toutes les notations de la partie IIT (tous les résultats de cette 
partie peuvent être admis). On a
donc en particulier card(Q,,) = n!. On admet, pour 0 < u < v et |x| assez petit, l'égalité H(x,u, 0) D Sr ua (À) . Q 29. À l'aide de la question 6, justifier que, pour tout entier n et tous u et v tels que 0 < u < v, la somme Dre us (2) est une fonction polynomiale de u et v. On a donc, d'après la question 16, pour tout entier n et tout t EUR |0,1|, FR Drva- y, Dans toute la suite, on fixe un entier n > 2.
+00

Q 30. Montrer que > pit = Of),

p=n<1 t--0T Q 31. En utilisant ce qui précède et en développant (1 -- t)"*!, déterminer le développement limité de g,, à l'ordre n en 0. Q 32. En déduire que, pour tout m dans [|1,n}, 2. 2019-02-15 09:54:50 Page 4/5 (Cc)EATET: V.B - Montées d'une permutation Soit n EUR N* et u = (up....,u,) une suite finie d'entiers, deux à deux distincts. Une montée (respectivement descente) de u est un indice à EUR [0,n -- 1] tel que u, < u,,, (respectivement u, > u,,:).

Q 33. Soit k un entier supérieur ou égal à 1, (up, ...,u,) une suite finie 
d'entiers, et a un entier tel que a > ü
pour tout p EUR [0,k]. On insère la valeur a dans cette suite juste après u,, 
avec à EUR [0,k -- 1], de manière à
obtenir la suite (up, ...,u;,a,u;,,,...,u,). Comparer le nombre de montées et 
de descentes de la nouvelle suite
par rapport à l'ancienne. On distinguera deux cas.

On note S,, l'ensemble des permutations de ]1,n{], c'est-à-dire des fonctions 
bijectives de [1,n] dans lui-même.
On représente un élément © de $,, par la suite finie (o(1),o(2),.....,o(n)) et 
on appelle montée (respectivement
descente) de o une montée de cette suite. Par exemple, avec n = 4, la 
permutation o représentée par la liste
(a(1),o(2),a(3),a(4)) = (4,1,3,2) admet une montée et deux descentes. Pour tout 
entier m, on note 4,,, le
nombre d'éléments de 5, avec m montées.

Q 34. Déterminer les éléments de 5, et calculer parmi eux le nombre de 
permutations avec m montées
pour tout entier m. Comparer les valeurs obtenues avec les coefficients de 
P,(X,1) où P; a été exprimé à la
question 13.

Q 35. Soit n > 2. Déterminer À

L'objectif de ces dernières questions est de déterminer À,,,, pour tous entiers 
n 2 2 et m < n -- 1 en établissant un lien entre ces valeurs et le modèle d'urne étudié dans cette partie. 0 Ann-1 © Aym POUT M Zn. On étudie un algorithme permettant de construire une permutation de $,, à partir d'une issue correspondant à n tirages. -- On démarre la construction à la suite du premier tirage : on a nécessairement tiré la boule blanche et l'urne contient maintenant une boule de chaque couleur. On considère la suite (0,1,0) qui comporte exactement une montée et une descente. -- Si on tire la boule blanche (respectivement noire) lors du deuxième tirage, on insère la valeur 2 au mi- lieu de la première et unique montée (respectivement descente) de la suite pour obtenir la suite (0,2,1,0) (respectivement (0,1,2,0)). -- Plus généralement, pour tout k EUR [2,n], si au k-ième tirage on tire une boule blanche (respectivement noire) numérotée p, on insère la valeur k dans la suite au milieu de la (p+1)-ième montée (respectivement descente). -- À Ja fin de la construction, on supprime les deux 0 de la liste (qui sont nécessairement restés en début et fin de liste). La liste obtenue contient les entiers de 1 à n et représente un élément © de $,,. Si w désigne la suite des tirages, on note o(w) la permutation obtenue. À titre d'exemple, construisons o((B,, No, B)). -- Tirage 1: B, On démarre avec la suite (0, 1,0). -- Tirage 2: N, insère au milieu de la première (p = 0) descente (la boule est noire) pour donner la L'entier 2 (k = 2)s 1,2,0) nouvelle suite (0, 1, -- Tirage 3: B, L'entier 3 s'insère au milieu de la deuxième montée pour donner (0,1,3,2,0). On obtient ainsi o((B,, No. B,)) = (1,3,2). Q 36. À l'aide de l'algorithme ci-dessus, construire la permutation de 5: associée à l'issue (B,, B,,N,,N,,B). Q 37.  Réciproquement, soit o l'élément de S; représenté par la suite (7,1,3,6,5,4,2). Déterminer une issue w comportant 7 tirages telle que o,, = a. Q 38. À l'aide de la question 33, comparer, pour une issue quelconque, le nombre de boules blanches dans la composition finale de l'urne au nombre de montées de la permutation qui lui est associée par l'algorithme ci-dessus. On admet que l'application w H o{w) est bijective de Q,, dans $,, et qu'elle induit une bijection entre l'évènement (X,, = m) et l'ensemble des permutations de $, ayant m -- 1 montées. Q 39. Soit m EUR ]1,n]. Déterminer, pour tout entier n > 2 et tout m EUR [0,n 
-- 1] le nombre 4,,, de
permutations de $, ayant m montées.

eeoeFrFINeee

2019-02-15 09:54:50 Page 5/5 (Cc)EATET:

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



Centrale Maths 1 PSI 2019 -- Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (professeur en CPGE) ; il a été
relu par Christophe Fiszka (professeur en CPGE) et Céline Chevalier 
(enseignantchercheur à l'université).

Cette épreuve a pour thème les modèles d'urne de Pólya. Introduite en 1923 puis
rapidement généralisée, la problématique consiste à étudier l'évolution du 
contenu
d'une urne contenant des boules blanches ou noires. À chaque instant, une boule 
est
tirée au hasard. On ajoute alors au contenu de l'urne une certaine quantité de 
boules,
celle-ci dépendant uniquement de la couleur de la boule piochée. Le sujet se 
focalise
sur une méthode d'analyse développée par le chercheur français Philippe 
Flajolet au
milieu des années 2000.
· La première partie introduit un certain nombre de résultats préliminaires. 
Elle
utilise les séries entières et les équations différentielles.
· La deuxième partie propose l'étude d'un premier exemple simple d'urne. Elle
porte uniquement sur le cours de probabilités. Son objectif est d'obtenir à 
l'aide
de relations de récurrence, dans un cas relativement simple, la loi de la 
variable
aléatoire Xn donnant le nombre de boules blanches dans l'urne après n tirages.
· La troisième partie concerne le coeur de la méthode du professeur Flajolet. 
S'attaquant au modèle généralisé d'urne de Pólya dit équilibré, elle a pour 
objectif
d'établir une équation aux dérivées partielles satisfaite par une fonction H de
3 variables introduite en milieu de partie. Cette fonction H est essentielle à
l'étude du modèle puisqu'elle permet, par de simples dérivations partielles et
développements en série entière, de retrouver la loi de la variable aléatoire 
Xn .
· La quatrième partie utilise les outils précédents pour l'étude du modèle 
historique introduit par Pólya en 1923 (avant donc ses généralisations).
· La cinquième partie commence par l'étude d'un second modèle introduit par
Friedman en 1945, avant d'appliquer les résultats obtenus à des problématiques
de dénombrement de permutations.
Cette épreuve permet donc de manipuler une bonne partie du programme d'analyse 
de prépa (séries entières, fonctions de plusieurs variables, théorèmes de 
dérivations terme à terme) et du programme de probabilités. La difficulté se 
veut résolument
progressive avec deux premières parties sans grandes difficultés techniques. Il 
s'agit
d'une épreuve originale donnant un aperçu très accessible d'un véritable 
travail de
recherche publié par un chercheur français renommé.

Indications
Partie I
1 Exprimer

f

en fonction de f .

2 Montrer que les fonctions g : x 7-
problème de Cauchy.

+
P

Ln ()

n=0

xn
et f sont solutions d'un même
n!

4 Remarquer que (1 - x)-(+) = (1 - x)- (1 - x)- .
6 Pour construire Rn+1 à partir de Rn , on pourra dériver l'égalité par rapport 
à x,
puis multiplier par x.
Partie II
7 Déterminer toutes les évolutions possibles de l'urne pendant 3 tirages. On 
pourra
utiliser une représentation sous la forme d'un arbre.
8 Utiliser le système complet d'évènements ((Xn-1 = p))pN .
9 Utiliser le résultat de la question précédente dans l'expression de gn , puis 
séparer
les sommes et réindexer.
10 Démontrer le résultat par récurrence sur n.
11 On pourra reconnaître une loi uniforme.
12 Procéder comme à la question 7 en énumérant toutes les évolutions possibles 
du
contenu total de l'urne.
Partie III
14 Remarquer que le nombre de boules dans l'urne après n tirages est indépendant
de la nature des tirages.
15 À l'aide de la question 14, remarquer que toutes les issues sont 
équiprobables.
16 La première égalité est une conséquence de la question 15. Pour la seconde, 
utiliser
la relation entre E(Xn ) et la dérivée de gn .
17 Calculer le membre de droite de l'égalité puis utiliser une partition 
judicieuse de
l'ensemble n+1 .
18 Majorer grossièrement la quantité Pn (u, v) xn /n!.
19 Remarquer que la fonction x 7- H(x, u, v) est la somme d'une série entière.
20 Appliquer le théorème de dérivation des séries de fonctions.
21 Utiliser la question 17 et les dérivations terme à terme justifiées dans les 
questions
précédentes.
Partie IV
22 Utiliser les développements en série entière de la question 2.
23 Passer par un argument de série entière comme à la question 19.
24 Utiliser le théorème de dérivation des séries de fonctions comme à la 
question 20.
On pourra utiliser la question 4 pour obtenir une majoration simple.
25 À l'aide de l'équation aux dérivées partielles et des « conditions initiales 
», démontrer que les suites (Pn )nN vérifient la même relation de récurrence et 
la même
condition initiale.

26 Utiliser l'unicité des coefficients d'une fonction polynomiale et les 
questions 14,
16 et 25.
27 Calculer pour tout entier p les quantités Lp (1) et Lp (2).
28 Utiliser les questions 16 et 20 (et non pas 19) puis l'unicité des 
coefficients d'une
série entière.
Partie V
n
P
29 Utiliser la question 6 en notant Rn =
ak Xk .
k=0

30 Majorer grossièrement (1 - t)
par 1 sur ] 0 ; 1 [ puis factoriser par tn+1 avant
d'utiliser un argument de continuité d'une série entière en 0.
n+1

31 Couper la somme au rang n à l'aide de la question précédente, puis 
développer le
terme (1 - t)n+1 à l'aide du binôme de Newton.
32 Utiliser l'unicité du développement limité en comparant l'expression donnée 
par
la définition de gn avec celle de la question précédente.
33 Distinguer deux cas suivant que l'insertion se fait au milieu d'une montée 
ou au
contraire d'une descente.
34 On doit retrouver des coefficients identiques, à un décalage d'indice près.
35 Remarquer le nombre de montées d'une permutation est compris entre 0 et n - 
1,
puis déterminer les cas d'égalité.
36 Ne pas oublier qu'on ne tient pas compte du premier tirage !
37 Reconstruire les étapes de construction de la suite en « remontant le temps 
»,
ce qui revient à enlever successivement le plus grand élément de la suite.
38 Regarder comment évolue le nombre de montées/descentes de la suite en 
construction en fonction de la couleur de la boule tirée.
39 Exprimer An,m en fonction de Card (n ) et P(Xn = m + 1) à l'aide du résultat
de la question précédente et sans oublier que toutes les issues sont 
équiprobables
dans le modèle d'urne.

I

Résultats préliminaires

1 Par définition, pour tout x < 1 f (x) = exp (- ln(1 - x)) ce qui prouve que La fonction f est définie sur D = ] - ; 1 [ Si  est un entier négatif, la fonction f est polynomiale donc définie sur R. Cette expression montre également que f est de classe C 1 par composition. De plus, f (x) x < 1 f (x) = (1 - x)--1 = 1-x d'où l'on déduit aussitôt que (1 - x)f (x) - f (x) = 0 x  ] - ; 1 [ 2 Le théorème de Cauchy pour une équation différentielle scalaire linéaire du premier ordre s'énonce ainsi : Soient a et b deux applications continues sur un intervalle I de R, et soient t0  I et y0  R. Alors, l'équation différentielle y  = ay + b admet une unique solution y définie sur I et telle que y(t0 ) = y0 . La fonction f est solution du problème de Cauchy ( y  (x) = y(x) 1-x y(0) = 1 Pour en déduire l'égalité demandée, il suffit donc de montrer que g : x 7- + P Ln () n=0 xn n! est également solution de ce problème de Cauchy. Commençons déjà par montrer que la fonction g est bien définie sur ] -1 ; 1 [. Si  est un entier négatif, alors Ln () est nul pour n >  donc f est bien définie (c'est même une application polynomiale).
Sinon, Ln () ne s'annule jamais et pour tout x > 0, si l'on pose un = Ln () xn 
/n!,
alors on a
un+1
|Ln+1 ()| n!
| + n|
= |x|
= |x|
----- |x|
un
|Ln ()| (n + 1)!
n + 1 n+
La règle de d'Alembert assure que la série de terme générale un converge si |x| 
< 1 et diverge si |x| > 1, donc la série entière de terme général Ln () xn /n! a un 
rayon
de convergence égal à 1 et sa somme g est définie sur ] -1 ; 1 [.
Par propriété des séries entières, on peut donc dériver terme à terme sur cet
intervalle et obtenir pour tout x tel que |x| < 1 g  (x) = + P Ln () n=1 + P n xn-1 xn = Ln+1 () n! n! n=0