1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 4
Текст из файла (страница 4)
Äîâåðèòåëüíàÿ22ãðàíèöà ñðàâíèâàåòñÿ ñî çíà÷åíèåì χ̃r−1 (n) èç (1.15), è åñëè χ̃r−1 (n) < χ2 (r − 1, 1 − ε), òîèññëåäóåìàÿ âûáîðêà {ξj } ñ÷èòàåòñÿ óäîâëåòâîðèòåëüíîé, à åñëè χ̃2r−1 (n) ≥ χ2 (r−1, 1−ε) íåóäîâëåòâîðèòåëüíîé. Äëÿ êðèòåðèÿ χ2 ðåêîìåíäóåòñÿ âûáèðàòü n è r òàêèì îáðàçîì, ÷òîáû âûïîëíÿëîñü íåðàâåíñòâî n/r ≥ 10.Äëÿ ïðîâåðêè ñâîéñòâà k -ðàâíîìåðíîñòè ïðèìåíÿåòñÿ òàêæå ðÿä äðóãèõ òåñòîâ.Ïðåæäå âñåãî óïîìÿíåìk", îñíîâàííûé íà ïåðåõîäå îò âåêòîðîâ(1.11) ê ñîîòâåòñòâóþùèì k -ìåðíûì âåêòîðàì íåçàâèñèìûõ ñòàíäàðòíûõ íîðìàëüíûõñëó÷àéíûõ âåëè÷èí.Âåñüìà øèðîêîå ïðèìåíåíèå èìåþò, îñíîâàííûå íà êðèòåðèèÂåéëÿ.(k)Óòâåðæäåíèå 1.7.{αn }(1.11)käîâåðèòåëüíîé ãðàíèöåé ñ óðîâíåì çíà÷èìîñòèòåñò " -íîðìàëüíîñòèñïåêòðàëüíûå òåñòûÄëÿ òîãî, ÷òîáû ïîñëåäîâàòåëüíîñòüèçáûëàðàñïðåäåëåíà ðàâíîìåðíî â -ìåðíîì åäèíè÷íîì êóáå, íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèå ðàâåíñòâàN1 Xexp(2πi(s1 αk(n−1)+1 + .
. . + sk αnk )) = 0.N →∞ Nn=1limäëÿ âñåõ öåëûõ s1, . . . , sk , íå ðàâíûõ îäíîâðåìåííî íóëþ.(1.16)Çäåñü ïîä k -ðàâíîìåðíîñòüþ ïîíèìàåòñÿ âûïîëíåíèå ñîîòíîøåíèÿ (1.12). Óïîìÿíåì, â ÷àñòíîñòè,, äëÿ êîòîðîãî ñ èñïîëüçîâàíèåì òðèãîíîìåòðè÷åñêèõîðòîãîíàëüíûõ áàçèñîâ îñóùåñòâëÿåòñÿ ïåðåõîä îò ñîîòíîøåíèÿ (1.16) ê ñëåäóþùåéêîíñòðóêöèè äëÿ ìåòîäà âû÷åòîâ (1.8), (1.10) ñ ìíîæèòåëåì M äëÿ ÷èñåë αn ñ îãðàíè÷åííîé ìàíòèññîé äëèíû m.Ðàññìàòðèâàþòñÿ âñåâîçìîæíûå íàáîðû öåëûõ ÷èñåë (s1 , s2 , .
. . , sk ) òàêèõ, ÷òî ñóìk−1ìà s1 + s2 M + s3 M 2 +ðàâíà íóëþ (ïî ìîäóëþ 2m ). ÂâîäèòñÿP.k. . +2 sk MW = mins1 ,...,sk i=1 si . Ñ÷èòàåòñÿ, ÷òî ïîñëåäîâàòåëüíîñòü îáëàäàåò ñâîéñòâîìk -ðàâíîìåðíîñòè, åñëè ÷èñëî W äîñòàòî÷íî âåëèêî (áîëåå òî÷íàÿ èíôîðìàöèÿ äàíà â[4]).
Èç îïðåäåëåíèÿ âîëíîâîãî ÷èñëà ñëåäóåò, ÷òî åñëè ïðè íåêîòîðîì k âîëíîâîå ÷èñëîìàëî, òî îíî íå âîçðàñòàåò è äëÿ k + 1. Âìåñòå ñ òåì, áîëüøîå çíà÷åíèå W ïðè íåêîòîðîì k íå ãàðàíòèðóåò óäîâëåòâîðèòåëüíîé âåëè÷èíû W äëÿ k + 1, ïîýòîìó ñëåäóåòíàõîäèòü çíà÷åíèÿ âîëíîâûõ ÷èñåë äëÿ íåêîòîðîãî ïðåäñòàâèòåëüíîãî íàáîðà ðàçìåðíîñòåé. Ïðåïÿòñòâèåì äëÿ ðàñïðîñòðàíåíèÿ âîëíîâîãî òåñòà ÿâëÿåòñÿ òî, ÷òî òåîðèåéíå íàéäåíà ôóíêöèÿ ðàñïðåäåëåíèÿ äëÿ W .Ó÷èòûâàÿ óòâåðæäåíèå 1.3, ïðè ïðîâåðêå ãåíåðàòîðîâ ìîæíî èññëåäîâàòü ñëó÷àéíîñòü öèôð ñòàíäàðòíûõ ÷èñåë α. Çäåñü ïðîâåðÿþò ÷àñòîòó ïîÿâëåíèÿ ðàçëè÷íûõ öèôðâ ÷èñëàõ, ðåàëèçóåìûõ ãåíåðàòîðîì (òåñò "ïðîâåðêà ÷àñòîò"); ÷àñòîòó ðàçëè÷íûõ äâóçíà÷íûõ ÷èñåë ñðåäè ïàð öèôð, ðåàëèçóåìûõ ïîäðÿä ãåíåðàòîðîì (òåñò "ïðîâåðêà ïàð");÷àñòîòó ðàçëè÷íûõ èíòåðâàëîâ ìåæäó äâóìÿ ïîñëåäîâàòåëüíûìè íóëÿìè (òåñò "ïðîâåðêà èíòåðâàëîâ"); ÷àñòîòó ðàçëè÷íûõ ÷åòûðåõçíà÷íûõ ÷èñåë ñðåäè ÷åòâåðîê öèôð,ðåàëèçóåìûõ ïîäðÿä (òåñò "ïðîâåðêà êîìáèíàöèé"); ÷àñòîòó ïîÿâëåíèÿ q îäèíàêîâûõöèôð ïîäðÿä ("òåñò ñåðèé"äëèíû q ) è äð.
 óïîìÿíóòûõ òåñòàõ òàêæå àêòèâíî èñïîëüçóåòñÿ êðèòåðèé õè-êâàäðàò.Äëÿ ïðîâåðêè êà÷åñòâà ñòàíäàðòíûõ ñëó÷àéíûõ è ïñåâäîñëó÷àéíûõ ÷èñåë èñïîëüçóþò òàêæå êðèòåðèé ω 2 Í.Â.Ñìèðíîâà, êîððåëÿöèîííûå êðèòåðèè è äð.Èçâåñòíû ýôôåêòèâíûå ìîäèôèêàöèè ìóëüòèïëèêàòèâíîãî ìåòîäà âû÷åòîâ, ñâÿçàííûå ñ èñïîëüçîâàíèåì îïåðàöèè êîíãðóýíòíîãî (ò.å. ïî ìîäóëþ 1) ñóììèðîâàíèÿ ïîñëåäîâàòåëüíîñòåé âèäà (1.13), à òàêæå ñ ïðèìåíåíèåì ôèçè÷åñêîãî äàò÷èêà äëÿ ïîëó÷åíèÿíà÷àëüíîãî ÷èñëà α0 (öåëåñîîáðàçíîñòü òàêîãî âûáîðà íà÷àëüíîãî ÷ëåíà ïîñëåäîâàòåëüíîñòè (1.8) ñëåäóåò èç óòâåðæäåíèÿ 1.6).âîëíîâîé òåñòâîëíîâîå÷èñëî1.1.6.
Èñïîëüçîâàíèå äàò÷èêîâ ïñåâäîñëó÷àéíûõ ÷èñåë â ïàðàëëåëüíûõâû÷èñëåíèÿõ. Ñôîðìóëèðóåì ðÿä çàìå÷àíèé îòíîñèòåëüíî âîçìîæíîñòåé ðàñïàðàëëåëèâàíèÿ àëãîðèòìîâ ìåòîäà Ìîíòå-Êàðëî. ßñíî, ÷òî èñïîëüçîâàíèå K íåçàâèñèìûõïðîöåññîðîâ ïóòåì ðàñïðåäåëåíèÿ ìåæäó íèìè íåçàâèñèìûõ èñïûòàíèé óìåíüøàåò òðóäîåìêîñòü ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ â K ðàç, ïîñêîëüêó çàòðàòû íà çàêëþ÷èòåëüíîå ñóììèðîâàíèå â ôîðìóëå (0.1) è îñðåäíåíèå ðåçóëüòàòîâ ïðàêòè÷åñêè íåñóùåñòâåííû. Êîíå÷íî, ïðè ýòîì ñëåäóåò äîïóñêàòü âîçìîæíîñòü ðåàëèçàöèè ðàçëè÷íûõ îáúåìîââûáîðîê {nk } íà ðàçëè÷íûõ ïðîöåññàõ ñ èñïîëüçîâàíèåì ñòàòèñòè÷åñêè îïòèìàëüíîãîñïîñîáà îñðåäíåíèÿ ïî ôîðìóëàì âèäàK1Xnk ζ̄nk ,ζ̄n =n k=1n=KXnk ,k=1ãäå ζ̄nk ñðåäíåå çíà÷åíèå, ïîëó÷åííîå íà k -îì ïðîöåññîðå.
Êàê óêàçàíî âûøå, åñëè K(è, ñîîòâåòñòâåííî, n) âåëèêî, òî íåîáõîäèìûé îáúåì âûáîðêè ñòàíäàðòíûõ ñëó÷àéíûõ÷èñåë òîæå âåëèê, ïîýòîìó öåëåñîîáðàçíî èñïîëüçîâàíèå äëèííîïåðèîäíûõ ïñåâäîñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé, äëÿ êîòîðûõ ñóùåñòâóåò ïðîñòîé ñïîñîá èõ ðàçáèåíèÿ íàK ÷àñòåé íåîáõîäèìîé äëèíû. Ìåòîä âû÷åòîâ (1.13) äàåò ýëåìåíòàðíûé ñïîñîá òàêîãîðàçáèåíèÿ.
Ïóñòü µ >> 1 êîëè÷åñòâî ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë, òðåáóþùèõñÿäëÿ âû÷èñëåíèé íà îäíîì ïðîöåññîðå. Äëÿ k -ãî ïðîöåññîðà íà÷àëüíîå ÷èñëî â ìåòîäåâû÷åòîâ ñ ìíîæèòåëåì M âûáåðåì ïî ôîðìóëå(k,µ)α0= uk,µ /2m ;uk,µ = uk−1,µ M µ (mod 2m ).(1.17)bf-ãåíåðàòîðîìÒàêîé ñïîñîá ðàñïðåäåëåíèÿ ñëó÷àéíûõ ÷èñåë ïî ïðîöåññîðàì íàçûâàþò(ñîêðàùåíèå îò "big-frog-ãåíåðàòîð).  îòäåëå ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ â ôèçèêåÈíñòèòóòà âû÷èñëèòåëüíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé ãåîôèçèêè ÑÎ ÐÀÍ ðåàëèçîâàí bf-ãåíåðàòîð ñ µ = 1026 (â êà÷åñòâå èñõîäíîãî èñïîëüçóåòñÿ äàò÷èê (1.13) ñ ïàðàìåòðàìè m = 128 è p = 50059). Ñîîòâåòñòâóþùèõ êîëè÷åñòâ ïñåâäîñëó÷àéíûõ ÷èñåëäëÿ êàæäîãî ïðîöåññîðà ñ èçáûòêîì õâàòàåò äëÿ âû÷èñëèòåëüíûõ ïîòðåáíîñòåé. Ãåíåðàòîð ïîçâîëÿåò, âîîáùå ãîâîðÿ, ðàñïðåäåëÿòü èñõîäíóþ ïîñëåäîâàòåëüíîñòü ïðèìåðíîíà 1012 ïðîöåññîðîâ. Ïîäðîáíîå îïèñàíèå ãåíåðàòîðà, ïðîãðàììû âû÷èñëåíèÿ íà÷àëüíûõ çíà÷åíèé (1.17), ìíîæèòåëåé Mµ = M µ (mod 2m ), à òàêæå ðåçóëüòàòû òåñòèðîâàíèÿäàò÷èêà ïðèâåäåíû â [3].Îòìåòèì, ÷òî â ñëó÷àå, êîãäà µ íåâåëèêî è ðàâíî êîëè÷åñòâó ïñåâäîñëó÷àéíûõ ÷èñåë, òðåáóþùèõñÿ äëÿ ïîñòðîåíèÿ îäíîé òðàåêòîðèè, èñïîëüçîâàíèå ÷èñåë (1.17) â êà÷åñòâå íà÷àëüíûõ äëÿ êàæäîé òðàåêòîðèè îïðåäåëÿåò(ñîêðàùåíèå îò "littlefrog-ãåíåðàòîð).
 îòëè÷èå îò îáû÷íîãî ñïîñîáà ðàñïðåäåëåíèÿ ñëó÷àéíûõ ÷èñåë "ïîäðÿä"(ò. å. â ïîðÿäêå îáðàùåíèÿ ê ãåíåðàòîðó (1.13)) lf-ãåíåðàòîð îáåñïå÷èâàåò ìàëîå èçìåíåíèå ðåçóëüòàòîâ ìîäåëèðîâàíèÿ ïðè ìàëîì èçìåíåíèè ïàðàìåòðîâ çàäà÷è.  ñâÿçèñ ýòèì lf-ãåíåðàòîð áîëåå êîððåêòíî ïðîâåðÿåòñÿ ðåøåíèåì òèïîâûõ çàäà÷ ïî ñðàâíåíèþñ îáû÷íûì ãåíåðàòîðîì (1.13). Êðîìå òîãî, lf-ãåíåðàòîð áîëüøå ñîîòâåòñòâóåò íàèáîëååâàæíûì òåñòàì íà k -ìåðíóþ ðàâíîìåðíîñòü äëÿ çàäà÷ îöåíêè ìíîãîêðàòíûõ èíòåãðàëîâ (ñì. ïîäðàçä.
1.1.3, 1.1.5).lf-ãåíåðàòîð1.2. ÌÎÄÅËÈÐÎÂÀÍÈÅ ÄÈÑÊÐÅÒÍÎÃÎ ÐÀÑÏÐÅÄÅËÅÍÈß(ÑÒÀÍÄÀÐÒÍÛÉ ÀËÃÎÐÈÒÌ)Íàëè÷èå íàäåæíîãî ãåíåðàòîðà ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë α (ñì. çàìå÷àíèå 1.1) ïîçâîëÿåò ïîëó÷àòü âûáîðî÷íûå çíà÷åíèÿ ñëó÷àéíûõ âåëè÷èí (îäíîìåðíûõ è ìíîãîìåðíûõ) ñ ïðîèçâîëüíûìè çàêîíàìè ðàñïðåäåëåíèÿ.Ïîðÿäîê îïèñàíèÿ ñîîòâåòñòâóþùèõ àëãîðèòìîâ â ýòîé ãëàâå àíàëîãè÷åí ïîðÿäêó èçó÷åíèÿ ñëó÷àéíûõ âåëè÷èí â êóðñàõ òåîðèè âåðîÿòíîñòåé: "îò ïðîñòîãî ê ñëîæíîìó"[5,6]. Ñíà÷àëà áóäóò èçó÷åíû àëãîðèòìû ìîäåëèðîâàíèÿ äëÿ äèñêðåòíûõ ñëó÷àéíûõ âåëè÷èí, çàòåì äëÿ îäíîìåðíûõ àáñîëþòíî íåïðåðûâíûõ âåëè÷èí è äàëåå äëÿ ìíîãîìåðíûõ ñëó÷àéíûõ âåëè÷èí (èëè ñëó÷àéíûõ âåêòîðîâ). Äëÿ êàæäîãî òèïà ñëó÷àéíûõ âåëè÷èí áóäåò ïðåäñòàâëåí ñîîòâåòñòâóþùèé ñòàíäàðòíûé àëãîðèòì.
Ó÷èòûâàÿ òî îáñòîÿòåëüñòâî, ÷òî ïðè ðåàëèçàöèè ìåòîäà Ìîíòå-Êàðëî (0.1) òðåáóåòñÿ ïîëó÷àòü áîëüøîåêîëè÷åñòâî n >> 1 âûáîðî÷íûõ çíà÷åíèé, îñîáîå âíèìàíèå áóäåò óäåëÿòüñÿ òðóäîåìêîñòè ïðåäñòàâëÿåìûõ àëãîðèòìîâ. Äëÿ ðÿäà âàæíåéøèõ (ñ ïðèêëàäíîé òî÷êè çðåíèÿ)ðàñïðåäåëåíèé ñòàíäàðòíûå àëãîðèòìû ëèáî íå ðåàëèçóåìû, ëèáî íå ýôôåêòèâíû. Âýòèõ ñëó÷àÿõ ïðåäïðèíèìàþòñÿ (÷àñòî äîâîëüíî óñïåøíûå) ïîïûòêè ïîñòðîèòü ñïåöèàëüíûå àëãîðèòìû ìîäåëèðîâàíèÿ, ó÷èòûâàþùèå ñâîéñòâà çàäàííîãî ðàñïðåäåëåíèÿ [2,79].Ðàññìîòðèì âîïðîñ î ìîäåëèðîâàíèè äèñêðåòíîé ñëó÷àéíîé âåëè÷èíû ξ ñ êîíå÷íûì1.2.1. Ñòàíäàðòíûé àëãîðèòì.÷èñëîì çíà÷åíèé x1 , .
. . , xN è ðàñïðåäåëåíèåì âåðîÿòíîñòåéP(ξ = xi ) = pi ;NXpi > 0,pi = 1.(1.18)i=1 ñèëó ñîîòíîøåíèé (1.18) ðåàëèçàöèÿ òîãî èëè èíîãî çíà÷åíèÿ xm ñëó÷àéíîé âåëè÷èíûξ îçíà÷àåò ðîçûãðûø ñîáûòèÿ ñ âåðîÿòíîñòüþ pm . Êðîìå òîãî, èç ñîîòíîøåíèé (1.18)ñëåäóåò, ÷òî èíòåðâàë (0, 1) ìîæíî ðàçáèòü íà ïîëóèíòåðâàëû ∆m äëèíû pm :∆m = [Rm−1 , Rm ); Rm =mXpi ;m = 1, 2, . . . , N ;i=1äëÿ m = 1 ïîëàãàåì Rm−1 = R0 = 0. Èñïîëüçóÿ ñîîòâåòñòâóþùèé ãåíåðàòîð, ðåàëèçóåìâûáîðî÷íîå çíà÷åíèå α ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà.
 ñèëó óòâåðæäåíèÿ 1.2 èìååìP(α ∈ ∆m ) = pm . Òàêèì îáðàçîì, åñëè α ∈ ∆m , òî äëÿ äàííîãî èñïûòàíèÿ ïîëàãàåìξ = xm .Òåõíè÷åñêè îïðåäåëåíèå òîãî íîìåðà m ïîëóèíòåðâàëà ∆m , â êîòîðûé ïîïàëî âûáîðî÷íîå çíà÷åíèå α, îñóùåñòâëÿåòñÿ ïîñëåäîâàòåëüíûì âû÷èòàíèåì èç α ñóìì Rm äëÿm = 1, 2, . . . äî òåõ ïîð, ïîêà ðàçíîñòü α − Rm íå ñòàíåò îòðèöàòåëüíîé. Îïèñàííóþîïåðàöèþ ìîæíî îñóùåñòâëÿòü áåç íåïîñðåäñòâåííîãî âû÷èñëåíèÿ ñóìì Rm , èñïîëüçóÿîïåðàöèþ ïåðåïðèñâàèâàíèÿ.Àëãîðèòì 1.1.Q := αQ := RAN DOMm := 1Ðåàëèçóåì çíà÷åíèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
