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

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

Зміст

Введення

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

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

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

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

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

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

Висновок

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

Введення

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

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

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

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

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

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

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

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

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

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

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

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

Таким чином, події називають станами системи, а випробування - змінами її станів.

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

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

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

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

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

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

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

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

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

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

Нехай число станів звичайно і одно.

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

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

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

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

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

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

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

S1

0,2 0,7

S2 0,4 S4

0,6 0,5

0,1 0,5

S3

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

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

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

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

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

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

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

. (1)

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

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

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

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

()

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

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

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

Дійсно, поклавши в рівності Маркова

,

Отримаємо

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

,

Або

(2)

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

Поклавши в (1), аналогічно одержимо

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

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

(3)

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

(4)

З рівностей

і

слід

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

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

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

(5)

Так як то де - матриця вірогідності переходу. З (5) випливає

(6)

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

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

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

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

.

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

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

(7)

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

,

(8)

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

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

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

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

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

, (9)

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

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

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

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

0 <<,

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

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

,

,

;

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

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

(10)

де, якщо, і в іншому випадку. Так як

,

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

.

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

(11)

Оскільки

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

при

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

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

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

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

і

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

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

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

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

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

. (12)

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

(13)

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

(14)

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

=

.

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

=.

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

Перейти до доказу теореми. Так як послідовності, монотонні, то

0 <. (15)

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

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

(16)

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

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

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

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

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

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

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

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

Висновок

Маркова. переходу.

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

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

2. Гнеденко Б.В.

3. Гмурман В.Є.

4. Вентцель Е.С.

5. Введення в теорію ймовірностей.

6.