Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей". В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений, особое внимание марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений.
Марковские цепи используются в теории массового обслуживания для расчета распределения вероятностей числа занятых приборов в системе, состоящей из n приборов с пауссоновским потоком требований и показательным законом времени обслуживания.
Условно будем говорить о некоторой физической системе, шаг за шагом меняющей свое фазовое состояние. Будем считать, что имеется лишь конечное или счетное число различных фазовых состояний ε1, ε2, ... Обозначим ξ (п) состояние системы через п шагов. Будем предполагать, что цепочка последовательных переходов
ξ(0) → ξ (1) …
зависит от вмешательства случая, причем соблюдается следующая закономерность: если на каком-либо шаге п система находится в состоянии εi, то, независимо от предшествующих обстоятельств, она на следующем шаге с вероятностью pij переходит в состояние εj
Задача о наилучшем выборе. Положим ξ0(0)=1 и обозначим: ξ(1) - порядковый номер первого предмета, оказавшегося наилучшим среди всех осмотренных ранее; ξ(2)-порядковый номер следующего наилучшего среди всех осмотренных до него предметов и т. д. Цепочка ξ(0)→ξ(1)→ξ(2)... обрывается на некотором ν-м шаге, если предмет с порядковым номером ξ(ν) оказывается абсолютно наилучшим, так что и среди не осмотренных еще предметов нет лучшего. Число ν является случайным, поскольку случайным является сам порядок осмотра. Введем состояния ε1, ε2, …εm, εm+1, охарактеризовав их следующим образом: εi при i=1, …, т означает, что предмет с порядковым номером i (т. е. i-й по счету осмотренный предмет) является наилучшим среди всех ранее осмотренных; εm+1 означает, что уже осмотрен абсолютно наилучший предмет. Если положить ξ(n) = εm+1, при всех п>ν, то последовательность ξ(0)→ξ(1)→ξ(2)... образует цепь Маркова.
Найдем соответствующие переходные вероятности рij Очевидно, рij=0 при i≥j, j≤m, а pm+1, m+1=1. Подсчитаем вероятности pij при i<j≤m. Обозначим εi событие, состоящее в том, что при случайном порядке осмотра j предметов наилучшим среди них является последний j-й предмет. Очевидно, переходные вероятности рij согласно общей формуле () совпадают с условными вероятностями
Случайные блуждания. Рассмотрим случайное блуждание, связанное с неограниченными испытаниями Бернулли, когда частица блуждает по целочисленным точкам действительной прямой таким образом, что, находясь в точке i она с вероятностью р переходит на следующем шаге в соседнюю точку i + 1, а с вероятностью q=1-р - в соседнюю точку i-1. Если обозначить ξ(n) положение частицы после п шагов, то последовательность ξ(0) →ξ(1)→ξ(2)... будет цепью Маркова с переходными вероятностями вида
Пусть εi - возвратное состояние εj достижимо из εi. Тогда εi в свою очередь достижимо из εj, так как в противном случае, выходя из εi система за М шагов с положительной вероятностью рij (М)=α>0 попадает в состояние εj, после чего уже не может вернуться в εi; таким образом, вероятность возвращения в εi будет не больше, чем 1-α, а это противоречит возвратности εi. Итак, если εj достижимо из возвратного состояния εi, то в свою очередь εi достижимо из εj, т. е. pij(N)=β>0 при некотором N. Как следует из формулы (8.7), при любом п
Интуитивно ясно, что, например, при р>q блуждающая частица постепенно будет уходить все дальше и дальше в положительном направлении, рано или поздно навсегда покидая любое фиксированное состояние i. При неограниченно продолжающемся симметричном случайном блуждании, когда р = q=, частица бесконечное число раз возвращается в каждое из состояний.
Рассмотрим теперь случайное блуждание, при котором частица из неотрицательной целой точки i на следующем шаге с вероятностью рi смещается в соседнюю точку j = i + 1, а с вероятностью qi = 1-рi переходит в нулевую точку j = 0. Очевидно, если все вероятности рi таковы, что 0<pi<1, то все состояния являются достижимыми одно из другого. Все они будут возвратными или невозвратными.
Предположим, что система находится в состоянии i=0. Вероятность того, что за последующие п шагов она ни разу не вернется в исходное положение i = 0, равна произведению p0p1 …pn-1 - вероятности того, что система последовательно пробегает цепочку состояний 0→1→...→п. Легко видеть, что вероятность за бесконечное число шагов ни разу не вернуться в исходное состояние i = 0 равна бесконечному произведению
work4.rtf | 1.621 Мб |