11.1: Вступ

Більшість нашого дослідження ймовірності стосувалося незалежних випробувань процесів. Ці процеси є основою класичної теорії ймовірностей і значної частини статистики. Ми обговорили дві основні теореми для цих процесів: Закон великих чисел і Центральна гранична теорема.

Ми бачили, що коли послідовність випадкових експериментів формує незалежний процес випробувань, можливі результати для кожного експерименту однакові і відбуваються з однаковою ймовірністю. Крім того, знання результатів попередніх експериментів не впливає на наші прогнози щодо результатів наступного експерименту. Розподіл результатів одного експерименту достатній для побудови дерева та міри дерева для послідовності$n$ експериментів, і ми можемо відповісти на будь-яке питання ймовірності щодо цих експериментів, використовуючи цю деревоподібну міру.

Сучасна теорія ймовірностей вивчає випадкові процеси, для яких знання попередніх результатів впливає на прогнози майбутніх експериментів. В принципі, коли ми спостерігаємо послідовність випадкових експериментів, всі минулі результати можуть вплинути на наші прогнози на наступний експеримент. Наприклад, це повинно бути при прогнозуванні оцінок учня за послідовністю іспитів на курсі. Але допустити таку велику спільність було б дуже важко довести загальні результати.

У 1907 році А.А.Марков почав вивчення важливого нового типу випадкового процесу. У цьому процесі результат даного експерименту може вплинути на результат наступного експерименту. Цей тип процесу називається марковської ланцюгом.

Визначення ланцюга Маркова

Ланцюг Маркова ми опишемо наступним чином: У нас є набір$S = \{s_1,s_2,\ldots,s_r\}$. Процес починається в одному з цих станів і послідовно переміщається з одного стану в інше. Кожен хід називається a Якщо ланцюг в даний час знаходиться в стані$s_i$, то він переходить до стану$s_j$ на наступному кроці з ймовірністю, позначеною$p_{ij}$, і ця ймовірність не залежить від того, в яких станах ланцюг перебував до поточного стану.

Імовірності$p_{ij}$ називаються Процес може залишатися в тому стані, в якому він знаходиться, і це відбувається з ймовірністю$p_{ii}$. Початковий розподіл ймовірностей, визначений на$S$, визначає початковий стан. Зазвичай це робиться шляхом вказівки певного стану в якості початкового стану.

R.A. Howard ¹ надає нам мальовничий опис ланцюга Маркова як жаби, що стрибає на наборі латаття. Жаба починається на одній з подушечок, а потім перестрибує з лілії на подушечку лілії з відповідними ймовірностями переходу.

[іспит 11.1.1] За словами Кемені, Снелл, і Томпсон, ² Земля Оз благословлена багатьма речами, але не гарною погодою. У них ніколи не буває двох приємних днів поспіль. Якщо у них хороший день, у них так само, як і сніг, як і дощ наступного дня. Якщо у них сніг або дощ, у них є навіть шанс мати те саме на наступний день. Якщо відбувається зміна від снігу або дощу, лише половина часу - це зміна до приємного дня. За допомогою цієї інформації формуємо марковський ланцюжок наступним чином. Візьмемо як стани види погоди R, N і S. З наведеної вище інформації визначаємо ймовірності переходу. Вони найзручніше представлені в квадратному масиві як $$\mat {P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox {R} & \mbox {N} & \mbox {S} \cr \mbox {R} & 1/2 & 1/4 & 1/4 \cr \mbox {N} & 1/2 & 0 & 1/2 \cr \mbox {S} & 1/4 & 1/4 & 1/2\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

Матриця переходу

Записи в першому рядку матриці$\mat {P}$ в прикладі [іспиту 11.1.1] представляють ймовірності для різних видів погоди після дощового дня. Аналогічно, записи у другому та третьому рядах представляють ймовірності для різних видів погоди після приємних та сніжних днів відповідно. Такий квадратний масив називається, або.

Розглянуто питання визначення ймовірності того, що, враховуючи, що ланцюг знаходиться в стані$i$ сьогодні, він буде в стані через$j$ два дні. Позначимо цю ймовірність по$p_{ij}^{(2)}$. У прикладі [іспиту 11.1.1] ми бачимо, що якщо сьогодні дощовий, то подія, що сніжна через два дні - це неспільний союз наступних трьох подій: 1) завтра дощовий і сніжний два дні відтепер, 2) добре завтра і сніжно через два дні, і 3) сніжно завтра і сніжно два дні відтепер. Імовірність першого з цих подій є добутком умовної ймовірності того, що завтра дощовий, враховуючи, що сьогодні дощовий, і умовної ймовірності того, що через два дні сніг, враховуючи, що завтра дощовий. Використовуючи матрицю переходу$\mat{P}$, ми можемо записати цей твір як$p_{11}p_{13}$. Інші дві події також мають ймовірності, які можуть бути записані як продукти записів$\mat{P}$. Таким чином, у нас є $$p_{13}^{(2)} = p_{11}p_{13} + p_{12}p_{23} + p_{13}p_{33}\ .$$ Це рівняння має нагадувати читачеві точковий добуток двох векторів; ми розставляємо перший рядок$\mat {P}$ з третім стовпцем$\mat {P}$. Це якраз те, що робиться в отриманні$1,3$ -запис продукту$\mat {P}$ з собою. Взагалі, якщо ланцюг Маркова має$r$ стани, то $$p_{ij}^{(2)} = \sum_{k = 1}^r p_{ik}p_{kj}\ .$$ наступну загальну теорему легко довести за допомогою наведеного вище спостереження і індукції.

[thm 11.1.1]$\mat {P}$ Нехай матриця переходу ланцюга Маркова. $ij$-й запис$p_{ij}^{(n)}$ матриці$\mat {P}^n$ дає ймовірність того, що ланцюжок Маркова, починаючи в стані$s_i$, буде перебувати в стані$s_j$ після$n$ кроків. Доказ цієї теореми залишається як вправа (Вправа [exer 11.1.18]).

[іспит 11.1.1.5] (Приклад [іспит 11.1.1] продовження) Подумайте ще раз про погоду в Країні Оз Ми знаємо, що повноваження матриці переходу дають нам цікаву інформацію про процес, коли він розвивається. Нас буде особливо цікавити стан ланцюга після великої кількості кроків. Програма MatrixPowers обчислює повноваження$\mat{P}$.

Ми запустили програму MatrixPowers для прикладу Країни Оз, щоб обчислити послідовні сили$\mat{P}$ від 1 до 6. Результати наведені в таблиці [табл. 11.1]. Відзначимо, що через шість днів наші прогнози погоди, до тридесяткової точності, незалежні від сьогоднішньої погоди. Імовірності для трьох типів погоди, R, N та S, становлять .4, .2 та .4 незалежно від того, де почався ланцюг. Це приклад типу ланцюга Маркова під назвою ланцюг Маркова. Для цього типу ланцюга вірно, що далекі прогнози не залежать від початкового стану. Не всі ланцюги регулярні, але це важливий клас ланцюгів, який ми детально вивчимо пізніше.

$$\mat{P}^1 = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{Rain}&\mbox{Nice}&\mbox{Snow} \cr \mbox{Rain} & .500 & .250 & .250 \cr \mbox{Nice} & .500 & .000 & .500 \cr \mbox{Snow} & .250 & .250 & .500 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup$$ $$\mat {P}^2 = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{Rain}&\mbox{Nice}&\mbox{Snow} \cr \mbox{Rain} & .438 & .188 & .375 \cr \mbox{Nice} & .375 & .250 & .375 \cr \mbox{Snow} & .375 & .188 & .438 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup$$ $$\mat {P}^3 = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{ Rain}&\mbox{Nice} &\mbox{Snow} \cr \mbox{Rain} & .406 & .203 & .391 \cr \mbox{Nice} & .406 & .188 & .406 \cr \mbox{Snow} & .391 & .203 & .406 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup$$ $$\mat {P}^4 = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{Rain}&\mbox{Nice}&\mbox{Snow} \cr \mbox{Rain} & .402 & .199 & .398 \cr \mbox{Nice} & .398 & .203 & .398 \cr \mbox{Snow} & .398 & .199 & .402 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup$$ $$\mat {P}^5 = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{Rain}&\mbox{Nice}&\mbox{Snow} \cr \mbox{Rain} & .400 & .200 & .399 \cr \mbox{Nice} & .400 & .199 & .400 \cr \mbox{Snow} & .399 & .200 & .400 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup$$ $$\mat {P}^6 = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{Rain}&\mbox{Nice}&\mbox{Snow} \cr \mbox{Rain} & .400 & .200 & .400 \cr \mbox{Nice} & .400 & .200 & .400 \cr \mbox{Snow} & .400 & .200 & .400 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup$$

Розглянемо довгострокову поведінку ланцюга Маркова, коли вона починається в стані, обраному розподілом ймовірностей на множині станів, які ми будемо називати a. Вектор ймовірності з$r$ компонентами - це вектор-рядок, записи якого невід'ємні і сумуються до 1. Якщо$\mat {u}$ є вектором ймовірності, який представляє початковий стан ланцюга Маркова, то ми думаємо про$i$ ту складову$\mat {u}$ як що представляє ймовірність того, що ланцюг починається в стані$s_i$.

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

[thm 11.1.2]$\mat{P}$ Дозволяти матриця переходу ланцюга Маркова, а$\mat {u}$ нехай вектор ймовірності, який представляє початковий розподіл. Тоді ймовірність того, що ланцюг знаходиться в стані$s_i$ після$n$ кроків - це запис у $$\mat{u}^{(n)} = \mat{u}{\mat{P}^n}\ .$$ векторі Доказ цієї теореми залишають як вправу (Вправа [exer 11.1.19]).$i$

Зауважимо, що якщо ми хочемо вивчити поведінку ланцюга за припущенням, що вона починається в певному стані$s_i$, ми просто$\mat {u}$ вибираємо вектор ймовірності з$i$ тим записом, рівним 1, а всі інші записи дорівнюють 0.

[іспит 11.1.1.6] У прикладі Землі Оз (Приклад [іспит 11.1.1]) Нехай початковий вектор ймовірності$\mat {u}$ дорівнює$(1/3, 1/3, 1/3)$. Потім ми можемо обчислити розподіл станів через три дні, використовуючи теорему [thm 11.1.2] і наш попередній розрахунок${\mat {P}^3}$. Отримуємо $$\begin{aligned} {\mat {u}}^{(3)} = {\mat {u}}{\mat {P}^3} &=& \pmatrix{ 1/3,& 1/3,& 1/3} \pmatrix{ .406 & .203 & .391 \cr .406 & .188 & .406 \cr .391 & .203 & .406 } \cr && \cr &=& \pmatrix{ .401,& .198,& .401} \ .\end{aligned}$$

Приклади

Наступні приклади ланцюгів Маркова будуть використані протягом усього розділу для вправ.

[іспит 11.1.2] Президент Сполучених Штатів повідомляє людині А його намір балотуватися чи не балотуватися на наступних виборах. Потім A передає новини B, який, в свою чергу, передає повідомлення на C, і так далі, завжди якоїсь нової людини. Ми припускаємо, що існує ймовірність$a$ того, що людина змінить відповідь «так» на «ні» при передачі її наступній людині, і ймовірність$b$ того, що він чи вона змінить її з «ні» на «так». Ми вибираємо, як стверджує повідомлення, або так, або ні. Матриця переходу - це $$\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{yes} & \mbox{no} \cr \mbox{yes} & 1 - a & a \cr \mbox{no} & b & 1 - b\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$ Початкова держава представляє вибір президента.

[іспит 11.1.3] Кожен раз, коли певна кінь біжить в гонці з трьома кіньми, він має ймовірність 1/2 перемоги, 1/4 приходу в другому, і 1/4 приходу в третій, незалежно від результату будь-якої попередньої гонки. У нас є самостійний процес випробувань, але його можна розглядати і з точки зору марковської ланцюгової теорії. Матриця переходу $$\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{W} & \mbox{P} & \mbox{S} \cr \mbox{W} & .5 & .25 & .25 \cr \mbox{P} & .5 & .25 & .25 \cr \mbox{S} & .5 & .25 & .25\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

-3пт

[іспит 11.1.4] У темні віки Гарвард, Дартмут і Єльський прийняті тільки студенти чоловічої статі. Припустимо, що в той час 80 відсотків синів Гарвардських чоловіків пішли до Гарварду, а решта - до Єльського університету, 40 відсотків синів єльських чоловіків пішли до Єльського університету, а решта рівномірно розділилася між Гарвардом і Дартмутом; а з синів дартмутських чоловіків 70 відсотків поїхали до Дартмута, 20 відсотків - до Гарварду та 10 відсотків до Єльського університету. Формуємо ланцюжок Маркова з перехідною матрицею $$\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{H} & \mbox{Y} & \mbox{D} \cr \mbox{H} & .8 & .2 & 0 \cr \mbox{Y} & .3 & .4 & .3 \cr \mbox{D} & .2 & .1 & .7\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

-3пт

[іспит 11.1.5] Змінити приклад [іспит 11.1.4], припускаючи, що син Гарвардської людини завжди пішов до Гарварду. Матриця переходу тепер $$\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{H} & \mbox{Y} & \mbox{D} \cr \mbox{H} & 1 & 0 & 0 \cr \mbox{Y} & .3 & .4 & .3 \cr \mbox{D} & .2 & .1 & .7\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

-3пт

[іспит 11.1.6] (Модель Ehrenfest) Нижче наведено окремий випадок моделі, яка називається модель Ehrenfest, ³, яка була використана для пояснення дифузії газів. Загальна модель буде детально розглянута в розділі 1.5. У нас є дві урни, які між ними містять чотири кулі. На кожному кроці один з чотирьох куль вибирається навмання і переміщується з урни, в якій він знаходиться, в іншу урну. Вибираємо, як станів, кількість кульок в першій урні. Потім матриця переходу $$\mat {P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 1 & 2 & 3 & 4 \cr 0 & 0 & 1 & 0 & 0 & 0 \cr 1 & 1/4 & 0 & 3/4 & 0 & 0 \cr 2 & 0 & 1/2 & 0 & 1/2 & 0 \cr 3 & 0 & 0 & 3/4 & 0 & 1/4 \cr 4 & 0 & 0 & 0 & 1 & 0 \cr\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

[іспит 11.1.7] (Gene Model) Найпростіший тип успадкування ознак у тварин відбувається, коли риса регулюється парою генів, кожен з яких може бути двох типів, скажімо G і g Індивід може мати комбінацію GG або Gg (яка генетично така ж, як gG) або gg. Дуже часто типи GG і Gg не відрізняються за зовнішнім виглядом, і тоді ми говоримо, що ген G домінує в гені g. Особа називається, якщо у неї є гени GG, якщо він або вона має gg, і з Gg сумішшю.

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

При спарюванні домінантного і гібридного тварини кожне потомство повинно отримати ген G від першого і мати рівні шанси на отримання G або g від останнього. Звідси є однакова ймовірність отримання домінуючого або гібридного потомства. Знову ж таки, в спарюванні рецесиву і гібрида є навіть шанс отримати або рецесив, або гібрид. У спарюванні двох гібридів потомство має рівні шанси отримати G або g від кожного з батьків. Звідси ймовірності становлять 1/4 для GG, 1/2 для Gg і 1/4 для gg.

Розглянемо процес продовження в'язки. Починаємо з індивіда відомого генетичного характеру і спаровуємо його з гібридом. Припускаємо, що є хоча б одне потомство. Потомство вибирається навмання і спаровується з гібридом, і цей процес повторюється через ряд поколінь. Генетичний тип обраного потомства в наступних поколіннях може бути представлений марковської ланцюгом. Стани є домінуючими, гібридними та рецесивними, і позначаються відповідно GG, Gg та gg.

Ймовірності переходу є $$\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{GG} & \mbox{Gg} & \mbox{gg} \cr \mbox{GG} & .5 & .5 & 0 \cr \mbox{Gg} & .25 & .5 & .25 \cr \mbox{gg} & 0 & .5 & .5 \crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

[іспит 11.1.8] Змініть приклад [іспит 11.1.7] наступним чином: Замість того, щоб спаровувати найстаріше потомство з гібридом, ми спаровуємо його з домінуючою особиною. Матриця переходу $$\mat{P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{GG} & \mbox{Gg} &\mbox{gg} \cr \mbox{GG} & 1 & 0 & 0 \cr \mbox{Gg} & .5 & .5 & 0 \cr \mbox{gg} & 0 & 1 & 0\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

[іспит 11.1.9] Ми починаємо з двох тварин протилежної статі, спаровуємо їх, вибираємо двох своїх нащадків протилежної статі, і спаровуємо їх тощо. Для спрощення прикладу будемо вважати, що розглянута риса не залежить від статі.

Тут стан визначається парою тварин. Отже, станами нашого процесу будуть:$s_1 = (\mbox{GG},\mbox{GG})$,$s_2 = (\mbox{GG},\mbox{Gg})$,$s_3 = (\mbox{GG},\mbox{gg})$,$s_4 = (\mbox{Gg},\mbox{Gg})$$s_5 = (\mbox{Gg},\mbox{gg})$, і$s_6 = (\mbox{gg},\mbox{gg})$.

Проілюструється розрахунок ймовірностей переходу в розрізі стану$s_2$. Коли процес знаходиться в такому стані, у одного з батьків є гени GG, у іншого Gg. Значить, ймовірність домінуючого потомства становить 1/2. Тоді ймовірність переходу до$s_1$ (виділення двох домінант) дорівнює 1/4, переходу до$s_2$ дорівнює 1/2, а до$s_4$ дорівнює 1/4. Решта стани трактуються аналогічно. Матриця переходу цього ланцюга:

$${\mat{P}^1} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% &\mbox{GG,GG}&\mbox{GG,Gg}&\mbox{GG,gg}&\mbox{Gg,Gg}&\mbox{Gg,gg}&\mbox{gg,gg}\cr \mbox{GG,GG} & 1.000 & .000 & .000 & .000 & .000 & .000\cr \mbox{GG,Gg} & .250 & .500 & .000 & .250 & .000 & .000\cr \mbox{GG,gg} & .000 & .000 & .000 & 1.000 & .000 & .000\cr \mbox{Gg,Gg} & .062 & .250 & .125 & .250 & .250 & .062\cr \mbox{Gg,gg} & .000 & .000 & .000 & .250 & .500 & .250\cr \mbox{gg,gg} & .000 & .000 & .000 & .000 & .000 & 1.000\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .$$

[іспит 11.1.10] (Модель Stepping Stone) Наш остаточний приклад - ще один приклад, який був використаний у вивченні генетики. Називається вона моделлю. ⁴ У цій моделі ми маємо$n$ -by-$n$ масив квадратів, і кожен квадрат спочатку будь-який з$k$ різних кольорів. Для кожного кроку навмання вибирається квадрат. Потім цей квадрат вибирає одного з восьми сусідів навмання і приймає колір цього сусіда. Щоб уникнути граничних проблем, ми припускаємо, що якщо квадрат$S$ знаходиться на лівій межі, скажімо, але не на куті, він примикає до квадрата$T$ на правій межі в тому ж ряду$S$,$S$ що і також примикає до квадратів трохи вище і знизу$T$. Аналогічне припущення робиться і щодо квадратів на верхній і нижній кордоні. Верхній лівий кутовий квадрат примикає до трьох очевидних сусідів, а саме квадратів під ним, праворуч і по діагоналі внизу і праворуч. Він має п'ять інших сусідів, які такі: інші три кутові квадрати, квадрат нижче верхнього правого кута і квадрат праворуч від нижнього лівого кута. Інші три кути також мають, аналогічним чином, вісім сусідів. (Ці суміжні набагато легше зрозуміти, якщо уявити, як зробити масив у циліндр, склеюючи верхній і нижній край разом, а потім перетворюючи циліндр в пончик, склеюючи дві кругові межі разом.) При цих суміжностях кожен квадрат в масиві прилягає рівно до восьми інших квадратів.

Держава в цьому марковському ланцюжку - опис кольору кожного квадрата. Для цього марковського ланцюжка кількість станів дорівнює$k^{n^2}$, яке навіть для невеликого масиву квадратів величезне. Це приклад ланцюга Маркова, який легко моделювати, але важко аналізувати з точки зору матриці переходу. Програма SteppingStone імітує цей ланцюжок. Ми почали з випадкової початкової конфігурації двох кольорів з$n = 20$ і показуємо результат після того, як процес пропрацював деякий час на малюнку [рис. 11.2].

Це приклад марковського ланцюга. Цей тип ланцюга буде вивчений в розділі 1.2. Одна з теорем, доведених в тому розділі, застосована до цього прикладу, має на увазі, що з ймовірністю 1 камені в кінцевому підсумку будуть все одного кольору. Спостерігаючи за запуском програми, ви можете побачити, що території встановлені і розвивається битва, щоб побачити, який колір вижив. У будь-який момент ймовірність того, що той чи інший колір виграє, дорівнює частці масиву цього кольору. Вас просять довести це у Вправі [сек 11.2]. [Експер 11.2.31].

i [exer 11.1.1] Йде дощ в Країні Оз. визначити дерево і дерево міра для наступних трьох днів 'погода. Знайдіть$\mat {w}^{(1)}, \mat {w}^{(2)},$$\mat {w}^{(3)}$ і порівняйте з результатами, отриманими з$\mat {P},~\mat {P}^2,$ і$\mat {P}^3$.

i [exer 11.1.2] У прикладі [іспит 11.1.2], нехай$a = 0$ і$b = 1/2$. Знайти$\mat {P},~ \mat {P}^2,$ і$\mat {P}^3.$ Що було$\mat {P}^n$ б? Що відбувається,$\mat {P}^n$ як$n$ прагне до нескінченності? Інтерпретуйте цей результат.

i [exer 11.1.3] У прикладі [іспит 11.1.3], знайти$\mat{P}$,$\mat {P}^2,$ і$\mat {P}^3.$ Що таке$\mat {P}^n$?

i [exer 11.1.4] Наприклад [іспит 11.1.4], знайти ймовірність того, що онук людини з Гарварду пішов до Гарварду.

i [exer 11.1.5] У прикладі [іспит 11.1.5], знайти ймовірність того, що онук людини з Гарварду пішов до Гарварду.

i [exer 11.1.6] У прикладі [іспит 11.1.7], припустимо, що ми починаємо з гібрида, виведеного до гібриду. Знайти$\mat {u}^{(1)},$$\mat {u}^{(2)},$ і$\mat {u}^{(3)}.$ Що було$\mat {u}^{(n)}$ б?

i [exer 11.1.7] Знайти матриці$\mat{ P}^2,~\mat {P}^3,~\mat {P}^4,$ і$\mat {P}^n$ для ланцюга Маркова визначається матрицею переходу$\mat {P} = \pmatrix{ 1 & 0 \cr 0 & 1 \cr}$. Те ж саме виконайте для матриці переходу$\mat {P} = \pmatrix{ 0 & 1 \cr 1 & 0 \cr}$. Інтерпретуйте, що відбувається в кожному з цих процесів.

i [exer 11.1.8] Певна обчислювальна машина використовує лише цифри 0 та 1. Передбачається передача однієї з цих цифр через кілька етапів. Однак на кожному етапі існує ймовірність$p$ того, що цифра, яка входить в цей етап, буде змінена, коли вона вийде, і ймовірність$q = 1 - p$ того, що вона не стане.Сформуйте ланцюжок Маркова для представлення процесу передачі, взявши за стан цифри 0 і 1. Що таке матриця ймовірностей переходу?

i [exer 11.1.9] Для ланцюга Маркова у Вправі [exer 11.1.8] намалюйте дерево та призначте деревоподібну міру, припускаючи, що процес починається у стані 0 і рухається через два етапи передачі. Яка ймовірність того, що автомат після двох етапів видає цифру 0 (тобто правильну цифру)? Яка ймовірність того, що автомат ніколи не змінював цифру з 0? Тепер давайте$p = .1$. Використовуючи програму MatrixPowers, обчислити 100-ту потужність матриці переходу. Інтерпретувати записи цієї матриці. Повторіть це з$p = .2$. Чому 100-ті сили здаються однаковими?

i [exer 11.1.10] Змініть програму MatrixPowers так, щоб вона друкувала середнє$\mat {A}_n$ значення повноважень$\mat {P}^n$,$n = 1$ для$N$. Спробуйте свою програму на прикладі Країни Оз і порівняйте$\mat {A}_n$ і$\mat {P}^n.$

i [exer 11.1.11] Припустимо, що професія чоловіка може бути класифікована як професійна, кваліфікований робітник, або некваліфікований робітник. Припустимо, що з синів професійних чоловіків 80 відсотків є професійними, 10 відсотків - кваліфікованими працівниками, а 10 відсотків - некваліфікованими працівниками. Що стосується синів кваліфікованих робітників, то 60 відсотків - кваліфіковані робітники, 20 відсотків - професіонали, а 20 відсотків - некваліфіковані. Нарешті, у випадку некваліфікованих робітників 50 відсотків синів є некваліфікованими працівниками, і 25 відсотків кожен з них відноситься до двох інших категорій. Припустимо, що у кожного чоловіка є хоча б один син, і сформуйте марковський ланцюжок, слідуючи професії випадково обраного сина даної сім'ї через кілька поколінь. Налаштуйте матрицю ймовірностей переходу. Знайдіть ймовірність того, що випадково обраний онук некваліфікованого робітника - професійна людина.

i [exer 11.1.12] У Вправи [exer 11.1.11], ми припустили, що кожна людина має сина. Припустимо замість цього, що ймовірність того, що чоловік має хоча б одного сина, дорівнює 8. Сформуйте ланцюжок Маркова з чотирма станами. Якщо у чоловіка є син, ймовірність того, що цей син знаходиться в тій чи іншій професії, така ж, як у Вправи [exer 11.1.11]. Якщо немає сина, процес переходить до штату чотири, які представляють сім'ї, чоловіча лінія яких вимерла. Знайдіть матрицю ймовірностей переходу і знайдіть ймовірність того, що випадково обраний онук некваліфікованого робітника - професійна людина.

i [exer 11.1.14] Написати програму для обчислення$\mat {u}^{(n)}$ заданого$\mat {u}$ і$\mat{P}$. Використовуйте цю програму для обчислення$\mat {u}^{(10)}$ для прикладу Країни Оз$\mat {u} = (0, 1, 0)$, з і з$\mat {u} = (1/3, 1/3, 1/3)$.

i [exer 11.1.15] Використовуючи програму MatrixPowers,$\mat {P}^1$ знайдіть$\mat {P}^6$ приклади [іспит 11.1.7] та [іспит 11.1.8]. Подивіться, чи можете ви передбачити далеку ймовірність знаходження процесу в кожному з станів для цих прикладів.

i [exer 11.1.16] Напишіть програму для моделювання результатів ланцюга Маркова після$n$ кроків, враховуючи початковий початковий стан і матрицю переходу$\mat{P}$ як дані (див. Приклад [іспиту 11.1.10]). Зберігайте цю програму для використання в подальших проблемах.

i [exer 11.1.17] Змініть програму вправ [exer 11.1.16] так, щоб вона відстежувала частку разів у кожному стані$n$ по кроках. Запустіть змінену програму для різних початкових станів, наприклад [іспит 11.1.1] та приклад [іспит 11.1.6]. Чи впливає початковий стан на частку часу, проведеного в кожному з штатів, якщо$n$ він великий?

i [exer 11.1.18] Доведено теорему [thm 11.1.1].

i [exer 11.1.19] Доведено теорему [thm 11.1.2].

i [exer 11.1.20] Розглянемо наступний процес. У нас є дві монети, одна з яких справедлива, а інша з яких має голови з обох сторін. Ці дві монети ми віддаємо нашому другові, який вибирає одну з них навмання (кожна з ймовірністю 1/2). Під час решти процесу вона використовує тільки ту монету, яку вибрала. Зараз вона приступає до багаторазового підкидання монети, повідомляючи про результати. Ми вважаємо, що цей процес складається виключно з того, що вона нам повідомляє.

1. З огляду на, що вона повідомляє головою$n$ на кидку, яка ймовірність того, що на$(n+1)$ кидок кинули голову?
2. Розглянемо цей процес як наявність двох станів, орел і решка. Обчисливши інші три ймовірності переходу, аналогічні тій, що є частиною (а), запишіть «матрицю переходу» для цього процесу.
3. Тепер припустимо, що процес знаходиться в державних «головах» як на$(n-1)$ 1-му, так і$n$ на кидку. Знайдіть ймовірність того, що голова підніметься на$(n+1)$ кидку.
4. Чи є цей процес ланцюгом Маркова?