1626435387-cbed9341b165fae9f16c4a05686b9115 (Войтишек - Основы метода Монте-Карло), страница 8

Àëãîðèòì 13.1íà ïåðâûé âçãëÿä çàêðûâàåò âîïðîñ î ìîäåëèðîâàíèè ñëó÷àéíûõ âåëè÷èí ξ ∈ (a, b). Îäíàêî îñòàåòñÿ îäíà âàæíàÿ ¾òåõíè÷åñêàÿ¿ ïðîáëåìà,ñâÿçàííàÿ ñ èñïîëüçîâàíèåì ôîðìóë âèäà (13.7) â ðåàëüíûõ âû÷èñëèòåëüíûõ ïðîãðàììàõ.ÇÀÄÀ×À 13.1. Ïðåäñòàâèòü çàâèñèìîñòü ψ(x) = F −1 (x) â âèäåïðîñòîé êîìïîçèöèè ýëåìåíòàðíûõ ôóíêöèé òàê, ÷òîáû âû÷èñëåíèåçíà÷åíèÿ ψ(x) ìîãëî áûòü ýôôåêòèâíî ðåàëèçîâàíî íà ÝÂÌ. ñëó÷àå, êîãäà çàäà÷à 13.1 ðàçðåøèìà, áóäåì íàçûâàòü ïëîòíîñòüðàñïðåäåëåíèÿ ñëó÷àéíîé âåëè÷èíû ξ è ñîîòâåòñòâóþùóþ ôîðìóëó (13.7) ýëåìåíòàðíûìè (ñ òî÷êè çðåíèÿ âîçìîæíîñòè ÷èñëåííîãî ìîäåëèðîâàíèÿ). Ñðàçó çàìåòèì, ÷òî ïðàêòè÷åñêè äëÿ âñåõ ðàñïðåäåëåíèé, äëÿ êîòîðûõ çàäà÷à 13.1 íåðàçðåøèìà, óäàåòñÿ ïîñòðîèòü àëüòåðíàòèâíûå àëãîðèòìû ÷èñëåííîé ðåàëèçàöèè (ìîäåëèðîâàíèÿ) âûáîðî÷íûõ çíà÷åíèé (ìåòîäû èñêëþ÷åíèÿ, ñóïåðïîçèöèè è ò.

ï. ñì. äàëååðàçä. 1517). Îäíàêî äëÿ ñëó÷àéíûõ âåëè÷èí, èìåþùèõ ýëåìåíòàðíûåðàñïðåäåëåíèÿ, àëãîðèòì 13.1 ÿâëÿåòñÿ, êàê ïðàâèëî, íàèáîëåå ýôôåêòèâíûì (ýêîíîìè÷íûì).13.4. Ïðèìåðû ïëîòíîñòåé, íå ÿâëÿþùèõñÿ ýëåìåíòàðíûìè.Îïèøåì òðóäíîñòè, âîçíèêàþùèå ïðè ðåøåíèè çàäà÷è 13.1. Ïóñòü èìååòñÿ íåïðåðûâíàÿ ñëó÷àéíàÿ âåëè÷èíà ξ ∈ (a, b), ðàñïðåäåëåííàÿ ñîãëàñíî ïëîòíîñòè f (u). Ñ ó÷åòîì òîãî ÷òî âåëè÷èíû ξ è F −1 (α) ïðèíàäëåæàòèíòåðâàëó (a, b), à ôóíêöèÿ F (x) ÿâëÿåòñÿ âîçðàñòàþùåé íà ýòîì èíòåðâàëå, ïåðåïèøåì ðàâåíñòâî (13.7) â ýêâèâàëåíòíîé ôîðìå F (ξ0 ) = α0 .40 ñâîþ î÷åðåäü, â ñèëó ñîîòíîøåíèé (13.5), (13.6), ïîñëåäíåå ðàâåíñòâîìîæíî ïåðåïèñàòü â âèäåZ ξ0f (u) du = α0 .(13.8)aÐàñïðåäåëåíèå ñëó÷àéíîé âåëè÷èíû ξ ÿâëÿåòñÿ ýëåìåíòàðíûì, åñëè ðåøåíèå óðàâíåíèÿ (13.8) ïðåäñòàâèìî â âèäå ξ0 = ψ(α0 ), ãäå ψ(x) ïðîñòàÿ êîìïîçèöèÿ ýëåìåíòàðíûõ ôóíêöèé, è âû÷èñëåíèå çíà÷åíèÿ ψ(x)íà ÝÂÌ ðåàëèçóåòñÿ äîñòàòî÷íî ýôôåêòèâíî.Óðàâíåíèå (13.8) ìîæåò áûòü íåðàçðåøèìûì ïî äâóì ïðè÷èíàì.Ïåðâàÿ ïðè÷èíà ñâÿçàíà ñ òåì, ÷òî èíòåãðàë â ëåâîé ÷àñòè ðàâåíñòâà(13.8) íå áåðåòñÿ (ò.

å. ñîîòâåòñòâóþùàÿ ïåðâîîáðàçíàÿ íå âûðàæàåòñÿâ ýëåìåíòàðíûõ ôóíêöèÿõ); ïðèìåðîì ìîæåò ñëóæèòü øèðîêî ïðèìåíÿåìîå ñòàíäàðòíîå íîðìàëüíîå ðàñïðåäåëåíèå (ñì., íàïðèìåð, [2]) ñïëîòíîñòüþ2e−u /2, −∞ < u < +∞;(13.9)f (u) = √2πçäåñü è äàëåå ïðåäåëû, îãðàíè÷èâàþùèå ïåðåìåííóþ u, îáîçíà÷àþò èíòåðâàë (a, b) (âíå ýòîãî èíòåðâàëà âûïîëíåíî ñîîòíîøåíèå (13.5)). Äëÿðàñïðåäåëåíèÿ (13.9) èìååòñÿ ýôôåêòèâíûé àëãîðèòì ìîäåëèðîâàíèÿ,ñâÿçàííûé ñî ñâîéñòâàìè èçîòðîïíîãî âåêòîðà ñëó÷àéíîé äëèíû (ñì.,íàïðèìåð, [1] è ðàçä. 17).Âòîðàÿ ïðè÷èíà, ïî êîòîðîé ðàñïðåäåëåíèå ñëó÷àéíîé âåëè÷èíû ìîæåò íå îêàçàòüñÿ ýëåìåíòàðíûì, ñâÿçàíà ñ òåì, ÷òî äàæå åñëè èíòåãðàëèç (13.8) áåðåòñÿ, ïîëó÷àåìîå óðàâíåíèå ìîæåò áûòü íåðàçðåøèìûì (âýëåìåíòàðíûõ ôóíêöèÿõ) îòíîñèòåëüíî ξ0 .

 êà÷åñòâå ïðèìåðà òàêîéñèòóàöèè ìîæíî ïðèâåñòè ðàñïðåäåëåíèå ñ ïîëèíîìèàëüíîé ïëîòíîñòüþf (u) =NXci ui , 0 < u < 1.(13.10)i=0Ïîëó÷àåìîå ïðè ðåøåíèè óðàâíåíèÿ (13.8) äëÿ ïëîòíîñòè (13.10) ñîîòíîøåíèåNXci ξ0i+1 /(i + 1) = α0i=0â îáùåì ñëó÷àå íåðàçðåøèìî (â ýëåìåíòàðíûõ ôóíêöèÿõ) îòíîñèòåëüíîξ0 ïðè N ≥ 2 è ci 6= 0. Ñïåöèàëüíûå àëãîðèòìû ìîäåëèðîâàíèÿ ðàñïðåäåëåíèÿ (13.10) (â ÷àñòíîñòè, ìåòîä ñóïåðïîçèöèè äëÿ ñëó÷àÿ ci ≥ 041è ìåòîä èñêëþ÷åíèÿ äëÿ ïðîèçâîëüíûõ êîýôôèöèåíòîâ {ci }, à òàêæåíåêîòîðûå ñïåöèàëüíûå ìåòîäû) ïðåäñòàâëåíû äàëåå â ðàçä. 16 (ñì.ïðèìåð 16.2).13.5. Ïðèìåðû ýëåìåíòàðíûõ ïëîòíîñòåé. Íåñìîòðÿ íà ïåðå÷èñëåííûå â ïðåäûäóùåì ïîäðàçäåëå òðóäíîñòè, ìîæíî ïîñòðîèòüíåîãðàíè÷åííîå êîëè÷åñòâî ïðèìåðîâ ýëåìåíòàðíûõ ðàñïðåäåëåíèé.

Ýòóâîçìîæíîñòü äàåò, â ÷àñòíîñòè, ïðîñòàÿ òåõíîëîãèÿ, îñíîâàííàÿ íà òåîðåìå î çàìåíå ñëó÷àéíûõ ïåðåìåííûõ (ñì. óòâåðæäåíèå 13.1 è òåõíîëîãèþ 13.1). Ïîýòîìó èìååò ñìûñë ïðåäñòàâëÿòü ýëåìåíòàðíûå ðàñïðåäåëåíèÿ, â òîé èëè èíîé ñòåïåíè ¾çíàìåíèòûå¿ (âàæíûå) â ïðèëîæåíèÿõìåòîäà Ìîíòå-Êàðëî è òåîðèè âåðîÿòíîñòåé.Îñîáî îòìåòèòì, ÷òî â çàãîëîâêàõ ïðèâîäèìûõ çäåñü è äàëåå â ðàçä.1416 è â ïðèë. 1 ïðèìåðîâ è çàäà÷ óêàçàí (â ñêîáêàõ) ïðèáëèçèòåëüíûéáàëë (â ïðåäåëàõ îò íóëÿ äî òðåõ) çà ñîîòâåòñòâóþùèé ïðèìåð ñ òî÷êèçðåíèÿ âûïîëíåíèÿ ñåìåñòðîâîãî äîìàøíåãî çàäàíèÿ (ñì. ïðèë. 3).ÏÐÈÌÅÐ 13.1 (0.5 áàëëà).

Ðàññìîòðèì ýêñïîíåíöèàëüíîå ðàñïðåäåëåíèå (ñì., íàïðèìåð, [2]) ñ ïëîòíîñòüþf (u) = λ e−λ u ,u > 0; λ > 0.(13.11)Ñôåðà ïðèìåíåíèÿ ýòîãî ðàñïðåäåëåíèÿ âåñüìà øèðîêà (ñì., íàïðèìåð,[1]). Íà îñíîâå ýòîãî ðàñïðåäåëåíèÿ ôîðìèðóþòñÿ ïóàññîíîâñêèå ïîòîêè, èñïîëüçóåìûå â òåîðèè ìàññîâîãî îáñëóæèâàíèÿ, â ïðîñòåéøèõ ìîäåëÿõ òåîðèè ïåðåíîñà èçëó÷åíèÿ, ïðè ìîäåëèðîâàíèè ñëó÷àéíûõ ïîëåéè ò. ä.Ðåøàÿ óðàâíåíèå âèäà (13.8), ïîñëåäîâàòåëüíî ïîëó÷àåìZ0ξ0ξ0λ e−λ u du = α0 , −e−λ u = α0 , 1 − e−λ ξ0 = α00è, íàêîíåö, ξ0 = − ln(1 − α0 )/λ.

Çàìåòèì, ÷òî âåëè÷èíà α0 = 1 − α ðàâíîìåðíî ðàñïðåäåëåíà â (0, 1). Äåéñòâèòåëüíî, â ñèëó òîãî ÷òîα ∈ (0, 1), èìååì Fα0 (x) = 0 ïðè x ∈ (−∞, 0] è Fα0 (x) = 1 ïðèx ∈ [1, +∞). Íàêîíåö, äëÿ x ∈ (0, 1) âûïîëíåíîFα0 (x) = P(1 − α < x) = P(α > 1 − x) = 1 − (1 − x) = x,(13.12)ò. å. ñëó÷àéíàÿ âåëè÷èíà α0 èìååò ôóíêöèþ ðàñïðåäåëåíèÿ (10.1). Îáðàùàÿñü ê äàò÷èêó òèïà RAN DOM , ìû ìîæåì ñ÷èòàòü, ÷òî ðåàëèçóåòñÿ42âûáîðî÷íîå çíà÷åíèå α0 , è òîãäà ìîäåëèðóþùàÿ ôîðìóëà äëÿ ýêñïîíåíöèàëüíîãî ðàñïðåäåëåíèÿ ïðèîáðåòàåò âèäξ0 = −ln α00.λ(13.13)ÇÀÌÅ×ÀÍÈÅ 13.1. Ïîñëåäíåå íà ïåðâûé âçãëÿä íåñóùåñòâåííîå ñîîáðàæåíèå î çàìåíå (1−α0 ) íà α00 ÿâëÿåòñÿ âåñüìà âàæíûì ñ ïðèêëàäíîé òî÷êè çðåíèÿ, ò.

ê. âî ìíîãèõ ïðàêòè÷åñêèõ ðàñ÷åòàõ êîëè÷åñòâîîáðàùåíèé n ê ôîðìóëå (13.13) î÷åíü âåëèêî (n 1) è íåáîëüøàÿ ýêîíîìèÿ ε, ñâÿçàííàÿ ñ ëèêâèäàöèåé îäíîãî âû÷èòàíèÿ, ìîæåò äàòüîùóòèìûé âûèãðûø â ýôôåêòèâíîñòè íà âåëè÷èíó nε. Ïðè ïðàêòè÷åñêîì ïðèìåíåíèè òåõ èëè èíûõ ìîäåëèðóþùèõ ñîîòíîøåíèé â òðóäîåìêèõ ïðåöåçèîííûõ ðàñ÷åòàõ ñëåäóåò âåñüìà òùàòåëüíî âûâåðÿòüýòè ôîðìóëû íà ïðåäìåò èõ ýôôåêòèâíîñòè. Íàïðèìåð, ñîîòíîøåíèå(13.13) ìîæíî ïåðåïèñàòü â âèäå ξ0 = (ln(1/α00 ))/λ, îäíàêî ïîñëåäíÿÿôîðìóëà õóæå ñ òî÷êè çðåíèÿ ïðàêòè÷åñêîãî ïðèìåíåíèÿ, ÷åì ñîîòíîøåíèå (13.13), ò. ê.

îïåðàöèÿ äåëåíèÿ áîëåå òðóäîåìêà, ÷åì âçÿòèåìèíóñà.ÇÀÌÅ×ÀÍÈÅ 13.2. Äëÿ îòíîñèòåëüíî ñëîæíûõ ýëåìåíòàðíûõïëîòíîñòåé f (u) ïðè ðåøåíèè óðàâíåíèÿ (13.8) è âûâîäå ñîîòâåòñòâóþùåé ôîðìóëû ξ0 = ψξ (α0 ) ìîãóò ñëó÷èòüñÿ íåòî÷íîñòè (îøèáêè). ïîäàâëÿþùåì ÷èñëå ñëó÷àåâ ýòè íåòî÷íîñòè ìîæíî îáíàðóæèòüñ ïîìîùüþ ñëåäóþùåé ïðîñòîé ïðîöåäóðû, êîòîðóþ ìû áóäåì â äàëüíåéøåì íàçûâàòü ÏÐÎÂÅÐÊÎÉ 13.1: ïîëó÷åííóþ ïðè ðåøåíèè óðàâíåíèÿ (13.8) ôîðìóëóξ0 = ψξ (α0 ) ïîäñòàâüòå α0 = 0. Ïðè ýòîì äîëæíî ïîëó÷èòüñÿξ0 = ψξ (0) = a. Ñîîòâåòñòâåííî äëÿ α0 = 1 äîëæíî ïîëó÷èòüñÿ ξ = ψξ (1) = b. ÷àñòíîñòè, äëÿ ôîðìóëû (13.13) ïðîâåðêà 13.1 ïðè α0 = 0äàåò α00 = 1 è ξ0 = (− ln 1)/λ = 0, à ïðè α0 = 1 èìååì α00 = 0 èξ0 = (− ln 0)/λ = +∞.Äëÿ ìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíû ξ ñ ïîëèíîìèàëüíîé ïëîòíîñòüþ (13.10) â ðàçä.

16 ïðåäñòàâëåíû ñïåöèàëüíûå ìåòîäû ñóïåðïîçèöèè è èñêëþ÷åíèÿ. Ïîñòðîåíèå ýòèõ ìåòîäîâ îñíîâàíî íà òîì, ÷òîïðè ci > 0 ñëàãàåìîå ci ui ñóììû (13.10) ïðîïîðöèîíàëüíî ñëåäóþùåéïëîòíîñòè ýëåìåíòàðíîãî ðàñïðåäåëåíèÿ.ÏÐÈÌÅÐ 13.2 (0.5 áàëëà). Ðàññìîòðèì ñòåïåííîå ðàñïðåäåëåíèå ñïëîòíîñòüþf (u) = (i + 1)ui , 0 < u < 1.(13.14)43Ðåøàÿ óðàâíåíèå (13.8) äëÿ ïëîòíîñòè (13.14), ïîëó÷àåì1/(i+1)ξ0i+1 = α0 èëè ξ0 = α0.(13.15)Ïðîâåðêà 13.1 ïðè α0 = 0 äàåò ξ0 = 0, à ïðè α0 = 1 èìååì ξ0 = 1.ÇÀÌÅ×ÀÍÈÅ 13.3.  äàëüíåéøåì áóäåì íàçûâàòü ðàñïðåäåëåíèÿ(13.11), (13.14) è ñîîòâåòñòâóþùèå ìîäåëèðóþùèå ôîðìóëû (13.13),(13.15) òàáëè÷íûìè è íå áóäåì ïðåäñòàâëÿòü äëÿ íèõ ðåçóëüòàòûïðîâåðêè 13.1. Òàáëè÷íûì áóäåì ñ÷èòàòü òàêæå ðàâíîìåðíîå ðàñïðåäåëåíèå íà êîíå÷íîì èíòåðâàëå (a, b) ñ ñîîòâåòñòâóþùèìè ïëîòíîñòüþ ðàñïðåäåëåíèÿ è ìîäåëèðóþùåé ôîðìóëîé:f (u) = 1/(b − a); a < u < b; ξ0 = a + (b − a)α0 .(13.16)ÏÐÈÌÅÐ 13.3 (0.5 áàëëà).

Ïîõîæàÿ íà (13.15) ôîðìóëà ïîëó÷àåòñÿ ïðè ìîäåëèðîâàíèè ñëó÷àéíîé âåëè÷èíû ξ ñ ðàñïðåäåëåíèåì Ïàðåòîf (u) = cu−c−1 , u > 1, c > 0. Ýòî ðàñïðåäåëåíèå âñòðå÷àåòñÿ â çàäà÷àõRξýêîíîìè÷åñêîé ñòàòèñòèêè. Ðåøåíèåì óðàâíåíèÿ 1 0 cu−c−1 du = α0 ÿâëÿåòñÿ ξ0 = (1 − α0 )−1/c . Ó÷èòûâàÿ, ÷òî ñëó÷àéíàÿ âåëè÷èíà α0 = 1 − αðàâíîìåðíî ðàñïðåäåëåíà (ñì. ñîîòíîøåíèå (13.12)), ñîãëàñíî çàìå÷àíèþ 13.1, öåëåñîîáðàçíî èñïîëüçîâàòü ôîðìóëó ξ0 = (α00 )−1/c .

Ïðîâåðêà 13.1 ïðè α0 = 0 äàåò α00 = 1 è ξ0 = 1, à ïðè α0 = 1 èìååì α00 = 0 èξ0 = +∞.ÏÐÈÌÅÐ 13.4 (2 áàëëà). Ïðè ÷èñëåííîì ðåøåíèè çàäà÷ òåîðèèïåðåíîñà èçëó÷åíèÿ (ñì. ðàçä. 6) øèðîêî èñïîëüçóåòñÿ èíäèêàòðèñàÕåíüè Ãðèíñòåéíà (ñì., íàïðèìåð, [1]), ïðåäñòàâëÿþùàÿ ñîáîéïëîòíîñòü ðàñïðåäåëåíèÿ êîñèíóñà óãëà ðàññåÿíèÿ ïðè ñòîëêíîâåíèè¾ôîòîíà¿ ñ ÷àñòèöåé ñðåäû ñëåäóþùåãî âèäà:f (u) =1 − µ22 (1 + µ2 − 2 µ u)3/2ïðè u, µ ∈ (−1, +1).(13.17)R1Íåñëîæíî ïîêàçàòü, ÷òî Eξ = −1 uf (u) du = µ. Äëÿ ìîäåëèðîâàíèÿ¾ðàññåÿíèÿ âïåðåä¿ ïðèíèìàþò µ ≈ 1, à äëÿ ¾ðàññåÿíèÿ íàçàä¿ áåðóòµ ≈ −1.