[PDF] Structures et algorithmes aléatoires

View - Download Structures et algorithmes aléatoires

Previous PDF

Next PDF

Structuresetal}orithmes aléatoires

Notesdébut2013 ω

AnneBouillard,anne.bouillard@ens.fr

Ons"intéresedans cecoursà desprobabilitésdiscrètes, iedansdes espacesauplus dénombrables.

Applicationsàl"informatique :

réseauxdecommunication étudedela distributiondeprobabilité desentréesd"un algo

Référencesbibliographiques:

MitzenmackeretUrfalprobabilityandcomputing:randomize dalgorithmsand probabi- litisticanalysis(2005) PierreBrémaudinitiaionauxpr obabilités(2009) PierreBrémaudmarkovchains,gibbs τelds,monteca rlosimulationand queues(1999)

2013-09-27

Algorithmedéterministe:lasor tiedé penduniquementde l"entrée(onauneapplication

I7!ALGOf(I)).

Algorithmeprob abiliste:lasortie dépendégalementd"un certainnombrede bitsaléatoiresr,ona alorsunefonction dutypeI;r7!f(I;r).

Ilya deuxtypesd"algorithmes aléatoires:

Onaune réponsepresquetoujours correcte,enun tempsraisonnablela plupartdutemps. Onaune réponsetoujoursrapide, correctelaplupart dutemps.

Deuxexemples.

Vériτcationdel'égalitéde deuxpolynomes. Pourunalgorithme déterministe:développer lespolynomeset comparerlescoefficients ; complexitéO(d2)pourledéveloppement (avecune méthodenaive). Algorithmeprobabiliste: soitr2f1;:::;100dg,évaluer F(r)etG(r),SiF(r)=/G(r)onsait quelespolynomes sontdifférents.Sinon, onprétendqu"ils sontégaux.La probabilitéd"une erreurestfacilement calculable,c"est1/100(puisquel"égalitésur dpointsimpliqueleur égalitépartout,pour deuxpolynomesdistincts ilya moinsdedpointsd"égalité).

Canaldeco mmunication.

Onades entréesquisont misesdansune file,enattente d"etretraitéespour produireune sortie.Onnote X(n)lenombrede clientsdansla filejusteaprès ledépartdu n-èmeclient. Onnotea?lenombrede clientsarrivant pendantleservice dun-èmeclient.

X(0)=0

X(n+1)=max(X(n)¡1;0)+a?

1 (X(n??n2Nestunprocessusstochastique.Souscertaines hypothèses,c"estune chaînede

Markov.

1I.Évènements etprobabilités

Ex.Lancéd"undé.

Obtenir3 :évènement deprobabilité∞/6. Obtenirun chiffrepair :évènementde probabilité∞/?. Ex.Onsedonne uncercleet ontireune cordeauhasard. Quelleestla probabilitéquecette corde

soitpluslongue quelecôté d"untriangleéquilatéral inscritdansce cercle?C"est ∞/3,eneffet on

fixelepremier point,ontrace letriangleéquilatéral passantparce pointeton constatedirectement quepourle secondpoint,la cordeseraplus longueseulements"il estdansl"arc opposéaupremier point.

1.1a.Tribus etévénements

décrittoutesles possibilitésd"uneexpérience. ( =f∞,?,3,4,5,6gpourundé).

Lesélémentsde

,ω,sontles épreuvesoules réalisations.

Onappelleévénement unsous-ensemblede

.Parexemple, onpeutdéfinir f?,4,6gl"évènement obtenirun chiffrepair.

Déf.Unetribusur

estunnefamille desous-ensemblesde ,F,telleque 2F

SiA2F,alors

nA2F

Si(An?n2N2FN,alorsS

n2NAn2F.

Tribugrossière:f?,

g.Tribu fine:P( Danslaplupart descas,on travaillerasur latribufine. Prop.Lestribussont stableparintersection dénombrable(complémentaire,toussa)

1.2b.Espacede probabilités,axiomedes probabilités

Déf.Soit

unespaced"épreuves etFunetribusur .Uneprobabilité sur( ,F?estunefonction P:

7!?0,∞]telleque:

P( Si(An?n2Nestunesuite d"événementsdeFdeuxàdeux disjoints,alorsP¡S n2NAn=P n2NP(An?. SiP(A?=∞alorsAestpresquesûr. SiP(A?=0alorsAestpresqueimpossible. Ex. =f0,∞gN,ω=ω?ωn,avec ωi2f0,∞g.

A=fωjωi2Ai,i6kgavecAif0,∞g.

Lesévénementsde typeAnesontpas stablesparunion dénombrable. 2

Notes?0∞4.2014-09-24.

Biblio}ra⎷hie:voirpageweb ducours.Première partieducours bienbaséesur Probabilityand Computing.Randomize dAlgorithmsandProbabilisticAnalysis. :espacedes épreuvesoudes réalisations. Théorème.Continuitéséquentiel le.(calculdelimitesdepr obabilités) Soient(An)n2N2Fnunesuited"évenements telsque8n,AnAn+∞,alors: P n2NA n! =limn!1P(An) Remarque.Mutuelleindépendance=/indépendance2à 2(c'estplus fort!) Théorème.Soit(An)n2Nunefamilled"évenements mutuellementindép endats,alors(Bn)n2N aussi,où8n,Bn=AnouAnc. Théorème.Soit(Cn)2FNunefamilledénombr abled"évenementsmutuel lementindépendants.

AlorsP¡T

n2NCn=Q n2NP(Cn).

Démonstration.PoserBn=T

k=?nCk;c"estune suitedécro issante.Onutilise lacontinuité séquentielle.(lasuiteQ k6nP(Ck)convergecardécro issantepositive;c"estune hypothèsede l"énoncéduthéorème).

P(AjB)=P(A)

P(B)P(BjA)

2014-10-01

Fo\ctio\sdeVA.Unefonctionde VAest uneVA. SiX:

!Eetf:E!F,alorsf(X): !F estunenouvelle VA(il fautvérierque sespréimagessontbienmesurables,ce quiestclair parles propriétésdesensembles quisontici auplusdénombrables).

Exem⎷lesdelois aléatoires.

Loidebernoulli :XBer(p)siP(X=1)=p=1¡P(X=0)

SiAestunévènement (A2F),alors1ABer(P(A))

Loibinomiale: XBin(n,p)siP(X=k)=n

k p k(1¡p)n¡k X=P i=∞nXi,oùXiBer(p)sontdesv aiid. Loigéométrique: XGeo(p)siP(X=n)=(1¡p)n¡∞ppourtoutn2N (probabilitéquele premierfaceintervienne aun elancer; Laloigéométrique estsansmémoire, ie8k>0,8n>1,P(X=n+kjX>k )=P(X=n). 3 •Loiuniformesur [0;1](cen?estpas uneloidiscrèteω) ?x?[0;1];P(X?x)=x.

•LoidePoisson deparamètre-.P(X=k)=k

k!e¡

Espérance.(voirpoly).Linéarité del?espérance. requiertl?espéranceτnie desdeuxfonctions.

Espéranceconditionnelle.SoitXuneVA etAunévènement,

E[X|A]=?

x2ExP(X=x|A)

Lemme.SoientX;YdesVA tellesqueE[X]existe.

E[X]=?

y2EP(Y=y)·E[X|Y=y]

Exemplesd"espérances.

•X≂Ber(p),E[X]=p

•X≂Bin(n;p),E[X]=np

•X≂Geo(p),E[X]=p?

i=11i(1-p)i¡1=1 pProposition.SiXestuneV Aréelle àvaleursentières,alors:

E[X]=?

i>1P(X?i)

Variance.SoitX;YdesVA réelles.Ondéτnit.

•Lek-èmemomentde X.E[Xk]

•Lavariance deX.V(X)=E[(X-E[X])2]=E[X2]-E[X]2

•Lacovariance deXetY.Cov(X;Y)=E[(X-E[X])·(Y-E[Y])] •L?écartλtype.ff(X)=V(X)?Prop.SiXetYsontindépendantes,alors E[XY]=E[X]E[Y].

Exemples.

•Var(Ber(p))=p-p2

•Var(Bin(n;p))=np(1-p)

•Var(Geo(p))secalculeen isolantlecas oùona lerésultatdès lapremièretentative, eten utilisantlapropriété desansmémoire.

2014-10-08.

Surlesgénératrices, rappel.P(X=n)=gX(n)(0)

n!.(vuen prépa) 4

Exem⎷lesde}é\ératrices.

XBer(p):gX(s)=(1¡p)+sp

XBin(n;p):gX(s)=((1¡p)+sp)n

XGeo(p):gX(s)=P

n>1sn(1¡p)n¡1p=spP n>0s(1¡p)n=ps

1¡(1¡p)s.

Plusgénéralement,E[Xk]peuts"écrireen fonctiondegX0(1);:::;gX(k)(1). Lie\e\tre{o\ctio\ }é\ératriceetdistributio\. SoientXetYdeuxV.A.de fontionsgéné- Bor\edeCher\o da\sl?autrese\s. SoientX1;:::;X ndesVA indépendantes,XiBer(pi) avecX=PXi,=E[X].Alors8S2]0;1[,: 1.

P(X6(1¡))6e¡

(1¡)1¡ 2.

P(X6(1¡))6e-2

2A⎷⎷licatio\autri ra⎷ide.Commentévaluer laprobabilitéqueletris"effectue ennlogn?

Onmontreque cetteprobaest ?1¡1

n.Ondécrit uneexécutiondu tricommeun arbreoùchaque noeudcorrespondau choixd"unpivot, etadeux sous-arbresquicorrespond auxsous-triseffectués. Siunnoeud estuntri surséléments,alorsun desesfils estdit" bonnoeud»siil doittrierau pluss/2éléments.Ons"intéresse auxlongueursdes branchesdel"arbres. Soitbunebranche,alors :

1.Ilexisteau pluslognbonnoeudssur bavec=1

log2?1;5 Eneffet,supposons qu"ilyait kbonsnoeudssur labranche,alors 16¡1 2kn.

2.P(jbj?logn)61

n

2SoitXiBer(pi)laprobabilitéque lei-èmenoeudde labranchesoit unbonnoeud. On

poseYiBer¡1

2,telleque Xi?Yip.s.etque lesYisoientmutuellementindépendantes.

P(jbj?m)6P(P

i=1mXi6logn)6P(P i=1mYi6logn) Onappliquela bornedeChernoff...safédégrocalcul

3.P(maxbjbj?logn)61

n4.P(QS(T)?logn)61 nA⎷⎷licatio\:estimatio\ d?u\⎷aramètre. p:intensitéd"une mutation(inconnue) n:populationtestée (échantillonsmutuellementindépendants).

Question:év aluerp.

5 O\⎷oseXle\ombrede mutatio\ssurla ⎷o⎷ulatio\.X=p˜n.

Déf.U\i\tervalle deco\a\cede(1¡γ)⎷ouru\⎷aramètre pestu\i\terv alle[p˜¡δ,p˜+δ]tel

queP(p2[p˜¡δ,p˜+δ])>1¡γ.O\veut δetγles⎷lus⎷etits ⎷ossibles.

XBi\(n,p).E[X]=np?etX=np˜

Deuxcas⎷our p2/[p˜¡δ,p˜+δ]:

1+ p p>p˜+δetX=np˜P(x2/[p˜¡δ,p˜+δ])=P Xn p 1+ p

6....(bor\edeCher\o?.

2014-10-15.

Limitedela loibinomiale.

k!.Ladistributio\ limiteest laloide Poisso\:XPoi(λ)siP(X=k)=e¡k k!8k2N.

Preuve:Soit gnlasérie}é\ératrice deXn:gn(s)=(1¡p(s)(1¡s))n.Si(gn)co\ver}esim⎷leme\t

versgu\esérie}é\ératrice ⎷ouru\i\terv alle[0,r]avecr>0?alorsla distributio\deXnte\d versladistributio\ pdé\ie⎷arg. Icio\vérie bie\quegn(s)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!n!1e¡(1¡s)=e¡P k2N(s)k k!?quiest u\esérie}é\ératrice ⎷our

XtellequeP(X=k)=e¡k

k!?c?est-à-direXPoi(λ). Propriétésdela loidePoiss on.O\sedo\\e XPoi(λ). gX(s)=e¡(1¡s)

E[X)=gX0(1)=λ

Lemme.Soie\tX1Poi(λ1)etX2Poi(λ2)?alorsX1+X2Poi(λ1+λ2).(ilsut dere}arder les{o\ctio\s}é\ératrices?

Modèlepossonienet modèleréel: corrolaire.Siu\évè\eme\t au\e⎷robabilité au⎷lusp

da\slemodèle ⎷oisso\ie\?alorsil au\e⎷robabilité au⎷lusempda\slemodèle réel.

Puissancededeux choix.O\anballesetnur\es.Pourchaque balleo\tire auhasard

u\i{orméme\tdur\eseto\ ⎷lacelabale da\sl?u\e?la moi\s⎷lei\e.A⎷rès aectatio\desnballes

(da\snur\es??la char}emaximaled?u\e ur\eestau ⎷lusln(lnn) nΔ.

Preuve:

Propriété.m2N,q61.O\a P(Bi\(m,q)>2mq)6e¡mq/3.(bor\ede Cher\o?avec δ=1?.

E\suite?o\⎷ose :

Bi=\ombred?ur\es dechar}eau moi\si

(βi)i>4dé\ie⎷arβ4=n

4etβi+1=2id

n d?1pi=id n d6

•Ei=00Bi6i

•i=minn

i?N|pi<6lnn no

Lemme.i=ln(lnn)

lnd+O(1) ??∞4-∞?-?? Laméth?de?r?babiliste. But:prouver l'existenced'objets satisfaisantunepropriété P. )rgume?tdec?m?tage. Onaune collectiond'objets (auplusdénombrable) (ai)i2IetPune propriété,onveut montrerqu'ilexiste unitelqueP(ai).Idée: déτnirXuneva surles(ai),et montrerqueP(XsatisfaitP)?0. Méth?dedu?remier m?me?t.OnutiliseP(X>E[X])?0etP(X6E[X])?0,oubien

P(X=/0)6E[X]pouruneV AsurN.Exemples...

Méth?dedusec??d m?me?t.SiXVAsurN,alorsP(X=0)6VarX

E[X]2.

??∞4-∞∞-∞?.

Gra?healéat?ireet c?m??sa?tegéa?te.

Onsedonne ungraphealéatoire avecp=c

nlaprobabilitéd'av oirunearête entredeuxnoeuds. Siuestunsommet, Cuestlacomposante connexedeu.Onnote C1;C2;:::lescomposantes connexesdugraphe delaplus grandeàla pluspetite.On note|C|lenombrede sommetsdansla composanteC. ?hé?rème.Selonlav aleurdec,onales comportementssuivants : i.Régimesouscritique :c<1.Ilexiste auneconstente(dépendant dec)telleque : lim n!1P(|C1|6alnn)=1 ii.Régimiecritique: c=1.Ilexiste k?0telque?a?0, lim n!1P¡|C1|>an2/3Δ6k a2iii.Régimecritique: c?1.Soitpel'uniquesolutiondans [0;1[dex=e¡c(1¡x).Ilexiste une constantea0telleque??0, lim n!1P |C1| n-(1-pe)6?|C2|6a0lnn =1 ).)??licati??? m?dèled'é?idémie.(Reed-Frost).Onanindividus,età t=0onaun individu

infecté.Àl'étape t,unindividu infectépeutinfecter n'importequelautre individuavec probabilité

p=c npouruncertain c,indépendamment desautresinfections.Siunindividu estinfectéà l'étape

t,ilest retirédela populationàt+1(immunisé).Quelleest l'espérancedela tailledela population

quiaété infectéeàune étape?

•Sic<1,ona E[|C|]6O(lnn).

7 •Sic>1,soitle sommetoriginalétait dansC1lacomposantegéante, soitpas.

2.Analysed'une composanteconnexepar unprocessusde branchement.Onimite

unparcoursen largeur.Lessommets sontsoitviv ants(dansla τle),soitneutres (pasencore découverts),soitmorts (déjàtraîtés). t=0.uestvivant, lesautressontneutres

Àl?étapet,onchoisit wdanslaτle, onleretire delaτle, onajoute sesvoisinsneutres danslaτle

(deviennentvivant), etwdevientmort.Quand laτleest vide,lessommets deC(u)correspondent auxsommetsmorts. OnnoteL(t);N(t);D(t)respectivementlenombre desommetsviv ants,

neutres,mortsà l?étapet.Onnote Z(t)lenombrede sommetsréajoutés àlaτle àl?étapet.

D(t)=t

L(t)=L(t-1)+Z(t-1)

=n-t-N(t)

N(t)=n-t-L(t)

=N(t-1)-Z(t)

Z(t)≂Bin(N(t-1);p)

≂Bin(n-t+1-L(t-1);p) Autreprésentationdes processusdebranchement deGalton-Watson .ZsontdesV AsurNiid. •Àl?étapet=0,ona justelaracine, numérotée1. •Àl?étape1, onajoute lesτlsde laracine,que l?onnumérote2à1+Z(1) •Etc...àl?étape t,ona joutelesZtτlsdusommet t,numérotésde 2+P i=1t¡1Zià1+P i=1tZi. Sionnote Y(t)lenombrede noeudsdela rangéet(ievivants àl?étapet),ona .Y0=1etpour t>0,Yt=Yt¡1+Zt-1.Leprocessus s?arrêtequandYt=0pourlapremière fois(onpeut déτnir Y tmêmeaprèsl?arrêt duprocessus). Comparaisonentreprocessus debranchements. SoitZ≂Bin(n;p).Onnote Tn;pbi?latailledu processusdebranchement pourunarbre binomialdeGalton-W atson,etTn;pgrlatailledu processus debranchementpour unecomposanteconnexe.

3.Régimesous-critique. Preuve.on faitdescalculs àpartirde celemme.k=alnn,a=?c

(1¡c)?,

4.Régumesur-critique. Ilya troisétapespour lapreuve.

•Montrerqu?ona despetiteset desgrandescomposantes

•Montrerqu?ona uneseulegrande composante

•Montrerquela tailledecette composanteest≂(1-pe)n.

4.a.Ily adespetites etdesgrandes composantesuniquement.Onnotek¡=a0lnn,et

k+=n2/3. Lemme.Pourtoutsommet v,avec forteproba,soiti)leprocessus debranchementdepuis v s?arrêteenmoins dek¡étapes,soitii) ?kentrek¡etk+,ily aaumoins (k-1)k/2sommets vivants.Unmauvaissommet nesatisfaitaucune decesdeuxpropriétés. 8 ?0∞4-∞∞-∞?. ChainesdeMarko v.Introduitesen1906, appliquéesen1913 àl'étudede l'alternanceconsonne- voyelle.Applicationscourantes:physique statistique,théoriede l'informationetcompression, réseauxdecommunication, bio-informatique,combinatoire,... Exemple.atelier deréparation.Aujourn,Zn+1machinestombenten panne.Aujour n+1,

lesmachinesen pannearrivent àl'atelier,et unemachinedéjà présenteestréparée.Xn=nombre

demachinesà l'atelirelejour n. X n+1=max(Xn¡1;0)+Zn+1

Autreexemplequi donnelamême chose:une led'attente.(se résoudavec dessériesgénératrices).

Troisreprésentations.Matricielle,fonction,graphique (zolidessin).Ex: faireunzoli dessinpour unemarchealéatoire deprobapdansunedimension :çafait uneligne.

Graphes.(polyp.17) Dénitions:

quotesdbs_dbs23.pdfusesText_29

[PDF] Algorithmes et programmation en Pascal TD corrigés - Limuniv-mrsfr

[PDF] Notes de cours / Algo et Python

[PDF] Algorithmique et Programmation Projet : algorithme de - DI ENS

[PDF] Score ASIA

[PDF] Un algorithme de simulation pour résoudre un problème de probabilité

[PDF] Algorithme PanaMaths

[PDF] Algorithmique en classe de première avec AlgoBox - Xm1 Math

[PDF] Algorithme U prend la valeur [expression de la suite - Maths en ligne

[PDF] Rappels sur les suites - Algorithme - Lycée d Adultes

[PDF] Les tableaux - Luc Brun

[PDF] Les tableaux 1 Exercice 1 - Lipn

[PDF] Terminale S Exercices sur les suites Exercice 1 On consid`ere la

[PDF] Cours d algorithmique BTS SIO première année - Bienvenue sur le

[PDF] Algorithmique et programmation, un levier pour développer des

[PDF] Algorithmique et Structures de Données