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

Визначення і загальна характеристика

МА́РКОВА ЛАНЦЮ́Г — випадковий процес, частковий випадок Марковського процесу, у якого часова множина та/або фазовий простiр дис­кретнi. Кон­­цепцiю М. л. сформував академік С.-Пе­тербур. АН А. Марков, який роз­глядав задачу знаходже­н­ня ймовiрнiстей появ послідов. голосних і приголосних у романі «Євгенiй Онєгiн» А. Пушкіна. Вiн ви­вчав на­ступнi ймовiрностi: p — ймовiрнiсть того, що буква є голосною, p₁ — ймовірність появи голосної слідом за голосною, p₀ — ймовірність появи голосної слідом за приголосною, p_1,1 — ймовірність появи голосної слідом за двома голосними, p_0,0 — ймовірність появи голосної слідом за двома приголосними i так далі. Роз­глядаючи такi ймовiрностi, А. Марков зʼясував, що ймовiр­­нiсть появи голосної або приголосної дуже залежить вiд того, якою була попередня лiтера. Таким чином, випадк. процес X_n, де X_n = 1, якщо n-а буква голосна, або X_n = 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д того, якою стороною вона випала, а X_n по­значає сумар. ви­граш або про­граш гравця у момент n. Припустивши, що гравець стартує з нуля, зро­зумiло, що в парнi моменти часу його ви­граш або про­граш може бути лише парним числом, а в непарнi — непарним. Таким чином, з парного стану в iн. парний можна потрапити лише за парну кiлькiсть крокiв. Подiбнi ланцюги будуть перiодичними, в iн. разi — аперiодичними. За певних умов М. л. властива ергодичність, це означає, що з часом імовiрностi пере­ходу все менше залежать вiд початк. значе­н­ня. Якщо ланцюг має таку властивiсть, то при великих n роз­­­подiл X_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н. сл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.

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

Завантажити статтю