Класифікація марківських випадкових процесів. Поняття про марківський процес

Випадковим процесом називається безліч чи сімейство випадкових величинзначення яких індексуються тимчасовим параметром. Наприклад, кількість студентів в аудиторії, атмосферний тиск або температура цієї аудиторії як функції часу є випадковими процесами.

Випадкові процеси знаходять широке застосування щодо складних стохастичних систем як адекватні математичні моделі процесу функціонування таких систем.

Основними поняттями для випадкових процесів є поняття стану процесуі переходуйого з одного стану до іншого.

Значення змінних, які описують випадковий процес, в даний момент називаються станомвипадковогопроцесу. Випадковий процес здійснює перехід з одного стану в інший, якщо значення змінних, що задають один стан, змінюються значення, які визначають інший стан.

Число можливих станів (простір станів) випадкового процесу може бути кінцевим або нескінченним. Якщо число можливих станів звичайно або рахункове (всім можливим станам можуть бути присвоєні порядкові номери), то випадковий процес називається процесом із дискретними станами. Наприклад, кількість покупців у магазині, кількість клієнтів у банку протягом дня описуються випадковими процесами з дискретними станами.

Якщо змінні, що описують випадковий процес, можуть набувати будь-яких значень з кінцевого або нескінченного безперервного інтервалу, а, значить, кількість станів незліченна, то випадковий процес називається процесом з безперервними станами. Наприклад, температура повітря протягом доби є випадковим процесом із безперервними станами.

Для випадкових процесів з дискретними станами характерні стрибкоподібні переходи з одного стану в інший, тоді як у процесах з безперервними станами переходи є плавними. Далі розглядатимемо лише процеси з дискретними станами, яких часто називають ланцюгами.

Позначимо через g(t) випадковий процес з дискретними станами, а можливі значення g(t), тобто. можливі стани ланцюга - через символи E 0 , E 1 , E 2 , … . Іноді позначення дискретних станів використовують числа 0, 1, 2,... з натурального ряду.

Випадковий процес g(t) називається процесомздискретнимчасом, якщо переходи процесу зі стану до стану можливі лише у суворо визначені, заздалегідь фіксовані моменти часу t 0 , t 1 , t 2 , … . Якщо перехід процесу зі стану на стан можливий у будь-який, заздалегідь невідомий момент часу, то випадковий процес називається процесомз безперервнимчасом. У першому випадку очевидно, що інтервали часу між переходами є детермінованими, а в другому - випадковими величинами.

Процес з дискретним часом має місце або коли структура системи, яка описується цим процесом, така, що її стану можуть змінюватися тільки в заздалегідь визначені моменти часу, або коли передбачається, що для опису процесу (системи) достатньо знати стану в певні моменти часу. Тоді ці моменти можна пронумерувати та говорити про стан E iу момент часу t i .

Випадкові процеси з дискретними станами можуть зображуватися як графа переходів (чи станів), у якому вершини відповідають станам, а орієнтовані дуги - переходам з одного стану до іншого. Якщо зі стану E iможливий перехід лише в один стан E j, то цей факт на графі переходів відбивається дугою, спрямованою з вершини E iу вершину E j(Рис.1, а). Переходи з одного стану в кілька інших станів та з кількох станів в один стан відбивається на графі переходів, як показано на рис.1, б і 1, ст.

Структура та класифікація систем масового обслуговування

Системи масового обслуговування

Нерідко виникає необхідність у вирішенні ймовірнісних завдань, пов'язаних із системами масового обслуговування (СМО), прикладами яких можуть бути:

Білетні каси;

Ремонтні майстерні;

торговельні, транспортні, енергетичні системи;

Системи зв'язку;

Спільність таких систем виявляється у єдності математичних методів і моделей, застосовуваних щодо їх діяльності.

Мал. 4.1. Основні сфери застосування ТМО

На вхід до СМО надходить потік вимог обслуговування. Наприклад, клієнти чи пацієнти, поломки в устаткуванні, телефонні дзвінки. Вимоги надходять нерегулярно, у довільні моменти часу. Випадковий характер має і тривалість обслуговування. Це створює нерегулярність у роботі СМО, спричиняє її перевантаження та недовантаження.

Системи масового обслуговування мають різну структуру, але зазвичай у них можна виділити чотири основні елементи:

1. Вхідний потік вимог.

2. Накопичувач (черга).

3. Прилади (канали обслуговування).

4. Потік, що виходить.

Мал. 4.2. Загальна схема систем масового обслуговування

Мал. 4.3. Модель роботи системи

(стрілками показані моменти надходження вимог до

систему, прямокутниками – час обслуговування)

На рис.4.3 представлена ​​модель роботи системи з регулярним потоком вимог. Оскільки відомий проміжок між надходженнями вимог, час обслуговування вибрано так, щоб повністю завантажити систему. Для системи зі стохастичним потоком вимог ситуація зовсім інша – вимоги приходять у різні моменти часу та час обслуговування теж є випадковою величиною, яка може бути описана певним законом розподілу (рис.4.3 б).

Залежно від правил освіти черги розрізняють такі СМО:

1) системи з відмовами , у яких за зайнятості всіх каналів обслуговування заявка залишає систему необслуженной;

2) системи з необмеженою чергою , в яких заявка постає в чергу, якщо на момент її надходження всі канали обслуговування були зайняті;

3) системи з очікуванням та обмеженою чергою , в яких час очікування обмежено будь-якими умовами або існують обмеження на кількість заявок, що стоять у черзі.

Розглянемо показники вхідного потоку вимог.

Потік вимог називається стаціонарним якщо ймовірність попадання того чи іншого числа подій на ділянку часу певної довжини залежить тільки від довжини цієї ділянки.

Потік подій називається потоком без наслідків , якщо кількість подій, які потрапляють на певну ділянку часу, залежить від кількості подій, які потрапляють інші.

Потік подій називається ординарним , якщо неможливе одночасне надходження двох чи більше подій.

Потік вимог називається пуассонівським (або найпростішим), якщо він має три властивості: стаціонарний, ординарен і не має наслідків. Назва пов'язана з тим, що при виконанні зазначених умов кількість подій, що потрапляють на фіксований інтервал часу, буде розподілено за законом Пуассона.

Інтенсивністюпотоку заявок називається середня кількість заявок, що надходять з потоку за одиницю часу.

Для стаціонарного потоку інтенсивність стала. Якщо τ – середнє значення інтервалу часу між двома сусідніми заявками, то у разі пуассонівського потоку ймовірність надходження на обслуговування mзаявок за проміжок часу tвизначається згідно із законом Пуассона:

Час між сусідніми заявками розподілено за експоненційним законом із щільністю ймовірності

Час обслуговування є випадковою величиною і підпорядковується показовому закону розподілу із щільністю ймовірності де μ – інтенсивність потоку обслуговування, тобто. середня кількість заявок, що обслуговуються в одиницю часу,

Відношення інтенсивності вхідного потоку до інтенсивності потоку обслуговування називається завантаженням системи

Система масового обслуговування є системою дискретного типуз кінцевим чи рахунковим безліччю станів, а перехід системи з одного стану в інший відбувається стрибком, коли здійснюється якась подія.

Процес називається процесом із дискретними станами якщо його можливі стани можна заздалегідь перенумерувати, і перехід системи зі стану в стан відбувається практично миттєво.

Такі процеси бувають двох типів: з дискретним чи безперервним часом.

У разі дискретного часу переходи зі стану в стан можуть відбуватися в певні моменти часу. Процеси з безперервним часом відрізняються тим, що перехід системи у новий стан можливий будь-якої миті часу.

Випадковим процесом називається відповідність, у якому кожному значенню аргументу (у разі – моменту з проміжку часу проведеного досвіду) ставиться у відповідність випадкова величина (у разі – стан СМО). Випадковою величиною називається величина, яка в результаті досвіду може прийняти одне, але невідоме заздалегідь, яке саме числове значення з даної числової множини.

Тож вирішення завдань теорії масового обслуговування необхідно цей випадковий процес вивчити, тобто. побудувати та проаналізувати його математичну модель.

Випадковий процесназивається марківським Якщо для будь-якого моменту часу ймовірнісні характеристики процесу в майбутньому залежать тільки від його стану в даний момент і не залежать від того, коли і як система прийшла в цей стан.

Переходи системи зі стану до стану відбувається під впливом якихось потоків (потік заявок, потік відмов). Якщо всі потоки подій, що приводять систему в новий стан, – найпростіші пуассонівські, то процес, що протікає в системі, буде марківським, оскільки найпростіший потік не має наслідку: у ньому майбутнє не залежить від минулого. - Група шахових фігур. Стан системи характеризується числом постатей противника, що збереглися на дошці в момент . Імовірність того, що в момент матеріальна перевага буде на боці одного з противників, залежить в першу чергу від того, в якому стані знаходиться система в даний момент, а не від того, коли і в якій послідовності зникли фігури з дошки до моменту.

Марківські довільні процеси.

Припустимо, що нам необхідно вивчити деяку «фізичну систему» S(процес функціонування якої можна описати явним чином), яка може з часом змінювати свій стан (переходить з одного стану до іншого) заздалегідь невідомим, випадковим чином. Під «фізичною системою» можна розуміти будь-що: технічний пристрій, групу таких пристроїв, підприємство, галузь промисловості, живий організм, популяцію тощо.

Вважаємо, що досліджувана система Sможе бути описана деякою кількістю можливих, заздалегідь відомих станів системи S i, які можна визначити виходячи з « фізичної природи» Досліджуваного процесу функціонування системи, тобто. .

- i-то стан системи залежить від kпараметрів.

Слід врахувати, що перехід із стану S i в стан S j носить стохастичний характер. Функціонування системи починаємо розглядати з початкового стану S 0 , якому відповідає момент часу t 0 . Тобто те, що було з системою до моменту часу t 0 відноситься до «минулого оною», до передісторії.

Визначення: Випадковий процес, що протікає в системі, називається марківським, якщо для будь-якого моменту часу t 0 ймовірнісні характеристики процесу в майбутньому залежать тільки від його стану в даний момент t 0 і не залежать від того, коли і як система прийшла до цього стану.

Вважаємо, що стан системи описується функцією S(t), аргумент цієї функції, - час tбезперервно, відомі моменти часу переходу системи з одного стану до іншого t: t 1 <t 2 < … <t n. Причому перехід із одного стану до іншого відбувається «стрибком», практично миттєво.

Прийшли до того, що процесу функціонування системи ставиться у відповідність ланцюг дискретних станів: S 1 ® S 2 ® … ® S n-1 ® S n (послідовний перехід із одного стану до іншого, без «перескакування» через будь-який стан). Тобто, розглянута система описується марковським випадковим процесом з дискретними станами та безперервним часом.

З теорії ймовірності ми знаємо, що функція щільності ймовірності для n-го стану шукається як спільна функція щільності для всієї «передісторії» процесу приходу системи на цей стан: .

Насправді марківські процеси у чистому вигляді не зустрічаються, але нерідко доводиться мати справу з процесами, котрим вплив передісторії можна знехтувати. Для вивчення таких процесів можна застосовувати марківські моделі.

При переході розгляду процесу як марковського аналітичний опис моделі спрощується, оскільки вважаємо, що стан системи залежить лише від попереднього стану: .

Ланцюги Маркова задаються набором чітко визначених станів: . По тому, коли і яким чином відбуваються «переходи», ланцюги Маркова діляться на дискретні, для яких час переходу з одного стану в інший фіксований, і визначається ймовірністю цього переходу, і безперервні, для яких дискретні стани, час безперервно і переходи з одного стану в інше відбуваються у випадкові, заздалегідь не відомі моменти часу.

При аналізі випадкових процесів із дискретними станами зручно користуватися геометричною схемою – так званим графом станів.

Визначення. Граф – це сукупність безлічі вершин Vі безліч упорядкованих пар вершин A={(a 1 a i) ( a 2 a j) … ), елементи якого називаються ребрами G(V,A).

Станам системи ставляться у відповідність вершини графа, а переходам з одного стану до іншого – верви із зазначенням «напряму протікання» процесу.

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

Приклад №1. Теа технічна експлуатація автомобіля.

Спрощена модель ТЕА має на увазі наявність хоча б чотирьох наступних станів: S 1 – діагностика стану автомобіля, S 2 - робота на лінії (автомобіль справний), S 3 – технічне обслуговування, S 4 – усунення несправності (ремонт).

Відповідний даній системі розмічений граф

m ij щільність ймовірності переходу зі стану S iу стан S j (S i® S j), де P ij(D t) – ймовірність того, що за проміжок часу Dt відбудеться цей перехід.

Для малих значень Dt справедлива наступна наближена рівність.

Значення ймовірностей переходів визначаються із системи диференціальних рівнянь (Колмогорова) за такими правилами:

1) кожній вершині ставиться у відповідність відповідний стан, що описується ймовірністю знаходження системи в оном, тому кількість станів визначає кількість рівнянь у системі;

2) у лівій частині рівняння – похідна ймовірності відповідного стану;

3) у правій частині стільки доданків, скільки переходів (гілок) у розміченому графі пов'язано з цим станом;

4) кожен елемент правої частини дорівнює добутку густини ймовірності переходу на густину ймовірності того стану, з якого здійснювався перехід;

5) у правій частині зі знаком «+» йдуть (складаються) елементи, що описують попадання системи в даний стан, та зі знаком «-» (віднімаються) елементи, що описують «вихід» системи з цього стану;

6) для спрощення «розв'язності» в систему вводиться норми рівняння, що описує повну групу подій: , де N-кількість вершин у розміченому графі станів.

Ця система рівнянь буде легше вирішувана у разі, коли вона визначає стаціонарний процес роботи досліджуваної технічної системи (зазвичай входження системи в стаціонарний режим функціонування займає від 2-х до 4-х тактів).

Насправді вважаємо, що припущення про стаціонарності функціонування системи правомірно, якщо час функціонування системи загалом значно вище, ніж (20?40)×тактов роботи системи («послідовне» одинарне проходження гілками графа).

Стаціонарність режиму роботи передбачає рівність нулю від похідних за часом ймовірностей стану, тобто. .

і його рішення вже не становить особливої ​​складності.

Система рівнянь по Колмогорову дозволяє вирішити завдання знаходження значень ймовірностей для стаціонарного режиму (фінальних ймовірностей) за відомими щільностями ймовірностей переходів по гілках графа, як і зворотну їй, тобто. знаходження щільності ймовірностей при заданих фінальних ймовірностях.

Приклад №2.

Розглянемо технічну систему S, що складається з двох паралельно працюючих вузлів (два пости на СТО, два заправні автомати на АЗС). Вважатимемо, що переходи системи з одного стану в інший відбуваються миттєво, у випадкові моменти часу. Як тільки вузол виходить з ладу, він миттєво надходить на ремонт і після приведення його в робочий стан він також миттєво починає експлуатуватися.

Вважаємо, що дана система повністю описується всього чотирма станами: S 0 – обидва вузли справні; S 1 – перший вузол ремонтується, другий справний; S 2 – другий вузол ремонтується, перший справний; S 3 – ремонтуються обидва вузли.

l 1 , l 2 – щільність ймовірності виходу з ладу першого та другого посту, m 1 , m 2 – щільність ймовірності відновлення першого та другого вузла відповідно.

Складемо систему диференціальних рівнянь по Колмогорову для можливостей станів цієї системи.

Щоб вирішити рівняння Колмогорова та знайти чисельні значення для ймовірностей відповідних станів, необхідно встановити початкові умови.

Вважатимемо, що у початковий час обидва вузла досліджуваної системи справні, система перебуває у стані S 0 , тобто. P 0 (t=0)=1, проте інші початкові ймовірності дорівнюють нулю: P 1 (0)=P 2 (0)=P 3 (0)=0.

Дана система рівнянь легко вирішується у разі, якщо система функціонує в режимі, що встановився, і всі процеси, що протікають в ній, стаціонарні.

Стаціонарність режиму роботи передбачає рівність нулю від похідних за часом від ймовірностей стану, тобто, i=1, 2, … , n, , де n- Кількість можливих станів. А з урахуванням повної групи подій додається рівняння

Остання, так звана нормувальна умова, дозволяє виключити із системи одне з рівнянь.

Вирішимо цю систему за наступних даних: l 1 =1, l 2 =2, m 1 =2, m 2 =3. Запишемо систему без четвертого рівняння.

Вирішуючи їх, отримаємо: P 0 =0,4; P 1 =0,2; P 2 @0,27; P 3 @0,13.

Тобто. у стаціонарному режимі роботи наша система в середньому 40% часу перебуватиме в стані S 0 – обидва вузли справні, і т.д.

Значення цих фінальних можливостей можуть допомогти оцінити середню ефективність роботи системи та завантаження ремонтних органів. Припустимо, що система Sв стані S 0 приносить дохід 8 умовних одиниць (у.о.) в одиницю часу, може S 1 3у.о., в S 2 5у.о., а в стані S 3 не дає доходу.

Розглянемо можливі стани марківських

процесів.

0 Досяжні стани: стан / призводить до стану j(позначають /->/), якщо існує шлях i 0 =i, i=jтакий, що всі перехідні ймовірності я, - д j > 0, до = 0,..., п-1.

Мал. 12.13.

На рис. 12.13 показаний шлях із одного стану в інший. Кажуть, що стан jможна досягти зі стану /.

Про Сполучені стани: стани /" та jсполучені (позначають //), якщо i~>jі у-»/- Сполучені стани можуть бути згруповані в клас еквівалентності. Усередині класу всі стани сполучені. Два стани різних класів не повідомляються друг з одним. Такі класи називаються ненаведеними.Марківський ланцюг зі станами, що утворюють ненаведений клас, називається ненаведеною.

Мал. 12.14.

Усі стани ергодичного ланцюга Маркова сполучаються і утворюють ергодичну безліч станів. Марківський ланцюг називається ергодичної, якщо всі ергодичні стану (рис. 12.14).

Про Неповоротні стани: стан доназивається неповоротним, якщо існує такий стан j (До ф j)і така кількість кроків п,що д., («)> 0, 71., (т)= Для всіх т>п.Бувають випадки, коли ланцюг

складається з кількох ергодичних множин, що не повідомляються один з одним (багатокомпонентний граф). Потрапивши в одну ергодичну безліч, процес ніколи не зможе його покинути. Ця множина по відношенню до початкового є безповоротною, а входять до неї стану називаються неповоротними.

Про Поглинаючий стан: стан / називається поглинаючимтоді і лише тоді, коли я та (п)= 1 для будь-якого п.Безліч станів називається замкнутим,якщо жодна з них не призводить до стану, що не входить до цієї множини. Якщо ергодична множина складається з одного стану, то цей стан поглинає, так що, потрапивши в нього, вже не можна з нього вийти. Якщо серед усіх станів ланцюга Маркова є хоча б одне поглинаюче, то такий ланцюг називається поглинаючої.

Кожен стан може бути рекурентно, що проходить або повторюється.

Про Стан, що проходить: стан /" буде проходить, якщо існує ненульова ймовірність того, що система ніколи не повернеться в нього. Підмножина станів називається транзитивним(що проходить), якщо можна увійти до цього підмножини і вийти з нього. Транзитивні стани можуть бути відвідані лише кінцеве число разів.

Про Рекурентний стан: стан буде рекурентним, якщо ймовірність повернення дорівнює 1. Рекурентні стани можуть бути класифіковані в залежності від часу першого повернення в цей стан: якщо цей час менший за нескінченність, то стану називаються позитивно рекурентні; якщо час дорівнює нескінченності, то нуль рекурентні.Рекурентні стани можуть бути періодичнимиі неперіодичними.Неперіодичні позитивно-рекурентні стани називаються ергодичними.

Залежно від типу станів ланцюга Маркова матрицю перехідних ймовірностей можна у тому чи іншому вигляді шляхом перестановки рядків і стовпців. Якщо матрицю перехідних ймовірностей можна подати у вигляді блоків

то процес, що виходить з деякого стану, що належить множині станів S, ніколи не зможе опинитися за будь-яке число кроків у стані, що належить множині Q, і навпаки. Матриця П у своїй називається розкладається,а два розглянуті безлічі станів замкнутими.Це твердження очевидне, оскільки

то для всіх парних ступенів матриця буде блочно-діагональною, а для непарних – мати первісний вигляд. Наприклад:

Процес по черзі переходитиме від станів, що належать Т, до станів, що належать R, і назад. Такий процес буде періодичним.

Якщо матриця перехідних ймовірностей має вигляд

то ймовірність того, що процес перебуватиме в одному із станів, що належать Q, не зросте зі збільшенням числа кроків. Перехід з будь-якого стану, що належить Q, в один із станів, що належать S, можливий, якщо R ф 0 але зворотний перехід відбутися не може. Отже, стани, відповідні Q, неповоротні, a S - поглинаючі.

Матрицю перехідних ймовірностей поглинаючого ланцюга записують у наступній канонічній формі:

Підматриця 0 складається з одних нулів, підматриця I - одинична матриця поглинаючих станів, підматриця Q описує поведінку процесу до виходу з безлічі неповоротних станів, підматриця R відповідає переходам з безповоротних станів поглинають.

Угода про використання матеріалів сайту

Просимо використовувати роботи, опубліковані на сайті, виключно в особистих цілях. Публікацію матеріалів на інших сайтах заборонено.
Ця робота (і всі інші) доступна для завантаження абсолютно безкоштовно. Подумки можете подякувати її автору та колективу сайту.

Надіслати свою гарну роботу до бази знань просто. Використовуйте форму, розташовану нижче

Студенти, аспіранти, молоді вчені, які використовують базу знань у своєму навчанні та роботі, будуть вам дуже вдячні.

Подібні документи

Основні поняття теорії марківських кіл. Теорія про граничні ймовірності. Області застосування ланцюгів Маркова. Керовані ланцюги Маркова. Вибір стратегії. Оптимальна стратегія є марківською – може залежати ще й від часу прийняття рішення.

реферат, доданий 08.03.2004


Ланцюг Маркова як простий випадок послідовності випадкових подій, сфери її застосування. Теорема про граничні ймовірності у ланцюзі Маркова, формула рівності Маркова. Приклади для типового та однорідного ланцюга Маркова, для знаходження матриці переходу.

курсова робота , доданий 20.04.2011


Основні поняття теорії марківських ланцюгів, їх використання теорії масового обслуговування до розрахунку розподілу ймовірностей числа зайнятих приладів у системі. Методика розв'язання задачі про найкращому виборі. Поняття поворотних та неповоротних станів.

курсова робота , доданий 06.11.2011


Ланцюги Маркова як узагальнення схеми Бернуллі, опис послідовності випадкових подій з кінцевим чи лічильним нескінченним числом результатів; властивість ланцюгів, їхня актуальність в інформатиці; Використання: визначення авторства тексту, використання PageRank.

дипломна робота , доданий 19.05.2011


Визначення випадкового процесу в математиці, ряд термінів та понять, що описують механізм цього процесу. Марківські, стаціонарні випадкові процеси із дискретними станами. Особливості ергодичного властивості стаціонарних випадкових процесів.

реферат, доданий 15.05.2010


Схожість послідовностей випадкових величин. Центральна гранична теорема для незалежних однаково розподілених випадкових величин. Основні завдання математичної статистики, їхня характеристика. Перевірка гіпотез за критерієм однорідності Смирнова.

курсова робота , доданий 13.11.2012


Класифікація випадкових подій. Функція розподілу. Числові характеристики дискретних випадкових величин. Закон рівномірного розподілу імовірностей. Розподіл Стьюдента. Завдання математичної статистики. Оцінки параметрів сукупності.