РЕФЕРАТ

На тему:

«Моделі систем масового обслуговування. Класифікація систем масового обслуговування»

Математичне введення в теорію ланцюгів Маркова. (Markov’s chain)

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

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

Для однорідного Марківського ланцюга можна визначити вірогідність переходу із стану i в стан j за m кроків

Ланцюг Маркова називається тією, що не приводиться, якщо кожний її стан може бути досягнутий з будь-якого іншого стану. Стан i називається поглинаючим, якщо для нього pii =1.

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

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

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

Теорема 1

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

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

Теорема 2

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

А) всі стани ланцюга неповоротні або всі поворотні нульові, і тоді вся гранична вірогідність рівна нулю і стаціонарного стану не існує;

Б) всі стани поворотні ненульові і тоді існує стаціонарний розподіл вірогідності:

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

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