Хомогенни вериги на Марков. Редовни вериги на Марков Разпознаване на циклични вериги на Марков pdf

Хомогенна е верига на Марков, за която условната вероятност за преход от състояние в състояние не зависи от номера на теста. Вместо това за хомогенни вериги
използвайте нотацията
.

Пример за хомогенна верига на Марков са случайните разходки. Нека има материална частица на правата Ox в точка с целочислена координата x=n. В определени моменти
частицата рязко променя позицията си (например с вероятност p може да се движи надясно, а с вероятност 1 –p– наляво). Очевидно координатата на частицата след скока зависи от това къде е била частицата след непосредствено предходния скок и не зависи от това как се е движила в предишни моменти от време.

По-нататък ще се ограничим до разглеждането на крайни хомогенни вериги на Марков.

Вероятности за преход. Преходна матрица.

Вероятност за преход
се нарича условната вероятност, че от състоянието В резултат на следващия тест системата ще премине в състояние . Така че индексът се отнася до предишния и - към последващото състояние.

Преходна матрица системи наричат матрица, която съдържа всички преходни вероятности на тази система:

, Където представят вероятностите за преход в една стъпка.

Нека да отбележим някои характеристики на преходната матрица.

Марковско равенство

Нека означим с
вероятността в резултат на n стъпки (тестове) системата да излезе от състоянието в състояние . Например,
- вероятността за преход в 10 стъпки от трето състояние към шесто. Имайте предвид, че когато n= 1, тази вероятност просто се свежда до вероятността за преход
.

Възниква въпросът: как, знаейки вероятностите за преход
, намерете вероятностите за преход на състоянието в състояние стъпка по стъпка За тази цел междинен (между И ) състояние. С други думи, смята се, че от първоначалното състояние След m стъпки системата ще премине в междинно състояние с вероятност
, след което в останалите n–m стъпки ще премине от междинно състояние към крайно състояние с вероятност
. Използване на формула пълна вероятност, може да се покаже, че формулата е валидна

Тази формула се нарича Марковско равенство .

Познаване на всички вероятности за преход
, т.е. познаване на матрицата на прехода от състояние на състояние в една стъпка, можете да намерите вероятностите
преход от състояние в състояние в две стъпки и следователно самата матрица на прехода , след това - според известната матрица - намирам и т.н.

Наистина, като поставим n= 2,m= 1 в равенството на Марков, получаваме

или
. В матрична форма това може да се запише като
.

Приемайки n=3,m=2, получаваме
. IN общ случайсъотношението е валидно
.

Пример. Нека преходната матрица равна на

Трябва да намерим матрицата на прехода
.

Умножаваща матрица върху себе си, получаваме
.

За практически приложения въпросът за изчисляване на вероятността дадена система да бъде в определено състояние в определен момент от време е изключително важен. Решаването на този въпрос изисква познаване на началните условия, т.е. вероятностите системата да бъде в определени състояния в началния момент. Първоначалното вероятностно разпределение на верига на Марков е вероятностното разпределение на състоянията в началото на процеса.

Тук чрез
показва вероятността системата да е в състояние в началния момент от времето. В специалния случай, ако първоначалното състояние на системата е точно известно (напр
), тогава първоначалната вероятност
, а всички останали са равни на нула.

Ако за хомогенна верига на Марков са дадени първоначалното вероятностно разпределение и преходната матрица, тогава вероятностите на състоянията на системата на n-та стъпка
се изчисляват по рекурентната формула

За да илюстрираме, нека дадем един прост пример. Нека разгледаме процеса на функциониране на определена система (например устройство). Оставете устройството да бъде в едно от двете състояния за един ден - изправно ( ) и дефектен ( ). В резултат на масови наблюдения на работата на устройството беше съставена следната матрица на прехода
,

Където - вероятността устройството да остане в добро състояние;

- вероятността устройството да премине от изправно към неизправно състояние;

- вероятността устройството да премине от неизправно в изправно състояние;

- вероятността устройството да остане в състояние "дефектно".

Нека векторът на началните вероятности за състояния на устройството е даден от релацията

, т.е.
(в първоначалния момент устройството беше дефектно). Необходимо е да се определят вероятностите за състоянието на устройството след три дни.

Решение: Използвайки матрицата на прехода, ние определяме вероятностите на състоянията след първата стъпка (след първия ден):

Вероятностите за състояния след втората стъпка (втори ден) са равни

И накрая, вероятностите за състояния след третата стъпка (третия ден) са равни

По този начин вероятността устройството да бъде в добро състояние е 0,819, а че ще бъде в неизправно състояние е съответно 0,181.

Марков процес- случаен процес, протичащ в системата, който има свойството: за всеки момент от време t 0, вероятността за всяко състояние на системата в бъдеще (при t>t 0) зависи само от нейното състояние в настоящето (при t = t 0) и не зависи от това кога и как системата е стигнала до това състояние (т.е. как се е развивал процесът в миналото).

В практиката често се сблъскваме със случайни процеси, които в различна степен на приближение могат да се считат за марковски.

Всеки процес на Марков се описва с помощта на вероятности за състояние и вероятности за преход.

Вероятности за състояния P k (t) на марковски процесса вероятностите случайният процес (система) в момент t да е в състояние S k:

Вероятности за преход на марковски процесса вероятностите за преминаване на процес (система) от едно състояние в друго:

Процесът на Марков се нарича хомогенен, ако вероятностите за преход за единица време не зависят от това къде на времевата ос се случва преходът.

Повечето прост процесе Маркова верига– Марков случаен процес с дискретно време и дискрет крайно множестводържави.

Когато се анализират, веригите на Марков са графика на състоянието, на който на една стъпка се отбелязват всички състояния на веригата (системата) и ненулеви вероятности.

Веригата на Марков може да се разглежда така, сякаш точка, представляваща система, се движи произволно през графика на състоянието, като се влачи от състояние в състояние в една стъпка или остава в едно и също състояние в продължение на няколко стъпки.

Вероятностите за преход на верига на Марков в една стъпка се записват под формата на матрица P=||P ij ||, която се нарича матрица на вероятността за преход или просто матрица на прехода.

Пример: наборът от състояния на студентите по специалността е както следва:

S 1 – първокурсник;

S 2 – второкурсник…;

S 5 – 5 курсист;

S 6 – специалист, завършил висше образование;

S 7 – лице, което е учило в университет, но не е завършило.

От състояние S 1 в рамките на една година са възможни преходи към състояние S 2 с вероятност r 1 ; S 1 с вероятност q 1 и S 7 с вероятност p 1 и:

r 1 +q 1 +p 1 =1.

Нека изградим графика на състоянието за тази верига на Марков и я маркираме с вероятности за преход (различни от нула).

Нека създадем матрица на вероятностите за преход:

Преходните матрици имат следните свойства:

Всички техни елементи са неотрицателни;

Сумите на техните редове са равни на единица.

Матриците с това свойство се наричат стохастични.

Преходните матрици ви позволяват да изчислите вероятността за всяка траектория на веригата на Марков, като използвате теоремата за умножение на вероятностите.

За хомогенните вериги на Марков преходните матрици не зависят от времето.

При изучаването на веригите на Марков най-голям интерес представляват:

Вероятности за преход в m стъпки;

Разпределение по състояния на стъпка m→∞;

Средно време, прекарано в определено състояние;

Средно време за връщане в това състояние.

Да разгледаме хомогенна верига на Марков с n състояния. За да се получи вероятността за преход от състояние S i към състояние S j на m стъпки, в съответствие с формулата за обща вероятност, трябва да се сумират продуктите на вероятността за преход от състояние Si към междинното състояние Sk на l стъпки с вероятността на преход от Sk към Sj в останалите m-l стъпки, т.е.

Тази връзка е за всички i=1, …, n; j=1, …,n може да бъде представено като произведение на матрици:

P(m)=P(l)*P(m-l).

Така имаме:

P(2)=P(1)*P(1)=P 2

P(3)=P(2)*P(1)=P(1)*P(2)=P 3 и т.н.

P(m)=P(m-1)*P(1)=P(1)*P(M-1)=P m,

което дава възможност да се намерят вероятностите за преход между състояния в произволен брой стъпки, като се знае матрицата на прехода в една стъпка, а именно P ij (m) - елемент от матрицата P(m) е вероятността за преминаване от състояние S i за заявяване на S j на m стъпки.

Пример: Времето в определен регион се редува между дъждовно и сухо за дълги периоди от време. Ако вали, тогава с вероятност 0,7 ще вали на следващия ден; Ако времето е сухо в определен ден, тогава с вероятност от 0,6 то ще се запази и на следващия ден. Известно е, че в сряда времето е било дъждовно. Каква е вероятността следващия петък да вали?

Нека запишем всички състояния на веригата на Марков в тази задача: D – дъждовно време, C – сухо време.

Нека изградим графика на състоянието:

Отговор: p 11 = p (D пета | D ср.) = 0,61.

Вероятностните граници р 1 (m), р 2 (m),…, р n (m) за m→∞, ако съществуват, се наричат ограничаващи вероятности на състоянията.

Следната теорема може да бъде доказана: ако във верига на Марков можете да преминете от + всяко състояние (в даден брой стъпки) едно към друго, тогава граничните вероятности на състоянията съществуват и не зависят от първоначалното състояние на системата .

Така при m→∞ в системата се установява определен граничен стационарен режим, в който всяко едно от състоянията възниква с определена постоянна вероятност.

Векторът p, съставен от пределни вероятности, трябва да удовлетворява отношението: p=p*P.

Средно време, прекарано в щата S i за време T е равно на p i *T, където p i - пределна вероятност за състояние S i . Средно време за връщане в състояние S i е равно на .

Пример.

За много икономически проблеми е необходимо да се знае редуването на години с определени стойности на годишните речни потоци. Разбира се, това редуване не може да се определи абсолютно точно. За да определим вероятностите за редуване (преход), разделяме потоците, като въвеждаме четири градации (състояния на системата): първо (най-нисък поток), второ, трето, четвърто (най-висок поток). За категоричност ще приемем, че първата градация никога не е последвана от четвърта, а четвъртата от първа поради натрупване на влага (в земята, резервоара и др.). Наблюденията показват, че в определен регион са възможни други преходи и:

а) от първата градация можете да преминете към всяка от средните два пъти по-често, отколкото отново към първата, т.е.

р 11 =0.2; р 12 =0.4; р 13 =0.4; р 14 =0;

б) от четвъртата градация преходите към втората и третата градация се случват четири и пет пъти по-често от връщанията, както във втората, т.е.

твърдо, т.е.

в четвъртата, т.е.

р 41 =0; р42 =0.4; р 43 =0.5; р44 =0.1;

в) от втората към други градации може да бъде само по-рядко: в първата - два пъти по-малко, в третата с 25%, в четвъртата - четири пъти по-рядко от прехода към втората, т.е.

р 21 =0,2; р 22 =0,4; р 23 =0.3; р 24 =0.1;

г) от третата степен преходът към втората степен е толкова вероятен, колкото връщането към третата степен, а преходите към първа и четвърта степен са четири пъти по-малко вероятни, т.е.

р31 =0.1; р 32 =0.4; р 33 =0.4; р 34 =0.1;

Нека изградим графика:

Нека създадем матрица на вероятностите за преход:

Нека намерим средното време между сушите и многоводните години. За да направите това, трябва да намерите граничното разпределение. Съществува, защото условието на теоремата е изпълнено (матрицата P2 не съдържа нулеви елементи, т.е. в две стъпки можете да преминете от всяко състояние на системата към всяко друго).

Където p4 =0.08; p 3 =; p 2 =; p 1 =0.15

Честотата на връщане към състояние S i е равна на .

Следователно честотата на сухите години е средно 6,85, т.е. 6-7 години, а дъждовните години 12.

Марковски вериги

Въведение

§ 1. Марковска верига

§ 2. Хомогенна верига на Марков. Вероятности за преход. Преходна матрица

§3. Марковско равенство

§4. Стационарно разпределение. Теорема за граничната вероятност

§5. Доказателство на теоремата за граничните вероятности във верига на Марков

§6. Приложения на веригите на Марков

Заключение

Списък на използваната литература

Въведение

Нашата тема курсова работаМарковски вериги. Веригите на Марков са кръстени на изключителния руски математик Андрей Андреевич Марков, който е работил много по случайни процесии има голям принос за развитието на тази област. Напоследък можете да чуете за използването на вериги на Марков в различни области: модерни уеб технологии, при анализиране на литературни текстове или дори при разработване на тактика за футболен отбор. Тези, които не знаят какво представляват марковите вериги, може да имат чувството, че това е нещо много сложно и почти неразбираемо.

Не, точно обратното е. Веригата на Марков е един от най-простите случаи на последователност от случайни събития. Но въпреки своята простота, той често може да бъде полезен дори когато описва доста сложни явления. Веригата на Марков е поредица от случайни събития, в които вероятността за всяко събитие зависи само от предишното, но не зависи от по-ранни събития.

Преди да се задълбочим, трябва да разгледаме няколко спомагателни въпроса, които са общоизвестни, но са абсолютно необходими за по-нататъшно изложение.

Целта на моята курсова работа е да изуча по-подробно приложенията на марковските вериги, постановката на проблема и проблемите на Марков.

§1. Маркова верига

Нека си представим, че се извършва поредица от тестове.

Определение.Веригата на Марков е поредица от опити, във всяко от които се появява едно и само едно от несъвместимите събития от пълната група, а условната вероятност събитието да се случи в тития опит е , при условие, че събитието се е случило в th процес , не зависи от резултатите от предишни тестове.

Например, ако последователността от опити образува верига на Марков и пълната група се състои от четири несъвместими събития и е известно, че събитието се е случило в шестия опит, тогава условната вероятност събитието да се случи в седмия опит не зависи какви събития се появиха в първия, ..., петия тест.

Имайте предвид, че независимите тестове са частен случай на верига на Марков. Наистина, ако тестовете са независими, тогава появата на определено събитие в който и да е тест не зависи от резултатите от предишни тестове. От това следва, че концепцията за верига на Марков е обобщение на концепцията за независими опити.

Често, когато представят теорията на веригите на Марков, те се придържат към различна терминология и говорят за определена физическа система, която във всеки момент от времето се намира в едно от състоянията: , и променя състоянието си само в отделни моменти от времето, т.е. е, системата преминава от едно състояние в друго (например от към ). За веригите на Марков вероятността за преминаване към всяко състояние е в момента зависи само от това в какво състояние е била системата в момента и не се променя, защото нейните състояния в по-ранни моменти стават известни. Освен това, по-специално, след теста системата може да остане в същото състояние („преместване“ от състояние в състояние).

За да илюстрираме, разгледайте един пример.

Пример 1.Нека си представим, че частица, разположена на права линия, се движи по тази права под въздействието на произволни удари, възникващи в моменти . Една частица може да бъде разположена в точки с цели координати: ; В точките са разположени отразяващите стени. Всяко натискане премества частицата надясно с вероятност и наляво с вероятност, освен ако частицата не е близо до стена. Ако частицата е близо до стената, тогава всяко натискане я премества с една единица навътре в празнината между стените. Тук виждаме, че този пример за ходене на частица е типична верига на Марков.

Така събитията се наричат състояния на системата, а тестовете се наричат промени в нейните състояния.

Нека сега дефинираме верига на Марков, използвайки нова терминология.

Маркова верига с дискретно време е верига, чиито състояния се променят в определени фиксирани времена.

Верига на Марков с непрекъснато време е верига, чиито състояния се променят във всеки произволен възможен момент във времето.

§2. Хомогенна верига на Марков. Вероятности за преход. Преходна матрица

Определение.Веригата на Марков се нарича хомогенна, ако условната вероятност (преход от състояние към състояние) не зависи от пробния номер. Следователно, вместо да пишете просто .

Пример 1.Случайна разходка. Нека има материална частица на права линия в точка с целочислена координата. В определени моменти от време частицата изпитва удари. Под въздействието на тласък частицата се движи с вероятност една единица надясно и с вероятност една единица наляво. Ясно е, че позицията (координатата) на частица след удар зависи от това къде се е намирала частицата след непосредствено предшестващия удар и не зависи от това как се е движила под въздействието на други предишни удари.

По този начин случайното ходене е пример за хомогенна верига на Марков с дискретно време.

Вероятността за преход е условната вероятност от състоянието (в което системата е попаднала в резултат на някакъв тест, без значение какъв брой) в резултат на следващия тест системата ще премине в състоянието.

Така в обозначението първият индекс показва номера на предишното състояние, а вторият номер на последващото състояние. Например, е вероятността за преход от второто състояние към третото.

Нека броят на състоянията е краен и равен на .

Преходната матрица на една система е матрица, която съдържа всички преходни вероятности на тази система:

Тъй като всеки ред от матрицата съдържа вероятностите за събития (преход от едно и също състояние към всяко възможно състояние), които образуват пълна група, сумата от вероятностите за тези събития е равна на единица. С други думи, сумата от вероятностите за преход на всеки ред от матрицата на прехода е равна на единица:

Нека дадем пример за преходната матрица на система, която може да бъде в три състояния; преходът от състояние към състояние се извършва по схемата на хомогенна верига на Марков; вероятностите за преход се дават от матрицата:

Тук виждаме, че ако системата е била в състояние, тогава след промяна на състоянието в една стъпка, тя ще остане в същото състояние с вероятност 0,5, ще остане в същото състояние с вероятност 0,5, ще премине в състояние с вероятност 0,2, след това след прехода може да се окаже в държави ; не може да премине от състояние към. Последният ред на матрицата ни показва, че от състояние да преминем към всяко от възможните състояния със същата вероятност от 0,1.

Въз основа на матрицата на прехода на системата можете да построите така наречената графика на състоянието на системата; тя се нарича също така обозначена графика на състоянието. Това е удобно за визуално представяне на веригата. Нека да разгледаме реда на конструиране на графики с помощта на пример.

Пример 2.Използвайки дадена матрица на прехода, изградете графика на състоянието.

защото матрица от четвърти ред, то съответно системата има 4 възможни състояния.

Графиката не показва вероятностите системата да премине от едно състояние в същото. Когато се разглеждат конкретни системи, е удобно първо да се изгради графика на състоянието, след което да се определи вероятността за преходи на системата от едно състояние към същото (въз основа на изискването сумата от елементите на редовете на матрицата да бъде равна на едно), и след това изградете преходна матрица на системата.

§3. Марковско равенство

Определение.Нека означим с вероятността, че в резултат на стъпки (тестове) системата ще премине от състояние в състояние. Например, е вероятността за преход в 10 стъпки от второ състояние към пето.

Подчертаваме, че при получаваме вероятностите за преход

Нека си поставим задача: знаейки вероятностите за преход, да намерим вероятностите системата да преминава от състояние в състояние на стъпки.

За тази цел въвеждаме в разглеждане междинно състояние (между и ). С други думи, ще приемем, че от началното състояние на стъпки системата ще премине в междинно състояние с вероятност , след което в останалите стъпки от междинното състояние ще премине в крайно състояние с вероятност .

Използвайки формулата за пълна вероятност, получаваме

. (1)

Тази формула се нарича равенство на Марков.

Обяснение.Нека въведем следната нотация:

– събитието, което ни интересува (на стъпки системата ще премине от начално състояние към крайно състояние), следователно, ; − хипотези (на стъпки системата ще премине от първоначалното състояние към междинното състояние), следователно − условна вероятност за възникване, при условие че хипотезата се е състояла (на стъпки системата ще се премести от междинното състояние към крайното състояние), Следователно,

Според формулата за пълна вероятност,

()

Или в нотацията, която сме приели

което съвпада с формулата на Марков (1).

Познавайки всички вероятности за преход, тоест знаейки матрицата на прехода от състояние към състояние в една стъпка, можете да намерите вероятностите за преход от състояние към състояние в две стъпки, а следователно и самата матрица на прехода; като използвате известна матрица, можете да намерите матрицата на прехода от състояние към състояние в три стъпки и т.н.

Наистина, поставяйки равенството на Марков

верига от белези случайна вероятност

(2)

По този начин, използвайки формула (2), можете да намерите всички вероятности и следователно самата матрица. Тъй като директното използване на формула (2) се оказва досадно, а матричното смятане води до целта по-бързо, ще напиша отношенията, произтичащи от (2), в матрична форма:

Поставяйки (1), получаваме по подобен начин

Общо взето

Теорема 1.За всяко s, t

(3)

Доказателство. Нека изчислим вероятността използвайки формулата за обща вероятност (), поставяйки

От равенствата

Следователно от равенства (4) и

получаваме твърдението на теоремата.

Нека дефинираме матрицата В матрична нотация (3) има формата

Оттогава къде е матрицата на вероятностите за преход. От (5) следва

(6)

Резултатите, получени в теорията на матриците, позволяват с помощта на формула (6) да се изчисли и изследва тяхното поведение, когато

Пример 1.Посочена матрица на прехода Намерете матрицата на прехода

Решение. Нека използваме формулата

Умножавайки матриците, накрая получаваме:

§4. Стационарно разпределение. Теорема за граничната вероятност

Разпределение на вероятностите в произволен моментвремето може да се намери с помощта на формулата за пълна вероятност

(7)

Може да се окаже, че не зависи от времето. Да се обадим стационарно разпределениевектор , отговарящи на условията

къде са вероятностите за преход.

Ако във верига Марков тогава за всякакви

Това твърдение следва чрез индукция от (7) и (8).

Нека представим формулировката на теоремата за граничните вероятности за един важен клас вериги на Марков.

Теорема 1. Ако за някои >0 всички елементи на матрицата са положителни, то за всяко , за

, (9)

Където стационарно разпределение с някаква константа, удовлетворяваща неравенството 0< ч <1.

Тъй като , тогава според условията на теоремата, от всяко състояние можете да стигнете до всяко състояние във времето с положителна вероятност. Условията на теоремата изключват вериги, които в известен смисъл са периодични.

Ако условията на теорема 1 са изпълнени, тогава вероятността системата да е в определено състояние в границата не зависи от първоначалното разпределение. Наистина, от (9) и (7) следва, че за всяко първоначално разпределение,

Нека разгледаме няколко примера за вериги на Марков, за които условията на теорема 1 не са изпълнени. Не е трудно да се провери дали подобни примери са примери. В примера вероятностите за преход имат граници, но тези граници зависят от първоначалното състояние. По-специално, когато

В други примери диапазоните на вероятността за очевидно не съществуват.

Нека намерим стационарното разпределение в пример 1. Трябва да намерим вектора удовлетворяващи условия (8):

;

Следователно съществува стационарно разпределение, но не всички координатни вектори са положителни.

За полиномиалната схема бяха въведени случайни променливи, равни на броя на резултатите от даден тип. Нека въведем подобни величини за вериги на Марков. Нека е броят пъти, в които системата влиза в състояние във времето. След това честотата на системата, удряща състоянието. Използвайки формули (9), можем да докажем, че когато подходи . За да направите това, трябва да получите асимптотични формули за и и да използвате неравенството на Чебишев. Ето извеждането на формулата за . Нека го представим във формата

(10)

къде, ако и иначе. защото

тогава, използвайки свойството на математическото очакване и формулата (9), получаваме

По силата на теорема 1, тройният член от дясната страна на това равенство е частична сума на конвергентен ред. Поставяне , получаваме

Тъй като

От формула (11), по-специално, следва, че

при

Можете също така да получите формула, която се използва за изчисляване на дисперсията.

§5. Доказателство на теоремата за граничните вероятности във верига на Марков

Нека първо докажем две леми. Да сложим

Лема 1. За всеки има граници

Доказателство. Използвайки уравнение (3) с получаваме

По този начин последователностите са едновременно монотонни и ограничени. Това предполага твърдението на лема 1.

Лема 2. Ако условията на теорема 2 са изпълнени, тогава има константи, такова, че

За всякакви

където , означава сумиране върху всички, за които е положително, и сумиране върху останалите . Оттук

. (12)

Тъй като при условията на теорема 1 вероятностите за преход за всички , то за всякакви

И поради крайния брой състояния

Нека сега преценим разликата . Използвайки уравнение (3) с , , получаваме

От тук, използвайки (8)-(10), намираме

Комбинирайки тази връзка с неравенството (14), получаваме твърдението на лемата.

Преминете към доказателството на теоремата. Тъй като последователностите са монотонни, тогава

0<. (15)

От това и лема 1 намираме

Ето защо, когато получите и

Положителността следва от неравенството (15). Преминавайки към границата при и в уравнение (3), получаваме, че удовлетворява уравнение (12). Теоремата е доказана.

§6. Приложения на веригите на Марков

Веригите на Марков служат като добро въведение в теорията на случайните процеси, т.е. теорията на простите последователности на семейство от случайни променливи, обикновено зависещи от параметър, който в повечето приложения играе ролята на време. Предназначен е основно да опише напълно както дългосрочното, така и локалното поведение на даден процес. Ето някои от най-проучваните въпроси в това отношение.

Брауновото движение и неговите обобщения - дифузионни процеси и процеси с независими нараствания . Теорията на случайните процеси допринесе за задълбочаване на връзката между теорията на вероятностите, теорията на операторите и теорията на диференциалните уравнения, което освен всичко друго беше важно за физиката и други приложения. Приложенията включват процеси, представляващи интерес за актюерската (застрахователната) математика, теорията на опашките, генетиката, контрола на трафика, теорията на електрическите вериги и теорията на инвентара.

Мартингали . Тези процеси запазват достатъчно свойства на веригите на Марков, че важни ергодични теореми остават валидни за тях. Мартингалите се различават от веригите на Марков по това, че когато текущото състояние е известно, само математическото очакване на бъдещето, но не непременно самото разпределение на вероятностите, не зависи от миналото. Освен че е важен изследователски инструмент, теорията на мартингала обогати теорията на случайните процеси, възникващи в статистиката, теорията за ядреното делене, генетиката и теорията на информацията с нови гранични теореми.

Стационарни процеси . Най-старата известна ергодична теорема, както беше отбелязано по-горе, може да се тълкува като резултат, описващ ограничаващото поведение на стационарен случаен процес. Такъв процес има свойството, че всички вероятностни закони, на които той отговаря, остават инвариантни по отношение на изместването на времето. Ергодичната теорема, формулирана за първи път от физиците като хипотеза, може да бъде представена като твърдение, че при определени условия средната стойност за ансамбъла съвпада със средната за времето. Това означава, че една и съща информация може да бъде получена от дългосрочно наблюдение на система и от едновременно (и мигновено) наблюдение на много независими копия на същата система. Законът за големите числа не е нищо повече от специален случай на ергодичната теорема на Биркхоф. Интерполацията и прогнозирането на поведението на стационарни гаусови процеси, разбирани в широк смисъл, служат като важно обобщение на класическата теория на най-малките квадрати. Теорията на стационарните процеси е необходим изследователски инструмент в много области, например в теорията на комуникацията, която се занимава с изучаването и създаването на системи, които предават съобщения в присъствието на шум или случайни смущения.

Процесите на Марков (процеси без последствия) играят огромна роля при моделирането на системите за масово обслужване (QS), както и при моделирането и избора на стратегия за управление на социално-икономическите процеси, протичащи в обществото.

Марковската верига може да се използва и за генериране на текстове. Като вход се подават няколко текста, след което се изгражда верига на Марков с вероятностите една дума да следва друга и полученият текст се създава въз основа на тази верига. Играчката се оказва много забавна!

Заключение

Така в нашата курсова работа говорихме за веригата на Марков. Научихме в какви области и как се използва, независими тестове доказаха теоремата за граничните вероятности във верига на Марков, дадоха примери за типична и хомогенна верига на Марков, както и за намиране на матрицата на прехода.

Видяхме, че дизайнът на веригата на Марков е пряко обобщение на дизайна на независимия тест.

Списък на използваната литература

1. Чистяков В.П. Курс по теория на вероятностите. 6-то издание, рев. − Санкт Петербург: Издателство Лан, 2003. − 272 с. − (Учебник за ВУЗ. Специална литература).

2. Гнеденко Б.В. Курс по теория на вероятностите.

3. Гмурман В.Е. Теория на вероятностите и математическа статистика.

4. Вентцел Е.С. Теория на вероятностите и нейните инженерни приложения.

5. Колмогоров А.Н., Журбенко И.Г., Прохоров А.В. Въведение в теорията на вероятностите. − Москва-Ижевск: Институт за компютърни изследвания, 2003, 188 с.

6. Katz M. Вероятност и свързани с нея въпроси във физиката.

Маркова верига- верига от събития, в която вероятността за всяко събитие зависи само от предишното състояние.

Тази статия е с абстрактен характер, написана е на базата на посочените в края източници, които са цитирани на места.

Въведение в теорията на веригите на Марков

Веригата на Марков е поредица от случайни събития, в които вероятността за всяко събитие зависи само от състоянието, в което процесът се намира в момента, и не зависи от предишни състояния. Крайната дискретна верига се определя от:

∑ j=1…n p ij = 1

Пример за матрица на вероятностите за преход с набор от състояния S = (S 1, ..., S 5), вектор на началните вероятности p (0) = (1, 0, 0, 0, 0):

СЪС Използвайки вектора на началните вероятности и преходната матрица, можем да изчислим стохастичния вектор p (n) - вектор, съставен от вероятностите p (n) (i), че процесът ще бъде в състояние i в момент n. Можете да получите p(n), като използвате формулата:

p(n) = p(0)×Pn

Векторите p (n) с нарастване на n в някои случаи се стабилизират - те се сближават до определен вектор на вероятността ρ, който може да се нарече стационарно разпределение на веригата. Стационарността се проявява във факта, че приемайки p (0) = ρ, получаваме p (n) = ρ за всяко n.

Най-простият критерий, който гарантира сходимост към стационарно разпределение, е следният: ако всички елементи на матрицата на вероятността за преход P са положителни, тогава когато n клони към безкрайност, векторът p (n) клони към вектора ρ, което е единственото решение към системата на формата

Може също да се покаже, че ако за някаква положителна стойност на n всички елементи на матрицата P n са положителни, тогава векторът p (n) все още ще се стабилизира.

Доказателствата за тези твърдения са представени подробно.

Веригата на Марков е изобразена като граф на преход, чиито върхове съответстват на състоянията на веригата, а дъгите съответстват на преходите между тях. Теглото на дъгата (i, j), свързваща върховете si и sj, ще бъде равно на вероятността pi(j) за преход от първото състояние към второто. Графика, съответстваща на матрицата, показана по-горе:

ДА СЕ класификация на състоянията на веригите на Марков

Когато разглеждаме вериги на Марков, може да се интересуваме от поведението на системата за кратък период от време. В този случай абсолютните вероятности се изчисляват с помощта на формулите от предишния раздел. По-важно е обаче да се изследва поведението на системата за дълъг интервал от време, когато броят на преходите клони към безкрайност. След това се въвеждат дефиниции на състоянията на веригите на Марков, които са необходими за изследване на поведението на системата в дългосрочен план.

Веригите на Марков се класифицират в зависимост от възможността за преход от едно състояние към друго.

Групи от състояния на верига на Марков (подмножества от върхове на преходната графа), които съответстват на задънените върхове на диаграмата на реда на преходната графа, се наричат ергодични класове на веригата. Ако разгледаме графиката, показана по-горе, можем да видим, че тя съдържа 1 ергодичен клас M1 = (S5), достижим от силно свързан компонент, съответстващ на подмножество от върхове M2 = (S1, S2, S3, S4). Състоянията, които са в ергодични класове, се наричат съществени, а останалите се наричат несъществени (въпреки че такива имена не са в съгласие със здравия разум). Поглъщащото състояние si е специален случай на ергодичния клас. След това, веднъж в такова състояние, процесът ще спре. За Si, pii = 1 ще бъде вярно, т.е. в графиката на прехода само едно ребро ще излезе от него - цикъл.

Абсорбиращите вериги на Марков се използват като временни модели на програми и изчислителни процеси. При моделиране на програма състоянията на веригата се идентифицират с блоковете на програмата, а матрицата на вероятностите за преход определя реда на преходите между блоковете, в зависимост от структурата на програмата и разпределението на първоначалните данни, стойностите от които влияят върху развитието на изчислителния процес. В резултат на представянето на програмата чрез абсорбираща верига е възможно да се изчисли броят на достъпите до програмните блокове и времето за изпълнение на програмата, оценено чрез средни стойности, отклонения и, ако е необходимо, разпределения. Използвайки тази статистика в бъдеще, можете да оптимизирате програмния код - използвайте методи на ниско ниво, за да ускорите критичните части на програмата. Този метод се нарича профилиране на код.

Например в алгоритъма на Дейкстра присъстват следните състояния на веригата:

vertex (v), извличане на нов връх от опашката с приоритети, преминаване само към състояние b;

начало (b), началото на цикъла на търсене на изходящи дъги за процедурата на отслабване;

анализ (a), анализ на следващата дъга, възможен преход към a, d или e;

намаляване (d), намаляване на оценката за някакъв връх на графиката, преместване на a;

край (e), завършване на цикъла, преминаване към следващия връх.

Остава да зададете вероятностите за преход между върховете и можете да изучавате продължителността на преходите между върховете, вероятностите за влизане в различни състояния и други средни характеристики на процеса.

По същия начин изчислителният процес, който се свежда до достъп до системните ресурси в реда, определен от програмата, може да бъде представен чрез абсорбираща верига на Марков, чиито състояния съответстват на използването на системни ресурси - преход на процесор, памет и периферни устройства; вероятностите отразяват реда на достъп до различни ресурси. Благодарение на това изчислителният процес се представя във вид, удобен за анализиране на неговите характеристики.

Веригата на Марков се нарича нередуцируема, ако всяко състояние Sj може да бъде достигнато от всяко друго състояние Si в краен брой преходи. В този случай се казва, че всички състояния на веригата комуникират, а графиката на прехода е компонент на силна свързаност. Процес, генериран от ергодична верига, започнал в определено състояние, никога не завършва, а последователно преминава от едно състояние в друго, завършвайки в различни състояния с различна честота в зависимост от вероятностите за преход. Следователно основната характеристика на ергодичната верига е

вероятността процесът да бъде в състояния Sj, j = 1,…, n, частта от времето, което процесът прекарва във всяко от състоянията. Нередуцируемите вериги се използват като модели за надеждност на системата. В действителност, ако ресурс, който процесът използва много често, се провали, функционалността на цялата система ще бъде изложена на риск. В този случай дублирането на такъв критичен ресурс може да помогне за избягване на повреди. В този случай състоянията на системата, които се различават в състава на работещо и повредено оборудване, се интерпретират като състояния на веригата, преходите между които са свързани с откази и възстановяване на устройства и промени във връзките между тях, извършени за поддържане на работоспособност на системата. Оценките на характеристиките на нередуцируема верига дават представа за надеждността на поведението на системата като цяло. Също така, такива схеми могат да бъдат модели на взаимодействие между устройства и задачи, изпратени за обработка.

Примери за използване

Система за обслужване при повреда

Сървърът се състои от няколко блока, като модеми или мрежови карти, които получават заявки от потребители за услуга. Ако всички блокове са заети, заявката се губи. Ако някой от блоковете приеме заявка, той става зает до края на обработката му. Нека вземем броя на незаетите блокове като състояния. Времето ще бъде дискретно. Нека означим с α вероятността за получаване на заявка. Ние също така вярваме, че времето за обслужване също е произволно и се състои от независими продължения, т.е. заявка с вероятност β се обслужва на една стъпка, а с вероятност (1 - β) се обслужва след тази стъпка като нова заявка. Това дава вероятността от (1 - β) β за услуга от две стъпки, (1 - β)2 β за услуга от три стъпки и т.н. Нека разгледаме пример с 4 устройства, работещи паралелно. Нека създадем матрица на вероятностите за преход за избраните състояния:

М Може да се отбележи, че има уникален ергодичен клас и следователно системата p × P = p в класа на вероятностните вектори има уникално решение. Нека запишем уравненията на системата, която ни позволява да намерим това решение:

Сега наборът от вероятности πi е известен, че в стационарен режим системата ще има i заети блокове. След това част от времето p 4 = C γ 4 /4 всички блокове в системата са заети, системата не отговаря на заявки. Получените резултати се отнасят за произволен брой блокове. Сега можете да се възползвате от тях: можете да сравните разходите за допълнителни устройства и намаляването на времето, през което системата е напълно заета.

Можете да прочетете повече за този пример в.

Процеси на вземане на решения с краен и безкраен брой етапи

Помислете за процес, в който има няколко матрици на вероятността за преход. За всеки момент от времето изборът на една или друга матрица зависи от решението, което вземаме. Горното може да се разбере чрез следния пример. В резултат на анализа на почвата градинарят оценява нейното състояние с едно от трите числа: (1) - добро, (2) - задоволително или (3) - лошо. В същото време градинарят забеляза, че производителността на почвата през текущата година зависи само от състоянието й през предходната година. Следователно вероятностите за преминаване на почвата без външни влияния от едно състояние в друго могат да бъдат представени чрез следната верига на Марков с матрица P1:

Л Естествено е продуктивността на почвата да се влошава с времето. Например, ако миналата година състоянието на почвата е било задоволително, то тази година може само да остане същото или да стане лошо, но няма да стане добро. Въпреки това, градинарят може да повлияе на състоянието на почвата и да промени вероятностите за преход в матрица P1 към съответните от матрица P2:

T Сега можем да свържем всеки преход от едно състояние в друго с определена функция на дохода, която се определя като печалба или загуба за период от една година. Градинарят може да избере да използва или да не използва торове, това ще определи крайния му доход или загуба. Нека въведем матрици R1 и R2, които определят функциите на дохода в зависимост от цената на торовете и качеството на почвата:

н И накрая, градинарят е изправен пред проблема коя стратегия да избере, за да максимизира средния очакван доход. Могат да се разглеждат два вида задачи: с краен и безкраен брой етапи. В този случай някой ден дейността на градинаря определено ще приключи. Освен това визуализаторите решават проблема с вземането на решение за краен брой етапи. Нека градинарят възнамерява да прекрати заниманието си след N години. Нашата задача сега е да определим оптималната стратегия за поведение на градинаря, тоест стратегията, която ще максимизира доходите му. Крайността на броя на етапите в нашата задача се проявява в това, че градинарят не се интересува какво ще се случи със земеделската му земя за N+1 година (за него са важни всички години до N включително). Сега можем да видим, че в този случай проблемът за търсене на стратегия се превръща в проблем за динамично програмиране. Ако означим с fn(i) максималния среден очакван доход, който може да бъде получен по време на етапи от n до N включително, като се започне от номер на състояние i, тогава е лесно да се извлече повтарящият се

З където k е номерът на използваната стратегия. Това уравнение се основава на факта, че общият доход rijk + fn+1(j) се получава в резултат на прехода от състояние i на етап n към състояние j на етап n+1 с вероятност pijk.

Сега оптималното решение може да бъде намерено чрез изчисляване на fn(i) последователно в низходяща посока (n = N…1). В същото време въвеждането на вектор от начални вероятности в постановката на проблема няма да усложни неговото решение.

Този пример също е обсъден в.

Моделиране на словосъчетания в текст

Да разгледаме текст, състоящ се от думите w. Нека си представим процес, в който състоянията са думи, така че когато е в състояние (Si), системата преминава в състояние (sj) според матрицата на вероятностите за преход. На първо място е необходимо да се „обучи“ системата: да се предостави достатъчно голям текст като вход за оценка на вероятностите за преход. И тогава можете да изградите траектории на веригата на Марков. Увеличаването на семантичното натоварване на текст, конструиран с помощта на алгоритъма на веригата на Марков, е възможно само чрез увеличаване на реда, където състоянието не е една дума, а множества с по-голяма мощност - двойки (u, v), тройки (u, v, w) и т.н. Освен това във веригите от първи и пети ред пак ще има малко смисъл. Значението ще започне да се появява, когато измерението на реда се увеличи поне до средния брой думи в типична фраза в изходния текст. Но е невъзможно да се движим по този начин, тъй като нарастването на семантичното натоварване на текста във веригите на Марков от висок ред става много по-бавно от намаляването на уникалността на текста. И текст, изграден върху вериги на Марков, например от тридесетия ред, все още няма да бъде толкова смислен, че да представлява интерес за човек, но вече е доста подобен на оригиналния текст, а броят на състоянията в такава верига ще бъди невероятен.

Тази технология сега е много широко използвана (за съжаление) в Интернет за създаване на съдържание на уеб страници. Хората, които искат да увеличат трафика към уебсайта си и да подобрят класирането му в търсачките, са склонни да поставят възможно най-много ключови думи за търсене на своите страници. Но търсачките използват алгоритми, които могат да разграничат истинския текст от несвързаната бъркотия от ключови думи. След това, за да заблудят търсачките, те използват текстове, създадени от генератор, базиран на верига на Марков. Има, разбира се, положителни примери за използване на вериги на Марков за работа с текст; те се използват при определяне на авторството и анализ на автентичността на текстовете.

Марковски вериги и лотарии

В някои случаи вероятностният модел се използва при прогнозиране на числа в различни лотарии. Очевидно няма смисъл да се използват вериги на Марков за моделиране на последователността на различни циркулации. Това, което се случи с топките в тегленето, по никакъв начин няма да повлияе на резултатите от следващото теглене, тъй като след тегленето топките се събират и при следващото теглене те се поставят в тавата за лотария в определен ред. В този случай се губи връзката с миналото обращение. Друго нещо е последователността от падащи топки в рамките на едно теглене. В този случай падането на следващата топка се определя от състоянието на лотарията в момента на падане на предишната топка. По този начин последователността от изпуснати топки в едно теглене е верига на Марков и такъв модел може да се използва. Тук има голяма трудност при анализирането на числови лотарии. Състоянието на лотарийната машина след падане на следващата топка определя по-нататъшните събития, но проблемът е, че това състояние е непознато за нас. Всичко, което знаем, е, че определена топка е паднала. Но когато тази топка бъде изпусната, останалите топки могат да бъдат подредени по различни начини, така че да има група от много голям брой състояния, съответстващи на едно и също наблюдавано събитие. Следователно можем да изградим само матрица на вероятностите за преход между такива групи от състояния. Тези вероятности са средна стойност на вероятностите за преходи между различни индивидуални състояния, което разбира се намалява ефективността на прилагането на модела на веригата на Марков към числови лотарии.

Подобно на този случай, такъв модел на невронна мрежа може да се използва за прогнозиране на времето, валутни котировки и във връзка с други системи, където са налични исторически данни и новополучената информация може да се използва в бъдеще. Добро приложение в този случай, когато са известни само проявите на системата, но не и вътрешните (скрити) състояния, може да се приложи към скрити модели на Марков, които са разгледани подробно в Wikibooks (скрити модели на Марков).

Марковски вериги

Въведение

§ 1. Марковска верига

§ 2. Хомогенна верига на Марков. Вероятности за преход. Преходна матрица

§3. Марковско равенство

§4. Стационарно разпределение. Теорема за граничната вероятност

§5. Доказателство на теоремата за граничните вероятности във верига на Марков

§6. Приложения на веригите на Марков

Заключение

Списък на използваната литература

Въведение

Темата на нашата курсова работа е веригата на Марков. Веригите на Марков са кръстени на изключителния руски математик Андрей Андреевич Марков, който работи широко върху случайни процеси и има голям принос за развитието на тази област. Напоследък можете да чуете за използването на вериги на Марков в различни области: модерни уеб технологии, при анализиране на литературни текстове или дори при разработване на тактика за футболен отбор. Тези, които не знаят какво представляват марковите вериги, може да имат чувството, че това е нещо много сложно и почти неразбираемо.

§1. Маркова верига

Нека си представим, че се извършва поредица от тестове.

Определение.Веригата на Марков е поредица от опити, във всяко от които се появява едно и само едно от следните.

несъвместими събития от пълната група и условната вероятност събитието да се случи в тия опит, при условие че събитието се е случило в тия опит, не зависи от резултатите от предишни опити.

Например, ако последователността от опити образува верига на Марков и пълната група се състои от четири несъвместими събития

и е известно, че събитието се е появило в шестия опит, тогава условната вероятност събитието да се случи в седмия опит не зависи от това какви събития са се появили в първия, втория, ..., петия опит.

Често, когато представят теорията на веригите на Марков, те се придържат към различна терминология и говорят за определена физическа система

, който във всеки момент от времето се намира в едно от състоянията: , и променя състоянието си само в отделни моменти от времето, т.е. системата преминава от едно състояние в друго (например от към ). За веригите на Марков вероятността за преминаване към което и да е състояние в момента зависи само от това в какво състояние е била системата в момента и не се променя, защото нейните състояния в по-ранни моменти стават известни. Освен това, по-специално, след теста системата може да остане в същото състояние („преместване“ от състояние в състояние).

За да илюстрираме, разгледайте един пример.

Пример 1.Нека си представим, че частица, разположена на права линия, се движи по тази права линия под въздействието на произволни удари, възникващи в моменти

. Една частица може да се намира в точки с цели координати: ; В точките са разположени отразяващите стени. Всяко натискане премества частицата надясно с вероятност и наляво с вероятност, освен ако частицата не е близо до стена. Ако частицата е близо до стената, тогава всяко натискане я премества с една единица навътре в празнината между стените. Тук виждаме, че този пример за ходене на частица е типична верига на Марков.

Така събитията се наричат състояния на системата, а тестовете се наричат промени в нейните състояния.

Нека сега дефинираме верига на Марков, използвайки нова терминология.

Маркова верига с дискретно време е верига, чиито състояния се променят в определени фиксирани времена.

§2. Хомогенна верига на Марков. Вероятности за преход. Преходна матрица

Определение.Веригата на Марков се нарича хомогенна, ако условната вероятност

(преход от състояние в състояние) не зависи от номера на теста. Следователно, вместо да пишете просто .

Пример 1.Случайна разходка. Нека е на права линия

в точка с целочислена координата има материална частица. В определени моменти от време частицата изпитва удари. Под въздействието на тласък частицата се движи с вероятност една единица надясно и с вероятност една единица наляво. Ясно е, че позицията (координатата) на частица след удар зависи от това къде се е намирала частицата след непосредствено предшестващия удар и не зависи от това как се е движила под въздействието на други предишни удари.

По този начин случайното ходене е пример за хомогенна верига на Марков с дискретно време.