Материал: Методические указания к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности «Компьютерная безопасность». Поздышева О.В., Остапенко А.Г

В случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вернуться в него.

2. Возвратное множество (рис. 3).

Рис. 3. Возвратное множество

В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.

3. Эргодическое множество (рис. 4).

Рис. 4. Эргодическое множество

В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4

4. Поглощающее множество (рис. 5)

Рис. 5. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие Марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений.

Основным признаком дискретной Марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими [21].

Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых выше, множеств состояний Марковские цепи могут быть поглощающими, если имеется хотя бы одно поглощающее состояние, или эргодическими, если переходные вероятности образуют эргодическое множество. В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через

5

определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.

1.1. Марковский процесс с дискретным временем

Итак, модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние), как показано на рис. 6.

Рис. 6. Пример графа переходов

Каждый переход характеризуется вероятностью перехода Pij. Вероятность Pij показывает, как часто после попадания в i-е состояние осуществляется затем переход в j-е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода [21].

Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие со-

6

стояния должна быть всегда равна 1, как показано на рис.

7) .

Рис. 7. Фрагмент графа переходов (переходы из i-го состояния являются полной группой случайных событий)

Реализация Марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние, как показано на рис. 8. Данный граф является примером Марковской цепи, смоделированной по Марковскому графу, изображенному на рис. 7. Данная цепь является случайной последовательностью и может иметь также и другие варианты реализации.

Рис. 8. Пример Марковской цепи

Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:

7