1626435387-cbed9341b165fae9f16c4a05686b9115 (Войтишек - Основы метода Монте-Карло), страница 7

Çäåñü àëãîðèòì 11.1 ïðèîáðåòàåò ñëåäóþùèé ïðîñòîé âèä.ÀËÃÎÐÈÒÌ 11.3. Ðåàëèçóåì çíà÷åíèå α0 . Åñëè α0 < p1 , òî ξ0 = x1 ,èíà÷å ξ0 = x2 .Åñëè x1 = 1 è x2 = 0, òî ξ áåðíóëëèåâñêàÿ ñëó÷àéíàÿ âåëè÷èíàñ âåðîÿòíîñòüþ óñïåõà p1 (ñì., íàïðèìåð, [2]).  ñâîþ î÷åðåäü, ìîæíî âñïîìíèòü î òîì, ÷òî áåðíóëëèåâñêàÿ ñëó÷àéíàÿ âåëè÷èíà ââîäèòñÿäëÿ ôîðìàëèçàöèè èçó÷åíèÿ ñëó÷àéíûõ ñîáûòèé. Åñëè ïðèäàòü âåëè÷èíàì x1 è x2 ¾ñëîâåñíûå¿ çíà÷åíèÿ x1 = {ñîáûòèå A ïðîèçîøëî} èx2 = {ñîáûòèå A íå ïðîèçîøëî}, òî àëãîðèòì 11.3 îïèñûâàåò ìîäåëèðîâàíèå ñëó÷àéíîãî ñîáûòèÿ A.11.5.

Ñëó÷àé ñ÷åòíîãî ÷èñëà çíà÷åíèé ñëó÷àéíîé âåëè÷èíû. ñëó÷àå N = ∞ äëÿ çàäàíèÿ ðàñïðåäåëåíèÿ (11.1) âìåñòî êîíêðåòíûõçíà÷åíèé {xi } è âåðîÿòíîñòåé {pi } çàäàþòñÿ ôîðìóëû èõ âû÷èñëåíèÿxi = ϕ(i); pi = ψ(i).(11.6)Äëÿ âû÷èñëåíèÿ âåðîÿòíîñòåé ÷àñòî áîëåå óäîáíûìè (ýêîíîìè÷íûìè)ÿâëÿþòñÿ ðåêóððåíòíûå ôîðìóëû âèäàpi+1 = z(pi ), à êîíêðåòíåå, pi+1 = pi r(i + 1).(11.7)Ïðè ðåàëèçàöèè àëãîðèòìà 11.1 â ñëó÷àå áåñêîíå÷íîãî ÷èñëà çíà÷åíèéïåðåä âû÷èòàíèåì ñîîòâåòñòâóþùåé âåðîÿòíîñòè òðåáóåòñÿ âû÷èñëèòüåå ïî îäíîé èç ôîðìóë (11.6) èëè (11.7).ÀËÃÎÐÈÒÌ 11.4.

Ðåàëèçóåì çíà÷åíèå ñòàíäàðòíîé ñëó÷àéíîé âåëè÷èíû Q := α0 è ïîëàãàåì m := 1 è P := p1 (èëè P := ψ(1)). Ïðîèçâîäèì ïåðåïðèñâàèâàíèåQ := Q − P.(11.8)Åñëè íîâîå Q íå ïîëîæèòåëüíî, òî â êà÷åñòâå âûáîðî÷íîãî çíà÷åíèÿξ0 ñëó÷àéíîé âåëè÷èíû ξ âûáèðàåì ξ0 = ϕ(m) äëÿ òåêóùåãî m; â ïðîòèâíîì ñëó÷àå ïîëàãàåì m := m + 1, ïðîèçâîäèì ïåðåñ÷åò âåðîÿòíîñòè P := ψ(m) (èëè P := z(P ), èëè P := P r(m)) è ïåðåïðèñâàèâàíèå(11.8) è âíîâü ïðîèçâîäèì ïðîâåðêó Q íà ïîëîæèòåëüíîñòü è ò.ä.Ñðåäíèå çàòðàòû àëãîðèòìà 11.4 ðàâíû!∞Xt=a+i pi × (b + c),(11.9)i=135ãäå c ñðåäíèå çàòðàòû íà ïåðåñ÷åò âåðîÿòíîñòè.

 ñëó÷àå, êîãäà ïåðåñ÷åò âåðîÿòíîñòåé ïðîèñõîäèò ïî ðåêóððåíòíûì ôîðìóëàì (11.7) èâåðîÿòíîñòü p1 çàäàíà, ÷èñëî t èç ðàâåíñòâà (11.9) óìåíüøàåòñÿ íà âåëè÷èíó c. Äëÿ öåëî÷èñëåííûõ ñëó÷àéíûõ âåëè÷èí η ñ ðàñïðåäåëåíèåì(11.3) ïðè i = 1, 2, . . . ôîðìóëà (11.9) èìååò âèät1 = a + (b + c)Eη.(11.10)Ñóùåñòâóåò ðÿä ñïîñîáîâ ïîíèçèòü òðóäîåìêîñòü (11.9), ê ÷èñëó êîòîðûõ îòíîñèòñÿ, â ÷àñòíîñòè, ðàñïîëîæåíèå (åñëè ýòî âîçìîæíî) âåðîÿòíîñòåé pi â ïîðÿäêå óáûâàíèÿ.  ñëó÷àå, êîãäà ïåðåñ÷åò âåðîÿòíîñòåéïî îäíîé èç ôîðìóë (11.6) èëè (11.7) ÿâëÿåòñÿ òðóäîåìêèì (ò.

å. âåëè÷èíà c âåëèêà), ìîæíî âûáðàòü ÷èñëî N0 òàê, ÷òîáû ñóììà âåðîÿòíîñòåéRN0 = p1 + p2 + . . . + pN0 áûëà áëèçêà ê åäèíèöå è èìåëàñü âîçìîæíîñòüñîõðàíèòü â îïåðàòèâíîé ïàìÿòè ÝÂÌ ìàññèâ çíà÷åíèé p0 , p1 , . . . , pN0 .Òîãäà ïðè α0 < RN0 ðåàëèçóåòñÿ àëãîðèòì 11.1 (áåç ïåðåñ÷åòà âåðîÿòíîñòåé), à ôîðìóëû (11.6) èëè (11.7) áóäóò èñïîëüçîâàòüñÿ òîëüêî ïðèα0 ≥ RN0 , ò. å. äîñòàòî÷íî ðåäêî. Ñóùåñòâåííî ñíèæàåò çàòðàòû (11.4),(11.9) àëãîðèòìîâ 11.1 è 11.4 äëÿ N 1 èëè N = ∞ ðàññìîòðåííûé âðàçä. 12 êâàíòèëüíûé ìåòîä (àëãîðèòì 12.2).  ýòîì àëãîðèòìå ñóùåñòâåííî èñïîëüçóåòñÿ ñïåöèàëüíûé àëãîðèòì ìîäåëèðîâàíèÿ ðàâíîìåðíîãî äèñêðåòíîãî ðàñïðåäåëåíèÿ (àëãîðèòì 12.1).12. Ìîäåëèðîâàíèå ðàâíîìåðíîãî äèñêðåòíîãîðàñïðåäåëåíèÿ.

Êâàíòèëüíûé ìåòîä12.1. Ñëó÷àé ðàâíûõ âåðîÿòíîñòåé. Ðåàëèçàöèÿ âûáîðî÷íîãîçíà÷åíèÿ ξ0 ñëó÷àéíîé âåëè÷èíû ξ ñ êîíå÷íûì ÷èñëîì çíà÷åíèé çàìåòíî óïðîùàåòñÿ, êîãäà âñå çíà÷åíèÿ x1 , . . . , xN ðàâíîâåðîÿòíû, ò. å. âñîîòíîøåíèè (11.1) âñå pi ðàâíû 1/N (òàêîå ðàñïðåäåëåíèå âåðîÿòíîñòåéíàçûâàåòñÿ äèñêðåòíûì ðàâíîìåðíûì).ÀËÃÎÐÈÒÌ 12.1 (ñì., íàïðèìåð, [1]). Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå α0 ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà α è ïîëàãàåìµ0 = [α0 N ] + 1 = [α0 N + 1](12.1)(çäåñü [A] îáîçíà÷àåò öåëóþ ÷àñòü ÷èñëà A) è ξ0 = xµ0 .Äëÿ îáîñíîâàíèÿ ïðàâèëüíîñòè âûáîðà íîìåðà µ0 ïî ôîðìóëå (12.1)íóæíî ïîêàçàòü, ÷òî äëÿ ëþáîãî k = 1, 2, .

. . , N âûïîëíåíî P(µ = k) =1/N . Èñïîëüçóÿ îïðåäåëåíèå öåëîé ÷àñòè ÷èñëà è óòâåðæäåíèå 10.2,36èìååìP(µ = k) = P([α N + 1] = k) = P(k − 1 ≤ α N < k) =k−1kkk−11=P≤α<=−= ,NNNNN÷òî è òðåáîâàëîñü äîêàçàòü.Äëÿ äîñòàòî÷íî áîëüøèõ N ïðåèìóùåñòâî èñïîëüçîâàíèÿ àëãîðèòìà 12.1 âìåñòî àëãîðèòìà 11.1 î÷åâèäíî. Îäíàêî íåâåðíî ãîâîðèòü, ÷òîàëãîðèòì 12.1 âñåãäà ýêîíîìè÷íåå àëãîðèòìà 11.1. Òàê, äëÿ N = 2 èp1 = p2 = 1/2 áîëåå ýêîíîìè÷íûì (ïî ñðàâíåíèþ ñ àëãîðèòìîì 12.1),êàê ïðàâèëî, ÿâëÿåòñÿ àëãîðèòì 11.3 (÷àñòíûé ñëó÷àé àëãîðèòìà 11.1).Çäåñü âñå çàâèñèò îò òîãî, íàñêîëüêî áûñòðî ðàáîòàþò îïåðàöèè âçÿòèÿöåëîé ÷àñòè ÷èñëà, âû÷èòàíèÿ, ñðàâíåíèÿ è ò.

ï., à ýòî, â ñâîþ î÷åðåäü,îïðåäåëÿåòñÿ âûáîðîì êîìïüþòåðà è ÿçûêà ïðîãðàììèðîâàíèÿ. Ïîýòîìó â êàæäîì êîíêðåòíîì ñëó÷àå ìîæåò ñóùåñòâîâàòü ñâîå ÷èñëî N0 ,äëÿ êîòîðîãî ïðè N ≤ N0 áîëåå ýêîíîìè÷íûì ÿâëÿåòñÿ àëãîðèòì 11.1,à ïðè N > N0 àëãîðèòì 12.1. Çíà÷åíèå N0 îïðåäåëÿåòñÿ ýêñïåðèìåíòàëüíî ñ ïîìîùüþ ðåàëèçàöèè âûáîðêè ξ1 , . . . , ξn è ôèêñàöèè çàòðàòs = nt äëÿ êàæäîãî èç àëãîðèòìîâ 11.1 è 12.1.12.2. Êâàíòèëüíûé ìåòîä. Àëãîðèòì 12.1 ïîçâîëÿåò ïîñòðîèòüñëåäóþùóþ ýôôåêòèâíóþ ìîäèôèêàöèþ àëãîðèòìîâ 11.1 è 11.4, êîòîðàÿ íîñèò íàçâàíèå êâàíòèëüíûé ìåòîä (ñì., íàïðèìåð, [1]) è ïðèìåíÿåòñÿ, êàê ïðàâèëî, â ñëó÷àå N 1 (è äàæå äëÿ N = ∞).Çàäàäèì öåëîå ÷èñëî K è ðàçîáüåì èíòåðâàë (0, 1) íà K ðàâíûõ÷àñòåé [(j − 1)/K, j/K), j = 1, .

. . , K . Äàëåå ïîñòðîèì ìàññèâ öåëûõ÷èñåë {Xj }Kj=1 òàêîé, ÷òîXj = min{k : Rk = p1 + p2 + . . . + pk ≥ (j − 1)/K},êîòîðûé íàçûâàåòñÿ ìàññèâîì íèæíèõ êâàíòèëåé. Ýòîò ìàññèâ çàäàåò íîìåð k ýëåìåíòà ìàññèâà {Ri ; i = 1, 2, . . . , N }, ñ êîòîðîãî ñëåäóåòíà÷èíàòü ïîèñê ¾ââåðõ¿ (ò. å. êàê è â àëãîðèòìå âèäà 11.1, âû÷èòàòü âåëè÷èíû Rq , q = k, k + 1, . .

. èç α0 äî ïîëó÷åíèÿ ïåðâîãî îòðèöàòåëüíîãîçíà÷åíèÿ) ïðè (j − 1)/K ≤ α0 < j/K . Îêîí÷àòåëüíî ìîäåëèðîâàíèåäèñêðåòíîé ñëó÷àéíîé âåëè÷èíû âûãëÿäèò ñëåäóþùèì îáðàçîì.ÀËÃÎÐÈÒÌ 12.2. 1. Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå α0 ðàâíîìåðíîðàñïðåäåëåííîé â èíòåðâàëå (0, 1) ñëó÷àéíîé âåëè÷èíû α.2.

Âû÷èñëÿåì íîìåð j0 ïîëóèíòåðâàëà [(j0 −1)/K, j0 /K), â êîòîðûéïîïàäàåò α0 ïî ôîðìóëå òèïà (12.1): j0 = [Kα0 + 1].373. Ðåàëèçóåì ïîñëåäîâàòåëüíûé ïîèñê ¾ñíèçó ââåðõ¿, íà÷èíàÿ ñ RXj0 .Òåñòîâûå âû÷èñëåíèÿ ïîêàçàëè, ÷òî ïðè N ≤ 3M0 (çäåñü ÷åðåç M0îáîçíà÷åí ðàçìåð ìàêñèìàëüíîãî ìàññèâà äëÿ çàäàííîãî êîìïüþòåðà èâûáðàííîãî ÿçûêà ïðîãðàììèðîâàíèÿ) ñëåäóåò âûáèðàòü ÷èñëî K êâàíòèëåé [(j − 1)/K, j/K) òàê, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèå N/K ≈ 3(ïðè ýòîì òðóäîåìêîñòü àëãîðèòìà 12.2 ïðàêòè÷åñêè íå ìåíÿåòñÿ ñ ðîñòîì N ). Äëÿ ñëó÷àÿ N = ∞ ìîæíî áðàòü K ≈ M0 .12.3. Ñëó÷àé ìàëîãî ÷èñëà âåðîÿòíîñòåé.

Ýôôåêòèâíûå âåðñèèêâàíòèëüíîãî ìåòîäà ìîæíî ñòðîèòü è äëÿ îòíîñèòåëüíî ìàëîãî ÷èñëàâåðîÿòíîñòåé. Ïóñòü 1/pmin < M0 (çäåñü pmin = min(p1 , . . . , pN )). Òîãäàìîæíî âçÿòü ÷èñëî êâàíòèëåé, ðàâíîå K = [1/pmin ] + 1. Ïðè ýòîì äëÿðåàëèçàöèè òðåòüåãî ïóíêòà àëãîðèòìà 12.2 ïîòðåáóåòñÿ íå áîëåå îäíîãîâû÷èòàíèÿ òèïà (11.2).Çàìåòèì òàêæå, ÷òî â öåëîì ðÿäå ñèòóàöèé öåëåñîîáðàçíî èñïîëüçîâàòü âìåñòî êâàíòèëüíîãî ìåòîäà àëãîðèòì Óîëêåðà èëè äàæå áèíàðíûéïîèñê (ñì., íàïðèìåð, [1]), îäíàêî àëãîðèòì 12.2 ÿâëÿåòñÿ áîëåå óíèâåðñàëüíûì è ïðîñòûì äëÿ ðåàëèçàöèè íà ÝÂÌ.13.

Ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ.Êîíñòðóèðîâàíèå ìîäåëèðóåìûõ ïëîòíîñòåé13.1. Îñîáåííîñòè ìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíûñ íåïðåðûâíûì ðàñïðåäåëåíèåì. Ðàññìîòðèì òåïåðü àëãîðèòìû÷èñëåííîé ðåàëèçàöèè âûáîðî÷íîãî çíà÷åíèÿ ξ0 ñëó÷àéíîé âåëè÷èíûξ , îáëàñòüþ çíà÷åíèé êîòîðîé ÿâëÿåòñÿ èíòåðâàë èëè îáúåäèíåíèå èíòåðâàëîâ.  äàëüíåéøåì â ïîäàâëÿþùåì ÷èñëå ñëó÷àåâ ïðåäïîëàãàåòñÿ,÷òî ξ ∈ (a, b), ò.

å. ñëó÷àéíàÿ âåëè÷èíà ξ ïðèíèìàåò çíà÷åíèÿ â èíòåðâàëå (a, b), ãäå −∞ ≤ a < b ≤ +∞, è åå ôóíêöèÿ ðàñïðåäåëåíèÿF (x) = P(ξ < x) íåïðåðûâíà è ñòðîãî âîçðàñòàåò ïðè x ∈ (a, b), ïðèýòîìF (x) = 0 ïðè x ≤ a è F (x) = 1 ïðè x ≥ b;(13.1)äëÿ ñëó÷àåâ a = −∞ è b = +∞ ñîîòíîøåíèÿ (13.1) ïðèîáðåòàþò âèäF (−∞) = 0,F (+∞) = 1 èëèlim F (x) = 0,x→−∞lim F (x) = 1.x→+∞Ñëó÷àè, êîãäà îáëàñòü çíà÷åíèé ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèåíåïåðåñåêàþùèõñÿ èíòåðâàëîâ èëè äèñêðåòíûõ ìíîæåñòâ ñ èíòåðâàëàìè (ïðè ýòîì íàðóøàþòñÿ óñëîâèÿ ñòðîãîé ìîíîòîííîñòè èëè íåïðåðûâíîñòè ôóíêöèè F (x)), áóäóò ñ÷èòàòüñÿ ¾ýêçîòè÷åñêèìè¿.38 ñëó÷àå ξ ∈ (a, b), â îòëè÷èå îò äèñêðåòíîãî ñëó÷àÿ, îòäåëüíîåçíà÷åíèå x0 ∈ (a, b) èìååò íóëåâóþ âåðîÿòíîñòü.

Çäåñü ôóíêöèÿ ðàñïðåäåëåíèÿ ïîçâîëÿåò âû÷èñëÿòü âåðîÿòíîñòè òîãî, ÷òî ξ ïðèíàäëåæèòíåêîòîðîìó èíòåðâàëó:P ξ ∈ (c, d) = F (d) − F (c).(13.2) äàëüíåéøåì ìû áóäåì ðàññìàòðèâàòü ïðàêòè÷åñêè çíà÷èìûå ñëó÷àéíûå âåëè÷èíû ξ ∈ (a, b), ðàñïðåäåëåíèÿ êîòîðûõ ÿâëÿþòñÿ àáñîëþòíî íåïðåðûâíûìè (ñì., íàïðèìåð, [2]), ÷òî îçíà÷àåò ñóùåñòâîâàíèå äëÿêàæäîé èç íèõ íåîòðèöàòåëüíîé ôóíêöèè f (u) òàêîé, ÷òî äëÿ ëþáîãîèíòåðâàëà (c, d) ⊆ (a, b) âûïîëíåíîP ξ ∈ (c, d) =Zdf (u) du.(13.3)cÔóíêöèÿ f (u) íàçûâàåòñÿ ïëîòíîñòüþ ðàñïðåäåëåíèÿ. Îíà îïðåäåëåíà ñ òî÷íîñòüþ äî çíà÷åíèé íà ìíîæåñòâå ìåðû íóëü.  äàëüíåéøåìðàññìàòðèâàþòñÿ íåïðåðûâíûå è êóñî÷íî-íåïðåðûâíûå ¾âåðñèè¿ ïëîòíîñòè f (u).

Ñâîéñòâàìè ïëîòíîñòè ÿâëÿþòñÿf (u) ≥ 0 ïðè u ∈ (a, b);Z+∞Zf (u) du =−∞bf (u) du = 1;(13.4)af (u) = 0 ïðè u ∈/ (a, b).(13.5)Áóäåì òàêæå ïðåäïîëàãàòü, ÷òî ïðè u ∈ (a, b) ìíîæåñòâî òî÷åê, òàêèõ÷òî f (u) = 0, èìååò ìåðó íóëü. Èç ñîîòíîøåíèé (13.2), (13.3) ñëåäóåò,÷òîZ xF (x) =f (u) du(13.6)−∞è ïî÷òè âñþäó (ïî ìåðå Ëåáåãà) èìååò ìåñòî ðàâåíñòâî f (u) = dF (u)/du.Èç ñîîòíîøåíèÿ (13.6) ñëåäóåò, ÷òî àáñîëþòíî íåïðåðûâíîå ðàñïðåäåëåíèå ìîæíî çàäàâàòü íå ôóíêöèåé ðàñïðåäåëåíèÿ F (x), à ïëîòíîñòüþf (u).

Åùå ðàç îòìåòèì, ÷òî ïîäàâëÿþùåå áîëüøèíñòâî ðàññìàòðèâàåìûõ äàëåå ðàñïðåäåëåíèé ÿâëÿþòñÿ àáñîëþòíî íåïðåðûâíûìè. Ñîîòâåòñòâóþùèå ñëó÷àéíûå âåëè÷èíû áóäåì íàçûâàòü íåïðåðûâíûìè (îïóñêàÿ äîïîëíåíèå àáñîëþòíî).3913.2. Ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ. Ñôîðìóëèðóåì ñòàíäàðòíûé àëãîðèòì (ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ).ÀËÃÎÐÈÒÌ 13.1 (ñì., íàïðèìåð, [1]).

Äëÿ ÷èñëåííîé ðåàëèçàöèè(ìîäåëèðîâàíèÿ) âûáîðî÷íîãî çíà÷åíèÿ ξ0 ñëó÷àéíîé âåëè÷èíû ξ ∈ (a, b)èñïîëüçóåì ôîðìóëóξ0 = F −1 (α0 );(13.7)çäåñü α0 ðåàëèçàöèÿ ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà α.Îáîñíîâàíèå ôîðìóëû (13.7) ñëåäóåò èç òîãî, ÷òî ñëó÷àéíûå âåëè÷èíû ξ è ξ˜ = F −1 (α) îäèíàêîâî ðàñïðåäåëåíû. Äåéñòâèòåëüíî, äëÿx ≤ a èìååì Fξ̃ (x) = P(ξ˜ < x) = F (x) = 0, äëÿ x ≥ b âûïîëíåíîFξ̃ (x) = F (x) = 1, à äëÿ a < x < b ñïðàâåäëèâî ðàâåíñòâîFξ̃ (x) = P(F −1 (α) < x) = P α < F (x) = F (x). ïîñëåäíåé âûêëàäêå èñïîëüçîâàíî óòâåðæäåíèå 10.2.13.3. Ýëåìåíòàðíûå ïëîòíîñòè ðàñïðåäåëåíèÿ.