1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 14
Текст из файла (страница 14)
. , pN }. Äðóãèìè ñëîâàìè, ðå÷ü èäåò î ìîäåëèðîâàíèè öåëî÷èñëåííîé ñëó÷àéíîé âåëè÷èíû m ñ ðàñïðåäåëåíèåì P(m = i) = pi . Äëÿ îáîñíîâàíèÿìîäèôèêàöèé îñíîâíîãî àëãîðèòìà 1.1 (â ÷àñòíîñòè, ìåòîäà Óîëêåðà ñì. àëãîðèòì1.6, è ìåòîäà 'ìàæîðàíòíîé ÷àñòîòû' ñì. àëãîðèòì 1.9) öåëåñîîáðàçíî ðàññìîòðåòüíåïðåðûâíóþ ñëó÷àéíóþ âåëè÷èíó ξ , ïðèíèìàþùóþ çíà÷åíèÿ íà èíòåðâàëå (1, N + 1),ñ êóñî÷íî-ïîñòîÿííîé ïëîòíîñòüþ ðàñïðåäåëåíèÿp1 ïðè u ∈ (1, 2), p2 ïðè u ∈ [2, 3),...f (u) =(1.109)pN ïðè u ∈ [N, N + 1),0 ïðè u ∈/ (1, N + 1),íûõ âåëè÷èí.íàçâàííîé â ïîäðàçä.
1.3.3 "äèàãðàììîé". Çàìåòèì, ÷òîZ i+1P ξ ∈ [i, i + 1) =f (u) du = pi è m = [ξ];(1.110)içäåñü [A] îáîçíà÷àåò öåëóþ ÷àñòü ÷èñëà A.Ïðè ñäåëàííûõ ïðåäïîëîæåíèÿõ íåñëîæíî óâèäåòü, ÷òî â àëãîðèòìå 1.9 âûáîð íîìåðà m ñîîòâåòñòâóåò ïðîñòåéøåé ìîäèôèêàöèè ìàæîðàíòíîãî ìåòîäà èñêëþ÷åíèÿ ìåòîäó Íåéìàíà (ñì. àëãîðèòì 1.25), ãäå â êà÷åñòâå ìàæîðàíòû ôóíêöèè f (u) áåðåòñÿïîñòîÿííàÿ ôóíêöèÿ g1 (u) ≡ max{p1 , . . . , pN } ïðè u ∈ (1, N + 1). Äðóãèìè ñëîâàìè,àëãîðèòì 1.9 ìîæíî ïåðåïèñàòü â ñëåäóþùåì âèäå:ξ1 = α1 N + 1 η = α2 max{p1 , .
. . , pN }η ≤ f (ξ1 )ξ = ξ1 m = [ξ1 ]1Àíàëîãè÷íóþ òðàêòîâêó äîïóñêàåò ìåòîä Óîëêåðà (àëãîðèòì 1.6). Çäåñü ïðîèñõîäèò ðîçûãðûø òî÷êè (ξ1 = α1 N + 1; η1 = α2 ), ðàâíîìåðíî ðàñïðåäåëåííîé â îáëàñòè1). Ðåàëèçóåì2). Åñëè, òîèè., èíà÷å ïîâòîðÿåì ï. è ò.ä.A = {1 < u < N + 1; 0 < v < 1/N } åäèíè÷íîé ïëîùàäè, ïðè÷åì ñóììàðíàÿ âåðîÿòíîñòüïîïàäàíèÿ ýòîé òî÷êè â ïîäñòîëáöû Fm è Em \ Fm , ñîîòâåòñòâóþùèå íîìåðó i, ðàâíà pi .Òàêîé ðîçûãðûø ýêâèâàëåíòåí ìîäåëèðîâàíèþ òî÷êè (ξ, η), ðàâíîìåðíî ðàñïðåäåëåííîé â "ïîäãðàôèêå"G ôóíêöèè g(u) = f (u), ò.ê.
Ḡ = 1 è ïëîùàäü ñòîëáöà äèàãðàììû(1.109) Ii = {i ≤ u < i + 1; 0 < v < pi }, ñîîòâåòñòâóþùåãî i-ìó íîìåðó, ðàâíà SIi = pi(ñì. ñîîòíîøåíèå (1.110)). Â ñèëó óòâåðæäåíèÿ 1.14, êîìïîíåíòà ξ ðàñïðåäåëåíà ñîãëàñíî ïëîòíîñòè (1.109). Òîãäà èç ñîîòíîøåíèÿ m = [ξ] ñëåäóåò, ÷òî â ìåòîäå Óîëêåðàìîäåëèðóåòñÿ òðåáóåìîå äèñêðåòíîå ðàñïðåäåëåíèå.1.8.3. Îñíîâíûå ìåòîäû ìîäåëèðîâàíèÿ ïîëèíîìèàëüíûõ ïëîòíîñòåé.
Âïîäðàçä. 1.4.1 áûëà ðàññìîòðåíà ñëó÷àéíàÿ âåëè÷èíà ξ , èìåþùàÿ ïîëèíîìèàëüíîå ðàñïðåäåëåíèå ñ ïëîòíîñòüþf (u) =AXai u i ,A = N ∨ +∞0 < u < 1,(1.111)i=0(ñì. òàêæå ôîðìóëó (1.50)). Äëÿ ðåàëèçàöèè âûáîðî÷íîãî çíà÷åíèÿ ñëó÷àéíîé âåëè÷èíû ξ èñïîëüçóþò ðàçëè÷íûå àëãîðèòìû â çàâèñèìîñòè îò âèäà êîýôôèöèåíòîâ {ai }.Òàê, ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ (àëãîðèòì 1.14) çàâåäîìî ðåàëèçóåì äëÿAp = 0 (ïðè ýòîì f (u) ≡ 1, 0 < u < 1 è ξ = α), äëÿ A = 1 (ïðè ýòîì ξ = (−a0 +a20 + 2a1 α)/a1 ), à òàêæå äëÿ ñëó÷àÿ ai = (i + 1) è aj = 0 ïðè j 6= i; ïðè ýòîì√f (u) = (i + 1)ui è ξ = α1/(i+1) = i+1 α.(1.112) îáùåì ñëó÷àå (ïðè A > 1 è ïðè íàëè÷èè äîñòàòî÷íî áîëüøîãî ÷èñëà íåíóëåâûõ êîýôôèöèåíòîâPai ) ïîïûòêà ïðèìåíèòü ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ ïðèâîäèòi+1/(i + 1) = α, êîòîðîå, êàê ïðàâèëî, íåðàçðåøèìî îòíîñèòåëüíîê óðàâíåíèþ Ai=0 ai ξξ , è íóæíî èñïîëüçîâàòü ñïåöèàëüíûå àëãîðèòìû ìîäåëèðîâàíèÿ (ìåòîä ñóïåðïîçèöèè,ìåòîä èñêëþ÷åíèÿ è äð.).Äëÿ ñëó÷àÿ ai ≥ 0, â ÷àñòíîñòè, óäàåòñÿ ïðåäñòàâèòü ïëîòíîñòü (1.111) â âèäåf (u) =AXpi fi (u); pi = ai /(i + 1);fi (u) = (i + 1)ui ,(1.113)i=0è ïîñòðîèòü ñëåäóþùèé ìåòîä ñóïåðïîçèöèè (ñì.
àëãîðèòì 1.20).Àëãîðèòì 1.32.α1{ai /(i + 1)}1.1mξfm (u) =√mm+1α2(m + 1)u(1.112) ξ = ñëó÷àå íàëè÷èÿ îòðèöàòåëüíûõ ÷èñåë ñðåäè êîýôôèöèåíòîâ {ai } âåëè÷èíû {pi }èç ñîîòíîøåíèÿ (1.113) íåëüçÿ ñ÷èòàòü âåðîÿòíîñòÿìè,òàê êàê îíè íå ÿâëÿþòñÿ ïîPAëîæèòåëüíûìè ÷èñëàìè (õîòÿ ñîîòíîøåíèåi=0 pi = 1 âûïîëíåíî â ëþáîì ñëó÷àå).Ïîëîæèì A = N < ∞. Äëÿ ôóíêöèè (1.111) ìîæíî ïîñòðîèòü ìàæîðàíòó1). Ðåàëèçîâàâ âûáîðî÷íîå çíà÷åíèå ñòàíäàðòíîãî ñëó÷àéíîãî÷èñëà, ñîãëàñíî âåðîÿòíîñòÿì, èñïîëüçóÿ àëãîðèòì èëè åãî ìîäèôèêàöèè, âûáèðàåì íîìåð .2). Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîé âåëè÷èíû ñîãëàñíî ïëîòíîñòè.ïî ôîðìóëå âèäà:f (u) ≤ g1 (u) =NXia+i u ,(1.114)i=0+ãäå a+i = ai ïðè ai ≥ 0 è ai = 0 ïðè ai < 0. Òîãäà ìîæíî ïðåäëîæèòü ñëåäóþùèé ìåòîäèñêëþ÷åíèÿ (ñì.
àëãîðèòì 1.24).1). Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîé âåëè÷èíû ξ1, ðàñïðåäåëåííîé ñ ïëîòíîñòüþÀëãîðèòì 1.33.f˜1 (u) =NX+p+i fi (u), pi =i=0a+a+i=,R 1iPN(i + 1) j=0 (a+/(j+1))(i + 1) 0 g1 (w) dwjñîãëàñíî àëãîðèòìó 1.32 (ïðè ýòîì èñïîëüçóþòñÿ äâà ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñëàα1 è α2 ).2). Ðåàëèçóåì òàêæå çíà÷åíèå η = α3g1(ξ1).3). Ïðîâåðÿåì íåðàâåíñòâî η < f (ξ1). Åñëè îíî âûïîëíåíî, òî ïîëàãàåì, ÷òî âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîé âåëè÷èíû ξ ðàâíî ξ = ξ1, èíà÷å ïîâòîðÿåì ïóíêòû 1 è 2 èò.ä.Òðóäîåìêîñòü ýòîãî àëãîðèòìà (ñðåäíåå ÷èñëî ïîâòîðåíèé ïóíêòîâ 1 è 2 äî âûïîëíåR1P+íèÿ íåðàâåíñòâà η < f (ξ1 )) ïðîïîðöèîíàëüíà âåëè÷èíå s1 = 0 g1 (w) dw = Nj=0 (aj /(j +1)) (ñì.
ñîîòíîøåíèå (1.92)).Âûáîð ìàæîðàíòûâèäà (1.114) íåîäíîçíà÷åí. Ìîæíî, íàïðèìåð, ðàññìîòðåòü ôóíêPi|a|uè èñïîëüçîâàòü äëÿ íåå àëãîðèòì 1.33 ñ çàìåíîé ξ1 íà ξ2 . Òàêîéöèþ g2 (u) = Nii=0âûáîð ìàæîðàíòû çàâåäîìî õóæå, ÷åì (1.114), ò. ê. g2 (u) > g1 (u) èZs2 =1g2 (w) dw =0NX(|aj |/(j + 1)) > s1 .j=0Îäíàêî íåñëîæíî ïîñòðîèòü ïðèìåð, â êîòîðîì ìàæîðàíòà (1.114) íå ÿâëÿåòñÿ ëó÷øåé.Ïðèìåð 1.16. Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ ñ êâàäðàòè÷íîé ïëîòíîñòüþ ðàñïðåäåëåíèÿ f (u) = 6u − 6u2 , 0 < u < 1.
 ýòîì ñëó÷àå g1 (u) = 6u è òðóäîåìêîñòü ñîîòR1âåòñòâóþùåãî àëãîðèòìà 1.33 ïðîïîðöèîíàëüíà âåëè÷èíå s1 = 0 6w dw = 3. Ñ äðóãîéñòîðîíû, äëÿ ïðîñòåéøåãî ìåòîäà Íåéìàíà (àëãîðèòì 1.25) ñ ïîñòîÿííîé ìàæîðàíòîég3 (u) ≡ max f (u) = f (1/2) = 3/2u∈(0,1)èìååì s3 = 3/2. Ýòà âåëè÷èíà â äâà ðàçà ìåíüøå, ÷åì s1 .1.8.4. Èñïîëüçîâàíèå ïîðÿäêîâûõ ñòàòèñòèê.Ïóñòü èìååòñÿ íàáîðξ1 , ξ2 , . . . , ξn èç n íåçàâèñèìûõ îäèíàêîâî(n) (n)ðàñïðåäåëåííûõ ñëó÷àéíûõ âåëè÷èí, à ξ1 , ξ2 , . . . , ξn(n) òå æå ñëó÷àéíûå âåëè÷èíû,ðàñïîëîæåííûå â ïîðÿäêå âîçðàñòàíèÿ.
Ñëó÷àéíàÿ âåëè÷èíà ξr(n) íàçûâàåòñÿ r-é ïîðÿäêîâîé ñòàòèñòèêîé.(n)(n)Îïðåäåëåíèå 1.4. ÷àñòíîñòè, ξ1= min{ξ1 , . . . , ξn } è ξn = max{ξ1 , . . . , ξn }. Ñïðàâåäëèâî ñëåäóþùååÓòâåðæäåíèå 1.16. Ïóñòü ñëó÷àéíûå âåëè÷èíû ξ1 , ξ2 , . . . , ξn èìåþò ôóíêöèþ ðàñïðåäåëåíèÿ F (u) è ïëîòíîñòü f (u). Òîãäà r-ÿ ïîðÿäêîâàÿ ñòàòèñòèêà ξr(n) èìååòïëîòíîñòü ðàñïðåäåëåíèÿr−1 r−1fr(n) (u) = n Cn−1F (u) (1 − F (u))n−r f (u),ãäå Cnk = n!/(k!(n − k)!) ÷èñëî ñî÷åòàíèé èç n ýëåìåíòîâ ïî k.(1.115)(n)Äëÿ ïîëó÷åíèÿ âûáîðî÷íûõ çíà÷åíèé ñëó÷àéíîé âåëè÷èíû ξr ìîæíî èñïîëüçîâàòü ñëåäóþùóþ ïðîöåäóðó.
Ïðåäïîëàãàåì, ÷òî èìååòñÿ ýôôåêòèâíûé àëãîðèòì âûáîðàìàêñèìàëüíîãî ýëåìåíòà AM è íîìåðà M ñîîòâåòñòâóþùåé ÿ÷åéêè ìàññèâà (a1 , . . . , ar ),ñîñòîÿùåãî èç r êîìïîíåíò. Çäåñü ãîäèòñÿ, â ÷àñòíîñòè, òàêîé àëãîðèòì: ïîëàãàåì ñíà÷àëà AM := a1 , M := 1 è ïîñëåäîâàòåëüíî äëÿ s = 2, . .
. , r ïðîâåðÿåì íåðàâåíñòâîas > AM ; åñëè îíî âûïîëíåíî, òî äåëàåì ïåðåïðèñâàèâàíèÿ AM := as , M := s.1). Ðåàëèçóåì r âûáîðî÷íûõ çíà÷åíèé Ξ = (ξ1, . . . , ξr ) ñëó÷àéíîéâåëè÷èíû ξ ñîãëàñíî ôóíêöèè ðàñïðåäåëåíèÿ F (u) (èëè ïëîòíîñòè ðàñïðåäåëåíèÿ f (u)),ïàðàëëåëüíîâûáèðàÿ ìàêñèìàëüíûé ýëåìåíò AM ïîëó÷àåìîãî ìàññèâà Ξ. Ïîëàãàåì(n)ξr := AM .2). Äëÿ s = r + 1, .
. . , n ðåàëèçóåì âûáîðî÷íûå çíà÷åíèÿ ξs. Åñëè ξs < AM , òîçàìåíÿåì M -þ êîìïîíåíòó ìàññèâà Ξ: ξM := ξs è íàõîäèì(n)ìàêñèìàëüíûé ýëåìåíòAM è íîìåð M äëÿ ïðåîáðàçîâàííîãî ìàññèâà Ξ. Ïîëàãàåì ξr := AM .Àëãîðèòì 1.34. ðÿäå ÷àñòíûõ ñëó÷àåâ àëãîðèòì 1.34 äîïóñêàåò ýôôåêòèâíûå ìîäèôèêàöèè. Íàïðèìåð, ïðè r = n íå íóæåí ïóíêò 2, à ïðè r = 1 òðåáóåòñÿ èñêàòü ìèíèìóì èç ïîëíîãîíàáîðà âûáîðî÷íûõ çíà÷åíèé (ξ1 , . . . , ξn ).(n) ÷àñòíîì ñëó÷àå, êîãäà ξi = αi , ïëîòíîñòü ïîðÿäêîâîé ñòàòèñòèêè αr íåçàâèñèìîéâûáîðêè îáúåìà n èç ñîâîêóïíîñòè ñ ðàâíîìåðíûì ðàñïðåäåëåíèåì â èíòåðâàëå (0, 1)èìååò âèär−1 r−1fr(n) (u) = n Cn−1u (1 − u)n−r , u ∈ (0, 1),(1.116)òàê êàê F (u) = u, f (u) ≡ 1 (ñì. ñîîòíîøåíèÿ (1.1), (1.2)). Àëãîðèòì 1.34 äëÿ ýòîãî ñëó÷àÿ äàåò ñïåöèàëüíûé ìåòîä ìîäåëèðîâàíèÿ ïîëèíîìèàëüíîé ïëîòíîñòè (1.111),äîïóñêàþùåé ïðåäñòàâëåíèå (1.116).Çàìåòèì, ÷òî ïëîòíîñòü f (u) = (i + 1)ui , 0 < u < 1 èç (1.112) ÿâëÿåòñÿ ÷àñòíûìñëó÷àåì ôîðìóëû (1.116) äëÿ n = r = i +√ 1.
Òàêèì îáðàçîì, ïîìèìî ôîðìóëû ìåòîäài+1α (ñì. ñîîòíîøåíèå (1.112)) ìîæíî ðàññìîòîáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ ξ =ðåòü ôîðìóëó, ïîðîæäàåìóþ àëãîðèòìîì 1.34: ξ = max{α1 , . . . , αi+1 }. Ñëåäóåò, îäíàêî,îòìåòèòü, ÷òî äëÿ ñîâðåìåííûõ êîìïüþòåðîâ ñ ìàòåìàòè÷åñêèìè ñîïðîöåññîðàìè (äëÿêîòîðûõ, â ÷àñòíîñòè, âû÷èñëåíèå êîðíÿ (i + 1)-é ñòåïåíè â ôîðìóëå (1.112), ïðîèñõîäèò äîñòàòî÷íî áûñòðî) è äëÿ ñîâðåìåííûõ ÿçûêîâ ïðîãðàììèðîâàíèÿ (òèïà ÑÈ++)ôîðìóëà (1.112) ÿâëÿåòñÿ áîëåå ýôôåêòèâíîé (ýêîíîìè÷íîé).1.8.5.Ìîäåëèðîâàíèåðàñïðåäåëåíèéñïëîòíîñòÿìè,ÿâëÿþùèìèñÿB -ñïëàéíàìè.
 òåîðèè ïðèáëèæåíèÿ ôóíêöèé øèðîêî ïðèìåíÿåòñÿ ñëåäóþùåå ïîíÿòèå.Îïðåäåëåíèå 1.5. B -ñïëàéíîì ïîðÿäêà r íàçûâàåòñÿ (r + 1)-é ÷ëåí β (r) (u) ðåêóððåíòíîé ïîñëåäîâàòåëüíîñòè β (i+1)(u) = β (0) ∗ β (i)(u), ãäå1 ïðè − 1/2 ≤ u < 1/2;(0)β (u) =(1.117)0 èíà÷å,ãäå çíàê ” ∗ ” îáîçíà÷àåò ñâåðòêóZ+∞g1 ∗ g2 (u) =g1 (w) g2 (u − w) dw.−∞Íåñëîæíî ïîíÿòü, ÷òî B -ñïëàéí ïðåäñòàâëÿþò ñîáîé êóñî÷íî-ïîëèíîìèàëüíûå ôóíêöèè r-é ñòåïåíè, ïðè÷åì äëÿ íå÷åòíûõ r ñîîòâåòñòâóþùèå óçëû ÿâëÿþòñÿ öåëûìè òî÷êàìè, ñèììåòðè÷íî ðàñïîëîæåííûìè îêîëî íóëÿ. Íàèáîëåå ÷àñòî èñïîëüçóþòñÿ ñïëàéíûïåðâîãî ïîðÿäêà (èëè") 1 + u äëÿ − 1 ≤ u ≤ 0,(1)1 − u äëÿ 0 ≤ u ≤ 1,β (u) =0 èíà÷åè òðåòüåãî ïîðÿäêà0ïðè u > 2 ;3(2−u)/6ïðè 1 ≤ u ≤ 2;β (3) (u) =231 + 3 (1 − u) + 3 (1 − u) − 3 (1 − u) /6 ïðè 0 ≤ u ≤ 1; (3)β (−u)ïðè u ≤ 0."ôóíêöèÿ-êðûøêàÁóäó÷è âêëþ÷åííûìè â êîíñòðóêöèè, èñïîëüçóåìûå äëÿ ïðèáëèæåíèÿ ôóíêöèé, B ñïëàéíû ïîçâîëÿþò ïîëó÷èòü õîðîøèå ñâîéñòâà àïïðîêñèìàöèè è îñîáåííî óñòîé÷èâîñòè ñîîòâåòñòâóþùåãî ïðèáëèæåíèÿ.
Îäíàêî åñòü åùå îäíî çàìå÷àòåëüíîå ñâîéñòâîôóíêöèé β (r) (u), ïîçâîëÿþùåå èñïîëüçîâàòü èõ â àëãîðèòìàõ ìåòîäà Ìîíòå-Êàðëî.Óòâåðæäåíèå 1.17.β (r) (u)Ôóíêöèÿíîé âåëè÷èíûÿâëÿåòñÿ ïëîòíîñòüþ ðàñïðåäåëåíèÿ ñëó÷àé-ξ (r) = α1 + . . . + αr + αr+1 − (r + 1)/2,ãäå αi íåçàâèñèìûå ñòàíäàðòíûå ñëó÷àéíûå âåëè÷èíû, ðàâíîìåðíî ðàñïðåäåëåííûå â(0, 1).Äëÿ íà÷àëà íàïîìíèì ñëåäóþùèé âåðîÿòíîñòíûé ôàêò. Åñëèèìåþòñÿ äâå íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èíû γ1 è γ2 ñ ïëîòíîñòÿìè ðàñïðåäåëåíèÿf1 (u) è f2 (u) ñîîòâåòñòâåííî, òî ñëó÷àéíàÿ âåëè÷èíà ζ = γ1 + γ2 èìååò ïëîòíîñòü ðàñïðåäåëåíèÿ fζ (u) = f1 ∗ f2 (u).Òåïåðü äîêàæåì óòâåðæäåíèå 1.17 ïî èíäóêöèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
