ведення в теорію ланцюгів Маркова. (Markov schain)
Діскретні ланцюги Маркова. Говорітімемо, что завдань дискретних ланцюг Маркова, если для послідовності Випадкове величин віконується Рівність.
Це означає, что потік Випадкове величин візначається только вірогідністю переходу від попередня значення віпадкової величину до подалі. Знаючі початковий Розподіл вірогідності, можна найти Розподіл на будь-якому кроці. Величини in можна інтерпретуваті як номери станів деякої дінамічної системи з дискретністю безліччю станів (типу кінцевого автомата). Если вірогідність переходів НЕ поклади від номера Крока, то такий ланцюг Маркова назівається одноріднім и ее визначення задається набором вірогідності.
Для однорідного Марківського ланцюга можна візначіті вірогідність переходу Із стану i в стан j за m кроків
Ланцюг Маркова назівається тією, что не наводитися, если Кожний ее стан может буті досягнутості з будь-которого Іншого стану. Стан i назівається поглінаючім, если для него pii=1.
Стан назівається поворотним, если вірогідність попадання в него за кінцеве число кроків рівна одиниці. У ІНШОМУ випадка стан відносіться до неповоротних. Поворотний стан может буті періодічнім и аперіодічнім залежних від наявності кратних кроків повернення. Введемо вірогідність повернення в стан i через n кроків после відходу з цього стану:
Смороду дозволяють візначіті Середнє число кроків або, інакше Кажучи, середній годину повернення:.
Стан назівається поворотним Нульовий, если середній годину повернення в него Рівно нескінченності, и поворотним ненульовім, если цею годину Звичайне. Відомі две Важливі теореми:
Теорема 1
Стані ланцюга Маркова, что не наводитися, або всі неповоротні, або всі поворотні нульові, або всі поворотні ненульові. У разі періодічного ланцюга всі стани мают одна и тієї ж период.
Друга теорема Розглядає вірогідність Досягнення станів в стаціонарному (тобто НЕ залежних від початкових розподілу вірогідності) режімі. Відповідній Розподіл вірогідності такоже назівають стаціонарнім. Знаходження стаціонарного розподілу вірогідності Досягнення станів один з основних завдань Теорії телетрафіка.
Теорема 2
Для ланцюга Маркова, что не наводитися и аперіодічної, всегда існує гранична вірогідність, що не залежна від початково розподілу вірогідності. Більш того, має місце один з Наступний двох можливіть:
А) всі стани ланцюга неповоротні або всі поворотні нульові, и тоді вся гранична вірогідність рівна нулю и стаціонарного стану НЕ існує;
Б) всі стани поворотні ненульові и тоді існує стаціонарний Розподіл вірогідності:
Стан назівається ергодічнім, если воно аперіодічне и поворотно-ненульове. Если всі стани ланцюга Маркова ергодічні, то весь ланцюг назівається ергодічнім. Граничну вірогідність ергодічного ланцюга Маркова назівають вірогідністю стану рівновагі, маючі на увазі, что залежність від початкових розподілу вірогідності Повністю відсутня.
Ланцюг Маркова з кінцевім числом станів (кінцевій ланцюг), зручне зображаті у виде орієнтованого графа, званого діаграмою переходів. Вершини графа асоціюються Із станами, а ребра з вірогідністю переходів.
Обчислення вірогідності Досягнення станів проводитися прямим методом або помощью z-превращение.
Ланцюг Маркова
Введемо матрицю вірогідності переходів и вектор-рядок вірогідності на кроці n
.
Розподіл вірогідності на довільному кроці тоді підкорятіметься матричному співвідношенню:
.
Воно дозволяє рекурентное обчіслюваті всю вірогідність станів. Для знаходження граничного розподілу (стаціонарного) нужно вірішіті Рівняння:
ЙОГО можна вірішуваті як систему лінійніх рівнянь алгебри, если ланцюг кінцевій.
Для прикладу (малий. 1) маємо:
.
и решение матричного Рівняння зводу до решение системи трьох рівнянь:
КОЕФІЦІЄНТИ Першого Рівняння в Цій сістемі доповнюють до одиниці суму Коефіцієнтів іншого и третього рівнянь; це свідчіть про лінійну залежність между ними. Тому для вирішенню системи рівнянь нужно ввести Додатковий нормуючу умову. У даного прікладі:.
Вірішуючі систему отриманий рівнянь, маємо:
Рівняння для вірогідності Досягнення стану в перехідному режімі вірішіті значний важче. Деяк Спрощення можна досягті, вікорістовуючі z - превращение. Застосуємо его до Рівняння для перехідної вірогідності
.
Позначаючі відповідні превращение, отрімаємо:.
Всі отрімані тут математичні результати відносіліся до однорідніх марківських процесів, де вірогідність переходів НЕ поклади від годині. У більш загально випадка така залежність має місце.
Розглянемо вірогідність переходу системи Із стану i на m-том кроці в стан...
