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

4.2.1. Означення марковського процесу з дискретними станами. Граф станів.

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

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

При вивченні випадкових процесів, які відбуваються в системах з дискретними станами, важливу роль відіграють ймовірності станів. Позначимо через стан системи в момент часу t. Ймовірністю i-го стану в момент t називається ймовірність події, яка полягає в тому, що в момент t система S буде знаходитися в стані . Позначимо цю ймовірність через :

. (4.46)

Оскільки для будь-якого t випадкові події попарно несумісні та утворюють повну группу, то сума ймовірностей цих подій для кожного t дорівнює одиниці:

. (4.47)

Означення. Випадковий процес, який відбувається в деякій системі S з дискретними станами, називається марковським (або процесом без післядії), якщо він має таку властивість: для будь-якого моменту часу ймовірність будь-якого стану системи в майбутньому (при ) залежить від її стану в теперішньому (при ) і не залежить від того як і скільки часу розвивався цей процес в минулому (при ).

Властивість відсутності післядії називають також властивістю відсутності пам’яті, а марковські процеси – процеси без пам’яті.

Граф станів. Марковські процеси з дискретними станами зручно ілюструвати за допомогою так званого графу станів (рис.4.3), де прямокутниками позначені стани системи, а стрілками – можливі переходи із стану в стан. На графі відзначаються тільки безпосередні переходи, а не переходи через інші стани. Іноді на графі відзначають не тільки можливі переходи із стану в стан, але і можливі затримки в попередньому стані; це зображається стрілкою (“петлею”), направленою з даного стану в цей самий стан (рис.4.3.).

Отже, на рис.4.3 зображений граф системи S з шістьма станами, з можливими безпосередніми переходами , , , , , , , . Що стосується, наприклад, переходу із стану в , то він можливий через стан і тому є опосередкованим; безпосередній ж перехід неможливий, оскільки на графі відсутня відповідна стрілка.

4.2.2. Ланцюги Маркова та їх основні

характеристики.

Марковський випадковий процес з дискретними станами та дискретним часом називається ланцюгом Маркова.

Як уже відзначалося в п. 4.1.1., для такого процесу моменти часу коли система S може змінювати свій стан, розглядають як послідовні кроки процесу, а в якості аргумента, від якого залежить процес, виступає не час t , а номер кроку 1, 2, …, k, … . Випадковий процес у цьому випадку характеризується послідовністю станів де – початковий стан системи (перед першим кроком), - стан системи після першого кроку, - стан системи після k -го кроку, … .

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

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

Очевидно, що реалізацію дискретного випадкового процесу з дискретним часом за будь-який (скінчений) проміжок часу можна представити невипадковою скінченною послідовністю (за індексом k) розглядуваних подій (i=1, …, n ; k= 0, 1, 2, …). Наприклад, припустимо, що граф станів системи S, в якій відбувається випадковий процес з дискретним часом, має вигляд, зображений на рис. 4.3. Спостереження за системою показало, що в початковий момент k = 0 система знаходилася в стані ; в момент першого кроку перейшла з нього стрибком у стан , з якого на другому кроці перейшла в , на третьому кроці перейшла в , на четвертому кроці перейшла в , після п’ятого кроку знаходилася в стані . Тоді реалізація випадкового процесу блукання по станах має такий вигляд: , , , , , .

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

Враховуючи дане зауваження, більш змістовне означення ланцюга Маркова можна сформулювати так.

Означення. Послідовність випадкових величин , k=0,1,2,…, називається ланцюгом Маркова з множиною станів , якщо

і для будь-яких , будь-яких та будь-яких підмножин множини E виконується рівність

. (4.48)

Властивість (4.48) означає, що при фіксованому значенні системи в даний момент часу l поведінка системи в майбутньому (k > l) не залежить від поведінки системи в минулому , або більш коротко: при фіксованому теперішньому майбутнє не залежить від минулого. Властивість (4.48) називають марковською властивістю.

Надалі ми будемо використовувати обидві термінології щодо інтерпретації ланцюга Маркова.

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

Означення. Ймовірністю переходу (перехідною ймовірністю) на k–му кроці із стану в стан називається умовна ймовірність того, що система S після k–го кроку виявиться в стані за умови, що безпосередньо перед цим (після -го кроку) вона знаходилася в стані :

, . (4.49)

Якщо множину станів позначити через то можна трактувати як ймовірність того, що ланцюг Маркова, знаходячись після -го кроку в стані i , після наступного k-го кроку виявиться в стані j :

, . (4.50)

У випадку, коли , то перехідна ймовірність називається ймовірністю затримки системи S у стані . Якщо на k-му кроці безпосередній перехід системи із стану в інший стан ( ) неможливий або неможливою є затримка ( ) в стані , то .

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

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

, (4.51)

вона називається однорідною матрицею переходів (перехідних ймовірностей). За означенням всі елементи матриці P невід’ємні. Крім цього, оскільки для будь-якої події , яка наступила після –го кроку, для наступного k–го кроку одна з подій обов’язково відбудеться, то елементи кожного рядка матриці P задовольняють умову

(4.52)

Означення. Квадратна матриця називається стохастичною, якщо її елементи невід’ємні і сума елементів будь-якого її рядка дорівнює одиниці.

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

Часто також задаються ймовірності станів ланцюга Маркова на початковому нульовому кроці:

або . (4.53)

На ймовірності накладаються очевидні умови невід’ємності і нормування:

. (4.54)

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

За допомогою формул (4.48), (4.50) із врахуванням (4.53) можна обчислити ймовірність будь-якої конкретної траєкторії ланцюга Маркова:

(4.55)

Легко показати, що формула (4.55) задає ймовірності на просторі всіх траєкторій довжини . Зокрема, виконується умова нормування для ймовірностей:

. (4.56)

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

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

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

, . (4.57)

Внаслідок цього стрілки – петлі та відповідні їм ймовірності затримок на графі, як правило, не відзначаються.

Приклад 4.7. Послідовність незалежних випробувань за схемою Бернуллі (див.1.3). Схему Бернуллі можна розглядати як частковий випадок ланцюга Маркова з двома станами: - наслідком окремого випробування є подія А і - наслідком окремого випробування є подія , в якому початковий розподіл ймовірностей (4.53) задається вектором , а матриця перехідних ймовірностей (4.51) має вигляд

.

Відповідний граф зображений на рис.4.5.

Рис.4.5. Послідовність незалежних випробувань за схемою Бернуллі.

Приклад 4.8. Задача про розорення гравця: випадкове блукання з поглинанням.

Нехай частинка може пересуватися вздовж прямої під дією випадкових поштовхів. Потрапивши в стан або , частинка залишається там назавжди. У всіх її інших станах вона під дією випадкового поштовху переходить на одиницю довжини вправо з ймовірністю p , вліво з ймовірністю . Отже, ми маємо ланцюг Маркова з можливими станами, а саме: . Перехідні ймовірності в цьому випадку дорівнюють: для , ; для , ; , для для . Матриця перехідних ймовірностей має вигляд

,

а граф переходів між станами зображений на рис. 4.6.

Рис.4.6. Випадкове блукання по цілочисельних точках відрізка з поглинаючими межами (екранами).

Часто використовується наступна інтерпретація цієї моделі. Два гравці розігрують декілька партій, кожна з яких завершується виграшем одного та програшем другого гравця. Гравець, який програв, виплачує партнеру одну грошову одиницю. Нехай початковий капітал першого гравця становить грошових одиниць, а другого гравця одиниць. Ймовірність виграшу першого гравця дорівнює , а другого . Гра закінчується, як тільки один з гравців залишиться без грошей. У даному випадку розиграш однієї партії відповідає одному кроку ланцюга Маркова, стан ланцюга - це кількість грошей першого гравця після партій. Початковий стан ланцюга . Інтерес представляють ймовірності виграшу першого та другого гравців.

Вище ми з’ясували, що при заданні ланцюга Маркова визначаються вектор початкового розподілу та матриця перехідних ймовірностей за один крок. Ці поняття відносяться до вихідних характеристик ланцюга Маркова.

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

Ймовірність переходу за k кроків. Розглянемо ймовірність переходу із стану , який реалізований, наприклад, після го кроку, в стан за кроків, тобто в стан після го кроку. Зрозуміло, що внаслідок однорідності ланцюга Маркова ця ймовірність залежить тільки від ( і не залежить від ). Позначимо її : . Тоді ймовірність переходу за кроків із стану в стан та - ймовірність переходу за кроків із стану в .

Використовуючи формулу повної ймовірності (1.24) та враховуючи, що проміжні стани на - у кроці утворюють повну групу попарно несумісних подій, знайдемо

, (4.58)

де - будь-яке ціле значення від 1 до

Позначимо через матрицю, яка складається з ймовірностей , отже - матриця переходів через кроків . Враховуючи формулу для перемноження квадратних матриць, рівність (4.58) можна записати в матричному вигляді:

, . (4.59)

Застосовуючи послідовно (4.59), одержимо

, (4.60)

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

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

Безумовна (абсолютна) ймовірність того, що система після го кроку знаходиться в стані , обчислюється також з використанням формули повної ймовірності:

, (4.61)

Простим наслідком формули (4.61) є наступне співвідношення

, . (4.62)

Рекурентні формули (4.61), (4.62) можна записати також у матричному вигляді. Справді, якщо абсолютні ймовірності станів визначені у векторній формі як , то на підставі рівностей (4.59) – (4.62) маємо

, . (4.63)

або

, (4.64)

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

.

Спираючись на формулу повної ймовірності, можуть бути обчислені через ймовірності внаслідок рекурентного застосування наступних формул:

, . (4.65)

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

• ймовірність того, що, починаючи зі стану , система коли-небудь потрапить в стан :

(4.66)

• середнє число кроків до першого досягнення стану при виході зі стану :

(4.67)

Приклад 4.9. Розглянемо стан банку, що характеризується однією з процентних ставок: 2 %, 3 %, 4 %, які встановлюються на початку кожного кварталу і є незмінними до його закінчення. Отже, якщо за систему S прийняти розглядуваний банк, то вона в кожний момент часу може знаходитися тільки в одному з трьох наступних станів: - процентна ставка 2 %, - процентна ставка 3 %, - процентна ставка 4 %. Аналіз роботи банку в попередні роки показав, що зміна перехідних ймовірностей з плином часу є незначною.

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

Рис. 4.7. Розмічений граф станів банку.

Розв’язання. Оскільки множина станів, у яких може знаходитися система S, скінченна (три стани), то випадковий процес, який відбувається в системі S – дискретний.

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

Внаслідок умов, прийнятих у прикладі, банк може переходити зі стану в стан тільки в наперед визначені моменти часу: - початок k–го кварталу, Отже, випадковий процес у системі S є процесом з дискретним часом.

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

Отже, випадковий процес, який відбувається в системі S, є однорідним ланцюгом Маркова.

Використовуючи розмічений граф на рис. 4.7, випишемо значення перехідних ймовірностей: Тоді за формулою (4.57) при Аналогічно, і, отже, . Нарешті, ;

Складемо матрицю перехідних ймовірностей:

.

Звернемо увагу на те, що матриця P– стохастична.

Оскільки в кінці попереднього року процентна ставка складала 3 %, то можна вважати, що в початковий момент система S знаходиться в стані . Тому початковий розподіл має вигляд

(4.68)

Ймовірності станів банку в кінці року, тобто після закінчення четвертого кварталу, можна знайти за формулою (4.64) при і . Для цього обчислимо спочатку

.

Тоді

.

З (4.64) при і з врахуванням (4.68) маємо

Отже, , тобто в кінці року ймовірності процентних ставок 2 %, 3 %, 4 % дорівнюють відповідно 0,2020; 0,4015; 0,3965. Отже, найбільш ймовірно процентна ставка в кінці року залишиться такою самою, якою вона була в кінці попереднього року, тобто 3 %.

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

Зауваження. Для знаходження вектора в прикладі 4.9 можна було б замість формули (4.64) чотири рази послідовно використати формулу (4.63), а саме, спочатку за цією формулою знайти вектор ймовірностей станів у першому кварталі , потім, у другому кварталі і т.д., поки не дійдемо до четвертого кварталу