марковские ланцюга
Моделювання економічних систем з використанням марковських випадкових процесів
Основні поняття марківських процесів
Функція ДО називається випадковою, якщо її значення при лю-бом аргументі / є випадковою величиною.
Випадкова функція ДО, аргументом якої є час, називається випадковим процесом.
Марковские процеси є приватним видом випадкових про-процесів. Особливе місце марковських процесів серед інших класів випадкових процесів обумовлено наступними обставинами: для марковських процесів добре розроблений математичний ап-Параті, що дозволяє вирішувати багато практичні завдання; за допомогою на-гою марковських процесів можна описати (точно або наближений-но) поведінка досить складних систем.
Визначення. Випадковий процес, що протікає в ка-кой-якій системі S, називається марковским (або процесом без післядії), якщо він має наступну властивість: для будь-якого моменту часу / 0 ймовірність будь-якого стану системи в майбутньому (при > / 0) залежить, тільки від її стану в сьогоденні (при / = / 0) і не залежить від того, коли і яким об-разом система S прийшла в цей стан.
Класифікація марківських процесів. Класифікація марков-ських випадкових процесів проводиться в залежності від неодмінно-ривності або дискретності безлічі значень функції X (t) і параметра /.
Розрізняють такі основні види марковських випадкових процесів:
• з дискретними станами та дискретним часом (ланцюг Маркова);
• з безперервними станами і дискретним часом (мар-ковские послідовності);
• з дискретними станами і безперервним часом (НЕ-безперервна ланцюг Маркова);
• з безперервним станом і безперервним часом.
У даній роботі будуть розглядатися тільки марковские про-процеси з дискретними станами Sb S2,. Sn.
Ц) аф станів. Марковские процеси з дискретними перебуваючи-нями зручно ілюструвати за допомогою так званого графа станів (рис. 2.1), де кружками позначені стану Si, S2,. системи S, а стрілками - можливі переходи з відбутися у-яния в стан. На графі зазначаються тільки безпосередні переходи, а не переходи через інші стани. Можливі за-тримки в колишньому стані зображують «петлею», т. Е. Стрілкою, спрямованої з даного стану в нього ж. Число станів системи може бути як кінцевим, так і нескінченним (але рахунок-ним). Приклад графа станів системи Ј представлений на рис.2.1.
Мал. 2.1. Граф станів системи S
Марковський випадковий процес з дискретними станами та дискретним часом називають марковської ланцюгом. Для такого про-процесу моменти tx. t2,. коли система 5 може змінювати своє відбутися у-яние, розглядають як послідовні кроки процесу, а в ка-честве аргументу, від якого залежить процес, виступає не час /, а номер кроку 1, 2. до ,. Випадковий процес в цьому випадку ха-рактерізует послідовністюстанів 5 (0), 5 (1), 5 (2). S (k) ,. де 5 (0) - початковий стан системи (перед першим кроком); 5 (1) - стан системи після першого кроку; S (k) - со-стояння системи після Л-го кроку.
Подія, що складається в тому, що відразу після до- го ша-га система знаходиться в стані 5 / (/ = 1, 2.), є випадок-ним подією. Послідовність станів 5 (0), 5 (1). 5 (). можна розглядати як послідовність випадкових подію-тий. Така випадкова послідовність подій називається мар-ської ланцюгом, якщо для кожного кроку ймовірність переходу з лю-бого стану 5 / в будь-який Sj не залежить від того, коли і як систе-ма прийшла в стан 5 /. Початкову-стан 5 (0) може бути заданим заздалегідь або випадковим.
Можливостями станів ланцюга Маркова називаються вероятнос-ти Pt (k) того, що після k-то кроку (і до (до + 1) -го) система 5 буде перебувати в стані 5, (/ = 1,2. П). Очевидно, для будь-якого до
Початковим розподілом ймовірностей марківського ланцюга називаються ється розподіл ймовірностей станів на початку процесу:
В окремому випадку, якщо початковий стан системи S в точ-ності відомо S (0) = Sh то початкова ймовірність РДО) = 1, а всі інші дорівнюють нулю.
Ймовірністю переходу (перехідною ймовірністю) на к-му кроці зі стану Si в стан Sj називається умовна ймовірність то-го, що система S після к-го кроку виявиться в стані Л при ус-ловіі, що безпосередньо перед цим (після к - 1 кроку) вона на-ходілась в стані 5 /.
Оскільки система може перебувати в одному з п станів, то для кожного моменту часу / необхідно задати п ймовірно-стей переходу Ру, які зручно представити у вигляді такої матриці:
де - ймовірність переходу за один крок зі стану Sj в стан S /, - ймовірність затримки системи в стані Sj.
Матриця (2.3) називається перехідною або матрицею перехідних ймовірностей.
Якщо перехідні імовірності не залежать від номера кроку (від часу), а залежать тільки від того, з якого стану в яке здійснюється перехід, то відповідна ланцюг Маркова називаються ється однорідною.
Перехідні ймовірності однорідної марковської ланцюга Ру об-роззують квадратну матрицю розміру п х п. Відзначимо деякі її особливості:
1. Кожен рядок характеризує обраний стан системи, а її елементи являють собою ймовірності всіх можливих переходів за один крок з обраного (з / -го) стану, в тому числі і перехід в самому собі.
2. Елементи стовпців показують ймовірності всіх можли-них переходів системи за один крок в заданий (j-e) стан (інакше кажучи, рядок характеризує ймовірність переходу системи зі стану, стовпець - в стан).
3. Сума ймовірностей кожного рядка дорівнює одиниці, так як переходи утворюють повну групу несумісних подій:
4. По головній діагоналі матриці перехідних ймовірностей стоять ймовірності того, що система не вийде зі стану а залишиться в ньому.
Якщо для однорідної марковської ланцюга задані початкова рас-пределеніе ймовірностей (2.2) і матриця перехідних ймовірностей
(2.3), то ймовірності станів системи визначаються по рекуррентной формулою:
Приклад 2.1. Розглянемо процес функціонування систе-ми автомобіля. Нехай автомобіль (система) протягом однієї сме-ни (діб) може знаходитися в одному з двох станів: исправ-ном і несправному. Граф станів системи представлений на рис. 2.2.
Мал. 2.2. Граф станів автомобіля
В результаті проведення масових спостережень за роботою ав-автомобіля складена наступна матриця ймовірностей переходу:
ймовірність того, що автомобіль залишиться у справному стані;
ймовірність переходу автомобіля зі стану «ІСПР-вен» в стан «несправний»;
ймовірність переходу автомобіля зі стану «неиспр-вен» в стан «справний»;
ймовірність того, що автомобіль залишиться в стані «несправний».
Вектор початкових ймовірностей станів автомобіля заданий
Потрібно визначити ймовірності станів автомобіля через три доби.
Використовуючи матрицю перехідних ймовірностей, визначимо веро-ятность станів РХк) після першого кроку (після першої доби):
Ймовірності станів після другого кроку (після других су-ток) такі:
Ймовірності станів після третього кроку (після третіх су-ток) рівні
Таким чином, після третьої доби автомобіль буде зна-диться в справному стані з ймовірністю 0,819 і в стані «несправний» з ймовірністю 0,181.
Приклад 2.2. В процесі експлуатації ЕОМ може розглядатися-тися як фізична система S, яка в результаті перевірки може виявитися в одному з наступних станів:
ЕОМ повністю справна;
ЕОМ має несправності в оперативній пам'яті, при ко
торих вона може вирішувати завдання;
-ЕВМ має суттєві несправності і може вирішувати
обмежений клас задач;
-ЕВМ повністю вийшла з ладу.
У початковий момент часу ЕОМ повністю справна (со-стояння Sx). Перевірка ЕОМ проводиться в фіксовані мо-менти часу tb t2. ty Процес, що протікає в системі S, може розглядатися як однорідна марковська ланцюг з трьома кроками (перша, друга, третя перевірки ЕОМ). Матриця перехідних веро-ятность має вигляд:
Визначте ймовірність станів ЕОМ після трьох перевірок.
Граф станів має вигляд, показаний на рис. 2.3. Проти каж-дой стрілки проставлена відповідна ймовірність переходу. Початкові ймовірності станів
Мал. 2.3. Граф станів ЕОМ
За формулою (2.5), враховуючи в сумі ймовірностей тільки ті з-стояння, з яких можливий безпосередній перехід в даний стан, знаходимо:
Отже, ймовірність станів ЕОМ після трьох перевірок сліду-ющие: