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