Цепи Маркова в теории вероятности и их приложения - диплом по математике

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

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

Условно будем говорить о некоторой физической системе, шаг за шагом меняющей свое фазовое состояние. Будем считать, что имеется лишь конечное или счетное число различных фазовых состояний ε₁, ε₂, ... Обозначим ξ (п) состояние системы через п шагов. Будем предполагать, что цепочка последовательных переходов

ξ(0) → ξ (1) …

зависит от вмешательства случая, причем соблюдается следующая закономерность: если на каком-либо шаге п система находится в состоянии ε_i, то, независимо от предшествующих обстоятельств, она на следующем шаге с вероятностью p_ij переходит в состояние ε_j

Задача о наилучшем выборе. Положим ξ₀(0)=1 и обозначим: ξ(1) - порядковый номер первого предмета, оказавшегося наилучшим среди всех осмотренных ранее; ξ(2)-порядковый номер следующего наилучшего среди всех осмотренных до него предметов и т. д. Цепочка ξ(0)→ξ(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, а p_m+1, m+1=1. Подсчитаем вероятности p_ij при 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, т. е. p_ij(N)=β>0 при некотором N. Как следует из формулы (8.7), при любом п

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

Рассмотрим теперь случайное блуждание, при котором частица из неотрицательной целой точки i на следующем шаге с вероятностью р_i смещается в соседнюю точку j = i + 1, а с вероятностью q_i = 1-р_i переходит в нулевую точку j = 0. Очевидно, если все вероятности р_i таковы, что 0<p_i<1, то все состояния являются достижимыми одно из другого. Все они будут возвратными или невозвратными.

Предположим, что система находится в состоянии i=0. Вероятность того, что за последующие п шагов она ни разу не вернется в исходное положение i = 0, равна произведению p₀p₁ …p_n-1 - вероятности того, что система последовательно пробегает цепочку состояний 0→1→...→п. Легко видеть, что вероятность за бесконечное число шагов ни разу не вернуться в исходное состояние i = 0 равна бесконечному произведению