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

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

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

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

Сценарій

Уявіть, що є лише дві погодні умови: може бути або сонячно, або похмуро. Завжди можна безпомилково визначити погоду зараз. Гарантовано буде ясно чи хмарно.

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

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

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

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

Модель

Формально ланцюг Маркова - це ймовірнісний автомат. Розподіл ймовірностей переходів зазвичай представляється як матриці. Якщо ланцюг Маркова має N можливих станів, то матриця матиме вигляд N x N, в якій запис (I, J) буде ймовірністю переходу зі стану I у стан J. Крім того, така матриця має бути стохастичною, тобто рядки або стовпці у сумі мають давати одиницю. У такій матриці кожен рядок матиме власний розподіл ймовірностей.

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

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

Ланцюг Маркова має початковий вектор стану, представлений у вигляді матриці N x 1. Він описує розподіл ймовірностей початку в кожному з N можливих станів. Запис I визначає ймовірність початку ланцюга у стані I.

Цих двох структур цілком вистачить на уявлення ланцюга Маркова.

Ми вже обговорили, як отримати можливість переходу з одного стану в інший, але що щодо отримання цієї можливості за кілька кроків? Для цього нам необхідно визначити можливість переходу зі стану I в стан J за M кроків. Насправді, це дуже просто. Матрицю переходу P можна визначити обчисленням (I, J) за допомогою зведення P у ступінь M. Для малих значень M це можна робити вручну за допомогою повторного множення. Але для великих значень M, якщо ви знайомі з лінійною алгеброю, більш ефективним способом зведення матриці в ступінь спочатку буде діагоналізувати цю матрицю.

Ланцюг Маркова: висновок

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

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

Вступ

§ 1. Ланцюг Маркова

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

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

§4. Стаціонарний розподіл. Теорема про граничні ймовірності

§5. Доказ теореми про граничні ймовірності в ланцюзі Маркова

§6. Області застосування ланцюгів Маркова

Висновок

Список використаної літератури

Вступ

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

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

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

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

§1. Ланцюг Маркова

Припустимо, що проводиться послідовність випробувань.

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

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

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

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

Для ілюстрації розглянемо приклад.

приклад 1.Припустимо, що частка, що знаходиться на прямій, рухається по цій прямій під впливом випадкових поштовхів, що відбуваються в моменти . Частка може знаходитися в точках з цілими координатами: ; в точках і знаходяться стіни, що відбивають. Кожен поштовх переміщає частинку вправо з імовірністю і вліво з імовірністю, якщо частка не знаходиться біля стінки. Якщо ж частка знаходиться біля стінки, то будь-який поштовх переводить її на одиницю всередину проміжку між стінками. Тут бачимо, що це приклад блукання частки є типовий ланцюг Маркова.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Підкреслимо, що при отримаємо перехідні ймовірності

Поставимо перед собою завдання: знаючи перехідні можливості знайти можливості переходу системи зі стану в стан за кроків.

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

За формулою повної ймовірності отримаємо

. (1)

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

Пояснення.Введемо позначення:

- Події, що цікавлять нас (за кроків система перейде з початкового стану в кінцеве ), отже, ; − гіпотези(за кроків система перейде з початкового стану в проміжний стан ), отже, − умовна ймовірність наступу за умови, що мала місце гіпотеза (за кроків система перейде з проміжного стану в кінцевий ), отже,

За формулою повної ймовірності,

()

Або у прийнятих нами позначеннях

що збігається з формулою Маркова (1).

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

Справді, поклавши у рівності Маркова

,

ланцюг марків випадковий ймовірність

,

(2)

Таким чином, за формулою (2) можна знайти всі ймовірності отже, і саму матрицю . Оскільки безпосереднє використання формули (2) виявляється стомлюючим, а матричне обчислення веде до мети швидше, напишу співвідношення (2) в матричній формі:

Поклавши в (1), аналогічно отримаємо

У загальному випадку

Теорема 1.У будь-яких s, t

(3)

Доведення. Обчислимо ймовірність за формулою повної ймовірності (), поклавши

З рівностей

Звідси з рівностей (4) і

отримаємо затвердження теореми.

Визначимо матрицю матричного запису (3) має вигляд

Бо де − матриця ймовірності переходу. З (5) випливає

(6)

Результати, отриманої в теорії матриць, дозволяють за формулою (6) обчислити та досліджувати їх поведінку при

приклад 1.Задано матрицю переходу Знайти матрицю переходу

Рішення. Скористаємося формулою

Перемноживши матриці, остаточно отримаємо:

.

§4. Стаціонарний розподіл. Теорема про граничні ймовірності

Розподіл ймовірностей у довільний момент часу можна знайти, скориставшись формулою повної ймовірності

(7)

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

де ймовірність переходу.

Якщо в ланцюзі Маркова то за будь-якого

Це твердження слід індукції з (7) і (8).

Наведемо формулювання теореми про граничні ймовірності одного важливого класу ланцюгів Маркова.

Теорема 1. Якщо за деякому >0 всі елементи матриця позитивні, то будь-яких , при

, (9)

де стаціонарний розподіл з деяка постійна, що задовольняє нерівністю 0< h <1.

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

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

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

В інших прикладах межі ймовірностей при очевидно не існують.

Знайдемо стаціонарний розподіл у прикладі 1. Потрібно знайти вектор що задовольняє умовам (8):

,

;

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

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

(10)

де , якщо , і інакше. Так як

,

то, скориставшись властивістю математичного очікування та формулою (9), отримаємо

.

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

Оскільки

З формули (11), зокрема, випливає, що

при

Також можна отримати формулу для яка використовується для обчислення дисперсії.

§5. Доказ теореми про граничні ймовірності в ланцюзі Маркова

Доведемо спочатку дві леми. Покладемо

Лемма 1. За будь-яких існують межі

Доведення. Використовуючи рівняння (3) з отримаємо

Таким чином, послідовності та монотонні та обмежені. Звідси випливає затвердження леми 1.

Лемма 2. Якщо виконані умови теореми 2, то існують постійні , такі, що

Для будь-яких

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

. (12)

Так як в умовах теореми 1 ймовірності переходу при всіх, то за будь-яких

І через кінцівку числа станів

Оцінимо тепер різницю . Використовуючи рівняння (3) з , , отримаємо

Звідси, використовуючи (8)-(10), знайдемо

=.

Поєднуючи це співвідношення з нерівністю (14), отримаємо затвердження леми.

Перейти до підтвердження теореми. Оскільки послідовності , монотонні, то

0<. (15)

Звідси і з леми 1 знаходимо

Отже, при отримуй і

Позитивність випливає з нерівності (15). Переходячи до межі при та у рівнянні (3), отримаємо, що задовольняє рівняння (12). Теорему доведено.

§6. Області застосування ланцюгів Маркова

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

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

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

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

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

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

Висновок

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

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

Список використаної літератури

1. Чистяков В.П. Курс теорії ймовірностей. 6-те вид., Випр. − СПб.: Видавництво «Лань», 2003. − 272 с. − (Підручник для вузів. Спеціальна література).

2. Гнєденко Б.В. Курс теорії ймовірностей.

3. Гмурман В.Є. Теорія ймовірностей та математична статистика.

4. Вентцель О.С. Теорія ймовірностей та її інженерні програми.

5. Колмогоров А.М., Журбенко І.Г., Прохоров А.В. Введення у теорію ймовірностей. − Москва-Іжевськ: Інститут комп'ютерних досліджень, 2003, 188 стор.

6. Кац М. Імовірність та суміжні питання у фізиці.

Марковий ланцюг (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).

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