Как найти состояние вероятности в стационарном состоянии

Уравнения Колмогорова.
Предельные вероятности состояний

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем* на примере случайного процесса из примера 1, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния в происходят под воздействием простейших потоков событий с интенсивностями ; так, переход системы из состояния в будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния в — под воздействием потока «окончаний ремонтов» первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. 1). Рассматриваемая система имеет четыре возможных состояния: .

Вероятностью i-го состояния называется вероятность того, что в момент система будет находиться в состоянии . Очевидно, что для любого момента сумма вероятностей всех состояний равна единице:

Рассмотрим систему в момент и, задав малый промежуток , найдем вероятность того, что система в момент будет находиться в состоянии . Это достигается разными способами.

1. Система в момент с вероятностью находилась в состоянии , а за время не вышла из него.

Вывести систему из этого состояния (см. граф на рис. 1) можно суммарным простейшим потоком с интенсивностью , т.е. в соответствии с формулой (7), с вероятностью, приближенно равной . А вероятность того, что система не выйдет из состояния , равна . Вероятность того, что система будет находиться в состоянии по первому способу (т.е. того, что находилась в состоянии и не выйдет из него за время ), равна по теореме умножения вероятностей:

2. Система в момент с вероятностями (или ) находилась в состоянии или и за время перешла в состояние .

Потоком интенсивностью (или — с- рис. 1) система перейдет в состояние с вероятностью, приближенно равной (или ). Вероятность того, что система будет находиться в состоянии по этому способу, равна (или ).

Применяя теорему сложения вероятностей, получим

Переходя к пределу при (приближенные равенства, связанные с применением формулы (7), перейдут в точные), получим в левой части уравнения производную (обозначим ее для простоты ):

Получили дифференциальное уравнение первого порядка, т.е. уравнение, содержащее как саму неизвестную функцию, так и ее производную первого порядка.

Рассуждая аналогично для других состояний системы , можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний:

Сформулируем правило составления уравнений Колмогорова . В левой части каждого из них стоит производная вероятности i-го состояния. В правой части — сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния).

В системе (9) независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение (8).

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

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени . Особый интерес представляют вероятности системы в предельном стационарном режиме , т.е. при , которые называются предельными (или финальными) вероятностями состояний.

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

Предельная вероятность состояния имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии . Например, если предельная вероятность состояния , т.е. , то это означает, что в среднем половину времени система находится в состоянии .

Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы с графом состояний, изображенном на рис. 1), такая система уравнений имеет вид:

Систему (10) можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом , согласно которому слева в уравнениях стоит предельная вероятность данного состояния , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Пример 2. Найти предельные вероятности для системы из примера 1, граф состояний которой приведен на рис. 1, при

Решение. Система алгебраических уравнений, описывающих стационарный режим для данной системы, имеет вид (10) или

(Здесь мы вместо одного «лишнего» уравнения системы (10) записали нормировочное условие (8)).

Решив систему (11), получим , т.е. в предельном, стационарном режиме система в среднем 40% времени будет находиться в состоянии (оба узла исправны), 20% — в состоянии (первый узел ремонтируется, второй работает), 27% — в состоянии (второй узел ремонтируется, первый работает) и 13% времени — в состоянии (оба узла ремонтируются)

Пример 3. Найти средний чистый доход от эксплуатации в стационарном режиме системы в условиях примеров 1 и 2, если известно, что в единицу времени исправная работа первого и второго узлов приносит доход соответственно в 10 и 6 ден.ед., а их ремонт требует затрат соответственно в 4 и 2 ден.ед. Оценить экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Решение. Из примера 2 следует, что в среднем первый узел исправно работает долю времени, равную , а второй узел — . В то же время первый узел находится в ремонте в среднем долю времени, равную , а второй узел — . Поэтому средний чистый доход в единицу времени от эксплуатации системы, т.е. разность между доходами и затратами, равен

Уменьшение вдвое среднего времени ремонта каждого из узлов в соответствии с (6) будет означать увеличение вдвое интенсивностей потока «окончаний ремонтов» каждого узла, т.е. теперь и система линейных алгебраических уравнений (10), описывающая стационарный режим системы , вместе с нормировочным условием (8) примет вид:

Решив систему, получим .

Учитывая, что , а затраты на ремонт первого и второго узла составляют теперь соответственно 8 и 4 ден.ед., вычислим средний чистый доход в единицу времени:

Так как больше (примерно на 20%), то экономическая целесообразность ускорения ремонтов узлов очевидна.

Процесс гибели и размножения

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 4.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями или .

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

В соответствии с правилом составления таких уравнений (см. 13) получим: для состояния

для состояния имеем , которое с учетом (12) приводится к виду

Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений:

к которой добавляется нормировочное условие

При анализе численности популяций считают, что состояние соответствует численности популяции, равной , и переход системы из состояния в состояние происходит при рождении одного члена популяции, а переход в состояние — при гибели одного члена популяции.

Решая систему (14), (15), можно получить

Легко заметить, что в формулах (17) для коэффициенты при есть слагаемые, стоящие после единицы в формуле (16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния , а знаменатели — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния .

Пример 4. Процесс гибели и размножения представлен графом (рис. 5). Найти предельные вероятности состояний.

Стационарный режим для цепи Маркова

В ряде задач практики нас интересует так называемый установившийся или стационарный режим работы системы, который в ней устанавливается, когда от начала процесса прошло достаточно большое время. Например, процесс изменения напряжения в сети питания технического устройства, пройдя сразу после включения через ряд колебаний, по прошествии времени устанавливается. Аналогично этому и в некоторых случайных процессах по прошествии достаточно большого времени устанавливается стационарный режим, во время которого состояния системы хотя и меняются случайным образом, но их вероятности p_i(t) (i = 1, 2, …) остаются постоянными. Обозначим эти постоянные вероятности p_i:

p_i = .

Вероятности p_i (i = 1, 2, …), если они существуют, называются финальными (предельными) вероятностями состояний. Финальную вероятность p_i можно понимать как среднюю долю времени, которую в стационарном режиме проводит система S в состоянии s_i.

Например, если рассматривать некое техническое устройство в двух состояниях: s₁ – исправно, s₂ – неисправно

то имеет место следующая динамика изменения вероятностей при начальных условиях р₁(0) = 0, р₂(0) = 0: р₁(1) = 0,7, р₁(2) = 0,61, р₁(3) = 0,583, р₁(4) = 0,5749 (доказать самим). Ниже мы покажем, что в этом случае р₁ = = 0,5714. Таким образом, в рассматриваемой системе стационарный режим наступит практически через четыре шага.

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

Сформулируем условия существования стационарного режима для системы S с конечным числом состояний n, в котором протекает марковский случайный процесс с дискретным состоянием и дискретным временем (цепь Маркова):

1. Множество всех состояний W системы S должно быть эргодическим.

2. Цепь Маркова должна быть однородной, т.е. p_ij(k) = p_ij.

3. Цепь Маркова должна быть «достаточно хорошо перемешиваемой» (не должна быть «циклической»).

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

Первое условие означает, что из любого состояния можно перейти в любое другое состояние и вернуться из состояния s_j в состояние s_i (i, j = 1, 2, …, n). При этом состояния s_i и s_j не обязательно должны быть соседними. Другими словами, при блуждании системы по своим состояниям она рано или поздно попадет в любое состояние и выйдет из него и вновь в него вернется.

Если все условия стационарного режима выполняются, то финальные вероятности не зависят от того, каково было состояние системы S в момент времени t₀ = 0 или каковым было распределение вероятностей в момент времени t₀ = 0.

Условия наличия стационарного режима можно представить наглядно в виде размеченного графа состояний. Первое условие состоит в том, что размеченный граф системы должен иметь все состояния и все группы состояний транзитивными. Второе условие: все переходные вероятности должны быть постоянными: p_ij(k) = p_ij. Третье условие состоит в том, что необходимо, чтобы моменты попадания в отдельные состояния или группы состояний не образовывали циклов.

Например граф следующего вида

соответствует первым двум условиям, но третье условие не выполняется.

Если р₁(0) = 1, то при k нечетном р₁(k) = 0, р₂(k) = 1, а при k четном р₁(k)= 1, р₂(k) = 0. Матрица переходных вероятностей для этого графа имеет вид . Таким образом, в общем случае стационарного режима не будет.

В общем случае не будет стационарного режима и у системы, размеченный граф состояний которой имеет следующий вид

несмотря на то, что первые два условия выполняются. Действительно, если, например р₁(0) + р₂(0) = 1, то при k нечетном система будет находиться в подмножестве состояний <s₃, s₄>, а при k четном – в подмножестве состояний<s₁, s₂>:

Матрица переходных вероятностей, соответствующая данному графу, имеет вид

.

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

В дальнейшем при рассмотрении стационарных режимов предполагается, что третье условие выполняется.

Будем считать, что условия существования финальных вероятностей выполнены и пределы

p_i = (i = 1, 2, …, n)

существуют и не зависят от начальных условий. Покажем, как найти эти вероятности.

Если цепь Маркова однородна, т.е. p_ij(k) = p_ij, то для стационарного режима (достигаемого при k → ∞) вероятность p_j состояния s_j на (k + 1)-м шаге должна быть такой же, как на k-м:

p_j(k + 1) = = p_j,

где p_j уже не зависит от k. Отсюда

p_j = .

Сумма в правой части последнего равенства распространяется на все значения номера состояний i, включая i = j, при этом p_jj – вероятность задержки системы в состоянии j. Разделим эту сумму на две части: в первой суммирование произведем по всем значениям i, кроме i = j, а во второй будет только один член, отвечающий условию i = j. Тогда

p_j = + p_jp_jj,

откуда при любом j получаем для p_j линейное алгебраическое уравнение вида

+ p_j (p_jj – 1) = 0.

Придавая в этой формуле индексу j значения 1, 2, …, n, получим для n финальных вероятностей p₁, p₂, …, p_n систему n линейных однородных алгебраических уравнений

+ p_j (p_jj – 1) = 0 (j = 1, 2, …, n). (1)

Как известно из алгебры, такая система уравнений имеет бесконечное множество решений. В рассматриваемом случае решение становится единственным, если добавить к системе (1) нормировочное условие

= 1

взамен которого можно устранить из системы (1) любое, например, первое. Получим систему уже n неоднородных линейных уравнений с n неизвестными

+ p_j (p_jj – 1) = 0 (j = 2, 2, …, n),

= 1.

В курсе линейной алгебры доказывается, что такая система имеет единственное решение, т.е. однозначно определяет финальные вероятности p₁, p₂, …, p_n, дающие в сумме единицу.

Таким образом, можно сформулировать следующую теорему.

Теорема. Если существуют финальные вероятности, то финальный вектор (р₁, р₂, …, р_n) можно найти из уравнения

где Р – матрица переходных вероятностей.

При составлении системы линейных уравнений (2) для финальных вероятностей p₁, p₂, …, p_n удобно пользоваться понятием «потока вероятностей». Назовем произведение p_ip_ij потоком вероятности, переводящим систему S из состояния s_i в состояние s_j. Полная вероятность перехода системы S в состояние s_j откуда бы то ни было равна сумме всех потоков вероятности, переводящих систему в это состояние, т.е. вероятность прийти в состояние s_j откуда бы то ни было равна

(i ≠ j).

Аналогично, сумма всех потоков вероятности, выводящих систему из состояния s_j куда бы то ни было, равна

= p_j .

Очевидно, что в стационарном режиме вероятность войти в любое состояние должна быть равна вероятности из него выйти (иначе режим не был бы стационарным). Уравнения для финальных вероятностей можно записывать, исходя из следующего правила: для стационарного режима суммарный поток вероятности, переводящий систему S в состояние s_j из других состояний, равен суммарному потоку вероятности, выводящему систему из состояния s_j:

= p_j (j = 1, 2, …, n) (3)

Условие (3) назовем балансовым условием для состояния s_j. К этим условиям надо добавить нормировочное условие

= 1,

отбросив одно любое уравнение из (3). Полученная система решается любым из известных методов из линейной алгебры.

Решение типовых задач

1. Совокупность семей некоторого региона можно разделить на три группы

1) Семьи, не имеющие автомобиля и не собирающиеся его покупать;

2) Семьи, не имеющие автомобиля, но намеревающиеся его приобрести;

3)Семьи, имеющие автомобиль.

Проведенное статистическое исследование показало, что матрица перехода за интервал один год имеет вид

.

В этой матрице элемент р₃₃ = 1 означает вероятность того, что семья, имеющая автомобиль через год также будет его иметь, а , например, элемент р₂₃ = 0,3 – вероятность того, что семья, не имевшая автомобиля, не решившая его приобрести, осуществит свое намерение в следующем году, и т.д.

Найти вероятности того, что

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

Б) Семья, не имевшая автомобиля, но намеревающаяся его приобрести, будет иметь автомобиль через 2 года.

Решение. Найдем матрицу перехода Р₂ через два года

Р₂ = = ∙ = .

Отсюда искомые в а) и б) вероятности равны соответственно р₁₁ = 0,64 и р₂₃ = 0,51. ►

2. Рассмотрим состояния банка, характеризующиеся одной из процентных ставок: 2%, 3%, 4%, которые устанавливаются в начале каждого квартала и фиксированы на всем его протяжении. Т.е., если рассматриваемый банк принять за систему S, тот она в каждый момент времени может находиться только в одном из трех состояний: s₁ – процентная ставка 2%, s₂ – процентная ставка 3%, s₃ – процентная ставка 4%. Анализ работы банка в предшествующие годы показал, что изменения переходных вероятностей с течением времени пренебрежимо мало. Определить вероятности указанных состояний банка в конце года, если в конце предыдущего года процентная ставка банка составляла 3%, а размеченный граф состояний имеет вид

Решение. Определим тип процесса. Так как множество состояний, в которых может находиться система, конечно – три состояния – то случайный процесс является дискретным.

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

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

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

По размеченному графу состояний найдем значения вероятностей задержек.

Теперь составим матрицу переходных вероятностей за один квартал

.

Так как в конце предшествующего года процентная ставка составляла 3%, то можно считать, что в начальный момент времени система находилась в состоянии s₂. Поэтому начальное распределение вероятностей имеет вид р₁(0)=0, р₂(0) = 1, р₃ (0) = 0.

Вероятность состояний банка в конце года, т.е. по прошествии четырех кварталов, находим по формуле Р₄ = Р₁ 4 , следовательно,

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

= (0; 1; 0) ∙ = (0,2020; 0,4015; 0,3965)

Итак, р₁(4) = 0,2020, р₂(4) = 0,4015, р₃ (4) = 0,3965, т.е. в конце года вероятнее всего процентная ставка останется такой же, как и в предшествующем году, т.е. 3%.►

3. Состояния банка s₁, s₂, s₃ характеризуются соответственно процентными ставками 5%, 8% и 11%, которые устанавливаются в начале года и не меняются до следующего года. Переходные вероятности постоянны.

Спрогнозируйте, какая ставка будет к концу 2014 года, если в 2010 году процентная ставка была 5%, а размеченный граф состояний выглядит следующим образом:

Ответ. Через 4 года процентные ставки 5%, 8% и 11% будут соответственно с вероятностями 0,2261; 0,4998 и 0,2741.Следовательно, в 2014 году ставка вероятнее всего будет 8%.

4. Состояния банка s₁, s₂, s₃ характеризуются соответственно процентными ставками 2%, 3% и 4%, которые устанавливаются в начале каждого квартала и не меняются до следующего квартала. Переходные вероятности зависят от моментов установления процентных ставок. Матрицы переходных вероятностей задаются следующим образом:

Р(1) = , Р(2) = ,

Р(3) = , Р(4) = .

В конце предшествующего года процентная ставка была 4%. Какой будет процентная ставка в конце этого года? Изобразить размеченные графы состояний системы для каждого квартала.

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

Шаг k = 1.

Шаг k = 2.

Шаг k =3.

Шаг k =4.

По условию вероятности состояний системы в начальный момент времени

Р(1)∙Р(2) = ∙ = .

Р(1)∙Р(2)∙Р(3) = ∙ =

Р(1)∙Р(2)∙Р(3)∙Р(4) = ∙ = = .

= (0, 0, 1)∙ = (0,3584; 0,3696; 0,2720).

Таким образом p₁(4) = 0,3584, p₂(4) = 0,3696, p₃(4) = 0,2720, и наиболее вероятной процентной ставкой в конце года будет 3%.►

5. Пусть имеется граф состояний

и задана матрица переходных состояний .

В начальный момент времени (t₀ = 0) система находится в состоянии s₁. Составить для системы размеченный граф состояний Найти распределение вероятностей состояний системы для первых четырех шагов (k = 1, 2, 3, 4); убедиться, что вероятность поглощающего состояния p₄(k) с увеличением k растет.

Решение. Составим для системы размеченный граф состояний.

Так как в начальный момент времени (t₀ = 0) система находится в состоянии s₁, то p₁(0) = 1, p₂(0) = p₃(0) = p₄(0) = 0. По формуле

p_j(k) = (k = 1,2,…; j = 1,2,…,n),

Снова применяя формулу, находим вероятности состояний на втором шаге

p₁(4) = 0,421·0,7 + 0,131·0,2 + 0,113·0,2 = 0,3435;

Мы убедились в том, что с возрастанием k вероятность поглощающего состояния p₄(k) растет, тогда как вероятность p₁(k) состояния s₁ растет. ►

6. Рассмотрим систему S – станок с числовым программным управлением, который может быть в следующих состояниях:

s₁ – исправен и работает;

s₂ – неисправен и неисправность не обнаружена;

s₃ – неисправен, проводится средний ремонт;

s₄ – не работает, находится на профилактике;

s₅ – неисправен, проводится капитальный ремонт.

Размеченный граф состояний имеет следующий вид

Решение. Рассмотрим состояние s₅ на графе. В это состояние направлено две стрелки, следовательно, в левой части уравнения (3) для j = 5 (состояние s₅) будет два слагаемых. Из этого состояния выходит одна стрелка, следовательно, в правой части уравнения (3) для j = 5 будет одно слагаемое. Получаем первое уравнение

Аналогично запишем еще три уравнения:

В качестве пятого уравнения возьмем нормировочное условие

Перепишем полученную систему уравнений в таком виде:

Решим эту систему уравнений. Из 2) находим

Подставляя соответствующие значения вероятностей, получим

а₂ = = ,

а₄ = = ,

а₃ = = ,

а₅ = = .

Подставляя полученные значения в равенство 5) получаем уравнение

р₁ + р₁ + р₁ + р₁ + р₁ = 1,

р₁ = ≈ 0,6139, p₂ = а₂р₁ = ≈ 0,0877, p₃ = а₃р₁ = ≈ 0,0743,

p₄ = а₄р₁ = ≈ 0,0682, p₅ = а₅р₁ = ≈ 0,1559. ►

Обратим внимание, что для решения этого примера нам потребовались только те вероятности, которые приведены на размеченном графе, и не потребовались вероятности задержки р₁₁, р₂₂, р₃₃, р₄₄, р₅₅.

7. Система S представляет собой вычислительный центр (ВЦ), в котором имеется три компьютерных блока. В определенные моменты времени, разделенные промежутком t, все блоки осматриваются, в результате чего каждый признается либо исправным и продолжает работать, либо признается неисправным и направляется в ремонт. Вероятность того, что исправный блок за время t выйдет из строя, не зависит от того, какое время он уже работал (от «предыстории» процесса), и равна r. Вероятность того, что ремонтируемый блок за время t будет приведен в исправность, не зависит от того, сколько времени уже продолжался ремонт и сколько блоков ремонтируется, и равна q. Процессы выхода блоков из строя и их восстановления протекают независимо друг от друга. Построить размеченный граф состояний ВЦ, нумеруя их по числу неисправных блоков:

s₁ – один блок неисправен, остальные два работают,

s₂ – два блока исправны, один работает,

s₃ – все три блока неисправны.

Полагая r = 0,2, q = 0,3, построить размеченный граф состояний ВЦ и найти финальные вероятности.

Решение. Размеченный граф состояний имеет следующий вид

Вычислим переходные вероятности p_ij.

Чтобы система перешла из состояния s₀ в состояние s₁, нужно, чтобы один из блоков на время t вышла из строя. Эта вероятность, согласно биномиальному распределению, равна р₀₁ = . Аналогично находим

р₀₂ = , р₀₃ = r 3 , р₀₀ = (1 – r) 3 .

Чтобы система из состояния s₁ перешла в состояние s₀, нужно, чтобы неисправный блок за время t был отремонтирован, а другие два исправных блока не вышли из строя: р₁₀ = q(1 – r) 2 . Аналогично находим

Рассуждая таким же способом, определяем

р₃₃ = (1 – q) 3 , р₃₂ = , р₃₁ = , р₃₀ = q 3 .

Теперь при r = 0,2 и q = 0,3 имеем

Для нашего примера система уравнений

= p_j (j = 1, 2, …, n)

с учетом нормировочного условия = 1 может быть записана в следующем виде:

Решая полученную систему линейных неоднородных уравнений одним из известных методов линейной алгебры, получим

8. Дана однородная марковская цепь со следующим размеченным графом состояний

Найти финальные вероятности.

Решение. Матрица переходных вероятностей имеет вид

Р = .

Тогда вектор финальных вероятностей

(р₁, р₂, р₃) = (р₁, р₂, р₃)∙Р = (р₁, р₂, р₃)∙ . (*)

Произведя умножение в правой части этого равенства, получим

Отсюда получаем следующую систему линейных уравнений

р₁ = 0,4р₁+ 0,2р₂ + 0,7р₃; 0,6р₁ – 0,2р₂ = 0;

Из первого уравнения

р₁ = р₂. (**)

Итак, (р₁ = р₂; р₂; р₃ = 0) – общее решение уравнения (*), зависящее от одного произвольного параметра р₂. Подберем этот параметр из нормировочного уравнения р₁ + р₂ + р₃ = 1. Отсюда р₂ = 1 – р₁. Подставив это выражение в (**), найдем р₁ = . Тогда р₂ = .

Окончательно вектор финальных вероятностей (р₁, р₂, р₃) = .►

9. Поведение рынка ценных бумаг обнаруживает следующую тенденцию: сделки, в которых цены возрастают, сменяются сделками, в которых цены падают. Наблюдения показали, что условная вероятность возрастания цен после предшествовавшего периода их падения равна 0,65, а условная вероятность падения цен после предшествовавшего периода их возрастания равна 0,6. Найти соответствующие состояния, построить размеченный граф состояний, выписать матрицу переходных вероятностей и найти финальные вероятности системы.

Решение. В качестве системы S будем рассматривать рынок ценных бумаг. Тогда система S может находиться только в двух состояниях: s₁ – падение цен, и s₂ – возрастание цен, следовательно, процесс, протекающий в системе S, является дискретным.

Предстоящее состояние, в которое перейдет система S, зависит (в существенном) от состояния, в котором она находится в настоящий момент времени, поэтому процесс является марковским.

Будем предполагать, что моменты времени t₁, t₂, t₃, … настолько близки друг к другу, что между ними система S не изменяет своего состояния и, следовательно, процесс с определенной погрешностью можно считать процессом с дискретным временем.

Условные вероятности 0,65 и 0,6, данные в условии, являются, очевидно, вероятностями р₁₂ и р₂₁. Тогда

Размеченный граф состояний будет иметь следующий вид

Матрица переходных вероятностей

Р = = .

Вектор финальных вероятностей ищем из уравнения

(р₁, р₂) = (р₁, р₂)∙Р = (р₁, р₂)∙ .

р₁ = 0,35р₁ + 0,6р₂; 0,65р₁ – 0,6р₂ = 0;

Уравнения полученной системы пропорциональны, поэтому одно из них (например, второе) можно отбросить, заменяя его нормировочным уравнением, т.е. получая систему

0,65р₁ – 0,6р₂ = 0;

Решая эту систему, находим вектор финальных вероятностей

Таким образом, при достаточно длительном функционировании рынка ценных бумаг финальные вероятности падения и роста цен равны соответственно 0,48 и 0,52. При этом они не зависят от начального состояния рынка.►

10. Компания по прокату автомобилей выдает автомобили напрокат в трех аэропортах А, В и С. Клиенты возвращают автомобили в эти аэропорты в соответствии с вероятностями, указанными в следующей таблице

Откуда	Куда
А	В	С
А	0,75	0,25
В	0,25	0,75
С	0,25	0,25	0,5

Компания планирует построить ремонтную станцию в одном из этих трех аэропортов. В каком из них это целесообразно сделать и почему?

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

s₁ – автомобиль находится в аэропорту А и не выдан напрокат или выдан напрокат из аэропорта А и находится у клиента;

Тогда вероятности, данные в условии задачи в таблице, являются переходными вероятностями системы S из одного из состояний s₁, s₂, s₃ в другое.

Промежуток времени между выдачей и возвращением автомобиля не может быть сколь угодно бесконечно малым и потому моменты времени t₁,t₂,t₃,… можно выбрать настолько близкими друг к другу, что между ними система S не изменяет своего состояния. Следовательно, процесс, протекающий в системе S, можно считать процессом с дискретным временем.

Таким образом, матрица переходных вероятностей

Р = .

Вектор финальных вероятностей ищем из уравнения

(р₁, р₂, р₃) = (р₁, р₂, р₃)∙Р = (р₁, р₂, р₃)∙ .

р₁ = 0,75р₁ + 0,25р₂ + 0,25р₃; 0,25р₁ – 0,25р₂ – 0,25р₃ = 0;

Заменяя, например, второе уравнение системы нормировочным уравнение, получим

р₁ – р₂ – р₃ = 0;

Решая последнюю систему, получим вектор финальных вероятностей (р₁,р₂, р₃) = (0,5, 0,2, 0,3). Таким образом, ремонтную станцию целесообразно строить в аэропорту А, т.к. финальная вероятность возврата в этот аэропорт наибольшая.►

Марковские случайные процессы. Уравнения Колмогорова для вероятностей состояний.

Наиболее полное исследование процесса функционирования систем получается, если известны явные математические зависимости, связывающие искомые показатели с начальными условиями, параметрами и переменными исследуемой системы. Для многих современных систем, являющихся объектами моделирования, такие математические зависимости отсутствуют или малопригодны, и следует применять другое моделирование, как правило, имитационное.

Большой класс случайных процессов составляют процессы без последействия, которые в математике называют марковскими процессами в честь Андрея Андреевича Маркова — старшего (1856 — 1922), выдающегося русского математика, разработавшего основы теории таких процессов.

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

Практически любой случайный процесс является марковским или может быть сведен к марковскому. В последнем случае достаточно в понятие состояния включить всю предысторию смен состояний системы.

Марковские процессы делятся на два класса:

· дискретные марковские процессы (марковские цепи);

· непрерывные марковские процессы.

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

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

Рассмотрим ситуацию, когда моделируемый процесс обладает следующими особенностями.

Система имеет возможных состояний: , . . Вообще говоря, число состояний может быть бесконечным. Однако модель, как правило, строится для конечного числа состояний.

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

Известны вероятности перехода системы за один шаг из состояния в состояние .

Цель моделирования: определить вероятности состояний системы после -го шага.

Обозначим эти вероятности (не путать с вероятностями ).

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

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

Значения обычно сводятся в матрицу переходных вероятностей:

Значения могут также указываться на графе состояний системы. На рис. показан размеченный граф для четырех состояний системы. Обычно вероятности переходов «в себя» — , и т. д. на графе состояний можно не проставлять, так как их значения дополняют до 1 сумму переходных вероятностей, указанных на ребрах (стрелках), выходящих из данного состояния.

Не указываются также нулевые вероятности переходов. Например, на рис. это вероятности , и др.

Математической моделью нахождения вероятностей состояний однородной марковской цепи является рекуррентная зависимость

где — вероятность -го состояния системы после -го шага, ;

— вероятность -го состояния системы после -го шага, ;

— число состояний системы;

-переходные вероятности.

Рис.Размеченный граф состояний системы

Для неоднородной марковской цепи вероятности состояний системы находятся по формуле:

где — значения переходных вероятностей для -го шага.

Сформулируем методику моделирования по схеме дискретных марковских процессов (марковских цепей).

1. Зафиксировать исследуемое свойство системы.

Определение свойства зависит от цели исследования. Например, если исследуется объект с целью получения характеристик надежности, то в качестве свойства следует выбрать исправность. Если исследуется загрузка системы, то — занятость. Если состояния объектов, то — поражен или непоражен.

2. Определить конечное число возможных состояний системы и убедиться в правомерности моделирования по схеме дискретных марковских процессов.

3. Составить и разметить граф состояний.

4. Определить начальное состояние.

5. По рекуррентной зависимости определить искомые вероятности.

В рамках изложенной методики моделирования исчерпывающей характеристикой поведения системы является совокупность вероятностей .

При моделировании состояния систем с непрерывными марковскими процессами мы уже не можем воспользоваться переходными вероятностями , так как вероятность «перескока» системы из одного состояния в другое точно в момент времени равна нулю (как вероятность любого отдельного значения непрерывной случайной величины).

Поэтому вместо переходных вероятностей вводятся в рассмотрение плотности вероятностей переходов :

где — вероятность того, что система, находившаяся в момент времени в состоянии за время перейдет в состояние .

С точностью до бесконечно малых второго порядка из приведенной формулы можно представить:

Непрерывный марковский процесс называется однородным,если плотности вероятностей переходов не зависят от времени (от момента начала промежутка ). В противном случае непрерывный марковский процесс называется неоднородным.

Целью моделирования,как и в случае дискретных процессов, является определение вероятностей состояний системы Эти вероятности находятся интегрированием системы дифференциальных уравнений Колмогорова.

Сформулируем методику моделирования по схеме непрерывных марковских процессов.

1. Определить состояния системы и плотности вероятностей переходов .

2. Составить и разметить граф состояний.

3. Составить систему дифференциальных уравнений Колмогорова. Число уравнений в системе равно числу состояний. Каждое уравнение формируется следующим образом.

4. B левой части уравнения записывается производная вероятности -го состоянии

5. В правой части записывается алгебраическая сумма произведений и . Число произведений столько, сколько стрелок связано с данным состоянием. Если стрелка графа направлена в данное состояние, то соответствующее произведение имеет знак плюс, если из данного состояния — минус.

6. Определить начальные условия и решить систему дифференциальных уравнений.

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

Рис. Размеченный граф состояний

Очевидно, .

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

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

Дата добавления: 2015-04-03 ; просмотров: 7833 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

В 1998 году Лоуренс Пейдж, Сергей Брин, Раджив Мотвани и Терри Виноград опубликовали статью «The PageRank Citation Ranking: Bringing Order to the Web», в которой описали знаменитый теперь алгоритм PageRank, ставший фундаментом Google. Спустя чуть менее двух десятков лет Google стал гигантом, и даже несмотря на то, что его алгоритм сильно эволюционировал, PageRank по-прежнему является «символом» алгоритмов ранжирования Google (хотя только немногие люди могут действительно сказать, какой вес он сегодня занимает в алгоритме).

С теоретической точки зрения интересно заметить, что одна из стандартных интерпретаций алгоритма PageRank основывается на простом, но фундаментальном понятии цепей Маркова. Из статьи мы увидим, что цепи Маркова — это мощные инструменты стохастического моделирования, которые могут быть полезны любому эксперту по аналитическим данным (data scientist). В частности, мы ответим на такие базовые вопросы: что такое цепи Маркова, какими хорошими свойствами они обладают, и что с их помощью можно делать?

Краткий обзор

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

Примечание. Для понимания этого поста необходимы знания основ вероятностей и линейной алгебры. В частности, будут использованы следующие понятия: условная вероятность, собственный вектор и формула полной вероятности.

---

Что такое цепи Маркова?

Случайные переменные и случайные процессы

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

Во-первых, вне языка математики случайной величиной X считается величина, которая определяется результатом случайного явления. Его результатом может быть число (или «подобие числа», например, векторы) или что-то иное. Например, мы можем определить случайную величину как результат броска кубика (число) или же как результат бросания монетки (не число, если только мы не обозначим, например, «орёл» как 0, а «решку» как 1). Также упомянем, что пространство возможных результатов случайной величины может быть дискретным или непрерывным: например, нормальная случайная величина непрерывна, а пуассоновская случайная величина дискретна.

Далее мы можем определить случайный процесс (также называемый стохастическим) как набор случайных величин, проиндексированных множеством T, которое часто обозначает разные моменты времени (в дальнейшем мы будем считать так). Два самых распространённых случая: T может быть или множеством натуральных чисел (случайный процесс с дискретным временем), или множеством вещественных чисел (случайный процесс с непрерывным временем). Например, если мы будем бросать монетку каждый день, то зададим случайный процесс с дискретным временем, а постоянно меняющаяся стоимость опциона на бирже задаёт случайный процесс с непрерывным временем. Случайные величины в разные моменты времени могут быть независимыми друг от друга (пример с подбрасыванием монетки), или иметь некую зависимость (пример со стоимостью опциона); кроме того, они могут иметь непрерывное или дискретное пространство состояний (пространство возможных результатов в каждый момент времени).

Разные виды случайных процессов (дискретные/непрерывные в пространстве/времени).

Марковское свойство и цепь Маркова

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

Одно из свойств, сильно упрощающее исследование случайного процесса — это «марковское свойство». Если объяснять очень неформальным языком, то марковское свойство сообщает нам, что если мы знаем значение, полученное каким-то случайным процессом в заданный момент времени, то не получим никакой дополнительной информации о будущем поведении процесса, собирая другие сведения о его прошлом. Более математическим языком: в любой момент времени условное распределение будущих состояний процесса с заданными текущим и прошлыми состояниями зависит только от текущего состояния, но не от прошлых состояний (свойство отсутствия памяти). Случайный процесс с марковским свойством называется марковским процессом.

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

На основании этого определения мы можем сформулировать определение «однородных цепей Маркова с дискретным временем» (в дальнейшем для простоты мы их будем называть «цепями Маркова»). Цепь Маркова — это марковский процесс с дискретным временем и дискретным пространством состояний. Итак, цепь Маркова — это дискретная последовательность состояний, каждое из которых берётся из дискретного пространства состояний (конечного или бесконечного), удовлетворяющее марковскому свойству.

Математически мы можем обозначить цепь Маркова так:

где в каждый момент времени процесс берёт свои значения из дискретного множества E, такого, что

Тогда марковское свойство подразумевает, что у нас есть

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

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

Характеризуем динамику случайности цепи Маркова

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

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

Однако благодаря марковскому свойству динамику цепи Маркова определить довольно просто. И в самом деле. нам нужно определить только два аспекта: исходное распределение вероятностей (то есть распределение вероятностей в момент времени n=0), обозначаемое

и матрицу переходных вероятностей (которая даёт нам вероятности того, что состояние в момент времени n+1 является последующим для другого состояния в момент n для любой пары состояний), обозначаемую

Если два этих аспекта известны, то полная (вероятностная) динамика процесса чётко определена. И в самом деле, вероятность любого результата процесса тогда можно вычислить циклически.

Пример: допустим, мы хотим знать вероятность того, что первые 3 состояния процесса будут иметь значения (s0, s1, s2). То есть мы хотим вычислить вероятность

Здесь мы применяем формулу полной вероятности, гласящую, что вероятность получения (s0, s1, s2) равна вероятности получения первого s0, умноженного на вероятность получения s1 с учётом того, что ранее мы получили s0, умноженного на вероятность получения s2 с учётом того, что мы получили ранее по порядку s0 и s1. Математически это можно записать как

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

получив таким образом

Так как они полностью характеризуют вероятностную динамику процесса, многие сложные события можно вычислить только на основании исходного распределения вероятностей q0 и матрицы переходной вероятности p. Стоит также привести ещё одну базовую связь: выражение распределения вероятностей во время n+1, выраженное относительно распределения вероятностей во время n

Цепи Маркова в конечных пространствах состояний

Представление в виде матриц и графов

Здесь мы допустим, что во множестве E есть конечное количество возможных состояний N:

Тогда исходное распределение вероятностей можно описать как вектор-строку q0 размером N, а переходные вероятности можно описать как матрицу p размером N на N, такую что

Преимущество такой записи заключается в том, что если мы обозначим распределение вероятностей на шаге n вектором-строкой qn, таким что его компоненты задаются

тогда простые матричные связи при этом сохраняются

(здесь мы не будем рассматривать доказательство, но воспроизвести его очень просто).

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

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

Динамику случайности цепи Маркова в конечном пространстве состояний можно с лёгкостью представить как нормированный ориентированный граф, такой что каждый узел графа является состоянием, а для каждой пары состояний (ei, ej) существует ребро, идущее от ei к ej, если p(ei,ej)>0. Тогда значение ребра будет той же вероятностью p(ei,ej).

Пример: читатель нашего сайта

Давайте проиллюстрируем всё это простым примером. Рассмотрим повседневное поведение вымышленного посетителя сайта. В каждый день у него есть 3 возможных состояния: читатель не посещает сайт в этот день (N), читатель посещает сайт, но не читает пост целиком (V) и читатель посещает сайт и читает один пост целиком (R ). Итак, у нас есть следующее пространство состояний:

Допустим, в первый день этот читатель имеет вероятность 50% только зайти на сайт и вероятность 50% посетить сайт и прочитать хотя бы одну статью. Вектор, описывающий исходное распределение вероятностей (n=0) тогда выглядит так:

Также представим, что наблюдаются следующие вероятности:

• когда читатель не посещает один день, то имеет вероятность 25% не посетить его и на следующий день, вероятность 50% только посетить его и 25% — посетить и прочитать статью
• когда читатель посещает сайт один день, но не читает, то имеет вероятность 50% снова посетить его на следующий день и не прочитать статью, и вероятность 50% посетить и прочитать
• когда читатель посещает и читает статью в один день, то имеет вероятность 33% не зайти на следующий день (надеюсь, этот пост не даст такого эффекта!), вероятность 33% только зайти на сайт и 34% — посетить и снова прочитать статью

Тогда у нас есть следующая переходная матрица:

Из предыдущего подраздела мы знаем как вычислить для этого читателя вероятность каждого состояния на следующий день (n=1)

Вероятностную динамику этой цепи Маркова можно графически представить так:

Представление в виде графа цепи Маркова, моделирующей поведение нашего придуманного посетителя сайта.

Свойства цепей Маркова

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

Разложимость, периодичность, невозвратность и возвратность

В этом подразделе давайте начнём с нескольких классических способов характеризации состояния или целой цепи Маркова.

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

Иллюстрация свойства неразложимости (несокращаемости). Цепь слева нельзя сократить: из 3 или 4 мы не можем попасть в 1 или 2. Цепь справа (добавлено одно ребро) можно сократить: каждого состояния можно достичь из любого другого.

Состояние имеет период k, если при уходе из него для любого возврата в это состояние нужно количество этапов времени, кратное k (k — наибольший общий делитель всех возможных длин путей возврата). Если k = 1, то говорят, что состояние является апериодическим, а вся цепь Маркова является апериодической, если апериодичны все её состояния. В случае неприводимой цепи Маркова можно также упомянуть, что если одно состояние апериодическое, то и все другие тоже являются апериодическими.

Иллюстрация свойства периодичности. Цепь слева периодична с k=2: при уходе из любого состояния для возврата в него всегда требуется количество шагов, кратное 2. Цепь справа имеет период 3.

Состояние является невозвратным, если при уходе из состояния существует ненулевая вероятность того, что мы никогда в него не вернёмся. И наоборот, состояние считается возвратным, если мы знаем, что после ухода из состояния можем в будущем вернуться в него с вероятностью 1 (если оно не является невозвратным).

Иллюстрация свойства возвратности/невозвратности. Цепь слева имеет такие свойства: 1, 2 и 3 невозвратны (при уходе из этих точек мы не можем быть абсолютно уверены, что вернёмся в них) и имеют период 3, а 4 и 5 возвратны (при уходе из этих точек мы абсолютно уверены, что когда-нибудь к ним вернёмся) и имеют период 2. Цепь справа имеет ещё одно ребро, делающее всю цепь возвратной и апериодической.

Для возвратного состояния мы можем вычислить среднее время возвратности, которое является ожидаемым временем возврата при покидании состояния. Заметьте, что даже вероятность возврата равна 1, то это не значит, что ожидаемое время возврата конечно. Поэтому среди всех возвратных состояний мы можем различать положительные возвратные состояния (с конечным ожидаемым временем возврата) и нулевые возвратные состояния (с бесконечным ожидаемым временем возврата).

Стационарное распределение, предельное поведение и эргодичность

В этом подразделе мы рассмотрим свойства, характеризующие некоторые аспекты (случайной) динамики, описываемой цепью Маркова.

Распределение вероятностей π по пространству состояний E называют стационарным распределением, если оно удовлетворяет выражению

Так как у нас есть

Тогда стационарное распределение удовлетворяет выражению

По определению, стационарное распределение вероятностей со временем не изменяется. То есть если исходное распределение q является стационарным, тогда оно будет одинаковых на всех последующих этапах времени. Если пространство состояний конечно, то p можно представить в виде матрицы, а π — в виде вектора-строки, и тогда мы получим

Это снова выражает тот факт, что стационарное распределение вероятностей со временем не меняется (как мы видим, умножение справа распределения вероятностей на p позволяет вычислить распределение вероятностей на следующем этапе времени). Учтите, что неразложимая цепь Маркова имеет стационарное распределение вероятностей тогда и только тогда, когда одно из её состояний является положительным возвратным.

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

Ещё раз подчеркнём тот факт, что мы не делаем никаких допущений об исходном распределении вероятностей: распределение вероятностей цепи сводится к стационарному распределению (равновесному распределению цепи) вне зависимости от исходных параметров.

Наконец, эргодичность — это ещё одно интересное свойство, связанное с поведением цепи Маркова. Если цепь Маркова неразложима, то также говорится, что она «эргодическая», потому что удовлетворяет следующей эргодической теореме. Допустим, у нас есть функция f(.), идущая от пространства состояний E к оси (это может быть, например, цена нахождения в каждом состоянии). Мы можем определить среднее значение, перемещающее эту функцию вдоль заданной траектории (временное среднее). Для n-ных первых членов это обозначается как

Также мы можем вычислить среднее значение функции f на множестве E, взвешенное по стационарному распределению (пространственное среднее), которое обозначается

Тогда эргодическая теорема говорит нам, что когда траектория становится бесконечно длинной, временное среднее равно пространственному среднему (взвешенному по стационарному распределению). Свойство эргодичности можно записать так:

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

Вернёмся к примеру с читателем сайта

Снова рассмотрим пример с читателем сайта. В этом простом примере очевидно, что цепь неразложима, апериодична и все её состояния положительно возвратны.

Чтобы показать, какие интересные результаты можно вычислить с помощью цепей Маркова, мы рассмотрим среднее время возвратности в состояние R (состояние «посещает сайт и читает статью»). Другими словами, мы хотим ответить на следующий вопрос: если наш читатель в один день заходит на сайт и читает статью, то сколько дней нам придётся ждать в среднем того, что он снова зайдёт и прочитает статью? Давайте попробуем получить интуитивное понятие о том, как вычисляется это значение.

Сначала мы обозначим

Итак, мы хотим вычислить m(R,R). Рассуждая о первом интервале, достигнутом после выхода из R, мы получим

Однако это выражение требует, чтобы для вычисления m(R,R) мы знали m(N,R) и m(V,R). Эти две величины можно выразить аналогичным образом:

Итак, у нас получилось 3 уравнения с 3 неизвестными и после их решения мы получим m(N,R) = 2.67, m(V,R) = 2.00 и m(R,R) = 2.54. Значение среднего времени возвращения в состояние R тогда равно 2.54. То есть с помощью линейной алгебры нам удалось вычислить среднее время возвращения в состояние R (а также среднее время перехода из N в R и среднее время перехода из V в R).

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

То есть нам нужно найти левый собственный вектор p, связанный с собственным вектором 1. Решая эту задачу, мы получаем следующее стационарное распределение:

Стационарное распределение в примере с читателем сайта.

Можно также заметить, что π( R ) = 1/m(R,R), и если немного поразмыслить, то это тождество довольно логично (но подробно об этом мы говорить не будем).

Поскольку цепь неразложима и апериодична, это означает, что в длительной перспективе распределение вероятностей сойдётся к стационарному распределению (для любых исходных параметров). Иными словами, каким бы ни было исходное состояние читателя сайта, если мы подождём достаточно долго и случайным образом выберем день, то получим вероятность π(N) того, что читатель не зайдёт на сайт в этот день, вероятность π(V) того, что читатель зайдёт, но не прочитает статью, и вероятность π® того, что читатель зайдёт и прочитает статью. Чтобы лучше уяснить свойство сходимости, давайте взглянем на следующий график, показывающий эволюцию распределений вероятностей, начинающихся с разных исходных точек и (быстро) сходящихся к стационарному распределению:

Визуализация сходимости 3 распределений вероятностей с разными исходными параметрами (синяя, оранжевая и зелёная) к стационарному распределению (красная).

Классический пример: алгоритм PageRank

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

Произвольный веб-пользователь

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

Чтобы решить эту задачу и иметь возможность отранжировать страницы, PageRank приблизительно выполняет следующий процесс. Мы считаем, что произвольный пользователь Интернета в исходный момент времени находится на одной из страниц. Затем этот пользователь начинает случайным образом начинает перемещаться, щёлкая на каждой странице по одной из ссылок, которые ведут на другую страницу рассматриваемого множества (предполагается, что все ссылки, ведущие вне этих страниц, запрещены). На любой странице все допустимые ссылки имеют одинаковую вероятность нажатия.

Так мы задаём цепь Маркова: страницы — это возможные состояния, переходные вероятности задаются ссылками со страницы на страницу (взвешенными таким образом, что на каждой странице все связанные страницы имеют одинаковую вероятность выбора), а свойства отсутствия памяти чётко определяются поведением пользователя. Если также предположить, что заданная цепь положительно возвратная и апериодичная (для удовлетворения этим требованиям применяются небольшие хитрости), тогда в длительной перспективе распределение вероятностей «текущей страницы» сходится к стационарному распределению. То есть какой бы ни была начальная страница, спустя длительное время каждая страница имеет вероятность (почти фиксированную) стать текущей, если мы выбираем случайный момент времени.

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

Искусственный пример

Чтобы это стало намного понятнее, давайте рассмотрим искусственный пример. Предположим, что у нас есть крошечный веб-сайт с 7 страницами, помеченными от 1 до 7, а ссылки между этими страницами соответствуют следующему графу.

Ради понятности вероятности каждого перехода в показанной выше анимации не показаны. Однако поскольку подразумевается, что «навигация» должна быть исключительно случайной (это называют «случайным блужданием»), то значения можно легко воспроизвести из следующего простого правила: для узла с K исходящими ссылками (странице с K ссылками на другие страницы) вероятность каждой исходящей ссылки равна 1/K. То есть переходная матрица вероятностей имеет вид:

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

Сделав так, мы получим следующие значения PageRank (значения стационарного распределения) для каждой страницы

Значения PageRank, вычисленные для нашего искусственного примера из 7 страниц.

Тогда ранжирование PageRank этого крошечного веб-сайта имеет вид 1 > 7 > 4 > 2 > 5 = 6 > 3.

---

Выводы

Основные выводы из этой статьи:

• случайные процессы — это наборы случайных величин, часто индексируемые по времени (индексы часто обозначают дискретное или непрерывное время)
• для случайного процесса марковское свойство означает, что при заданном текущем вероятность будущего не зависит от прошлого (это свойство также называется «отсутствием памяти»)
• цепь Маркова с дискретным временем — это случайные процессы с индексами дискретного времени, удовлетворяющие марковскому свойству
• марковское свойство цепей Маркова сильно облегчает изучение этих процессов и позволяет вывести различные интересные явные результаты (среднее время возвратности, стационарное распределение…)
• одна из возможных интерпретаций PageRank (не единственная) заключается в имитации веб-пользователя, случайным образом перемещающегося от страницы к странице; при этом показателем ранжирования становится индуцированное стационарное распределение страниц (грубо говоря, на самые посещаемые страницы в устоявшемся состоянии должны ссылаться другие часто посещаемые страницы, а значит, самые посещаемые должны быть наиболее релевантными)

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

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

Содержание:

Случайные процессы:

Пусть T – некоторое множество действительных чисел. Случайной функцией называется совокупность случайных величин

Что такое случайный процесс

При наблюдении случайной функции мы получаем одну из возможных ее реализаций – неслучайную функцию. Поэтому случайную функцию можно рассматривать как совокупность всех ее возможных реализаций (см. рис. 4.1, на котором жирной линией выделена одна из возможных реализаций, а точками отмечены возможные значения случайной величины

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

С изменением параметра t изменяется и закон распределения случайной величины Этот закон распределения можно задать в виде функции распределения

Если функция распределения дифференцируема, то

называется функцией плотности вероятности.

Для дискретной случайной величины одномерный закон распределения задается перечислением возможных значений и соответствующих им вероятностей

Конечномерным законом распределения случайной функции называется закон распределения n сечений случайной функции 

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

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

Дисперсией случайного процесса называют неслучайную функцию значение которой при каждом фиксированном значении параметра t равно дисперсии сечения процесса при этом значении параметра, т.е.

На рис. 4.2 и рис. 4.3 изображены несколько реализаций соответственно случайных процессов и , которые имеют одинаковые математические ожидания и дисперсии. Однако характер протекания этих процессов существенно различен. У процесса реализации плавные. Это свидетельствует о зависимости значений процесса, отделенных небольшими промежутками времени. Процесс же меняется быстро и влияние предыдущих значений процесса быстро иссякает. 

Для описания этих особенностей процесса существует специальная характеристика, которая называется корреляционной функцией (иногда говорят об автокорреляционной функции).

Корреляционной функцией случайного процесса называют неслучайную функцию значение которой при каждых фиксированных значениях параметра t₁ и t₂ равно коэффициенту ковариации величин и , т.е.

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

Свойства корреляционной функции

Отметим некоторые свойства корреляционной функции:

1. При перестановке аргументов корреляционная функция не меняется:

2. Прибавление к случайной функции неслучайной функции не меняет ее корреляционной функции. Если то

3. При умножении случайной функции на неслучайную функцию корреляционная функция умножается на произведение Если то

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

Например, где случайными величинами являются амплитуда X, частота Y и фаза Z гармонических колебаний.

Пример №1

Элементарная случайная функция имеет вид где X и Y независимы, причем X имеет плотность вероятности (показательный закон распределения с параметром ), а случайная величина Y равномерно распределена в отрезке Требуется найти для математическое ожидание, дисперсию и автокорреляционную функцию.

Решение. Обозначим через Учитывая, что случайная величина Y равномерно распределена на с постоянной плотностью имеем

Поэтому

так как для показательного закона распределения Вычислим

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

а 

Поэтому и при и при  

Для вычисления дисперсии возьмем в полученном выражении 

Ответ. 

Пример №2

Пусть – последовательность независимых случайных величин с функцией плотности вероятности

Говорят, что последовательность превышает уровень (выходит за уровень ) в момент если Рассмотрим  – момент первого выхода последовательности (случайного процесса с дискретным временем) за уровень . Требуется найти распределение случайной величины и ее математическое ожидание.

Решение. Вычислим

Тогда и

– это геометрический закон распределения.

Но для геометрического закона распределения  В нашем случае роль p играет величина Поэтому

Ответ.  

Пример №3

Пусть – последовательность независимых случайных величин с нулевыми математическими ожиданиями и равными дисперсиями Требуется найти корреляционную функцию для случайной последовательности

Решение. Так как математические ожидания случайных величин равны нулю, то Поэтому

 

При 

При  

При остальных s = 2,3,… величина

Ответ.   при остальных s = 2,3,… величина

Пример №4

Все положения случайной точки (X,Y) равновозможны в области Для случайного процесса  постоянная w > 0, требуется найти математическое ожидание дисперсию и корреляционную функцию

Решение. По свойствам математического ожидания

Так как площадь области D равна , а все положения случайной точки (X,Y) в этой области равновозможны, то плотность вероятности случайной точки при и при остальных

Маргинальная плотность вероятности случайной величины X равна

Поэтому

Аналогично, Поэтому

Вычислим дисперсию X. Так как

то Аналогично находим, что  

Вычислим теперь корреляционную функцию процесса:

Вычислим 

Но  Поэтому 

С учетом этого получаем 

Ответ. 

             

Взаимной корреляционной функцией двух случайных функций X(t) и Y(t) называют неслучайную функцию двух независимых аргументов t₁ и t₂, значения которой равны корреляционному моменту случайных величин X(t₁) и Y(t₂):

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

Если рассматривать многомерный случайный процесс то он имеет характеристики 

Эти характеристики описывают поведение отдельно взятых координат случайного процесса, но не учитывают взаимодействие между ними. В качестве характеристики взаимозависимости координат случайного процесса используют взаимную корреляционную функцию  В общем случае взаимная корреляционная функция  не равна  так как ковариация между сечениями  (на рис. 4.4 точки 3 и 4).

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

 

Наглядным примером двумерного случайного процесса (или случайного поля) может служить поверхность моря.

Пример №5

Даны два случайных процесса 

где случайные величины U и V независимы и имеют равные дисперсии Требуется найти взаимную корреляционную функцию этих процессов.

Решение. Так как  то 

Аналогично,  Тогда 

Величины U и V независимы, а значит и некоррелированы. Поэтому С учетом того, что а получаем

Ответ. 

Пример №6

Даны два случайных процесса и где U и V независимы, имеют и Требуется найти взаимную корреляционную функцию этих процессов.

Решение. Так как 

Ответ. 

Пусть X(t) и Y(t) – две случайные функции, а случайная функция Z(t) равна Выразим характеристики Z(t) через характеристики X(t) и Y(t).

Математическое ожидание суммы двух случайных функций равно сумме математических ожиданий этих функций:

Заметим, что 

Поэтому 

Легко видеть, что для процесса корреляционная функция имеет вид:

Пример №7

Случайный процесс а где – случайная величина с равномерным законом распределения на Необходимо найти корреляционную функцию случайного процесса

Решение. Прежде всего вычислим математические ожидания случайных процессов. Случайная величина равномерно распределена на с плотностью вероятности равной Поэтому

Вычислим величины необходимые для использования формулы (4.1):

Аналогично, По формуле (4.1)

Ответ. 

Стационарные случайные процессы

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

Определение. Случайная функция X(t) называется строго стационарной (стационарной в узком смысле), если все ее конечномерные законы распределения не изменяются от сдвига параметра (времени) на произвольную величину t₀. Это в частности означает, что ее математическое ожидание и дисперсия постоянны, а корреляционная функции зависит только от разности аргументов.

Определение. Случайная функция X(t) называется стационарной в широком смысле, если ее математическое ожидание постоянно, а корреляционная функции зависит только от разности аргументов т.е.

Так как  то условие (4.1.1) означает и постоянство дисперсии.

Пример 4.8.

Дан случайный процесс где  – случайная величина, равномерно распределенная в отрезке Требуется доказать, что этот случайный процесс стационарен в широком смысле.

Решение. Для доказательства необходимо проверить выполнение условий (4.1.1). Найдем математическое ожидание

так как 

где – плотность вероятности случайной величины . Заметим, что  Поэтому 

так как 

Итак, т.е. зависит только от разности Корреляционная функция оказалась независящей от величины , которую в приложениях обычно трактуют как «фазу».

Ответ. Процесс стационарен в широком смысле.

Пример 4.9.

Значения случайного процесса X(t) изменяются скачками в случайные моменты времени . Моменты скачков образуют простейший (пуассоновский) поток событий интенсивности т.е. вероятность того, что за время t произойдет k скачков равна

В интервале , между двумя скачками X(t) может принимать лишь два значения 0 или 1 с вероятностями соответственно Значения X(t) в различных интервалах независимы. (Такой процесс называют фототелеграфным сигналом.)

Необходимо найти и выяснить, является ли этот процесс X(t) стационарным в широком смысле.

Решение. В произвольный момент времени t значения процесса имеют распределение

Поэтому

Заметим, что если между моментами t₁ и t₂ не было скачков процесса (вероятность чего по формуле (4.1.2) равна где то значения процесса X(t₁) и X(t₂) совпадают и

Если же между моментами t₁ и t₂ скачки были, то величины X(t₁) и X(t₂) независимы и . Поэтому

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

Ответ. Процесс стационарен в широком смысле.

Пример 4.10.

Случайный процесс X(t) строится следующим образом. В некоторый случайный момент времени T появляется прямоугольный импульс длительности t₀ и случайной амплитудой A₁. В момент времени этот импульс сменяется новым импульсом той же длительности и случайной амплитуды A₂, и т. д. Величины A₁, A₂,… независимы, и каждая с равными вероятностями принимает одно из двух значений «+1» или «–1». Одна из возможных реализаций процесса X(t) показана на рис. 4.1.1.

Требуется найти и выяснить, является ли этот процесс X(t) стационарным в широком смысле.

Решение. Для любого момента времени t:

Обозначим Так как равновозможны все положения точки t в то t имеет равномерное распределение в с функцией плотности вероятности

Случайный процесс центрирован поэтому

Если вместе принадлежит промежутку то

Вероятность этого

Если же  вероятность чего равна то

в силу независимости случайных величин Поэтому

 при  и  при  (см. рис. 4.1.2).

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

Ответ. при  и   при  Процесс стационарен в широком смысле.

Пример 4.11.

Случайный процесс X(t) строится следующим образом. На числовой оси реализуется простейший поток событий интенсивности Случайный процесс X(t) принимает попеременно случайные значения и –. При наступлении события простейшего потока X(t) скачком меняет свое значение с на – или наоборот. Одна из реализаций процесса показана на рис. 4.1.4, где точками на оси отмечены события простейшего потока. 

Требуется найти математическое ожидание, дисперсию и ковариационную функцию этого случайного процесса.

Решение. Так как моменты изменения знака никак не связаны со значениями процесса X(t), нет оснований считать, что какое либо из значений ( или –) более вероятно, чем другое. Следовательно, 

Рассмотрим значения процесса в произвольные моменты времени t₁ и t₂. Так как то

Произведение если в интервале происходит нечетное число событий (тогда значения процесса X(t₁) и X(t₂) будут разных знаков). Если же в интервале происходит четное число событий, то

Вероятность появления за время четного числа событий простейшего потока равна

Тогда

Следовательно, 

Аналогично, при т.е. при

Полученные выражения для можно объединить в одну запись:

График этой функции изображен на рис. 4.1.5.

Дисперсия процесса равна

Ответ. Процесс стационарен в широком смысле.

Пример 4.12.

Случайный процесс X(t) устроен следующим образом. На оси времени реализуется простейший поток событий интенсивности При появлении события этого потока процесс X(t) скачком возрастает на единицу. Между скачками он убывает линейно под углом минус 45°. Одна из реализаций процесса приведена на рис. 4.1.7, где точками на оси отмечены моменты появления событий простейшего потока.

Требуется найти математическое ожидание дисперсию и корреляционную функцию этого случайного процесса и его нормированную корреляционную функцию.

Решение. Каждый скачок процесса равен единице. Поэтому значение процесса в момент времени t можно записать в виде

где N(t) – число скачков за время t.

Случайная величина N(t) имеет пуассоновский закон распределения, причем

Поэтому 

Так как  то при 

В свою очередь

 

Так как случайные величины и независимы, а для распределения Пуассона если параметр распределения равен то

В итоге имеем

Аналогично, при получаем Поэтому

Нормированная корреляционная функция:

Если то если же то Величины X(t₁) и X(t₂) коррелированы положительно.

Ответ. 

Пример 4.13.

Случайный процесс X(t) изменяет свое состояние в моменты времени, которые образуют простейший поток интенсивности В каждой точке скачка процесс X(t) возрастает на единицу, а затем убывает по экспоненте с показателем –1 до точки следующего скачка. Одна из реализаций такого процесса приведена на рис. 4.1.10. Требуется найти математическое ожидание, дисперсию и ковариационную функцию этого случайного процесса.

Замечание. Описанный процесс может служить простейшей математической моделью воздействия потока электронов на анод. Поток электронов от катода к аноду близок к простейшему потоку некоторой интенсивности При попадании электрона на анод напряжение на нем X(t) возрастает на некоторую единицу, а затем убывает по экспоненте, показатель которой зависит от характеристик электронной схемы.

Решение. Результат воздействия -го скачка, происшедшего в момент времени имеет вид: при и при или

где  при  и  при 

Так как поток скачков простейший, то за время t произойдет случайное число скачков N, распределенных по закону Пуассона с параметром Поэтому X(t) является суммой случайного числа N случайных слагаемых

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

где все равномерно распределены на а N не зависит от . Из (4.1.4) следует, что

(Здесь мы воспользовались тем, что математическое ожидание суммы случайного числа одинаково распределенных случайных величин равно произведению математического ожидания числа этих величин на математическое ожидание одной из них.)

Так как число слагаемых N распределено по закону Пуассона, то

Каждая из величин равномерно распределена в . Поэтому 

В итоге

Кроме того,

 

Рассмотрим два момента времени t₁ и t₂ Значение X(t₂) равно значению 1 X(t₁), умноженному на , плюс вклад от скачков процесса на интервале

Величины X(t₁), и независимы, так как они связаны со скачками процесса в непересекающихся интервалах времени и . Поэтому при

Аналогично, при получим

Поэтому Остается вычислить:

С учетом (4.1.5), (4.1.6) и того, что получаем

В итоге, 

Ответ. 

Стационарная в широком смысле функция X(t), представимая во всей области определения в виде 

где U_k и V_k – центрированные случайные величины, удовлетворяющие условиям при ,  при всех i и j, называется случайной функцией с дискретным спектром.

Такая случайная функция имеет автокорреляционную функцию

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

Говорят, что стационарная случайная функция X(t) является случайной функцией с непрерывным спектром, если существует такая действительная неотрицательная функция  определенная при всех  что 

Функцию называют спектральной плотностью, а формулы (4.1.9) и (4.1.10) называют формулами Винера–Хинчина. Из этих формул и свойств корреляционной функции следует, что  – функция четная, т.е.  Поэтому изображают обычно только для неотрицательных . Случайные функции, обладающие конечной дисперсией, имеют спектральные плотности, которые стремятся к нулю на бесконечности быстрее, чем

В силу четности корреляционной функции стационарного процесса и
его спектральной плотности формулы (4.1.9) и (4.1.10) можно записать в
виде:

Формулы (4.1.11) и (4.1.12) означают, что корреляционная функция и спектральная плотность связаны взаимно обратными преобразованиями Фурье. Выражения вида (4.1.11) называют интегралом Фурье. Интеграл Фурье является обобщением разложения в ряд Фурье для случая непериодической функции на бесконечном интервале. Это разложение функции на сумму простых гармонических колебаний с непрерывным спектром.

Заметим, что дисперсию стационарного случайного процесса с непрерывным спектром можно выразить в виде интеграла от спектральной плотности:

Пример 4.14.

Корреляционная функция стационарного случайного процесса X(t) имеет вид

Требуется найти спектральную плотность процесса.

Решение. В соответствии с формулой (4.1.12)

Вычислим сначала первый интеграл

Аналогично

Поэтому

Ответ. 

Спектральная плотность производной от случайной функции X(t) связана со спектральной плотностью этой функции соотношением

Пример 4.15.

Спектральная плотность случайной функции X(t) имеет вид  Требуется найти дисперсию производной этой случайной функции.

Решение. Согласно (4.1.13) спектральная плотность производной X'(t) имеет вид   Тогда

Ответ. 

Пусть – автокорреляционная функция стационарного случайного процесса X(t). Найдем взаимную корреляционную функцию процессов X'(t) и X(t). Так как процесс X(t) стационарен, то Поэтому

Так как 

Аналогично 

Пример 4.16.

Спектральная плотность случайного стационарного процесса X(t) имеет вид:  если и при остальных х. Требуется найти автокорреляционную функцию этого процесса. 

Решение. Так как функция четная, то по формуле (4.1.11) получаем

Ответ. 

Пример 4.17.

Задана спектральная плотность стационарного случайного процесса 

Требуется найти корреляционную функцию этого процесса.

Решение. По формуле (4.1.11) получим:

Непосредственно вычислять такой интеграл трудно. Поэтому воспользуемся следующим приемом. Продифференцируем обе части равенства: 

Проинтегрируем по частям:  
Тогда Первое слагаемое в скобке равно нулю, так как  Интеграл во втором слагаемом совпадает с . 

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

Это уравнение с разделяющимися переменными. Его общее решение: 

Для определения произвольной постоянной зададим начальное условие 

(Напомним, что интеграл Пуассона )

При таком начальном условии Искомая корреляционная функция имеет вид:

Заметим, что и спектральная плотность, и корреляционная функция этого процесса относятся к типу гауссовских кривых. 

Ответ. 

Преобразование случайных процессов динамическими системами

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

Говорят, что случайная последовательность  сходится к числу b в среднеквадратическом смысле, если

(этот факт записывают кратко ).

Случайный процесс X(t) называется стохастически непрерывным в точке если

Случайная величина X'(t) называется среднеквадратической производной случайной функции X(t) в точке если

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

На вход системы непрерывно подаются некоторые данные, система их перерабатывает и выдает результат этой переработки. Иногда входящие в систему данные называют «воздействием» или «сигналом», данные на выходе называют «реакцией» или «откликом» на воздействие. Обычно вместе с полезным сигналом поступают и случайные помехи, которые тоже перерабатываются динамической системой и влияют на отклик. Поэтому в общем виде ставится формальная задача о переработке динамической системой некоторого случайного процесса X(t). На выходе тоже получается случайный процесс Y(t). Схема описанной системы приведена на рисунке 4.2.1.

Естественно возникает вопрос: как по характеристикам X(t), с учетом особенностей динамической системы, найти характеристики сигнала на выходе?

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

Правило, по которому функция X(t) на входе преобразуется в функцию Y(t) на выходе, называется оператором. Символически это записывают в виде:

Оператор L называется линейным однородным оператором, если он обладает следующими свойствами:

1.
2. где C – постоянная величина.

Примерами линейных операторов могут служить операторы

где – некоторая функция.

Оператор называют линейным неоднородным, если он состоит из линейной части с прибавлением некоторой определенной функции:

Если случайная функция X(t) с математическим ожиданием  и корреляционной функцией преобразуется линейным однородным оператором L в случайную функцию 

то для нахождения математического ожидания нужно применить этот оператор к  т.е.

А для нахождения корреляционной функции  необходимо применить этот оператор к корреляционной функции сначала по одному аргументу, а затем по другому:

Например, если линейный оператор дифференцирования  применяется к случайному процессу X(t) с математическим ожиданием  и корреляционной функцией , то для  математическое ожидание а корреляционная функция 

Пример 4.18.

Задана – корреляционная функция стационарного случайного процесса X(t). Требуется найти корреляционную функцию процесса

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

Так как процесс X(t) стационарен, то его математическое ожидание и математическое ожидание его производной равны нулю. Поэтому 

Но так как 

Аналогично,

Так как где  то а Поэтому по формуле (4.2.1) 

В итоге по формуле (4.2)

 

Ответ. 

Стационарной линейной динамической системой называется устройство, которое можно описать линейным дифференциальным уравнением с постоянными коэффициентами:

где – постоянные коэффициенты, X(t) – входящий стационарный процесс (воздействие), а Y(t) – случайный процесс на выходе из системы (отклик). Если динамическая система устойчива, то по окончании переходного периода процесс Y(t)  тоже стационарен.

Найдем характеристики Y(t) по характеристикам X(t). Возьмем математическое ожидание от правой и левой частей равенства (4.2.3).Так как X(t) и Y(t) стационарные процессы, то их математические ожидания m_x и m_y постоянны, а производные математических ожиданий равны нулю. Поэтому 

Обозначим оператор дифференцирования через p, оператор через p² и т.д. Тогда уравнение (4.2.3) можно записать в виде 

или

Выражение

называют передаточной функцией.

Уравнение (4.2.3) в операторной форме кратко записывается в виде

Частотной характеристикой линейной динамической системы называют функцию, которая получается заменой p на в передаточной функции:

Доказано, что спектральные плотности процессов X(t) и Y(t) связаны соотношением

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

Пример 4.19.

Динамическая система задана уравнением

На вход системы подается стационарный случайный процесс X(t) с корреляционной функцией Требуется найти дисперсию процесса на выходе в установившемся режиме.

Решение. Вычислим спектральную плотность случайного процесса X(t) по формуле (4.1.12)

В операторной форме уравнение (4.2.8) имеет вид

Поэтому частотная характеристика По формуле

Поэтому

Ответ.

Пример 4.20.

На вход линейной динамической системы, описываемой уравнением

подается стационарный случайный процесс X(t) с математическим ожиданием и корреляционной функцией Требуется найти математическое ожидание и дисперсию процесса на выходе.

Решение. Вычислим спектральную плотность случайного процесса X(t). По формуле (4.1.12)

Обозначим оператор дифференцирования через p, а оператор через p² . Тогда уравнение (4.2.9) можно записать в виде

или

Передаточная функция динамической системы имеет вид 

а ее частотная характеристика 

Спектральная плотность процесса на выходе системы равна, согласно (4.2.7), 

Дисперсия процесса на выходе равна 

Если динамическая система устойчива, то при достаточно больших значениях t (после переходного периода) функцию Y(t) можно считать стационарной. Так как X(t) и Y(t) стационарны, то математические ожидания их производных равны нулю. Поэтому переход к математическим ожиданиям в равенстве (4.2.9) дает 

Ответ.  

Пример 4.21.

Пусть X – случайная величина с Случайный процесс Y(t) определяется уравнением

где – постоянные коэффициенты. Требуется найти дисперсию процесса Y(t).

Решение. Решим линейное дифференциальное уравнение (4.2.10) методом Бернулли. Будем искать решение в виде Тогда уравнение (4.2.10) можно переписать:

Подберем u(t) так, чтобы т. е. При таком u(t) получаем уравнение Откуда или В итоге получаем общее решение уравнения (4.3.2):

При начальных условиях имеем Частное решение уравнения (4.2.10) имеет вид Поэтому

Ответ. 

Пример 4.22.

На RC – цепь, схема которой изображена на рис. 4.2.3, подается случайное напряжение X(t) с математическим ожиданием и ковариационной функцией

Требуется найти математическое ожидание и дисперсию с напряжения Y(t) на выходе.

Решение. Дифференциальное уравнение, связывающее сигнал на выходе Y(t) с сигналом X(t) на входе имеет вид 

Решение этого уравнения можно получить, например, методом вариации произвольной постоянной. Однородному уравнению соответствует характеристическое уравнение Поэтому решение соответствующего однородного уравнения имеет вид Вместо произвольной постоянной C подберем такую функцию C(t), чтобы стало решением уравнения (4.2.11). Тогда при подстановке этого Y(t) в уравнение (4.2.11) получаем

Откуда следует, что

Поэтому решение уравнения (4.2.11) имеет вид

Запись (4.2.12) означает, что Y(t) является результатом действия на X(t) линейного оператора:

В соответствии с (4.2.1)

По формуле (4.2.2) при

Аналогично при

Поэтому дисперсия

Ответ. 

Процессы «гибели и рождения»

Пусть некоторый объект может в каждый момент времени может находиться в одном из состояний: множество которых конечно или счетно. (Счетным называют множество, все элементы которого могут быть занумерованы с помощью натуральных чисел.) В случайные моменты времени возможны переходы из состояния в состояние. Особенность этих переходов состоит в том, что за бесконечно малый промежуток времени возможны переходы только в соседние состояния.

Формально это означает следующее. Если в момент времени t объект находится в состоянии то за малый промежуток времени h объект из состояния может перейти в состояние с вероятностью а вероятность перехода в состояние равна Напомним, что означает величину бесконечно малую более высокого порядка малости по сравнению с h. Вероятность перехода из в другие состояния за бесконечно малый промежуток времени h пренебрежимо мала  Отсюда следует, что вероятность за время h сохранить состояние равна

Пусть постоянные и не зависят от времени t и от способа прихода объекта в состояние . Эти предположения позволяют нарисовать следующую схему возможных переходов (см. рис. 4.3.1). 

Процесс изменения состояний объекта по приведенной схеме называется процессом гибели и рождения.

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

В терминах процессов гибели и размножения можно обсуждать многие технические задачи. Например, для математической модели транспортного предприятия под состоянием можно понимать число автомобилей, которые пригодны для эксплуатации. Тогда выход из стоя автомобиля означает переход в состояние с номером на единицу меньше (т.е. «гибель»), а восстановление машины после ремонта – переход в состояние с номером на единицу больше («рождение»).

Обозначим через вероятность того, что в момент времени t объект находится в состоянии и выведем уравнения для этих вероятностей. Сначала выведем уравнение при Для этого рассмотрим отрезок времени и учтем возможные изменения состояния объекта за малый промежуток времени h. Объект в момент времени будет находиться в состоянии , вероятность чего равна если в момент t он находился в состоянии вероятность чего равна и за время h произошел переход в состояние , вероятность чего равна или в момент t он находился в состоянии , вероятность чего равна и за время h переходов не было, вероятность чего равна или в момент t он находился в состоянии вероятность чего равна и за время h произошел переход в состояние , вероятность чего равна

Символическая запись этой фразы имеет вид 

Перенесем из правой части в левую   и разделим каждое слагаемое в равенстве на h:

При получаем дифференциальное уравнение

Уравнение для k=0 получается из следующих рассуждений. Объект в момент времени будет находиться в состоянии Е₀, вероятность чего равна если в момент t он находился в состоянии Е₀, вероятность чего равна и за время h переходов не было, вероятность чего равна или в момент t он находился в состоянии Е₁, вероятность чего равна и за время h произошел переход в состояние Е₀, вероятность чего равна Символически эта фраза может быть записана в виде

Перенос слагаемого в левую часть, деление правой и левой частей равенства на h, предельный переход при приводят к дифференциальному уравнению

Уравнения (4.3.2) и (4.3.3) называют системой уравнений гибели и рождения. В общем виде решение этой системы получить сложно, но в отдельных частных случаях это вполне обозримая работа.

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

Выбрать единственное решение системы позволяет условие нормировки Для этого выразим все вероятности, например, через  Из первого уравнения С учетом этого, из второго уравнения получаем

Третье уравнение дает равенство Продолжая подобные действия, найдем, что Тогда по условию нормировки .

В итоге получаем, что

Замечание. Если ряд в знаменателе (4.3.4) расходится, то все Это означает «взрыв» численности, т.е. за конечное время произойдем бесконечно много рождений. Сходимость ряда является достаточным условием существования ненулевых вероятностей Для сходимости ряда по признаку Даламбера требуется, чтобы

т.е. начиная с некоторого номера n интенсивность гибели должна превосходить интенсивность рождений.

Пример 4.23.

Система состоит из основного блока, одного блока в «горячем» резерве (т.е. работающего одновременно с основным) и одного блока в «холодном» резерве (т.е. этот резервный блок не работает). Длительность безотказной работы работающего блока распределена по показательному закону с параметром Вышедший из строя блок практически мгновенно заменяется блоком из холодного резерва, а вышедший из строя блок незамедлительно начинают ремонтировать. Время ремонта распределено по показательному закону с параметром n. Система прекращает свою работу, как только остается всего один работоспособный элемент. Требуется найти вероятность того, что система выйдет из строя до момента времени t.

Решение. 1. Состояния системы будем различать по числу вышедших из строя блоков. Обозначим через – состояние, в котором блоков вышли из строя. Тогда граф состояний системы имеет вид, изображенный на рис. 4.3.2. 

Происходит переход если один из двух работающих блоков выходит из строя. Интенсивность таких переходов равна При окончании ремонта происходит переход с интенсивностью n. Состояние E₂ является «поглощающим» – если система попала в него, то она это состояние не покинет.

2. Обозначим через вероятность того, что в момент времени t система будет находиться в состоянии . Нас интересует  – вероятность того, что в момент времени t система уже вышла из строя. Выход из строя можно считать «рождением» неполадки, а ее устранение – «гибелью». Система уравнений гибели и размножения (4.3.2) и (4.3.3) в нашем случае имеет вид:

Любое из уравнений системы можно заменить условием нормировки

Пусть система начинает свою работу из состояния E₁, т.е. имеет начальные условия:

3. Перейдем в системе (4.3.5) к преобразованиям Лапласа:

или

Решение системы (4.3.6), например, по формулам Крамера дает:

Остается найти обратное преобразование от Например, при и выражение (4.3.7) принимает вид

(Здесь мы пользуемся методом неопределенных коэффициентов для разложения на простые дроби). Имея две равные дроби с равными знаменателями, приравниваем числители этих дробей

Приравнивая в правой и левой частях равенства коэффициенты при равных степенях получим В итоге имеем

Обращение преобразования Лапласа дает искомую вероятность

Ответ. 

Пример 4.24.

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

Решение. Состояния контактного телефона будем различать по числу занятых операторов. Пусть E_k – означает, что заняты k из них. Тогда граф состояний имеет вид, изображенный на рис. 4.3.3.

Составим уравнения для вероятностей Сопоставим значения этих вероятностей в моменты времени

Перенос слагаемого в левую часть, деление правой и левой частей равенства на , предельный переход при приводят к дифференциальному уравнению

На контактном телефоне в момент времени будет занят один оператор, вероятность чего равна если в момент t все операторы были свободны, вероятность чего равна и за время один из операторов включился в работу, вероятность чего равна или в момент t был занят только один оператор, вероятность чего равна и за время переходов не было, вероятность чего равна или в момент t были заняты два оператора, вероятность чего равна и за время один из операторов освободился

Символическая запись этой фразы имеет вид

Перенесем из правой части в левую и разделим каждое слагаемое в равенстве на :

При получаем дифференциальное уравнение

Аналогично выводятся уравнения

С течением времени вероятности состояний стабилизируются и перестают зависеть от времени (от начального состояния), т.е. 

Но при этом В результате система дифференциальных уравнений превращается в систему однородных линейных алгебраических уравнений 

Выбрать единственное решение системы позволяет условие нормировки Для этого выразим все вероятности, например, через Р₀. Из первого уравнения С учетом этого, из второго уравнения получаем

Третье уравнение дает равенство  Продолжая подобные действия, найдем, что Тогда по условию нормировки

Обозначим через Тогда

Откуда

Ответ. 

Пример 4.25.

Система массового обслуживания состоит из двух обслуживающих устройств. В систему поступает простейший поток требований на обслуживание интенсивности Времена обслуживания требований независимы и имеют показательный закон распределения с параметром ( – интенсивность обслуживания). Требование, заставшее все устройства занятыми, может встать в очередь или покинуть систему. Вероятность присоединения к очереди пропорциональна числу обслуживающих устройств и обратно пропорциональна числу требований в системе плюс один. Это означает, что интенсивность перехода равна Требуется найти стационарные вероятности числа требований в системе.

Решение. Обозначим через E_k – состояние системы, когда в ней находятся k требований. Если в системе находится требований (два требования обслуживаются и ожидают в очереди), то вероятность присоединения к очереди по условию задачи равна Это означает, что интенсивность перехода равна Граф состояний системы изображен на рис. 4.3.4

Составим систему уравнений гибели и размножения

Для стационарного режима получаем систему однородных линейных алгебраических уравнений

Эту систему естественно дополнить условием нормировки Из первого уравнения получаем, что Подставляя этот результат во второе уравнение, находим Из третьего уравнения, с учетом полученных для P₁ и Р₂ выражений, имеем Продолжая действовать подобным образом, получим    Обозначим через Воспользуемся условием нормировки:

откуда  или  В итоге

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

Вероятность того, что требование поступит на обслуживание без ожидания в очереди, равна Вероятность наличия очереди в системе равна

Ответ. 

Пример 4.26.

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

Требуется найти долю времени простоя системы из-за выхода из строя приборов. Найти наработку на отказ, т.е. среднее время работы системы между пребываниями в отказных состояниях.

Решение. Состояния системы будем различать по числу вышедших из строя приборов. Обозначим через состояние системы, в котором элементов системы находятся в нерабочем состоянии. Тогда состояние E₂ можно назвать отказным состоянием, поскольку оба элемента вышли из строя. Граф состояний системы изображен на рис. 4.3.5.

Если считать выход из строя прибора рождением неполадки, а завершение ремонта ее гибелью, то система уравнений гибели и размножения по формулам (4.3.2), (4.3.3) для нашего случая принимает вид

Это система линейных однородных дифференциальных уравнений с постоянными коэффициентами. Любое уравнение системы можно заменить условием нормировки:

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

Эта система имеет бесконечно много решений. Для выбора приемлемого для нас решения одно из уравнений, например, второе заменим условием нормировки

Из первого уравнения имеем а из третьего уравнения Тогда по условию нормировки откуда

где  Тогда 

Стационарную вероятность P₂ можно понимать как долю времени, в течение которой система находится в нерабочем состоянии (оба прибора вышли из строя).

Для вычисления наработки на отказ сделаем состояние E₂ поглощающим, т.е. исключим переход Тогда граф состояний будет иметь вид, изображенный на рис. 4.3.6.

Этому графу состояний соответствует система уравнений

Зададим начальное состояние. Пусть, например, Обозначим через преобразование Лапласа от и запишем систему (4.3.9) в преобразованиях Лапласа:

или

Найдем например, по правилу Крамера. Вычислим определитель системы (4.3.10):

и  Поэтому 

Обозначим через – вероятность безотказной работы системы до момента t, а через – ее преобразование Лапласа. Тогда

Заметим, что где T – время достижения отказного состояния, т.е. время безотказной работы системы.

Последний вывод основан на следующих соображениях. Пусть X – неотрицательная случайная величина с функцией распределения Интегрируя по частям, вычислим

В нашем случае Первое слагаемое равно наработке на отказ за счет холодного резервирования, второе слагаемое возникло за счет ремонта.

Ответ. 

Рассмотрим систему массового обслуживания, в которую поступает простейший поток требований интенсивности Время обслуживания распределено показательно с параметром Каждое требование при поступлении в систему начинает обслуживаться немедленно, если есть хотя бы один свободный прибор. Если требование застает все n приборов обслуживания занятыми, то оно получает отказ и теряется. Такую систему называют системой с потерями. Примером такой системы может служить телефонный узел.

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

Под состоянием можно полагать то состояние системы, при котором в ней находится (обслуживается) k требований. Тогда система может находиться только в состояниях Вероятность перехода из состояния в состояние при равна Если в системе находится k требований, то интенсивность обслуживания равна kn и вероятность перехода из в за малое время равна Мы имеем дело с процессом гибели и размножения, для которого при и при при и при Если ввести обозначение то формула (4.3.4) дает вероятности состояний системы при

Формулы (4.3.11) называют формулами Эрланга, который их впервые вывел в 1917 г. В последующем оказалось, что для систем с потерями формулы Эрланга сохраняют свою структуру при любом распределении длительности обслуживания, лишь бы среднее время обслуживания равнялось

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

Пример 4.27.

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

Требование, заставшее все каналы обслуживания занятыми, теряется. Необходимо найти вероятность потери требования и среднее число занятых обслуживанием каналов.

Решение. Пусть V – время обслуживания требования. Вычислим среднее время обслуживания

В формулах Эрланга . Заменяя на получаем По формуле (4.3.11) имеем:

и . Вероятность застать все каналы занятыми равна Это и есть вероятность потери требования.

Среднее число занятых каналов равно

Ответ. 

Пример 4.28.

На многоканальный контактный телефон фирмы поступает простейший поток звонков интенсивности пять звонков в час. Время разговора с каждым клиентом в среднем занимает 10 минут. Звонки, заставшие все каналы занятыми, теряются. Сколько должно быть каналов для того, чтобы терялось не более 10% звонков?

Решение. Формулы Эрланга сохраняют свою структуру при любом распределении времени обслуживания и зависят только от среднего значения длительности обслуживания. В нашем случае среднее время обслуживания равно 1/6 ч. Поэтому Явно решить неравенство 

даже при известном значении , едва ли возможно. Поэтому естественно найти n простым перебором его значений. Начнем с n=2. По формуле (4.3.12) при n=2

По той же формуле при n=3

Вычисления показали, что при двух каналах теряется около 16% звонков, а уже при трех каналах потери составят около 5% звонков.

Ответ. Достаточно трех каналов.

Метод фаз Эрланга

Случайная величина X имеет распределение Эрланга порядка k с параметром , если ее функция плотности вероятности имеет вид

На рис. 4.4.1 приведены графики распределения Эрланга при значении параметра и разных значениях k.

При k=1 получается плотность показательного распределения.

Метод фаз Эрланга применяется тогда, когда наряду с показательными распределениями в стохастической системе встречаются распределения Эрланга.

Математическое описание такой системы возможно с помощью Марковского процесса. Эта возможность основана на том, что случайную величину, имеющую распределение Эрланга порядка k с параметром , можно представить в виде суммы k независимых показательно распределенных случайных величин с параметром . Например, длительность обслуживания, имеющую распределение Эрланга порядка k, можно считать состоящей из k независимых «фаз», каждая из которых имеет одно и то же показательное распределение.

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

Пример 4.29 (система Энгсета с потерями)

Система обслуживания состоит из одного прибора. Из n независимых источников поступают требования. Время обслуживания любого требования имеет распределение Эрланга 3-го порядка с параметром Из каждого источника поступает на обслуживание простейший поток заявок, интенсивности . Интервалы между приходами требований из данного источника назовем паузами. Если требование застает прибор свободным, то начинает сразу обслуживаться. Пока происходит это обслуживание, из данного источника новых требований не поступает. После завершения обслуживания начинается отсчет новой паузы на данном источнике. Требуется найти долю времени, в течение которой прибор будет занят.

Решение. Выделим состояния системы: – прибор свободен; – прибор занят -й фазой обслуживания. Граф состояний системы изображен на рис. 4.4.2.

Для вероятностей состояний системы в момент времени t можно составить систему уравнений:

Тогда для стационарных вероятностей получаем систему

из которой Из условия нормировки Поэтому Вероятность того, что система занята равна

Ответ. 

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

Цепи Маркова:

Случайным процессом называется семейство случайных величин X(t), зависящих от параметра t, который пробегает некоторое множество значений T. Предполагается, что все эти случайные величины определены на одном и том же вероятностном пространстве и принимают действительные значения. Множество значений будем называть пространством состояний, а под параметром t будем понимать время. Так что величина X(t) указывает состояние системы в момент времени t. Множество значений t может быть дискретным или непрерывным Иногда вместо X(t) будем использовать обозначение X_t .

Определение. Случайный процесс X_t называется марковским, если для любого момента времени развитие процесса в последующие моменты времени (при ) зависит только от состояния процесса в момент времени t₀ и не зависит от того, когда и как процесс пришел в это состояние.

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

Например, в графе состояний (рис. 4.5.1) E0 означает, что устройство новое и не включено в работу, E₁ – устройство работает, E₂ – устройство неисправно, E₃ – происходит поиск причин неисправности, E₄ – производится ремонт, E₅ – устройство признано не подлежащим ремонту и утилизировано. Если ремонт удался, то происходит переход в состояние E₁.

Взаимное расположение состояний в графе позволяет их классифицировать следующим образом:

1. Состояние называется источником, если объект может выйти их него, но попасть вновь в него не может (в приведенном примере состояние E₀).
2. Состояние называется поглощающим (или концевым), если в него можно войти, но из него выйти нельзя (в приведенном примере состояние E₅).
3. Состояние E_i называется соседним к состоянию E_j , если возможен непосредственный переход из состояния E_j в состояние Ei . В приведенном примере E₃ соседнее состояние по отношению к E₂, но E₂ не соседнее состояние по отношению к E₃.
4. Подмножество состояний называется эргодическим (или связным), если из каждого состояния этого подмножества можно попасть в любое другое состояние этого подмножества.

Например, в графе (см. рис. 4.5.2)два эргодических подмножества состояний: и

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

С точки зрения описания объекта первостепенный интерес представляют вероятности состояний этого объекта. Обозначим через – вероятность того, что в момент времени t объект находится в состоянии E_i . Очевидно, что

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

Величину P_i можно понимать как среднюю долю времени, в течение которой объект находится в состоянии E_i. В общем случае зависят от всей предыстории переходов из состояния в состояние до момента времени t. Это чрезвычайно усложняет математическую модель такого процесса. В математическом плане наиболее просты марковские процессы, не обладающие «памятью» о прошлом.

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

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

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

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

Для однозначного в вероятностном смысле описания процесса переходов из состояния в состояние нужно, помимо переходных матриц, указать начальное распределение состояний, т.е. вероятности Обычно процесс начинается из определенного состояния E_i . Тогда а при

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

Заметим, что каждому графу состояний для однородной цепи соответствует определенная переходная матрица.

Графу состояний (рис. 4.5.3) соответствует переходная матрица

где  (это вероятности сохранить свое состояние на очередном шаге).

Пусть задано распределение состояний в начальный момент времени: По формуле полной вероятности получаем распределение состояний после первого шага:

Используя полученные вероятности, можно по формуле полной вероятности вычислить вероятности состояний на втором шаге:

Продолжение этих рассуждений приводит к рекуррентному соотношению 

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

Условия существования финальных вероятностей:

1. множество всех состояний должно быть эргодическим;
2. цепь должна быть однородной (во всяком случае переходные вероятности должны удовлетворять условию:
3. должно быть хорошее перемешивание состояний (не должно быть периодических циклов). 

Например, для цепи с графом состояний условие 3) не выполняется, так как при начале из состояния Е₁ на нечетном шаге цепь будет находиться в состоянии Е₂, а на четном — в состоянии Е₁.

Если для однородной цепи финальное распределение существует, то

и равенства (4.5.1) имеют вид

Иногда в этой записи выделяют слагаемые в правой части с Тогда

или

Для определения финальных вероятностей нужно решить систему линейных однородных уравнений (4.5.2). Такая система всегда совместна, (имеет тривиальное решение при всех i). Если же есть нетривиальные решения, то их бесконечно много. Для выбора необходимого единственного решения следует добавить условие нормировки

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

Пример 4.30.

Граф состояний марковской цепи изображен на рис. 4.5.4. При начальном распределении найти наименее вероятное состояние на третьем шаге. Найти финальные вероятности состояний цепи.

Решение. Переходная матрица этой цепи имеет вид

Найдем вероятности состояний цепи на первом шаге. Воспользуемся формулой (4.5.1), но учтем, что переходные вероятности нам каждом шаге одинаковы (цепь однородная) и поэтому

На втором шаге имеем вероятности состояний:

Для третьего шага получаем вероятности:

Можно, повторяя вывод уравнений (4.5.1), для определения финальных вероятностей записать систему равенств

 Но проще составить систему (4.5.3):

Решая систему, например, по правилу Крамера, получим Эти результаты означают, что примерно 20% времени цепь проведет в состоянии Е₁, 10% времени – состоянии Е₂, 70% времени – в состоянии Е₃.

Ответ. Е₂ – наименее вероятное состояние на третьем шаге;

Пример 4.31.

В городе N каждый житель имел одну из профессий A, B или C. Дети в следующем поколении сохраняли профессию отцов с вероятностями соответственно 0,6, 0,2 и 0,4 и с равными вероятностями выбирали любую из двух других профессий. Если в данный момент профессию A имеет 20% жителей города, профессию B – 30%, а профессию C – 50% жителей, то

1) каково распределение по профессиям будет в следующем поколении;

2) каким будет распределение по профессиям через много поколений (финальное распределение)?

Решение. Смену поколений будем считать шагом Марковской цепи. Имеем начальное распределение (на нулевом шаге): Переходная матрица имеет вид:

В соответствии с формулами (4.5.1) получаем распределение вероятностей на первом шаге (в первом поколении): 

Для вычисления финальных вероятностей составляем систему уравнений (4.5.2)

Эта система уравнений при условии нормировки имеет решение

Ответ. 

Пример 4.32.

Устройство состоит из двух блоков (например, двигатель и ходовая часть). Пусть A означает безотказную работу первого блока, B – безотказную работу второго блока. По истечении каждой единицы времени проверяется состояние этих блоков, и в случае неисправности производится их ремонт. Вероятность безотказной работы блоков в течение единицы времени равны соответственно 0,9 и 0,8. Если неисправность блока обнаружена, то вероятность отремонтировать блок в течение единицы времени равна соответственно 0,3 и 0,4. Найти предельные вероятности для состояний устройства:

Замечание. В сформулированном примере по умолчанию предполагается, что распределение времени безотказной работы и распределение времени ремонта каждого блока не имеют «памяти» о прошлом. Единственным распределением такого сорта является показательное распределение. Если, например, время ремонта распределено по показательному закону и ремонт уже продолжается некоторое время, то оставшаяся часть времени ремонта имеет то же самое распределение, что и в начале ремонта.

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

В итоге переходная матрица имеет вид

Составим систему уравнений для определения финальных вероятностей:

Это система линейных однородных уравнений, она имеет бесконечно много решений. Для получения единственного нужного нам решения вместо любого из уравнений запишем условие нормировки Решая систему, например, по формулам Крамера получим

Ответ.  

Пример 4.33.

В зоне обслуживания бригады ремонтников находится три прибора, работающих в автоматическом режиме. В конце каждого месяца ремонтники проводят профилактический осмотр приборов и, в случае обнаружения неисправных, забирают их для ремонта или замены на новые. Отремонтированный (или новый) прибор возвращают на место при очередном профилактическом осмотре, т.е. через месяц. Вероятность выхода из строя в течение месяца работающего прибора равна 1/3. Требуется найти стационарное распределение вероятностей числа исправных приборов в начале каждого месяца.

Решение. Рассмотрим марковскую цепь, состояния которой будем различать по числу работоспособных приборов. Пусть – означает, что работоспособны приборы. Всего имеется четыре возможных состояния:

Составим переходную матрицу этой цепи. Если на данном шаге цепь находится в состоянии E₀, то на очередном шаге будут доставлены три работоспособных прибора и цепь с вероятностью 1 перейдет в состояние E₃. Поэтому

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

При наличии на данном шаге двух годных приборов в соответствии с формулой Бернулли, имеем переходные вероятности:

Наконец, при трех годных приборах на данном шаге

Запишем переходную матрицу:

Этой переходной матрице соответствует система уравнений (4.5.2) для вычисления стационарных вероятностей: 

Решая эту систему уравнений, с учетом условия нормировки получаем

Ответ. 

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

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

Суммарный поток событий, выводящих процесс из состояния Е_i, тоже будет пуассоновским с интенсивностью Тогда вероятность покинуть состояние Е_i за малый промежуток времени равна

а вероятность сохранить состояние Е_i за малый промежуток времени равна

Выведем уравнения для вероятностей состояний процесса В момент процесс будет находиться в состоянии Е_i (вероятность чего равна ), если в момент t он находился в состоянии Е_i (вероятность чего равна ) и в течении времени оставался в этом состоянии (вероятность чего равна   ), или процесс в момент времени t находился в любом другом состоянии (с вероятностью ) и за время  перешел в состояние Е_i (вероятность чего равна  ). Символическая запись этой длинной фразы имеет вид

Если перегруппировать слагаемые, разделить равенство на , то при получим систему уравнений

Это система уравнений Колмогорова А.Н. Для решения системы нужно задать начальные условия, а вместо одного из уравнений можно использовать условие нормировки

Пример 4.34.

На рис. 4.6.1 дан граф состояний некоторого объекта. Интенсивности переходов из состояния в состояние указаны на этом же рисунке. Записать систему уравнений для вероятностей состояний объекта. При постоянных и найти предельные (финитные) вероятности его состояний.

Система уравнений Колмогорова (4.6.1) в рассматриваемом случае имеет вид

Вместо одного из уравнений (например, вместо второго) можно воспользоваться условием нормировки

Если то существуют стационарные вероятности, для которых все и система уравнений принимает вид

Эта система имеет решение

Пример 4.35.

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

Решение. Обозначим через – рабочее состояние механизма, через – состояние го отказа. Тогда граф состояний механизма имеет вид, изображенный на рис. 4.6.3.

Система уравнений (4.6.1) для этого случая имеет вид

Условия существования стационарных вероятностей марковского процесса выполнены. Поэтому при вероятности – постоянные величины, а Для стационарных вероятностей получаем систему

Из второго и третьего уравнений находим соответственно и Вместо первого уравнения используем условие нормировки:

Откуда

Ответ.  

Модели управления запасами

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

И поступление продукции и ее расход могут быть случайными и во времени и по объему.

Простым примером может служить водохранилище, уровень воды в котором зависит от притока (определяемого случайно выпадающими осадками) и расхода воды на разные нужды.

Представляют, например, интерес:

• 1) стационарное распределение запаса и условия его существования;
• 2) оптимальная политика пополнения и расхода запаса;
• 3) распределение периода нулевого уровня и т.д.

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

1. Приток. Пусть X_k – количество воды, поступившее в водохранилище за единицу времени (год, сутки, час и т.д.) от k до (k +1) моментов. Величины полагаем независимыми и одинаково распределенными.

2. Сток. Пусть объем водохранилища равен K. Обозначим через Z_n размер запаса в момент т.е. количество воды перед поступлением в хранилище X_n. Если , то водохранилище переполняется и избыток теряется. Поэтому в водохранилище запас будет равен

3. Правило расхода воды. В момент времени из водохранилища выпускают количество воды, равное если  . Если же то расходуют весь имеющийся запас Так что величина расхода равна Из этих допущений можно сделать вывод, что размер запаса удовлетворяет рекуррентному соотношению:

Последовательность образует однородную цепь Маркова.

Упростим задачу еще, полагая приток дискретным. Пусть 

В этом случае цепь Маркова имеет конечное число состояний Обозначим вероятности переходов из начального состояния за n шагов через

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

Обозначим производящую функцию распределения вероятностей через

Тогда средний приток в единицу времени равен

Матрица переходных вероятностей для цепи Маркова имеет вид:

Если все то цепь неприводимая и непериодическая. Поэтому существует стационарное распределение вероятностей

которые являются единственным решением уравнений

при условии, что Для этих вероятностей имеет место следующая теорема.

Теорема Морана (Moran P.). 1. Если – стационарное распределение запаса воды в хранилище емкости K, то отношения

не зависят от K.

2. Значения можно найти как коэффициенты при в разложении по степеням функции

Доказательство. Для доказательства первой части теоремы достаточно записать уравнения для финальных вероятностей

Решая последовательно эти уравнения, получим из первого уравнения:

Из второго уравнения получим:

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

Можно показать, что

В самом деле,

Отсюда при

Здесь величина равна среднему притоку.

Итак, представляет из себя сумму бесконечной геометрической прогрессии со знаменателем который тоже разложим по степеням z. Разложим в степенной ряд:

Коэффициенты определяются из равенства

если приравнять коэффициенты при одинаковых степенях z в его правой и левой частях. Величины этих коэффициентов совпадают с их значениями по формулам (4.7.4). Этим и завершается доказательство теоремы.

Пример 4.36.

Пусть в хранилище объема K поступление запаса имеет распределение

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

Решение. Воспользуемся теоремой Морана. Для этого сначала найдем производящую функцию для распределения случайной величины X.

Имеем 

Если то можно считать суммой бесконечной убывающей прогрессии. Поэтому

Из этой записи следует, что

Эти коэффициенты можно преобразовать к виду: 

Тогда в соответствии с формулами (4.7.2) имеем 

Если объем хранилища неограничен, то из условия нормировки:

Тогда 

Если же объем хранилища равен К, то согласно теореме Морана соотношения (4.7.6) остаются в силе, но условие нормировки имеет вид 

Поэтому – вероятность того, что к моменту очередного расхода запаса хранилище окажется пустым,

Ответ. 

Пример 4.37.

Хранилище имеет емкость шести единиц хранения (например, шесть контейнеров, шесть вагонов и т.д.). В течение каждого дня в хранилище поступает случайное количество продукции X. Величины X независимы и одинаково распределены:

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

Для стационарного режима требуется найти: вероятность того, что поставляемая продукция будет полностью (без потерь) принята на хранение; вероятность того, что отпуск продукции будет производиться в полном объеме.

Решение. Будем рассматривать состояния хранилища мгновение спустя после очередной отгрузки. Тогда возможных состояний будет пять: где номер состояния соответствует числу находящихся на хранении единиц продукции.

В нашем примере Составим переходную матрицу:

В соответствии с переходной матрицей запишем систему уравнений (4.7.1) для вычисления стационарных вероятностей:

Вместо любого из уравнений можно взять условие нормировки Итак, имеем систему уравнений

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

Подставляя найденное выражение для u₃ в предыдущее уравнение, получаем

С учетом (4.7.7) и (4.7.8) из третьего уравнения находим, что

Из первого уравнения и соотношений (4.7.7) – (4.7.9) следует, что

Воспользуемся теперь условием нормировки

откуда Подставляя найденное значение u₄ в равенства (4.7.7) – (4.7.10), получаем

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

Математическое ожидание количества теряемой продукции при каждом ее поступлении равно

ед. прод.

Вероятность того, что отпуск продукции будет производиться в полном объеме (в количестве двух единиц), равна

Заметим, что В среднем поступает столько, сколько должно тратиться за день. Но за счет неравномерности поступления продукции в хранилище возникают и неполные поставки и потери продукции из-за переполнения склада.

Ответ. 0, 906; 0,962.

Пример 4.38.

Хранилище имеет емкость пять единиц хранения. В течение каждого дня в хранилище поступает случайное количество X единиц продукции. Величины X независимы и имеют одинаковое распределение

При заполнении хранилища избыток поступившей продукции теряется. В конце каждого дня из хранилища отпускается потребителю случайное число единиц продукции (или весь запас, если он не превосходит ). Известно, что а

Для стационарного режима найдите: вероятность того, что поставляемая продукция будет полностью (без потерь) принята на хранение; вероятность того, что отпуск продукции будет производиться в полном объеме.

Решение. Если рассматривать состояние хранилища в моменты сразу после очередной отгрузки продукции, то имеется пять возможных состояний: где номер состояния соответствует числу находящихся на хранении единиц продукции. Состояния хранилища в моменты после очередной отгрузки образуют цепь Маркова. Найдем ее переходные вероятности.

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

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

Переходы происходят, если поступает одна единица хранения, а отгружаются две. Вероятность этого

Хранилище сохранит свое состояние E₂ или E₃, если поступит столько единиц хранения, сколько и будет отгружено. Поэтому

Переходы происходят, если поступит три единицы хранения, а будет отгружена только одна. Поэтому

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

Переход произойдет, если в хранилище поступит две или три единицы продукции, а будет отгружена только одна, вероятность чего равна

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

Хранилище сохранит свое состояние E₄, если при поступлении любого количества единиц хранения (хранилище тогда будет заполнено) будет отгружена одна единица хранения. Вероятность этого

Итак, переходная матрица имеет вид:

В соответствии с переходной матрицей запишем систему уравнений (4.7.1) для вычисления стационарных вероятностей:

Это система линейных однородных уравнений. Вместо любого из уравнений можно взять условие нормировки Тогда получится система линейных неоднородных уравнений. Решая эту систему любым способом (по формулам Крамера, по методу Гаусса и т.д.) получим, что

Вероятность потери поступающей продукции из-за переполнения склада равна т.е. потери составят около 7%. Вероятность полного приема на хранение равна

Вероятность отгрузки в требуемом объеме равна

Ответ.  0,9275; 0,9153.

Полумарковские процессы

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

Пусть – возможные состояния процесса. Чтобы задать ПМП необходимо указать:

1. матрицу вероятностей переходов
2. матрицу функций распределения – функция распределения времени пребывания процесса в состоянии при условии, что следующим состоянием будет
3. начальное распределение (например, при – это означает, что процесс начинается из состояния Е₁).

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

Практический интерес представляют многие характеристики ПМП:

1. среднее время достижения состояния из начального состояния;
2. среднее число попаданий в состояние за время t;
3. стационарные вероятности того, что процесс находится в состоянии .

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

где – среднее время пребывания в состоянии , а – математическое ожидание, соответствующее распределению

Обозначим через – среднее время до первого попадания из состояния в состояние Легко видеть, что

или

Откуда в силу (4.8.1) получаем систему уравнений для определения 

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

В заключение приведем частичную формулировку одной из важных теорем о ПМП.

Теорема Пайка (Pyke). Стационарные вероятности пребывания процесса в состояниях  равны 

где – финитные вероятности вложенной марковской цепи, – среднее время пребывания в состоянии , а – стационарные вероятности состояний.

Пример 4.39.

Пусть устройство состоит из трех однотипных приборов. В момент времени t=0 начинает работу прибор №1, который спустя случайное время Т₁ выходит из строя. В этот момент начинает работу прибор №2, длительность безотказной работы которого равна Т₂, и начинается ремонт прибора № 1, причем время ремонта равно  Если то в момент времени начинает работу прибор №1, а прибор №2 поступает на ремонт. Если же то начинает работать элемент №3, а вышедшие из стоя приборы продолжают ремонтироваться в порядке очереди с той же интенсивностью, и т.д. Устройство отказывает, если все три прибора выходят из строя. Предположим, что величины и независимы и имеют соответственно функции распределения и . Вычислим среднюю длительность безотказной работы системы (или «наработку на отказ»).

Пусть – количество работоспособных приборов в момент времени t. Система начинает работу при трех работоспособных приборах, поэтому при t=0 имеем , а в момент, когда , устройство выходит из строя. Одна из возможных реализаций процесса изображена на рис. 4.8.1

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

Для процесса в моменты переходов из состояния в состояние имеем вероятности переходов

Остается вычислить среднюю длительность пребывания системы в множестве состояний при условии, что функционирование системы начинается из состояния , т.е. наработка на отказ равна . Последнюю величину можно найти из системы уравнений, которая согласно (4.8.2) имеет вид:

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

Ответ.  

Пример 4.40.

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

Решение. Будем различать состояние E₀, в котором обслуживающий прибор исправен и свободен, состояние E₁, в котором прибор обслуживает требование, состояние E₂, в котором прибор неисправен и ремонтируется. Пусть – состояние системы в момент времени t. Процесс q t( ) является полумарковским. Назовем его характеристики.

1. Переходные вероятности:

(того, что требование поступит в свободную систему ранее, чем прибор выйдет из строя)

(того, что время обслуживания меньше времени безотказной 354 работы занятого прибора) 

Итак, переходная матрица имеет вид: 

Запишем уравнения для финитных вероятностей вложенной цепи:

Из первого и второго уравнений следует, что Поэтому из условия нормировки получаем, что

2. Вычислим теперь среднее время пребывания в каждом из состояний. Время пребывания в состоянии E₀ равно минимальному из времени паузы и времени безотказной работы свободного прибора. Пусть X – время пребывания в состоянии E₀, X₀ – время безотказной работы в ненагруженном состоянии, а X₁ – время до прихода ближайшего требования. Тогда X имеет функцию распределения

Это показательный закон распределения с параметром Поэтому среднее время пребывания в состоянии E₀ равно Время пребывания в состоянии E₁ равно минимуму времени обслуживания и времени выхода из строя занятого прибора. Поэтому

 

Это равенство получается из следующих соображений. Если X – неотрицательная случайная величина с функцией распределения то

в этом можно убедиться, взяв по частям интеграл в правой части равенства.

Пусть T – время пребывания системы в состоянии E₁, V – время обслуживания, W – время безотказной работы прибора в занятом состоянии. Тогда Так как а то

Время пребывания в состоянии E₃ равно времени ремонта. Поэтому

Доля времени пребывания в отказном состоянии равна стационарной вероятности состояния E₂. По формуле (4.8.4) эта стационарная вероятность равна

Ответ. 

Задачи с решением на случайные процессы

Поток требований называется простейшим, если интервалы времени между последовательными моментами прихода требований независимы и имеют показательный закон распределения.

Заметим, что в показательном законе распределения наиболее вероятны малые значения случайной величины. Это означает, что часто будут реализовываться малые интервалы между требованиями и редко – большие. Для наблюдателя это будет выглядеть как локальные сгущения требований и локальные разряжения. Тем самым подтверждается бытующее представление о «полосе везения» и «полосе невезения». Действительно, случайные события, даже будучи независимыми, имеют свойство группироваться во времени.

Задача 5.1 (о времени ожидания).

Отметим одну особенность простейшего потока, связанную с «парадоксом времени ожидания». Предположим сначала, что к остановке с равными интервалами подходят автобусы (поток автобусов детерминированный). Пассажир в случайный момент времени приходит на остановку и ожидает ближайшего по времени автобуса. Каково среднее время ожидания пассажира?

Решение. Пусть интервал между автобусами равен t. Так как равновозможно любое значение времени ожидания Х в пределах от 0 до , то среднее время ожидания равно

Пусть теперь моменты прибытия автобусов на остановку образуют простейший поток интенсивности Так как интервалы между последовательно приходящими автобусами имеют показательный закон распределения, то средний интервал между прибытиями автобусов будет равен

Интеграл можно взять по частям. Поэтому 

Плотность вероятности того, что момент прихода пассажира придется на интервал между автобусами длины , имеет вид

Согласно (5.1) при интервале между автобусами длиной х среднее время ожидания равно . Поэтому среднее время ожидания в случае простейшего потока равно

(последний интеграл дважды берется по частям). Итак, при регулярном потоке среднее время ожидания равно половине интервала между прибытиями автобусов. При чисто случайном потоке автобусов среднее время ожидания совпадает со средним интервалом между автобусами.

Заметим, что среднее время ожидания пассажира может быть значительно больше среднего интервала между автобусами. Например, пусть автобусы приходят по расписанию, но такому, что сначала подряд с интервалами в две минуты проходят пять автобусов, а шестой приходит через 50 минут. Тогда средний интервал будет равен мин.

Пассажир может с вероятностью 1/5 попасть на череду коротких интервалов между автобусами и среднее время ожидания для него будет равно 1 мин. На большой интервал можно попасть с вероятностью 5/6 и тогда среднее время ожидания будет 25 мин. Поэтому среднее время ожидания равно мин. Минимальным среднее время ожидания будет при регулярном потоке автобусов при равных интервалах между ними.

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

Найдем плотность вероятности длины того интервала , на который попала случайная точка t. Понятно, что шансы точкой попасть в длинный интервал больше, чем в короткий. Поэтому сам факт попадания случайной точки t на интервал меняет его распределение. Рассмотрим

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

При получается точное равенство, из которого следует:

Средняя длина интервала, в который попала точка, равна

Так как  то 

Например, для показательного закона распределения интервалов (для простейшего потока событий интенсивности поэтому и

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

Пусть и соответственно функция распределения и функция плотности вероятности интервала X между моментами появления соседних событий. Предположим, что с момента появления последнего события уже прошло время t. Найдем распределения оставшейся части интервала, которую обозначим через R:

откуда 

Задача 5.2 (о наилучшем выборе)

Имеется n однородных предметов различного качества, причем заранее о предметах ничего не известно. Предметы можно выбирать наугад по одному и обследовать. Если качество предмета нас не устраивает, то выбираем очередной предмет, но к отвергнутому предмету вернуться нельзя. Какой стратегии следовать, чтобы вероятность выбрать наилучший предмет была наибольшей? (Эту задачу называют еще задачей о разборчивой невесте. К невесте последовательно сватаются n женихов. Жених, получивший отказ, повторно не сватается.)

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

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

Обозначим через – событие, состоящее в том, что наилучшим является й предмет и при этом наилучший из первых k предметов находится среди первых предметов (последнее условие гарантирует нам, что дело дойдет до выбора го предмета.). Тогда 

Выберем число s между 0 и 1 и пусть – наибольшее целое число, меньшее, чем ns. Определим при наилучшее значение s (наилучшее в смысле максимизации исследуемой вероятности). Заметим:

Найдем максимальное значение функции По необходимому условию экстремума  – критическая точка. В этой точке функция имеет максимум так как в этой точке

Итак, оптимальная стратегия рекомендует просмотреть примерно треть предметов (точнее, ) и затем остановить свой выбор на первом предмете лучшем, чем все ранее просмотренные. Не исключено, что лучший предмет уже был просмотрен в первой трети предметов, и отвергнут. Тогда придется остановиться на последнем из предметов. Еще раз подчеркнем, что предлагаемая стратегия не гарантирует выбор наилучшего предмета, но делает его выбор наиболее вероятным.

Задача 5.3.

Вы принимаете участие в телеигре, и Вам предлагают выбрать одну из трех шкатулок, в одной из которых лежат деньги. Вы выбрали некоторую шкатулку (например, шкатулку №1). Ведущий после этого открывает одну из двух других шкатулок (например, шкатулку №3), показывает, что она пуста, и спрашивает: не желаете ли Вы изменить свое решение и выбрать шкатулку №2? Следует ли Вам менять свое решение или нет?

Решение. Будем полагать, что ведущий знает, где деньги лежат, и поэтому открывает именно пустую шкатулку. Насчет шкатулки с деньгами есть три одинаково вероятных предположения: – деньги находятся в й шкатулке,

Событие A состоит в том, что Вы выбрали шкатулку №1, а ведущий открыл шкатулку №3. При пустой третьей шкатулке в силу симметрии Ваши шансы на выигрыш равны 1/2.

Если деньги действительно находятся в первой шкатулке, то ведущий с вероятностью 1/2 откроет именно шкатулку №3. Поэтому

Если деньги находятся во второй шкатулке, то ведущий с вероятностью 1 откроет именно шкатулку №3

Если деньги в третьей шкатулке, то вероятность выбора ведущим третьей шкатулки нулевая

По формулам Байеса 

Если ведущий не знает где деньги лежат, то и тогда

Итак, игроку предварительно следует осведомиться у ведущего, знает ли он где деньги лежат. При положительном ответе следует изменить свой выбор. Если ведущий не знает, в какой шкатулке деньги, то менять выбор смысла нет.

Задача 5.4.

Производитель некоторой продукции затеял рекламную акцию. Объявлено, что в каждый пакет продукта заложен один из n различных типов жетонов. Покупатель, собравший все n типов жетонов, получает дисконтную карту для длительных скидок на этот продукт. Сколько в среднем пакетов продукта придется купить, чтобы собрать полный комплект из n различных жетонов?

Решение. Понятно, что по мере накопления жетонов, шансы найти новый жетон в очередном пакете убывают. Обозначим через – число пакетов, которые придется купить после обретения -го жетона, чтобы найтий жетон. Тогда общее число купленных пакетов

А математическое ожидание этого числа равно 

Вероятность того, что для поиска второго жетона придется вскрыть k пакетов, равна

(имеется в виду, что раз попадутся пакеты с уже обретенным жетоном и k-й по счету жетон с вероятностью — будет содержать жетон нового типа). Соответственно

Известно, что это геометрический закон распределения. Но для геометрического закона распределения: среднее значение равно

В нашем случае для вероятность Поэтому В итоге

или

Например, при имеем

В заключение можно заметить, что при больших n можно воспользоваться асимптотической формулой

Приложения

Таблица П.1

Таблица значений функции 

Таблица П.2

Таблица значений функции 

Таблица П.3

Значения удовлетворяющие равенству где – плотность вероятности распределения Стьюдента с n–1 степенью свободы

Таблица П.4

Значения удовлетворяющие равенству , где – плотность распределения «хи-квадрат» с степенями свободы

Таблица П.5

Значения функции (распределение Пуассона)

Определение случайных процессов

Элементы теории случайных процессов:

Пусть задано вероятностное пространство , где  — пространст­во элементарных событий, F —  -алгебра событий, Р — вероятностная мера.
Рассмотрим функцию  двух аргументов, где  элемент  и t — свободный аргумент, обычно время.
 

Случайным процессом называется случайная величина , заданная на вероятностном пространстве  Так как параметр t интерпретиру­ется как время, то если t = (0,1,2,…), то говорят что  — процесс с дис­кретным временем’, если  — процесс с непрерывным временем.
 

Пусть  приняло какое-то конкретное значение  Тогда  будет функцией только аргумента t и называется реализацией случайного процесса. Другими словами, реализация — это тот вид, который принимает случайный процесс в результате какого-то конкретного опыта (рис. 13.1). В каждом опыте наблюдается своя реализация  случайного процесса (СП). Сово­купность реализаций  носит название ансамбля. Значение случайного процесса в некоторый момент времени t называется отсчетом.

Рассмотрим отсчет  случайного процесса x(t) в момент времени  (см. рис. 13.1).

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

Более подробное представление о случайном процессе получается, если рассматривать два отсчета , берущихся в моменты времени   И характеризовать их двумерной плотностью распределения:  Тогда мерная плотность распределения запишется так:

                                             (13.1)

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

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

Числовые характеристики случайного процесса

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

Математическое ожидание случайного процесса (среднее по ансамблю) вводится следующим образом:

В отличие от теории вероятностей  не число, а функция от времени.
Оно дает некоторую кривую, около которой группируются все реализации случайного процесса (рис. 13.2).

Дисперсия случайного процесса (средняя по ансамблю):
                                       (13.3)

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

Функция корреляции случайного процесса (средняя по ансамблю)’.
                                    (13.4)

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

Наряду с  употребляется еще одна функция корреляции — это функ­ция корреляции флуктуаций’.
(13.5)
 

И нормированная функция корреляцию.
                                           (13.6)

Последняя ничем по смыслу не отличается от коэффициента корреляции и определяет степень линейной зависимости отсчетов случайного процесса в моменты времени

Стационарные случайные процессы

Случайный процесс называется стационарным в узком смысле, если для любых  и любых целых  имеет место равенство
                 (13.7)

Смысл определения в следующем.

В левой части равенства стоят отсчеты, берущиеся в моменты времени  и плотность распределений  полностью описывает свойства случайного процесса в моменты времени  В правой части равенства стоят отсчеты, берущиеся в моменты времени  и соответствующая плотность распределений  описывает свойства случайного процесса в эти сдвинутые моменты времени. Равенство этих плотностей распределений означает, что свойства случайного процесса одинаковы как в моменты времени  , так и в моменты времени  Таким образом, стационарность в узком смысле означает, что все свойства, характеристики и т. п. случайного процесса не зависят от начала отсчета времени. Грубо говоря, какими свойствами обладает случайный процесс сегодня, такие же свойства он имел год тому назад и такие же свойства он будет иметь через 1000 лет. Но реально это несколько не так. Все меняется, но нас интересуют отрезки времени, малые по сравнению со временем существования самого процесса.
 

Следствия стационарности:

1. Предположим в (13.7) , получим

Поскольку  произвольно, то полагая  получим:

Поэтому

 Отметим, что у стационарных случайных процессов математическое ожидание, дисперсия и плотность распределения от времени не зависят и D — числа, плотность распределения  — функция только от

 2. Полагая в (13.7)  = 2 и  = получим

Тогда функция корреляции принимает вид

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

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

На рис. 13.3 показан вид стационарного случайного процесса.

Числовые характеристики случайного процесса — средние по времени

Ранее мы рассмотрели числовые характеристики случайного процесса, средние по ансамблю, общий вид которых
(13.8)
Они называются средними по ансамблю потому, что фиксируются моменты времени  и перебираются все возможные значения , т. е. весь ансамбль реализаций случайного процесса, на рис. 13.4 жирной линией
изображены Кривые плотностей распределений  в моменты времени

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

Характерным для средних по времени является то, что фиксируются реализации, а «перебираются» все моменты времени. В средних по времени характерно также отсутствие плотности распределения т. к. для стационарных процессов все моменты времени равноправны.

Тогда числовые характеристики средние по времени определяются так:

1. Математическое ожидание случайного процесса среднее по времени:
                         (13.10)

2. Дисперсия случайного процесса средняя по времени:
                               (13.11)

3. Функция корреляции, средняя по времени (в ней фигурирует произведение значений случайного процесса в два различных момента времени  и ). Учитывая, что усредненная величина имеет вид , получим
                        (13.12) 

Свойства функций корреляции случайного процесса

1. Функция корреляции является симметричной функцией:

Для стационарного случайного процесса — четная функция:

2. Функция корреляции — ограниченная функция. Воспользуемся неравенством

Шварца (неравенство Коши-Буняковского):
                                      (13.13)
Обозначим отсчеты, как  и подставим в (13.13):

 С учетом определения (13.4), получаем

Тогда

 Когда  получаем:

3. Для стационарного случайного процесса дисперсия и математическое ожидание могут быть получены через функцию корреляции: 

Откуда следует, что
.
Найдем дисперсию:

Если рассматривать функцию корреляции флуктуаций (13.5), то

4. Функция корреляции является положительно определенной функцией.

Рассмотрим моменты времени , и произвольные величины  поскольку:

вычисляя математическое ожидание, получим

 

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

5. Время корреляции для стационарного случайного процесса определяется как
                                       (13.14)

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

6. При изучении реальных случайных процессов для  используют следующие аппроксимации:

Зависимость  приведена на рис. 13.5.

Зависимость  приведена на рис. 13.6.

Эргодические случайные процессы

Случайный прогресс называется эргодическим, если для него временные средние с вероятностью, равной 1, совпадают с соответствующими средними по ансамблю:

Эргодическим может быть только стационарный случайный процесс, но не всякий стационарный случайный процесс может быть эргодичен. Эргодичность имеет большое значение: она позволяет заменить изучение ансамбля реализаций изучением одной длинной реализации, т. к. каждая реализация (у эрго­дического случайного процесса) с вероятностью 1 имеет те же характеристики, что и весь ансамбль.

Спектр мощности случайного процесса

 — амплитудный спектр и

 — фазовый спектр функции x(t) .
Для стационарного случайного процесса поэтому преобра­зование Фурье можно ввести так: определим урезанный случайный процесс 

Тогда  и для процесса  можно написать  разложение в интеграл Фурье:

Рассмотрим величину  . В большинстве физических формул  — величина пропорциональна энергии случайного процесса на интервале а величина W имеет смысл средней мощности случайного процесса.

ее свойство: 

                  (13.19)
Обозначим  -эта функция называется спектром мощности случайного процесса.
 

Тогда запишем среднюю мощность так:
                         (13.20)
где  — мощность, выделяемая случайным процессом в полосе частот

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

Теорема Винера-Хинчина

Эта теорема устанавливает связь между спектром мощности и функцией корреляции. Запишем функцию корреляции (13.12) через урезанный случайный процесс:

комплексная величина, поэтому запишем  в виде комплексно сопряженных величин, используя (13.17):  и учтем сопряженную вели­чину

                                (13.21)

Таким образом, видим, что функция корреляции является прямым преобразованием Фурье от спектра мощности
                 (13.22)

Тогда спектр мощности определится через обратное преобразование Фурье:

                          (13.23)
Запишем спектр мощности через тригонометрические функции, используя формулу Эйлера:

                                       (13.24)

Последний интеграл в (13.24) равен нулю, т. к.  четная функция. Тогда
              (13.25)

Отсюда следует, что спектр мощности  также четная функция. С учетом выше сказанного перепишем функцию корреляции (13.22):

                                    (13.26)

В формулы (13.25), (13.26) входит круговая частота   линейная частота. Перепишем эти формулы через линейную частоту, вводя обо­значения  Тогда
                    (13.27)
                     (13.28)

В этих формулах фигурируют отрицательные частоты от  до 0, т. к. они ничем не отличаются от положительных, то часто рассматривают только частотный интервал  и определяют  так:

В (13.29) мощность отрицательных частот прибавили к мощности поло­жительных, тогда
                 (13.30)

 (13.31) 

Если вместо  взять функцию корреляции флуктуаций, то получится спектр мощности флуктуаций:
                                              (13.32)

                                                   (13.33)
 

Соотношение неопределенности для стационарных случайных процессов

Шириной спектра случайного процесса называется величина

Время корреляции

Умножая (13.34) на (13.35) получаем

Подставляя в круговую частоту, получим  и окончательно
                                       (13.36)

Разложение случайного процесса в ряд Котельникова

Пусть  — функция корреляции случайного процесса  Учитывая, что  можно записать  Здесь функция корреляции зависит от момента времени , поэтому запишем функцию корреляции как функцию двух аргументов . Тогда на основании теоремы Винера- Хинчина можно записать

Теорема: Если  для всех  при , то имеет место разло­жение

                                         (13.38)

где  — отсчет случайного процесса в момент времени
На рис. 13.7 показана заштрихованная область частот, для которой спектр мощности

Доказательство:

Предположим, что спектр мощности является периодической функцией с периодом  Тогда спектр мощности можно представить в виде ряда Фурье:

                          (13.39)
Коэффициенты  определяются как

Подставим  в (13.39):

Определим функцию корреляции, используя (13.37):

Поскольку функция корреляции симметрична, то можно записать

Докажем основное положение теоремы. Используем следующее опреде­ление сходимости: Последовательность случайных величин сходится к случайной величине X в среднем квадратическом, если  Это определение заложено в основу метода наименьших квадратов.

Используя (13.38), можно записать

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

Классификация случайных процессов

Ранее, в разделе 13.1 мы отмечали, что все случайные процессы делятся на два основных класса: прогрессы с дискретным временем и процессы с непрерывным временем. После описания вероятностных характеристик случайного процесса, в частности мерной плотности распределения (раздел 13.1), мы да­лее ввели следующее разделение случайных процессов с учетом ограничений их вероятностных характеристик: стационарные в узком смысле и стационарные в широком смысле (раздел 13.3). Затем для стационарных случайных процессов в узком смысле мы ввели понятие эргодических случайных процессов (раздел 13.6). Далее мы рассмотрели энергетические характеристики случайных процессов, в частности спектр мощности случайного процесса (раздел 13.7).

Иногда стационарные случайные процессы классифицируют по спектральным
характеристикам: различают стационарные случайные процессы в широком смысле — узкополосные, когда спектр мощности сосредоточен в узкой полосе частот возле определенной фиксированной частоты  В разделе 13.9 мы вве­ли понятие ширины спектра  если  то стационарный случайный процесс будет называться узкополосным. На рис. 13.8 изображен узкополосный спектр мощности  случайного процесса. На рис. 13.9 функция корреляции узкополосного случайного процесса.

 

 Из рис. 13.9 видим, что функция корреляции узкополосного случайного процесса — это быстро осциллирующая функция с частотой  но с медленно меняющейся огибающей. Ширина спектра  и время корреляции определяются правыми частями формул (13.34) и (13.35).

Следующим классом будут стационарные в широком смысле случайные процессы — широкополосные. Здесь спектр мощности сохраняет постоянное значение  на всех частотах (рис. 13.10):
 (13.41)

Тогда стационарный в широком смысле случайный процесс с равномер­ным спектром мощности на всех частотах называется белым шумом. Функ­ция корреляции белого шума представляет собой 5-функцию, расположенную в начале координат, (рис. 13.11):

 

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

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

Марковские случайные процессы

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

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

Цепи Маркова

Пусть некоторая физическая система может находиться в состояниях  и переходить случайным образом из состояния в состояние в фиксированные моменты времени Эволюция системы образует дискретную цепь Маркова с дискретным временем, если выполняется следующее условие (13.43) (условная вероятность в состояниив момент времени  опре­деляется при условии, что в момент система была в состоянии  ): 

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

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

Введем понятие переходной вероятности — это вероятность перехода системы из одного состояния в другое:

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

                                (13.45)

Свойства матрицы переходных вероятностей:

1.

2. Сумма по строке —  — количество состояний.

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

Вероятность перехода за  шагов. Рассмотрим вероятность перехода из состояния , которое реализовано в  испытании, в состояние  за  шагов, т. е. в состояние  испытании. Эта вероятность зависит только от (и не зависит от ). Обозначим ее  Тогда  — вероятность перехода за  шагов из состояния в состояние  — вероятность перехода за  шагов из состояния — (рис. 13.12). Используя формулу полной вероятности и учитывая, что промежуточные состояния  испытании образуют полную группу попарно несовместимых событий, получим
    (13.46)

Формула Маркова для цепей

Обозначим через , матрицу, составленную из вероятностей  таким образом — матрица перехода через  испытаний. Используя формулу для перемножения квадратных матриц (13.46), можно записать в матричном виде:
                               (13.47)
Применяя последовательно формулу (13.47), получим

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

Пусть существует предел
                            (13.48)
 

Тогда говорят, что существует предельное, финальное, распределение веро­ятностей  состояний  , не зависящее от начального распределения . Финальные вероятности удовлетворяют следующей системе уравнений:

 

Пример №8

Дана цепь Маркова, которая описывается матрицей переходных вероятностей

(сумма вероятностей по строке равна 1).

Необходимо определить вероятность  системы в 1-м состоянии.
 

Решение.

Запишем вероятность перехода за  шагов, применяя формулу (13.46), получим для

Обозначая  , запишем вероятность перехода за  шагов в новых переменных:

Учтем, что  — сумма геометрической прогрессии, тогда

Найдем предел при

Тогда искомая вероятность вычисляется так:

Марковские процессы с непрерывным временем

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

Среди марковских процессов с непрерывным множеством состояний наиболее важными являются процессы, которые имеют -мерную плотность рас­пределения. Если  — случайный процесс, , то пусть для каждого набора моментов времени мерная случайная величина  имеет  мерную плотность распределения  Эта плотность обладает следующими свойствами:

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

2. Плотность любого мерного распределения при  определятся с помощью мерного распределения:

Поскольку вероятностные свойства процесса в момент  определяются состоянием в момент и не зависят от протекания процессов в предшествующие моменты времени, тогда условная плотность распределения

                    (13.51)

Условную плотность распределения  называют переходной плотностью распределения в состояние  при условии, что процесс находится в состоянии

Зная, что  для условной плотности распределения

                                    (13.52)

Учитываем свойство марковских цепей:

                                                (13.53)

Тогда  и применяя эту формулу в правой части для  а затем для , получим
                                            (13.54)

Отсюда видно, что для задания мерной плотности распределения марковского процесса достаточно знать лишь две функции: одномерную плотность  и переходную плотность распределения .

Рассмотрим 3 момента времени:  Согласно (13.54), имеем
                             (13.55)

                                             (13.56)

Это уравнение Смолуковского (или Колмогорова-Чепмена) является основным в теории непрерывных марковских процессов.

Уравнения Колмогорова

Введем следующие обозначения:

Запишем переходные вероятности через уравнение Смолуковского в моменты
                                (13.59)

                                       (13.60)
Вычтем из формулы (13.60) формулу (13.59):

                                    (13.61)
Разложим в ряд Тейлора функцию

Подставляя это разложение в интеграл (13.61), разделим левую и правую часть на  и перейдем к пределу при
                            (13.62)

                (13.63)

Это первое уравнение Колмогорова, где
             (13.64)

              (13.65)

Аналогично выводится втрое уравнение Колмогорова:

                  (13.66)

Здесь — те же функции, что и  (13.64) и  (13.65), но взятые для

Непрерывный марковский процесс, который описывается уравнениями (13.63) и (13.66) называется диффузионным. Коэффициент  называется коэффициентом сноса, а коэффициент  — коэффициентом диффузии.
Уравнение (13.66) называется прямым уравнением Колмогорова, а уравнение (13.63) называется обратным уравнением Колмогорова. Уравнения Колмогорова относятся к классу параболических дифференциальных уравнений в частных производных.

Уравнения Колмогорова.
Предельные вероятности состояний

Рассмотрим математическое описание марковского процесса с дискретными состояниями и непрерывным временем* на примере случайного процесса из примера 1, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния в происходят под воздействием простейших потоков событий с интенсивностями ; так, переход системы из состояния в будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния в — под воздействием потока «окончаний ремонтов» первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. 1). Рассматриваемая система имеет четыре возможных состояния: .

Вероятностью i-го состояния называется вероятность того, что в момент система будет находиться в состоянии . Очевидно, что для любого момента сумма вероятностей всех состояний равна единице:

Рассмотрим систему в момент и, задав малый промежуток , найдем вероятность того, что система в момент будет находиться в состоянии . Это достигается разными способами.

1. Система в момент с вероятностью находилась в состоянии , а за время не вышла из него.

Вывести систему из этого состояния (см. граф на рис. 1) можно суммарным простейшим потоком с интенсивностью , т.е. в соответствии с формулой (7), с вероятностью, приближенно равной . А вероятность того, что система не выйдет из состояния , равна . Вероятность того, что система будет находиться в состоянии по первому способу (т.е. того, что находилась в состоянии и не выйдет из него за время ), равна по теореме умножения вероятностей:

2. Система в момент с вероятностями (или ) находилась в состоянии или и за время перешла в состояние .

Потоком интенсивностью (или — с- рис. 1) система перейдет в состояние с вероятностью, приближенно равной (или ). Вероятность того, что система будет находиться в состоянии по этому способу, равна (или ).

Применяя теорему сложения вероятностей, получим

откуда

Переходя к пределу при (приближенные равенства, связанные с применением формулы (7), перейдут в точные), получим в левой части уравнения производную (обозначим ее для простоты ):

Получили дифференциальное уравнение первого порядка, т.е. уравнение, содержащее как саму неизвестную функцию, так и ее производную первого порядка.

Рассуждая аналогично для других состояний системы , можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний:

Сформулируем правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности i-го состояния. В правой части — сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-го состояния).

В системе (9) независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение (8).

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

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы в предельном стационарном режиме, т.е. при , которые называются предельными (или финальными) вероятностями состояний.

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

Предельная вероятность состояния имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния , т.е. , то это означает, что в среднем половину времени система находится в состоянии .

Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы с графом состояний, изображенном на рис. 1), такая система уравнений имеет вид:

Систему (10) можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в уравнениях стоит предельная вероятность данного состояния , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

---

Пример 2. Найти предельные вероятности для системы из примера 1, граф состояний которой приведен на рис. 1, при

Решение. Система алгебраических уравнений, описывающих стационарный режим для данной системы, имеет вид (10) или

(Здесь мы вместо одного «лишнего» уравнения системы (10) записали нормировочное условие (8)).

Решив систему (11), получим , т.е. в предельном, стационарном режиме система в среднем 40% времени будет находиться в состоянии (оба узла исправны), 20% — в состоянии (первый узел ремонтируется, второй работает), 27% — в состоянии (второй узел ремонтируется, первый работает) и 13% времени — в состоянии (оба узла ремонтируются)

---

Пример 3. Найти средний чистый доход от эксплуатации в стационарном режиме системы в условиях примеров 1 и 2, если известно, что в единицу времени исправная работа первого и второго узлов приносит доход соответственно в 10 и 6 ден.ед., а их ремонт требует затрат соответственно в 4 и 2 ден.ед. Оценить экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Решение. Из примера 2 следует, что в среднем первый узел исправно работает долю времени, равную , а второй узел — . В то же время первый узел находится в ремонте в среднем долю времени, равную , а второй узел — . Поэтому средний чистый доход в единицу времени от эксплуатации системы, т.е. разность между доходами и затратами, равен

ден. ед.

Уменьшение вдвое среднего времени ремонта каждого из узлов в соответствии с (6) будет означать увеличение вдвое интенсивностей потока «окончаний ремонтов» каждого узла, т.е. теперь и система линейных алгебраических уравнений (10), описывающая стационарный режим системы , вместе с нормировочным условием (8) примет вид:

Решив систему, получим .

Учитывая, что , а затраты на ремонт первого и второго узла составляют теперь соответственно 8 и 4 ден.ед., вычислим средний чистый доход в единицу времени:

ден.ед.

Так как больше (примерно на 20%), то экономическая целесообразность ускорения ремонтов узлов очевидна.

---

Процесс гибели и размножения

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рис. 4.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями или .

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

В соответствии с правилом составления таких уравнений (см. 13) получим: для состояния

для состояния имеем , которое с учетом (12) приводится к виду

Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений:

к которой добавляется нормировочное условие

При анализе численности популяций считают, что состояние соответствует численности популяции, равной , и переход системы из состояния в состояние происходит при рождении одного члена популяции, а переход в состояние — при гибели одного члена популяции.

Решая систему (14), (15), можно получить

Легко заметить, что в формулах (17) для коэффициенты при есть слагаемые, стоящие после единицы в формуле (16). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния , а знаменатели — произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния .

---

Пример 4. Процесс гибели и размножения представлен графом (рис. 5). Найти предельные вероятности состояний.

Решение. По формуле (16) найдем

по (17)

т.е. в установившемся, стационарном режиме в среднем 70,6% времени система будет находиться в состоянии , 17,6% — в состоянии и 11,8% — в состоянии .

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.