1625915144-a0b004e5d7d0e6e9b8f80b0c67f3317f (843874), страница 20
Текст из файла (страница 20)
Åå íàçûâàþò ìàðêîâñêîé ïî èìåíè èçâåñòíîãî ðóññêîãî ìàòåìàòèêà À.À.Ìàðêîâà (1856 1922), â òðóäàõ êîòîðîãî âïåðâûå ñèñòåìàòè÷åñêè èçó÷àëàñü òàêàÿ çàâèñèìîñòü.Öåïü íàçûâàåòñÿ îäíîðîäíîé, åñëè âåðîÿòíîñòè ïåðåõîäà P(Xn = j/Xn−1 = i) íåçàâèñÿò îò n. Ìû áóäåì èçó÷àòü òîëüêî îäíîðîäíûå öåïè Ìàðêîâà.Áóäåì îáîçíà÷àòü ÷åðåç pij = P(Xn = j/Xn−1 = i) âåðîÿòíîñòè ïåðåõîäà èç i-ãîñîñòîÿíèÿ â j -å çà îäèí øàã è pij (n) = P(Xn+k = j/Xk = i) = P(Xn = j/X0 = i) 96âåðîÿòíîñòè ïåðåõîäà çà n øàãîâ (ýòè âåðîÿòíîñòè îò k íå çàâèñÿò äëÿ îäíîðîäíûõöåïåé).Ïóñòü çàäàíî ðàñïðåäåëåíèå ñëó÷àéíîé âåëè÷èíû X0 , åãî íàçûâàþò íà÷àëüíûìðàñïðåäåëåíèåì öåïè:Xπj0 = P(X0 = j),πj0 = 1,jè ïóñòü çàäàíû òàêæå âåðîÿòíîñòè ïåðåõîäà {pij }. Ýòîãî äîñòàòî÷íî, ÷òîáû íàéòèðàñïðåäåëåíèå öåïè πjn = P(Xn = j) äëÿ ëþáîãî ìîìåíòà âðåìåíè n.
Äåéñòâèòåëüíî,äëÿ ëþáîãî j ïî ôîðìóëå ïîëíîé âåðîÿòíîñòè ïîëó÷àåìXXπj1 = P(X1 = j) =P(X0 = i)P(X1 = j/X0 = i) =πi0 pij ,(7)iiP(Xn−1 = i)P(Xn = j/Xn−1 = i) =Xè àíàëîãè÷íîπjn = P(Xn = j) =Xiπin−1 pij .iÏðåäïîëîæèì äëÿ ïðîñòîòû, ÷òî öåïü èìååò êîíå÷íîå ìíîæåñòâî ñîñòîÿíèéE1 , E2 , . .
. , Er . Òîãäà ñîâîêóïíîñòü âåðîÿòíîñòåé ïåðåõîäà {pij } îáðàçóåò ìàòðèöór × r, êîòîðóþ ìû îáîçíà÷èì P. Îíà, î÷åâèäíî, îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:1) pij ≥ 0 ïðè âñåõ i = 1, . . . , r; j = 1, . . . , r;2)rPpij = 1 (ò.å. ñóììà ýëåìåíòîâ ëþáîé ñòðîêè ðàâíà 1).j=1Ìàòðèöû ñ óêàçàííûìè äâóìÿ ñâîéñòâàìè íàçûâàþòñÿ ñòîõàñòè÷åñêèìè. Îáîçíà÷èì âåêòîð-ñòðîêó ðàñïðåäåëåíèÿ Xn ÷åðåç π n = (π1n , . . .
, πrn ), òîãäà äëÿ âåêòîðàπ 1 èìååì â ñèëó (7)π 1 = π 0 P,è àíàëîãè÷íî äëÿ ëþáîãî nπ n = π n−1 P = . . . = π 0 Pn .Êðîìå òîãî,πjn=rXP(X0 = i)P(Xn = j/X0 = i) =i=1rXπi0 pij (n).i=1Ýòî îçíà÷àåò, ÷òî ÷èñëà pij (n) ÿâëÿþòñÿ ýëåìåíòàìè ìàòðèöû Pn .Òàêèì îáðàçîì, çíàíèå íà÷àëüíîãî ðàñïðåäåëåíèÿ π 0 è ìàòðèöû ïåðåõîäíûõ âåðîÿòíîñòåé P ïîçâîëÿåò âû÷èñëèòü ðàñïðåäåëåíèå Xn â ïðîèçâîëüíûé ìîìåíò âðåìåíè n.Åñëè ìíîæåñòâî ñîñòîÿíèé áåñêîíå÷íî, òî è ìàòðèöà P áóäåò áåñêîíå÷íîé, íîïðèâåäåííûå ñîîòíîøåíèÿ ñîõðàíÿòñÿ.Ïðèìåðû.1. Ïîñëåäîâàòåëüíîñòü Yn , n ≥ 0, íåçàâèñèìûõ öåëî÷èñëåííûõ ñëó÷àéíûõ âåëè÷èí, î÷åâèäíî, ÿâëÿåòñÿ öåïüþ Ìàðêîâà.2. Ïóñòü Yn , n ≥ 0 íåçàâèñèìûå öåëî÷èñëåííûå ñëó÷àéíûå âåëè÷èíû.
Òîãäàïîñëåäîâàòåëüíîñòü ñóìì Xn = Y0 + . . . + Yn , n ≥ 0, îáðàçóåò öåïü Ìàðêîâà. Äåéñòâèòåëüíî, äëÿ ëþáûõ ìîìåíòîâ âðåìåíè 0 ≤ n1 < n2 < . . . < nk < m < n è äëÿ97ëþáûõ öåëûõ ÷èñåë i1 , i2 , . . . , ik , i, j èìååìP(Xn = j/Xn1 = i1 , . . . , Xnk = ik , Xm = i) ====P(Xn = j, Xn1 = i1 , . . .
, Xnk = ik , Xm = i)=P(Xn1 = i1 , . . . , Xnk = ik , Xm = i)P(Ym+1 + . . . + Yn = j − i, Xn1 = i1 , . . . , Xnk = ik , Xm = i)=P(Xn1 = i1 , . . . , Xnk = ik , Xm = i)P(Ym+1 + . . . + Yn = j − i)P(Xn1 = i1 , . . . , Xnk = ik , Xm = i)=P(Xn1 = i1 , . . . , Xnk = ik , Xm = i)= P(Ym+1 + . . . + Yn = j − i) = P(Xn = j/Xm = i).Åñëè ñëó÷àéíûå âåëè÷èíû Yn â ýòèõ ïðèìåðàõ âäîáàâîê êî âñåìó îäèíàêîâî ðàñïðåäåëåíû, òî öåïè Ìàðêîâà áóäóò îäíîðîäíûìè. Íåòðóäíî íàéòè äëÿ íèõ âåðîÿòíîñòè ïåðåõîäà çà îäèí øàã. Ïóñòü P(Yn = j) = pj .  ïåðâîì èç ïðèìåðîâP(Yn = j/Yn−1 = i) = P(Yn = j) = pj ,âî âòîðîì èç íèõP(Xn = j/Xn−1 = i) = P(Yn = j − i) = pj−i .3. Ïðåäïîëîæèì, ÷òî êàæäûé äåíü íà ñêëàä çàâîçèòñÿ íåêîòîðîå ñëó÷àéíîå ÷èñëîìåøêîâ ñ ìóêîé, è äîëæíî âûâîçèòüñÿ åæåäíåâíî òàêæå íåêîòîðîå ñëó÷àéíîå ÷èñëîìåøêîâ. Ñ÷èòàåì, ÷òî äâèæåíèå ïðîäóêöèè â ðàçíûå äíè íå ñâÿçàíî äðóã ñ äðóãîì.Îáîçíà÷èì ÷åðåç Xn êîëè÷åñòâî ìåøêîâ ñ ìóêîé íà ñêëàäå ê êîíöó n-ãî äíÿ.
Ïîñêîëüêó âìåñòèìîñòü ñêëàäà îãðàíè÷åíà (ñêàæåì, ÷èñëîì M ìåøêîâ), òî, î÷åâèäíî,Xn−1 + Yn , åñëè 0 ≤ Xn−1 + Yn ≤ MXn = 0,åñëè Xn−1 + Yn < 0,M,åñëè Xn−1 + Yn > M,ãäå ÷åðåç Yn îáîçíà÷åíî ïðåäïîëàãàåìîå ïðèðàùåíèå ïðîäóêöèè (ïîñòóïëåíèå ìèíóñâûâîç) â n-é äåíü. Íåòðóäíî âèäåòü, ÷òî ïîñëåäîâàòåëüíîñòü Xn òàêæå îáðàçóåò öåïüÌàðêîâà.5.2.Âîçâðàòíîñòü ñîñòîÿíèéÎáîçíà÷èì ÷åðåçqj (n) = P(Xn = j, Xn−1 6= j, . . . , X1 6= j / X0 = j)âåðîÿòíîñòü òîãî, ÷òî, âûéäÿ èç ñîñòîÿíèÿ ñ íîìåðîì j , íàøà öåïü âïåðâûå âåðíåòñÿâ íåãî íà n-ì øàãå. Ïóñòü∞XQj =qj (n)n=198 âåðîÿòíîñòü òîãî, ÷òî, âûéäÿ èç ñîñòîÿíèÿ ñ íîìåðîì j , öåïü êîãäà-ëèáî âåðíåòñÿâ íåãî.Ñîñòîÿíèå Ej íàçûâàåòñÿ âîçâðàòíûì, åñëè Qj = 1, è íåâîçâðàòíûì, åñëè Qj < 1.Ïðèìåð.
×àñòèöà áëóæäàåò ïî öåëî÷èñëåííûì òî÷êàì âåùåñòâåííîé îñè, îñóùåñòâëÿÿ ñ âåðîÿòíîñòüþ 1/2 â êàæäûé ìîìåíò âðåìåíè n = 1, 2, . . . ïðûæîê âïðàâîíà åäèíèöó, è îñòàâàÿñü íà ìåñòå ñ âåðîÿòíîñòüþ 1/2. Ýòî ñîîòâåòñòâóåò òîìó, ÷òîpjj = pj,j+1 = 1/2 äëÿ ëþáîãî j .1/2Îïðåäåëåíèå.1/2j s-j+1ßñíî, ÷òî qj (1) = 1/2 è qj (n) = 0 ïðè n > 1. Ïîýòîìó Qj = 1/2 äëÿ ëþáîãî j , èâñå ñîñòîÿíèÿ öåïè íåâîçâðàòíû.Ñîñòîÿíèå Ej âîçâðàòíî òîãäà è òîëüêî òîãäà, êîãäàÒåîðåìà.Pj =∞Xpjj (n) = ∞.n=1Pj.1 + PjÄëÿ íåâîçâðàòíîãî Ej èìååò ìåñòî Qj =Äîêàçàòåëüñòâî.Èìååò ìåñòî ñîîòíîøåíèåpjj (n) = qj (1)pjj (n − 1) + . .
. + qj (n − 1)pjj (1) + qj (n).(8)Ñìûñë åãî â ñëåäóþùåì. Âåðîÿòíîñòü âåðíóòüñÿ â j -å ñîñòîÿíèå çà n øàãîâ ðàçáèâàåòñÿ íà ïåðåáîð âçàèìíî èñêëþ÷àþùèõ ñëó÷àåâ â çàâèñèìîñòè îò òîãî, çà êàêîå÷èñëî øàãîâ öåïü âïåðâûå âåðíåòñÿ â ñîñòîÿíèå Ej . Åñëè, ê ïðèìåðó, âïåðâûå öåïüâåðíåòñÿ çà k øàãîâ (âåðîÿòíîñòü ýòîãî ðàâíà qj (k)), òî çàòåì åé íóæíî ãäå-òî ïîãóëÿòü è âåðíóòüñÿ íàçàä çà îñòàâøèåñÿ n − k øàãîâ.
Ïåðåáîð âàðèàíòîâ ïî âñåì kîñóùåñòâëÿåòñÿ ñóììèðîâàíèåì. Ôîðìàëüíî (8) ïîëó÷àåòñÿ èç öåïî÷êè ðàâåíñòâP(Xn = j/X0 = j) ==nX1P(X0 = j)P(Xn = j, X0 = j)=P(X0 = j)P(X0 = j, X1 6= j, . . . , Xk−1 6= j, Xk = j, Xn = j) =k=1nXP(X0 = j, X1 6= j, . . . , Xk−1 6= j, Xk = j)=×P(X0 = j)k=1nP(X0 = j, X1 6= j, . . . , Xk−1 6= j, Xk = j, Xn = j) X×=qj (k)pjj (n − k).P(X0 = j, X1 6= j, . . .
, Xk−1 6= j, Xk = j)k=1Äàëåå íàì ïîòðåáóåòñÿ ïîíÿòèå ïðîèçâîäÿùåé ôóíêöèè. Ðàíåå ââîäèëîñü ïîíÿòèå ïðîèçâîäÿùåé ôóíêöèè äëÿ ðàñïðåäåëåíèÿ, ñîñðåäîòî÷åííîãî íà ðåøåòêå öåëûõ÷èñåë. Ïóñòü òåïåðü {an , n ≥ 1} ïðîèçâîëüíàÿ îãðàíè÷åííàÿ ÷èñëîâàÿ ïîñëåäîâàòåëüíîñòü, ñâîéñòâà êîòîðîé òðåáóåòñÿ èçó÷èòü. Ïðîèçâîäÿùåé ôóíêöèåé ýòîé ïîñëåäîâàòåëüíîñòè íàçûâàåòñÿ ñóììà ðÿäàg(z) =∞Xn=199an z n .Ýòîò ðÿä ñõîäèòñÿ àáñîëþòíî ïðè êàæäîì z èç ìíîæåñòâà |z| <P1 è ÿâëÿåòñÿ òàìíåïðåðûâíîé (è äàæå àíàëèòè÷åñêîé) ôóíêöèåé. Åñëè, ê òîìó æå, ∞n=1 |an | < ∞, òîíåïðåðûâíîñòü áóäåò èìåòü ìåñòî ïðè |z| ≤ 1. Çíàÿ ôóíêöèþ g(z), ìîæíî îäíîçíà÷íîâîññòàíîâèòü âñå êîýôôèöèåíòû an ; ïî ïîâåäåíèþ ôóíêöèè g(z) ìîæíî îïðåäåëèòüìíîãèå ñâîéñòâà ýòèõ êîýôôèöèåíòîâ.
Èññëåäîâàíèå ñâîéñòâ ïîñëåäîâàòåëüíîñòè an÷åðåç åå ïðîèçâîäÿùóþ ôóíêöèþ âî ìíîãèõ ñëó÷àÿõ ÿâëÿåòñÿ âåñüìà ýôôåêòèâíûì.Ìû âîñïîëüçóåìñÿ ýòèì èíñòðóìåíòîì.Ââåäåì ïðîèçâîäÿùèå ôóíêöèèPj (z) =∞XQj (z) =pjj (n)z n ,|z| < 1,qj (n)z n ,|z| ≤ 1.n=1∞Xn=1Óìíîæèì îáå ÷àñòè ðàâåíñòâà (8) íà z n è ïðîñóììèðóåì ïî n (çäåñü |z| < 1):Pj (z) =∞Xznn=1==∞Xk=1∞XnXqj (k)pjj (n − k) =k=1zk∞Xz n−k qj (k)pjj (n − k) =n=kkz qj (k)∞Xz m pjj (m) = Qj (z)(1 + Pj (z)).m=0k=1Îòñþäà ïîëó÷àåìQj (z) =Pj (z),1 + Pj (z)Pj (z) =Qj (z).1 − Qj (z)(9)Ïóñòü òåïåðü Pj = ∞.
Ïîêàæåì, ÷òî â ýòîì ñëó÷àå Pj (z) → ∞ ïðè z % 1.Äåéñòâèòåëüíî,P∞ ÷èñëî NP äëÿ ëþáîãî êàê óãîäíî áîëüøîãî ÷èñëà M ìîæíî íàéòèp(n)≥2M.ÝòîñëåäóåòèçðàñõîäèìîñòèðÿäàP=òàêîå, ÷òî Njn=1 pjj (n).n=1 jjÄëÿ ïîëîæèòåëüíûõ ÷èñåë z , äîñòàòî÷íî áëèçêèõ ê 1, áóäåò âûïîëíÿòüñÿ z N ≥ 1/2èNNXXnPj (z) ≥pjj (n)z ≥pjj (n)z N ≥ M.n=1n=1Èòàê, ðàç Pj (z) → ∞, òî Qj (z) → 1, ýòî ñëåäóåò èç ïåðâîãî ðàâåíñòâà â (9).
Ïîñêîëüêóôóêíêöèÿ Qj (z) íåïðåðûâíà â òî÷êå z = 1, òî ïðè z → 1Qj (z) → Qj (1) = Qj = 1,òî åñòü ñîñòîÿíèå âîçâðàòíî.Îáðàòíî, ïóñòü Qj = 1. Òîãäà îïÿòü â ñèëó íåïðåðûâíîñòè Qj (z) → Qj (1) = 1ïðè z → 1, à çíà÷èò Pj (z) → ∞ ýòî ñëåäóåò èç âòîðîãî ðàâåíñòâà â (9). Îòñþäàñëåäóåò, ÷òî Pj = ∞, ïîñêîëüêó â ïðîòèâíîì ñëó÷àå ðÿäPj (z) =∞Xpjj (n)z nn=1ñõîäèëñÿ áû ïðè |z| ≤ 1 è áûë áû íåïðåðûâíîé ôóíêöèåé â òî÷êå z = 1, òî åñòü áûëîáû Pj (z) → Pj (1) < ∞, ÷òî íåâîçìîæíî.100Pj.
Òåîðåìà äîêàçàíà.1 + Pj. Ñîñòîÿíèÿ Ei è Ej íàçûâàþòñÿ ñîîáùàþùèìèñÿ, åñëè pij (m) > 0è pji (k) > 0 ïðè íåêîòîðûõ m ≥ 1 è k ≥ 1.. Ñîîáùàþùèåñÿ ñîñòîÿíèÿ îäíîâðåìåííî îáà âîçâðàòíû èëè îáà íåâîçâðàòíû.Äîêàçàòåëüñòâî. Ïóñòü äëÿ ñîñòîÿíèé Ei è Ej âûïîëíÿåòñÿ pij (m) > 0 è pji (k) > 0ïðè íåêîòîðûõ m ≥ 1 è k ≥ 1. Òîãäà ïðè n ≥ 1Åñëè Pj < ∞, òî ïðè z → 1 ïîëó÷àåì èç (9) Qj =ÎïðåäåëåíèåÒåîðåìà ñîëèäàðíîñòèpii (n + m + k) ≥ pij (m)pjj (n)pji (k), pjj (n + m + k) ≥ pji (k)pii (n)pij (m),PP∞ïîýòîìó ðÿäû ∞n=1 pii (n) èn=1 pjj (n) ñõîäÿòñÿ èëè ðàñõîäÿòñÿ îäíîâðåìåííî.5.3.Ýðãîäè÷åñêàÿ òåîðåìàÌû âèäåëè, ÷òî öåïè Ìàðêîâà ìîãóò ðàññìàòðèâàòüñÿ â êà÷åñòâå ìàòåìàòè÷åñêèõìîäåëåé, êîòîðûå îïèñûâàþò ýâîëþöèþ âî âðåìåíè òîãî èëè èíîãî îáúåêòà.