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

Ця стаття носить реферативний характер, написана на основі наведених наприкінці джерел, які подекуди цитуються.

Введення в теорію марківських кіл

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

1. множиною станів S = ( s 1 , …, s n ), подією є перехід з одного стану в інший в результаті випадкового випробування
2. вектором початкових ймовірностей (початковим розподілом) p(0) = (p(0)(1),…, p(0)(n)), що визначає ймовірність p(0)(i) того, що в початковий момент часу t = 0 процес перебував у стані s i
3. матрицею перехідних ймовірностей P = ( p i j ), що характеризує ймовірність переходу процесу з поточним станом s i наступне стан s j , при цьому сума ймовірностей переходів з одного стану дорівнює 1:

∑ j =1… n p i j = 1

Приклад матриці перехідних ймовірностей з безліччю станів S = ( S 1 , …, S 5 ), вектором початкових ймовірностей p (0) = (1, 0, 0, 0, 0):

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

P(n) = p(0) × P n

Вектори p (n) при зростанні n у деяких випадках стабілізуються - сходяться до деякого ймовірнісного вектора ρ, який можна назвати стаціонарним розподілом ланцюга. Стаціонарність проявляється в тому, що взявши p(0) = ρ, ми отримаємо p(n) = ρ для будь-якого n.
Найпростіший критерій, який гарантує збіжність до стаціонарного розподілу, виглядає наступним чином: якщо всі елементи матриці перехідних ймовірностей P позитивні, то при n, що прагне нескінченності, вектор p (n) прагне вектора ρ, що є єдиним рішенням системи виду
p × P = p.
Також можна показати, що якщо при якомусь позитивному значенні n всі елементи матриці P n позитивні, тоді вектор p (n) все одно буде стабілізуватися.
Доказ цих тверджень є у докладному вигляді.

Марківський ланцюг зображується як графа переходів, вершини якого відповідають станам ланцюга, а дуги — переходам з-поміж них. Вага дуги (i, j), що зв'язує вершини s i і s j буде дорівнює ймовірності p i (j) переходу з першого стану до другого. Граф, що відповідає матриці, зображеній вище:

Класифікація станів марківських кіл

При розгляді ланцюгів Маркова нас може цікавити поведінка системи на короткому відрізку часу. У разі абсолютні ймовірності обчислюються з допомогою формул з попереднього розділу. Однак важливіше вивчити поведінку системи на великому інтервалі часу, коли кількість переходів прагне нескінченності. Далі вводяться визначення станів марківських ланцюгів, які необхідні вивчення поведінки системи у довгостроковій перспективі.
Марківські ланцюги класифікуються залежно від можливості переходу з одних станів до інших.
Групи станів марківського ланцюга (підмножини вершин графа переходів), яким відповідають тупикові вершини діаграми порядку графа переходів, називаються ергодичними класами ланцюга. Якщо розглянути граф, зображений вище, то видно, що в ньому 1 ергодичний клас M 1 = ( S 5 ), досяжний з компоненти сильної зв'язності, що відповідає підмножині вершин M 2 = ( S 1 , S 2 , S 3 , S 4 ). Стани, що знаходяться в ергодичних класах, називаються суттєвими, а решта — несуттєвими (хоча такі назви погано узгоджуються зі здоровим глуздом). Поглинаючий стан s i є окремим випадком ергодичного класу. Тоді потрапивши у такий стан, процес припиниться. Для S i буде правильно p ii = 1, тобто. у графі переходів із нього виходитиме лише одне ребро — петля.

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

Наприклад, в алгоритмі Дейкстри є такі стани ланцюга:

• vertex (v), витягання нової вершини з черги з пріоритетами, перехід тільки в стан b ;
• begin (b) початок циклу перебору вихідних дуг для процедури ослаблення;
• analysis (a), аналіз наступної дуги, можливий перехід до a, d, або e;
• decrease (d), зменшення оцінки для деякої вершини графа, перехід до a;
• end(e), завершення роботи циклу, перехід до наступної вершини.

Залишається встановити можливість переходом між вершинами, і можна вивчати тривалості переходів між вершинами, можливості потрапляння в різні стани та інші середні характеристики процесу.

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

Ланцюг Маркова називається непривідним, якщо будь-який стан S j може бути досягнутий з будь-якого іншого стану S i за кінцеве число переходів. В цьому випадку всі стани ланцюга називаються сполученими, а граф переходів є компонентом сильної зв'язності. Процес, що породжується ергодичним ланцюгом, розпочавшись у певному стані, ніколи не завершується, а послідовно переходить з одного стану до іншого, потрапляючи в різні стани з різною частотою, яка залежить від перехідних ймовірностей. Тому основна характеристика ергодичного ланцюга -
ймовірності перебування процесу станах S j , j = 1,…, n , частка часу, яку процес проводить у кожному зі станів. Ненаведені ланцюги використовуються як моделі надійності систем. Дійсно, при відмові ресурсу, який процес використовує дуже часто, працездатність усієї системи опиниться під загрозою. У такому разі дублювання такого критичного ресурсу допоможе уникнути відмов. При цьому стани системи, що відрізняються складом справного і обладнання, що відмовило, трактуються як стану ланцюга, переходи між якими пов'язані з відмовими і відновленням пристроїв і зміною зв'язків між ними, що проводиться для збереження працездатності системи. Оцінки параметрів ланцюга, що не наводиться, дають уявлення про надійність поведінки системи в цілому. Також такі ланцюги можуть бути моделями взаємодії пристроїв із завданнями, що надходять на обробку.

Приклади використання

Система обслуговування із відмовими

Сервер складається з декількох блоків, наприклад, модемів або мережевих карт, до яких надходять запити від користувачів на обслуговування. Якщо всі блоки зайняті, запит втрачається. Якщо один із блоків приймає запит, то він стає зайнятим до кінця його обробки. Як стани візьмемо кількість незайнятих блоків. Час буде дискретним. Позначимо за імовірність надходження запиту. Також ми вважаємо, що час обслуговування є випадковим і що складається з незалежних продовжень, тобто. запит із ймовірністю β обслуговується за один крок, а з ймовірністю (1 – β) обслуговується після цього кроку як новий запит. Це дає можливість (1 - β) β для обслуговування за два кроки, (1 - β) 2 β для обслуговування за три кроки і т.д. Розглянемо приклад із 4 пристроями, що працюють паралельно. Складемо матрицю перехідних ймовірностей для вибраних станів:

Можна помітити, що вона має єдиний ергодичний клас, і, отже, система p × P = p у класі ймовірнісних векторів має єдине рішення. Випишемо рівняння системи, що дозволяє знаходити це рішення:

P 0 (1 - α) + p 1 β = p 0
p 0 α + p 1 (1 - α - β) + p 2 2 β = p 1 ,
p 1 α + p 2 (1 - α - 2 β) + p 3 3 β = p 2 ,
p 2 α + p 3 (1 - α - 3 β) + p 4 4 β = p 3
p 3 α + p 4 (1 - 4 β) = p 4 .

Звідси одержуємо (при γ = α / β):

P 1 = γ p 0 ,
p 2 = γ 2 p 0 /2,
p 3 = γ 3 p 0 /3,
p 4 = γ 4 p 0 /4,

з умови нормування випливає:

P 0 = С = (1 + γ + γ 2 /2 + γ 3 /3 + γ 4 /4) -1 .

Тепер відомий набір ймовірностей π i того, що у стаціонарному режимі в системі буде зайнято i блоків. Тоді частку часу p 4 = З 4 / 4 в системі зайняті всі блоки, система не відповідає на запити. Отримані результати поширюються на кількість блоків. Тепер можна скористатися ними: можна зіставити витрати на додаткові пристрої та скорочення часу повної зайнятості системи.
Докладніше можна ознайомитися з цим прикладом.

Процеси прийняття рішень з кінцевим та нескінченним числом етапів

Розглянемо процес, де є кілька матриць перехідних ймовірностей. Для кожного моменту часу вибір тієї чи іншої матриці залежить від прийнятого рішення. Зрозуміти вищесказане можна на прикладі. Садівник в результаті аналізу ґрунту оцінює його стан одним із трьох чисел: (1) – добрий, (2) – задовільний або (3) – поганий. При цьому садівник зауважив, що продуктивність ґрунту у поточному році залежить лише від його стану у попередньому році. Тому ймовірності переходу ґрунту без зовнішніх впливів з одного стану в інший можна уявити наступним ланцюгом Маркова з матрицею P1:

Тепер можна зіставити кожному переходу з одного стану до іншого деяку функцію доходу, яка визначається як прибуток або збиток за однорічний період. Садівник може вибирати використовувати чи не використовувати добрива, саме від цього залежатиме його кінцевий дохід чи збиток. Введемо матриці R1 і R2, що визначають функції доходу в залежності від витрат на добрива та якості ґрунту:

Нарешті, перед садівником стоїть завдання, яку стратегію потрібно вибрати для максимізації середнього очікуваного доходу. Може розглядатися два типи завдань: з кінцевою та нескінченною кількістю етапів. У разі коли-небудь діяльність садівника обов'язково закінчиться. З іншого боку, візуалізатори вирішують завдання прийняття рішень кінцевого числа етапів. Нехай садівник має намір припинити своє заняття через N років. Наше завдання тепер полягає в тому, щоб визначити оптимальну стратегію поведінки садівника, тобто стратегію, за якої його дохід буде максимальним. Кінцевість числа етапів у нашій задачі проявляється в тому, що садівнику не важливо, що буде з його сільськогосподарським угіддям на N+1 рік (йому важливі усі роки до N включно). Тепер видно, що в цьому випадку завдання пошуку стратегії перетворюється на задачу динамічного програмування. Якщо через f n (i) позначити максимальний середній очікуваний дохід, який можна отримати за етапи від n до N включно, починаючи зі стану з номером i , то нескладно вивести рекурентне співвідношення, що зв'язує f n (i) з числами f n +1 (j)

F n (i) = max k (∑ j = 1 m p ij k [r ij k + f n +1 (j)]), n = 1, 2, …, N

Тут k – номер використовуваної стратегії. Це рівняння ґрунтується на тому, що сумарний дохід r ij k + f n +1 (j) виходить в результаті переходу зі стану i на етапі n стан j на етапі n +1 з ймовірністю p ij k .
Тепер оптимальне рішення можна знайти, послідовно обчислюючи f n (i) в низхідному напрямку (n = N …1). При цьому введення вектора початкових ймовірностей за умови завдання не ускладнить її вирішення.
Цей приклад також розглянуто в .

Моделювання поєднань слів у тексті

Розглянемо текст, що складається зі слів w . Представимо процес, у якому станами є слова, отже коли він перебуває у стані (S i) система перетворюється на стан (s j) відповідно до матриці перехідних ймовірностей. Насамперед треба «навчити» систему: подати на вхід досить великий текст для оцінки перехідних ймовірностей. А потім можна будувати траєкторії марківського кола. Збільшення смислового навантаження тексту, побудованого за допомогою алгоритму ланцюгів Маркова можливе тільки при збільшенні порядку, де станом є не одне слово, а множини з більшою потужністю - пари (u, v), трійки (u, v, w) і т.д. Причому, що в ланцюгах першого, що п'ятого порядку, сенсу буде ще трохи. Сенс почне з'являтися зі збільшенням розмірності порядку як мінімум середньої кількості слів у типовій фразі вихідного тексту. Але таким шляхом рухатися не можна, тому що зростання значеннєвого навантаження тексту в ланцюгах Маркова високих порядків відбувається значно повільніше, ніж падіння унікальності тексту. А текст, побудований на марківських ланцюгах, наприклад, тридцятого порядку, все ще буде не настільки осмисленим, щоб представляти інтерес для людини, але вже досить схожим з оригінальним текстом, до того ж кількість станів у такому ланцюзі буде приголомшливим.
Ця технологія зараз дуже застосовується (на жаль) в Інтернеті для створення контенту веб-сторінок. Люди, які бажають збільшити трафік на свій сайт та підвищити його рейтинг у пошукових системах, прагнуть помістити на свої сторінки якнайбільше ключових слів для пошуку. Але пошукові системи використовують алгоритми, які вміють відрізняти реальний текст від безладного нагромадження ключових слів. Тоді, щоб обдурити пошукові системи використовують тексти, створені генератором на основі марківського ланцюга. Є, звісно, ​​і позитивні приклади використання ланцюгів Маркова до роботи з текстом, їх застосовують щодо авторства, аналізі справжності текстів.

Ланцюги Маркова та лотереї

У деяких випадках імовірнісна модель використовується у прогнозі номерів у різних лотереях. Очевидно, використовувати ланцюги Маркова для моделювання послідовності різних тиражів немає сенсу. Те, що відбувалося з кульками у тиражі, ніяк не вплине на результати наступного тиражу, оскільки після тиражу кулі збирають, а в наступному тиражі їх укладають у лоток лототрону у фіксованому порядку. Зв'язок із минулим тиражем при цьому втрачається. Інша справа – послідовність випадання куль у межах одного тиражу. У цьому випадку випадання чергової кулі визначається станом лототрону на момент випадання попередньої кулі. Таким чином, послідовність випадень куль в одному тиражі є ланцюгом Маркова, і можна використовувати таку модель. При аналізі числових лотерей тут є велика складність. Стан лототрону після випадання чергової кулі визначає подальші події, але проблема в тому, що цей стан нам невідомий. Все що нам відомо, що випала деяка куля. Але при випаданні цієї кулі, інші кулі можуть бути розташовані по-різному, так що є група з дуже великого числа станів, відповідна одному і тому ж події, що спостерігається. Тому ми можемо збудувати лише матрицю ймовірностей переходів між такими групами станів. Ці ймовірності є усередненням ймовірностей переходів між різними окремими станами, що, звичайно, знижує ефективність застосування моделі марківського ланцюга до числових лотереїв.
Аналогічно цьому випадку, така модель нейронної мережі може бути використана для передбачення погоди, котирувань валют і у зв'язку з іншими системами, де є історичні дані, і в майбутньому може бути використана інформація, що надходить. Хорошим застосуванням у разі, коли відомі лише прояви системи, але з внутрішні (приховані) стану, можуть бути застосовані приховані марківські моделі, які докладно розглянуті у Вікіпідручнику (приховані марківські моделі).

Література

1. Романовський І.В. Дискретний аналіз: Навчальний посібник для студентів, 3-тє вид. - СПб: Невський діалект; БХВ Петербург, 2003.
2. Таха, Хемді А. Введення в дослідження операцій, 6-те вид. - М.: Видавничий дім "Вільямс", 2001.
3. Вернер М. Основи кодування. Підручник для вузів. - М.: Техносфера, 2004.
4. Бєляєв А., Гаврилов М., Масальських А., Медвінський М. Марківські процеси, 2004.

Візуалізатори

1. Алексєєв В. Марківські процеси прийняття рішень, 2002.
2. Бєляєв А. Марківські ланцюги, 2002.

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

Прикладом однорідного ланцюга Маркова можуть бути випадкові блукання. Нехай на прямій Ox у точці з цілою координатою x = n знаходиться матеріальна частка. У певні моменти часу
частка стрибкоподібно змінює своє становище (наприклад, з ймовірністю pможе зміститися вправо і з ймовірністю 1 -p - вліво). Очевидно, координата частки після стрибка залежить від того, де знаходилася частка після безпосередньо попереднього стрибка, і не залежить від того, як вона рухалася в попередні моменти часу.

Надалі обмежимося розглядом кінцевих однорідних ланцюгів Маркова.

Перехідні можливості. Матриця переходу.

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

Матрицею переходу системи називають матрицю, яка містить усі перехідні ймовірності цієї системи:

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

Зазначимо деякі особливості матриці переходу.

Рівність Маркова

Позначимо через
ймовірність того, що в результаті nкроків (випробувань) система перейде зі стану у стан . Наприклад,
- можливість переходу за 10 кроків з третього стану в шосте. Зазначимо, що n= 1 ця ймовірність зводиться просто до перехідної ймовірності
.

Виникає питання, як, знаючи перехідні можливості
знайти ймовірність переходу стану у стан заnкроків. З цією метою вводиться на розгляд проміжний (між і ) станr. Іншими словами, вважають, що з первісного стану замшагов система перейде в проміжний стан з ймовірністю
, після чого за залишилися n–mкроків з проміжного стануrона перейде в кінцевий стан з ймовірністю
. Використовуючи повну ймовірність формули, можна показати, що справедлива формула

Цю формулу називають рівністю Маркова .

Знаючи всі перехідні можливості
, тобто. знаючи матрицю переходу зі стану в стан за один крок можна знайти ймовірності
переходу зі стан у стан за два кроки, а отже, і саму матрицю переходу , далі – за відомою матрицею - знайти і т.д.

Справді, вважаючи у рівності Маркова n= 2,m= 1 отримаємо

або
. У матричному вигляді це можна записати як
.

Вважаючи n=3,m=2, отримаємо
. У випадку справедливе співвідношення
.

приклад. Нехай матриця переходу дорівнює

Потрібно знайти матрицю переходу
.

Помножуючи матрицю саму на себе, отримаємо
.

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

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

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

.

Для ілюстрації наведемо найпростіший приклад. Розглянемо процес функціонування деякої системи (наприклад, приладу). Нехай прилад протягом однієї доби може перебувати в одному з двох станів – справному ( ) та несправному ( ). В результаті масових спостережень за роботою приладу складено таку матрицю переходу
,

де - ймовірність того, що прилад залишиться у справному стані;

- можливість переходу приладу зі справного в несправний стан;

- ймовірність переходу приладу з несправного у справний стан;

- Імовірність того, що прилад залишиться в стані "несправний".

Нехай вектор початкових ймовірностей станів приладу заданий співвідношенням

, тобто.
(В початковий момент прилад був несправний). Потрібно визначити ймовірність стану приладу через три доби.

Рішення: Використовуючи матрицю переходу, визначимо ймовірність станів після першого кроку (після першої доби):

Імовірність станів після другого кроку (другої доби) дорівнює

Нарешті, ймовірності станів після третього кроку (третьої доби) рівні

Таким чином, ймовірність того, що прилад перебуватиме у справному стані, дорівнює 0,819, і того, що в несправному – відповідно 0,181.

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

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

або в матричному записі

Звідси, даючи послідовно значення, отримаємо важливу формулу

Якщо існують межі

або в матричному записі

то величини називаються граничними чи фінальними перехідними ймовірностями.

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

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

Правильна матриця характеризується тим, що у її нормальній формі (69) (стор. 373) матриці є примітивними. Для регулярної матриці додатково.

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

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

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

Справді, нехай - мінімальний багаточлен правильної матриці. Тоді

Відповідно до теореми 10 можна прийняти, що

З формули (24) гол. V (стор. 113)

(96)

де - наведена приєднана матриця та

Якщо – правильна матриця, то

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

Зворотне становище очевидне. Якщо існує межа

то матриця не може мати характеристичного числа , для якого , а , так як тоді не існувала б межа [Ця ж межа повинна існувати через існування межі (97").]

Ми довели, що для правильного (і тільки для правильного) однорідного ланцюга Маркова існує матриця. Ця матриця визначається формулою (97).

Покажемо, як можна виразити матрицю через характеристичний багаточлен

та приєднану матрицю .

З тотожності

в силу (95), (95") та (98) випливає:

Тому формулу (97) можна замінити формулою

(97)

Для регулярного ланцюга Маркова, оскільки він є приватним видом правильного ланцюга, матриця існує і визначається будь-якою з формул (97), (97"). У цьому випадку і формула (97") має вигляд

2. Розглянемо правильний ланцюг загального типу (нерегулярний). Відповідну матрицю запишемо у нормальній формі

(100)

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

,

запишемо у вигляді

(101)

Але , Оскільки всі характеристичні числа матриці за модулем менше одиниці. Тому

(102)

Оскільки - примітивні стохастичні матриці, то матриці згідно з формулами (99) та (35) (стор. 362) позитивні

і в кожному стовпці будь-якої з цих матриць всі елементи рівні між собою:

.

Зауважимо, що нормальному виду (100) стохастичної матриці відповідає розбиття станів системи на групи:

Кожній групі (104) відповідає своя група рядів (101). По термінології Л. Н. Колмогорова стану системи, що входять до , називаються суттєвими, а стани, що входять до інших груп - несуттєвими.

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

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

3. З формули (97) випливає:

.

Звідси видно, кожен стовпець матриці є власним вектором стохастичної матриці для характеристичного числа .

Для регулярної матриці число 1 є простим коренем характеристичного рівняння і цьому числу відповідає лише один (з точністю до скалярного множника) власний вектор матриці. Тому в будь-якому стовпці матриці всі елементи рівні одному й тому ж невід'ємному числу:

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

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

Для ациклічної ланцюга, яка є окремим випадком регулярного ланцюга, - примітивна матриця. Тому при деякому (див. теорему 8 на стор. 377). Але тоді й .

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

Отримані результати ми сформулюємо у вигляді наступної теореми:

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

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

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

4. Введемо на розгляд стовпці з абсолютних ймовірностей

(105)

де - ймовірність знаходження системи у момент у стані (,). Користуючись теоремами складання та множення ймовірностей, знайдемо:

(,),

або в матричному записі

де - транспонована матриця для матриці.

Усі абсолютні ймовірності (105) визначаються з формули (106), якщо відомі початкові ймовірності та матриця перехідних ймовірностей

Введемо на розгляд граничні абсолютні ймовірності

Переходячи в обох частинах рівності (106) до межі при , отримаємо:

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

З формули (107) і виду (102) матриці випливає, що граничні абсолютні ймовірності, що відповідають несуттєвим станам, дорівнюють нулю.

Помножуючи обидві частини матричної рівності

праворуч на , ми в силу (107) отримаємо:

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

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

Нехай даний регулярний ланцюг Маркова. Тоді з (104) і (107) випливає:

(109)

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

Назад, може не залежати від наявності формули (107) тоді і тільки тоді, коли всі рядки матриці однакові, тобто.

,

і тому (відповідно до теореми 11) - регулярна матриця.

Якщо - примітивна матриця, то , а звідси (109)

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

З викладеного випливає, що теорему 11 можна сформулювати так:

Теорема 11". 1. Для того щоб в однорідному ланцюгу Маркова існували всі граничні абсолютні ймовірності при будь-яких початкових ймовірностях, необхідно і достатньо, щоб ланцюг був правильним.

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

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

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

Візьмемо нормальну форму (69) матриці і позначимо через індекси імпримітивності матриць (69). Нехай - найменше загальне кратне цілих чисел. Тоді матриця немає характеристичних чисел, рівних по модулю одиниці, але відмінних від одиниці, т. е. - правильна матриця; при цьому – найменший показник, при якому – правильна матриця. Число назвемо періодом даного однорідного ланцюга Маркова і.. Назад, якщо і , Які визначаються формулами (110) і (110").

Середні граничні абсолютні ймовірності, що відповідають несуттєвим станам, завжди дорівнюють нулю.

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

Марковий ланцюг (Markov Chain) - марківський процес з дискретним часом, заданий у просторі, що вимірюється.

Вступ

Марківські випадкові процеси названі на ім'я видатного російського математика А.А.Маркова (1856-1922), що вперше почав вивчення імовірнісного зв'язку випадкових величин і створив теорію, яку можна назвати "динамікою ймовірностей".

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

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

Простий приклад: кидання монети

Перш ніж дати опис загальної схеми, звернімося до прикладу. Припустимо, що йдеться про послідовні кидання монети при грі "в орлянку"; монета кидається в умовні моменти часу t = 0, 1, ... і на кожному кроці гравець може виграти ±1 з однаковою ймовірністю 1/2, таким чином у момент t його сумарний виграш є випадковою величиною ξ(t) з можливими значеннями j = 0, ±1, ...

За умови, що ξ(t) = k, на наступному кроці виграш дорівнюватиме ξ(t+1) = k ± 1, приймаючи зазначені значення j = k ± 1 c однаковою ймовірністю 1/2.

Умовно можна сказати, що тут з відповідною ймовірністю відбувається перехід зі стану ξ(t) = k стан ξ(t+1) = k ± 1.

Формули та визначення

Узагальнюючи цей приклад, можна уявити "систему" з рахунковим числом можливих "фазових" станів, яка з часом дискретного часу t = 0, 1, ... випадково переходить зі стану в стан.

Нехай ξ(t) є її становище в момент t в результаті ланцюжка випадкових переходів

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Формально позначимо всі можливі стани цілими i = 0, ±1, ... Припустимо, що за відомого стану ξ(t) = k на наступному кроці система переходить у стан ξ(t+1) = j з умовною ймовірністю

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

незалежно від її поведінки у минулому, точніше, незалежно від ланцюжка переходів (1) до моменту t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всіх t, k, j ... (3) - марківська властивість.

Таку імовірнісну схему називають однорідним ланцюгом Маркова з рахунковим станом- її однорідність полягає в тому, що визначені (2) перехідні ймовірності p kj, ∑ j p kj = 1, k = 0, ±1, ..., не залежить від часу, тобто. P(ξ(t+1) = j|ξ(t) = k) = P ij - матриця ймовірностей переходуза крок не залежить від n.

Зрозуміло, що P ij - квадратна матриця з невід'ємними елементами та одиничними сумами рядків.

Така матриця (кінцева чи нескінченна) називається стохастичною матрицею. Будь-яка стохастична матриця може бути матрицею перехідних ймовірностей.

На практиці: доставка обладнання по округах

Припустимо, деяка фірма здійснює доставку обладнання по Москві: у північний округ (позначимо А), південний (В) і центральний (С). Фірма має групу кур'єрів, що обслуговує ці райони. Зрозуміло, що для здійснення наступної доставки кур'єр їде до району, який на даний момент йому ближче. Статистично було визначено таке:

1) після здійснення доставки А наступна доставка в 30 випадках здійснюється в А, в 30 випадках - в В і в 40 випадках - в С;

2) після здійснення доставки до наступна доставка в 40 випадках здійснюється в А, в 40 випадках - у В і в 20 випадках - в С;

3) після здійснення доставки С наступна доставка в 50 випадках здійснюється в А, в 30 випадках - в В і в 20 випадках - в С.

Таким чином, район наступної доставки визначається лише попередньою доставкою.

Матриця ймовірностей переходу виглядатиме так:

Наприклад, р 12 = 0.4 - це ймовірність того, що після доставки в район наступна доставка буде проводитися в районі А.

Припустимо, кожна доставка з наступним переміщенням до наступного району займає 15 хвилин. Тоді, відповідно до статистичних даних, через 15 хвилин 30% з кур'єрів, які перебували в А, будуть в А, 30% будуть у В і 40% - у С.

Так як у наступний момент часу кожен з кур'єрів обов'язково буде в одному з округів, то сума по стовпцях дорівнює 1. І оскільки ми маємо справу з ймовірностями, кожен елемент матриці 0<р ij <1.

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

Тепер поставимо просте запитання: якщо кур'єр стартує з, яка ймовірність того, що здійснивши дві доставки, він буде в, тобто. як можна досягти В 2 кроки? Отже, існує кілька шляхів із С до В за 2 кроки:

1) спочатку із С в С і потім із С в С;

2) С-->B і B-->B;

3) С->A і A->B.

Враховуючи правило множення незалежних подій, отримаємо, що ймовірність дорівнює:

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Підставляючи числові значення:

P = 0.5 * 0.3 + 0.3 * 0.4 + 0.2 * 0.3 = 0.33

Отриманий результат говорить про те, що якщо кур'єр почав роботу з С, то в 33 випадках зі 100 він буде у В через дві доставки.

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

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

Тоді елемент (2, 3) - це вірогідність переходу з С до 2 кроку, яка була отримана вище іншим способом. Зауважимо, що елементи в матриці P 2 також знаходяться в межах від 0 до 1 і сума по стовпцях дорівнює 1.

Т.о. якщо Вам необхідно визначити ймовірності переходу із С до В за 3 кроки:

1 спосіб. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, де p(CA) - ймовірність переходу з А в 2 кроки (тобто це елемент (1, 3) матриці P 2).

2 спосіб.Обчислити матрицю P 3:

Матриця перехідних ймовірностей у 7 ступеня виглядатиме так:

Легко помітити, що елементи кожного рядка прагнуть деяких цифр. Це говорить про те, що після досить великої кількості доставок вже не має значення, в якому окрузі кур'єр почав роботу. Т.о. наприкінці тижня приблизно 38,9% будуть у А, 33,3% будуть у В та 27,8% будуть у С.

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

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

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

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

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

Отже, у позначенні перший індекс вказує номер попереднього, а другий? номер наступного стану. Наприклад, - ймовірність переходу з другого стану до третього.

Нехай кількість станів звісно й дорівнює.

Матрицею переходу системи називають матрицю, яка містить усі перехідні ймовірності цієї системи:

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

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

Тут бачимо, що якщо система перебувала в стані, то після зміни стану за один крок вона з імовірністю 0,5 залишиться в цьому ж стані, з імовірністю 0,5 залишиться в цьому ж стані, з імовірністю 0,2 перейде в стан, то після переходу вона може опинитися у станах; перейти ж зі стану вона не може. Останній рядок матриці показує нам, що зі стану перейти в будь-який з можливих станів з однією ймовірністю 0,1.

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

приклад 2.За заданою матрицею переходу побудувати граф станів.

Т.к. матриця четвертого порядку, то, відповідно, система має 4 можливі стани.

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