Ланцюги Маркова
Зміст
Введення
В§ 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
На графі не зазначаються ймовірності переходу системи з одного стану в те ж саме. При розгляді конкретних систем зручно спочатку побудувати граф станів, потім визначити ймовірність переходів системи з одного стану в той же самий (виходячи з вимоги рівності одиниці суми елементів рядків матриці), а потім скласти матрицю перех...
