[PDF] Mines 2017 - PSI1 Marche aléatoire dans un labyrinthe : un corrigé

View - Download Mines 2017 - PSI1 Marche aléatoire dans un labyrinthe : un corrigé

Previous PDF

Next PDF

Mines 2017 - PSI1

Marche aleatoire dans un labyrinthe : un corrige

1 Premiers pas

1. (Sk=i)1i5est un systeme complet d'evenements. La formule des probabilites totales donne

8k2N;P(Sk+1= 1) =5X

i=1P(Sk+1= 1jSk=i)P(Sk=i) Il reste a remarquer que les salles 2;3;4;5 menent toutes a 1 avec probabilite13 pour en deduire8k2N;P(Sk+1= 1) =13 5 P i=2P(Sk=i)2. On peut proceder de m^eme pour expliciterP(Sk+1=j) pourj= 2;3;4;5 et obtenit

P(Sk+1= 2) =14

P(Sk= 1) +13

P(Sk= 3) +13

P(Sk= 5)

P(Sk+1= 3) =14

P(Sk= 1) +13

P(Sk= 2) +13

P(Sk= 4)

P(Sk+1= 4) =14

P(Sk= 1) +13

P(Sk= 3) +13

P(Sk= 5)

P(Sk+1= 5) =14

P(Sk= 1) +13

P(Sk= 2) +13

P(Sk= 4)

Ce qui se traduit matriciellement par8k2N; Xk+1=BXkavecB=0 B BBB@0 13 13 13 13 14 013 013 14 13 013 0 14 013 013 14 13 013 01 C CCCA3. La somme des elements de chaque colonne deB, et donc de chaque ligne detB, vaut 1. Ceci signie que t B0 B BBB@1 1 1 1 11 C

CCCA=0

B BBB@1 1 1 1 11 C CCCA ou encore que12Sp(tB) et0 B BBB@1 1 1 1 11 C CCCA2ker(tBI5)4. Un calcul immediat donneBX0=X0et, par recurrence immediate,Xk=BkX0=X0pour tout entierk.Xkdonnant la loi deSk, 1

toutes lesSkont m^eme loi dans ce cas5. Si le rat est dans une piece, il la quitte au temps suivant. Ainsi,P(S0= 1\S1= 1) = 0. Or

P(S0= 1)P(S1= 1) =116

6= 0. AinsiS

0etS1ne sont pas independantes2 Convergence dansMn(R)

6. Soitx2ker(uIE). On au(x) =xet par recurrence immediate,uk(x) =xpour toutk. Ainsi,

r

k(x) =xet8x2ker(uIE),rk(x)!x7. Soitx2Im(uIE). Il existeytel quex= (uIE)(y) et doncx=u(y)y. Ainsiul(x) =

u l+1(x)ul(x) et (telescopage) r k(x) =1k k1X l=0(ul+1(x)ul(x)) =1k (uk(x)x)

On en deduit quekrk(x)k 1k

(kuk(x)k+kxk). Or,ucontractant les normes,kuk(x)k kxket

donc notre majorant est de limite nulle. Ceci montre que8x2Im(uIE),rk(x)!0E8. Par theoreme du rang, on a les bonnes dimensions. De plus, six2Im(uIE)\ker(uIE),

(rk(x)) est simultanement de limitexet 0Eet doncx= 0Epar unicite de la limite. L'intersection est donc reduite a 0

Eet la somme est directe. FinalementE= ker(uIE)Im(uIE)9. Soitx2E. Il existey2ker(uIE) etz2Im(uIE) tels quex=y+z. On a alors

r

k(x) =rk(y) +rk(z)!y.x7!yest la projection sur ker(uIE) de direction Im(uIE).8x2E,rk(x)!p(x) avecpprojection sur ker(uIE) de direction Im(uIE)10. Pour parler de convergence dansMn(R), on doit munir cet espace d'une norme. Et comme

l'espace est de dimension nie, le choix de la norme est indierent (les normes sont equivalentes en dimension nie). Les m^emes calculs que ceux menes ci-dessus montrent que

8X2Rn; RkX!PX

ouPest la matrice (dans la base canonique) de la projection sur ker(AIn) de direction Im(AIn) (espaces supplementaires dansRn). Appliquons ceci aux elementsEide la base canonique deRn:8i;kRkEiPEik !0. Comme tous les normes sont equivalentes surRn, on peut choisir de travailler avec la norme innie associee a la base canonique.kRkEiPEik !0 signie alors que chaque suite des coecients deRkEiconverge vers le coecient associe dePEi. Ceci signie donc que chaque suite coecient deRkconverge vers le coecient dePassocie. Ou encore queRk!Pau sens de la norme \maximum du module des coecients". On a donc convergence de (Rk) versP. Enn,Pest la matrice d'une projection etP2=P.9P= Rk!PetP2=P2

3 Matrices stochastiques

11. PosonsV=AU. On a

8i; Vi=nX

j=1a i;jUj=nX j=1a i;j

On en deduit que(4) equivaut aAU=U12. SoientA;Bstochastiques. Par les formules de produit,C=ABest a coecients positifs (chaque

c i;jest somme et produit de termes0). En outreCU=ABU=AU=Uavec la question

precedente. Cette m^eme question indique queCverie (4) et est donc stochastique.Eest stable par multiplication13. Soit (Ak) une suite convergente de matrices stochastiques etAsa limite. Chaque coecient de

Aest limite de la suite correspondante des coecients deAket est positif comme limite de tels

termes. De plus,8k; AkU=UdonneAU=U. AinsiAest stochastique.Eest fermeSoientA;Bstochastiques et2[0;1]. PosonsM=A+(1)B. La positivite des coecients de

AetBentra^ne celle des coecients deM. De plusMU=AU+(1)BU=U+(1)U=U ce qui donne (4) pourMqui est donc stochastique.Eest convexe14. PosonsY=AX= (yi)1in. On a

8i;jyij=

n X j=1a i;jxj nX j=1jai;jj jxjj kxk1n X j=1a i;j=kxk1

Ceci etant vrai pour touti, on akAXk1 kXk1pour toutX2Rn15. NotonsB=Ap= (bi;j).Best une matrice stochastique (question 12) a coecients>0. Soit

X2ker(BIn) etsun indice tel quexsest le maximum desxi. On aBX=Xet, en regardant le coecient d'indicesde cet element deRn, x s=nX j=1b i;jxjxsn X j=1b i;j=xs (on a utilise la positivite desbi;jpour dire quebi;jxjbi;jxs). Si, par l'absurde, il existait unj tel quexj< xsalors, commebi;j>0, on auraitbi;jxj< bi;jxset on obtiendrait ci-dessusxs< xs et donc une contradiction. Ceci montre que lesxjsont tous egaus et donc queX2Vect(U). Ainsi ker(ApIn)Vect(U). MaisApest une matrice stochastique (question 12) et on a donc

U2ker(AIp). Ainsiker(ApIn) = Vect(U) et donc dim(ker(ApIn)) = 116. On sait deja que Vect(U)ker(AIn) carAest stochastique. SiAX=Xalors par recurrence

A kX=Xpour toutket en particulierApX=X. la question precedente montre queX2

Vect(U) et ainsi

3

ker(AIn) = Vect(U)17. LesAlsont toutes stochastiques (question 12).Rkest donc a coecients positifs comme somme

de telles matrices. De plus R kU=1k k1X l=0A lU=1k k1X l=0U=U et on a aussi (4). FinalementR

kest stochastique pour toutkOn aurait aussi pu utiliser la convexite deEpuisqueEest isobarycentre de matrices stochastiques.

18. Les questions 10 et 14 montrent que (Rk) est convergente de limitePtelle queP2=P. De

plus, les questions 17 et 13 (caractere ferme) montrent quePest stochastique. La partie2a montre quePest la matrice de la projection sur ker(AIn) de direction Im(AIn). On a donc

Im(P) = Vect(U) etPest de rang 1.R

k!P,P2 E, Im(P) = Vect(U)19. Toutes les colonnes dePsont ainsi multiples dePet il existeitelle que la colonneis'ecriveiU.

En posantL= (1;:::;n) (matrice ligne) on a alorsP=UL. Comme toutes les coordonnees

deUvalent 1, toutes les lignes dePvalentL. CommePest stochastique,Ll'est aussi.P=ULavecLmatrice ligne stochastique20. Remarquons que

R kA=1k k X l=1A l=1k ((k+ 1)Rk+1In) =k+ 1k

Rk+11k

In

En faisant tendrekvers +1, on obtientPA=POn aurait aussi pu dire queIm(AIn) = ker(P)et que doncP(AIn) = 0.

Pest une matrice dont toutes les lignes sont egale aL.PAest ainsi une matrice dont toutes les lignes sontLA. L'egalitePA=Pdonne ainsiLA=L. SiYest une matrice ligne,Y A=As'ecrit aussitAtY=tYou encore (tAIn)tY= 0. Or, avec la question 16,AInest de rangn1 (par theoreme du rang) et il en est de m^eme detAIn. Le noyau de tAInest ainsi de dimension 1. Il contient la matricetLqui est non nulle (car sinon P= 0). Ainsi, les matrices ligneYveriantY A=Asont les multiples deL. La somme des

coecients deLne valant 1 que si= 1, on a nalementLest la seule ligne stochastique telle queLA=L21. On montre par recurrence simple queLAk=Lpour toutk. En particulier,LAp=L. Si, par

l'absurde, on avaiti= 0 alors en regardant lei-eme coecient deLAp=L, on aurait 0 = nX j=1 j(Ap)j;i Les (Ap)j;ietant>0 et lesjpositifs non tous nuls, ceci est impossible. On a montre que 4

Lest a coecients strictement positifs22. On sait que ker(AIn)Im(AIn) =Rn. Les espacesF= ker(AIn) etG= Im(AIn) sont

stables par l'endomorphisme canoniquement associe aA. En notantuF2 L(F) etuG2 L(G) les endomorphismes induits, commeFG=Rn, u=uFuG Fest de dimension 1 etuF= IdFdoncuF= (X1). CommeF\G=f0g,uGIdGest inversible et 1 n'est pas racine deuG. De tout cela, on deduit que 1 est racine simple deu, c'est a dire1 est valeur propre simple deA4 Application au labyrinthe

23. On aP=ULouLest l'unique ligne stochastique telle queLA=L, c'est a dire outLa des

coecients positifs de somme 1 et verie tAtL=tL, c'est a dire outLest vecteur propre deB associe a la valeur propre 1. (4;3;3;3;3) est un tel vecteur propre et doncL=116 (4;3;3;3;3).

Finalement,P=116

0 B

BBB@4 3 3 3 3

4 3 3 3 3

4 3 3 3 3

4 3 3 3 3

4 3 3 3 31

C CCCA24. Supposons queS0suive une loi convenable. On a alorsS0=BS0et, par recurrence,S0= B kS0. En transposant, combinant et passant a la limite, on obtienttS0A=tS0. CommetS0est stochastique, la question 20 montre que tS0=Ltrouve ci-dessus. La reciproque a ete traitee en question 4.Le seul cas ou lesSkont la m^eme loi est donnee par0 B

BBB@1=4

3=16 3=16 3=16 3=161 C CCCA5quotesdbs_dbs47.pdfusesText_47

[PDF] maths : les équations des droites

[PDF] Maths : Les fonctions

[PDF] Maths : Les pourcentages

[PDF] Maths : Les probabilités

[PDF] maths : les suites geometriques

[PDF] Maths : les vecteurs

[PDF] maths : limite et continuité

[PDF] maths : limite infinie

[PDF] Maths : polynomes du second degré

[PDF] Maths : Pourcentage*

[PDF] Maths : Probabilité 2nd ( Besoin d'une simple correction ;) )

[PDF] Maths : Problèmes de fractions

[PDF] Maths : Quelle fraction de cette année representent tous les dimanches

[PDF] Maths : Résolution Algébrique

[PDF] Maths : S'il vous plaît !