CCP Maths PC 2017

Thème de l'épreuve Automate probabiliste
Principaux outils utilisés probabilités, séries entières, déterminants, polynôme caractéristique
Mots clefs automate, temps d'attente

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


SESSION 2017

PCMA002

!

!
!

EPREUVE SPECIFIQUE - FILIERE PC!
!!!!!!!!!!!!!!!!!!!!"
!

MATHEMATIQUES
Mardi 2 mai : 14 h - 18 h!
!!!!!!!!!!!!!!!!!!!!"
N.B. : le candidat attachera la plus grande importance à la clarté, à la 
précision et à la concision de
la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être 
une erreur d'énoncé, il le
signalera sur sa copie et devra poursuivre sa composition en expliquant les 
raisons des initiatives
qu'il a été amené à prendre.!

!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
!
!
!
!
!
!
!
!
Les calculatrices sont interdites
!
!
!
!
!
!
!
!
L'epreuve est constituee d'un probleme en cinq parties largement independantes.
!
!
!
!
! Lorsqu'un raisonnement utilise un resultat obtenu precedemment dans le 
probleme, il est
! demande au candidat d'indiquer precisement le numero de la question utilisee.
!
!
!
!
!
1/7

!

PROBLEME
Soit p  ]0, 1[. On pose q = 1 - p.
On considere un automate qui genere successivement les lettres C ou P jusqu'a 
obtenir une
certaine sequence predefinie.
On suppose que pour tout n  N , l'automate genere la n-ieme lettre a l'instant 
n de facon
independante de toutes les generations precedentes. On suppose egalement qu'a 
chaque generation,
les lettres P et C ont des probabilites p et q (respectivement) d'etre 
generees. Suivant les parties
considerees, on definit differents niveaux que l'automate peut atteindre.
On considere dans tous les cas que l'automate est initialement au niveau 0. On 
se propose
alors d'etudier essentiellement l'existence de l'esperance et de la variance de 
la variable aleatoire
correspondant au temps d'attente de la sequence predefinie a travers sa serie 
generatrice.
Pour cette etude probabiliste, on mobilise diverses proprietes analytiques 
(surtout sur les series
entieres) et quelques proprietes d'algebre lineaire.
Dans les parties I, II et V, on examine le temps d'attente pour les sequences C 
puis CC, puis
CPC et CCPPC. La partie II est independante de la partie I et traite de 
questions preliminaires
sur les series entieres qui seront investies dans les parties III et V. La 
partie IV est independante
des parties precedentes et traite les questions preliminaires d'algebre 
lineaire qui servent exclusivement dans la partie V. La partie III ne depend de 
la partie I que par la question Q4 et de
la partie II que par la question Q10. La partie V utilise seulement la question 
Q11 de la partie
II et la partie IV.
Pour n  N , on note Pn l'evenement  l'automate genere la lettre P a l'instant n
l'evenement  l'automate genere la lettre C a l'instant n .

et Cn

Partie I - Etude d'un cas simple
Dans cette partie, on dit que l'automate passe du niveau 0 au niveau 1 des 
qu'il genere la lettre
C. Si, en revanche, il genere la lettre P, alors il reste au niveau 0. 
L'experience s'arrete des que
l'automate a atteint le niveau 1. On resume l'experience par la figure 1 
suivante :

C

0

1

P
Figure 1
On note Y l'instant ou, pour la premiere fois, l'automate atteint le niveau 1. 
On admet que Y
est une variable aleatoire definie sur un espace probabilise (, A , P) telle 
que Y ()  N . On
note GY la serie generatrice de Y et RY son rayon de convergence.
On sait alors que RY  1 et que :
t  ] - RY , RY [,

Y

GY (t) = E(t ) =

+

n=1

2/7

P(Y = n)tn .

Q1. Reconnaitre la loi de Y et preciser en particulier P(Y = n) pour n  N .

1 1
1
qt
.
, GY (t) =
Q2. Montrer que RY = > 1 et que : t  - ,
p
p p
1 - pt
Q3. Montrer que GY est 2 fois derivable en 1 et que GY (1) =

1
2p
et GY (1) = 2 .
q
q

Q4. Donner les valeurs de E(Y ) et de V(Y ).

Partie II - Series entieres
Soit z  C et a  C . Pour n  N, on pose un (a) = -
Q5. Montrer que

1
an+1

.

un (a)z n est une serie entiere de rayon de convergence egal a |a|.
+

1
Q6. Montrer que si |z| < |a|, on a :
=
un (a)z n .
z - a n=0
Soit a, b et  des nombres complexes non nuls. Dans les questions Q7 a Q10, on 
suppose que
n

uk (a)un-k (b) et pour tout reel t tel que
|a| < |b|. On definit alors, pour tout n  N, vn =
k=0

t2
.
|t| < |a|, f (t) =
(t - a)(t - b)

Q7. Montrer que l'on a :

n  k
1
1  b
1
1
.
vn = n+1
=
-
ab
a
b - a an+1 bn+1
k=0
Q8. Trouver un equivalent simple de vn quand n tend vers +.

Q9. En deduire que le rayon de convergence de
vn z n est egal a |a| et que si |z| < |a|, alors
+

1
=
vn z n .
(z - a)(z - b) n=0
Q10. Justifier que f est developpable en serie entiere au voisinage de 0 et que 
la serie entiere
qui lui est associee possede un rayon de convergence Rf tel que Rf = |a|.
Soit a, b, c et  des nombres complexes non nuls. On suppose que : |a|  |b|  |c|.
Pour tout reel t tel que |t| < |a|, on pose : g(t) =

t3
.
(t - a)(t - b)(t - c)

Q11. Justifier que g est developpable en serie entiere au voisinage de 0 et que 
la serie entiere qui
lui est associee possede un rayon de convergence Rg tel que Rg  |a|.

3/7

Partie III - Etude d'un cas intermediaire
Dans cette partie, on suppose que l'automate passe du niveau 0 au niveau 1 en 
generant la lettre
C. De meme, l'automate passe du niveau 1 au niveau 2 en generant la lettre C. 
Si, en revanche,
il genere la lettre P, alors qu'il est au niveau 0 ou 1, il retombe au niveau 
0. L'experience s'arrete
des que l'automate a atteint le niveau 2, c'est-a-dire des que l'automate aura 
genere la sequence
CC. On resume l'experience par la figure 2 suivante :

C

0
P

1

C

2

P
Figure 2

On note Z l'instant ou, pour la premiere fois, l'automate atteint le niveau 2. 
Ainsi Z est le
temps d'attente de la sequence CC.
On admet que Z est une variable aleatoire definie sur un espace probabilise (, 
A , P) telle que
Z()  N . Pour tout n  N , on note pn = P(Z = n). On note GZ la serie 
generatrice de Z
et RZ son rayon de convergence. On rappelle que RZ  1.
Q12. Calculer p1 , p2 et p3 .
Q13. Justifier que (P1 , C1  P2 , C1  C2 ) est un systeme complet d'evenements.
Q14. En deduire que pour tout n  3, on a : pn = ppn-1 + pqpn-2 .
Q15. En deduire que pour tout t  [-1, 1], on a : GZ (t)(1 - pt - pqt2 ) = q 2 
t2 .

- -p
-p
2
2
Pour t  R, on note Q(t) = 1 - pt - pqt ,  = p + 4pq > 0, a =
et b =
.
2pq
2pq
Q16. Montrer que Q(-1) = 1 + p2 > 0 et que Q(1) = q 2 > 0.
Q17. Montrer que, pour tout t  R, Q(t) = -pq(t - a)(t - b).
Q18. Montrer que 1 < |a| < |b|.
Pour tout reel t tel que |t| < |a|, on definit f (t) =

q 2 t2
.
1 - pt - pqt2

Q19. Montrer a l'aide de la question Q10 que f est developpable en serie 
entiere au voisinage
de 0, que sa serie entiere associee est GZ et que RZ = |a|.
Q20. Montrer que, pour tout t  ]-|a|, |a|[, on a : GZ (t) =

q 2 t2
.
1 - pt - pqt2

Q21. Montrer que Z admet une esperance et une variance puis que E(Z) = q -1 + q 
-2 .
Q22. Verifier, a l'aide des questions Q4 et Q21, que E(Z)  E(Y ) + 1 ou Y est 
la variable
aleatoire definie en partie I.
Q23. Pouvait-on prevoir ce resultat ?
4/7

Partie IV - Algebre lineaire

1
0
On considere les matrices I4 = 
0
0

0
1
0
0

0
0
1
0

p
0
q
0
, A = 
0
0
0
1

0
q
p
0

p
0
0
q

1
0
0 
0
 et L =  .
0 
0
0
0

Soit t  R. On note A le polynome caracteristique de A, si bien que A (t) est le 
determinant
de A - tI4 .
Q24. Montrer que 0 est valeur propre de A et donner un vecteur propre de A 
associe a la valeur
propre 0.
Q25. Trouver les reels ,  et  tels que, pour tout t  R, A (t) = t4 - t3 + t2 + 
t + .
 
S0
 S1 

On dit que la matrice colonne S = 
S2  est solution de (Et ) lorsque S = tAS + L.
S3
Q26. Montrer que, pour tout t  R, S est solution de (Et ) si et seulement si 
(I4 - tA)S = L.
Pour tout t  R, on note A (t) le determinant de la matrice I4 - tA.
Q27. Montrer que pour tout t  R , A (t) = t4 A (1/t).
Q28. Verifier que pour tout t  R, A (t) = -p2 qt3 + pqt2 - t + 1.
Q29. En deduire que, pour t au voisinage de 0, l'equation (Et ) possede une 
unique solution S.
Pour tout k  [[1, 4]], on note Uk la k-ieme colonne de
- tA. On note B la base canonique de
 I4
S0
 S1 

M4,1 (C) et on suppose que la matrice colonne S = 
S2  est solution de (Et ).
S3
Q30. Verifier que L = U1 S0 + U2 S1 + U3 S2 + U4 S3 .
Q31. En deduire que detB (U1 , U2 , U3 , L) = S3 · detB (U1 , U2 , U3 , U4 ) = 
S3 · A (t).
Q32. Montrer que, pour t au voisinage de 0, on a l'egalite :
S3 =

pq 2 t3
.
-p2 qt3 + pqt2 - t + 1

On se propose de determiner certaines proprietes des valeurs propres de A. On 
note  une valeur
propre complexe non nulle de A.
Q33. Montrer que  est valeur propre de la matrice transposee de A.

5/7

Q34. En deduire qu'il existe trois complexes non tous nuls x1 , x2 et x3 tels 
que :

 px1 + qx2 = x1
qx2 + px3 = x2 .
(H )

px1 = x3
On considere desormais trois complexes non tous nuls x1 , x2 et x3 qui 
verifient le systeme (H ).
On note alors M = max(|x1 |, |x2 |, |x3 |) et on remarque que l'on peut 
toujours se placer dans l'un
des trois cas suivants :
i) M = |x3 | ; ii) M = |x2 | avec M > |x3 | ;

iii) M = |x1 | avec M > |x2 | et M > |x3 |.

Q35. Montrer, en distinguant ces trois cas, que || < 1.
Q36. Montrer l'existence de nombres complexes 1 , 2 et 3 tels que :
0 < |1 |  |2 |  |3 | < 1

et

t  R,

A (t) = t(t - 1 )(t - 2 )(t - 3 ).

Q37. Montrer l'existence de nombres complexes µ, a, b et c tels que :
µ = 0,

1 < |a|  |b|  |c|

et

A (t) = µ(t - a)(t - b)(t - c).

t  R,

Partie V - Etude d'un dernier cas
Dans cette partie, on suppose que :
· l'automate passe du niveau 0 au niveau 1 en generant la lettre C ;
· l'automate passe du niveau 1 au niveau 2 en generant la lettre P ;
· l'automate passe du niveau 2 au niveau 3 en generant la lettre C ;
· si l'automate est au niveau 0 ou 2 et qu'il genere la lettre P, alors il 
retombe au niveau 0 ;
· si l'automate est au niveau 1 et qu'il genere la lettre C, alors il reste au 
niveau 1.
L'experience s'arrete des que l'automate a atteint le niveau 3, c'est-a-dire 
des que l'automate
aura genere la sequence CPC.
Q38. Reproduire, sur votre copie, la figure 3 suivante en la completant pour 
resumer l'experience
de cette partie V.

0

1

2

3

Figure 3
Pour i  [[0, 3]] et n  N , on note En,i l'evenement
l'automate se trouve au niveau i  et E0,i l'evenement
niveau i . On pose pn,i

apres avoir genere la n-ieme lettre,
l'automate se trouve initialement au
+

= P(En,i ) et pour tout t  [-1, 1], on definit Si (t) =
pn,i tn .
6/7

n=0

On note T l'instant ou, pour la premiere fois, l'automate atteint le niveau 3.
On admet que T est une variable aleatoire definie sur un espace probabilise (, 
A , P) telle que
T ()  N .
On remarque que la serie generatrice de T (notee GT ) est alors S3 et on note 
RT son rayon de
convergence. On rappelle que RT  1.
Q39. Determiner p0,0 , p0,1 , p0,2 et p0,3 .

pn,0

p
n,1
Q40. Montrer que pour tout n  N , on a :
p

n,2

pn,3

=
=
=
=

p · pn-1,0 + p · pn-1,2
q · pn-1,0 + q · pn-1,1
.
p · pn-1,1
q · pn-1,2

S0 (t)
S1 (t)

Soit t  [-1, 1]. On note S(t) la matrice colonne suivante : S(t) = 
S2 (t).
S3 (t)

S0 (t) = tp · S0 (t) + tp · S2 (t) +1

S1 (t) = tq · S0 (t) + tq · S1 (t)
.
Q41. Montrer que
S2 (t) = tp · S1 (t)

S3 (t) = tq · S2 (t)

Q42. Montrer que la matrice colonne S(t) est solution de l'equation (Et ) 
definie en partie IV.
Q43. Montrer que t  ] - RT , RT [, GT (t) =

pq 2 t3
et montrer que RT > 1.
-p2 qt3 + pqt2 - t + 1

Q44. Montrer que T admet une esperance et une variance.
Q45. Donner l'expression de E(T ) en fonction de q seulement.
Q46. Proposer une methode permettant de determiner le temps d'attente moyen de 
la premiere
realisation par l'automate de la sequence CCPPC : on precisera notamment le 
schema des six
niveaux correspondants et la matrice analogue a A que l'on peut faire 
intervenir dans ce probleme.

FIN

7/7

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



CCP Maths PC 2017 -- Corrigé
Ce corrigé est proposé par Thierry Limoges (ENS Cachan) ; il a été relu par Maël
Mevel (professeur agrégé) et Benjamin Monmege (enseignant-chercheur à 
l'université).

Comme dans un jeu de Pile ou Face, on génère aléatoirement une suite de lettres
qui peuvent être P ou C. Les tirages sont identiques et indépendants. Un mot 
écrit
avec les lettres P et C étant fixé, on cherche le temps au bout duquel il 
apparaîtra
dans la suite.
Le problème est modélisé par un automate probabiliste. Une variable aléatoire
compte le nombre de lettres générées jusqu'à ce que l'automate soit dans son 
état
final, qui correspond à la première apparition du mot voulu. On étudie la loi de
cette variable aléatoire à travers sa série génératrice, et on calcule 
notamment son
espérance.
· Dans la partie I, on étudie le cas où le mot voulu est simplement C. Cette 
partie
redémontre le cours sur la loi géométrique.
· La partie II est également élémentaire. Elle porte sur les séries 
géométriques et
leur produit de Cauchy.
· Dans la partie III, on étudie le temps d'attente pour obtenir deux C 
consécutifs. La méthode repose sur les probabilités conditionnelles et les 
fonctions
polynomiales de degré 2.
· La partie IV établit une méthode de calcul de la série génératrice du temps 
d'attente à partir de la matrice de transition de l'automate. On utilise le 
caractère
multilinéaire alterné du déterminant, en dimension 4, à travers des polynômes
caractéristiques.
· Dans la partie V, on applique la partie IV pour calculer le temps d'attente
de la séquence CPC. La dernière question propose d'étendre la méthode pour
calculer le temps d'attente de la séquence CCPPC. On s'amusera au passage
du fait que le choix inhabituel des lettres P et C au lieu des lettres P (pile)
et F (face) s'explique donc essentiellement par un clin d'oeil au concours CCP,
filière PC.
Ce sujet comporte la bagatelle de 46 questions réparties en 5 parties, mais sa
difficulté est modérée et sa longueur se révèle donc raisonnable. Peu de 
questions
nécessitent une prise d'initiative. Il illustre et éclaire les cours sur la loi 
géométrique
et les séries génératrices ; il peut être abordé dès que ces chapitres ont été 
étudiés.

Indications
Partie I
1 Décrire l'évènement (Y = n) à l'aide des Pk et Ck .
2 Reconnaître une série géométrique.
4 Rappeler pourquoi E(Y) = GY  (1) et E(Y(Y - 1)) = GY  (1) en écrivant les

2
sommes, puis en déduire V(Y) = GY  (1) + GY  (1) - GY  (1) .
Partie II

5 Appliquer la règle de D'Alembert.

1
1
8 Montrer que n+1 = o
.
n+ an+1
b
P
P
9 Si |un |  |vn |, alors
un z n et
vn z n ont même rayon de convergence.
n+

10 Donner explicitement un développement en série entière de f au voisinage de 
0,
invoquer l'unicité et étudier son rayon.
Partie III
14 Appliquer la formule des probabilités totales à P(Z = n) et au système 
complet
d'évènements de la question 13. Remarquer, en particulier, que
P(Z = n|P1 ) = P(Z = n - 1) = pn-1

18 Appliquer l'inégalité triangulaire à  et -p. Déterminer le signe de Q(t) 
entre
ses racines et utiliser la question 16.
19 Diviser par Q(t) au voisinage de 0 et invoquer l'unicité du développement en 
série
entière.
21 Montrer l'existence de GZ  (1) et GZ  (1).
Partie IV
25 Écrire la matrice A-tI4 et développer son déterminant, de préférence par 
rapport
à une colonne ou une ligne comportant beaucoup de 0.
27 Utiliser la multilinéarité du déterminant.
29 Montrer que I4 - tA est inversible pour t au voisinage de 0.
31 Utiliser la multilinéarité et le caractère alterné du déterminant.
32 Calculer explicitement detB (U1 , U2 , U3 , L).
34 Écrire que (x1 , x2 , x3 , x4 ) est un vecteur propre de t A pour la valeur 
propre .
35 Diviser par M une égalité bien choisie du système H pour chaque cas.
37 Utiliser la question 27.
Partie V
40 Pour tout k  [[ 0 ; 3 ]], étudier les états possibles au temps n - 1 pour se 
retrouver
à l'état k au temps n.
41 Revenir à la définition des Si (t) et utiliser la question 40.
43 Utiliser la question 32 en ayant préalablement vérifié ses hypothèses, puis 
la question 11.
45 Calculer GT  (1) et remplacer les « p » par « 1 - q ».

I. Étude d'un cas simple
1 Soit n  N . Par construction, l'évènement (Y = n) est
n-1
\
k=1

P k  Cn

C'est une intersection d'événements mutuellement indépendants, sa probabilité 
est
le produit
n-1

P(Y = n) =
Ainsi,

 P(Pk )P(Cn ) = pn-1 (1 - p) = (1 - q)n-1 q

k=1

La variable aléatoire Y suit une loi géométrique de paramètre q.

2 Soit t  R. Le terme général de la série

P

P(Y = n)tn est

(1 - q)n-1 qtn = qt((1 - q)t)n-1 = qt(pt)n-1
C'est le terme général d'une série géométrique de raison pt. D'une part, si |t| 
< 1/p,
on a |pt| < 1, et alors cette série converge. D'autre part, si |t| > 1/p, on a 
|pt| > 1, et
alors cette série diverge grossièrement. Le rayon de GY est donc 1/p, et RY = 
1/p > 1
car 0 < p < 1. Calculons sa somme. Soit t  ] -RY ; RY [. Alors
+

GY (t) =

P

+

qt(pt)n-1 = qt

n=1

P

(pt)n =

n=0

qt
1 - pt

La fonction génératrice GY admet pour rayon
RY = 1/p > 1 et pour tout t  ] -RY ; RY [,
GY (t) =

qt
1 - pt

3 Le rayon de la série entière GY est RY = 1/p > 1, ainsi GY est de classe C 
sur ] -1/p ; 1/p [. Cet intervalle ouvert contient 1, donc GY est deux fois 
dérivable
en 1. Pour tout t  ] -RY ; RY [,
GY  (t) =
et
D'où

q
q(1 - pt) - qt(-p)
=
2
(1 - pt)
(1 - pt)2
-2q(-p)
2pq
=
(1 - pt)3
(1 - pt)3

GY  (t) =
GY  (1) =

En conclusion,

q
1
=
2
(1 - p)
q

et

GY  (1) =

2pq
2p
= 2
3
(1 - p)
q

1
q

et

GY  (1) =

2p
q2

GY  (1) =
+

4 On a

E(Y) =

P

nP(Y = n)1n = GY  (1) =

n=1

1
q

+

De plus,

E(Y(Y - 1)) =

P

n(n - 1)P(Y = n)1n = GY  (1)

n=1

Par linéarité de l'espérance, il vient
V(Y) = E(Y2 ) - E(Y)2
= E(Y2 - Y) + E(Y) - E(Y)2
= E(Y(Y - 1)) + E(Y) - E(Y)2

2
= GY  (1) + GY  (1) - GY  (1)
2p 1
1
+ - 2
q2
q q
2p + q - 1
=
q2
p
V(Y) = 2
q
=

Finalement,

E(Y) =

1
q

et

V(Y) =

p
q2

II. Séries entières
5 Soit z  C . Comme a 6= 0, on peut calculer
n+1

n

un+1 (a)z n+1
|z|
|a|
|z|
= n+1 n =
un (a)z n
|a|
|a|
|z|
P
D'après la règle de D'Alembert, pour |z| < |a|, la série
un (a)z n converge, tandis
que pour |z| > |a|, elle diverge grossièrement. Son rayon est donc égal à |a|. 
Ainsi,
La série entière

P

un (a)z n a un rayon de convergence égal à |a|.

6 Soit z  C avec |z| < |a|. D'après la question 5, la série
Comme z/a 6= 1, on a
+

P

P

un (a)z n converge.

P -1  z n
-1 1
-1
1
=
z = a-z = z-a
a
a
a
n=0
1-
a
+

un (a)z n =

n=0

Pour tout z  C avec |z| < |a|, on a

+
P
1
=
un (a)z n .
z - a n=0

7 Soit n  N. Par définition,
vn =

n
P

k=0

uk (a)un-k (b) =

n -1
n
n
P
-1
1 P
1
1 P
= n+1
= n+1
k+1
n-k+1
k
-k
b
ab
ab
k=0 a
k=0 a b
k=0

 k
b
a