1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 5
Текст из файла (страница 5)
Ïðîèçâîäèì ïåðåïðèñâàèâàíèå(ò. å.) è ïîëàãàåìQ := Q − pm(1.19)(ò. å. çàíîñèì íîâîå çíà÷åíèå (α −p1) â ÿ÷åéêó Q). Åñëè íîâîå Q íå ïîëîæèòåëüíî, òîâ êà÷åñòâå m âûáèðàåì òåêóùåå åãî çíà÷åíèå è ïîëàãàåì ξ = xm, â ïðîòèâíîì ñëó÷àåïðîèçâîäèì ïåðåïðèñâàèâàíèÿ m := m + 1 è (1.19) è âíîâü ïðîèçâîäèì ïðîâåðêó Q íàïîëîæèòåëüíîñòü è ò. ä.Âàæíûì ïðèìåðîì äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí ÿâëÿþòñÿ öåëî÷èñëåííûå ñëó÷àéíûå âåëè÷èíû η, äëÿ êîòîðûõxi = i,P(η = i) = pi(1.20)äëÿ i = 1, 2, . . . , N .
Àëãîðèòì 1.1 â ýòîì ñëó÷àå èìååò ñëåäóþùèé âèä.Àëãîðèòì 1.2.Q := αm := 1(1.19)Qη=mm := m + 1 (1.19)Q1.2.2. Òðóäîåìêîñòü ñòàíäàðòíîãî àëãîðèòìà.  ðàçäåëå 0.5 óêàçàíî, ÷òî ôîðìóëå (0.5) äëÿ òðóäîåìêîñòè ìåòîäà Ìîíòå-Êàðëî (0.1) âåëè÷èíà t ÿâëÿåòñÿ ñðåäíèìâðåìåíåì âû÷èñëåíèÿ îäíîãî âûáîðî÷íîãî çíà÷åíèÿ ξj .
Ñëîâîçäåñü ïðèíöèïèàëüíî, òàê êàê çàòðàòû íà ìîäåëèðîâàíèå êîíêðåòíîãî âûáîðî÷íîãî çíà÷åíèÿ ξj ÿâëÿþòñÿ, âîîáùå ãîâîðÿ, ñëó÷àéíûìè. Ýòî ïðîÿâëÿåòñÿ óæå íà ïðîñòåéøåì ïðèìåðåñëó÷àéíîé âåëè÷èíû ξ ñ äèñêðåòíûì ðàñïðåäåëåíèåì.Ëåãêî âèäåòü, ÷òî â ñëó÷àå, êîãäà ξ = xm , ïðèõîäèòñÿ îñóùåñòâëÿòü m ïðîâåðîê Q íàïîëîæèòåëüíîñòü.  îáùèå çàòðàòû δ àëãîðèòìà 1.1 âõîäÿò çàòðàòû íà ìîäåëèðîâàíèåîäíîé ñòàíäàðòíîé ñëó÷àéíîé âåëè÷èíû (èõ îáîçíà÷èì a) è ðåàëèçàöèþ ñðàâíåíèé QÐåàëèçóåì çíà÷åíèåè ïîëàãàåì.
Ïðîèçâîäèì ïåðåïðèñâàèâàíèå. Åñëè íîâîå çíà÷åíèå íå ïîëîæèòåëüíî, òî ïîëàãàåì,âïðîòèâíîì ñëó÷àå ïðîèçâîäèì ïåðåïðèñâàèâàíèÿèè âíîâü ïðîèçâîäèì ïðîâåðêó íà ïîëîæèòåëüíîñòü è ò. ä.ñðåäíååñ íóëåì (çàòðàòû íà êàæäîå ñðàâíåíèå îáîçíà÷èì b). Òîãäà ñðåäíÿÿ òðóäîåìêîñòü tàëãîðèòìà ðàâíà!NXt = Eδ = a +ipi × b.(1.21)i=1Çàìåòèì, ÷òî äëÿ öåëî÷èñëåííîé ñëó÷àéíîé âåëè÷èíû η ñ ðàñïðåäåëåíèåì (1.20)âåëè÷èíà t èç (1.21) ïðåäñòàâèìà â âèäåt1 = a + b Eη.(1.22)Ïðè ðåàëèçàöèè àëãîðèòìîâ 1.1 è 1.2 öåëåñîîáðàçíî (åñëè ýòî âîçìîæíî) ðàñïîëàãàòüâåðîÿòíîñòè pi â ïîðÿäêå èõ óáûâàíèÿ.Óòâåðæäåíèå 1.8.
Îïòèìàëüíûì ðàñïðåäåëåíèåì âåðîÿòíîñòåé, ïðè êîòîðîìñðåäíèå çàòðàòû t èç (1.21) ìèíèìàëüíû, ÿâëÿåòñÿp1 ≥ p2 ≥ . . . ≥ pN .(1.23)Äîêàçàòåëüñòâî. Ðàññóæäàåì îò ïðîòèâíîãî. Ïóñòü äëÿ íåêîòîðîãî ðàñïðåäåëåíèÿ{p01 , . . . , p0N } ñîîòíîøåíèå (1.23) íå âûïîëíåíî, à âåëè÷èíà t0 = a +P âåðîÿòíîñòåéN0i=1 ipi × b ìèíèìàëüíà. Òîãäà íàéäóòñÿ òàêèå íîìåðà s è k , äëÿ êîòîðûõ îäíîâðåìåííî âûïîëíåíîs < k è p0s < p0k .(1.24)Ðàññìîòðèì íîâîå ðàñïðåäåëåíèå âåðîÿòíîñòåé {p001 , . . . , p00N }, êîòîðîå ïîëó÷åíî èç ðàñïðåäåëåíèÿ {p01 , .
. . , p0N } ïåðåñòàíîâêîé âåðîÿòíîñòåé p0s è p0k , ò. å. p00j = p0j ïðè j 6= s, j 6= kè p00s = p0k , p00k = p0s . Ðàññìîòðèì ðàçíîñòüt0 − t00 = (sp0s + kp0k − sp00s − kp00k )b = (sp0s + kp0k − sp0k − kp0s )b1 = (k − s)(p0k − p0s )b.Èç (1.24) ñëåäóåò, ÷òî t0 − t00 > 0 è t00 < t0 . Ïîëó÷èëè ïðîòèâîðå÷èå ñ òåì, ÷òî âåëè÷èíàt0 ìèíèìàëüíà.1.2.3. Ñëó÷àè ìàëîãî è áåñêîíå÷íîãî ÷èñëà çíà÷åíèé. Ïðèìåðû. Îòìåòèì,÷òî â àëãîðèòìå 1.1 âîçìîæíà ñëåäóþùàÿ ìîäèôèêàöèÿ. Åñëè α − RN −1 > 0, òî ïîñëåäíåå âû÷èòàíèå ìîæíî íå ïðîèçâîäèòü, òàê êàê â ýòîì ñëó÷àå α ∈ ∆N . Ñîîòâåòñòâóþùèåàíàëîãè ôîðìóë (1.21) è (1.22) èìåþò âèä!N−1Xt=a+ipi + (N − 1) pN × b; t1 = a − b pN + b Eη.i=1Îäíàêî âûèãðûø îò ýòîé ìîäèôèêàöèè ñêàçûâàåòñÿ òîëüêî äëÿ ìàëûõ N , òàê êàê ïðèåå ïðèìåíåíèè òðåáóåòñÿ ïðîâîäèòü ñðàâíåíèå òåêóùåãî m c (N − 1).Ðàññìîòðèì, â ÷àñòíîñòè, ñëó÷àé N = 2. Çäåñü àëãîðèòì 1.1 ïðèîáðåòàåò ñëåäóþùèéïðîñòîé âèä.Àëãîðèòì 1.3.αα < p1ξ = x1ξ = x2Åñëè x1 = 1 è x2 = 0, òî ξ ñ âåðîÿòíîñòüþ óñïåõà p1 .
 ñâîþ î÷åðåäü, ìîæíî âñïîìíèòü î òîì, ÷òî áåðíóëëèåâñêàÿ ñëó÷àéíàÿ âåëè÷èíà ââîäèòñÿ äëÿ ôîðìàëèçàöèè èçó÷åíèÿ ñëó÷àéíûõ ñîáûòèé. Åñëè ïðèäàòü âåëè÷èíàì x1 è x2 "ñëîâåñíûå"çíà÷åíèÿ x1 = {A} è x2 ={A}, òî àëãîðèòì 1.3 îïèñûâàåòAÐåàëèçóåì çíà÷åíèå . Åñëè, òî, èíà÷åáåðíóëëèåâñêàÿ ñëó÷àéíàÿ âåëè÷èíàñîáûòèå íå ïðîèçîøëîáûòèÿ ..ñîáûòèå ïðîèçîøëîìîäåëèðîâàíèå ñëó÷àéíîãî ñî- ñëó÷àå N = ∞ äëÿ çàäàíèÿ ðàñïðåäåëåíèÿ (1.18) âìåñòî êîíêðåòíûõ çíà÷åíèé{xi } è âåðîÿòíîñòåé {pi } çàäàþòñÿ ôîðìóëû èõ âû÷èñëåíèÿxi = ϕ(i); pi = ψ(i).(1.25)Äëÿ âû÷èñëåíèÿ âåðîÿòíîñòåé ÷àñòî áîëåå óäîáíûìè (ýêîíîìè÷íûìè) ÿâëÿþòñÿ ðåêóððåíòíûå ôîðìóëû âèäàpi+1 = z(pi ),à êîíêðåòíåå, pi+1 = pi r(i + 1).(1.26)Ïðè ðåàëèçàöèè àëãîðèòìà 1.1 â ñëó÷àå áåñêîíå÷íîãî ÷èñëà çíà÷åíèé ïåðåä âû÷èòàíèåìñîîòâåòñòâóþùåé âåðîÿòíîñòè òðåáóåòñÿ âû÷èñëèòü åå ïî îäíîé èç ôîðìóë (1.25) èëè(1.26).Àëãîðèòì 1.4.Q := αm := 1 P := p1P := ψ(1)ïîëàãàåìÐåàëèçóåì çíà÷åíèå ñòàíäàðòíîé ñëó÷àéíîé âåëè÷èíûè(èëè). Ïðîèçâîäèì ïåðåïðèñâàèâàíèåQ := Q − P.è(1.27)Åñëè íîâîå Q íå ïîëîæèòåëüíî, òî â êà÷åñòâå çíà÷åíèÿ ξ âûáèðàåì ξ = ϕ(m) äëÿòåêóùåãî m; â ïðîòèâíîì ñëó÷àå ïîëàãàåì m := m + 1, ïðîèçâîäèì ïåðåñ÷åò âåðîÿòíîñòè P := ψ(m) (èëè P := z(P ), èëè P := P r(m)) è ïåðåïðèñâàèâàíèå (1.27) è âíîâüïðîèçâîäèì ïðîâåðêó Q íà ïîëîæèòåëüíîñòü è ò.ä.Ñðåäíèå çàòðàòû àëãîðèòìà 1.4 ðàâíût=a+∞X!i pi(b + c),(1.28)i=1ãäå c ñðåäíèå çàòðàòû íà ïåðåñ÷åò âåðîÿòíîñòè.
 ñëó÷àå, êîãäà ïåðåñ÷åò âåðîÿòíîñòåéïðîèñõîäèò ïî ðåêóððåíòíûì ôîðìóëàì (1.26) è âåðîÿòíîñòü p1 çàäàíà, ÷èñëî t èç (1.28)óìåíüøàåòñÿ íà âåëè÷èíó c. Äëÿ öåëî÷èñëåííûõ ñëó÷àéíûõ âåëè÷èí η ñ ðàñïðåäåëåíèåì(1.20) ïðè i = 1, 2, . . . ôîðìóëà (1.28) èìååò âèät1 = a + (b + c)Eη.(1.29)Ñóùåñòâóåò ðÿä ñïîñîáîâ ïîíèçèòü òðóäîåìêîñòü (1.28), ê ÷èñëó êîòîðûõ îòíîñèòñÿ, â ÷àñòíîñòè, ðàñïîëîæåíèå (åñëè ýòî âîçìîæíî) âåðîÿòíîñòåé pi â ïîðÿäêå óáûâàíèÿ(ñì. óòâåðæäåíèå 1.8).  ñëó÷àå, êîãäà ïåðåñ÷åò âåðîÿòíîñòåé ïî îäíîé èç ôîðìóë (1.25)èëè (1.26) ÿâëÿåòñÿ òðóäîåìêèì (ò. å.
âåëè÷èíà c âåëèêà), ìîæíî âûáðàòü ÷èñëî N0 òàê,÷òîáû ñóììà âåðîÿòíîñòåé RN0 = p1 + p2 + . . . + pN0 áûëà áëèçêà ê åäèíèöå è èìåëàñüâîçìîæíîñòü ñîõðàíèòü â îïåðàòèâíîé ïàìÿòè ÝÂÌ ìàññèâ çíà÷åíèé p0 , p1 , . . . , pN0 . Òîãäà ïðè α < RN0 ðåàëèçóåòñÿ àëãîðèòì 1.1 (áåç ïåðåñ÷åòà âåðîÿòíîñòåé), à ôîðìóëû(1.25) èëè (1.26) áóäóò èñïîëüçîâàòüñÿ òîëüêî ïðè α ≥ RN0 , ò. å. äîñòàòî÷íî ðåäêî. Ñóùåñòâåííî ñíèæàþò çàòðàòû (1.21), (1.28) àëãîðèòìîâ 1.1 è 1.4 äëÿ N >> 1 èëè N = ∞ðàññìîòðåííûå äàëåå â ðàçäåëå 1.3è(àëãîðèòìû1.6 è 1.7).  ýòèõ àëãîðèòìàõ ñóùåñòâåííî èñïîëüçóåòñÿ ñïåöèàëüíûé àëãîðèòì ìîäåëèðîâàíèÿ(àëãîðèòì 1.5). êà÷åñòâå ïðèìåðîâ ñëó÷àéíûõ âåëè÷èí ñ áîëüøèì èëè áåñêîíå÷íûì ÷èñëîì çíà÷åíèé ðàññìîòðèì øèðîêî ïðèìåíèìûå â òåîðèè âåðîÿòíîñòåé ñïåöèàëüíûå öåëî÷èñëåííûå ñëó÷àéíûå âåëè÷èíû η ñ ðàñïðåäåëåíèåì (1.20) (äëÿ íèõ ñîîòíîøåíèå (1.25) èìååòâèä xi = ϕ(i) = i). Ýòè ñëó÷àéíûå âåëè÷èíû ñâÿçàíû ñ óïîìÿíóòûìè âûøå èñïûòàíèÿìè Áåðíóëëè, ò.
å. ñ ðåàëèçàöèåé çíà÷åíèé ñëó÷àéíîé âåëè÷èíû γ c ðàñïðåäåëåíèåìâåðîÿòíîñòåéP(γ = 1) = p, P(γ = 0) = 1 − p; 0 < p < 1.ìåòîä Óîëêåðà êâàíòèëüíûé ìåòîäðàâíîìåðíîãî äèñêðåòíîãî ðàñïðåäåëåíèÿÑîáûòèå {γ = 1} íàçûâàþòòèå {γ = 0} .óñïåõîì (òîãäà âåëè÷èíà p âåðîÿòíîñòü óñïåõà), à ñîáû-íåóñïåõîìÃåîìåòðè÷åñêîå ðàñïðåäåëåíèå ñ ïàðàìåòðîì p, çäåñüÏðèìåð 1.1.pi = p (1 − p)i−1 , i = 1, 2, . . . .(1.30)Ñîîòâåòñòâóþùàÿ ñëó÷àéíàÿ âåëè÷èíà η îïðåäåëÿåò êîëè÷åñòâî èñïûòàíèé Áåðíóëëèγïåðâîãî óñïåõà.
Îòìåòèì, ÷òî âî ìíîãèõ èçäàíèÿõ â êà÷åñòâå ñëó÷àéíîéâåëè÷èíû, èìåþùåé ãåîìåòðè÷åñêîå ðàñïðåäåëåíèå, áåðåòñÿ η 0 = η − 1. Ýòà âåëè÷èíàðàâíà ÷èñëó èñïûòàíèé Áåðíóëëè,ïåðâîìó óñïåõó. Äëÿ íóæä ÷èñëåííîãî ìîäåëèðîâàíèÿ óäîáíåå èñïîëüçîâàòü âåðñèþ (1.30) ãåîìåòðè÷åñêîãî ðàñïðåäåëåíèÿ.
Ïðè ðåàëèçàöèè àëãîðèòìà 1.4 äëÿ ïåðåñ÷åòà âåðîÿòíîñòåé öåëåñîîáðàçíî èñïîëüçîâàòü ìóëüòèïëèêàòèâíóþ ðåêóððåíòíóþ ôîðìóëó (1.26) ïðè r(i + 1) = pi+1 /pi ≡ 1 − p.Ðàçëàãàÿ ôóíêöèþ 1/(1 − z)2 â ðÿä Òåéëîðà â òî÷êå z0 = 0 è ïîëàãàÿ z = q = 1 − p,ïîëó÷àåìäî ïîëó÷åíèÿïðåäøåñòâóþùèõ∞∞XXp11i−1=iqèòîãäàEξ=ipq i−1 == .22(1 − q)(1 − q)pi=1i=1(1.31)Ñîãëàñíî ôîðìóëå (1.29), òðóäîåìêîñòü ñòàíäàðòíîãî àëãîðèòìà 1.4 ðàâíà t1 = a + (b +c)/p.Ïðèìåð 1.2.p N , çäåñüÁèíîìèàëüíîå ðàñïðåäåëåíèå ñ ïàðàìåòðàìè èpi = CNi pi (1 − p)N −i ; i = 0, 1, . . . , N ; CNi =N!.i!(N − i)!(1.32)Ñîîòâåòñòâóþùàÿ ñëó÷àéíàÿ âåëè÷èíàηp,N = γ1 + . .
. + γN(1.33)îïðåäåëÿåò êîëè÷åñòâî óñïåõîâ â N èñïûòàíèÿõ Áåðíóëëè. Ïðè ðåàëèçàöèè àëãîðèòìà1.4 ñëåäóåò ñíà÷àëà ïîëàãàòü m := 0 (âìåñòî m := 1; ïðè ýòîì ñðåäíåå ÷èñëî âû÷èòàíèé(1.27) óâåëè÷èòñÿ íà åäèíèöó) è äëÿ ïåðåñ÷åòà âåðîÿòíîñòåé èñïîëüçîâàòü ôîðìóëó(1.26) ïðè r(i + 1) = (p(N − i))/(q(i + 1)). Èç ôîðìóëû (1.33) ñëåäóåò, ÷òî Eηp,N = N pè òîãäà, ñîãëàñíî ôîðìóëå (1.22), t1 = a + (b + c)(N p + 1).Ïðèìåð 1.3.λ > 0, çäåñüÐàñïðåäåëåíèå Ïóàññîíà ñ ïàðàìåòðîìpi =λi −λe ; i = 0, 1, .
. . .i!(1.34)Ñîãëàñíî òåîðåìå Ïóàññîíà, ýòî ðàñïðåäåëåíèå ÿâëÿåòñÿ ïðåäåëüíîé ôîðìîé áèíîìèàëüíîãî ðàñïðåäåëåíèÿ ïðèN → ∞,p(N ) → 0,N p(N ) → λ.(1.35)Ïðè ðåàëèçàöèè àëãîðèòìà 1.4 ñëåäóåò ñíà÷àëà ïîëàãàòü m := 0 è äëÿ ïåðåñ÷åòà âåðîÿòíîñòåé èñïîëüçîâàòü ôîðìóëó (1.26) ïðè r(i + 1) = λ/(i + 1). Èñïîëüçóÿ èçâåñòíîåðàçëîæåíèå ôóíêöèè eλ â ðÿä Òåéëîðà â òî÷êå λ0 = 0, èìååì∞∞XXλi −λλj−λEη =i e = λe= λ;i!j!i=0j=1çäåñü j = i − 1. Ñëåäîâàòåëüíî, t1 = a + (b + c)(λ + 1). çàêëþ÷åíèå îòìåòèì, ÷òî äàëåå â ïîäðàçä. 1.3.71.3.9 ïðèâåäåí ðÿä ñïåöèàëüíûõìåòîäîâ ìîäåëèðîâàíèÿ ñëó÷àéíûõ âåëè÷èí èç ïðèìåðîâ 1.11.3 è ïðîâåäåí àíàëèç ýòèõìåòîäîâ ñðàâíèòåëüíî ñî ñòàíäàðòíûìè àëãîðèòìàìè 1.2 è 1.4.1.3. ÑÏÅÖÈÀËÜÍÛÅ ÀËÃÎÐÈÒÌÛ ÌÎÄÅËÈÐÎÂÀÍÈßÄÈÑÊÐÅÒÍÎÃÎ ÐÀÑÏÐÅÄÅËÅÍÈßÐåàëèçàöèÿ ñëó÷àéíîé âåëè÷èíû ξ ñ êîíå÷íûì ÷èñëîì çíà÷åíèé çàìåòíî óïðîùàåòñÿ, êîãäà âñåçíà÷åíèÿ x1 , .
. . , xN ðàâíîâåðîÿòíû, ò. å. â (1.18) âñå pi ðàâíû 1/N (òàêîå ðàñïðåäåëåíèåâåðîÿòíîñòåé íàçûâàåòñÿ).Àëãîðèòì 1.5.α1.3.1. Ìîäåëèðîâàíèå ðàâíîìåðíîãî äèñêðåòíîãî ðàñïðåäåëåíèÿ.è ïîëàãàåìäèñêðåòíûì ðàâíîìåðíûìÐåàëèçóåì âûáîðî÷íîå çíà÷åíèå ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëàm = [α N ] + 1 = [αN + 1](1.36)(çäåñü [A] îáîçíà÷àåò öåëóþ ÷àñòü ÷èñëà A) è ξ = xm.Äëÿ îáîñíîâàíèÿ ïðàâèëüíîñòè âûáîðà íîìåðà m ïî ôîðìóëå (1.36) íóæíî ïîêàçàòü,÷òî äëÿ ëþáîãî k = 1, 2, . . .
, N âûïîëíåíî P(m = k) = 1/N . Èñïîëüçóÿ îïðåäåëåíèåöåëîé ÷àñòè ÷èñëà è óòâåðæäåíèå 1.2, èìååìP(m = k) = P([α N + 1] = k) = P(k − 1 ≤ α N < k) =kk−11kk−1≤α<−= ,==PNNNNN÷òî è òðåáîâàëîñü äîêàçàòü.Çàìå÷àíèå 1.3. Äëÿ äîñòàòî÷íî áîëüøèõ N ïðåèìóùåñòâî èñïîëüçîâàíèÿ àëãîðèòìà 1.5 âìåñòî àëãîðèòìà 1.1 î÷åâèäíî. Îäíàêî íåâåðíî ãîâîðèòü ÷òî àëãîðèòì 1.5ýêîíîìè÷íåå àëãîðèòìà 1.1.
Òàê, äëÿ N = 2 è p1 = p2 = 1/2 áîëåå ýêîíîìè÷íûì(ïî ñðàâíåíèþ ñ àëãîðèòìîì 1.5), êàê ïðàâèëî, ÿâëÿåòñÿ àëãîðèòì 1.3 (÷àñòíûé ñëó÷àéàëãîðèòìà 1.1). Çäåñü âñå çàâèñèò îò òîãî, íàñêîëüêî áûñòðî ðàáîòàþò îïåðàöèè âçÿòèÿöåëîé ÷àñòè ÷èñëà, âû÷èòàíèÿ, ñðàâíåíèÿ è ò. ï., à ýòî, â ñâîþ î÷åðåäü, îïðåäåëÿåòñÿâûáîðîì êîìïüþòåðà è ÿçûêà ïðîãðàììèðîâàíèÿ. Ïîýòîìó â êàæäîì êîíêðåòíîì ñëó÷àå ìîæåò ñóùåñòâîâàòü ñâîå ÷èñëî N0 , äëÿ êîòîðîãî ïðè N ≤ N0 áîëåå ýêîíîìè÷íûìÿâëÿåòñÿ àëãîðèòì 1.1, à ïðè N > N0 àëãîðèòì 1.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
