Марковские ланцюга - студопедія

Марковський випадковий процес з дискретними станами та дискретним часом називають марковської ланцюгом. Для такого процесу моменти t1. t2. ..., коли система S може змінювати свій стан, розглядають як послідовні кроки процесу, а в якості аргументу, від якого залежить процес, виступає не час t. а номер кроку 1, 2. k. Випадковий процес в цьому випадку характеризується послідовністю станів S (0). S (1). S (2). S (k). де S (0) - початковий стан системи (перед першим кроком); S (1) - стан системи після першого кроку; S (k) - стан системи після k -го кроку.

Подія S (k) = Si>, що складається в тому, що відразу після k -го кроку система знаходиться в стані Si (i = 1, 2.), є випадковою подією. Послідовність станів S (0). S (1). S (k). можна розглядати як послідовність випадкових подій. Така випадкова послідовність подій називається марковської ланцюгом. якщо для кожного кроку ймовірність переходу з будь-якого стану Si в будь-який Sj не залежить від того, коли і як система прийшла в стан Si. Початковий стан S (0) може бути заданим заздалегідь або випадковим.

Можливостями станів ланцюга Маркова називаються ймовірності Pi (k) того, що після k -го кроку (і до (k + 1) -го) система S буде знаходитися в стані Si (i = 1, 2. n). Очевидно, для любою k.

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

В окремому випадку, якщо початковий стан системи S в точності відомо S (0) = Si. то початкова ймовірність Рi (0) = 1, а всі інші дорівнюють нулю.

Ймовірністю переходу (перехідною ймовірністю) на k-му кроці зі стану Si в стан Sj називається умовна ймовірність того, що система S після k -го кроку виявиться в стані Sj за умови, що безпосередньо перед цим (після k - 1 кроку) вона перебувала в стані Si.

Оскільки система може перебувати в одному з n станів, то для кожного моменту часу t необхідно задати n 2 ймовірностей переходу Pij. які зручно представити у вигляді такої матриці:

де Рij - ймовірність переходу за один крок зі стану Si в стан Sj;

РII - ймовірність затримки системи в стані Si.

Така матриця називається перехідною або матрицею перехідних ймовірностей.

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

Перехідні ймовірності однорідного Марківського ланцюга Рij утворюють квадратну матрицю розміру n m. Відзначимо деякі її особливості.

1. Кожен рядок характеризує обраний стан системи, а її елементи являють собою ймовірності всіх можливих переходів за один крок з обраного (з i -го) стану, в тому числі і перехід в самому собі.

2. Елементи стовпців показують ймовірності всіх можливих переходів системи за один крок в заданий (j -е) стан (інакше кажучи, рядок характеризує ймовірність переходу системи зі стану, стовпець - в стан).

3. Сума ймовірностей кожного рядка дорівнює одиниці, так як переходи утворюють повну групу несумісних подій:

4. По головній діагоналі матриці перехідних ймовірностей стоять ймовірності РII того, що система не вийде зі стану Si. а залишиться в ньому.

Якщо для однорідного Марківського ланцюга задані початковий розподіл ймовірностей і матриця перехідних ймовірностей. то ймовірності станів системи Pi (k) (i, j = 1, 2, ..., n) визначаються по рекуррентной формулою:

Приклад 1. Розглянемо процес функціонування системи - автомобіль. Нехай автомобіль (система) протягом однієї зміни (доби) може знаходитися в одному з двох станів: справному (S1) і несправному (S2). Граф станів системи представлений на рис. 3.2.

Мал. 3.2.Граф станів автомобіля

В результаті проведення масових спостережень за роботою автомобіля складена наступна матриця ймовірностей переходу:

де P11 = 0,8 - ймовірність того, що автомобіль залишиться у справному стані;

P12 = 0,2 - ймовірність переходу автомобіля зі стану «справний» в стан «несправний»;

P21 = 0,9 - ймовірність переходу автомобіля зі стану «несправний» в стан «справний»;

P22 = 0,1 - ймовірність того, що автомобіль залишиться в стані «несправний».

Вектор початкових ймовірностей станів автомобіля заданий. тобто Р1 (0) = 0 і Р2 (0) = 1.

Потрібно визначити ймовірності станів автомобіля через три доби.

Використовуючи матрицю перехідних ймовірностей і формулу (3.1), визначимо ймовірності станів Pi (k) після першого кроку (після першої доби):

Ймовірності станів після другого кроку (після другої доби) такі:

Ймовірності станів після третього кроку (після третьої доби) рівні

Таким чином, після третьої доби автомобіль буде знаходитися в справному стані з ймовірністю 0,819 і в стані «несправний» з ймовірністю 0,181.

Приклад 2. У процесі експлуатації ЕОМ може розглядатися як фізична система S. яка в результаті перевірки може виявитися в одному з наступних станів: S1 - ЕОМ повністю справна; S2 - ЕОМ має несправності в оперативній пам'яті, при яких вона може вирішувати завдання; S3 - ЕОМ має суттєві несправності і може вирішувати обмежений клас задач; S4 - ЕОМ повністю вийшла з ладу.

У початковий момент часу ЕОМ повністю справна (стан S1). Перевірка ЕОМ проводиться в фіксовані моменти часу t1. t2. t3. Процес, що протікає в системі S. може розглядатися як однорідна марковська ланцюг з трьома кроками (перша, друга, третя перевірки ЕОМ). Матриця перехідних ймовірностей має вигляд

Визначити ймовірності станів ЕОМ після трьох перевірок.

Рішення. Граф станів має вигляд, показаний на рис. 3.3. Проти кожної стрілки проставлена ​​відповідна ймовірність переходу. Початкові ймовірності станів P1 (0) = 1, P2 (0) = P3 (0) = P4 (0) = 0.

Мал. 3.3. Граф станів ЕОМ

За формулою (3.1), враховуючи в сумі ймовірностей тільки ті стану, з яких можливий безпосередній перехід в даний стан, знаходимо:

Отже, ймовірність станів ЕОМ після трьох перевірок такі: P1 (3) = 0,027; P2 (3) = 0,076; P3 (3) = 0,217; P4 (3) = 0,680.

Завдання 1. За деякою мети ведеться стрілянина чотирма пострілами в моменти часу t1. t2. t3. t4.

Можливі стану системи: S1 - мета неушкоджена; S2 - мета незначно пошкоджена; S3 - мета отримала значні пошкодження; S4 - мета повністю вражена. У початковий момент часу мета знаходиться в стані S1. Визначити ймовірності станів мети після чотирьох пострілів якщо матриця перехідних ймовірностей має вигляд: