1626435387-cbed9341b165fae9f16c4a05686b9115 (844203), страница 14
Текст из файла (страница 14)
Èìååòñÿ åùå,îäíàêî, óòâåðæäåíèå 10.1, èç êîòîðîãî ñëåäóåò, ÷òî åñëè ïîãðóçèòü ¾ïîäãðàôèê¿ G â îáëàñòü G(1) â ñèñòåìå êîîðäèíàò (u, v) (ò. å. G ⊆ G(1) ) è(1)ðåàëèçîâàòü âûáîðî÷íîå çíà÷åíèå (ξ 0 , η0 ) ñëó÷àéíîãî âåêòîðà (ξ (1) , η),(1)ðàâíîìåðíî ðàñïðåäåëåííîãî â G(1) , òî ïðè óñëîâèè (ξ 0 , η0 ) ∈ G ïàðà(1)(ξ 0 , η0 ) ðàâíîìåðíî ðàñïðåäåëåíà â G. Òîãäà, ñîãëàñíî óòâåðæäåíèþ(1)16.1, âåêòîð ξ 0 èìååò òðåáóåìîå ðàñïðåäåëåíèå ñ ïëîòíîñòüþ (16.2).Êîíñòðóèðîâàíèå îáëàñòè G(1) ñâÿçàíî ñ ðàñøèðåíèåì ¾ïîäãðàôèêà¿ G â íàïðàâëåíèè îñè v . Äðóãèìè ñëîâàìè, ðàññìàòðèâàåòñÿ ìàæîðàíòà g (1) (u) ôóíêöèè g(u) òàêàÿ, ÷òî g(u) ≤ g (1) (u) ïðè u ∈ U .
Ïåðâîå òðåáîâàíèå ê ìàæîðàíòå g (1) (u) òàêîâî, ÷òî äëÿ ïëîòíîñòè (16.3)(1)èìååòñÿ ýôôåêòèâíûé àëãîðèòì (ôîðìóëà) âèäà ξ 0 = ψ (1) (ᾱ1 ) äëÿ(1)ðåàëèçàöèè âûáîðî÷íîãî çíà÷åíèÿ ξ 0 ñëó÷àéíîãî âåêòîðà ξ (1) ñîãëàñíî îäíîìó èç âàðèàíòîâ àëãîðèòìà 14.1 (çäåñü ᾱ1 ñîîòâåòñòâóþùèéíàáîð ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë).
Ýòî äàåò ìàæîðàíòíûé ìåòîäèñêëþ÷åíèÿ.ÀËÃÎÐÈÒÌ 16.2 (ñì., íàïðèìåð, [1]). 1. Ðåàëèçóåì âûáîðî÷íîå çíà(1)(1)÷åíèå ξ0 ñîãëàñíî ïëîòíîñòè (16.3): ξ0 = ψ (1) (ᾱ1 ), à òàêæå çíà÷å(1)íèå η0 = α2 g (1) (ξ0 ).2. Åñëè(1)η0 < g(ξ 0 ),(16.4)òî â êà÷åñòâå èñêîìîãî âûáîðî÷íîãî çíà÷åíèÿ ξ0 âåêòîðà ξ ïðèíèìàåì(1)ξ 0 = ξ 0 .  ñëó÷àå, êîãäà íåðàâåíñòâî (16.4) íå âûïîëíåíî, ïîâòîðÿåìï. 1 äàííîãî àëãîðèòìà è ò. ä.(1)Ñîãëàñíî óòâåðæäåíèþ 16.2, òî÷êà (ξ 0 , η0 ), ðåàëèçóåìàÿ â ï.
1 àëãîðèòìà 16.2, ðàâíîìåðíî ðàñïðåäåëåíà â îáëàñòè G(1) . Åñëè âûïîëíåíî(1)óñëîâèå (16.4), òî ïàðà (ξ 0 , η0 ) ïðèíàäëåæèò îáëàñòè G è, ñîãëàñíîóòâåðæäåíèþ 10.1, ðàâíîìåðíî ðàñïðåäåëåíà â ýòîé îáëàñòè, è òîãäà,(1)ñîãëàñíî óòâåðæäåíèþ 16.1, âåëè÷èíó ξ 0 ìîæíî ïðèíÿòü â êà÷åñòâåèñêîìîãî âûáîðî÷íîãî çíà÷åíèÿ ξ 0 .76Ñîãëàñíî ôîðìóëå (16.1) è óòâåðæäåíèþ 10.1, òðóäîåìêîñòü s̃ àëãîðèòìà 16.2 ïðîïîðöèîíàëüíà âåëè÷èíås=1P (ξ(1), η) ∈ G=Ḡ(1).Ḡ(16.5)Òàêèì îáðàçîì, ìàæîðàíòó g (1) (u) ôóíêöèè g(u) ñëåäóåò ïîäáèðàòü òàê,÷òîáû îáúåìû Ḡ(1) è Ḡ áûëè áëèçêè; ýòî âûïîëíåíî ïðè g (1) (u) ≈ g(u).Êàê óêàçàíî âûøå, ìàæîðàíòíûé ìåòîä èñêëþ÷åíèÿ èñïîëüçóåòñÿíàìíîãî ÷àùå äðóãèõ ìåòîäîâ îòáîðà, ïîýòîìó â ëèòåðàòóðå ÷àñòî àëãîðèòì 16.2 íàçûâàåòñÿ ïðîñòî ìåòîäîì èñêëþ÷åíèÿ.ÏÐÈÌÅÐ 16.1 (1.5 áàëëà).
Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ , èìåþùóþ ïëîòíîñòü ðàñïðåäåëåíèÿ f (u), ïðîïîðöèîíàëüíóþ ôóíêöèèsin ue−u , u > 0.(16.6)g(u) = 1 +2Èíòåãðèðóÿ ïî ÷àñòÿì, ïîëó÷àåìZ+∞g(u) du =−u−e0ò. å.4f (u) =5(cos u + sin u) e−u−4sin u1+2e−u ,+∞5= ,4(16.7)0u > 0.Èç ñîîòíîøåíèÿ (16.7) ñëåäóåò, ÷òî ôóíêöèÿ f (u) íå ÿâëÿåòñÿ ïëîòíîñòüþ ýëåìåíòàðíîãî ðàñïðåäåëåíèÿ, ò.
å. óðàâíåíèå ìåòîäà îáðàòíîéRξôóíêöèè ðàñïðåäåëåíèÿ 0 0 f (u) du = α0 (ñì. ñîîòíîøåíèå (13.8)) ïðèâîäèò ê óðàâíåíèþ (4 + cos ξ0 + sin ξ0 )e−ξ0 = 5α00 , α00 = 1 − α0 , êîòîðîåíåðàçðåøèìî îòíîñèòåëüíî ξ0 . ñèëó òîãî ÷òî | sin u| ≤ 1, â êà÷åñòâå ìàæîðàíòû ôóíêöèè (16.6)ìîæíî âçÿòü ôóíêöèþ g (1) (u) = 3 e−u /2. Ëåãêî âû÷èñëèòü èíòåãðàëR +∞ (1)g (u) du = 3/2. Ñëåäîâàòåëüíî, f (1) (u) = e−u , u > 0. Ýòî ÷àñòíûé0ñëó÷àé òàáëè÷íîé (ýêñïîíåíöèàëüíîé) ïëîòíîñòè (13.11) äëÿ λ = 1 ñì.ïðèåð 13.1 è çàìå÷àíèå 13.3. Îòñþäà ïîëó÷àåì ñëåäóþùèé àëãîðèòììåòîäà èñêëþ÷åíèÿ.1. Ñîãëàñíî òàáëè÷íîé ôîðìóëå (13.13) ïîëó÷àåì âûáîðî÷íîå çíà(1)÷åíèå ξ0 = − ln α1 .
Ðåàëèçóåì òàêæå âåëè÷èíó η0 = α2 g (1) (ξ1 ) =(1)3 α2 exp(−ξ0 )/2.77(1)(1)2. Ïðîâåðÿåì íåðàâåíñòâî η < g(ξ0 ) èëè 3 α2 < 2 + sin ξ0 . Åñëèýòî íåðàâåíñòâî âûïîëíåíî, òî ïîëàãàåì, ÷òî âûáîðî÷íîå çíà÷åíèå ξ0(1)ñëó÷àéíîé âåëè÷èíû ξ ðàâíî ξ0 = ξ0 , èíà÷å ïîâòîðÿåì ï. 1 è ò. ä.Òðóäîåìêîñòü ýòîãî àëãîðèòìà ïðîïîðöèîíàëüíà âåëè÷èíås = 3/2 : 5/4 = 1.2 (ñì. ñîîòíîøåíèå (16.5)). Îïèñàíèå ïðèìåðà 16.1çàêîí÷åíî.16.3. Ìîäåëèðîâàíèå ðàñïðåäåëåíèÿ ñ ïîëèíîìèàëüíîé ïëîòíîñòüþ.
Ïðèâåäåì åùå îäèí âàæíûéÏÐÈÌÅÐ 16.2 (1 áàëë). Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ , èìåþùóþ ïîëèíîìèàëüíóþ ïëîòíîñòü ðàñïðåäåëåíèÿf (u) =NXci ui , 0 < u < 1(16.8)i=0(ñì. òàêæå ïîäðàçä. 13.4 è ôîðìóëó (13.10)). Äëÿ ðåàëèçàöèè âûáîðî÷íîãî çíà÷åíèÿ ξ0 ñëó÷àéíîé âåëè÷èíû ξ èñïîëüçóþò ðàçëè÷íûå àëãîðèòìû â çàâèñèìîñòè îò âèäà êîýôôèöèåíòîâ {ci }.
Òàê, ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ (àëãîðèòì 13.1) çàâåäîìî ðåàëèçóåì äëÿN = 0 (ïðè ýòîìp f (u) ≡ 1, 0 < u < 1 è ξ0 = α0 ), äëÿ N = 1 (ïðè ýòîìξ0 = (−c0 + c20 + 2c1 α0 )/c1 ), à òàêæå äëÿ ñëó÷àÿ ci = (i + 1) è cj = 0ïðè j 6= i (ñì. ïðèìåð 13.2); ïðè ýòîì√1/(i+1)f (u) = (i + 1)ui è ξ0 = α0= i+1 α0 .(16.9) îáùåì ñëó÷àå (ïðè N > 1 è ïðè íàëè÷èè äîñòàòî÷íî áîëüøîãî ÷èñëà íåíóëåâûõ êîýôôèöèåíòîâ ci ) ïîïûòêà ïðèìåíèòü ìåòîä îáðàòíîéPNôóíêöèè ðàñïðåäåëåíèÿ ïðèâîäèò ê óðàâíåíèþ i=0 ci ξ0i+1 /(i+1) = α0 ,êîòîðîå, êàê ïðàâèëî, íåðàçðåøèìî îòíîñèòåëüíî ξ0 è íóæíî èñïîëüçîâàòü ñïåöèàëüíûå àëãîðèòìû ìîäåëèðîâàíèÿ (ìåòîä ñóïåðïîçèöèè, ìåòîä èñêëþ÷åíèÿ è äð.).Äëÿ ñëó÷àÿ ci ≥ 0, â ÷àñòíîñòè, óäàåòñÿ ïðåäñòàâèòü ïëîòíîñòü (16.8)â âèäåf (u) =NXi=0pi fi (u); pi =ci; fi (u) = (i + 1)uii+1(16.10)è ïîñòðîèòü ñëåäóþùèé ìåòîä ñóïåðïîçèöèè.1.
Ðåàëèçóÿ âûáîðî÷íîå çíà÷åíèå α1 ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëàα, ñîãëàñíî âåðîÿòíîñòÿì {ci /(i + 1)}, èñïîëüçóÿ àëãîðèòì 11.1 èëèåãî ìîäèôèêàöèè, âûáèðàåì íîìåð m.782. Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ξ0 ñëó÷àéíîé âåëè÷èíû ξ ñîãëàñíî√ïëîòíîñòè fm (u) = (m + 1)um ïî ôîðìóëå âèäà (16.9): ξ0 = m+1 α2 . ñëó÷àå íàëè÷èÿ îòðèöàòåëüíûõ ÷èñåë ñðåäè êîýôôèöèåíòîâ {ci }âåëè÷èíû {pi } èç ñîîòíîøåíèÿ (16.10) íåëüçÿ ñ÷èòàòü âåðîÿòíîñòÿìè,òàê êàê îíè íå ÿâëÿþòñÿ ïîëîæèòåëüíûìè ÷èñëàìè (õîòÿ ñîîòíîøåíèåPNi=0 pi = 1 âûïîëíåíî â ëþáîì ñëó÷àå). Äëÿ ôóíêöèè (16.8) ìîæíîïîñòðîèòü ìàæîðàíòóf (u) ≤ g (1) (u) =NXic+i u ,(16.11)i=0+ãäå c+i = ci ïðè ci ≥ 0 è ci = 0 ïðè ci < 0. Òîãäà ìîæíî ïðåäëîæèòüñëåäóþùèé ìåòîä èñêëþ÷åíèÿ (ñì. àëãîðèòì 16.2).(1)1.
Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîé âåëè÷èíû ξ0 , ðàñïðåPN +(1)äåëåííîé ñîãëàñíî ïëîòíîñòè f (u) = i=0 pi fi (u), ãäåp+i =c+c+i=,R1iPN(i + 1) j=0 (c+(i + 1) 0 g (1) (w) dwj /(j + 1))ñîãëàñíî ñôîðìóëèðîâàííîìó âûøå àëãîðèòìó ìåòîäà ñóïåðïîçèöèè(ïðè ýòîì èñïîëüçóþòñÿ äâà ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñëà α1 è α2 ).(1)2. Ðåàëèçóåì òàêæå çíà÷åíèå η0 = α3 g (1) (ξ0 ).(1)3. Ïðîâåðÿåì íåðàâåíñòâî η0 < f (ξ0 ). Åñëè îíî âûïîëíåíî, òî ïîëàãàåì, ÷òî âûáîðî÷íîå çíà÷åíèå ξ0 ñëó÷àéíîé âåëè÷èíû ξ ðàâíî(1)ξ0 = ξ0 , èíà÷å ïîâòîðÿåì ïï. 1, 2 è ò.
ä.Òðóäîåìêîñòü ýòîãî àëãîðèòìà (ñðåäíåå ÷èñëî ïîâòîðåíèé(1)ïï. 1 è 2 äî âûïîëíåíèÿ íåðàâåíñòâà η0 < f (ξ0 )) ïðîïîðöèîíàëüíà âåRP1Nëè÷èíå s(1) = 0 g (1) (w) dw = i=0 (c+i /(i + 1)) (ñì. ñîîòíîøåíèå (16.5)).Âûáîð ìàæîðàíòû âèäà (16.11) íåîäíîçíà÷åí.
Ìîæíî, íàïðèìåð,PNðàññìîòðåòü ôóíêöèþ g (2) (u) = i=0 |ci |ui è èñïîëüçîâàòü äëÿ íåå ñôîðìóëèðîâàííûé àëãîðèòì ìåòîäà èñêëþ÷åíèÿ ñ çàìåíîé ξ (1) íà ξ (2) . Òàêîé âûáîð ìàæîðàíòû çàâåäîìî õóæå, ÷åì (16.11), ò. ê. g (2) (u) > g (1) (u)R1PNè s(2) = 0 g (2) (w) dw = i=0 (|ci |/(i + 1)) > s(1) .Îäíàêî íåñëîæíî ïîñòðîèòü ïðèìåð, â êîòîðîì ìàæîðàíòà (16.11)íå ÿâëÿåòñÿ ëó÷øåé. Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ ñ êâàäðàòè÷íîéïëîòíîñòüþ ðàñïðåäåëåíèÿ f (u) = 6u − 6u2 , 0 < u < 1.
 ýòîì ñëó÷àåg (1) (u) = 6u è òðóäîåìêîñòü ñîîòâåòñòâóþùåãî àëãîðèòìà ìåòîäà èñR1êëþ÷åíèÿ ïðîïîðöèîíàëüíà âåëè÷èíå s(1) = 0 6w dw = 3. Ñ äðóãîé79ñòîðîíû, äëÿ ìåòîäà èñêëþ÷åíèÿ ñ ïîñòîÿííîé ìàæîðàíòîé 13g (3) (u) ≡ max f (u) = f=22u∈(0,1)èìååì s(3) = 3/2. Ýòà âåëè÷èíà â äâà ðàçà ìåíüøå, ÷åì s(1) .16.4. Òåõíîëîãèÿ ¾ïîð÷è¿ ìîäåëèðóåìîé ïëîòíîñòè. Ïðè ïîñòðîåíèè ïðèìåðà 16.1 èñïîëüçîâàëàñü ñëåäóþùàÿÒÅÕÍÎËÎÃÈß 16.1. Êîíñòðóèðóåì ñíà÷àëà ïëîòíîñòü f (1) (u)(u ∈ U ⊆ Rd ) âåêòîðà ξ (1) , äëÿ êîòîðîãî ñóùåñòâóåò ýôôåêòèâíûé(1)àëãîðèòì (ôîðìóëà) ÷èñëåííîé ðåàëèçàöèè: ξ0 = ψ (1) (ᾱ1 ) (ýòîò àëãîðèòì èñïîëüçóåòñÿ çàòåì â ïåðâîì ïóíêòå àëãîðèòìà 16.2). Äëÿïîñòðîåíèÿ ôóíêöèè f (1) (u) ìîæíî èñïîëüçîâàòü âåñü àðñåíàë êîíñòðóèðîâàíèÿ ìîäåëèðóåìûõ ïëîòíîñòåé (òåõíîëîãèè 13.1, 14.1, 15.1è äð.).
Äàëåå ïðåîáðàçóåì ïëîòíîñòü f (1) (u) òàêèì îáðàçîì, ÷òîáûîíà ïðåâðàòèëàñü â ôóíêöèþ g(u), ïðîïîðöèîíàëüíóþ ¾íåìîäåëèðóåìîé¿ ïëîòíîñòè f (u) (ïî ñóòè ìû ¾ïîðòèì¿ ìîäåëèðóåìóþ ïëîòíîñòü f (1) (u)). Îäíèì èç ïðîñòåéøèõ ïðåîáðàçîâàíèé ÿâëÿåòñÿ óìíîæåíèå ïëîòíîñòè f (1) (u) íà ìàëî ìåíÿþùóþñÿ ôóíêöèþ Y (u):g(u) = f (1) (u) Y (u), u ∈ U ; ãäå 0 < A ≤ Y (u) ≤ B(16.12)è (B − A) áëèçêàÿ ê íóëþ ïîëîæèòåëüíàÿ âåëè÷èíà.  êà÷åñòâå ìàæîðàíòû òîãäà ìîæíî âçÿòü g (1) (u) = B f (1) (u). Ïëîòíîñòü, ïðîïîðöèîíàëüíàÿ ýòîé ôóíêöèè, î÷åâèäíî, ðàâíà f (1) (u).
Èíòåãðèðóÿ íåîòðèöàòåëüíûå ôóíêöèè g (1) (u) è g(u) ïî îáëàñòè U ñ ó÷åòîì ñîîòíîøåíèÿ Af (1) (u) = Ag (1) (u)/B ≤ g(u), ïîëó÷àåì A Ḡ(1) /B ≤ Ḡ, è òîãäàs=BḠ(1)≤ ,AḠ(16.13)ò. å. ïðè A ≈ B âåëè÷èíà s èç ñîîòíîøåíèÿ (16.5) äëÿ àëãîðèòìà 16.2íåâåëèêà (áëèçêà ê åäèíèöå).Äëÿ óäîáñòâà âûêëàäîê â ðàâåíñòâå (16.12) âìåñòî ïëîòíîñòè f (1) (u)ìîæíî ðàññìàòðèâàòü ïðîïîðöèîíàëüíóþ åé ôóíêöèþ g̃ (1) (u) (îïóñêàÿ,ê ïðèìåðó, íîðìèðóþùóþ êîíñòàíòó).ÇÀÌÅ×ÀÍÈÅ 16.1.
Äëÿ ïðåäëàãàåìîé òåõíîëîãèè 16.1 íåðàâåíñòâî(16.4) èìååò âèä(1)η0 = α2 g (1) (ξ 0 ) = α2 Bf (1) (ξ (1) ) < g(ξ (1) ) = f (1) (ξ (1) )Y (ξ (1) ),80è îíî ìîæåò áûòü óïðîùåíî, ïî êðàéíå ìåðå, äî âèäàα2 B < Y (ξ (1) );(16.14)ýòî óïðîùåíèå ñëåäóåò ïðîäåëûâàòü ïðè ðåàëèçàöèè ñîîòâåòñòâóþùåãî àëãîðèòìà 16.2.16.5. Ïðèìåðû ïðèìåíåíèÿ òåõíîëîãèè 16.1.  ïðèìåðå 16.1â êà÷åñòâå f (1) (u) èç ðàâåíñòâà (16.12) âûáðàíà òàáëè÷íàÿ ïëîòíîñòüf (1) (u) = e−u , u > 0, à â êà÷åñòâå Y (u) èñïîëüçîâàíà ôóíêöèÿY (u) = 1 + sin(u/2). Äëÿ îöåíêè âåëè÷èíû s èç ñîîòíîøåíèÿ (16.5)ôîðìóëà (16.13) íå íóæíà, òàê êàê, â ñèëó âûêëàäîê (16.7), âåëè÷èíàḠ âû÷èñëÿåòñÿ òî÷íî.ÏÐÈÌÅÐ 16.3 (2 áàëëà).
Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ , èìåþùåé ïëîòíîñòü ðàñïðåäåëåíèÿ f (u), ïðîïîðöèîíàëüíóþ ôóíêöèèg(u) =1, 0 < u < 1.u2 lg(u + 10) + 10R1Èíòåãðàë Ḡ = 0 (1/(u2 lg(u + 10) + 10)) du íå áåðåòñÿ, ïîýòîìó ôóíêöèÿf (u) íå ÿâëÿåòñÿ ïëîòíîñòüþ ýëåìåíòàðíîãî ðàñïðåäåëåíèÿ. Çàìåòèì,÷òî g(u) ≤ g (1) (u) = 1/(u2 + 10), ò.
å. çäåñüY (u) =11u2 + 10, ïðè÷åì< Y (u) < 1.u2 lg(u + 10) + 10lg 11 + 10Âû÷èñëèì èíòåãðàë√√Z 1Z 11arctg(1/ 10)dud(u/ 10)(1)√√Ḡ ==√=.210 0 (u/ 10)2 + 1100 u + 10(16.15)(16.16)Òàêèì îáðàçîì,f(1)√10√(u) =, 0 < u < 1.arctg(1/ 10)(u2 + 10)Ôîðìóëà ìåòîäà îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ äëÿ âûáîðî÷íîãî(1)çíà÷åíèÿ ξ0 ñëó÷àéíîé âåëè÷èíû ξ (1) ïîëó÷àåòñÿ (ñ ó÷åòîì âûêëàäîê(16.16)) èç öåïî÷êè ðàâåíñòâ√10√arctg(1/ 10)Z0(1)ξ0u2√√du(1)= α0 , arctg(ξ0 / 10) = α0 arctg(1/ 10)+ 1081√√(1)è, íàêîíåö, √ξ0 = 10 tg(α0 arctg(1/10)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
