[PDF] Nombre détats visités par une marche aléatoire

View - Download Nombre détats visités par une marche aléatoire

Previous PDF

Next PDF

Nombre d"états visités par une marche aléatoire mots-clés: marche aléatoire, transience, séries génératrices.

Lamarche aléatoirede loi des pasµest la suite de vecteurs aléatoires(Xn)n∈Ndéfinie par

X

0= (0,...,0) ;∀n≥1, Xn=T1+T2+···+Tn,

où les pasTi≥1sont des vecteurs aléatoires indépendants et tous de loiµ: ∀x∈Zd,∀i≥1,P[Ti=x] =µ(x).

Par exemple, sid= 1etµ=12

δ1+12

δ-1, alors on retrouve avec(Xn)n∈Nla marche aléatoire simple symétrique sur l"ensemble des entiersZ. Pourn≥1, on pose C n= card({X1,X2,...,Xn}). (Cn)n≥1dansdiversessituations.Sid= 2etsiµ=14 ci-dessous :1 41
4 1 41
4

visite (bleu au tempsn= 0, et de plus en plus rouge jusqu"au tempsn= 1000). La courbe suivante représente alors

1

À première vue,(Cn)n∈Nsemble croître linéairement avecn(avec bien sûr des fluctuations aléatoires autour de ce

comportement moyen). Nous verrons plus loin que c"est bien le cas pour les marches aléatoires transientes, mais qu"il y a

une correction logarithmique à la croissance linéaire dans le cas de la marche bidimensionnelle présentée ci-dessus.

1 Taux de croissance linéaire

Dans cette section,detµsont arbitraires. On noteR+0= inf{n≥1|Xn= (0,...,0)}, avec par convention

R

+0= +∞si la marche aléatoire(Xn)n∈Nne repasse jamais par l"origine. Soitα=P[R+0= +∞]. L"origine0 = (0,...,0)

est un état transient si et seulement siα >0. Théorème 1(Kesten-Spitzer-Whitman).La suite(Cn)n≥1vérifie : C nn

Démonstration.Estimons les deux premiers moments deCn. La différenceCn+1-Cnvaut1siXn+1/∈ {X1,...,Xn},

et0sinon. On a donc pour toutn≥1: C n=nX i=11 (Xi/∈{X1,...,Xi-1})=nX i=11 (Xi-X1̸=0,...,Xi-Xi-1̸=0).

En prenant les espérances, on obtient :

E Cnn =1n n X i=1P[Ti+···+T2̸= 0,...,Ti+Ti-1̸= 0, Ti̸= 0] =1n n X i=1P[X1̸= 0, X2̸= 0,...,Xi-1̸= 0].

L"espérance de

Cnn est donc la moyenne de Cesàro d"une suite tendant versα, etE[Cnn ]→n→∞α. Pour le second moment, on développe le carré deCn: (Cn)2=X (Xi/∈{X1,...,Xi-1})1(Xj/∈{X1,...,Xj-1})= 2X (Xi/∈{X1,...,Xi-1}, Xj/∈{X1,...,Xj-1})+Cn.

L"espérance de chaque variable de Bernoulli dans la somme ci-dessus peut être majorée comme suit :

P[Xi/∈ {X1,...,Xi-1}, Xj/∈ {X1,...,Xj-1}]

avecαi=P[X1̸= 0, X2̸= 0,...,Xi-1̸= 0]. Commeαi→αetαj-i→αlorsqueietj-itendent vers l"infini,

E[(Cnn

)2]est majoré parE[Cn]n

2=O(n-1)plus une moyenne de Cesàro de termes proches deα2. Ainsi,

E Cnn 2# En retranchant le carré de l"espérance, on obtient doncvar(Cnn ) =o(1), et l"inégalité de Bienaymé-Chebyshev donne maintenant P C nn -ECnn

2→n→∞0

pour toutε >0. On conclut en utilisant le fait queE[Cnn

]→n→∞α.Considérons par exemple la marche aléatoire surZ3dont la loi des pas est uniforme sur les six directions(±1,0,0),

(0,±1,0)et(0,0,±1). Cette marche est transiente, avec un coefficientαpour lequel il existe une formule exacte(obtenue

notamment par Montroll en 1964) :

α=(2π)33

R (-π,π)3dθ dϕdψ3-cosθ-cosϕ-cosψ≃0.6595...(2) 2

020040060080010000200400600

2 Récurrence de la marche bidimensionnelle

D"après ce qui précède, si l"origine est un état récurrent, alors Cnn tend vers0, et le nombre d"états visités croît sous-

linéairement. Pour étudier plus précisément le comportement deCndans ce cas, on a besoin de savoir à quelle vitesse

P[R+0> n]tend vers0.

Proposition 2.Pour la marche aléatoire bidimensionnelle standard,

P[X2n= (0,0)] =1πn

+O1n 2

Démonstration.La parité de la somme de l"abscisse et l"ordonnée change à chaque pas de la marche bidimensionnelle, ce

qui explique pourquoi on ne calcule que la probabilité d"un retour en0à un temps pair2n. Cette probabilité est14

2nfois

le nombre de chemins de longueur2nreliant(0,0)à(0,0). Un tel chemin est constitué den1pas vers le haut,n1pas vers

le bas,n2pas vers la droite etn2pas vers la gauche avecn1+n2=n. On a donc :

P[X2n= (0,0)] =14

2nX n

1+n2=n(2n)!(n1!)2(n2!)2=14

2n 2n n X n

1+n2=n

n n 1 n n 2 L"identité de Vandermonde assure que la somme des produits de coefficients binomiaux vaut 2n n, donc

P[X2n= (0,0)] =14

2n 2n n 2 .(3) L"estimée se déduit maintenant immédiatement de la formule de Stirlingn! = (ne

l"estimée implique que la marche aléatoire bidimensionnelle standard est récurrente : en effet,P∞

n=0P[Xn= (0,0)] =

+∞.On se concentre dans ce qui suit sur la marche aléatoire bidimensionnelle. PosonsG1(z) =P∞

n=0P[X2n= (0,0)]zn.

C"est une série entière de rayon de convergence1, et lorsquezs"approche de1en restant dans le disque unité,

G

1(z) = 1 +1π

X n=1z nn +O ∞X n=1|z|nn 2! =-1π log(1-z) +O(1) car la série

P∞

n=11n

2est convergente. Posons ensuiteG2(z) =P∞

n=1P[R+0= 2n]zn. On introduit plus généralement le temps dek-ième retour R (k)

0= inf{n > R(k-1)

0|Xn= (0,0)},

3

étant entendu queR(k)

0= +∞s"il y a moins dekretours en l"origine. La propriété de Markov forte permet de montrer

par récurrence surk≥1l"identité suivante : ∀k≥1, G2,k(z) =∞X n=1P[R(k)

0= 2n]zn= (G2(z))k.(4)

Proposition 3.Pour toutznombre complexe de module plus petit que1,G1(z) =11-G2(z). Démonstration.SiX2n= (0,0), alors2nest l"un des temps de retour en0. On a donc : G

1(z) = 1 +∞X

n=1P[X2n= (0,0)]zn= 1 +∞X k=1 ∞X n=1P[R(k)

0= 2n]zn!

= 1 +∞X k=1(G2,k(z)), et l"équation ( 4

)per metde conclur e.En particulier, puisqueG1(z)tend vers l"infini lorsqueztend vers1,G2(z)doit tendre vers1et ceci implique que

P[R+0<+∞] =G2(1) = 1; la marche aléatoire bidimensionnelle est donc récurrente. Par le Théorème1 , on a donc

dans ce contexte la convergence en probabilité Cnn →0. Considérons finalementG3(z) =P∞ n=0P[R+0>2n]zn. Comme

P[R+0>2n] =P

k>nP[R+0= 2k], une interversion de sommes donne la relation G

3(z) =G2(z)-1z-1=1(1-z)G1(z).(5)

Ceci implique qu"au voisinage dez= 1, la série entièreG3(z)s"écrit G

3(z)∼z→1-π(1-z)log(1-z).

Dans ce contexte, on peut utiliser le :

Théorème 4(Hardy-Littlewood, 1914).SoitG(z) =P∞ n=0anznune série entière à coefficients positifs et décroissants, de

rayon de convergence1, avecG(z)≃ -11-z1log(1-z)lorsqueztend vers1par valeurs inférieures. Alors,an≃n→+∞1logn.

Nous admettrons ce résultat asymptotique, qui est un cas particulier de la théorie de transfert des singularités des séries

entières en des comportements asymptotiques de leurs coefficients. Ceci implique l"estimée n=P[R+0≥n]≃πlogn lorsquentend vers l"infini.

3 Croissance sous-linéaire du nombre d"états pour la marche bidimensionnelle

L"estimée fineP[R+0≥n]≃πlognpermet de préciser le comportement asymptotique de(Cn)n∈Npour la marche

aléatoire bidimensionnelle : (logn)Cnn

Démonstration.On reprend les mêmes arguments que dans la preuve du Théorème1 . L"espérance deCns"écrit

E[Cn] =nX

i=1P[X1̸= 0, X2̸= 0,...,Xi-1̸= 0] =nX i=1α i, elle est donc équivalente àπnlogn. Puis, iαj-i+E[Cn].

La somme double est équivalente à(πnlogn)2, donc la variance deCnest uno(nlogn)2. L"inégalité de Bienaymé-Chebyshev

permet de conclure.4

Questions

1.

et avec les pas choisis uniformément parmi les2,4,6ou8directions±eipossibles,eidésignant lei-ième vecteur

de la base canonique. Dans toutes les questions qui suivent, les marches aléatoires considérées sur ces réseaux auront

cette distribution de pas (marche aléatoirestandard). 2.

Donner des es timationsdu par amètreαlorsqued= 3ou4. Pourd= 3, comparer avec la formule (2).Lor sque

3. Lor squed= 1, on noteMn= max({X1,...,Xn})etmn= min({X1,...,Xn}). Quelle est la relation entreCn, M netmn? Montrer que pour toutb∈N, 4.

On suppose t oujoursd= 1. Soitbetadeux entiers, avecb≥0. Établir par un décompte de chemins l"identité

P[Mn≥betXn=a] =(

P[Xn=a]sia≥b,

P[Xn= 2b-a]sia < b.

Sia < b, on pourra associer à tout cheminC= (0 =x0,x1,...,xm,...,xn=a)qui atteint ou dépassebavant le

tempsnet qui s"arrête enale cheminC′= (0 =x0,x1,...,xm,2b-xm+1,...,2b-xn= 2b-a)qui commence

niveaub. Faire un dessin de cette transformation, et identifier les ensembles de chemins qu"elle met en bijection.

Déduire de ce qui précède queP[Mn≥b] =P[Xn≥b] +P[Xn≥b+ 1], puis que la suite de variables aléatoires

)n≥1esttendue: lim

L→+∞

sup ≥L = 0. 5.

On adme tq ue

admet une loi limite lorsqued= 1etntend vers l"infini; la question précédente est un premier pas vers ce résultat. Illustrer cette loi limite par des programmes. 6.

Démontr ercom plétementl"es timée(

1 ).On demande en par ticulierde pr éciserl"ar gumentde somme de Cesàr o,

qui est utilisé avec une somme double sur des indicesietj(indication : on pourra mettre de côté dans la somme les

indicesietjtels queiouj-iest trop petit). 7.

La pr euvede la Pr oposition

2 r eposeen par ticuliersur l"identit éde V andermonde l X k=0 n k m l-k =n+m l

valable pour tous entiersn,m,l≥0(dans le texte, on utilise le cas particuliern=m). Donner une preuve de cette

identité. 8.

Si (X(1)n)n∈Net(X(2)n)n∈Ndésignent respectivement les marches aléatoires standards en dimensionsd= 1etd= 2,

alors l"équation ( 3 )se r éécrit:

P[X(2)

2n= (0,0)] =

P[X(1)

2n= 0]

2. (indication : tourner la tête de 45 degrés). 9.

Démontr erles identit és(

4 )e t( 5 )( pourla seconde identit é,on pour rautiliser le r ésultatde la Pr oposition 3 10. en dimensiond= 1, qui est une loi sur R +. Proposer des programmes qui illustrent le fait suivant : pour toute loi de pasµsurZtelle queP k∈Zµ(k)k= 0 etP k∈Zµ(k)k2= 1(donc, pas forcément avecµ=12

δ1+12

5quotesdbs_dbs47.pdfusesText_47

[PDF] Marche de la Banane Economie

[PDF] marché des télécoms d'entreprise

[PDF] Marché et Prix

[PDF] Marche et prix SES 2nde Cned

[PDF] Marché et prix SES 2nde Cned Exercice 1 et 4

[PDF] marché et prix ses seconde

[PDF] marché et prix ses seconde exercices

[PDF] marché générique

[PDF] marché imparfaitement concurrentiel définition

[PDF] marche martin luther king selma

[PDF] marché mondial de la banane

[PDF] marché mondial du cacao

[PDF] marché non concurrentiel définition

[PDF] marché non concurrentiel exemple

[PDF] marché public appel d'offre