Маркова ланцюг
МА́РКОВА ЛАНЦЮ́Г — випадковий процес, окремий випадок Марковського процесу, у якому часова множина та/або фазовий простір дискретні. Концепцію М. л. сформував академік С.-Петербурзької АН А. Марков, який розглядав задачу знаходження ймовірностей появи послідовних голосних і приголосних у романі «Євгеній Онєгін» О. Пушкіна. Він вивчав такі ймовірності: p — ймовірність того, що буква є голосною, p1 — ймовірність появи голосної після голосної, p0 — ймовірність появи голосної після приголосної, p1,1 — ймовірність появи голосної після двох голосних, p0,0 — ймовірність появи голосної після двох приголосних і так далі. Розглядаючи такі ймовірності, А. Марков зʼясував, що ймовірність появи голосної або приголосної дуже залежить від того, якою була попередня літера. Таким чином, випадковий процес Xn, де Xn = 1, якщо n-а буква голосна, або Xn = 0, якщо n-а буква приголосна, не є класичним випадковим блуканням, і величини Xn є залежними. Аналізуючи частоти появи голосних і приголосних, математик відкрив певний вид залежності, який полягає в тому, що розподіл значення процесу в певний момент часу повністю визначається його значенням у попередній момент часу і не залежить від усієї попередньої історії. Ця властивість була названа марковською властивістю. Випадкові процеси, що мають таку властивість, відіграють значну роль у практичних застосуваннях, а також мають власну теоретичну цінність. Оскільки розподіл ланцюга на певному кроці залежить і повністю визначений значенням процесу на попередньому кроці, то для того, щоб визначити процес, потрібно вказати ймовірності набуття ним усіх можливих значень для кожного попереднього значення (для ланцюгів із дискретним часом і дискретною множиною значень).
Такі значення ще називають станами процесу, множину значень — простором станів, або фазовим простором, а ймовірності записують у вигляді матриці перехідних ймовірностей за один крок. Якщо матриці перехідних ймовірностей однакові у різні моменти часу, то ланцюг називають однорідним, в іншому разі — неоднорідним. Існують М. л. зі скінченним або зліченним простором станів — дискретним простором (напр., сумарна кількість очок, що випала при n підкиданнях кубика), а також з недискретним простором станів (температура повітря, що вимірюється, напр., щогодини), з неперервним часом, але дискретним простором станів. Дослідника, який використовує М. л., можуть цікавити наступні питання: коли вперше ланцюг потрапить у певний стан; яка ймовірність того, що протягом певного часу ланцюг не потрапить у певний стан та ін. Теорія М. л. надзвичайно розвинена та дозволяє давати відповіді на подібні запитання, хоча складність подібних задач дуже залежить від типу ланцюга (однорідний чи неоднорідний, дискретний чи довільний простір станів, дискретний чи неперервний час). Властивості М. л. залежать і від поведінки ланцюга. Якщо ланцюг нескінченно часто відвідує кожен стан і з ймовірністю 1 повертається у початковий стан, то такий ланцюг є рекурентним. У протилежному випадку, якщо існує стан, чи множина, з якої неможливо вийти, потрапивши туди один раз (такі ситуації типові при моделюванні поведінки різних приладів, які можуть зламатися, або стану людини, яка може померти), ланцюг є транзієнтним. Інша важлива характеристика М. л. — періодичність.
Яскравим прикладом може бути гра, в якій підкидається монета і гравець виграє або програє залежно від того, якою стороною вона випала, а Xn позначає сумарний виграш або програш гравця у момент n. Припустивши, що гравець стартує з нуля, зрозуміло, що в парні моменти часу його виграш або програш може бути лише парним числом, а в непарні — непарним. Таким чином, з парного стану в інший парний можна потрапити лише за парну кількість кроків. Подібні ланцюги будуть періодичними, в іншому разі — аперіодичними. За певних умов М. л. властива ергодичність, це означає, що з часом імовірності переходу все менше залежать від початкового значення. Якщо ланцюг має таку властивість, то при великих n розподіл Xn не буде залежати від початкового стану ланцюга. Властивість ергодичності є ключовою під час дослідження ланцюгів і дозволяє отримувати багато практичних результатів. Ергодична теорія М. л. широко розвинена для різних типів ланцюгів і продовжує активно розвиватися донині. М. л. застосовують у теорії масового обслуговування при оцінюванні довжини черги, в біології при аналізі зростання популяції, в обчислювальній математиці, у лінгвістиці при аналізі частот вживання тих чи інших слів або конструкцій, при розробленні телекомунікацій і компʼютерних мереж. З ергодичної теорії М. л. з довільним фазовим простором класичною стала стаття українських математиків М. Боголюбова та М. Крилова («О некоторых проблемах эргодической теории стохастических систем» // «Записки Кафедры математической физики АН УССР», 1939, т. 4). Розвитком теорії М. л. займалися А. Скороход, В. Королюк, І. Коваленко, В. Анисимов, М. Карташов, О. Іксанов.
Рекомендована література
Завантажити статтю
