Марков дискретті тізбегі - Discrete-time Markov chain

Екі күйі бар Марков тізбегі, A және E.

Жылы ықтималдық, a (дискретті уақыт) Марков тізбегі (DTMC) - а деп аталатын кездейсоқ шамалардың тізбегі стохастикалық процесс, онда келесі айнымалының мәні тек өткен айнымалының емес, тек ағымдағы айнымалының мәніне тәуелді болады. Мысалы, машинада екі күй болуы мүмкін, A және E. Ол күйде болған кезде A, оның күйге өтуінің 40% мүмкіндігі бар E және оның күйінде қалуының 60% мүмкіндігі A. Ол күйде болған кезде E, оған көшудің 70% мүмкіндігі бар A және оның қалуының 30% мүмкіндігі E. Машинаның күйлерінің реттілігі - Марков тізбегі. Егер тізбекті арқылы белгілесек содан кейін - бұл машинаның басталатын күйі және болып табылады кездейсоқ шама оның 10 өткелден кейінгі күйін сипаттайтын. Процесс мәңгі жалғасады, индекстелген натурал сандар.

Марков тізбегі болып табылмайтын стохастикалық процестің мысалы күйлерге ие машинаның моделі болып табылады A және E және ауысады A кез келген штаттан 50% мүмкіндігі бар кез-келген штаттан A бұрын, және егер ол ешқашан келмеген болса, 20% мүмкіндік A дейін (машинаның қозғалатын мүмкіндігінің 50% немесе 80% қалдыру) E). Себебі машинаның әрекеті бүкіл тарихқа байланысты - егер машина болса E, оған көшу мүмкіндігі 50% немесе 20% болуы мүмкін A, оның өткен мәндеріне байланысты. Демек, ол жоқ Марковтың меншігі.

Марков тізбегін а стохастикалық матрица, бұл кез-келген жеке күйден әр күйге көшу ықтималдығын тізімдейді. Осы матрицадан белгілі бір күйде болу ықтималдығы n болашақтағы қадамдарды есептеуге болады. Марков тізбегінің күй кеңістігін қандай күйлердің бір-біріне қол жетімді екендігін сипаттайтын байланысатын сыныптарға бөлуге болады (бір өтуде немесе көп жағдайда). Әр күйді тізбектің сол күйге оралу ықтималдығына байланысты уақытша немесе қайталанатын деп сипаттауға болады. Марков тізбектері мерзімділікті, қайтымдылықты және тұрақтылықты қамтитын қасиеттерге ие бола алады. A үздіксіз Марков тізбегі дискретті уақыттағы Марков тізбегіне ұқсайды, бірақ ол күйлерді дискретті уақыт қадамдары ретінде емес, уақыт бойынша үздіксіз жылжытады. Басқа стохастикалық процестер Марковтың қасиетін қанағаттандыра алады, өткен мінез-құлық процеске әсер етпейтін қасиет, тек қазіргі күйге.

Анықтама

Марков дискретті тізбегі дегеніміз кездейсоқ шамалар бірге Марковтың меншігі, атап айтқанда келесі күйге өту ықтималдығы алдыңғы күйлерге емес, тек қазіргі күйге байланысты:

егер екеуі болса шартты ықтималдықтар жақсы анықталған, яғни, егер

Мүмкін мәндері Xмен а есептелетін жиынтық S тізбектің күй кеңістігі деп аталады.[1]

Марков тізбектері көбінесе тізбегімен сипатталады бағытталған графиктер, мұнда графтың шеттері n уақытта бір күйден шығу ықтималдығымен белгіленеді n уақытында басқа мемлекеттерге n + 1, Сол ақпарат уақыт бойынша ауысу матрицасымен ұсынылған n уақытқа n + 1. Алайда, Марков тізбектері уақыт бойынша біртектес деп саналады (төмендегі вариацияларды қараңыз), бұл жағдайда график пен матрица тәуелді емес n және осылайша дәйектілік ретінде ұсынылмайды.

Бұл сипаттамалар Марков тізбегінің алғашқы таралуына тәуелсіз құрылымын ерекше көрсетеді Уақыт біртектес болған кезде тізбекті а деп түсіндіруге болады мемлекеттік машина әр шыңнан немесе күйден көршіге секіру ықтималдығын тағайындау. Ықтималдық машина күйін элементі бар машинаның статистикалық әрекеті ретінде талдауға болады күйдің кеңістігі ретінде немесе алғашқы үлестірілімімен машинаның әрекеті ретінде мемлекеттердің кірісі ретінде, қайда болып табылады Айверсон жақшасы.[дәйексөз қажет ]

Вариациялар

  • Уақыт біртекті Марков тізбектері (немесе стационарлық Марков тізбектері) - бұл процестер
барлығына n. Өту ықтималдығы тәуелді емес n.[1]
  • Марков тізбегі жадымен (немесе Марков тізбегінің тізбегі) м)
қайда м ақырлы, қанағаттандыратын процесс
Басқаша айтқанда, болашақ мемлекет өткенге байланысты м мемлекеттер. Тізбек құруға болады бастап Марковтың 'классикалық' қасиеті бар, ол мемлекеттік кеңістікті ретке келтіріп алады м-жастары X мәндер, яғни. .[дәйексөз қажет ]

n- қадамдық ауысулар

Күйден шығу ықтималдығы мен мемлекетке j жылы n уақыт қадамдары

және бір сатылы көшу болып табылады

Уақыт біртекті Марков тізбегі үшін:

және

The n-адамның ауысу ықтималдығы Чапман - Колмогоров теңдеуі, бұл кез келген үшін к осылай 0 <к < n,

қайда S бұл Марков тізбегінің мемлекеттік кеңістігі.[1]

The шекті үлестіру Pr (Xn = х) дегеніміз - уақыт бойынша күйлер бойынша таралуы n. Бастапқы үлестіру Pr (X0 = х). Бір реттік қадам арқылы процестің эволюциясы сипатталады

(Жоғарғы әріп (n) болып табылады индекс, және емес көрсеткіш ).

Сыныптар мен қасиеттерді байланыстыру

Мемлекет j штаттан қол жетімді дейді мен (жазбаша) мен → j) егер жүйе күйінде басталған болса мен күйге өтудің нөлдік емес ықтималдығы бар j бір сәтте. Ресми түрде, мемлекет j штаттан қол жетімді мен егер бүтін сан болса nиж ≥ 0 осылай

Мемлекет мен мемлекетпен байланыс жасайды дейді j (жазбаша) мен ↔ j) егер екеуі болса мен → j және j → мен. Қарым-қатынас жасайтын сынып - күйлердің максималды жиынтығы C мемлекеттердің әр жұбы C бір-бірімен байланыста болады. Байланыс эквиваленттік қатынас және байланыстырушы сыныптар болып табылады эквиваленттік сыныптар осы қатынастың.[1]

Байланыс жасайтын сынып жабылады, егер сыныптан шығу ықтималдығы нөлге тең болса, атап айтқанда, егер мен ішінде C бірақ j олай емес j қол жетімді емесмен.[1] Қарым-қатынас сыныптарының жиынтығы а бағытталған, ациклдік график көрсеткілерді бастапқы күй кеңістігінен мұра ету арқылы. Қарым-қатынас жасайтын сынып осы графикте шығыс көрсеткілері болмаса ғана жабылады.

Мемлекет мен бәрі үшін маңызды немесе түпкілікті деп аталады j осындай мен → j бұл шындық j → мен. Мемлекет мен маңызды емес болса, маңызды емес.[2] Күй тек егер оның байланыс сыныбы жабық болса ғана болады.

Марков тізбегі, егер оның кеңістігі бірыңғай байланыс жасайтын класс болса, оны азайтуға болмайды деп айтады; басқаша айтқанда, кез-келген күйге кез-келген күйден жету мүмкіндігі болса.[1][3]

Мерзімділігі

Мемлекет кезеңі бар егер мемлекетке қайтып оралса еселіктерінде болуы керек уақыт қадамдары. Ресми түрде кезең мемлекет ретінде анықталады

(қайда болып табылады ең үлкен ортақ бөлгіш ) егер бұл жиын бос болмаса. Әйтпесе кезең анықталмаған.[1] Штаттың кезеңі болғанымен , мемлекетке жету мүмкін емес қадамдар. Мысалы, мемлекетке қайтып оралу мүмкін делік уақыт қадамдары; болар еді , Сөйтсе де бұл тізімде жоқ.

Егер , содан кейін мемлекет апериодты деп аталады. Әйтпесе (), мемлекет периодты деп аталады. Периодтылық - бұл сыныптық қасиет, яғни егер күйде кезең болса демек, әр мемлекет өзінің байланыс сыныбында кезеңге ие болады .[1]

Өтпелі кезең және қайталану

Мемлекет мен егер біз күйден бастасақ, өтпелі деп аталады мен, біз ешқашан оралмайтын нөлге тең емес ықтималдығы бар мен. Ресми түрде кездейсоқ шама Тмен күйге қайтарудың алғашқы уақыты мен («соққы уақыты»):

Нөмір

күйге оралуымыздың ықтималдығы мен кейін бірінші рет n қадамдар. Сондықтан, мемлекет мен егер өтпелі болса

Мемлекет мен өтпелі болмаса, қайталанатын (немесе тұрақты) болып табылады. Қайталану мен өтпелілік - бұл сыныптық қасиеттер, яғни олар байланыстағы сыныптың барлық мүшелеріне бірдей ие немесе бірдей бола бермейді.[1]

Мемлекет мен қайталанатын болып табылады егер және егер болса келуінің күтілетін саны мен шексіз:[1]

Оң рецидив

Егер соққы уақыты ықтималдықпен шектелген болса да 1, оның ақырғы болуы қажет емес күту. Жағдайдағы орташа қайталану уақыты мен күтілетін қайтару уақыты Ммен:

Мемлекет мен оң қайталанатын болып табылады (немесе тұрақты емес), егер Ммен ақырлы; әйтпесе, мемлекет мен нөлдік қайталанатын (немесе нөлдік тұрақты). Позитивті және нөлдік қайталану - бұл класстардың қасиеттері.[1]

Сіңіру күйлері

Мемлекет мен егер бұл күйден шығу мүмкін болмаса, сіңіру деп аталады. Сондықтан мемлекет мен сіңіреді, егер болса және ол

Егер әрбір күй жұтылатын күйге жете алса, онда Марков тізбегі Марков тізбегін сіңіру.[3]

Марковтың қайтымды тізбегі

Марков тізбегі қайтымды деп аталады, егер ықтималдық таралуы болса π оның мемлекеттерінің үстінен

барлық уақытта n және барлық штаттар мен және j. Бұл жағдай белгілі толық теңгерім шарт (немесе жергілікті баланс теңдеуі).

Бекітілген ерікті уақытты қарастыру n және стенографияны қолдану

егжей-тегжейлі теңгерім теңдеуін ықшам етіп жазуға болады

[1]

Бір қадамдық қадам n дейін n + 1 әр адам ретінде қарастырылуы мүмкін мен бар πмен доллар және әр адамға төлеу j бөлшек биж оның. Баланстың егжей-тегжейлі шарты әр төлем кезінде екінші адамның дәл сол ақшаны қайтаратынын айтады.[4] Ақшаның жалпы сомасы π әр адам уақыт қадамынан кейін өзгеріссіз қалады, өйткені әрбір жұмсалған доллар алынған долларға сәйкес келеді. Мұны теңдік формальды түрде көрсете алады

бұл, негізінен, адамның жалпы ақшасының мөлшері туралы айтады j уақыт кезеңінде алады (соның ішінде өзінен) ол басқаларға төлейтін ақша сомасына тең болады, бұл барлық ақшалар жұмсалды деп есептелгендіктен, бастапқыда болған барлық ақшаға тең болады (яғни, бджи 1-ден асады мен). Болжам техникалық сипатқа ие, өйткені шын мәнінде пайдаланылмаған ақша тек адамнан төленеді деп есептеледі j өзіне (яғни, бjj міндетті түрде нөл емес).

Қалай n ерікті болды, бұл кез-келген себепке негізделген n, демек, қайтымды Марков тізбектері үшін π әрқашан тұрақты күйдегі үлестірім (Xn+1 = j | Xn = мен) әрқайсысы үшінn.

Егер Марков тізбегі тұрақты күйдегі үлестіруден басталса, яғни , содан кейін барлығына және егжей-тегжейлі теңдеу теңдеуін келесі түрде жазуға болады

Осы соңғы теңдеудің сол және оң жақтары уақыт индекстерінің кері бағытын қоспағанда бірдей n жәнеn + 1.

Колмогоров критерийі Марков тізбегінің өтпелі матрицалық ықтималдықтардан тікелей қайтымды болуы үшін қажетті және жеткілікті шарт береді. Критерий әрбір тұйық цикл айналасындағы ықтималдықтардың көбейтіндісі цикл айналасында екі бағытта бірдей болуын талап етеді.

Марков тізбегіндегі қайтымды тізбектер Монте-Карло (MCMC) тәсілдерінде жиі кездеседі, өйткені қалаған үлестірім үшін теңгерімнің егжей-тегжейлі теңдеуі π міндетті түрде Марков тізбегі осылай салынғанын білдіреді π тұрақты күйдегі таралу болып табылады. Көптеген өтпелі матрицалар қолданылатын уақыт біртектес емес Марков тізбектерінде де, егер әрбір осындай өтпелі матрица қажетті тепе-теңдікті көрсетсе π тарату, бұл міндетті түрде оны білдіреді π Марков тізбегінің тұрақты күйінде таралуы.

Стационарлық үлестірулер

Тарату стохастикалық матрицасы бар Марков тізбегінің стационарлық таралуы егер және егер болса . Мұны келесідей жазуға болады:[1]

Бұл жағдай оны білдіреді егер Марков тізбегі болса бастапқы таралуы бар содан кейін (тарату кезінде) кез-келгені үшін .[1]

Егер Марков тізбегі қысқартылмайтын болса, онда ол стационарлық үлестірілімге ие, егер ол тек оң қайталанатын болса,[5] бұл жағдайда бірегей осындай үлестіру беріледі қайда орташа қайталану уақыты мен.[1]

Егер тізбекте бірнеше жабық байланыс сыныбы болса, оның стационарлық үлестірімдері ерекше болмайды (кез келгенін ескеріңіз) жабық байланыс сыныбы тізбекте; әрқайсысының өзіндік стационарлық таралуы болады . Бұл үлестірулерді жалпы тізбекке дейін кеңейте отырып, байланыс мәнінен тыс барлық мәндерді нөлге теңестіре отырып, бастапқы тізбектің инвариантты өлшемдерінің жиынтығы барлық дөңес комбинацияларының жиынтығы болып табылады ). Алайда, егер мемлекет j апериодикалық болып табыладыжәне кез-келген басқа мемлекет үшін мен, рұқсат етіңіз fиж тізбектің күйге келу ықтималдығы болуы керек j егер ол басталсамен,

Егер мемлекет мен периодпен периодты болып табылады к > 1 содан кейін шектеужоқ болса да, жоқбарлық сан үшін бар ма?р.

Марков тізбегінің тұрақты және біртекті емес тізбегі

Марков тізбегі тепе-теңдік үлестірімі үшін уақыт бойынша біртектес болуы шарт емес. Егер күйлер бойынша ықтималдық үлестірімі болса осындай

әр штат үшін j және әр уақытта n содан кейін бұл Марков тізбегінің тепе-теңдік үлестірімі. Марков тізбегінде Монте-Карло (MCMC) тізбегінде бірқатар әртүрлі өтпелі матрицалар қолданылатын жағдайларда пайда болуы мүмкін, өйткені әрқайсысы белгілі бір араластыру түрі үшін тиімді, бірақ әр матрица ортақ тепе-теңдік үлестірімді құрметтейді.

Соққы уақыттары

Соққы уақыты - бұл берілген күйлер жиынтығынан бастап, тізбек берілген күйге немесе күйлер жиынтығына келгенге дейінгі уақыт. Мұндай уақыт кезеңінің таралуы фазалық типтік үлестірілімге ие. Мұндай қарапайым үлестіру - экспоненциалды түрде бөлінген бір ауысу.[дәйексөз қажет ]

Ұрыс уақыты күтілуде

Күйлердің жиынтығы үшін A ⊆ S, вектор кA соққы уақыты (бұл жерде элемент білдіреді күтілетін мән күйінен басталады мен бұл тізбектің жиынтықтағы күйлердің біріне енетіндігі A) - минималды теріс емес шешім[6]

Эргодикалық теорема

Данасы эргодикалық теория, кез-келген екі күймен қысқартылмайтын апериодты Марков тізбегі үшін күйлер үшін эргодикалық теорема мен және j,[1]

сияқты

Ескертулер

  1. ^ а б c г. e f ж сағ мен j к л м n o б Гримметт, Г.; Stirzaker, D. R. (1992). «6». Ықтималдық және кездейсоқ процестер (екінші басылым). Оксфорд университетінің баспасы. ISBN  0198572220.
  2. ^ Ашер Левин, Дэвид (2009). Марков тізбектері және араластыру уақыты. б.16. ISBN  978-0-8218-4739-8.
  3. ^ а б Гагнюк, Пол А. (2017). Марков тізбектері: теориядан тәжірибеге және іске асыруға дейін. АҚШ, NJ: Джон Вили және ұлдары. 1–235 беттер. ISBN  978-1-119-38755-8.
  4. ^ Ричард Дуррет (19 мамыр 2012). Стохастикалық процестердің негіздері. Springer Science & Business Media. б. 37. ISBN  978-1-4614-3615-7. Мұрағатталды түпнұсқадан 2017 жылғы 6 ақпанда.
  5. ^ Серфозо, Ричард (2009), «Қолданбалы стохастикалық процестердің негіздері», Ықтималдық және оның қолданылуы: 35, дои:10.1007/978-3-540-89332-5, ISBN  978-3-540-89331-8, МЫРЗА  2484222, мұрағатталды түпнұсқасынан 2015-03-19
  6. ^ Норрис, Дж. Р. (1997). «Үздіксіз Марков тізбектері II». Марков тізбектері. 108–127 беттер. дои:10.1017 / CBO9780511810633.005. ISBN  9780511810633.

Әдебиеттер тізімі

  • Марков А. (1971). «Ықтималдықтар теориясының шекті теоремаларын тізбекке қосылған айнымалылардың қосындысына дейін кеңейту». В қосымшасында қайта басылған: Р. Ховард. Динамикалық ықтималдық жүйелер, 1 том: Марков тізбектері. Джон Вили және ұлдары.
  • Марков, А.А (2006). Аударған Линк, Дэвид. «Евгений Онегин мәтінін статистикалық зерттеуге мысалдардың тізбектерге қосылуына қатысты мысалы». Ғылым контекстте. 19 (4): 591–600. дои:10.1017 / s0269889706001074.
  • Лео Брейман (1992) [1968] Ықтималдық. Аддисон-Уэсли шығарған түпнұсқа басылым; қайта басылған Өнеркәсіптік және қолданбалы математика қоғамы ISBN  0-89871-296-3. (7-тарауды қараңыз)
  • J. L. Doob (1953) Стохастикалық процестер. Нью-Йорк: Джон Вили және ұлдары ISBN  0-471-52369-0.
  • С. П. Мейн және Р. Л. Твиди (1993) Марков тізбектері және стохастикалық тұрақтылық. Лондон: Спрингер-Верлаг ISBN  0-387-19832-6. желіде: MCSS . Екінші басылым пайда болды, Cambridge University Press, 2009 ж.
  • Кемени, Джон Г. Хазлтон Миркил; Дж. Лори Снелл; Томпсон Джеральд (1959). Соңғы математикалық құрылымдар (1-ші басылым). Englewood Cliffs, NJ: Prentice-Hall, Inc. Конгресс кітапханасының карточкасының каталогы 59-12841. Классикалық мәтін. cf 6-тарау Соңғы Марков тізбектері 384ff бет.
  • Джон Г. & Дж. Лори Снелл (1960) Соңғы Марков тізбектері, D. van Nostrand компаниясы ISBN  0-442-04328-7
  • Э. Нуммелин. «Марковтың жалпы төмендетілмейтін тізбектері және теріс емес операторлар». Кембридж университетінің баспасы, 1984, 2004 ж. ISBN  0-521-60494-X
  • Сенета, Э. Теріс емес матрицалар және Марков тізбектері. 2-ші айналым ред., 1981, XVI, 288 б., Статистикадағы жұмсақ мұқабалы Springer Series. (Бастапқыда Allen & Unwin Ltd. баспасынан шыққан, Лондон, 1973 ж.) ISBN  978-0-387-29765-1