![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Математическое введение в теорию цепей Маркова⇐ ПредыдущаяСтр 35 из 35 Дискретные цепи Маркова. Задана дискретная цепь Маркова, если для последовательности случайных величин выполняется равенство
Это означает, что поток случайных величин определяется только вероятностью перехода от предыдущего значения случайной величины к последующему. Зная начальное распределение вероятностей, можно найти распределение на любом шаге. Величины in можно интерпретировать как номера состояний некоторой динамической системы с дискретным множеством состояний. Если вероятности переходов не зависят от номера шага, то такая цепь Маркова называется однородной и ее определение задается набором вероятностей Для однородной Марковской цепи можно определить вероятности перехода из состояния i в состояние j за m шагов Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния. Состояние i называется поглощающим, если для него pii =1. Состояние называется возвратным, если вероятность попадания в него за конечное число шагов равна единице. В другом случае состояние относится к невозвратным. Возвратное состояние может быть периодическими апериодическим в зависимости от наличия кратных шагов возврата. Введем вероятности возврата в состояние i через n шагов после ухода из этого состояния: Они позволяют определить среднее число шагов, т.е среднее время возврата: Состояние называется возвратным нулевым, если среднее время возвращения в него равно бесконечности, и возвратным ненулевым, если это время конечно. Теорема 1. Состояния неприводимой цепи Маркова либо все невозвратные, либо все возвратные нулевые, либо все возвратные ненулевые. В случае периодической цепи все состояния имеют один и тот же период. Вторая теорема рассматривает вероятности достижения состояний в стационарном (то есть не зависящем от начального распределения вероятностей) режиме. Теорема 2. Для неприводимой и апериодической цепи Маркова всегда существуют предельные вероятности, не зависящие от начального распределения вероятностей. Более того, имеет место одна из следующих двух возможностей: А) все состояния цепи невозвратные или все возвратные нулевые, и тогда все предельные вероятности равны нулю и стационарного состояния не существует; Б) все состояния возвратные ненулевые и тогда существует стационарное распределение вероятностей: Состояние называется эргодическим, если оно апериодично и возвратно ненулевое. Если все состояния цепи Маркова эргодичны, то вся цепь называется эргодической. Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полностью отсутствует. Цепь Маркова с конечным числом состояний (конечная цепь), удобно изображать в виде ориентированного графа, называемого диаграммой переходов (рис.1). Вершины графа ассоциируются с состояниями, а ребра с вероятностями переходов. Вычисления вероятностей достижения состояний производится прямыми методами или с помощью z-преобразования. Рис. 1. Цепь Маркова.
У однородных Марковских процессов вероятности переходов не зависят от времени. Вероятности перехода системы из состояния i на m-том шаге в состояние j на n-том шаге для n > m. Эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова.(Chapman - Kolmogorov)
Для однородных цепей Маркова эти уравнения упрощаются так
Классификация систем массового обслуживания.Используется трех -, четырех -, шести – компонентное символическое обозначение системы массового обслуживания, предложенное Кендаллом (Candall) и развитое в работах Г.П.Барашина. a/b/c :d/e/f a –распределение поступающего потока запросов. b– закон распределения времени обслуживания. Типовые условные обозначения: М – экспоненциальное (Марковское) распределение, D – детерминированное распределение, Ek – эрланговское распределение k-го порядка, HMk – гиперэкспоненциальное, HEk – гиперэрланговское распределение порядка k, GI – произвольное распределение независимых промежутков между заявками, G – произвольное распределение длительностей обслуживания. c –структура системы обслуживания (обычно число серверов). d –дисциплина обслуживания (параметры после двоеточия иногда опускают). Обычно используется сокращенное символическое обозначение, например FF вместо FIFO, LF, PR и т.п. e –максимальное число запросов, воспринимаемое системой, может употребляться символ ¥. f –максимальное число запросов к системе обслуживания. 2) Система типа G/G/1 Система типа G/G/1-этот класс систем предполагает, что как распределение интервалов времени между поступлением входных заявок-требований, так и распределение времени обслуживания в сервере описываются произвольными функциями плотности вероятности. Обозначим функцию плотности вероятности входного потока заявок a(t), а функцию плотности вероятности времени обслуживания b(x). Рассмотрим последовательность поступающих заявок на обслуживание - требований, пронумерованных индексами и вспомним обозначения, введенные ранее. Cn - n-е требование, поступающее в систему, tn- промежуток времени между поступлениями n-го и n-1 требований, плотность вероятности a(t) - не зависит от n. xn - время обслуживания n-го требования, плотность вероятности b(x) -также не зависит от n, wn - время ожидания n- го требования в очереди. Рис. 1 Случай, когда требование Cn+1 поступает в занятую систему. Рис. 2 Случай, когда требование Cn+1 поступает в свободную систему. 3. Задача. Межузловая ветвь вторичной сети связи имеет n = 7 каналов. Поток сообщений, поступающих для передачи по каналам ветви связи, имеет интенсивность = 16 сообщений в секунду. Среднее время t = 0,4 передачи одного сообщения равно t/n = 0,06 секунд. В накопители очереди ожидающих передачи сообщений может находиться до m = 8 сообщений. Сообщение, прибывшее в момент, когда все m мест в очереди заняты, получает отказ передачи по ветви связи. Найти характеристики СМО: Ротк ,Q ,А ,Z ,Lоч ,Тож , Тсист .
|