8.1. Ланцюги Маркова

8.1.1. Означення ланцюга Маркова. Ймовірності переходу. Ланцюги Маркова можна розглядати як важливе узагальнення схеми незалежних випробувань на випадок, коли випробування залежні.

Нехай проводиться послідовність випробувань і в -му випробуванні можуть настати події . Ці події можна розглядати як стан деякої системи в момент часу , при цьому ми будемо вважати, що стан системи в момент часу залежить лише від стану системи у попередній момент часу і не залежить від інших станів системи, тобто ймовірність того, що в -му випробуванні настане подія залежить тільки від того, яка із подій настає в ( )-му випробуванні і не залежить від результатів попередніх випробувань, тобто, . Такі системи називаються марковськими системами або ланцюгами Маркова. Множину всіх станів системи називають фазовим простором ланцюга Маркова.

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

Позначимо через стан системи у момент часу . При цьому – стан системи в момент часу – є випадковою величиною. Система знаходиться в стані означає, що , , . Таким чином, поведінка системи повністю визначається послідовністю випадкових величин . Якщо

,

тоді називають ланцюгом Маркова. Для ланцюга Маркова при відомому стані на наступному кроці система переходить в стан з умовною ймовірністю . Якщо ця ймовірність

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

.

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

Позначимо , , – початковий розподіл ланцюга Маркова. Тоді поведінка системи в момент часу повністю визначається початковим розподілом та ймовірностями переходу :

.

Розглянемо матрицю . Для скінченної кількості станів

.

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

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

Розглянемо приклад блукання по відрізку , де - натуральне. Якщо точка знаходиться в положенні , то з ймовірностями вона може перейти в положення або . При з ймовірностями вона може перейти в положення або залишитись на місці, аналогічно, при з ймовірностями вона може перейти в положення або залишитись на місці. Тоді матриця переходу буде мати вигляд

.

Розглянемо ймовірності . Такі ймовірності називаються ймовірностями переходу із стану в стан за кроків. Тоді . Покажемо, що

. (1)

Для обґрунтування цієї формули позначимо через подію, яка полягає у тому, що система із стану перейде в стан за кроків, тоді ця подія може настати із однією із подій – система із стану перейде в стан за кроків . Тоді за формулою повної ймовірності , де , , , одержуємо .

Позначимо через матрицю ймовірностей переходу за кроків, тобто . Тоді із формули (1) випливає, що для довільного буде справедлива рівність

.

Зокрема, , де – матриця ймовірностей переходу за один крок.

Позначимо – розподіл ланцюга Маркова в момент часу . Тоді

,

тобто, розподіл ланцюга Маркова в момент часу визначається початковим розподілом і ймовірностями переходу за кроків. Дана рівність випливає з формули повної ймовірності.

8.1.2. Класифікація станів однорідного ланцюга Маркова. Кажуть, що стан досягається із стану , якщо існує , що або існують , що , ,…, .

Кажуть, що стан та стан сполучаються, якщо кожен із них досягається із іншого, тобто існують і такі, що і .

Розглянемо довільний стан і позначимо через множину всіх станів, які сполучаються з . Тоді множина всіх станів розбивається на класи без спільних елементів. Тобто для двох станів і класи і або співпадають або не перетинаються. Якщо , то – класи будуть співпадати, якщо ж , то .

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

Розглянемо систему, яка складається із чотирьох станів із матрицею переходу

.

В даному прикладі стани і неістотні, а і є істотними станами, що сполучаються.

Якщо ланцюг Маркова складається лише з одного класу істотних станів, то такий ланцюг Маркова називається незвідним.

Введемо ймовірність того, що система, яка вийшла із стану рівно за кроків вперше повернеться в стан : . не співпадає з .

Ймовірність того, що система, яка вийшла із стану , знову коли-небудь повернеться в нього, дорівнює – ймовірність повернення.

Якщо , то стан називається рекурентним, якщо ж , то стан називається не рекурентним.

Стан називається нульовим, якщо , а в протилежному випадку – ненульовим.

Стан називається періодичним з періодом , якщо повернення в цей стан можливе тільки через число кроків кратне .

Наведемо деякі властивості.

Якщо стан неістотний, то для довільного .

Стан рекурентний тоді і тільки тоді, коли .

Для нерекурентнного стану

.

Нерекурентний стан завжди є нульовим.

Для доведення цього за формулою повної ймовірності маємо

.

Розглянемо твірні функції послідовностей і :

, .

Помножимо рівність для на і додамо одержані рівності по , тоді одержимо

.

Отже, , . Якщо , то при , тому . Отже, . Справедливо і навпаки. Якщо ж , то при одержуємо формулу для .

8.1.3. Ергодична теорема Маркова. Нехай множина станів ланцюга Маркова скінченна.

Теорема. Нехай існує , для якого , . Тоді для довільного існують границі

. (2)

Граничні ймовірності не залежать від початкового стану і є єдиним розв’язком системи

, , . (3)

Доведення. Із (1) одержимо . Звідки, для всіх і , бо . Тому виконується і нерівність

.

Аналогічно, для для всіх і ,

.

Отже, для всіх і

. (4)

Таким чином, при зростанні відрізки є вкладеними. Якщо ми доведемо, що при довжина відрізка

, (5)

то із (4) випливатиме , що має границю і ця границя не залежить від .

Будемо вважати, що . Тоді із (1) при

. (6)

Позначимо через невід’ємні різниці і через – від’ємні різниці у (6). У будь-якому випадку і невід‘ємні. Враховуючи, що , , одержимо: , а це означає, що . Якщо для всіх , то із (6) випливає, що для всіх і , а це означає, що не залежить від і , тому існують границі (2). Якщо ж принаймні при одному , то із умови , , одержимо, що , а тому і . Тоді із рівності (6) одержуємо

.

Тому і . Якщо ми врахуємо, що , то одержимо:

. (7)

До другого множника у правій частині можна знову застосувати цю нерівність. Застосувавши нерівність (7) раз ( – ціла частина ), одержимо:

,

бо , . Отже, (5) виконується, тому виконується і (2).

Враховуючи рівності , , і переходячи в них до границі при , одержимо (3). Теорема доведена.

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

Матриця переходу за два кроки є добуток матриць переходу за один крок:

.

Всі елементи матриці додатні, тому за теоремою існують граничні ймовірності. Для їх знаходження складемо систему (3):

, , , .

Із другого рівняння , а із третього . Підставляючи їх у четверте рівняння, одержимо . Тому , . Отже, граничні ймовірності рівні , , . Відзначимо, що ми зовсім не використовували перше рівняння. В загальному випадку одне із рівнянь системи (3) є наслідком решти.

Вправи.

1. В урні міститься 5 куль, білі і чорні. Випробування полягає у тому, що із урни випадково вибирається одна куля і повертається в урну куля іншого кольору (замість білої – чорна і навпаки). Знайти матрицю ймовірностей переходу ланцюга Маркова за один крок, якщо його станами є кількість білих куль в урні. Знайти ймовірності переходу за два кроки.

2. Задано матрицю переходу системи із стану в стан ( ) за один крок . Знайти матрицю переходу за два кроки. Знайти граничні ймовірності , .