1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 12
Текст из файла (страница 12)
. . +a1ampm fm (u) du = α èëèZξfm (u) du = β.(1.85)amÑðàâíèâàÿ ñîîòíîøåíèÿ (1.82) è (1.85), ïîëó÷àåì ñëåäóþùååÓòâåðæäåíèå 1.13. Ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ äëÿ ñëó÷àéíîé âåëè÷èíû ξ ñ ñîñòàâíîé ïëîòíîñòüþ âèäà (1.83) (àëãîðèòì 1.22) ñîâïàäàåò ñ ìîäèôèöèðîâàííûì ìåòîäîì ñóïåðïîçèöèè (àëãîðèòì 1.21) ñ îïðåäåëåíèåì íîìåðà m ñîãëàñíîñòàíäàðòíîìó àëãîðèòìó ìîäåëèðîâàíèÿ äèñêðåòíîé ñëó÷àéíîé âåëè÷èíû (àëãîðèòì1.1).Çàìå÷àíèå 1.4. Äëÿ äîñòàòî÷íî áîëüøèõ M öåëåñîîáðàçíî âûáèðàòü èç ýêâèâàëåíòíûõ àëãîðèòìîâ 1.21 è 1.22 ìîäèôèöèðîâàííûé ìåòîä ñóïåðïîçèöèè 1.21 è èñïîëüçîâàòü íà ïåðâîì øàãå ýòîãî àëãîðèòìà ýôôåêòèâíûå ìîäèôèêàöèè ñòàíäàðòíîãî àëãîðèòìà 1.1 èç ðàçä. 1.3 (ìåòîä Óîëêåðà, êâàíòèëüíûé ìåòîä è äð.).
Ïðèìåðàìè ýôôåêòèâíîãî èñïîëüçîâàíèÿ ýòîãî ñîîáðàæåíèÿ ìîãóò ñëóæèòü àëãîðèòìû 1.30 è 1.31, ñôîðìóëèðîâàííûå äàëåå â ïîäðàçä. 1.8.1 äëÿ ñëó÷àéíûõ âåëè÷èí ñ êóñî÷íî-ïîñòîÿííûìè èêóñî÷íî-ëèíåéíûìè ïëîòíîñòÿìè.1.7. ÌÅÒÎÄÛ ÈÑÊËÞ×ÅÍÈß1.7.1. Îáùèå ïðèíöèïû ïîñòðîåíèÿ è òðóäîåìêîñòü ìåòîäîâ èñêëþ÷åíèÿ.ìåìåòîäû îòáîðà ìåòîäû îòêàçîârejection òåîðèè ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ øèðîêî èñïîëüçóþòñÿ òàê íàçûâàåìûå(èíîãäà ïðèìåíÿþòñÿ òåðìèíûè,êîòîðûå òàêæå ñîîòâåòñòâóþò, õîòÿ è â ìåíüøåé ñòåïåíè, àíãëèéñêîìó òåðìèíó).Ñóòü ýòèõ ìåòîäîâ ñîñòîèò â ñëåäóþùåì. Ïóñòü ñëó÷àéíûé âåêòîð (ñëó÷àéíàÿ òî÷êà)ζ ðàñïðåäåëåí â íåêîòîðîì ìíîæåñòâå X è äàíî ïîäìíîæåñòâî A ⊆ X .Àëãîðèòì 1.23.TTζATζ∈/AÍàçîâåìs̃ àëãîðèòìà 1.23 ñðåäíèå çàòðàòû íà ïîñòðîåíèå âûáîðî÷íûõ çíà÷åíèé âåêòîðà ζ äî ðåàëèçàöèè T .
Î÷åâèäíî, ÷òî âåëè÷èíà s̃ ïðîïîðöèîíàëüíàìàòåìàòè÷åñêîìó îæèäàíèþ öåëî÷èñëåííîé ñëó÷àéíîé âåëè÷èíû, èìåþùåé ãåîìåòðè÷åñêîå ðàñïðåäåëåíèå ñ ïàðàìåòðîì p = P(ζ ∈ A) (ñì. ïðèìåð 1.1). Ñîãëàñíî ôîðìóëå(1.31) èìååì11.(1.86)s̃ ∼ s = =pP(ζ ∈ A)òîäû èñêëþ÷åíèÿtechniqueÏðîâîäèòñÿ íåêîòîðîå ñòàòèñòè÷åñêîå èñïûòàíèå è ñ÷èòàåòñÿ, ÷òî ñîñòîÿëîñü, åñëè ÷èñëåííàÿ ðåàëèçàöèÿ âåêòîðà ïðèíàäëåæèò , èíå ñîñòîÿëîñü, åñëè.òðóäîåìêîñòüþÎ÷åâèäíî, ÷òî s ≥ 1. Îïòèìèçàöèÿ àëãîðèòìà 1.23 ñâÿçàíà ñ ïðèáëèæåíèåì âåëè÷èíûs ê åäèíèöå.1.7.2. Ìàæîðàíòíûé ìåòîä èñêëþ÷åíèÿ.
 ïîäàâëÿþùåì ÷èñëå ñëó÷àåâ àëãîðèòì 1.23 ïðèìåíÿåòñÿ â ñëåäóþùåé ñèòóàöèè. Ïóñòü òðåáóåòñÿ ìîäåëèðîâàòü ñëó÷àéíûé âåêòîð (ñëó÷àéíóþ âåëè÷èíó) ξ , ðàñïðåäåëåííûé â îáëàñòè U ∈ Rl ñîãëàñíîïëîòíîñòè f (u), êîòîðàÿ ïðîïîðöèîíàëüíà çàäàííîé íåîòðèöàòåëüíîé ôóíêöèè g(u),ò. å.Zg(u), Ḡ =g(u) du.(1.87)f (u) =ḠUÏðåäïîëàãàåòñÿ, ÷òî íè îäèí èç ðàññìîòðåííûõ ðàíåå ìåòîäîâ íå äàåò ýôôåêòèâíîãîàëãîðèòìà ìîäåëèðîâàíèÿ âåêòîðà ξ . Íàäåæäó íà ïîñòðîåíèå ìîäåëèðóþùåãî àëãîðèòìà äëÿ ñëó÷àéíîãî âåêòîðà ñ ïëîòíîñòüþ (1.87) äàåò ñëåäóþùååÓòâåðæäåíèå 1.14.(ξ, η)Ïóñòü òî÷êàðàâíîìåðíî ðàñïðåäåëåíà â îáëàñòèG = {u ∈ U, 0 < v < g(u)},(1.88)ò.å. â "ïîäãðàôèêå"ôóíêöèè g(u); ïðè ýòîì ξ ∈ U è η ∈ (0, g(ξ)). Òîãäà ñëó÷àéíûéâåêòîð ξ ðàñïðåäåëåí ñîãëàñíî ïëîòíîñòè (1.87).Äîêàçàòåëüñòâî.
Òî, ÷òî (l + 1)-ìåðíàÿ òî÷êà (ξ, η) ðàâíîìåðíî ðàñïðåäåëåíà âîáëàñòè G, îçíà÷àåò, ÷òî ñîâìåñòíàÿ ïëîòíîñòü f(ξ ,η) (u, v) òîæäåñòâåííî ðàâíà 1/Ḡ ïðè(u, v) ∈ G è íóëþ èíà÷å. Ñîãëàñíî ôîðìóëå (1.70) äëÿ η = η èìååìZfξ (u) =+∞−∞Zf(ξ ,η) (u, v) dv =0g(u)dvg(u)=.ḠḠÒàêèì îáðàçîì, åñëè ïîëó÷èòü âûáîðî÷íîå çíà÷åíèå òî÷êè (ξ, η), ðàâíîìåðíî ðàñïðåäåëåííîé â G, òî çíà÷åíèå ξ áóäåò ðàñïðåäåëåíî ñîãëàñíî ïëîòíîñòè (1.87).Âîçíèêàåò âîïðîñ: êàêèì îáðàçîì ìîæíî ðåàëèçîâàòü òî÷êó, ðàâíîìåðíî ðàñïðåäåëåííóþ â "ïîäãðàôèêå"çàäàííîé ôóíêöèè? Îòâåò íà ýòîò âîïðîñ äàåò ñëåäóþùååóòâåðæäåíèå, êîòîðîå ÿâëÿåòñÿ ïî ñóòè îáðàòíûì ê óòâåðæäåíèþ 1.14.Óòâåðæäåíèå 1.15.ξ1Zg1 (u)f1 (u) =, Ḡ1 =g1 (u) du,(1.89)Ḡ1UÏóñòü ñëó÷àéíûé âåêòîð ðàñïðåäåëåí ñîãëàñíî ïëîòíîñòèà óñëîâíîå ðàñïðåäåëåíèå ïðè ôèêñèðîâàííîì çíà÷åíèè ξ1 ñëó÷àéíîé âåëè÷èíû η ÿâëÿåòñÿ ðàâíîìåðíûì íà èíòåðâàëå (0, g1(ξ1)).
Òîãäà ñëó÷àéíàÿ òî÷êà (ξ1, η) ðàâíîìåðíîðàñïðåäåëåíà â "ïîäãðàôèêå"G1 = {u ∈ U, 0 < v < g1 (u)}(1.90)ôóíêöèè g1(u).Òî, ÷òî ñëó÷àéíàÿ âåëè÷èíà η óñëîâíî ðàâíîìåðíî ðàñïðåäåëåíàíà èíòåðâàëå (0, g1 (ξ 1 )) îçíà÷àåò, ÷òî ïëîòíîñòü fη (v|ξ 1 ) òîæäåñòâåííî ðàâíà 1/g1 (ξ 1 )ïðè v ∈ (0, g1 (ξ 1 )) è íóëþ èíà÷å. Ñîãëàñíî ôîðìóëàì (1.69), (1.70) äëÿ ξ = ξ 1 è η = η ,èìååì, ÷òî ïëîòíîñòü ðàñïðåäåëåíèÿ ñëó÷àéíîé òî÷êè (ξ 1 , η) ðàâíàÄîêàçàòåëüñòâî.f(ξ1 ,η)(u, v) = f1 (u)fη (v|u) =11g1 (u)×≡,g1 (u)Ḡ1Ḡ1(u, v) ∈ G1 .Åñëè â óòâåðæäåíèè 1.15 âûáðàòü ξ 1 = ξ , òî â ñîâîêóïíîñòè ñ óòâåðæäåíèåì 1.14ïîëó÷àåì ëîãè÷åñêèé êðóã: íàì íóæíî ðàçûãðàòü ñëó÷àéíóþ òî÷êó (ξ, η), ðàâíîìåðíîðàñïðåäåëåííóþ â "ïîäãðàôèêå"G (è òîãäà êîîðäèíàòà ξ èìååò òðåáóåìîå ðàñïðåäåëåíèå ñ ïëîòíîñòüþ (1.87)), íî äëÿ ýòîãî íóæíî ðåàëèçîâàòü âåêòîð ξ ïî ïëîòíîñòè(1.87).
Èìååòñÿ åùå, îäíàêî, óòâåðæäåíèå 1.1, èç êîòîðîãî ñëåäóåò, ÷òî åñëè ïîãðóçèòü"ïîäãðàôèê"G â îáëàñòü G1 â ñèñòåìå êîîðäèíàò (u, v) (ò. å. G ⊆ G1 ) è ðåàëèçîâàòüâûáîðî÷íîå çíà÷åíèå ñëó÷àéíîãî âåêòîðà (ξ 1 , η), ðàâíîìåðíî ðàñïðåäåëåííîãî â G1 , òîïðè óñëîâèè (ξ 1 , η) ∈ G ïàðà (ξ 1 , η) ðàâíîìåðíî ðàñïðåäåëåíà â G. Òîãäà, ñîãëàñíîóòâåðæäåíèþ 1.14, âåêòîð ξ 1 èìååò òðåáóåìîå ðàñïðåäåëåíèå ñ ïëîòíîñòüþ (1.87).Êîíñòðóèðîâàíèå îáëàñòè G1 ñâÿçàíî ñ ðàñøèðåíèåì "ïîäãðàôèêà"G â íàïðàâëåíèè îñè v . Äðóãèìè ñëîâàìè, ðàññìàòðèâàåòñÿ ìàæîðàíòà g1 (u) ôóíêöèè g(u) òàêàÿ,÷òî g(u) ≤ g1 (u) ïðè u ∈ U . Ïåðâîå òðåáîâàíèå ê ìàæîðàíòå g1 (u) òàêîâî, ÷òî äëÿïëîòíîñòè (1.89) èìååòñÿ ýôôåêòèâíûé àëãîðèòì (ôîðìóëà) âèäà ξ 1 = ψ1 (ᾱ1 ) äëÿ ðåàëèçàöèè âûáîðî÷íîãî çíà÷åíèÿ ñëó÷àéíîãî âåêòîðà ξ 1 ñîãëàñíî îäíîìó èç âàðèàíòîâàëãîðèòìà 1.16 (çäåñü ᾱ1 ñîîòâåòñòâóþùèé íàáîð ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë).
Ýòîäàåò.Àëãîðèòì 1.24.ξ1(1.89)ξ 1 = ψ1 (ᾱ1 )η = α2 g1 (ξ 1 )ìàæîðàíòíûé ìåòîä èñêëþ÷åíèÿ1). Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå ñîãëàñíî ïëîòíîñòè, à òàêæå çíà÷åíèå.2). Åñëèη < g(ξ 1 ),:(1.91)òî â êà÷åñòâå èñêîìîãî âûáîðî÷íîãî çíà÷åíèÿ ïðèíèìàåì ξ = ξ1.  ñëó÷àå, êîãäàíåðàâåíñòâî (1.91) íå âûïîëíåíî, ïîâòîðÿåì ïóíêò 1 äàííîãî àëãîðèòìà è ò.
ä.Ñîãëàñíî óòâåðæäåíèþ 1.15, òî÷êà (ξ 1 , η), ðåàëèçóåìàÿ â ïåðâîì ïóíêòå àëãîðèòìà1.24, ðàâíîìåðíî ðàñïðåäåëåíà â îáëàñòè G1 . Åñëè âûïîëíåíî óñëîâèå (1.91), òî ïàðà(ξ 1 , η) ïðèíàäëåæèò îáëàñòè G è, ñîãëàñíî óòâåðæäåíèþ 1.1, ðàâíîìåðíî ðàñïðåäåëåíàâ ýòîé îáëàñòè, è òîãäà, ñîãëàñíî óòâåðæäåíèþ 1.14, âåëè÷èíó ξ 1 ìîæíî ïðèíÿòü âêà÷åñòâå èñêîìîãî âûáîðî÷íîãî çíà÷åíèÿ ξ .Ñîãëàñíî ôîðìóëå (1.86) è óòâåðæäåíèþ 1.1, òðóäîåìêîñòü s̃ àëãîðèòìà 1.24 ïðîïîðöèîíàëüíà âåëè÷èíå1Ḡ = 1.s=(1.92)ḠP (ξ 1 , η) ∈ GÒàêèì îáðàçîì, ìàæîðàíòó g1 (u) ôóíêöèè g(u) ñëåäóåò ïîäáèðàòü òàê, ÷òîáû îáúåìûḠ1 è Ḡ áûëè áëèçêè; ýòî âûïîëíåíî ïðè g1 (u) ≈ g(u).Êàê óêàçàíî âûøå, ìàæîðàíòíûé ìåòîä èñêëþ÷åíèÿ èñïîëüçóåòñÿ íàìíîãî ÷àùåäðóãèõ ìåòîäîâ îòáîðà, ïîýòîìó â ëèòåðàòóðå ÷àñòî àëãîðèòì 1.24 íàçûâàåòñÿ ïðîñòî.Ïðèìåð 1.13.
Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ , èìåþùóþ ïëîòíîñòü ðàñïðåäåëåíèÿ f (u), ïðîïîðöèîíàëüíóþ ôóíêöèèsin ue−u , u > 0.(1.93)g(u) = 1 +2ìåòîäîì èñêëþ÷åíèÿÈíòåãðèðóÿ ïî ÷àñòÿì, ïîëó÷àåì:+∞Z +∞−u (cos u + sin u) eg(u) du = −e−u −= 5/4,40òî åñòü(1.94)04sin uf (u) =1+e−u , u > 0.52Èç ñîîòíîøåíèÿ (1.94) ñëåäóåò, ÷òî ôóíêöèÿ f (u) íå ÿâëÿåòñÿ ïëîòíîñòüþ ýëåìåíòàðíîRξãî ðàñïðåäåëåíèÿ, ò. å. óðàâíåíèå ìåòîäà îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ 0 f (u) du =α (ñì. ñîîòíîøåíèå (1.48)) íåðàçðåøèìî îòíîñèòåëüíî ξ .  ñèëó òîãî, ÷òî | sin u| ≤ 1, âêà÷åñòâå ìàæîðàíòûôóíêöèè (1.93) ìîæíî âçÿòü ôóíêöèþ g1 (u) = 3 e−u /2.
Ëåãêî âûR +∞÷èñëèòü èíòåãðàë 0 g1 (u) du = 3/2. Ñëåäîâàòåëüíî, f1 (u) = e−u , u > 0. Ýòî ÷àñòíûéñëó÷àé ýêñïîíåíöèàëüíîé ïëîòíîñòè (1.51) äëÿ λ = 1. Îòñþäà ïîëó÷àåì ñëåäóþùèéàëãîðèòì ìåòîäà èñêëþ÷åíèÿ:1. Ñîãëàñíî ôîðìóëå (1.53) ïîëó÷àåì âûáîðî÷íîå çíà÷åíèå ξ1 = − ln α1. Ðåàëèçóåìòàêæå âåëè÷èíó η = α2 g1(ξ1) = 3 α2 exp(−ξ1)/2.2. Ïðîâåðÿåì íåðàâåíñòâî η < g(ξ1) èëè 3 α2 < 2 + sin ξ1. Åñëè ýòî íåðàâåíñòâîâûïîëíåíî, òî ïîëàãàåì, ÷òî âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîé âåëè÷èíû ξ ðàâíî ξ = ξ1,èíà÷å ïîâòîðÿåì ïóíêò 1 è ò.ä.Òðóäîåìêîñòü ýòîãî àëãîðèòìà ïðîïîðöèîíàëüíà âåëè÷èíå s = 3/2 : 5/4 = 1, 2 (ñì.ñîîòíîøåíèå (1.92)).1.7.3. Ñïåöèàëüíûå ìåòîäû ïîñòðîåíèÿ ìàæîðàíò.
Íàèáîëåå ïðîñòîé âàðèàíòìàæîðàíòíîãî ìåòîäà èñêëþ÷åíèÿ ïîëó÷àåòñÿ â ñëó÷àå, êîãäà ôóíêöèÿ g(u) îïðåäåëåíà íà îãðàíè÷åííîì ìíîæåñòâå U â Rl è ñóùåñòâóåò (èçâåñòíà) êîíñòàíòà C , òàêàÿ,÷òî g(u) ≤ C ïðè u ∈ U .  êà÷åñòâå ìàæîðàíòû çäåñü ìîæíî âûáðàòü g1 (u) ≡ C , èíà ïåðâîì ýòàïå àëãîðèòìà 1.24 âûáîðî÷íîå çíà÷åíèå âåêòîðà ξ 1 ðåàëèçóåòñÿ ñîãëàñíîðàâíîìåðíîìó ðàñïðåäåëåíèþ â ìíîæåñòâå U .  îäíîìåðíîì ñëó÷àå äëÿ U = (a, b) ⊂ Ràëãîðèòì 1.24 âûãëÿäèò çäåñü ñëåäóþùèì îáðàçîì.Àëãîðèòì 1.25. 1.
Ðåàëèçóåì ξ1 = a + α1 (b − a) è η = α2 C .2. Åñëè η ≤ g(ξ1), òî â êà÷åñòâå âûáîðî÷íîãî çíà÷åíèÿ ñëó÷àéíîé âåëè÷èíû ξ ∈ (a, b)ïðèíèìàåì ξ = ξ1, èíà÷å ïîâòîðÿåì ï. 1 è ò.ä. ñâîå âðåìÿ Äæ.Íåéìàí ïåðâûì ïðåäëîæèë ìàæîðàíòíûé ìåòîä èñêëþ÷åíèÿ èìåííî â òàêîé ôîðìå, è ÷àñòî ýòîò ïðîñòîé ÷àñòíûé ñëó÷àé íàçûâàþò ìåòîäîì Íåéìàíà (ìû òàêæå áóäåì ïðèäåðæèâàòüñÿ ýòîé òåðìèíîëîãèè).  ëèòåðàòóðå ïî ìåòîäàìÌîíòå-Êàðëî èíîãäà ìåòîäàìè Íåéìàíà íàçûâàþò âñå ìåòîäû èñêëþ÷åíèÿ.Âàæíîå îáîáùåíèå àëãîðèòìà 1.25 ñâÿçàíî ñ èñïîëüçîâàíèåì êóñî÷íî-ïîñòîÿííûõìàæîðàíò, êîãäà èíòåðâàë (a, b) ðàçáèò íà ïîëóèíòåðâàëû ∆i = (ui−1 , ui ], i = 1, .
. . , Mòî÷êàìè a = u0 < u1 < . . . < uM −1 < uM = b, è äëÿ êàæäîãî ∆i èçâåñòíà êîíñòàíòàCi òàêàÿ, ÷òî g(u) ≤ Ci ïðè u ∈ ∆i . Åñëè g1 (u) ≡ Ci ïðè u ∈ ∆i , òî íà ïåðâîì ýòàïåàëãîðèòìà 1.24 òðåáóåòñÿ ìîäåëèðîâàòü âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîé âåëè÷èíû ξ1ñîãëàñíî êóñî÷íî-ïîñòîÿííîé ïëîòíîñòè (îñîáåííîñòè òàêîãî ìîäåëèðîâàíèÿ ïîäðîáíîðàçîáðàíû â ïîäðàçä. 1.8.1).Äëÿ ïîñòðîåíèÿ ìàæîðàíòû ìîæíî èñïîëüçîâàòü äðóãèå (êðîìå îãðàíè÷åííîñòè)ñâîéñòâà çàäàííîé ôóíêöèè g(u).
 ñëåäóþùåì ïðèìåðå èñïîëüçîâàíî ñâîéñòâî âûïóêëîñòè (â îäíîìåðíîì ñëó÷àå).Ïðèìåð 1.14. Ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ξ , èìåþùóþ ïëîòíîñòü ðàñïðåäåëåíèÿ2 arcsin u, 0<u<1(1.95).f (u) =π−2Ôóíêöèÿ (1.95) íå ÿâëÿåòñÿ ïëîòíîñòüþ ýëåìåíòàðíîãî ðàñïðåäåëåíèÿ, ò. ê. èíòåãðèðîâàíèå ïî ÷àñòÿì äàåòZ ξp2f (u) du =(ξ arcsin ξ + 1 − ξ 2 − 1);π−20ê ñëîâó, ïîñëåäíåå ñîîòíîøåíèå îáîñíîâûâàåò ïðàâèëüíîñòü íîðìèðóþùåé êîíñòàíòû2/(π−2) ïëîòíîñòè (1.95). Ôóíêöèÿ (1.95) âûïóêëà âíèç è âîçðàñòàåò (f 0 (u) > 0, f 00 (u) >0 ïðè 0 < u < 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
