Xreferat.com » Рефераты по математике » Методы и алгоритмы построения элементов систем статистического моделирования

Методы и алгоритмы построения элементов систем статистического моделирования

эту неясность следует устранить. Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.

Если случайная последовательность обладает марковским свойством, то она называется цепью Маркова.

С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется марковским процессом с непрерывным временем.

Марковский СП называется однородным, если переходные вероятности Методы и алгоритмы построения элементов систем статистического моделирования остаются постоянными в ходе процесса.

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

Методы и алгоритмы построения элементов систем статистического моделирования. (2)

2. Имеется вектор начальных вероятностей

Методы и алгоритмы построения элементов систем статистического моделирования, ….. (3)

описывающий начальное состояние системы.

Матрица (2) называется переходной матрицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е состояние за один шаг процесса. Переходная матрица (2) обладает следующими свойствами:

a) Методы и алгоритмы построения элементов систем статистического моделирования, (3a)

б) Методы и алгоритмы построения элементов систем статистического моделирования.

Матрица, обладающая свойством (3a), называется стохастической. Кроме матричной формы модель марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 2).

Методы и алгоритмы построения элементов систем статистического моделирования

Рис. 2. Ориентированный взвешенный граф

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

Множество состояний системы марковской цепи, определенным образом классифицируется с учетом дальнейшего поведения системы.

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

Методы и алгоритмы построения элементов систем статистического моделирования

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

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

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

Методы и алгоритмы построения элементов систем статистического моделирования

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

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

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

Методы и алгоритмы построения элементов систем статистического моделирования

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

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

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

Методы и алгоритмы построения элементов систем статистического моделирования

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

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

Кроме описанной выше классификации множеств различают состояния системы:

а) существенное состояние (рис.7): возможны переходы из Методы и алгоритмы построения элементов систем статистического моделирования в Методы и алгоритмы построения элементов систем статистического моделирования и обратно.

Методы и алгоритмы построения элементов систем статистического моделирования

Рис. 7. Существенное состояние

б) несущественное состояние (рис. 8): возможен переход из Методы и алгоритмы построения элементов систем статистического моделирования в Методы и алгоритмы построения элементов систем статистического моделирования, но невозможен обратный.

Методы и алгоритмы построения элементов систем статистического моделирования

Рис. 8. Несущественное состояние

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

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

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

В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают. Если просуммировать все вышесказанные определения, то можно дать следующую классификацию марковских процессов (рис. 9):

Методы и алгоритмы построения элементов систем статистического моделирования

Рис. 9. Классификация марковских процессов

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

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

Методы и алгоритмы построения элементов систем статистического моделирования (4)

и называется уравнением Колмогорова-Чепмена.

Уравнение Колмогорова-Чепмена относится к классу рекуррентных соотношений, позволяющих вычислить вероятность состояний марковского случайного процесса на любом шаге (этапе) при наличии информации о предшествующих состояниях.

Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.

4.1. Поглощающие марковские цепи

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

Для примера рассмотрим переходную матрицу, описывающую переходы в системе, имеющей 4 возможных состояния, два из которых являются поглощающими. Матрица перехода такой цепи будет иметь вид:

Методы и алгоритмы построения элементов систем статистического моделирования(5)

Практически важным является вопрос о том, сколько шагов сможет пройти система до остановки процесса, то есть поглощения в том или ином состоянии. Для получения дальнейших соотношений путем переименования состояний матрицу (8.5) переводят к блочной форме:

Методы и алгоритмы построения элементов систем статистического моделирования(6)

Методы и алгоритмы построения элементов систем статистического моделирования

Такая форма позволяет представить матрицу (6) в каноническом виде:

Методы и алгоритмы построения элементов систем статистического моделирования(6а)

где Методы и алгоритмы построения элементов систем статистического моделирования - единичная матрица;

Методы и алгоритмы построения элементов систем статистического моделирования - нулевая матрица;

Методы и алгоритмы построения элементов систем статистического моделирования - матрица, описывающая переходы в системе из невозвратного множества состояний в поглощающее множество;

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

На основании канонической формы (6а) получена матрица, называемая фундаментальной:

Методы и алгоритмы построения элементов систем статистического моделирования(7)

В матрице (7) символ (-1) означает операцию обращения, то есть

Методы и алгоритмы построения элементов систем статистического моделирования(8)

После соответствующих преобразований матрица (7) примет вид:

Методы и алгоритмы построения элементов систем статистического моделирования(7а)

Каждый элемент матрицы (7а) соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).

Если необходимо получить общее среднее количество раз попадания системы в то или иное состояние до поглощения, то фундаментальную матрицу М необходимо умножить справа на вектор-столбец, элементами которого будут единицы, то есть

Методы и алгоритмы построения элементов систем статистического моделирования(8а)

где Методы и алгоритмы построения элементов систем статистического моделирования.

Для иллюстрации приведем конкретный числовой пример: пусть известны значения переходных вероятностей матрицы Методы и алгоритмы построения элементов систем статистического моделирования с одним поглощающим состоянием: Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования.

Переходная матрица в блочной системе будет выглядеть так:

Методы и алгоритмы построения элементов систем статистического моделирования

В данном случае

Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования; Методы и алгоритмы построения элементов систем статистического моделирования ; Методы и алгоритмы построения элементов систем статистического моделирования

Проделаем необходимые вычисления:

Методы и алгоритмы построения элементов систем статистического моделирования;

Методы и алгоритмы построения элементов систем статистического моделирования;

Методы и алгоритмы построения элементов систем статистического моделирования .

В данном случае компоненты вектора Методы и алгоритмы построения элементов систем статистического моделирования означают, что если процесс начинается с состояния Методы и алгоритмы построения элементов систем статистического моделирования, то общее среднее число шагов процесса до поглощения будет равно 3,34 и, соответственно, если процесс начинается с состояния Методы и алгоритмы построения элементов систем статистического моделирования, то - 2,26.

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

Так, если задать в нашем примере время пребывания в состоянии Методы и алгоритмы построения элементов систем статистического моделирования Методы и алгоритмы построения элементов систем статистического моделирования, а в состоянии Методы и алгоритмы построения элементов систем статистического моделирования- Методы и алгоритмы построения элементов систем статистического моделирования, то общее время до поглощения будет равно:

Методы и алгоритмы построения элементов систем статистического моделирования

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

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

Методы и алгоритмы построения элементов систем статистического моделирования(8.9)

где

М - фундаментальная матрица с размерностью S;

R - блок фундаментальной матрицы с размерностью r.

Рассмотрим конкретный пример системы с четырьмя состояниями Методы и алгоритмы построения элементов систем статистического моделирования, два из которых- Методы и алгоритмы построения элементов систем статистического моделирования

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: