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

. .ðàâåí 1/M s äëÿ ëþáîãî öåëîãî ïîëîæèòåëüíîãî M .Èç óòâåðæäåíèÿ 10.5 ñëåäóåò, ÷òî ïðè M 1 êîýôôèöèåíò êîððåëÿöèè ìåæäó çàâèñèìûìè âåëè÷èíàìè αn+s è αn íåâåëèê è ðàâåí 1/M s .10.6. Ó÷åò êîíå÷íîñòè ìàíòèññû. Ïåðèîäè÷íîñòü è òåñòèðîâàíèå ìåòîäà âû÷åòîâ. Îòìåòèì, ÷òî óòâåðæäåíèÿ 10.4 è 10.5 ñôîð-ìóëèðîâàíû äëÿ ¾íàñòîÿùåãî¿ ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà α. Ìîæíî ñôîðìóëèðîâàòü àíàëîãè ýòèõ óòâåðæäåíèé â ñëó÷àå ïðèìåíåíèÿìåòîäà (10.3), (10.4) äëÿ ÷èñåë αn ñ îãðàíè÷åííîé ìàíòèññîé äëèíû m.Ïðè ýòîì äëÿ äîñòàòî÷íî áîëüøîãî m ïðè óäà÷íîì ïîäáîðå ìíîæèòåëÿM ñòàòèñòè÷åñêèå ñâîéñòâà ÷ëåíîâ ïîñëåäîâàòåëüíîñòè (10.3), (10.4) è¾íàñòîÿùåãî¿ ñòàíäàðòíîãî ÷èñëà α áëèçêè.Ïðåäïîëîæèì, ÷òî íà÷àëüíûé ýëåìåíò ïîñëåäîâàòåëüíîñòè (10.3),(10.4) ðàâåí α0 = 2−m , à ìíîæèòåëü èìååò âèä M = 52p+1 , ãäå p öåëîåïîëîæèòåëüíîå ÷èñëî.

Òàêîé âûáîð îáúÿñíÿåòñÿ, â ÷àñòíîñòè, òåì, ÷òîìíîãèå ñïåöèàëèñòû èñïîëüçîâàëè è ïðîâåðÿëè ïîñëåäîâàòåëüíîñòè ñìíîæèòåëÿìè M èìåííî òàêîãî âèäà. Ñïðàâåäëèâî ïðåäñòàâëåíèåαn = kn 2−m ; k0 = 1, kn ≡ kn−1 52p+1 (mod 2m ).(10.5)Ñóùåñòâåííûé íåäîñòàòîê ìóëüòèïëèêàòèâíîãî ìåòîäà âû÷åòîâ (10.5)ñâÿçàí ñ òåì, ÷òî êîëè÷åñòâî ÷èñåë, èìåþùèõ ìàíòèññó äëèíû m è ïðèíàäëåæàùèõ èíòåðâàëó (0, 1), ÿâëÿåòñÿ êîíå÷íûì, è ïîýòîìó ïîñëåäîâàòåëüíîñòü (10.5) ÿâëÿåòñÿ ïåðèîäè÷åñêîé, ò. å. ðàíî èëè ïîçäíî êàêîåíèáóäü çíà÷åíèå αL ñîâïàäåò ñî çíà÷åíèåì α0 , è òîãäà, â ñèëó ðàâåíñòâà(10.3), èìååìαL+i = αi ïðè i = 1, 2, .

. .(10.6)30Íàèìåíüøåå ÷èñëî L, óäîâëåòâîðÿþùåå ñîîòíîøåíèþ (10.6), íàçûâàåòñÿäëèíîé ïåðèîäà. Îáû÷íî äëÿ ðàñ÷åòîâ íå ðåêîìåíäóþò èñïîëüçîâàòüáîëüøå ÷åì L/2 ÷èñåë ïîñëåäîâàòåëüíîñòè (10.3), (10.4). Ñòàíäàðòíûìèìåòîäàìè òåîðèè ÷èñåë ìîæíî äîêàçàòü, ÷òî äëÿ ìóëüòèïëèêàòèâíîãîìåòîäà âû÷åòîâ (10.5) ïåðèîä ðàâåí L = 2m−2 . Âåëè÷èíà M = 52p+1 âäâîè÷íîì ïðåäñòàâëåíèè îêàí÷èâàåòñÿ íà 01, ïîýòîìó âñå αn ÿâëÿþòñÿm-ðàçðÿäíûìè äâîè÷íûìè äðîáÿìè, ïîñëåäíèå äâà ðàçðÿäà êîòîðûõðàâíû 01. Âñëåäñòâèå ðàâåíñòâà L = 2m−2 îñòàëüíûå m − 2 ðàçðÿäà¾ïðîáåãàþò¿ âñå âîçìîæíûå êîìáèíàöèè.

Ïîýòîìó â êà÷åñòâå α0 ìîæíîâûáðàòü ëþáóþ m-ðàçðÿäíóþ äâîè÷íóþ äðîáü óêàçàííîãî òèïà.Âîïðîñ î ïðèãîäíîñòè ïñåâäîñëó÷àéíûõ ÷èñåë (10.5) èññëåäóåòñÿ ñïîìîùüþ ñïåöèàëüíûõ ñòàòèñòè÷åñêèõ òåñòîâ è ðåøåíèÿ äîñòàòî÷íîñëîæíûõ òåñòîâûõ çàäà÷. Äëÿ íåêîòîðûõ ïàðàìåòðîâ (m, p) ïîëó÷àþòñÿ óäîâëåòâîðèòåëüíûå ïîñëåäîâàòåëüíîñòè, äëÿ äðóãèõ ïëîõèå. Âíîâîñèáèðñêîé øêîëå ìåòîäîâ Ìîíòå-Êàðëî äëÿ àëãîðèòìîâ ñ ÷èñëîìèñïûòàíèé n ïîðÿäêà 109 è ìåíüøå äîëãèå ãîäû âïîëíå óäîâëåòâîðèòåëüíûì ñ÷èòàåòñÿ ãåíåðàòîð (10.5) ñ ïàðàìåòðàìè m = 40 è p = 8,ïðîøåäøèé âñåñòîðîííåå ìíîãîëåòíåå òåñòèðîâàíèå.  ïîñëåäíåå âðåìÿ â ñâÿçè ñ ðîñòîì ìîùíîñòåé ñîâðåìåííûõ âû÷èñëèòåëüíûõ ñèñòåìâîçíèêëà ïîòðåáíîñòü â ãåíåðàòîðàõ ñ óâåëè÷åííûì ïåðèîäîì.

 ÷àñòíîñòè, äëÿ ïàðàëëåëüíûõ âû÷èñëåíèé èñïîëüçóåòñÿ ãåíåðàòîð (10.5) ñïàðàìåòðàìè m = 128 è p = 50059 èç ðàáîòû [9]. Îïðåäåëåííûå òðóäíîñòè êîíêðåòíîé ðåàëèçàöèè ôîðìóë (10.5) íà êîìïüþòåðå ñâÿçàíû ñòåì, ÷òî íóæíî ïðîèçâîäèòü äåéñòâèÿ ñ ÷èñëàìè, èìåþùèìè ìàíòèññóäëèíû m, ïðåâîñõîäÿùóþ ñòàíäàðòíûé ôîðìàò ÝÂÌ.10.7. Äâà âàæíûõ çàìå÷àíèÿ.  çàêëþ÷åíèå ýòîãî ðàçäåëà ñôîðìóëèðóåì äâà ïðèíöèïèàëüíûõ ñîîáðàæåíèÿ.ÇÀÌÅ×ÀÍÈÅ 10.2. Êàê ïðàâèëî, ãåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåë, ïðåäñòàâëåííûå â ñîâðåìåííûõ âåðñèÿõ ÿçûêîâ ïðîãðàììèðîâàíèÿ(FORTRAN, PASCAL, ÑÈ++ è äð.) äîñòàòî÷íî õîðîøî ïðîòåñòèðîâàíû è äàþò ñòàòèñòè÷åñêè óäîâëåòâîðèòåëüíûå ðåçóëüòàòû âû÷èñëåíèé ïî ìåòîäó Ìîíòå-Êàðëî (âî âñÿêîì ñëó÷àå, äëÿ çàäà÷, â êîòîðûõ èñïîëüçóåòñÿ óìåðåííî áîëüøîå êîëè÷åñòâî âûáîðî÷íûõ çíà÷åíèé ñëó÷àéíûõ âåëè÷èí).

Ïîýòîìó, íåñìîòðÿ íà ñôîðìóëèðîâàííûåâûøå çàìå÷àíèÿ î âîçìîæíûõ íåäîñòàòêàõ äàò÷èêîâ (êîíå÷íîñòü èñïîëüçóåìîé ìàíòèññû, ïåðèîäè÷íîñòü è ò. ï.), â äàëüíåéøåì áóäåìïîëàãàòü, ÷òî èñïîëüçóåìûé â ðàñ÷åòàõ ãåíåðàòîð ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë äàåò ¾íàñòîÿùèå¿ (òåîðåòè÷åñêèå) âûáîðî÷íûå çíà÷åíèÿ α.31Çàìåòèì, îäíàêî, ÷òî äëÿ ïðîâåäåíèÿ ïðåöåçèîííûõ ðàñ÷åòîâ öåëåñîîáðàçíî èñïîëüçîâàòü äàò÷èê, ðåçóëüòàòû ïðîâåðêè êîòîðîãî èçâåñòíû. Îñîáóþ ðîëü èãðàþò êîíòðîëüíûå ðàñ÷åòû äëÿ çàäà÷ (áëèçêèõ êðåàëüíûì) ñ èçâåñòíûì ðåøåíèåì.ÇÀÌÅ×ÀÍÈÅ 10.3. Ìóëüòèïëèêàòèâíûé ìåòîä âû÷åòîâ (10.5),äàæå ðåàëèçîâàííûé îïòèìàëüíî äëÿ èñïîëüçóåìîãî ÿçûêà ïðîãðàììèðîâàíèÿ, ÿâëÿåòñÿ îòíîñèòåëüíî òðóäîåìêèì (ïî ñðàâíåíèþ, íàïðèìåð, ñ ïðîñòûì óìíîæåíèåì ÷èñåë).

Ïîýòîìó ïðè îïòèìèçàöèè àëãîðèòìîâ ìåòîäà Ìîíòå-Êàðëî öåëåñîîáðàçíî ïî-âîçìîæíîñòè óìåíüøàòü ÷èñëî îáðàùåíèé ê ïîäïðîãðàììå òèïà RAN DOM .11. Ñòàíäàðòíûé ìåòîä ìîäåëèðîâàíèÿ äèñêðåòíîãîðàñïðåäåëåíèÿ è åãî òðóäîåìêîñòü11.1. Ïîðÿäîê èçó÷åíèÿ àëãîðèòìîâ ÷èñëåííîãî ìîäåëèðîâàíèÿ ñëó÷àéíûõ âåëè÷èí. Íàëè÷èå íàäåæíîãî ãåíåðàòîðà ñòàí-äàðòíûõ ñëó÷àéíûõ ÷èñåë α ïîçâîëÿåò ïîëó÷àòü âûáîðî÷íûå çíà÷åíèÿξj ñëó÷àéíûõ âåëè÷èí ξ (îäíîìåðíûõ è ìíîãîìåðíûõ) ñ ïðîèçâîëüíûìè çàêîíàìè ðàñïðåäåëåíèÿ. Ïîðÿäîê îïèñàíèÿ ñîîòâåòñòâóþùèõ àëãîðèòìîâ â ýòîì ïîñîáèè àíàëîãè÷åí ïîðÿäêó èçó÷åíèÿ ñëó÷àéíûõ âåëè÷èí â êóðñàõ òåîðèè âåðîÿòíîñòåé: ¾îò ïðîñòîãî ê ñëîæíîìó¿ (ñì.,íàïðèìåð, [2]).

Ñíà÷àëà áóäóò èçó÷åíû àëãîðèòìû ìîäåëèðîâàíèÿ äëÿäèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí, çàòåì äëÿ îäíîìåðíûõ àáñîëþòíîíåïðåðûâíûõ âåëè÷èí è äàëåå äëÿ ìíîãîìåðíûõ ñëó÷àéíûõ âåëè÷èí(èëè ñëó÷àéíûõ âåêòîðîâ). Äëÿ êàæäîãî òèïà ñëó÷àéíûõ âåëè÷èí áóäåòïðåäñòàâëåí ñîîòâåòñòâóþùèé ñòàíäàðòíûé àëãîðèòì. Ó÷èòûâàÿ òî îáñòîÿòåëüñòâî, ÷òî ïðè ðåàëèçàöèè ìåòîäà Ìîíòå-Êàðëî (1.1) òðåáóåòñÿïîëó÷àòü áîëüøîå êîëè÷åñòâî n 1 âûáîðî÷íûõ çíà÷åíèé, îñîáîå âíèìàíèå áóäåò óäåëÿòüñÿ òðóäîåìêîñòè ïðåäñòàâëÿåìûõ àëãîðèòìîâ. Äëÿðÿäà âàæíåéøèõ (ñ ïðèêëàäíîé òî÷êè çðåíèÿ) ðàñïðåäåëåíèé ñòàíäàðòíûå àëãîðèòìû ëèáî íå ðåàëèçóåìû, ëèáî íå ýôôåêòèâíû.

 ýòèõ ñëó÷àÿõ ïðåäïðèíèìàþòñÿ (÷àñòî äîâîëüíî óñïåøíûå) ïîïûòêè ïîñòðîèòüñïåöèàëüíûå àëãîðèòìû ìîäåëèðîâàíèÿ, ó÷èòûâàþùèå ñâîéñòâà çàäàííîãî ðàñïðåäåëåíèÿ (ñì., íàïðèìåð, [1], à òàêæå ðàçä. 12 è 17).11.2. Ñòàíäàðòíûé àëãîðèòì ìîäåëèðîâàíèÿ äèñêðåòíîãîðàñïðåäåëåíèÿ. Ðàññìîòðèì âîïðîñ î ìîäåëèðîâàíèè äèñêðåòíîé ñëó-÷àéíîé âåëè÷èíû ξ ñ êîíå÷íûì ÷èñëîì çíà÷åíèé x1 , . .

. , xN è ðàñïðåäå-32ëåíèåì âåðîÿòíîñòåéP(ξ = xi ) = pi ; pi > 0,NXpi = 1;(11.1)i=1äàëåå â ïîäðàçä. 11.5 ðàññìîòðåí ñëó÷àé ñ÷åòíîãî ÷èñëà çíà÷åíèé, äëÿêîòîðîãî N = ∞. ñèëó ñîîòíîøåíèé (11.1), ðåàëèçàöèÿ òîãî èëè èíîãî çíà÷åíèÿ xmñëó÷àéíîé âåëè÷èíû ξ îçíà÷àåò ðîçûãðûø ñîáûòèÿ ñ âåðîÿòíîñòüþ pm .Êðîìå òîãî, èç ñîîòíîøåíèé (11.1) ñëåäóåò, ÷òî èíòåðâàë (0, 1) ìîæíîðàçáèòü íà ïîëóèíòåðâàëû ∆m äëèíû pm :∆m = [Rm−1 , Rm ); Rm =mXpi ; m = 1, 2, . . . , N ;i=1äëÿ m = 1 ïîëàãàåì Rm−1 = R0 = 0. Èñïîëüçóÿ ñîîòâåòñòâóþùèé ãåíåðàòîð, ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå α0 ñòàíäàðòíîãî ñëó÷àéíîãî÷èñëà.  ñèëó óòâåðæäåíèÿ 10.2, èìååì P(α ∈ ∆m ) = pm .

Òàêèì îáðàçîì, åñëè α0 ∈ ∆m , òî äëÿ äàííîãî èñïûòàíèÿ ïîëàãàåì, ÷òî âûáîðî÷íîåçíà÷åíèå ñëó÷àéíîé âåëè÷èíû ξ ðàâíî ξ0 = xm .Òåõíè÷åñêè îïðåäåëåíèå òîãî íîìåðà m ïîëóèíòåðâàëà ∆m , â êîòîðûé ïîïàëî âûáîðî÷íîå çíà÷åíèå α0 , îñóùåñòâëÿåòñÿ ïîñëåäîâàòåëüíûì âû÷èòàíèåì èç α0 ñóìì Rm äëÿ m = 1, 2, . . . äî òåõ ïîð, ïîêà ðàçíîñòü α0 − Rm íå ñòàíåò îòðèöàòåëüíîé. Îïèñàííóþ îïåðàöèþ ìîæíîîñóùåñòâëÿòü áåç íåïîñðåäñòâåííîãî âû÷èñëåíèÿ ñóìì Rm , èñïîëüçóÿîïåðàöèþ ïåðåïðèñâàèâàíèÿ.ÀËÃÎÐÈÒÌ 11.1 (ñì., íàïðèìåð. [1]).

Ðåàëèçóåì çíà÷åíèå Q := α0(ò. å. Q := RAN DOM ) è ïîëàãàåì m := 1. Ïðîèçâîäèì ïåðåïðèñâàèâàíèåQ := Q − pm(11.2)(ò. å. çàíîñèì íîâîå çíà÷åíèå (α0 − p1 ) â ÿ÷åéêó Q). Åñëè íîâîå Q íåïîëîæèòåëüíî, òî â êà÷åñòâå m âûáèðàåì òåêóùåå åãî çíà÷åíèå èïîëàãàåì ξ0 = xm , â ïðîòèâíîì ñëó÷àå ïðîèçâîäèì ïåðåïðèñâàèâàíèÿm := m + 1 è (11.2) è âíîâü ïðîèçâîäèì ïðîâåðêó Q íà ïîëîæèòåëüíîñòü è ò.

ä.Âàæíûì ïðèìåðîì äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí ÿâëÿþòñÿ öåëî÷èñëåííûå ñëó÷àéíûå âåëè÷èíû η , äëÿ êîòîðûõxi = i, P(η = i) = pi ; i = 1, 2, . . . , N.33(11.3)Àëãîðèòì 11.1 â ýòîì ñëó÷àå èìååò ñëåäóþùèé âèä.ÀËÃÎÐÈÒÌ 11.2. Ðåàëèçóåì çíà÷åíèå Q := α0 è ïîëàãàåì m := 1.Ïðîèçâîäèì ïåðåïðèñâàèâàíèå (11.2). Åñëè íîâîå çíà÷åíèå Q íå ïîëîæèòåëüíî, òî ïîëàãàåì η0 = m, â ïðîòèâíîì ñëó÷àå ïðîèçâîäèì ïåðåïðèñâàèâàíèÿ m := m + 1 è (11.2) è âíîâü ïðîèçâîäèì ïðîâåðêó Q íàïîëîæèòåëüíîñòü è ò. ä.11.3.

Òðóäîåìêîñòü ñòàíäàðòíîãî àëãîðèòìà.  ðàçä. 4 óêàçàíî, ÷òî â ôîðìóëå (4.1) äëÿ òðóäîåìêîñòè ìåòîäà Ìîíòå-Êàðëî (1.1)âåëè÷èíà t ÿâëÿåòñÿ ñðåäíèì âðåìåíåì âû÷èñëåíèÿ îäíîãî âûáîðî÷íîãî çíà÷åíèÿ ζj . Ñëîâî ñðåäíåå çäåñü ïðèíöèïèàëüíî, òàê êàê çàòðàòû íàìîäåëèðîâàíèå êîíêðåòíîãî âûáîðî÷íîãî çíà÷åíèÿ ζj ÿâëÿþòñÿ, âîîáùå ãîâîðÿ, ñëó÷àéíûìè. Ýòî ïðîÿâëÿåòñÿ óæå íà ïðîñòåéøåì ïðèìåðåñëó÷àéíîé âåëè÷èíû ξ ñ äèñêðåòíûì ðàñïðåäåëåíèåì (åñëè ñòàâèòü çàPNäà÷ó âû÷èñëåíèÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ Eξ = i=1 xi pi ìåòîäîìÌîíòå-Êàðëî, íàïðèìåð, ñ öåëüþ òåñòèðîâàíèÿ ãåíåðàòîðîâ ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë).Ëåãêî âèäåòü, ÷òî â ñëó÷àå, êîãäà ξ0 = xm , ïðèõîäèòñÿ îñóùåñòâëÿòü m ïðîâåðîê Q íà ïîëîæèòåëüíîñòü.

 îáùèå çàòðàòû δ àëãîðèòìà11.1 âõîäÿò çàòðàòû íà ìîäåëèðîâàíèå îäíîé ñòàíäàðòíîé ñëó÷àéíîéâåëè÷èíû (èõ îáîçíà÷èì a) è ðåàëèçàöèþ ñðàâíåíèé Q ñ íóëåì (çàòðàòû íà êàæäîå ñðàâíåíèå îáîçíà÷èì b). Òîãäà ñðåäíÿÿ òðóäîåìêîñòü tàëãîðèòìà ðàâíà!NXt = Eδ = a +ipi × b.(11.4)i=1Çàìåòèì, ÷òî äëÿ öåëî÷èñëåííîé ñëó÷àéíîé âåëè÷èíû η ñ ðàñïðåäåëåíèåì (11.3) âåëè÷èíà t èç (11.4) ïðåäñòàâèìà â âèäåt1 = a + b Eη.(11.5)Ïðè ðåàëèçàöèè àëãîðèòìîâ 11.1 è 11.2 öåëåñîîáðàçíî (åñëè ýòî âîçìîæíî) ðàñïîëàãàòü âåðîÿòíîñòè pi â ïîðÿäêå èõ óáûâàíèÿ.11.4. Ñëó÷àé ìàëîãî ÷èñëà çíà÷åíèé ñëó÷àéíîé âåëè÷èíû.Îòìåòèì, ÷òî â àëãîðèòìå 11.1 âîçìîæíà ñëåäóþùàÿ ìîäèôèêàöèÿ. Åñëè α0 − RN −1 > 0, òî ïîñëåäíåå âû÷èòàíèå ìîæíî íå ïðîèçâîäèòü, òàêêàê â ýòîì ñëó÷àå α0 ∈ ∆N . Ñîîòâåòñòâóþùèå àíàëîãè ôîðìóë (11.4) è(11.5) èìåþò âèä!N−1Xt=a+ipi + (N − 1) pN × b; t1 = a − b pN + b Eη.i=134Îäíàêî âûèãðûø îò ýòîé ìîäèôèêàöèè ñêàçûâàåòñÿ òîëüêî äëÿ ìàëûõN , òàê êàê ïðè åå ïðèìåíåíèè òðåáóåòñÿ ïðîâîäèòü ñðàâíåíèå òåêóùåãîm c (N − 1).Ðàññìîòðèì, â ÷àñòíîñòè, ñëó÷àé N = 2.