1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 7
Текст из файла (страница 7)
Ñïåöèàëüíûå ìåòîäû ìîäåëèðîâàíèÿ ãåîìåòðè÷åñêîãî ðàñïðåäåëå-Äëÿ ìîäåëèðîâàíèÿ öåëî÷èñëåííûõ ñëó÷àéíûõ âåëè÷èí èç ïðèìåðîâ 1.11.3 ìîæíî ïðåäëîæèòü ñïåöèàëüíûå ìåòîäû, ñâÿçàííûå ñ îñîáåííîñòÿìè ñîîòâåòñòâóþùèõ âåðîÿòíîñòíûõ ðàñïðåäåëåíèé. Ñðàçó îòìåòèì, ÷òî öåëåñîîáðàçíîñòü ïðèìåíåíèÿ òîãîèëè èíîãî ñïåöèàëüíîãî ìåòîäà (âìåñòî ñòàíäàðòíîãî) òðåáóåò îòäåëüíîãî îáñóæäåíèÿè èññëåäîâàíèÿ.Ðàññìîòðèì ñíà÷àëà ñïåöèàëüíûé ìåòîä ìîäåëèðîâàíèÿ öåëî÷èñëåííîé ñëó÷àéíîéâåëè÷èíû η , èìåþùåé ãåîìåòðè÷åñêîå ðàñïðåäåëåíèå (1.30) (ñì.
ïðèìåð 1.1).íèÿ.Àëãîðèòì 1.10.Ìîäåëèðîâàíèå ïðîèçâîäèòñÿ ïî ôîðìóëåln α+ 1, 0 < p < 1.η=ln(1 − p)(1.38)Ïîêàæåì, ÷òî ñëó÷àéíàÿ âåëè÷èíà (1.38) èìååò ãåîìåòðè÷åñêîå ðàñïðåäåëåíèå, ò. å.pk = P(η = k) = p (1 − p)k−1 ïðè k = 1, 2, . . .. Èìååìln αP(η = k) = P k − 1 ≤< k = P k ln(1 − p) < ln α ≤ (k − 1) ln(1 − p) =ln(1 − p)= P ln(1 − p)k < ln α ≤ ln(1 − p)k−1 = P (1 − p)k < α ≤ (1 − p)k−1 == (1 − p)k−1 − (1 − p)k = (1 − p)k−1 (1 − (1 − p)) = p (1 − p)k−1 ,÷òî è òðåáîâàëîñü äîêàçàòü.Ïðè îïèñàíèè ñëó÷àéíûõ âåëè÷èí η èç ïðèìåðîâ 1.11.3 ãîâîðèëîñü î òîì, ÷òî ýòèâåëè÷èíû ñâÿçàíû ñ êîìáèíàöèÿìè íåçàâèñèìûõ áåðíóëëèåâñêèõ ñëó÷àéíûõ âåëè÷èí{γi } ñ âåðîÿòíîñòüþ óñïåõà p.
Èç ýòîãî ñëåäóåò, ÷òî ìîäåëèðîâàíèå η ìîæíî îñóùåñòâëÿòü ñ ïîìîùüþ ðåàëèçàöèè ñîîòâåòñòâóþùèõ êîìáèíàöèé âåëè÷èí {γi }; òàêèå àëãîðèòìû íàçûâàþòñÿ.  ÷àñòíîñòè, äëÿ ãåîìåòðè÷åñêîãî ðàñïðåäåëåíèÿξ = min{i : γi = 1}, ò. å. ìåòîä áðàêîâêè ñîñòîèò â ïîñëåäîâàòåëüíîé ïðîâåðêå íåðàâåíñòâà αi < p (ñì. àëãîðèòì 1.3) äî òåõ ïîð, ïîêà îíî íå îêàæåòñÿ âåðíûì.  ñèëóçàìå÷àíèÿ 1.2, ìåòîäû áðàêîâêè íåýôôåêòèâíû èç-çà íåîáõîäèìîñòè ðåàëèçàöèè áîëüøîãî êîëè÷åñòâà ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë {αi } (ò. å. ìåòîäû áðàêîâêè ñëåäóåò"çàáðàêîâàòü").ìåòîäàìè áðàêîâêèÑðàâíèâàÿ àëãîðèòìû 1.4 è 1.10 äëÿ ãåîìåòðè÷åñêîãî ðàñïðåäåëåíèÿ, ìîæíî, ïîàíàëîãèè ñ çàìå÷àíèåì 1.3, îòìåòèòü, ÷òî íåñìîòðÿ íà êîìïàêòíîñòü ôîðìóëû (1.38)íåâåðíî ãîâîðèòü, ÷òî àëãîðèòì 1.10 âñåãäà ýêîíîìè÷íåå àëãîðèòìà 1.4. Äëÿ âåðîÿòíîñòè óñïåõà p, áëèçêîé ê åäèíèöå, çàòðàòû t èç (1.29) îòíîñèòåëüíî íåâåëèêè, à â ôîðìóëå (1.38) äëÿ ëþáîãî p äâàæäû ïðèìåíÿåòñÿ òðóäîåìêàÿ îïåðàöèÿ ëîãàðèôìèðîâàíèÿ.Ïîýòîìó äëÿ âûáðàííîãî êîìïüþòåðà è äàííîãî ÿçûêà ïðîãðàììèðîâàíèÿ ìîæíî ýêñïåðèìåíòàëüíî íàéòè ÷èñëî p0 , äëÿ êîòîðîãî ïðè p ≥ p0 áîëåå ýêîíîìè÷íûì ÿâëÿåòñÿàëãîðèòì 1.4, à ïðè p < p0 àëãîðèòì 1.10.1.3.7.
Ñïåöèàëüíûå ìåòîäû ìîäåëèðîâàíèÿ áèíîìèàëüíîãî ðàñïðåäåëåíèÿ. Ðàññìîòðèì òåïåðü ñïåöèàëüíûå ìåòîäû ìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíû ηp,N ,èìåþùåé áèíîìèàëüíîå ðàñïðåäåëåíèå (1.32) ñ ïàðàìåòðàìè p è N (ñì. ïðèìåð 1.2). Ìåòîä áðàêîâêè äëÿ âåëè÷èíû ηp,N îïðåäåëÿåòñÿ ôîðìóëîé (1.33). Ïðè N p(1 − p) > 9 è1/(N + 1) < p < N/(N + 1) ìîæíî òàêæå ïðèìåíÿòü ñëåäóþùèé ïðèáëèæåííûé àëãîðèòì.Àëãîðèòì 1.11.ηp,NihpN p(1 − p) ζ + N p ,(1.39)ηp,N =Ìîäåëèðîâàíèåïðîèçâîäèòñÿ ïî ñëåäóþùåé ôîðìóëå:ãäå ζ ñòàíäàðòíàÿ íîðìàëüíàÿ ñëó÷àéíàÿ âåëè÷èíà.Àëãîðèòìû ìîäåëèðîâàíèÿ ñòàíäàðòíîé íîðìàëüíîé ñëó÷àéíîé âåëè÷èíû ζ ðàññìîòðåíû äàëåå â ðàçä.
1.10. Îáîñíîâàíèå àëãîðèòìà 1.11 ñëåäóåò èç ñîîòíîøåíèÿ (1.33)è òåîðåìûÌóàâðàËàïëàñà, óòâåðæäàþùåé, ÷òî ñëó÷àéíàÿ âåëè÷èíà θN = (ηp,N −pN p)/ N p(1 − p) ñõîäèòñÿ ïî ðàñïðåäåëåíèþ ïðè N → ∞ ê ñòàíäàðòíîé íîðìàëüíîéâåëè÷èíå ζ . Òåîðåìà ÁåððèÝññåíà, â ñâîþ î÷åðåäü, äàåò ñêîðîñòü ýòîé ñõîäèìîñòèp2 + (1 − p)2|FN (x) − Φ(x)| ≤ p,−∞≤x≤+∞N p(1 − p)supãäå FN (x) ôóíêöèÿ ðàñïðåäåëåíèÿ ñëó÷àéíîé âåëè÷èíû θN , à Φ(x) ôóíêöèÿ ðàñïðåäåëåíèÿ ñòàíäàðòíîé íîðìàëüíîé âåëè÷èíû ζ .
Åñëè N p3/2 > 1.07, òî îøèáêà ïðèèñïîëüçîâàíèè íîðìàëüíîé ôóíêöèè ðàñïðåäåëåíèÿ Φ(x) âìåñòî FN (x) íå ïðåâîñõîäèò0.05 ïðè âñåõ x. îïèñàíèè ïðèìåðà 1.3 óïîìÿíóòà òåîðåìà Ïóàññîíà, â êîòîðîé óòâåðæäàåòñÿ, ÷òîïðè âûïîëíåíèè óñëîâèé (1.35) áèíîìèàëüíîå ðàñïðåäåëåíèå ñõîäèòñÿ ê ðàñïðåäåëåíèþÏóàññîíà ñ ïàðàìåòðîì λ. Òåîðåìà Þ.Â.Ïðîõîðîâà äàåò ñêîðîñòü ýòîé ñõîäèìîñòèN i −λ X i iλeN−i ≤ 2λ min(2, λ).CN p (1 − p)−i! Ni=0Èç ýòîãî ñëåäóåò, ÷òî åñëè p èìååò îäèíàêîâûé ñ 1/N ïîðÿäîê ñ ðîñòîì N ëèáî p < 0.1,òî âìåñòî áèíîìèàëüíîãî ðàñïðåäåëåíèÿ ìîæíî ìîäåëèðîâàòü ðàñïðåäåëåíèå Ïóàññîíàñ âåðîÿòíîñòÿìè pi = (N p)i e−N p /i!, i = 0, 1, . . .
, N .  ñâîþ î÷åðåäü, äëÿ ìîäåëèðîâàíèÿðàñïðåäåëåíèÿ Ïóàññîíà ìîæíî èñïîëüçîâàòü êàê ñòàíäàðòíûé àëãîðèòì 1.4 è åãî ìîäèôèêàöèè (ìåòîä Óîëêåðà, êâàíòèëüíûé ìåòîä è ò. ï.), òàê è ñïåöèàëüíûå ìåòîäû èçïîäðàçä. 1.3.8.1.3.8. Ñïåöèàëüíûå ìåòîäû ìîäåëèðîâàíèÿ ðàñïðåäåëåíèÿ Ïóàññîíà. Äëÿíà÷àëà îòìåòèì, ÷òî âåðîÿòíîñòè pi ðàñïðåäåëåíèÿ Ïóàññîíà (1.34) (ñì. ïðèìåð 1.3)ðàñòóò ïðè i = 0, 1, . . . , [λ] è óáûâàþò ïðè i = [λ] + 1, [λ] + 2, .
. .. Èç ýòîãî ñëåäóåò,÷òî äëÿ îòíîñèòåëüíî íåáîëüøèõ λ ðàñïðåäåëåíèå Ïóàññîíà äîïóñêàåò îïòèìàëüíîåðàñïîëîæåíèå âåðîÿòíîñòåé ïî óáûâàíèþ âèäà (1.23); ïðè ýòîì, îäíàêî, ïðè ðåàëèçàöèè ñîîòâåòñòâóþùåãî ñòàíäàðòíîãî àëãîðèòìà 1.4 ñëåäóåò ñîñòàâèòü ìàññèâ íà÷àëüíûõçíà÷åíèé, òàê êàê ïîñëå ïåðåñòàíîâêè âåðîÿòíîñòåé ñîîòíîøåíèå xi = i íå âûïîëíåíîäëÿ íà÷àëüíûõ i. ñâîþ î÷åðåäü, â ñèëó òåîðåìû Ïóàññîíà, äëÿ äîñòàòî÷íî áîëüøèõ λ (êîíêðåòíåå,äëÿ λ > 9) ìîæíî ïðèìåíÿòü ñëåäóþùèé àíàëîã ïðèáëèæåííîãî àëãîðèòìà 1.11.Àëãîðèòì 1.12.η√η = [ λ ζ + λ],Ìîäåëèðîâàíèå ïðîèçâîäèòñÿ ïî ñëåäóþùåé ôîðìóëå:ãäå ζ ñòàíäàðòíàÿ íîðìàëüíàÿ ñëó÷àéíàÿ âåëè÷èíà.Ðàññìîòðèì òàêæå ñëåäóþùèé ìåòîä.Ñëó÷àéíóþ âåëè÷èíó η, èìåþùóþ ðàñïðåäåëåíèå Ïóàññîíà (1.34),ìîæíî ìîäåëèðîâàòü ïî ôîðìóëåÀëãîðèòì 1.13.mYαk < e−λ .η = min m :(1.40)k=0Ôîðìóëó (1.40) ìîæíî îáîñíîâàòü, èñïîëüçóÿ ñëåäóþùåå ñâîéñòâî ïóàññîíîâñêîãîïîòîêà (ñì.
äàëåå ïðèìåð 2.2 èç ïîäðàçä. 2.4.2): ñëó÷àéíàÿ âåëè÷èíà!mX0(− ln αk ) > λη = min m :k=0ïóàññîíîâñêèé ìîìåíò(ýòî òàê íàçûâàåìûé) èìååò ðàñïðåäåëåíèå (1.34).Îðèãèíàëüíûé, ïðîñòîé (â ñìûñëå ïðîãðàììíîé ðåàëèçàöèè) àëãîðèòì 1.13 ìîæåòîêàçàòüñÿ íåýôôåêòèâíûì äëÿ ñëó÷àÿ ìàëûõ λ, â êîòîðîì òðåáóåòñÿ ìíîãîêðàòíîå îáðàùåíèå ê äàò÷èêó ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë (ñì. çàìå÷àíèå 1.2).1.4. ÑÒÀÍÄÀÐÒÍÛÉ ÀËÃÎÐÈÒÌ ÌÎÄÅËÈÐÎÂÀÍÈßÍÅÏÐÅÐÛÂÍÎÉ ÑËÓ×ÀÉÍÎÉ ÂÅËÈ×ÈÍÛ1.4.1.
Ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ. Ïðèìåðû. Ðàññìîòðèì òåïåðü àëãîðèòìû ìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíû ξ , îáëàñòüþ çíà÷åíèé êîòîðîéÿâëÿåòñÿ èíòåðâàë èëè îáúåäèíåíèå èíòåðâàëîâ.  äàëüíåéøåì â ïîäàâëÿþùåì ÷èñëåñëó÷àåâ ïðåäïîëàãàåòñÿ, ÷òî ξ ∈ (a, b), ò. å. ñëó÷àéíàÿ âåëè÷èíà ξ ïðèíèìàåò çíà÷åíèÿ âèíòåðâàëå (a, b), ãäå −∞ ≤ a < b ≤ +∞, è åå ôóíêöèÿ ðàñïðåäåëåíèÿ F (x) = P(ξ < x)íåïðåðûâíà è ñòðîãî âîçðàñòàåò ïðè x ∈ (a, b), ïðè ýòîìF (x) = 0 ïðè x ≤ a è F (x) = 1 ïðè x ≥ b;(1.41)äëÿ ñëó÷àåâ a = −∞ è b = +∞ ñîîòíîøåíèÿ (1.41) ïðèîáðåòàþò âèäF (−∞) = 0,F (+∞) = 1 èëèlim F (x) = 0,x→−∞lim F (x) = 1.x→+∞Ñëó÷àè, êîãäà îáëàñòü çíà÷åíèé ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå íåïåðåñåêàþùèõñÿèíòåðâàëîâ èëè äèñêðåòíûõ ìíîæåñòâ ñ èíòåðâàëàìè (ïðè ýòîì íàðóøàþòñÿ óñëîâèÿñòðîãîé ìîíîòîííîñòè èëè íåïðåðûâíîñòè ôóíêöèè F (x)), áóäóò ñ÷èòàòüñÿ "ýêçîòè÷åñêèìè"(ñì.
äàëåå ïîäðàçä. 1.4.2). ñëó÷àå ξ ∈ (a, b), â îòëè÷èå îò äèñêðåòíîãî ñëó÷àÿ, îòäåëüíîå çíà÷åíèå x0 ∈ (a, b)èìååò íóëåâóþ âåðîÿòíîñòü. Çäåñü ôóíêöèÿ ðàñïðåäåëåíèÿ ïîçâîëÿåò âû÷èñëÿòü âåðîÿòíîñòè òîãî, ÷òî ξ ïðèíàäëåæèò íåêîòîðîìó èíòåðâàëó:P ξ ∈ (c, d) = F (d) − F (c).(1.42)ñòàíäàðòíûé àëãîðèòì (ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ).Àëãîðèòì 1.14. Äëÿ ÷èñëåííîé ðåàëèçàöèè (ìîäåëèðîâàíèÿ) âûáîðî÷íîãî çíà÷åíèÿξ ∈ (a, b) èñïîëüçóåì ôîðìóëó−1Ñôîðìóëèðóåìξ=Fçäåñü α ñòàíäàðòíîå ñëó÷àéíîå ÷èñëî.(α);(1.43)Îáîñíîâàíèå ôîðìóëû (1.43) ñëåäóåò èç òîãî, ÷òî ñëó÷àéíûå âåëè÷èíû ξ è ξ˜ =F (α) îäèíàêîâî ðàñïðåäåëåíû.
Äåéñòâèòåëüíî, äëÿ x ≤ a èìååì Fξ̃ (x) = P(ξ˜ < x) =F (x) = 0, äëÿ x ≥ b âûïîëíåíî Fξ̃ (x) = F (x) = 1, à äëÿ a < x < b ñïðàâåäëèâî ðàâåíñòâîFξ̃ (x) = P(F −1 (α) < x) = P α < F (x) = F (x).−1 ïîñëåäíåé âûêëàäêå èñïîëüçîâàíî óòâåðæäåíèå 1.2.Àëãîðèòì 1.14, íà ïåðâûé âçãëÿä, çàêðûâàåò âîïðîñ î ìîäåëèðîâàíèè ñëó÷àéíûõâåëè÷èí ξ ∈ (a, b). Îäíàêî îñòàåòñÿ îäíà âàæíàÿ "òåõíè÷åñêàÿ"ïðîáëåìà, ñâÿçàííàÿ ñèñïîëüçîâàíèåì ôîðìóë âèäà (1.43) â ðåàëüíûõ âû÷èñëèòåëüíûõ ïðîãðàììàõ.Çàäà÷à 1.1.ψ(x) = F −1 (x)ψ(x)Ïðåäñòàâèòü çàâèñèìîñòüâ âèäå ïðîñòîé êîìïîçèöèèýëåìåíòàðíûõ ôóíêöèé òàê, ÷òîáû âû÷èñëåíèå çíà÷åíèÿìîãëî áûòü ýôôåêòèâíî ðåàëèçîâàíî íà ÝÂÌ. ñëó÷àå, êîãäà çàäà÷à 1.1 ðàçðåøèìà, áóäåì íàçûâàòü ðàñïðåäåëåíèå ñëó÷àéíîéâåëè÷èíû ξ è ñîîòâåòñòâóþùèå ôîðìóëó (1.43) è àëãîðèòì 1.14(ñ òî÷êè çðåíèÿ âîçìîæíîñòè ÷èñëåííîãî ìîäåëèðîâàíèÿ).
Ñðàçó çàìåòèì, ÷òî ïðàêòè÷åñêèäëÿ âñåõ ðàñïðåäåëåíèé, äëÿ êîòîðûõ çàäà÷à 1.1 íåðàçðåøèìà, óäàåòñÿ ïîñòðîèòü àëüòåðíàòèâíûå àëãîðèòìû ÷èñëåííîé ðåàëèçàöèè (ìîäåëèðîâàíèÿ) âûáîðî÷íûõ çíà÷åíèé(ìåòîäû èñêëþ÷åíèÿ, ñóïåðïîçèöèè è ò. ï. ñì. äàëåå ðàçä. 1.61.10). Îäíàêî äëÿ ñëó÷àéíûõ âåëè÷èí, èìåþùèõ ýëåìåíòàðíûå ðàñïðåäåëåíèÿ, àëãîðèòì 1.14 ÿâëÿåòñÿ, êàêïðàâèëî, íàèáîëåå ýôôåêòèâíûì (ýêîíîìè÷íûì).Ðåøåíèå çàäà÷è 1.1 áóäåì ðàññìàòðèâàòü äëÿ ñëó÷àÿ, êîãäà ðàñïðåäåëåíèå âåëè÷èíûξ ∈ (a, b) ÿâëÿåòñÿ, ÷òî îçíà÷àåò ñóùåñòâîâàíèå íåîòðèöàòåëüíîé ôóíêöèè f (u) òàêîé, ÷òî äëÿ ëþáîãî èíòåðâàëà (c, d) ⊆ (a, b) âûïîëíåíîZ dP ξ ∈ (c, d) =f (u) du;(1.44)ýëåìåíòàðíûìèàáñîëþòíî íåïðåðûâíûìcýòî àíàëîã ñîîòíîøåíèÿ (1.42) (ñì. òàêæå îïðåäåëåíèå 1.1 è ñîîòíîøåíèå (1.4)).
Ôóíêöèÿ f (u) íàçûâàåòñÿ. Îíà îïðåäåëåíà ñ òî÷íîñòüþ äî çíà÷åíèé íà ìíîæåñòâå ìåðû íóëü.  äàëüíåéøåì ðàññìàòðèâàþòñÿ íåïðåðûâíûå è êóñî÷íîíåïðåðûâíûå "âåðñèè"ïëîòíîñòè f (u). Ñâîéñòâàìè ïëîòíîñòè ÿâëÿþòñÿ:Z +∞Z bf (u) du =f (u) du = 1;(1.45)f (u) ≥ 0 ïðè u ∈ (a, b);ïëîòíîñòüþ ðàñïðåäåëåíèÿ−∞f (u) = 0 ïðè u ∈/ (a, b).a(1.46)Áóäåì òàêæå ïðåäïîëàãàòü, ÷òî ïðè u ∈ (a, b) ìíîæåñòâî òî÷åê, òàêèõ, ÷òî f (u) = 0,èìååò ìåðó íóëü.
Èç ñîîòíîøåíèé (1.42), (1.44) ñëåäóåò, ÷òîZ xF (x) =f (u) du(1.47)−∞è ïî÷òè âñþäó (ïî ìåðå Ëåáåãà) èìååò ìåñòî ðàâåíñòâî f (u) = dF (u)/du. Èç ñîîòíîøåíèÿ (1.47) ñëåäóåò, ÷òî àáñîëþòíî íåïðåðûâíîå ðàñïðåäåëåíèå ìîæíî çàäàâàòü íåôóíêöèåé ðàñïðåäåëåíèÿ F (x), à ïëîòíîñòüþ f (u). Îòìåòèì òàêæå, ÷òî ïîäàâëÿþùååáîëüøèíñòâî ðàññìàòðèâàåìûõ äàëåå ðàñïðåäåëåíèé ÿâëÿþòñÿ àáñîëþòíî íåïðåðûâíûìè. Ñîîòâåòñòâóþùèå ñëó÷àéíûå âåëè÷èíû áóäåì íàçûâàòü.Èòàê, ïóñòü èìååòñÿ íåïðåðûâíàÿ ñëó÷àéíàÿ âåëè÷èíà ξ ∈ (a, b), ðàñïðåäåëåííàÿñîãëàñíî ïëîòíîñòè f (u).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
