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