Цепи Маркова

№4

Дано:

Абонент забыл последнюю  цифру номера телефона и поэтому  набирает её наугад. Определить вероятность  того, что ему придётся звонить  не более чем в 3 места.

Решение:

Вероятность набрать верную цифру из десяти равна по условию  . Рассмотрим следующие случаи:

1. первый звонок оказался  верным, вероятность равна  (сразу набрана нужная цифра).

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

3. первый и второй звонки  оказались неверными, а третий - верным, вероятность равна  (аналогично пункту 2).

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

Ответ: 0,3

 

№5

Абонент забыл последние 2 цифры телефонного номера, но помнит, что они различны и образуют двузначное число, меньшее 30. С учетом этого  он набирает наугад 2 цифры. Найти вероятность  того, что это будут нужные цифры.

Решение:

Используем классическое определение вероятности: где n - число всех возможных элементарных исходов, m - число элементарных исходов, благоприятствующих осуществлению события.

m = 1, так как только  одно число правильное. Подсчитаем  количество всех возможных двузначных  чисел с разными цифрами, меньшее  30, которые может набрать абонент:

10  12  13  14  15  16  17 18  19

20  21  23  24  25  26  27 28  29

Таких чисел n = 18 штук. Тогда  искомая вероятность 

Ответ:

 

 

№6

Теория для  решения задачи:

Для случайных  процессов с дискретным временем изменения состояний возможны только в определенные моменты времени, и эти моменты обозначим через t₀, t₁, t₂, … . В случае дискретной цепи Маркова для описания переходов между состояниями используются вероятности переходов, определяемые как:

p_ij(t_k)=Pr{g(t_k+1)=E_j|g(t_k)=E_i}, i,j=0,n.                         (4)

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

Если  вероятности переходов p_ij(t_k) не зависят от момента времени t_k, т.е. p_ij(t_k)=p_ij, то цепь Маркова называется однородной, в противном случае - неоднородной. Далее будем рассматривать только однородные цепи Маркова.

Вероятности переходов p_ij, i,j=0,n, обычно задаются в виде квадратной матрицы T размерности (n+1)´(n+1):

    

элементы которой удовлетворяются  условиям:

, i=0,n;

, i,j=0,n.

Условие (5) означает, что  в любой момент времени t₀, t₁, t₂, … процесс обязательно (с вероятностью 1) перейдет из состояния E_i в какое-либо другое состояние E₀, E₁,×××, E_n, причем не исключается возможность перехода в то же самое состояние.

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

Наряду с вероятностями  переходов p_ij за один шаг, определим вероятности переходов за m шагов в виде:

, m=1, 2, …

Здесь задет вероятность того, что через m переходов случайный процесс окажется в состоянии E_j при условии, что на текущем шаге он находится в состоянии E_i. В силу однородности марковской цепи вероятности , i,j=0,n, не зависят от текущего времени t_k.

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

, m=2, 3, …

Это равенство означает, что для попадания из состояния E_i в состояние E_j за m шагов необходимо сначала попасть из состояния E_i  в некоторое состояние E_k за m-1 шагов, а затем за один шаг перейти из E_k в E_j. Вероятность этих двух независимых событий (они независимы в силу марковского свойства) равна произведению вероятностей каждого из них, и, если просуммировать эти произведения по всем возможным промежуточным состояниям E_k, то получится вероятность .

Цепь Маркова называется неприводимой, если каждое ее состояние  может быть достигнуто из любого другого  состояния, т.е. для каждой пары состояний E_i  и E_j существует целое число m₀ такое, что . Состояние E_i называется поглощающим, если процесс достигнув это состояние, не покидает его. Очевидно, для поглощающего состояния p_ii=1. Состояние E_i называется невозвратным, если случайный процесс после какого-то числа переходов непременно покидает его.

Вернемся к вопросу определения  вероятностей состояний P_i(t_k), i=0,n, предполагая, что начальные вероятности P_i(t₀), i=0,n, при t₀=0 известны.

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

, i=0,n.

Вероятности состояний после  второго шага на момент времени t₂ определяются аналогично:

, i=0,n.

В общем случае после k-го шага на момент времени t_k, k=1, 2,..., вероятности состояний будут равны

, i=0,n.

В векторной форме равенства (8) имеют вид:

P(t_k)=P(t_k-1)T.

Если случайный процесс обладает эргодическим свойством, т.е. существуют пределы  , i=0,n, то соответствующие предельные значения вероятностей состояний P_i, i=0,n, для стационарного режима определяются из решения системы уравнений:

, i=0,n

или в векторном виде

P=PT

с нормировочным условием

 

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

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

Дано:

Рассмотрим систему, которая  состоит из двух устройств y₁ и y₂, каждое из которых может находиться в одном из двух состояний:

- не работает (обозначим это состояние через 0);

- работает (состояние 1).

В определенные моменты времени  может включиться или выключиться только одно устройство. Рассматриваемый случайный процесс обладает эргодическим свойством. Процесс функционирования такой системы описывается процессом с дискретным временем. Известны вероятности переходов, представленные в виде матрицы и начальные вероятности: P₀(0)=0,7, P₁(0)=P₂(0)=P₃(0)=0,1:

А) Выделить возможные состояния процесса (системы)?

Б) Представить граф переходов для этого процесса?

В) Определить вероятности состояний на различные моменты времени?

Г) Определить вероятности  состояний для стационарного  режима?

Решение:

А)

y1	0	0	1	1
y2	0	1	0	1

Б)

 

 

 

         Рис. 2. Граф переходов.

 

В) Определим вероятности состояний на различные моменты времени. Согласно формуле (8) вероятности состояний на:

момент времени t₁:

P₀ (t₁) =P₀ (0) p₀₀ + P₁ (0) p₁₀ +P₂  (0) p₂₀ + P₃  (0) p₃₀ =0.1;

P₁ (t₁) =P₀ (0) p₀₁ + P₁ (0) p₁₁ +P₂  (0) p₂₁ + P₃  (0) p₃₁ =0.18;

P₂ (t₁) =P₀ (0) p₀₂ + P₁ (0) p₁₂ +P₂  (0) p₂₂ + P₃ (0) p₃₂ =0.62;

P₃ (t₁) =P₀ (0) p₀₃+ P₁ (0) p₁₃ +P₂ (0) p₂₃ + P₃ (0) p₃₃ =0.1.

 

момент времени t₂:

P₀ (t₂) = P₀ (t₁) p₀₀ + P₁ (t₁) p₁₀ + P₂ (t₁) p₂₀ + P₃ (t₁) p₃₀ =0.4;

P₁ (t₂) = P₀ (t₁) p₀₁ + P₁ (t₁) p₁₁ + P₂ (t₁) p₂₁ + P₃ (t₁) p₃₁ =0.06;

P₂ (t₂) = P₀ (t₁) p₀₂ + P₁ (t₁) p₁₂ + P₂ (t₁) p₂₂ + P₃ (t₁) p₃₂ =0.14;

P₃ (t₂) = P₀ (t₁) p₀₃ + P₁ (t₁) p₁₃ + P₂ (t₁) p₂₃ + P₃ (t₁) p₃₃ =0.4.

и т.д.

Г) Определим вероятности состояний для стационарного режима. Искомые вероятности P₀, P₁, P₂, P₃ могут быть найдены, согласно равенствам (10) и (11), из системы уравнений:

P₀ = 0.5P₁ +0.5P₂

P₁ = 0.2P₀ +0.4P₃

P₂ = 0.8P₀ +0.6P₃

P₃ = 0.5P₁ +0.5P₂

P₀ +P₁+P₂ +P₃ =1.

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

Решив систему уравнений, получим: P₀ =0.25; P₁ =0.15; P₂ =0.35; P₃ =0.25.

 

№7

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

1) после осуществления  доставки в А следующая доставка  в 30 случаях осуществляется в  А, в 30 случаях - в В и в 40 случаях - в С;

2) после осуществления  доставки в В следующая доставка  в 40 случаях осуществляется в  А, в 40 случаях - в В и в  20 случаях - в С;

3) после осуществления  доставки в С следующая доставка  в 50 случаях осуществляется в  А, в 30 случаях - в В и в  20 случаях - в С.

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

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

Например, р12 = 0.4 - это вероятность  того, что после доставки в район  В следующая доставка будет производиться в районе А.

Допустим, что каждая доставка с последующим перемещением в  следующий район занимает 15 минут. Тогда, в соответствии со статистическими  данными, через 15 минут:

30% из курьеров, находившихся  в А, будут в А;

30% будут находится в В;

40% будут в С.

Так как в следующий  момент времени каждый из курьеров обязательно будет в одном  из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с  вероятностями, каждый элемент матрицы 0<P_ij<1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождние курьера в момент времени t+1 зависит только от местонахождения в момент времени t.

Теперь зададим простой  вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей из С в В за 2 шага:

1) сначала из С в  С и потом из С в В;

2) из С-->B и B-->B;

3) из С-->A и A-->B.

Учитывая правило умножения  независимых событий, получим, что искомая вероятность равна:

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Подставляя числовые значения:

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

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

Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много  времени.

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

Тогда элемент (2, 3) - это вероятность  перехода из С в В за 2 шага, которая  была получена выше другим способом. Заметим, что элементы в матрице P² также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

 

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ

p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность  перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы  P2).