Маркова ланцюг — Енциклопедія Сучасної України

Маркова ланцюг

МА́РКОВА ЛАНЦЮ́Г – випадковий процес, частковий випадок Марковського процесу, у якого часова множина та/або фазовий прост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ї М. л. займалися А. Скороход, В. Королюк, І. Коваленко, В. Анисимов, М. Карташов, О. Іксанов.

Лiт.: Марков А. А. Пример статистического исследования над текстом «Евгения Онегина», иллюстрирующий связь испытаний в цепь // Изв. С.-Пе­тербур. АН. 1913. Т. 7, вып. 3; Чжун Кай-лай. Однородные цепи Маркова / Пер. с англ. Москва, 1964; S. P. Mayn, R. L. Tweedie. Markov Сhains and Sto­­chastic Stability. 1993; N. V. Kartashov. Strong Stable Markov Chains. 1996.

В. В. Голомозий


Покликання на статтю