2012 JAROMÍR ANTOCH. 16. ledna 2012

J. ANTOCH, KPMS

´ ˇ ˇ POZNAMKY K PREDM ETU NMAI060

´ ˇÍKLADY POZNAMKY A PR ˇ ˇ K PREDM ETU NMAI 060 JAROMÍR ANTOCH

16. ledna 2012

2011/2012

J. ANTOCH, KPMS


2011/2012

Vytvoˇruj´ıc´ı funkce Definice 1. Necht’ a0 , a1 , a2 , . . . je posloupnost re´ alných ˇc´ısel. Jestliˇze ˇrada X∞ A(x) = aj x j j=0

konverguje v nˇekterém okol´ı nuly, nazveme ji vytvoˇruj´ıc´ı funkc´ı posloupnosti {aj }.

Pozn´ amka 1. Je-li {aj } omezen´ a, pak zˇrejmˇe A(x) konverguje alespoˇ n v intervalu (−1, 1). Definice 2. Je-li X celoˇc´ıseln´ a n´ ahodn´ a veliˇcina, tj. P P(X = j) = pj , j = 0, 1, 2, . . . , p pak jej´ı (pravdˇepodobnostn´ı) j j = 1, P j vytvoˇruj´ıc´ı funkc´ı budeme rozumˇet P(x) = ∞ j=0 pj x .

Pozn´ amka 2. P nme: E g (X ) = j pj g (xj ) . Vˇsimnˇete si, ˇze P(z) = E z X pˇripomeˇ Pro celoˇc´ıselnou náhodnou veliˇcinu X jej´ı vytvoˇruj´ıc´ı funkce vˇzdy konverguje také v bodˇe x = 1, nebot’ P(1) = 1.


J. ANTOCH, KPMS

2011/2012

Vlastnosti vytvoˇruj´ıc´ı funkce I P Vˇ eta 1. Oznaˇcme qk = P(X > k) = j>k pj , k = 0, 1, 2, . . . a P j odpov´ıdaj´ıc´ı vytvoˇruj´ıc´ı funkci Q(x) = ∞ j=0 qj x . Pak pro −1 < x < 1 plat´ı Q(x) = 1 − P(x) /(1 − x). Vˇ eta 2. Pro celoˇc´ıselnou n´ ahodnou veliˇcinu X plat´ı X∞ X∞ EX = jpj = qj = P ′ (1) = Q(1) i =0

j=0

Vˇ eta 3. Necht’ pro celoˇc´ıselnou n´ ahodnou veliˇcinu X je polomˇer konvergence odpov´ıdaj´ıc´ı vytvoˇruj´ıc´ı funkce vˇetˇs´ı neˇz jedna. Potom plat´ı 2 2 var X = P ′′ (1) + P ′ (1) − P ′ (1) = 2Q′ (1) + Q(1) − Q(1)

Pozn´ amka 3. Vˇeta 3 z˚ ust´ av´ a v platnosti i v pˇr´ıpadˇe, ˇze polomˇer konvergence P(x) je roven jedné, pokud existuje koneˇcná limx→1− Q′′ (x) a pokud derivaci v bodˇe x = 1 vystupuj´ıc´ı ve vzorci pro var X nahrad´ıme jejich limitami pro x → 1− .


J. ANTOCH, KPMS

2011/2012

Rozklad na ˇ c´ asteˇ cn´ e zlomky Pozn´ amka 4. Teoreticky je znalost P(x) ekvivalentn´ı znalosti {pj }, uˇze být z´ısk´ an´ı jednotlivých nebot’ pj = P (j) (0)/j!. V praxi vˇsak m˚ pravdˇepodobnost´ı znaˇcnˇe n´ aroˇcné. V nˇekterých pˇr´ıpadech nám pom˚ uˇze n´ asleduj´ıc´ı tvrzen´ı. Vˇ eta 4. Necht’ vytvoˇruj´ıc´ı funkce P(x) posloupnosti {pj } se dá vyjádˇrit ve tvaru P(x) = U(x)/V (x), kde U(x) a V (x) jsou polynomy bez spoleˇcných koˇren˚ u, U(x) je stupnˇe niˇzˇs´ıho neˇz V (x) a necht’ koˇreny polynomu V (x) jsou vesmˇes jednoduché. Potom pn =

ρ1 x1n+1

+ ··· +

ρm n+1 , xm

0 ≤ n < ∞,

kde m je stupeˇ n polynomu V (x), x1 , . . . , xm jsou jeho koˇreny a ρk = −U(xk )/V ′ (xk ), 1 ≤ k ≤ m. Pozn´ amka 5. Pro výpoˇct ρk se zpravidla uˇz´ıv´ a technika rozkladu na ˇc´ asteˇcné zlomky, kterou ma zabudovanou jak program Maple tak program Mathematica.

J. ANTOCH, KPMS


2011/2012

Rozklad na ˇ c´ asteˇ cn´ e zlomky (pokr.) Pozn´ amka 6. Necht’ x1 je ten koˇren V (x) pro nˇejˇz |x1 | < xk , 2 ≤ k ≤ m. Potom ρ2 x1 n+1 ρm x1 n+1 ρ1 , + ... + pn = n+1 1 + ρ1 x2 ρ1 x m x1 takˇze pro n → ∞ plat´ı pn ≈ ρ1 /x1n+1 , kde ρ1 = −U(x1 )/V ′ (x1 ).

Pozn´ amka 7. Pro platnost asymptotického vztahu pn ≈ ρ1 /x1n+1 lze vynechat pˇredpoklad, ˇze U(x) je stupnˇe menˇs´ıho neˇz V (x) a jednoduchost staˇc´ı poˇzadovat jenom u koˇrene x1 . Ze zkuˇsenosti je pˇritom zn´ amo, ˇze aproximace je dobr´ a i pro malé hodnoty n. Pˇr´ıklad 1. Necht’ qn je pravdˇepodobnost toho, ˇze v posloupnosti n hod˚ u minc´ı nepadne ani jednou trojice l´ıc˚ u za sebou. Odvod’te vytvoˇruj´ıc´ı funkci Q(x) a spoˇctˇete pro menˇs´ı hodnoty n pravdˇepodobnosti qn jak pˇresnˇe, tak pˇribliˇznˇe. ˇ sen´ı: Q(x) = 8 + 4x + 2x 2 / 8 − 4x − 2x 2 − x 3 . Reˇ

J. ANTOCH, KPMS


2011/2012

Vytvoˇruj´ıc´ı funkce – pˇr´ıklady Pˇr´ıklad 2. Ovˇeˇrte tvar vytvoˇruj´ıc´ıch funkci pro n´ asleduj´ıc´ı rozdˇelen´ı: Alternativn´ı Binomické Poissonovo Geometrické

. . . P(x) = q + px

. . . P(x) = (q + px)n

. . . P(x) = exp{−λ + λx}

. . . P(x) = p/(1 − qx) resp. = px/(1 − qx)

r Negativnˇe binomické . . . P(x) = p/(1 − qx) r resp. = px/(1 − qx) Rovnomˇerné

. . . P(x) = (1 − x n+1 )/ (n + 1)(1− x) resp. = x(1 − x n ) / n(1 − x)

Spoˇctˇete pomoc´ı tˇechto vytvoˇruj´ıc´ıch funkc´ı odpov´ıdaj´ıc´ı stˇredn´ı hodnotu a rozptyl. Pozn´ amka 8. Uvˇedomte si, ˇze geometrické, respektive negativnˇe binomické, rozdˇelen´ı jsou nejjednoduˇsˇs´ı modely popisuj´ıc´ı doby ˇcekán´ı.

J. ANTOCH, KPMS


2011/2012

Konvoluce Definice 3. Necht’ a0 , a1 , . . . a b0 , b1 , . . . jsou dvˇe posloupnosti reálných a vztahem ˇc´ısel. Potom posloupnost c0 , c1 , . . . definovan´ cn = a0 bn + a1 bn−1 + . . . + an b0 , n = 0, 1, . . . se nazývá konvoluce posloupnost´ı {aj } a {bj }, a znaˇc´ı se {cj } = {aj } ⋆ {bj }. Vˇ eta 5. Necht’ {aj } a {bj } jsou posloupnost´ı s vytvoˇruj´ıc´ımi funkcemi A(x) a B(x). Potom pro vytvoˇruj´ıc´ı funkci jejich konvoluce {cj } plat´ı C(x) = A(x)B(x).

Pozn´ amka 9. Konvoluci {aj } ⋆ {aj } nazýv´ ame konvoluˇcn´ı mocninou a znaˇc´ıme ji {aj }2⋆ . Podobnˇe n-tou konvoluˇcn´ı mocninu {aj } ⋆ . . . ⋆ {aj } znaˇc´ıme {aj }n⋆ . Vˇ eta 6. Necht’ X1 , X2 , . . . , Xn jsou nez´ avislé stejnˇe rozdˇelené celoˇc´ıselné n´ ahodné veliˇciny s rozdˇelen´ım {pj } a vytvoˇruj´ıc´ı funkc´ı P(x). Pak rozdˇelen´ı souˇctu X1 + X2 + . . . + Xn je d´ ano n-tou konvoluˇcn´ı mocninou {pj }n⋆ a odpov´ıdaj´ıc´ı vytvoˇruj´ıc´ı funkce je P(x) . . . P(x) = P n (x).

J. ANTOCH, KPMS


2011/2012

Sloˇ zen´ a rozdˇ elen´ı Vˇ eta 7. Necht’ X1 , X2 , . . . a N jsou nez´ avislé celoˇc´ıselné náhodné veliˇciny, Xi maj´ı totéˇz rozdˇelen´ı {fj } a N necht’ m´ a rozdˇelen´ı {gj }. Potom SN = X1 + . . . + XN je téˇz celoˇc´ıseln´ a n´ ahodn´ a veliˇcina s rozdˇelen´ım {hj } a plat´ı X∞ hj = P(SN = j) = gn · {fj }n⋆ . n=0

Jsou-li A(x), B(x) a C(x) vytvoˇruj´ıc´ı funkce pozdˇelen´ı {fj }, {gj } a {hj }, potom C(x) = B A(x) a E SN = E X1 · E N. Rozptyl spoˇcteme aplikac´ı Vˇety 3 a pravidel pro derivaci sloˇzené funkce. Pozn´ amka 10. Vˇsimnˇeme si, ˇze n´ ahodn´ a veliˇcina SN = X1 + . . . + XN nen´ı nic jiného neˇz náhodný souˇcet n´ ahodných veliˇcin. Pˇr´ıklad 3. Necht’ poˇcet snesených vaj´ıˇcek N se ˇr´ıd´ı Poissonovým rozdˇelen´ım Po(λ) a pravdˇepodobnost narozen´ı jedince z vaj´ıˇcka necht’ je p, tj. Xi se ˇr´ıd´ı alternativn´ım rozdˇelen´ım. Ukaˇzte, ˇze potom SN se ˇr´ıd´ı Poissonovým rozdˇelen´ım Po(λp).

J. ANTOCH, KPMS


Vˇ etv´ıc´ı se proces – aneb jak se mohou ˇs´ıˇrit viry

2011/2012

J. ANTOCH, KPMS


2011/2012

Rekurentn´ı jevy I Uvaˇzujme posloupnost opakovaných (ne nutnˇe nez´ avislých) pokus˚ u, z nichˇz kaˇzdý má tutéˇz koneˇcnou nebo spoˇcetnou mnoˇzinu moˇzných výsledk˚ u E1 , E2 , . . .. Necht’ o n (1) Ej1 , Ej2 , . . . , Ejn znaˇc´ı jev, ˇze prvn´ı pokus skonˇcil Ej1 , druhý Ej2 , . . . , n-tý Ejn .

Necht’ pro vˇsechny koneˇcné posloupnosti typu (1): P P Ej1 , . . . , Ejn−1 = ∞ jn =1 P Ej1 , . . . , Ejn−1 , Ejn , 1 < n < ∞.

O kaˇzdé posloupnosti typu (1) lze jednoznaˇcnˇe rozhodnout, zda má ˇci nemá vlastnost ξ.

Výrokem ξ nastává na n-tém m´ıstˇe (koneˇcné nebo nekoneˇcné) posloupnosti Ej1 , Ej2 , . . . budeme rozumˇet pr´ avˇe to, ˇze posloupnost Ej1 , Ej2 , . . . , Ejn má vlastnost ξ.

J. ANTOCH, KPMS


2011/2012

Rekurentn´ı jevy I Definice 4. Vlastnost ξ nazveme rekurentn´ım jevem, jestliˇze: 1

ξ nastal na n-tém a (n+m)-tém m´ıstˇe posloupnosti Ej1 , Ej2 , . . . , Ejn+m tehdy a jen tehdy, nastane-li na posledn´ım m´ıstˇe posloupnosti Ej1 , . . . , Ejn a na posledn´ım m´ıstˇe posloupnosti Ejn+1 , . . . , Ejn+m ;

2

v takovém pˇr´ıpadˇe plat´ı: P Ej1 , Ej2 , . . . , Ejn+m = P Ej1 , . . . , Ejn · P Ejn+1 , . . . , Ejn+m

Definice 5. Kaˇzdému rekurentn´ımu jevu ξ pˇriˇrad’me posloupnosti ˇc´ısel un = P ξ nastane v pokusu n − tém 1≤n<∞ fn = P ξ nastane v pokusu n − tém poprvé 1≤n<∞ Dodefinujme alnˇe u0 = 1, P f0 = 0 a zaved’me vytvoˇruj´ıc´ı fukce P∞ form´ n n F (x) = n=0 fn x a U(x) = ∞ n=0 un x .

J. ANTOCH, KPMS


2011/2012

Vztah mezi {un } a {fn } Pozn´ amka 11. Mezi pravdˇepodobnostmi {un } a {fn }, respektive mezi jejich vytvoˇruj´ıc´ımi funkcemi F (x) a U(x), plat´ı: un = f0 un + f1 un−1 + . . . + fn u0 ,

n ≥ 1,

U(x) − 1 = F (x)U(x), −1 < x < 1. P Pozn´ amka 12. Je-li f = n fn = 1, pak {fn } je rozdˇelen´ı an´ı na prvn´ı výskyt pravdˇepodobnosti náhodné veliˇciny T1 popisuj´ıc´ı ˇcek´ rekurentn´ıho jevu ξ. Je-li f < 1, pak doba ˇcek´ an´ı T1 je nevlastn´ı náhodná veliˇcina, která nabývá s kladnou pravdˇepodobnost´ı (= 1 − f ) nevlastn´ı hodnoty ∞, kterou interpretujeme tak, ˇze jev ξ nenastal. Pozn´ amka 13. Necht’ Ti , 1 ≤ i ≤ r , jsou nez´ avislé náhodné veliˇciny maj´ıc´ı totéˇz rozdˇelen´ı {fn }, kde Ti interpretujeme jako dobu, která uplyne mezi (i-1)-n´ım a i-tým výskytem ξ (tzv. doba návratu). Pak T (r ) = T1 + . . . + Tr interpretujeme jako dobu ˇcek´ an´ı na r-tý výskyt ξ.


J. ANTOCH, KPMS

2011/2012

Pravdˇ epodobnosti r-t´ ych n´ avrat˚ u (r )

Oznaˇcme fn , 1 ≤ n < ∞ pravdˇepodobnost toho, ˇze ξ nastane po r-té (r ) v n-tém pokusu, a poloˇzme f0 = 0. Vˇ eta 8. Plat´ı

(r )

fn

r ⋆ = fn

Vˇ eta 9. Pravdˇepodobnost jevu, ˇze rekurentn´ı jev nastaneP v nekoneˇcné r posloupnosti pokus˚ u alespoˇ n r -kr´ at je rovna f , kde f = i fi .

J. ANTOCH, KPMS


2011/2012

Klasifikace rekurentn´ıch jev˚ u Definice 6. Rekurentn´ı jev ξ se P nazýv´ a trvalý, je-li f = 1, respektive pˇrechodný, je-li f < 1, kde f = ∞ n=0 fn .

Vˇ eta 10. Pravdˇepodobnost toho, ˇze rekurentn´ı jev ξ nastane v nekoneˇcné posloupnosti pokus˚ u nekoneˇcnˇe mnohokrát je rovna jedné, jedná-li se o jev trvalý, a je rovna nule, jedn´ a-li se o jev pˇrechodný. Vˇ ta 11. Rekurentn´ı jev ξ je pˇrechodný tehdy a jen tehdy, je-li P Pe∞ r´ıpadˇe je f = (u − 1)/u, kde u = ∞ n=0 un . n=0 un < +∞. V tom pˇ

Je-li f = 1, oznaˇcme µ = E T1 = stˇredn´ı dobu návratu jevu ξ.

P∞

n=0

nfn a interptetujme ji jako

Definice 7. Trvalý rekurentn´ı jev ξ se nazýv´ a nenulový, jestliˇze µ < +∞, respektive nulový, jestliˇze µ = +∞. Definice 8. Rekurentn´ı jev ξ se nazýv´ a periodický, jestliˇze existuje pˇrirozené λ > 1 tak, ˇze un = 0 pro vˇsechna n kter´ a nejsou dˇelitelná λ. a periodou jevu ξ. Nejvˇetˇs´ı ˇc´ıslo λ s touto vlastnost´ı se nazýv´

J. ANTOCH, KPMS


2011/2012

Pˇr´ıklady rekurentn´ıch jev˚ uI Pˇr´ıklad 4. Uvaˇzujme posloupnosti nez´ avislých pokus˚ u s alternativn´ı ˇ ˇze v ˇcase n nastává odpovˇed´ı s pravdˇepodobnost´ı zdaru p. Rekneme, u a nezdar˚ u v prvn´ıch n pokusech jsou si rovny. jev ξ, jestliˇze poˇcty zdar˚ Ukaˇzte, ˇze se jedná o periodický rekurentn´ı jev, který je pro p = 1/2 trvalý a pro p 6= 1/2 pˇrechodný. Spoˇctˇete pravdˇepodobnosti un a fn a jejich aproximace. Ukaˇzte, ˇze plat´ı: n P 2n U(x) = ∞ pqx 2 = √ 1 2 n=0 n 1−4pqx p F (x) = 1 − 1 − 4pqx 2 n n f2n−1 = 0, f2n = n2 2n−2 n−1 p q , n = 1, 2, . . . √ pro p = 1/2 je un ≈ 1/ πn

Nasimulujte nˇekolik realizac´ı této n´ ahodné procházky délky alespoˇ n nte pˇritom na volbu p = 1/2. 105 pro r˚ uzné hodnoty p a nezapomeˇ Nakreslete si odpov´ıdaj´ıc´ı grafy a rozmyslete.

J. ANTOCH, KPMS


2011/2012

Pˇr´ıklady rekurentn´ıch jev˚ u II Pˇr´ıklad 5. Uvaˇzujme ˇcástici, kter´ a se pohybuje po celoˇc´ıselných bodech v rovinˇe tak, ˇze v kaˇzdém kroku se posune o jednotku vlevo, vpravo, nahoru nebo dol˚ u. Vˇsechny ˇctyˇri moˇznosti jsou stejnˇe pravdˇepodobné ˇ a nezávislé na pˇredchoz´ıch kroc´ıch. Rekneme, ˇze v ˇcase n nastává jev ξ, jestliˇze jsme se vrátili do výchoz´ı pozice. Ukaˇzte, ˇze se jedná o periodický rekurentn´ı jev, který je trvalý. Spoˇctˇete pravdˇepodobnosti un a jejich aproximace. Pˇr´ıklad 6. Uvaˇzujme ˇcástici, kter´ a se pohybuje po celoˇc´ıselných bodech v prostoru tak, ˇze v kaˇzdém kroku se posune o jednotku vlevo, vpravo, nahoru, dol˚ u, dopˇredu nebo dozadu. Vˇsechny tyto moˇznosti jsou stejnˇe ˇ pravdˇepodobné a nezávislé na pˇredchoz´ıch kroc´ıch. Rekneme, ˇze v ˇcase n nastává jev ξ, jestliˇze jsme se vr´ atili do výchoz´ı pozice. Ukaˇzte, ˇze se jedná o periodický rekurentn´ı jev, který je pˇrechodný. Spoˇctˇete pravdˇepodobnosti un a jejich aproximace. Pom˚ ucka. Vzpomeˇ nte si na multinomické rozdˇelen´ı.

J. ANTOCH, KPMS


Limitn´ı vˇ eta Vˇ eta 12. Necht’ rekurentn´ı jev ξ je trvalý neperiodický. Potom ( 1 µ<∞ lim un = µ n→∞ 0 µ=∞ Vˇ eta 13. Necht’ rekurentn´ı jev ξ je trvalý periodický s periodou λ. Potom ( λ µ<∞ lim unλ = µ n→∞ 0 µ=∞ Pozn´ amka 14. D˚ ukaz se prov´ ad´ı pomoc´ı vˇety 6 a tvrzen´ı uvedeného v poznámce 4.

2011/2012


J. ANTOCH, KPMS

2011/2012

Asymptotick´ e rozdˇ elen´ı ˇ cetnost´ı rekurentn´ıch jev˚ u Vˇ eta 14. Necht’ rekurentn´ı jev ξ je trvalý. Oznaˇcme Nn poˇcet výskyt˚ uξ (r ) do ˇcasu n a T dobu ˇcek´ an´ı na r-tý výskyt ξ. Potom jevy [Nn ≥ r ] a [T (r ) ≤ n], 1 ≤ r ≤ n < ∞ jsou ekvivalentn´ı. Pˇredpokládejme dále, ˇze rozdˇelen´ı dob prvn´ıch návrat˚ a koneˇ cnou stˇredn´ı hodnotu µ a koneˇcný u m´ n nσ2 2 rozptyl σ . Potom Nn ∼ N µ , µ3 a lim P

r →∞

T (r ) − r µ √ ≤y σ r

!

= Φ(y ),

y ∈ R1 .

Vˇ eta 15. Necht’ rekurentn´ı jev ξ je trvalý nenulový. Potom pro n → ∞ plat´ı E Nn ≈ n/µ, kde µ je stˇredn´ı doba n´ avratu.

Pozn´ amka 15. Necht’ rekurentn´ı jev ξ je trvalý nulový. Potom E Nn nen´ı obecnˇe ˇrádu n1 , viz model n´ ahodné proch´ p azky popsaný v pˇr´ıkladu 4. Ukaˇzte, ˇze v tomto pˇr´ıpadˇe E N2n ≈ 2 n/π.

J. ANTOCH, KPMS


2011/2012

Rovnice obnovy Pozn´ amka 16. Limitn´ı vˇety pˇredchoz´ıch odstavc˚ u lze povaˇzovat za speciáln´ı pˇr´ıpady urˇcité obecné vˇety, kterou lze formulovat analyticky bez pouˇzit´ı pravdˇepodobnostn´ıch pojm˚ u. Jak uvid´ıme, i tato obecná vˇeta má pravdˇepodobnostn´ı význam. Definice 9. Necht’ a0 , a1 , a2 , . . . a b0 , b1 , b2 , . . . jsou dvˇePposloupnosti ∞ takové, ˇze a0 = 0, 0 ≤ an ≤ 1, bn ≥ 0, n = 0, 1, 2, . . . , i =n bn < ∞. Poloˇzme un = bn + a0 un + a1 un−1 . . . + an u0 , n = 0, 1, 2, . . ., tj. un = bn + a n ⋆ un (2) Vztah (2) je v literatuˇre nazýv´ an rovnic´ı obnovy .

Pozn´ amka 17. Pro vytvoˇruj´ıc´ı funkce posloupnost´ı uvaˇzovaných v definici 9 plat´ı U(x) = B(x) + A(x)U(x)

≡

U(x) =

B(x) 1 − A(x)


J. ANTOCH, KPMS

2011/2012

Rovnice obnovy (pokr. I) Definice 10. Posloupnost {an } nazveme priodickou, existuje-li λ > 1 tak, ˇze an = 0 pro vˇsechna n nedˇeliteln´ a λ. Nejvˇetˇs´ı takové λ nazveme periodou. Vˇ eta 16. Necht’ posloupnost {an } je neperiodick´ a. Potom plat´ı: P∞ P∞ an < 1, potom n=1 un < ∞. 1 Je-li Pn=1 ∞ 2 Je-li zovat za rozdˇelen´ı doby návratu n=1 an = 1, tj. {an } lze povaˇ nˇejakého trvalého neperiodického rekurentn´ıho jevu ξ, potom (P P∞ P∞ ∞ n=1 nan , n=1 nan < ∞, n=0 bn lim un = P∞ n→∞ 0, n=1 nan = ∞. 3

Je-li

P∞

n=1

an > 1, potom pro n → ∞ je un ≈

B(x) x n+1 A′ (x)

,

kde x < 1 je jediný koˇren rovnice A(x) = 1.

J. ANTOCH, KPMS


2011/2012

Rovnice obnovy (pokr. II) Vˇ eta 17. Necht’ posloupnost {an } je periodick´ a s periodou λ. Potom plat´ı: P∞ P∞ 1 Je-li n=1 an < 1, potom n=1 un < ∞. 2 3

Je-li µ = ∞, potom limn→∞ un = 0. P Je-li µ < ∞ ∞ zovat za rozdˇelen´ı doby n=1 an = 1, tj. {an } lze povaˇ návratu nˇejakého trvalého periodického rekurentn´ıho jevu ξ, potom pro 0 ≤ j < λ plat´ı: P P∞ λ ∞ bk 1 Xn k=0 bkλ+j uν = k=0 . lim unλ+j = & lim ν=1 n→∞ n→∞ n µ µ

J. ANTOCH, KPMS


Rekurentn´ı jevy se zpoˇ zdˇ en´ım

2011/2012

J. ANTOCH, KPMS


2011/2012

Markovovy ˇretˇ ezce Definice 11. Posloupnost pokus˚ u, z nichˇz kaˇzdý m´ a tu samou koneˇcnou nebo spoˇcetou mnoˇzinu moˇzných výsledk˚ u E1 , E2 , . . . nazveme ˇ jestliˇze pravdˇepodobnosti kaˇzdé koneˇcné Markovovým ˇretˇezcem (MR), posloupnosti výsledk˚ u (pokus˚ u nultého aˇz n-tého) je dána vztahem P Ej0 , Ej1 , . . . , Ejn = aj0 pj0 j1 . . . pjn−1 jn , (3) kde ak , k = 1, 2, . . . jsou pravdˇepodobnosti výsledk˚ u nultého pokusu a pjk , 1 ≤ j < +∞, 1 ≤ k < +∞ je (pro vˇsechny pokusy táˇz) podm´ınˇená pravdˇepodobnost výsledku Ek za podm´ınky výsledku Ej v pokuse pˇredchoz´ım.

Pozn´ amka 18. Posloupnost {ak }k nazýv´ ame poˇcateˇcn´ım rozdˇelen´ım pravdˇepodobnost´ı, podm´ınˇené pravdˇepodobnosti pjk nazýváme pravdˇepodobnostmi pˇrechodu. Zat´ımco tedy k popisu nezávislých jev˚ u ˇ staˇc´ı zn´ a t pravdˇ e podobnosti p , k popisu M R potˇ r ebujeme zn´ a t a ≡ {a iP k} a P ≡ pjk . Vˇsimnˇeme si, ˇze j pij = 1 ∀i ∈ N.

J. ANTOCH, KPMS


2011/2012

Pˇr´ıklady Markovov´ ych ˇretˇ ezc˚ u ˇ vhodného pro popis: Sestavte matice pˇrechodu MR 1 N´ ahodné procházky po pˇr´ımce. 2 N´ ahodné procházky po pˇr´ımce s odr´ aˇzej´ıc´ımi stˇenami. 3 N´ ahodná procházka po pˇr´ımce s pohlcuj´ıc´ımi stˇenami. 4 Ehrenfest˚ uv myˇslený pokus. Necht’ a rozliˇsitelných molekul je rozdˇeleno do dvou n´ adob oznaˇcených A a B. V kaˇzdém kroku se náhodnˇe zvol´ı jedna molekula s tou samou pst´ı 1/a a pˇrem´ıst´ı se do nádoby opaˇcné. Stavem systému je poˇcet molekul v nádobˇe A. 5 Modifikovan´ y Ehrenfest˚ uv myˇslený pokus. Necht’ a rozliˇsitelných molekul je rozdˇeleno do dvou n´ adob oznaˇcených A a B. V kaˇzdém kroku se náhodnˇe zvol´ı jedna n´ adoba a jedna molekula z n´ı se pˇrem´ıst´ı se do nádoby opaˇcné. Stavem systému je poˇcet molekul v nádobˇe A. 6 Posloupnost nez´ avislých opakovaných pokus˚ u. ˇu 7 Modelujte pomoc´ ı MR ´lohu o zruinov´ an´ı hr´ aˇce.


J. ANTOCH, KPMS

2011/2012

Psti pˇrechodu vyˇsˇs´ıch ˇr´ ad˚ u Vˇ eta 18. Pravdˇepodobnosti pˇrechodu ze stavu Ej do stavu Ek po (n) n-kroc´ıch, jeˇz oznaˇc´ıme pjk , dostaneme jako prvky matice Pn . Je pˇritom zvykem dodefinovat P0 = I. Pozn´ amka 19. Matici Pn m˚ uˇzeme spoˇc´ıtat ˇradou zp˚ usob˚ u: Postupným umocˇ nov´ an´ım. Pˇr´ımo z definice (principu). Pomoc´ı tzv. Perronova vzorce vyuˇz´ıvaj´ıc´ıho znalosti vlastn´ıch ˇc´ısel P. (n) Definice 12. Vedle podm´ınˇených pravdˇepodobnost´ı pjk zaved’me (n)

nepodm´ınˇené (absolutn´ı) pravdˇepodobnosti ak jako pravdˇepodobnosti jevu, ˇze systém je v ˇcase n ve stavu Ek . Pozn´ amka 20. Zˇrejmˇe plat´ı, ˇze: X X (m) (n) (0) (n) (n) (n+m) ak = ak , ak = aj pjk a ak = aj pjk j

(n) limn→∞ pjk

Existuje-li jsou si rovny.

j

(n)

nez´ avisl´ a na j, pak existuje také limn→∞ ak

a


J. ANTOCH, KPMS

2011/2012

Znaˇ cen´ı Oznaˇcme: (n) fjj rozdˇelen´ı pravdˇepodobnost´ı prvn´ıch n´ avrat˚ u do stavu Ej , zaˇc´ınáme-li ve stavu Ej . (n)

pjj pravdˇepodobnost toho, ˇze systém je v ˇcase n ve stavu Ej , zaˇc´ınáme-li ve stavu Ej . (n)

uchodu stavem Ej , zaˇc´ınáme-li ve fij pravdˇepodobnosti prvn´ıho pr˚ stavu Ei . Vˇ eta 19. Poloˇzme (0)

fjj

(1)

(0)

(0)

= 0, pjj = pjj , pjj = 1, fij

(0)

= 0, pij = 0.

Potom plat´ı (n)

(0) (n)

(1) (n−1)

pjj = fjj pjj + fjj pjj

(n) (0)

+ . . . + fjj pjj

(n) (n) (n) (n) ⋆ pij + fjj = fij pij

J. ANTOCH, KPMS


2011/2012

ˇ Klasifikace stav˚ u MR Vˇ eta 20. V Markovˇe ˇretˇezci zvolme pevnˇe stav Ej . a) Je-li systém na poˇcátku ve stavu Ej , pak kaˇzdý pr˚ uchod systému stavem Ej je rekurentn´ı jev. b) Je-li systém na poˇcátku ve stavu Ei , pak kaˇzdý pr˚ uchod systému stavem Ej je rekurentn´ı jev se zpoˇzdˇen´ım. Teorie Markovsk´ ych ˇretˇ ezc˚ u je tedy v podstatˇ e teori´ı rekurentn´ıch jev˚ u. Nov´ e je jen to, ˇ ze studujeme v´ıce rekurentn´ıch jev˚ u souˇ casnˇ e. Vˇ eta 21. V Markovˇe ˇretˇezci zvolme pevnˇe stav Ej . P (n) em pˇr´ıpadˇe Stav Ej je pˇrechodný ⇔ ∞ n=1 pjj < ∞. V takov´ P∞ (n) sechna i . n=1 pij < ∞ pro vˇ P (n) (n) Stav Ej je trvalý nulový ⇔ ∞ n=1 pjj = ∞ a limn→∞ pjj = 0. P (n) sechna i . V takovém pˇr´ıpadˇe ∞ n=1 pij < ∞ pro vˇ


J. ANTOCH, KPMS

2011/2012

ˇ pokr. Klasifikace stav˚ u MR Vˇ eta 22. V Markovˇe ˇretˇezci zvolme pevnˇe stav Ej . Je-li stav Ej trvalý nenulový neperiodický, potom (n)

lim pjj =

n→∞

1 , µj

(n)

lim pij =

n→∞

fij , i 6= j, µj

kde fij =

X∞

(n) f n=1 ij

Je-li stav Ej trvalý nenulový periodický s periodou λ, potom (nλ)

lim pjj

n→∞

=

λ µj

a pro vˇsechna i 6= j a 0 ≤ ν ≤ λ − 1 P (kλ+ν) λ ∞ k=0 fij (nλ+ν) = lim p n→∞ ij µj Dále plat´ı (n)

lim p ij =

n→∞

fij , µj

(n)

kde p ij =

1 X∞ pk k=1 ij n

J. ANTOCH, KPMS


2011/2012

Nerozloˇ ziteln´ e a rozloˇ ziteln´ e ˇretˇ ezce I Definice 13. ˇrekneme, ˇze stav Ek je dosaˇzitelný ze stavu Ej , jestliˇze (n) existuje n ≥ 0 takové, ˇze pjk > 0.

Definice 14. Neprázdná mnoˇzina stav˚ u C se nazýv´ a uzavˇrená, jestliˇze ˇz´ adný stav vnˇe C nen´ı dosaˇzitelný z ˇz´ adného stavu uvnitˇr C . Vˇ eta 23. Mnoˇzina stav˚ u C je uzavˇren´ a ⇔ pjk = 0 pro vˇsechna Ej ∈ C a Ek ∈ / C.

Definice 15. Je-li jednobodov´ a mnoˇzina {Ej } uzavˇrená, tj. je-li pjj = 1, pak se stav Ej nazývá absorbˇ cn´ı stav. ˇ ˇr´ Pozn´ amka 21. Vynecháme-li v matici P MR adky a sloupce odpov´ıdaj´ıc´ı stav˚ um vnˇe uzavˇrené mnoˇziny C , dostaneme opˇet stochastickou matici. Mnoˇzina C tedy pˇredstavuje opˇet Markov˚ uv ˇ ˇretˇezec, kterému se ˇr´ıká podˇretˇ ezec p˚ uvodn´ıho MR.

J. ANTOCH, KPMS


2011/2012

Nerozloˇ ziteln´ e a rozloˇ ziteln´ e ˇretˇ ezce II ˇ se nazýv´ Definice 16. MR a nerozloˇ ziteln´ y, jestliˇze v nˇem kromˇe mnoˇziny vˇsech stav˚ u neexistuje ˇz´ adn´ a jin´ a uzavˇren´ a mnoˇzina stav˚ u. V opaˇcném pˇr´ıpadˇe se nazýv´ a rozloˇzitelný. ˇ ezec je nerozloˇzitelný ⇔ kaˇzdý jeho stav je dosaˇzitelný Vˇ eta 24. Retˇ z kaˇzdého jiného stavu. ˇ ezec s koneˇcnˇe mnoha stavy je rozliˇzitelný ⇔ odpov´ıdaj´ıc´ı Vˇ eta 25. Retˇ matice P je po pˇr´ıpadném pˇreˇc´ıslov´ an´ı stav˚ u tvaru P1 0 P= A B kde v diagonáln´ıch pol´ıch stoj´ı ˇctvercové matice. ˇ ˇze stavy Ej a Ek jsou téhoˇz typu, budeme Pozn´ amka 22. Rekneme-li, ’ t´ım rozumˇet, ˇze jsou bud oba pˇrechodné nebo oba trvalé nulové nebo oba trvalé nenulové a souˇcasnˇe ˇze jsou oba neperiodickénebo oba periodické s toutéˇz periodou.

J. ANTOCH, KPMS


2011/2012

Nerozloˇ ziteln´ e a rozloˇ ziteln´ e ˇretˇ ezce III Vˇ eta 26. Je-li stav Ek dosaˇzitelný ze stavu Ej a naopak, stav Ej je dosaˇzitelný ze stavu Ek , pak jsou oba stavy téhoˇz typu. Vˇ eta 27. Je-li stav Ek dosaˇzitelný ze stavu Ej a stav Ej je dosaˇzitelný ze stavu Ek , pak jsou oba stavy téhoˇz typu. ˇ jsou vˇsechny stavy téhoˇz typu. Vˇ eta 28. V nerozloˇzitelném MR ˇ s koneˇcnˇe mnoha stavy neexistuj´ı stavy nulové a nen´ı Vˇ eta 29. V MR moˇzné, aby vˇsechny stavy byly pˇrechodné.


J. ANTOCH, KPMS

Stacion´ arn´ı rozdˇ elen´ı I ˇ s matic´ı pravdˇepodobnost´ı Definice 17. Mˇejme nerozloˇzitelný MR pˇrechod˚ u P. Rozdˇelen´ı {vj } se nazýv´ a stacion´ arn´ı rozdˇelen´ı tohoto ˇretˇezce, jestliˇze X vj = vi pij ∀j i

Tento vztah lze maticovˇe zapsat jako v = P′ v, kde P′ znaˇc´ı matici transponovanou k P. ˇ existuje stacion´ Vˇ eta 30. V nerozloˇzitelném MR arn´ı rozdˇelen´ı ⇔ jsou vˇsechny stavy trvalé nenulové. Toto stacion´ arn´ı rozdˇelen´ı v je jediné a pro vˇsechna i , j plat´ı: (n)

v neperiodickem pripade vj = lim pij > 0 n→∞ 1 Xn (k) p > 0 v periodickem pripade vj = lim k=1 ij n→∞ n

2011/2012

J. ANTOCH, KPMS


2011/2012

Stacion´ arn´ı rozdˇ elen´ı II ˇ s koneˇcnˇe mnoha stavy jsou dle Pozn´ amka 23. V nerozloˇzitelném MR vˇety 29, takˇze stacionárn´ı rozdˇelen´ı existuje. Definice 18. Matice s nez´ apornými prvky takov´ a, ˇze vˇsechny ˇrádkové i sloupcové souˇcty jsou rovny jedné se nazýv´ a dvojnˇe stochastická. Vˇ eta 31. Mˇejme nerozloˇzitelný ˇretˇezec s dvojnˇe stochastickou matic´ı. Je-li poˇcet stav˚ u koneˇcný, ˇreknˇeme n, potom stacion´ arn´ı rozdˇelen´ı je rovnomˇerné, tj. vi = 1/n pro 1 ≤ i ≤ n. Je-li poˇcet stav˚ u nekoneˇcný, potom stacionárn´ı rozdˇelen´ı neexistuje. Pˇr´ıklad 7. Naleznˇete stacionarn´ı rozdˇelen´ı pro n´ ahodnou procházku s dvˇema odráˇzej´ıc´ımi stˇenami. Zjistˇete, pro které hodnoty p existuje stacion´ arn´ı rozdˇelen´ı v pˇr´ıpadˇe náhodné procházky odr´ aˇzej´ıc´ı stˇenou v nule a neohraniˇcenou zprava. Naleznˇete stacionárn´ı rozdˇelen´ı pro Ehrenfest˚ um myˇslený pokus.

J. ANTOCH, KPMS


2011/2012

Pˇrechodn´ e stavy ˇ obsahuj´ıc´ı stavy trvalé i pˇrechodné. Necht’ T je mnoˇzina Uvaˇzujme MR vˇsech pˇrechodných stav˚ u a C je nˇejak´ a nerozloˇziteln´ a uzavˇrená mnoˇzina trvalých stav˚ u. Zafixujme nˇekterý stav Ej a oznaˇcme: xj = P Ej → C je pravdˇepodobnost absorbce v C 1 − xj je pravdˇepodobnost jevu, ˇze systém, který je na poˇcátku ve stavu Ej , navˇzdy setrv´ a v T nebo dojde k absorbci v jiné uzavˇrené mnoˇzinˇe stav˚ u P (1) xj = k∈C pjk je pravdˇepodobnost absorbce v C v prvn´ım kroku yj je pravdˇepodobnost jevu, ˇze systém, který je na poˇcátku ve stavu Ej , navˇzdy setrv´ avT


J. ANTOCH, KPMS

2011/2012

Pˇrechodn´ e stavy – pokr. Vˇ eta 32. Pravdˇepodobnosti xj , j ∈ T , vyhovuj´ı soustavˇe rovnic ξj −

X

ν∈T

(1)

pjν ξν = xj ,

j ∈ T.

Vˇ eta 33. Pravdˇepodobnosti yj , j ∈ T , vyhovuj´ı soustavˇe rovnic X ηj = pjν ην , j ∈ T . ν∈T

(4)

(5)

Vˇ eta 34. Soustava (4) m´ a jediné omezené ˇreˇsen´ı ⇔ soustava (6) nemá jiné omezené ˇreˇsen´ı neˇz trivi´ aln´ı. Vˇ eta 35. Pravdˇepodobnosti setrv´ an´ı yj jsou rovny nule ∀ j ∈ T ⇔ soustava (6) nemá jiné omezené ˇreˇsen´ı neˇz trivi´ aln´ı. Vˇ eta 36. V ˇretˇezci s koneˇcnˇe mnoha stavy vˇsechna yj = 0 a xj jsou tedy jediným ˇreˇsen´ım soustavy (4).

J. ANTOCH, KPMS


2011/2012

Pˇrechodn´ e stavy – pokr. Pozn´ amka 24. V d??? Vˇ eta 37. V ˇretˇezci se stavy E0 , E1 , E2 . . . jsou vˇsechny stavy pˇrechodné ⇔ soustava X∞ ηj = pjν ην , 1 ≤ j < ∞, (6) ν=1

m´ a netriviáln´ı omezené ˇreˇsen´ı.

J. ANTOCH, KPMS


2011/2012

Ising˚ uv model – u ´vodn´ı pojmy G . . . graf V . . . vrcholy (vertexes), |V | = card(V ) E . . . hrany (edges)

pro jednoduchost necht’ kaˇzdý vrchol i m´ a stavy σi ∈ {−1, +1}

obecnˇe mohou být stavy {1, . . . , K } a popisovat ˇsedi ˇci barvy atd. σ = σ1 , . . . , σ|V | popisuje stav systému prostorem stav˚ u S rozum´ıme {−1, +1}|V | , resp. {1, . . . , K }|V |


J. ANTOCH, KPMS

2011/2012

Ising˚ uv model Definice 19. Ising˚ uv model je pravdˇepodobnostn´ı rozdˇelen´ı π(β) na prostoru stav˚ u S = {−1, +1}|V | , kde π(β) = Cβ−1 e −βH(σ)

a H(σ) =

X

(i ,j)∈E

I σi 6= σj

a

Cβ =

X

σ⋆ ∈S

e −βH(σ

⋆)

Funkce H(σ) se ve fyzice nazýv´ a Hamiltoni´ an a reprezentuje energii konfigurace stav˚ u σ. Pozn´ amka 25. Pro β > 0 jsou v daném modelu nejpravdˇepodobnˇejˇs´ı ty a, tj. mnoho soused˚ u má tutéˇz konfigurace stav˚ u σ, pro nˇeˇz je H(σ) mal´ hodnotu stavu (týˇz spin), tj. maj´ı malou energii (informaci). Definice 20. Stˇredn´ım spinem konfigurace σ rozum´ıme 1 X M(σ) = σi i ∈V |V |


J. ANTOCH, KPMS

2011/2012

Modifikace Isingova modelu Klasick´ y Ising˚ uv model: S = {−1, +1}|V |

a

H(σ) =

   1 0 1 1 1 1 0 1 0 ⇒ 3 3 3 1 0 1 2 3 2 

Ising˚ uv model s vnˇ ejˇs´ım polem: S = {−1, +1}|V |

a H(σ, h) =

X

(i ,j)∈E

I σi 6= σj .

   1 1 1 1 1 1 0 0 0 ⇒ 2 1 2 1 0 1 2 2 2 

X

(i ,j)∈E

X I σi 6= σj − h σi . i ∈V

Pro vˇsechna β > 0 a h > 0 jsou hodnoty +1 preferovány pˇred hodnotami −1.

J. ANTOCH, KPMS


2011/2012

Modifikace Isingova modelu – pokraˇ cov´ an´ı Pot˚ uv model pro n´ ahodné z´ aplatov´ an´ı barevných obrázk˚ u“: ” X S = {1, . . . , K }|V | a H(σ) = I σi 6= σj . (i ,j)∈E

Ising˚ uv model pro ˇ cernob´ıl´ e obr´ azky: S = {1, . . . , K }|V |

a

H(σ) =

X

(i ,j)∈E

a f (.) je nˇekterá vhodn´ a vzd´ alenost, napˇr´ıklad: p f (σi , σj ) = σi − σj , p ≥ 1.

f σi , σj ,

Vrcholy typicky reprezentuj´ı pixely a na rozd´ıl od Potova modelu zde chceme, aby sousedi byli podobnˇe ˇsed´ı“, nikoliv identiˇct´ı. ”

J. ANTOCH, KPMS


2011/2012

Aplikace v anal´ yze obrazu Zad´ an´ı: Uvaˇzujme fotku prezentovanou matic´ı pixel˚ u rozmˇer˚ u L1 × L2 . Vrcholy jsou jednotlivé pixely. Hrany spojuj´ı sousedn´ı pixely. Stavy jsou {1, . . . , K }.

Prostor stav˚ u S = {1, . . . , K }V .

Obrázek je reprezentov´ an konfigurac´ı σ = σ1 , . . . , σ|V | ∈ S. Pozorujeme zaˇsumˇenýobraz Y = σ + ε, kde ε1 , . . . , ε|V | ∼ N 0, δ2 .

Probl´ em: Odhadnout skuteˇcný obraz σ pozorujeme-li Y a pˇredpokládáme, ˇze σ má apriorn´ı rozdˇelen´ı Cβ−1 e −βH(σ) . N´ astroj: Bayesovská statistika a Markovské ˇretˇezce (náhodná procházka po grafu).

J. ANTOCH, KPMS


2011/2012

Aplikace v anal´ yze obrazu – pokraˇ cov´ an´ı Sdruˇzené rozdˇelen´ı vektoru (σ, Y) je Q e −βH(σ) · i ∈V exp − (Yi − σi )2 /2δ2 L(σ, Y) ∼ konstanta jeˇz zalezi na (σ, Y) Aposteriorn´ı rozdˇelen´ı je P exp − βH(σ) + 2δ2 )−1 i ∈V 2Yi σi − σi2 L(σ | Y) ∼ funkce jeˇz z´ aleˇz´ı na (σ, β, Y) Dalˇs´ı postup: Generovat z aposteriorn´ıho rozdˇelen´ı (σ | Y). Rozsáhlý výbˇer pak reprezentuje konfigurace které lze povaˇzovat za moˇzné (vˇerohodné) reprezentace obrazu. Alternativou je nalézt nejlepˇs´ı (nejpravdˇepodobnˇejˇs´ı) obraz, tj. b maximalizuj´ıc´ı P(σ | Y). nalézt konfiguraci σ

J. ANTOCH, KPMS


2011/2012

Exponenci´ aln´ı rozdˇ elen´ı – opakov´ an´ı ˇ ˇze n´ ahodn´ a veliˇcina X se ˇr´ıd´ı exponenciáln´ım Definice 21. Rekneme, a-li hustotu tvaru: rozdˇelen´ım (X ∼ Exp(λ)), m´ ( λe −λx , x > 0, λ > 0, f (x; λ) = 0 jinak. Vˇ eta 38. Necht’ X ∼ Exp(λ). Potom F (x) = 1 − e −λx , E X = λ−1 a var X = λ−2 . Vˇ eta 39. Vlastnost zapom´ın´ an´ı. Necht’ X ∼ Exp(λ) a interpretujme ji jako dobu ˇzivota nˇejakého procesu. Potom pravdˇepodobnost jevu, ˇze proces pˇreˇzije dobu y (> 0) za podm´ınky, ˇze doposud pˇreˇzil dobu x(> 0) na dobˇe dosavadn´ıho ˇzivota nez´ aleˇz´ı. • Pro exponenciáln´ı rozdˇelen´ı plat´ı, ˇze je jediné spojité rozdˇelen´ı pro nˇeˇz P(X > x + y | X > x) = P(X > y ). • Mezi diskrétn´ımi rozdˇelen´ımi m´ a tuto vlastnost rozd. geometrické.

J. ANTOCH, KPMS


2011/2012

Funkce intenzity Definice 22. Necht’ náhodn´ a veliˇcina X m´ a hustotu f (x) a distribuˇcn´ı funkci F (x). Potom funkc´ı intenzity nazveme Λ(x) =

f (x) , 1 − F (x)

x ∈ R1 .

Pozn´ amka 26. Necht’ n´ ahodn´ a veliˇcina X , kterou interpretujme jako dobu ˇzivota nˇejakého procesu, m´ a hustotu f (x) a distribuˇcn´ı funkci F (x). Potom pro pravdˇepodobnost okamˇzitého selh´ an´ı plat´ı: P(x < X ≤ x + ∆) F (x + ∆) − F (x) P x < X ≤ x + ∆|X > x = = P(X > x) 1 − F (x) F (x + ∆) − F (x) ∆ ∆→0 f (x) = ≈ ∆ 1 − F (x) ∆ 1 − F (x) Pozn´ amka 27. Necht’ n´ ahodn´ a veliˇcina X ∼ Exp(λ). Potom Λ(x) = λ. Exponenciáln´ı rozdˇelen´ı je jediné spojité rozdˇelen´ı s konstantn´ı intenzitou.

J. ANTOCH, KPMS


2011/2012

Line´ arn´ı proces zrodu a z´ aniku I Uvaˇzujme systém, který m´ a koneˇcnˇe nebo spoˇcetnˇe mnoho stacv˚ u a ze uˇze s nezanedbatelnou ravdˇepodobnost´ı pˇrecházet pouze do stavu En m˚ sousedn´ıch stav˚ u, tj. En → En+1 . . . zrod

En → En−1 . . . z´ anik

Do jiných soused˚ u m˚ uˇze pˇrej´ıt pouze s pravdˇepodobnost´ı nekoneˇcnˇe malou“. ” Pravdˇepodobnosti pˇrechod˚ u v ˇcasovém intervalu (t, t + h) necht’ jsou: P En → En+1 = λn h + o(h) P En → En−1 = µn h + o(h) P En → En±j , j > 1 = o(h)

J. ANTOCH, KPMS


2011/2012

Line´ arn´ı proces zrodu a z´ aniku II Oznaˇcme Pn (t) pravdˇepodobnost toho, ˇze systém je v ˇcase t ve stavu En . C´ılem je urˇcit Pn (t + h) a naj´ıt pn = limt→∞ Pn (t). Pravdˇepodobnosti Pn (t) splˇ nuj´ı n´ asleduj´ıc´ı systém diferenciáln´ıch rovnic: P0′ (t) = −λ0 P0 (t) + µ1 P1 (t) (7) ′ Pn (t) = − λn + µn Pn (t) + µn+1 Pn+1 (t) + λn−1 Pn−1 (t), n ≥ 1 Je-li systém v ˇcase 0 ve stavu Ei , pak jsou splnˇeny následuj´ıc´ı poˇcáteˇcn´ı podm´ınky, tj. Pi (0) = 1 a Pn (0) = 0 pro n 6= i . Pravdˇepodobnosti pn existuj´ı, nez´ avis´ı na poˇc´ ateˇcn´ıch podm´ınkách a vyhovuj´ı systému line´ arn´ıch rovnic, který dostaneme z (7) poloˇz´ıme-li Pn′ (t) = 0, n ≥ 0, tj. soustavˇe 0 = −λ0 p0 + µ1 p1 0 = − λn + µn pn + µn+1 pn+1 + λn−1 pn−1 n ≥ 1

(8)


J. ANTOCH, KPMS

2011/2012

Line´ arn´ı r˚ ust Model. Pˇredpokládejme, ˇze systém je sloˇzen z prvk˚ u, které se mohou dˇelit i zanikat. Za malý ˇcasový interval délky h necht’ pravdˇepodobnost toho, ˇze se jeden prvek rozdˇel´ı na dva rovna je rovna λh + o(h), a pravdˇepodobnost, ˇze zanikne, je rovna µh + o(h), pˇriˇcemˇz λ, µ jsou konstanty, které charakterizuj´ı prvky. Pozn´ amka 28. Je-li chov´ an´ı prvk˚ u nez´ avislé, pak jde o model mnoˇzen´ı a z´ aniku s parametry λn = nλ, µn = nµ. Vˇ eta 40. Soustava (7) m´ a n´ asleduj´ıc´ı ˇreˇsen´ı: P0 (t) = A(t)

kde

n−1 Pn (t) = 1 − A(t) 1 − B(t) B(t) , n≥1

µ e (λ−µ)t − 1 , A(t) = λe (λ−µ)t − µ

λ e (λ−µ)t − 1 B(t) = . λe (λ−µ)t − µ


J. ANTOCH, KPMS

2011/2012

Model u ´stˇredny s nekoneˇ cnˇ e mnoha linkami Pˇr´ıklad 8. Mˇejme u ´stˇrednu s nekoneˇcnˇe mnoha telefon´ımi linkami. ˇ Rekneme, ˇze se systém nach´ az´ı ve stavu En , je-li obsazeno právˇe n linek. Pˇredpokládejme, ˇze: Pravdˇepodobnost jevu, ˇze jeden hovor skonˇc´ı v pr˚ ubˇehu intervalu (t, t + h), je rovna µh + o(h). Délky hovor˚ u jsou vz´ ajemnˇe nez´ avislé. Pravdˇepodobnost jevu, ˇze v intervalu (t, t + h) bude obsazena nová linka, je λh + o(h). ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze limitn´ı pravdˇepodobnosti pn se ˇr´ıd´ı Poissonovým rozdˇelen´ım s parametrem λ/µ.

J. ANTOCH, KPMS


2011/2012

Model telefonn´ı dvojbudky s neomezenou frontou ?K? a m˚ uˇze souˇcasnˇe obsluhovat Pˇr´ıklad 9. Uvaˇzujme stanici obsluhy, kter´ nejvýˇse dva zákazn´ıky, napˇr. telefonn´ı dvojbudku. Z´ akazn´ıci, kteˇr´ı ˇ nemohou být obslouˇzeni, se ˇrad´ı do jediné neomezené fronty. Rekneme, akazn´ık˚ u (v obsluze i ve ˇze se systém nacház´ı ve stavu En , je-li poˇcet z´ frontˇe) právˇe n. Pˇredpokládejme, ˇze: Pravdˇepodobnost jevu, ˇze z´ akazn´ık, který je v ˇcase t obsluhován, bude v intervalu (t, t + h) obslouˇzen, je rovna µh + o(h). Délky obsluhy jsou vz´ ajemnˇe nez´ avislé. Pravdˇepodobnost, ˇze v intervalu (t, t + h) pˇrijde nový zákazn´ık, je λh + o(h). ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze pokud λ < 2µ, pak pro limitn´ı pravdˇepodobnosti pn plat´ı n 2µ − λ λ 1

J. ANTOCH, KPMS


2011/2012

Model parkoviˇstˇ e pˇred MFF bez fronty Pˇr´ıklad 10. Uvaˇzujme parkoviˇstˇe automobil˚ u pˇred MFF UK s kapacitou N m´ıst. Stavem systému je poˇcet aut na parkoviˇsti, fronta se netvoˇr´ı. Pˇredpokládejme, ˇze: Pravdˇepodobnost jevu, ˇze automobil, který v ˇcase t parkuje, odjede v intervalu (t, t + h), je rovna µh + o(h). Délky stán´ı jsou vzájemnˇe nez´ avislé. Pravdˇepodobnost jevu, ˇze v intervalu (t, t + h) pˇrijede nový automobil, je λh + o(h). ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze limitn´ı pravdˇepodobnosti pn se ˇr´ıd´ı useknutým Poissonovým rozdˇelen´ım s parametrem λ/µ.

J. ANTOCH, KPMS


2011/2012

Model telefonn´ı budky s omezenou frontou Pˇr´ıklad 11. Uvaˇzujme stanici obsluhy, kter´ a m˚ uˇze obsluhovat nejvýˇse jednoho zákazn´ıka, napˇr. telefonn´ı budku. Z´ akazn´ıci, kteˇr´ı nemohou být ˇ ˇze se obslouˇzeni, se ˇrad´ı do jediné omezené fronty délky N. Rekneme, systém nacház´ı ve stavu En , je-li poˇcet z´ akazn´ık˚ u (v obsluze i ve frontˇe) pr´ avˇe n. Pˇredpokládejme, ˇze: Pravdˇepodobnost jevu, ˇze z´ akazn´ık, který je v ˇcase t obsluhován, bude v intervalu (t, t + h) obslouˇzen, je rovna µh + o(h). Délky obsluhy jsou vz´ ajemnˇe nez´ avislé. Pravdˇepodobnost jevu, ˇze v intervalu (t, t + h) pˇrijde nový zákazn´ık, je λh + o(h). ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze pro limitn´ı pravdˇepodobnosti pn plat´ı n λ λ−µ p0 , kde p0 = µN+1 N+2 . pn = µ λ − µN+2

J. ANTOCH, KPMS


2011/2012

Probl´ em jednoho oprav´ aˇre a mnoha stroj˚ u ?K? ˇ Pˇr´ıklad 12. Mˇejme M stroj˚ u obsluhovaných jedn´ım opraváˇrem. Rekneme, u. ˇze se systém nacház´ı ve stavu En , jestliˇze nepracuje právˇe n stroj˚ Pˇredpokládejme, ˇze: Pravdˇepodobnost jevu, ˇze stroj který je v ˇcase t opravován, zaˇcne v intervalu (t, t + h) pracovat, je rovna µh + o(h). Délky oprav jsou vzájemnˇe nez´ avislé. Pravdˇepodobnost jevu, ˇze stroj který v ˇcase t pracoval, se v intervalu (t, t + h) porouch´ a, je rovna λh + o(h). ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze limitn´ı pravdˇepodobnosti pM−k se ˇr´ıd´ı useknutým Poissonovým rozdˇelen´ım s parametrem µ/λ, tj. pro k = 1, . . . , M XM 1 µ k −1 1 µ k pM−k = pM , kde pM = 1 + k=1 k! λ k! λ

J. ANTOCH, KPMS


2011/2012

Model popisuj´ıc´ı pr´ aci nˇ ekolika sv´ aˇreˇ c˚ u ?K? Pˇr´ıklad 13. Mˇejme N sváˇreˇc˚ u, kteˇr´ı nez´ avisle na sobˇe ve v´ıceménˇe ˇ n´ ahodných intervalech odeb´ıraj´ı proud. Rekneme, ˇze se systém nacház´ı ve avˇe n sv´ aˇreˇc˚ u. stavu En , jestliˇze pracuje pr´ Pˇredpokládejme, ˇze: Pravdˇepodobnost jevu, ˇze sv´ aˇreˇc který je v ˇcase t pracuje, pˇrestane pracovat v intervalu (t, t + h), je rovna µh + o(h). Délky sváˇren´ı jsou vz´ ajemnˇe nez´ avislé. Pravdˇepodobnost jevu, ˇze sv´ aˇreˇc, který v ˇcase t nepracoval, v intervalu (t, t + h) pracovat zaˇcne, je rovna λh + o(h). ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze limitn´ı pravdˇepodobnosti pn se ˇr´ıd´ı binomickým rozdˇelen´ım Bi N, µ/(µ + λ) N−n n N µ λ pn = , n = 0, 1, . . . , N. n µ+λ µ+λ

J. ANTOCH, KPMS


2011/2012

Model kinetiky nevratn´ e chemick´ e reakce Pˇr´ıklad 14. Mˇejme látku A (reagent), jej´ıˇz molekuly se nevratnˇe pˇremˇen ˇuj´ı v molekuly látky B (produkt), pˇriˇcemˇz rychlost reakce je dána konstantou κ > 0. Necht’ koncentrace reagentu A v ˇcase t je pˇredstavována náhodnou veliˇcinou X (t), pˇriˇcemˇz X (0) = n0 . Z fyzikáln´ı podstaty pˇredpokl´ adejme, ˇze: Pst jevu, ˇze se zmˇen´ı jedna molekuly za (t, t + h) v pˇr´ıpadˇe, kdy se avˇe n0 − n molekul, je nκh + o(h). za ˇcas (0, t) zmˇenilo pr´ Pst zmˇeny v´ıce neˇz jedné molekuly za (t, t + h) je nulová. Látky A a B jsou statisticky nez´ avislé. Inverzn´ı reakce B → A nast´ av´ a s pravdˇepodobnost´ı nula.

´ Ukoly:

Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze limitn´ı pravdˇ epodobnosti pn se ˇr´ıd´ı binomickým rozdˇelen´ım Bi n0 , e −κt .

J. ANTOCH, KPMS

x


2011/2012

J. ANTOCH, KPMS


2011/2012

Poisson˚ uv proces jako model zrodu a z´ aniku Pˇr´ıklad 15. Uvaˇzujme fyzik´ aln´ı systém, který podléh´ a okamˇzitým zmˇenám zp˚ usobeným nahodilými vlivy, napˇr. telefonn´ı hovory, rozpad atom˚ u apod. Oznaˇcme Pn (t) pravdˇepodobnost jevu, ˇze za dobu t nastalo pr´ avˇe n zmˇen. Pˇredpokládejme: Stacionárn´ı proces, tj. ˇze tato situace nez´ avis´ı na poloze intervalu a délce t na ˇcasové ose. Bez ohledu na poˇcet zmˇen v intervalu (0, t) necht’ pst jevu, ˇze v intervalu (t, t + h) nastane jedna zmˇena je λh + o(h), zat´ımco pst jevu, ˇze nastane v´ıce zmˇen je o(h). Pozn´ amka 29. Vˇsimnˇete si, ˇze zmˇeny v intervalech (0, t) a (t, t + h) jsou nezávislé. ´ Ukoly: Sestavte diferenciáln´ı rovnice pro pravdˇepodobnosti Pn (t). Ukaˇzte, ˇze pravdˇepodobnosti Pn (t) se ˇr´ıd´ı Poissonovým rozdˇelen´ım s parametrem λt.

J. ANTOCH, KPMS


2011/2012

Syst´ emy hromadn´ e obsluhy Definice 23. Syst´ emem hromadn´ e obsluhy budeme rozumˇet: Jednu nebo v´ıce paraleln´ıch stanic obsluhy (linek), k nimˇz pˇricházej´ı zákazn´ıci, kteˇr´ı obsluhu poˇzaduj´ı a po obslouˇzen´ı systém opouˇstˇej´ı. Zákazn´ıci, kteˇr´ı nemohou být okamˇzitˇe obslouˇzeni (protoˇze vˇsechny stanice obsluhy jsou obsazené) se ˇrad´ı do jediné fronty. Doby mezi pˇr´ıchody po sobˇe jdouc´ıch z´ akazn´ık˚ u jsou nezávislé stejnˇe rozdˇelené náhodné veliˇciny s rozdˇelen´ım A. Doby obslohy, do nichˇz se nezapoˇc´ıt´ av´ a doba ˇcekán´ı ve frontˇe) jsou nezávislé stejnˇe rozdˇelené n´ ahodné veliˇciny s rozdˇelen´ım B. Pozn´ amka 30. Rozdˇelen´ı dob pˇr´ıchod˚ u se zpravidla pˇredpokládá: exponenciáln´ı . . . M (Markovian) deterministické . . . D (Deterministic) obecné . . . G (General) Erlangovo, tj. Γ(n, λ) . . . En (Erlang)

J. ANTOCH, KPMS


2011/2012

M/M/1, M/M/c a M/M/∞ Definice 24. Systémy hromadné obsluhy M/M/x jsou charakterizovány t´ım, ˇze pˇr´ıchody zákazn´ık˚ u se ˇr´ıd´ı homogenn´ım Poissonovým procesem a doby obsluhy maj´ı exponenci´ aln´ı rozdˇelen´ı. Vˇ eta 41. Systémy M/M/x lze popsat obecným procesem zrodu a z´ aniku. Pozn´ amka 31. Pro model: M/M/1 : λj = λ, 0 ≤ j < ∞ a µj = µ, 1 ≤ j < ∞ M/M/c : λj = λ, 0 ≤ j < ∞, µj = jµ, 0 ≤ j ≤ c a µj = cµ, c ≤ j < ∞

M/M/∞ : λj = λ, 0 ≤ j < ∞, µ0 = 0 a µj = jµ, 0 ≤ j < ∞ Bl´ıˇze viz pˇr´ıklad o telefonn´ı u ´stˇrednˇe s nekoneˇcnˇe mnoho linkami nebo pˇr´ıklad o dvojbudce s neomezenou frontou, tj. pˇr´ıklady 8 a 9.

J. ANTOCH, KPMS


2011/2012

M/M/1, M/M/c a M/M/∞ Vˇ eta 42. Pro systémy M/M/x plat´ı: M/M/1 : limitn´ı pravdˇepodobnosti pn se ˇr´ıd´ı geometrickým rozdˇelen´ım s parametrem 1 − λ/µ. M/M/c : limitn´ı pravdˇepodobnosti pn se ˇr´ıd´ı useknut´ ym Poissonovým rozdˇelen´ım s parametry c + 1, λ/µ .

M/M/∞ : limitn´ı pravdˇepodobnosti pn se ˇr´ıd´ı Poissonovým rozdˇelen´ım s parametrem λ/µ. Vˇ eta 43. Pro systém M/M/c plat´ı, ˇze odchody ze stabilizovaného systému s neomezenou frontou (beze ztr´ at, odpad´ an´ı apod.) any homogenn´ım s parametry λ (vstup) a µ (výstup) jsou opˇet pops´ Poissonovým procesem s parametrem λ! Pozn´ amka 32. Systémy M/M/c se tedy daj´ı dobˇre kombinovat a za pˇredpokladu stabilizovatelnosti se chod výsledného systému dá popsat vhodným Markovským procesem.

J. ANTOCH, KPMS


2011/2012

M/M/1 Pozn´ amka 33. Uvaˇzujme model M/M/1. Z vˇety 42 v´ıme, ˇze limitn´ı an´ı popisuj´ıc´ı poˇcet zákazn´ık˚ u pravdˇepodobnosti pn ustáleného chov´ v ustáleném provozu systému se ˇr´ıd´ı geometrickým rozdˇelen´ım s parametrem 1 − λ/µ. Odtud ze z´ akladn´ıch vlastnost´ı geometrického rozdˇelen´ı vyplývá, ˇze: Stˇredn´ı poˇcet zákazn´ık˚ u v systému je µλ 1 − µλ 2 Rozptyl poˇctu zákazn´ık˚ u v systému je µλ 1 − µλ 2 P Stˇredn´ı délka fronty je j jpj+1 = µλ 1 − µλ

Pozn´ amka 34. Vˇsimnˇeme si, ˇze rozd´ıl mezi stˇredn´ım poˇctem zákazn´ık˚ u v systému a stˇredn´ı dobou fronty je λ − µ a nikoliv 1. Rozmyslete!

J. ANTOCH, KPMS


2011/2012

M/M/1 – pokraˇ cov´ an´ı Pozn´ amka 35. Uvaˇzujme model M/M/1. akazn´ıkem, který se zaˇradil jako Potom doba Tn strávená v systému z´ n-tý se ˇr´ıd´ı gamma rozdˇelen´ım Γ(n + 1, µ), nebot’ hledaný ˇcas se skládá ze zbytkového ˇcasu obsluhovaného z´ akazn´ıka a ˇcas˚ u obsluhy vˇsech ˇcekaj´ıc´ıch ve frontˇe, vˇcetnˇe naˇseho z´ akazn´ıka. Rozdˇelen´ı doby ˇcekán´ı T jednoho n´ ahodnˇe vybraného zákazn´ıka je podle vˇety o u ´plné pravdˇepodobnosti smˇes´ı rozdˇelen´ı Tn s vahami danými pravdˇepodobnostmi ustáleného provozu pn . Ukaˇzte, ˇze: P(T ≤ t) = 1 − e −(µ−λ)t , takˇze stˇredn´ı doba setrván´ı v systému je rovna

t ≥ 0, 1 µ−λ .

J. ANTOCH, KPMS


2011/2012

M/M/1 + M/M/1 = tandem Sériové propojen´ı dvou systém˚ u obsluhy M/M/1 se nazývá tandemov´ e uspoˇr´ ad´ an´ı. Podrobnosti jeˇstˇe budou doplnˇeny.

J. ANTOCH, KPMS


Simulace M/M/1 for (i in 1:maxim´ aln´ ı poˇ cet z´ akazn´ ık˚ u){ if (aktcas >= maxim´ aln´ ı ˇ cas){break} # simulace konˇ c´ ı, pokud je dosaˇ zeno maxim´ aln´ ıho ˇ casu while (min(ˇ casy napl´ anovan´ ych ud´ alost´ ı) < ˇ cas pˇ r´ ıchodu dalˇ s´ ıho z´ akazn´ ıka){ # nˇ ekdo skonˇ c´ ı obsluhu dˇ r´ ıv, neˇ z doraz´ ı dalˇ s´ ı z´ akazn´ ık aktcas <- min(ˇ casy napl´ anovan´ ych ud´ alost´ ı) stav <- stav - 1 z´ aznam ud´ alosti, odebr´ an´ ı z´ akazn´ ıka z~obsluhy # zaˇ c´ atek obsluhy dalˇ s´ ıho z´ akazn´ ıka # (uvolnila se obsluˇ zn´ a stanice) if (fronta nen´ ı pr´ azdn´ a){ d´ elka obsluhy <- obsluha(aktcas,stav,stanice) zaˇ c´ atek obsluhy z´ akazn´ ıka, aktualizace fronty } } # nejbliˇ zˇ s´ ı ud´ alost´ ı je pˇ r´ ıchod i-t´ eho z´ akazn´ ıka aktcas <- ˇ cas pˇ r´ ıchodu dalˇ s´ ıho z´ akazn´ ıka stav <- stav + 1 z´ aznam ud´ alosti # pokud je voln´ a stanice, bude z´ akazn´ ık rovnou obsluhov´ an if (nˇ ekter´ a stanice je voln´ a){zaˇ c´ atek obsluhy z´ akazn´ ıka} else{zaˇ razen´ ı z´ akazn´ ıka na konec fronty} # urˇ cen´ ı ˇ casu pˇ r´ ıchodu dalˇ s´ ıho z´ akazn´ ıka pˇ r´ ıchod dalˇ s´ ıho z´ akazn´ ıka <- aktcas + prichod(aktcas,stav)}

2011/2012


J. ANTOCH, KPMS

2011/2012

M/M/1 příchod stav + 1

aktuální čas (událost č. k)

odchod stav - 1

nejbližší událost (č. k+1)

příchod stav + 1

další událost (č. k+2)

Schéma pr˚ ubˇehu uvaˇzovaného simulaˇcn´ıho algoritmu.


J. ANTOCH, KPMS

2011/2012

M/M/1

20 15 10 5 0

Pocet zakazniku v systemu

Vyvoj systemu v case

0

100

200

300

400

500

Cas

ˇ Casov´ y vývoj poˇctu z´ akazn´ık˚ u v systému M/M/1 s parametry λ = 1 a µ = 1.2.


J. ANTOCH, KPMS

2011/2012

M/M/1

10 20 30 40 50 0

Pocet zakazniku

Histogram dob cekani zakazniku, kteri museli na zacatek obsluhy cekat kladnou dobu

0

2

4

6

8

10

12

Doba cekani

Histogram doby ˇcekán´ı na zaˇc´ atek obsluhy tˇech zákazn´ık˚ u, kteˇr´ı museli ˇcekat kladnou dobu (v systému M/M/1 s parametry λ = 1 a µ = 1.2).


J. ANTOCH, KPMS

2011/2012

M/M/1

0.05

0.10

0.15

skutecna hodnota metoda MLE metoda podilu casu

0.00

Pravdepodobnost

0.20

Odhady pravdepodobnosti stacionarniho rozdeleni

0

5

10

15

20

Stav systemu

Srovnán´ı metod odhadu pravdˇepodobnost´ı stacionárn´ıho rozdˇelen´ı v systému M/M/1 s parametry λ = 1 a µ = 1.2.

J. ANTOCH, KPMS


2011/2012

O spolehlivosti lid´ı

Human error is here to stay Anonymous

J. ANTOCH, KPMS


2011/2012

Pˇredpovˇ ed’ spolehlivosti Pˇredpovˇed’ spolehlivosti je proces, jehoˇz c´ılem uˇcit, jaké zmˇeny (opravy) komponent, resp. blok˚ u systému podniknout, aby se zlepˇsila spolehlivost celého systému. C´ıle Porovnat r˚ uzná ˇreˇsen´ı Vyhodnotit spolehlivost pro r˚ uzné konfigurace Odhalit slabé body navrˇzeného ˇreˇsen´ı Vylepˇsit návrh systému N´ astroje 1

Klasické spolehlivostn´ı techniky a modely

2

Analýza stromu poruch (fault tree analysis – FTA)

3

Markovské modelován´ı spolehlivosti

4

Pouˇzit´ı pravdˇepodobnostn´ıch strom˚ u atd.

J. ANTOCH, KPMS


Stˇredn´ı doba do poruchy Motto: Selhán´ı systému nemus´ı být zp˚ usobeno pouze chybami materiálu, hardware ˇci software, ale také lidskými chybami. Praktické zkuˇsenosti ukazuj´ı, ˇze lidské kon´ an´ı m˚ uˇze být pops´ ano podobnˇe jako spolehlivost stroj˚ u, výrobk˚ u apod., tj. pomoc´ı Y . . . doby do (lidské) s chyby odpov´ıdaj´ıc´ı F (t) = P(Y ≤ t) . . . distribuˇcn´ı funkc´ı f (t) = F ′ (t) . . . hustotou

R(t) = 1 − F (t) = P(Y > t) . . . funkc´ı spolehlivosti (pˇreˇz´ıván´ı) f (t) f (t) λH (t) = R(t) = 1−F (t) . . . intenzitou poruch t (hazard rate function), kde P(t < Y ≤ t + ∆ | Y > t) ≈ ∆ · λH (t)

2011/2012


J. ANTOCH, KPMS

2011/2012

Stˇredn´ı doba do poruchy Snadno lze ukázat, ˇze mimo jiné plat´ı: R(t) = P(Y > t) = e −

Rt 0

λH (u) du

,

coˇz m˚ uˇze být pouˇzito k predikci spolehlivosti, pokud se doby mezi chybami (poruchami) ˇr´ıd´ı nˇekterým zn´ amým rozdˇelen´ım. Odtud lze z´ıskat obecný pˇredpis pro stˇredn´ı dobu mezi chybami mean time to error (MTTE) pomoc´ı Z ∞ R Z ∞ t e − 0 λH (u) du dt R(t) dt = MTTE = 0

0

Mezi nejtypiˇctˇejˇs´ı rozdˇelen´ı uˇz´ıvan´ a ve spolehlivosti patˇr´ı exponenciáln´ı Weibullovo gamma lognormáln´ı

J. ANTOCH, KPMS


Vybran´ e c´ıle statisick´ e inference Pˇredpokládejme, ˇze sledujeme ˇcasy mezi chybami a m˚ uˇzeme o nich usuzovat, ˇze jsou nezávislé. Mezi hlavn´ı c´ıle statistické inference patˇr´ı odhadnout základn´ı charakteristiky daného modelu a urˇcit pro nˇe odpov´ıdaj´ıc´ı intervaly spolehlivosti, tj. odhadnout parametry zvoleného rozdˇelen´ı odhadnout stˇredn´ı dobu do poruchy E Y funkci spolehlivosti R(t) v ˇcase t p % kvantil rozdˇelen´ı poruch (chyb) Moˇznost´ı je celá ˇrada, v z´ asadˇe parametrické a neparametrické.

2011/2012

J. ANTOCH, KPMS


Weibullovo rozdˇ elen´ı Hustota Weibullova rozdˇelen´ı s parametry β a ν má tvar:   ν y ν−1 exp − y /β ν , y ≥ 0, f (y ; β, ν) = β β 0, y < 0, kde E Y = β Γ 1 + ν1 a var Y = β 2 Γ 1 + ν2 − Γ2 1 + ν1

MLE βb and νb parametr˚ u β a ν dostaneme jako ˇreˇsen´ı soustavy rovnic 1/bν 1 Xn , βb = Yiνb i =1 n Pn νb 1 1 Xn =1 Yi log Yi − = iP log Yi , n νb i =1 νb n i =1 Yi

2011/2012


J. ANTOCH, KPMS

2011/2012

Weibullovo rozdˇ elen´ı MLE E Y is βb Γ 1 + urˇc´ı pro

1

νb

. Interval spolehlivosti pro E Y se nejprve

1 log E Y = log β + log Γ 1 + ν = η + log Γ(1 + δ) / a teprve potom transformuje pro E Y . b a pro jeho asymptotický rozplyl MLE pro log E Y je ηb + log Γ(1 + δ) V (δ)/n plat´ı b V (δ) = n var ηb + n ψ 2 (1 + δ) var δb + 2n ψ(1 + δ) cov (b η , δ) Asymptotický (1 − α) 100% konfidenˇcn´ı interval pro E Y má hranice: q n o b βb Γ 1 + 1/b ν exp − u1−α/2 V (δ)/n q o n b b β Γ 1 + 1/b ν exp u1−α/2 V (δ)/n

J. ANTOCH, KPMS


2011/2012

Weibullovo rozdˇ elen´ı d = exp − (t/β) b νb . MLE odhad funkce pˇreˇz´ıv´ an´ı R(t) je R(t) Asymptotický (1 − α) 100 % konfidenˇcn´ı interval má tvar d −u d +u R(t) σ b , R(t) σ b 1−α/2 R(t) 1−α/2 R(t) ,

d s parametry nahrazenými kde σ bR(t) je standardn´ı odchylka R(t) MLE odhady etc. n o MLE p % kvantilu tp je tbp = βb exp 1 log − log (1 − p) . νb

Asymptotický (1 − α) % konfidenˇcn´ı interval lze zaloˇzit na log tp = log β +

etc. etc.

1 log − log(1 − p) = η + δ log − log(1 − p) . ν


J. ANTOCH, KPMS

Weibullovo rozdˇ elen´ı (pˇr´ıklad) 0.58 1.39 0.76 0.63

0.29 1.89 0.64 0.87

0.93 0.28 2.12 0.57

Y = 0.963 a σn2 = 0.29516 βb = 1.089, kde var βb = 0.01868 νb = 1.876, kde var νb = 0.10698 b νb) = 0.01400 cov (β, Ed Y = 0.967 [ b νb } = 0.426 R(1) = exp{−(1/β)

1.11 0.44 0.25 0.64

1.26 1.57 1.36 1.68

[ = 0.007968 var R(1) asymptotický 95% konfidenˇcn´ı interval pro R(1) je bud’ (0.251, 0.601) nebo (0.267, 0.603)

2011/2012


J. ANTOCH, KPMS

Vybran´ e dalˇs´ı c´ıle statistick´ e inference Pˇredpokládejme, ˇze jsme napozorovali doby mezi poruchami {Yi }, o nichˇz m˚ uˇzeme pˇredpokl´ adat, ˇze tvoˇr´ı n´ ahodný výbˇer. Statistika dále nab´ız´ı: testy o typu rozdˇelen´ı testy o parametrech zvoleného rozdˇelen´ı testy o zmˇenách modelu etc. etc.

2011/2012


J. ANTOCH, KPMS

2011/2012

Vybran´ e dalˇs´ı c´ıle statistick´ e inference Pˇredpokládejme, ˇze jsme napozorovali doby mezi poruchami {Yi }, o nichˇz m˚ uˇzeme pˇredpokl´ adat, ˇze tvoˇr´ı n´ ahodný výbˇer. Statistika dále nab´ız´ı: testy o typu rozdˇelen´ı testy o parametrech zvoleného rozdˇelen´ı testy o zmˇenách modelu etc. etc.

ˇ MÍT ROZMYSLENO ˇ CO BYSTE MELI VY? CO TYTO POJMY A TESTY ZNAMENAJÍ !

J. ANTOCH, KPMS


2011/2012

FTA – Anal´ yza stromu poruch Formáln´ı metoda pro výpoˇcet sloˇzitých pravdˇepodobnost´ı pomoc´ı “kombinován´ı” jednoduchých, tzv. z´ akladn´ıch, ud´ alost´ı Historie 1956 – Bell ve snaze zvýˇsit spolehlivost balistických stˇrel Dnes – Aeronautika, automobilový pr˚ umysl, spolehlivost sloˇzitých pr˚ umyslových systém˚ u jako jsou atomové elektr´ arny ˇci cognitive sciences pro modelov´ an´ı lidského chov´ an´ı Moˇ znosti Graphická reprezentace systému Odhalen´ı zdroj˚ u moˇzných pot´ıˇz´ı Výpoˇcet pravdˇepodobnosti poruch Etc., etc.

J. ANTOCH, KPMS


2011/2012

Re´ aln´ y, byt’ uˇ cebnicov´ y, probl´ em Vaˇs´ım u ´kolem je provést n´ asleduj´ıc´ı u ´kol, který se skl´ adá z “nezávislých” pod´ uloh X a Y . Aby byl u ´kol splnˇen, mus´ı být obˇe pod´ ulohy provedeny bezchybnˇe. Pod´ uloha X se sklád´ a z dvou pod´ ukol˚ u X1 a X2 . Pro splnˇen´ı n jednoho z tˇechto pod´ ukol˚ u. pod´ ulohy X staˇc´ı splnˇen´ı alespoˇ Pod´ uloha Y se sklád´ a z tˇr´ı pod´ ukol˚ u Y1 , Y2 a Y3 . Aby byla splnˇena ukoly mus´ı výt vyˇreˇseny pod´ uloha Y správnˇe, vˇsechny tˇri pod´ správnˇe. Pod´ ukohy X1 a Y1 se skl´ adaj´ı ze dvou krok˚ u, ˇreknˇeme x1 a x2 , resp. y1 a y2 . Pro korektn´ı splnˇen´ı kaˇzdého z tˇechto pod´ ukol˚ u mus´ı být splnˇeny korektnˇe oba kroky. ´ Ukol pro v´ as: Navrhnˇete model pro výˇse popsanou situaci a spoˇctˇete pravdˇepodobnost bezchybného splnˇen´ı u ´kolu.

J. ANTOCH, KPMS


Re´ aln´ y, byt’ uˇ cebnicov´ y, probl´ em

2011/2012

J. ANTOCH, KPMS



2011/2012

J. ANTOCH, KPMS



2011/2012

J. ANTOCH, KPMS


2011/2012

Z´ akladn´ı principy FTA Strom poruch se skládá z u ´rovn´ı spojených logickými branami popisuj´ıc´ımi vytváˇren´ı neˇz´ adouc´ıch ud´ alost´ı. Z´ akladn´ı stavebn´ı kameny Logick´ e br´ any (logical gates) Z´ akladn´ı ud´ alosti (basic events), umoˇzn ˇuj´ıc´ı “rozklad” problému Neˇ z´ adouc´ı ud´ alosti (undesired events): pˇresnˇe definované negativn´ı události jeˇz jsou pro daný problém jednoznaˇcné


J. ANTOCH, KPMS

Reprezentace logick´ ych bran Symbol

N´ azev

Popis

OR gate

Ud´ alost S nastane tehdy, nastane-li libovoln´ a z událost´ı E1 nebo E2

AND gate

Ud´ alost S nastane nastanou-li obˇe ud´ alosti E1 i E2

2011/2012

J. ANTOCH, KPMS


Reprezentace logick´ ych bran Symbol

N´ azev

Popis

Exclusive OR gate

Ud´ alost S nastane, jestliˇze jedna z ud´ alost´ı E1 nebo E2 nastane a druh´ a nikoliv

Priority AND gate

Ud´ alost S nastane, jestliˇze ud´ alosti E1 a E2 nastanou v daném poˇrad´ı

2011/2012


J. ANTOCH, KPMS

Reprezentace ud´ alost´ı Symbol

N´ azev

Popis

Basic event

Nejniˇzˇs´ı u ´roveˇ n chyb. Mezi základn´ı ud´ alosti patˇr´ı poruchy individuáln´ıch komponent, liské chyby ˇci chyby software.

Conditional event

House event

Podm´ınˇené ud´ alosti závis´ı na z´ akladn´ıch poruch´ ach a jsou ve stromu poruch um´ıstˇeny nad branami. Ud´ alost kter´ a m˚ uˇze být zapnuta nebo vypnuta. Je.li zapnuta, ze odpov´ıdaj´ıc´ı pravdˇepodobnost výskytu poruchy nastavena na 1, jinak je nastavena na 0.

2011/2012


J. ANTOCH, KPMS

Reprezentace ud´ alost´ı Symbol

N´ azev Undeveloped event Triangle in Triangle out

Popis Tato ud´ alost nebyla, z jakéhokoliv d˚ uvodu, definov´ ana. Uˇz´ıv´ a se pro naznaˇcen´ı opakován´ı ˇc´ asti stromu poruch nebo jako pokraˇcov´ an´ı na dalˇs´ı stranˇe. Pouˇz´ıv´ a se ve spojen´ı s blokem Triangle in.

2011/2012

J. ANTOCH, KPMS


2011/2012

“Cut sets” Definice: Cut set may be described as a collection of basic events that will cause the top fault tree event to occur. A cut set is said minimal if it cannot be further reduced but it can still to ensure the occurence of the top fault tree event.

J. ANTOCH, KPMS


Jak nal´ ezt “cut sets”? “Cut sets” se zpravidla hledaj´ıc´ı pomoc´ı n´ astroj˚ u Boolovské algebry. Pro kaˇzdý jev je definovan´ a boolovsk´ a promˇenn´ a. Boolovský operátor “·” je pˇriˇrazen br´ anˇe AND Gate Boolovský operátor “+” je pˇriˇrazen br´ anˇe OR Gate Fault Tree je zjednoduˇsen pomoc´ı pravidel Boolovsk´ e algebry.

2011/2012

J. ANTOCH, KPMS


Pravidla Boolovsk´ e algebry

2011/2012


J. ANTOCH, KPMS

2011/2012

Kvantitativn´ı anal´ yza Pravdˇepodobnost neˇz´ adouc´ı ud´ alosti je d´ ana vztahem P(Undesired Event) =P C1 + C2 + . . . + Cn Xn X = P C1 · Cj P Ci − i <j i =1 n+1 + . . . + (−1) P C1 · . . . Cn Bonferroniho approximace pro mal´ a P(Ci ) Xn P(Undesired Event) ≈

i =1

resp. Xn

i =1

P Ci ,

Xn X P Ci − P Ci ·Cj ≤ P(Undesired Event) ≤ i <j

i =1

P Ci

J. ANTOCH, KPMS


Re´ aln´ y, byt’ uˇ cebnicov´ y, probl´ em, naposledy

2011/2012

J. ANTOCH, KPMS


2011/2012

V´ yhody a nev´ yhody FTA V´ yhody Deduktivnˇe identifikuje poruchy (zdroje poruch) Slouˇz´ı jako grafický n´ astroj pro rozhodov´ an´ı Poskytuje náhled na chov´ an´ı celého systému Je schopna se vypoˇrádat i s velmi sloˇzitými systémy Dovoluje se soustˇredit v daném ˇcase na specifické chyby. Dovoluje jak kvantitativn´ı tak kvalitativn´ı analýzu problému. Nev´ yhody Analytik mus´ı problému rozumˇet skuteˇcnˇe do hloubky Je nároˇcná na ˇcas i n´ aklady Nen´ı snadné provést jej´ı nez´ avislou kontrolu Typicky pracuje pouze s ud´ alostmi typu ANO/NE a nen´ı snadné s jej´ı pomoc´ı popsat systémy, které pracuj´ı tzv. “nap˚ ul” (ˇcásteˇcnˇe)

J. ANTOCH, KPMS


Jin´ y uˇ cebnicov´ y pˇr´ıklad

Neˇ z´ adouc´ı ud´ alost: Zmáˇckneme vyp´ınaˇc a lampa se nerosv´ıt´ı. ´ Ukol pro v´ as: Navrhnˇete strom poruch a spoˇctˇete pravdˇepodobnost neˇz´ adouc´ı události.

2011/2012

J. ANTOCH, KPMS


O uˇ ziteˇ cnosti stochastiky ´ VYSLEDKY ´ ˇ MOHOU BYT PRAVDEPODOBNOSTI ˇ ˇ ´ ´ A STATISTIKY UZITECNE TAKE PRO INFORMATIKY?

2011/2012

J. ANTOCH, KPMS


2011/2012

O uˇ ziteˇ cnosti stochastiky ´ VYSLEDKY ´ ˇ MOHOU BYT PRAVDEPODOBNOSTI ˇ ˇ ´ ´ A STATISTIKY UZITECNE TAKE PRO INFORMATIKY?

ˇ ANO, SOUDÍM, ZE ´ O TOM A PROTO JSEM VAM ´ SEMESTR POVÍDAL CELY

2012 JAROMÍR ANTOCH. 16. ledna 2012

Recommend Documents