Дискретные цепи Маркова. Однородные цепи Маркова. Определение.
Множество случайных величин образует цепь Маркова, если вероятность того, что следующее значение (состояние) равно зависит только от текущего состояния (значения) и не зависит от предыдущих значений процесса.
Цепь Маркова – последовательность случайных величин {ξn}:
P{ ξn =i/ ξ0 =i0, ξ1 =i1,…, ξn-2 =in-2, ξn-1 =j}=P{ ξn =i/ ξn-1 =j}=pij(n) - свойство отсутствия последствий с начальным состоянием P{ ξ0 =i} =pi(0), (0)=1
pij(n) – вероятность перехода.
Рассмотрим путешественника, переезжающего из города в город на попутных машинах. – город, в котором он окажется в полдень n-го дня. Когда путешественник находится в некотором городе, он предпринимает первую попытку покинуть этот город вечером. Временем передвижения из города в город пренебрегаем. Если поездка не состоится, то путешественник останется в городе i до следующего вечера. Так как движение транспорта между соседними городами непредсказуемо, положение путешественника в некоторые моменты в будущем несомненно является случайной величиной. Эту случайную величину можно должным образом описать с помощью цепи Маркова.
Последовательность случайных величин образует дискретную цепь Маркова, если для всех n (n=1,2,…) и возможных значений случайной величины выполняется равенство.
.
Вероятность попадания путешественника в следующий город зависит только от того, в каком городе он находится в настоящее время, и не зависит от того, какие города он уже посетил.
- вероятность перехода (за 1 шаг)
Она задает условную вероятность перехода из состояния на n-1 шаге в состояние на n-м шаге процесса.
Если вероятности переходов не зависят от n, то цепь Маркова называется однородной.
- вероятность перехода на следующем шаге из состояния в состояние .
Однородная цепь Маркова – вероятности перехода pij(n) не зависят от времени, то есть
Вероятности перехода стационарны во времени. Если задано текущее состояние, то вероятности различных состояний через m шагов зависят только от этих m шагов и не зависят от текущего времени.
Вероятность перехода за m шагов:
Свойство отсутствия последствий – поведение процесса в будущем зависит только от фиксированного настоящего и не зависит от его прошлого.
-
Содержание
- Случайные процессы. Основные определения и понятия.
- Случайные процессы. Основные характеристики: плотность распределения, среднее значение, скорость изменения и автокорреляционная функция.
- Дискретные цепи Маркова. Однородные цепи Маркова. Определение.
- Классификация цепей Маркова. Основные определения и понятия, характеристики.
- Теорема о существовании предельных вероятностей для неприводимой и апериодической однородной цепи Маркова.
- Вычисление предельных вероятностей эргодической цепи Маркова (на основе примера).
- Цепи Маркова с непрерывным временем. Основные понятия.
- Уравнение Колмогорова (прямое). Следствия из уравнений Колмогорова.
- Уравнение Колмогорова (обратное). Следствия из уравнений Колмогорова.
- Процессы гибели и размножения (определение). Уравнение Колмогорова для процессов гибели и размножения.
- Процесс чистого размножения. Распределение Пуассона.
- Процесс Пуассона и его основные свойства.
- Процедуры просеивания пуассоновского потока: регулярная, случайная.
- Связь пуассоновского потока с экспоненциальным временем интервалов между соседними заявками.
- Системы массового обслуживания. Основные понятия.
- Элементы систем массового обслуживания. Классификация Кендала.
- Однолинейная смо с конечным накопителем (граф переходов, система уравнений). Стационарные вероятности состояний.
- Однолинейная смо с конечным накопителем. Вычисление среднего числа заявок в очереди.
- Однолинейная смо с конечным накопителем. Вычисление среднего числа заявок в системе.
- Однолинейная смо с конечным накопителем. Вычисление среднего времени ожидания обслуживания.
- Однолинейная смо с конечным накопителем. Вычисление среднего времени пребывания заявок в системе.
- Однолинейная смо с бесконечным накопителем. Вычисление основных характеристик системы.
- Многоканальная смо с пуассоновским потоком и экспоненциальным временем обслуживания. Граф переходов. Система уравнений.
- Многоканальная смо с пуассоновским потоком и экспоненциальным временем обслуживания. Среднее число заявок в очереди. Среднее время ожидания.
- Многоканальная смо с пуассоновским потоком и экспоненциальным временем обслуживания. Среднее число заявок в системе. Среднее время пребывания заявок в системе.
- Многоканальная замкнутая смо. Диаграмма интенсивностей переходов и уравнения для вероятностей состояний переходов. Основные характеристики системы для стационарного режима.
- 24. Метод этапов. Последовательное расположение этапов с экспоненциальным распределением каждой фазы обработки. Распределение Эрланга.
- Двухэтапный эрланговский обслуживающий прибор .
- 25. Распределение Эрланга с этапами обслуживания
- 26. Преобразование Лапласа для распределения Эрланга с r этапами обслуживания
- 27. Коэффициент вариации для последовательного представления этапов.
- 28. Коэффициент вариации для параллельной организации этапов.
- Последовательно-параллельные методы обобщения.