- •Введение
- •Глава 1. Основные понятия теории моделирования
- •1.1. Классификация видов моделирования
- •1.2. Жизненный цикл компьютерной модели
- •1.3. Вычислительный эксперимент
- •1.4. Наиболее известные методологии и системы компьютерного моделирования
- •1.4.1. Универсальные системы моделирования
- •1.4.2.Системы моделирования бизнес-процессов
- •1.5. О моделировании вычислительных систем
- •Глава 2. Введение в сети Петри
- •2.1. Обыкновенные сети Петри
- •2.1.1. Формальное определение
- •2.1.2. Графы сетей Петри
- •2.1.3. Пространство состояний сети Петри
- •2.1.4. Основные свойства сетей Петри
- •2.1.5. Некоторые обобщения сетей Петри
- •Инварианты сетей Петри
- •2.2. Раскрашенные (цветные) сети Петри
- •2.2.1. Мультимножества
- •2 2.2. Формальное определение cpn
- •2.2.3. Функционирование cpn
- •2.2.4. Расширения cpn
- •2.2.5. Сравнение формализмов обыкновенных и раскрашенных сетей Петри
- •2.2.6. О моделирующих возможностях сетей Петри.
- •2.3. Моделирование дискретных систем
- •2.3.1. Моделирование вычислительных систем
- •1. Простейшая система массового обслуживания.
- •2.3.2. Моделирование программ
- •1. Последовательная модель программирования
- •2. Модель параллелизма данных
- •3. Моделирование некоторых структур параллельного программирования. Семафоры
- •4. Метод асинхронного программирования
- •3 Моделирование протоколов передачи данных
- •1. Описание работы протокола
- •3. Временной механизм работы cpn
- •4. Описание работы cpn
- •2.3.4. Об исследовании сетей Петри с помощью эвм
- •Глава 3. Моделирование вычислительных Процессов с помощью цепей Маркова
- •3.1. Определение цепи Маркова
- •3.3. Классификация состояний цепей Маркова
- •3.4. Оценка длительности пребывания процесса в множестве невозвратных состояний
- •3.5. Исследование динамики цепей Маркова при большом числе шагов
- •4.1. Задачи и упражнения по главе 2
- •4.2. Задачи и упражнения по главе 3
- •1. Запуск программы и построение графа сети Петри
- •2. Задание цветовых множеств, переменных и начальной маркировки
- •Библиографический список
- •Глава 1.Основные понятия теории моделирования 5
- •Глава 2 Введение в сети Петри 21
- •Глава 4. Задания для самостоятельной работы 148
- •Глава 5. Лабораторный практикум 162
3.3. Классификация состояний цепей Маркова
Введем классификацию состояний цепи Маркова. Множество всех состояний может быть разбито на непересекающиеся подмножества, или классы: невозвратные и
эргодические. Их свойства определяются следующим образом. Если процесс покинул класс первого типа, он никогда в него не возвращается. Если процесс попал в класс состояний второго типа, то он никогда его не покидает. Невозвратное множество мы будем обозначать Т, а эргодическое - Ť. При этом T uŤ = S, Т∩Т = 0 . Если эргодическое множество содержит только одно состояние, то это состояние называется поглощающим. Для такого состояния S элемент переходной матрицы рii должен быть равен 1, следовательно, все остальные элементы соответствующей строки равны 0. Цепь, все эргодические состояния которой являются поглощающими, называется поглощающей цепью.
Для цепи Маркова с N состояниями, в которой имеются как невозвратные, так и эргодические множества, структура матрицы вероятностей переходов (возможно, после перенумерации состояний) имеет канонический вид
где s - количество состояний в невозвратном множестве;
п — s - количество состояний в эргодическом множестве.
Матрица W размерности (n-s)x(n-s) определяет динамику эргодических состояний. Поскольку из множества Ť невозможно выйти, то матрица Ø размерности (n-s)x s состоит из нулей.
Матрица Q размерности sxs определяет поведение процесса до выхода из множества невозвратных состояний.
Матрица R размерности s x(n — s) определяет вероятности перехода из множества невозвратных состояний в эргодическое множество.
При возведении матрицы Р в степень перемножаются блоки, указанные в (3.9), и произвольная степень канонической матрицы имеет вид
где Сki - биномиальные коэффициенты. В соответствии со сказанным выше, i-я строка матрицы R(k) содержит вероятности перехода системы во все состояния эргодического множества Ť за к шагов при старте из состояния Si € T.
Если цепь Маркова поглощающая, то W = I - единичная матрица размерности п - s, и все ее степени - также единичная матрица той же размерности.
Отметим еще два специальных вида матриц переходных вероятностей.
Матрица Р называется редуцируемой, если имеет вид
Цепь Маркова, определяемая матрицей вида (3.12), фактически распадается на две независимые цепи Маркова, задавааемые соответственно матрицами А и В .
Матрица Р называется периодической, если она имеет вид
где нулевые матрицы - квадратные. Здесь также присутствует два множества состояний, и на каждом шаге процесс переходит из одного множества состояний в другое. Именно такую структуру имеет переходная матрица в приведенном выше примере, если рассматривать матрицу перехода внутри множества невозвратных состояний.