Поглинальні ланцюги Маркова та їх основні числові характеристики (реферат)

РЕФЕРАТ На тему:

Поглинальні ланцюги Маркова та їх основні числові характеристики Вивчаючи поглинальні ланцюги Маркова, визначають:

1) імовірності переходу до поглинального стану за умови, що процес почався з непоглинального стану;

2) середнє значення часу перебування процесу в непоглинальному стані, перш ніж він перейде до одного з поглинальних станів, за умови, що в початковий момент часу процес був у непоглинальному стані;

3) середню кількість зроблених кроків, перш ніж процес перейде до поглинального стану, якщо початковий стан процесу був непоглинальним.

1. Канонічна форма матриці.

Розглядаючи поглинальні ланцюги Маркова, стани процесу нумерують так, щоб поглинальні дістали перші номери.

З огляду на це матриця — вона в такому разі називається канонічною формою матриці у загальному випадку подається у вигляді:

$$\begin{array}{ccc}{}_1& {}_2& {}_m\end{array}$$ $$\begin{array}{ccc}{}_{m+1}& {}_{m+2}& {}_N\end{array}$$.

$$=\begin{array}{c}\begin{array}{cc}\text{Поглинальні стани}& {}_1\\ & {}_2\\ & \\ & {}_m\end{array}\\ \begin{array}{cc}\text{Непоглинальні стани}& {}_{m+1}\\ & {}_{m+2}\\ & \\ & {}_N\end{array}\end{array}\left(\begin{array}{cccccccc}& & & & & & & \\ & I& & & & & O& \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & R& & & & & Q& \\ & & & & & & & \end{array}\right)$$. (24).

Тут I — одинична матриця розміром mxm;

O — матриця розміром $$mx\left(N-m\right),$$ усі елементи якої дорівнюють нулю;

Q — матриця розміром $$\left(N-m\right)x\left(N-m\right),$$ елементами якої є ймовірності переходів системи з непоглинальних станів до непоглинальних;

R — матриця розміром $$\left(N-m\right)xm,$$ елементами якої є ймовірності, що визначають перехід системи з непоглинального стану до поглинального.

Приклад 11. За даною матрицею ймовірностей однокрокового переходу поглинального ланцюга Маркова.

$$=\left(\begin{array}{cccc}\mathrm{0,1}& \mathrm{0,6}& \mathrm{0,3}& 0\\ 0& \mathrm{0,1}& \mathrm{0,4}& \mathrm{0,5}\\ \mathrm{0,}\text{05}& \mathrm{0,}\text{75}& 0& \mathrm{0,2}\\ 0& 0& 0& 1\end{array}\right)$$.

побудувати її канонічну форму.

Розв’язання. Матриця писує поглинальний ланцюг Маркова з чотирма станами $${}_1,{}_2,{}_3,{}_4,$$ із яких стан $${}_4$$ є поглинальним.

Тому для матриці.

$$\begin{array}{c}\begin{array}{cccc}{}_1& {}_2& {}_3& {}_4\end{array}\\ =\begin{array}{c}{}_1\\ {}_2\\ {}_3\\ {}_4\end{array}\left(\begin{array}{cccc}\mathrm{0,1}& \mathrm{0,6}& \mathrm{0,3}& 0\\ 0& \mathrm{0,1}& \mathrm{0,4}& \mathrm{0,5}\\ \mathrm{0,}\text{05}& \mathrm{0,}\text{75}& 0& \mathrm{0,2}\\ 0& 0& 0& 1\end{array}\right)\end{array}$$.

канонічна форма набирає такого вигляду:

$$\begin{array}{c}\begin{array}{cccc}{}_4& {}_1& {}_2& {}_3\end{array}\\ \begin{array}{c}{}_4\\ {}_1\\ {}_2\\ {}_3\end{array}\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& \mathrm{0,1}& \mathrm{0,6}& \mathrm{0,3}\\ \mathrm{0,5}& 0& \mathrm{0,1}& \mathrm{0,4}\\ \mathrm{0,2}& \mathrm{0,}\text{05}& \mathrm{0,}\text{75}& 0\end{array}\right)\end{array}$$ ,.

де $$I=\left(1\right)-O=\left(\begin{array}{ccc}0& 0& 0\end{array}\right)-$$.

$$Q=\left(\begin{array}{ccc}\mathrm{0,1}& \mathrm{0,6}& \mathrm{0,3}\\ 0& \mathrm{0,1}& \mathrm{0,4}\\ \mathrm{0,}\text{05}& \mathrm{0,}\text{75}& \mathrm{0,2}\end{array}\right)-$$ $$R=\left(\begin{array}{c}0\\ \mathrm{0,5}\\ \mathrm{0,2}\end{array}\right)$$ .

Приклад 12. За даною матрицею ймовірностей однокрокового переходу системи.

$$\begin{array}{c}\begin{array}{ccccc}{}_1& {}_2& {}_3& {}_4& {}_5\end{array}\\ =\begin{array}{c}{}_1\\ {}_2\\ {}_3\\ {}_4\\ {}_5\end{array}\left(\begin{array}{ccccc}\mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}& \mathrm{0,1}& \mathrm{0,2}\\ \mathrm{0,4}& 0& \mathrm{0,1}& \mathrm{0,3}& \mathrm{0,2}\\ \mathrm{0,2}& \mathrm{0,1}& 0& \mathrm{0,2}& \mathrm{0,5}\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\end{array}\right)\end{array}$$.

побудувати канонічну матрицю.

Розв’язання. Канонічна форма матриці буде така:

$$\begin{array}{c}\begin{array}{ccccc}{}_n& {}_5& {}_1& {}_2& {}_3\end{array}\\ \begin{array}{c}{}_4\\ {}_5\\ {}_1\\ {}_2\\ {}_3\end{array}\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}\\ \mathrm{0,3}& \mathrm{0,2}& \mathrm{0,4}& 0& \mathrm{0,1}\\ \mathrm{0,2}& \mathrm{0,5}& \mathrm{0,2}& \mathrm{0,1}& 0\end{array}\right)\end{array}$$ ,.

де $$I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)-$$ $$O=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\end{array}\right)-$$ $$Q=\left(\begin{array}{ccc}\mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}\\ \mathrm{0,4}& 0& \mathrm{0,1}\\ \mathrm{0,2}& \mathrm{0,1}& 0\end{array}\right)-$$ $$R=\left(\begin{array}{cc}\mathrm{0,1}& \mathrm{0,2}\\ \mathrm{0,3}& \mathrm{0,2}\\ \mathrm{0,2}& \mathrm{0,5}\end{array}\right)$$ .

2. Фундаментальна матриця Для поглинального ланцюга Маркова з однокроковою матрицею ймовірностей, поданою в канонічній формі (24), справджуються такі твердження:

1) $$\underset{k->\mathrm{}}{\text{lim}}{Q}^k=O,$$ де О — нульова матриця, всі елементи якої нулі;

2) матриця $$\left(I-Q\right),$$ де І - одинична матриця, має обернену;

3) $${\left(I-Q\right)}^{-1}=I+Q+Q^2+Q^3+\text{.}\text{.}\text{.}=\underset{k=0}{\overset{\mathrm{}}{}}{Q}^k$$. (25).

Для поглинального ланцюга Маркова ймовірність переходу системи (процесу) в поглинальний стан зі збільшенням числа кроків переходу k прямує до одиниці. А тому і буде виконуватися рівність.

$$\underset{k->\mathrm{}}{\text{lim}}{Q}^k=O$$. (26).

Приклад 13. За даною однокроковою матрицею ймовірностей.

$$\begin{array}{c}\begin{array}{ccccc}{}_1& {}_2& {}_3& {}_4& {}_5\end{array}\\ =\begin{array}{c}{}_1\\ {}_2\\ {}_3\\ {}_4\\ {}_5\end{array}\left(\begin{array}{ccccc}\mathrm{0,2}& \mathrm{0,1}& \mathrm{0,4}& \mathrm{0,1}& \mathrm{0,1}\\ 0& 1& 0& \mathrm{0,3}& 0\\ \mathrm{0,5}& \mathrm{0,}\text{05}& \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,2}\\ \mathrm{0,}\text{25}& \mathrm{0,}\text{15}& \mathrm{0,2}& 1& \mathrm{0,}\text{35}\\ 0& 0& 0& 0& 1\end{array}\right)\end{array}$$.

установити, як змінюються значення ймовірностей переходу з одного стану до іншого зі зростанням кількості кроків k.

Розв’язання. Перейдемо від матриці о її канонічної форми, беручи до уваги, що стани $${}_2$$ і $${}_5$$ поглинальні:

$$\begin{array}{c}\begin{array}{ccccc}{}_2& {}_5& {}_1& {}_3& {}_4\end{array}\\ \begin{array}{c}{}_2\\ {}_5\\ {}_1\\ {}_3\\ {}_4\end{array}\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,1}& \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}& \mathrm{0,2}\\ \mathrm{0,}\text{05}& \mathrm{0,2}& \mathrm{0,5}& \mathrm{0,1}& \mathrm{0,}\text{15}\\ \mathrm{0,}\text{15}& \mathrm{0,}\text{35}& \mathrm{0,}\text{25}& \mathrm{0,2}& \mathrm{0,}\text{05}\end{array}\right)\end{array}$$ .

Отже, маємо:

$$I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)-$$ $$O=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\end{array}\right)$$ …

$$R=\left(\begin{array}{cc}\mathrm{0,1}& \mathrm{0,1}\\ \mathrm{0,}\text{05}& \mathrm{0,2}\\ \mathrm{0,}\text{15}& \mathrm{0,}\text{35}\end{array}\right)$$ — матриця, елементи якої є ймовірності переходів системи з непоглинальних станів $${}_{i}Q=\left({}_1,{}_3,{}_4\right)$$ до поглинальних $${}_{j}I=\left({}_2,{}_5\right)-$$.

$$Q=\left(\begin{array}{ccc}\mathrm{0,2}& \mathrm{0,4}& \mathrm{0,2}\\ \mathrm{0,5}& \mathrm{0,1}& \mathrm{0,}\text{15}\\ \mathrm{0,}\text{25}& \mathrm{0,2}& \mathrm{0,}\text{05}\end{array}\right)$$ — матриця, елементами якої є ймовірності переходів системи з непоглинальних станів до непоглинальних (тобто система перебуває лише у станах $${}_{i}Q\left({}_1,{}_2,{}_3\right))\text{.}$$.

Простежимо, як змінюються значення ймовірностей переходу для матриць R і Q зі зміною кількості кроків.

1) $$k=5$$ :

$${\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,1}& \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}& \mathrm{0,2}\\ \mathrm{0,}\text{05}& \mathrm{0,2}& \mathrm{0,5}& \mathrm{0,1}& \mathrm{0,}\text{15}\\ \mathrm{0,}\text{15}& \mathrm{0,}\text{35}& \mathrm{0,}\text{25}& \mathrm{0,2}& \mathrm{0,}\text{05}\end{array}\right)}^5=\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,}\text{288}& \mathrm{0,}\text{502}& \mathrm{0,}\text{091}& \mathrm{0,}\text{075}& \mathrm{0,}\text{044}\\ \mathrm{0,}\text{24}& \mathrm{0,}\text{557}& \mathrm{0,}\text{091}& \mathrm{0,}\text{07}& \mathrm{0,}\text{042}\\ \mathrm{0,}\text{271}& \mathrm{0,}\text{59}& \mathrm{0,}\text{061}& \mathrm{0,}\text{049}& \mathrm{0,}\text{029}\end{array}\right)$$ .

2) $$k=\text{20}$$ :

$${\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,1}& \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}& \mathrm{0,2}\\ \mathrm{0,}\text{05}& \mathrm{0,2}& \mathrm{0,5}& \mathrm{0,1}& \mathrm{0,}\text{15}\\ \mathrm{0,}\text{15}& \mathrm{0,}\text{35}& \mathrm{0,}\text{25}& \mathrm{0,2}& \mathrm{0,}\text{05}\end{array}\right)}^{\text{20}}=$$.

$$=\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,}\text{357}& \mathrm{0,}\text{641}& \mathrm{6,}\text{611}{\text{10}}^{-4}& \mathrm{5,}\text{289}{\text{10}}^{-4}& \mathrm{3,}\text{16}{\text{10}}^{-4}\\ \mathrm{0,}\text{307}& \mathrm{0,}\text{692}& \mathrm{6,}\text{396}{\text{10}}^{-4}& \mathrm{5,}\text{117}{\text{10}}^{-4}& \mathrm{3,}\text{057}{\text{10}}^{-4}\\ \mathrm{0,}\text{316}& \mathrm{0,}\text{683}& \mathrm{4,}\text{379}{\text{10}}^{-4}& \mathrm{3,}\text{503}{\text{10}}^{-4}& \mathrm{2,}\text{093}{\text{10}}^{-4}\end{array}\right)$$ .

Як бачимо, зі зростанням кількості кроків імовірності матриці R збільшуються, а ймовірності матриці Q зменшуються. І вже за $$k=\text{105}$$ матриця набирає такого вигляду:

$${\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,1}& \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,4}& \mathrm{0,2}\\ \mathrm{0,}\text{05}& \mathrm{0,2}& \mathrm{0,5}& \mathrm{0,1}& \mathrm{0,}\text{15}\\ \mathrm{0,}\text{15}& \mathrm{0,}\text{35}& \mathrm{0,}\text{25}& \mathrm{0,2}& \mathrm{0,}\text{05}\end{array}\right)}^{\text{105}}=\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ \mathrm{0,}\text{358}& \mathrm{0,}\text{642}& 0& 0& 0\\ \mathrm{0,}\text{307}& \mathrm{0,}\text{693}& 0& 0& 0\\ \mathrm{0,}\text{317}& \mathrm{0,}\text{683}& 0& 0& 0\end{array}\right)\text{.}$$.

Отже, коли кількість кроків $$k=\text{105}$$, усі елементи матриці Q дорівнюють нулям, і система може перебувати лише у стані $${}_{i}R,$$ із якого вона неодмінно переходить до одного з поглинальних станів — $${}_2$$ чи $${}_5\text{.}$$.

Матриця $$\left(I-Q\right)$$ матиме обернену лише за умови, що визначник її не дорівнює нулю, тобто $$\text{det}\left(I-Q\right)/=0\text{.}$$.

Доведемо, що $$\text{det}\left(I-Q\right)/=0\text{.}$$.

Скориставшись властивістю визначника.

$$\text{det}\left(\text{AB}\right)=\text{det}A\text{det}B,$$ (27).

розглянемо рівність.

$$\begin{array}{c}\left(I-Q\right)\left(I+Q+Q^2+Q^3+\text{.}\text{.}\text{.}+Q^{n-1}\right)=\\ \left(I-Q\right)+\left(Q-Q^2\right)+\text{.}\text{.}\text{.}+\left(Q^{n-1}-Q^n\right)=I-Q^n,\end{array}$$.

звідки.

$$\left(I-Q\right)\left(I+Q+Q^2+Q^3+\text{.}\text{.}\text{.}+Q^{n-1}\right)=I-Q^n\text{.}$$ (28) (28).

Отже, $$\underset{n->\mathrm{}}{\text{lim}}\left(I-Q^n\right)=I,$$ а тому для великих значень n (кількості кроків) $$\text{det}\left(I-Q^n\right)/=0\text{.}$$.

Із (27) і (28) випливає, що.

$$\text{det}\left(I-Q\right)\left(I+Q+Q^2+\text{.}\text{.}\text{.}+Q^{n-1}\right)=$$.

$$=\text{det}\left(I-Q\right)\text{det}\left(I+Q+Q^2+\text{.}\text{.}\text{.}+Q^{n-1}\right)/=0\text{.}$$.

Оскільки $$\text{det}\left(I-Q\right)/=\mathrm{0,}$$ то матриця $$\left(I-Q\right)$$ має обернену. Із (28) маємо: $$I+Q+Q^2+\text{.}\text{.}\text{.}+Q^{n-1}={\left(I-Q\right)}^{-1}\left(I-Q^n\right)$$. Звідси при $$n->\mathrm{}$$ дістаємо $$I+Q+Q^2+Q^3+\text{.}\text{.}\text{.}={\left(I-Q\right)}^{-1}=\underset{k=0}{\overset{\mathrm{}}{}}{Q}^k\text{.}$$.

На практиці обернену матрицю $${\left(I-Q\right)}^{-1}$$ знаходять, здебільшого, традиційними методами.

Матрицю $$N={\left(I-Q\right)}^{-1}$$ називають фундаментальною для поглинального ланцюга Маркова.

Елемент, який у матриці N міститься на перетині і-го рядка і.

j-го стовпця, характеризує середнє значення кількості випадків перебування системи (процесу) у стані $${}_j$$ і позначається $$M_i\left({}_j\right)$$ .

Фундаментальну матрицю N можна дістати й іншим методом. Справді, нехай $$n_j$$ — функція, значення якої дорівнює загальній кількості моментів часу, протягом якого система (процес) перебуватиме у стані $${}_{j}Q,$$ а $$u_j^{\left(k\right)}$$ — функція, яка може набувати лише двох значень: 1 — з імовірністю $$p_{\text{ij}}^{\left(k\right)},$$ коли система на k-му кроці перебуватиме у стані $${}_j,$$ і 0 — з імовірністю $$\left(1-p_{\text{ij}}^{\left(k\right)}\right)$$ у протилежному випадку.

Тоді дістаємо:

$$M_i\left(n_j\right)=\left\{M_i\underset{k=0}{\overset{\mathrm{}}{}}{u}_j^{\left(k\right)}\right\}=\left\{\underset{k=0}{\overset{\mathrm{}}{}}{M}_i\left(u_j^{\left(k\right)}\right)\right\}=$$.

$$=\left\{\underset{k=0}{\overset{\mathrm{}}{}}\left(1p_{\text{ij}}^{\left(k\right)}+0\left(1-p_{\text{ij}}^{\left(k\right)}\right)\right)\right\}=\left\{\underset{k=0}{\overset{\mathrm{}}{}}{p}_{\text{ij}}^{\left(k\right)}\right\}=\underset{k=0}{\overset{\mathrm{}}{}}\left\{p_{\text{ij}}^{\left(k\right)}\right\}=\underset{k=0}{\overset{\mathrm{}}{}}{Q}^k\text{.}$$.