Пример 5. Задача о наилучшем выборе.

Федеральное агентство по образованию

Сибирский Федеральный университет

Факультет математики и информатики

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

Учебное пособие

Часть I

Красноярск 2014

© Т.В. Крупкина

Марковские цепи

Основные понятия

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

Определение 1. Пусть дана последовательность случайных величин {ξ_n}, определенных на одном вероятностном пространстве и принимающих не более чем счетное множество значений. Последовательность случайных величин {ξ_n} образует цепь Маркова (связана в цепь Маркова), если для любого n и любой последовательности значений

ε_0, ε₁, ε₂, … имеет место равенство

P(ξ_n = ε _j / ξ₀ = ε_i0,…, ξ_n–2 = ε_n–2, ξ_n–1 = ε_n-1) = P(ξ_n = ε _j / ξ_n–1 = ε_n-1) (марковское свойство).

Случайную величину ξ_n можно интерпретировать как состояние цепи Маркова на n-м шаге. Соответственно цепь Маркова можно представить как некоторую систему с возможными состояниями {ε₀, ε₁, ε₂,…}, которая меняет свое состояние в целочисленные моменты времени, новое состояние зависит только от предыдущего (при фиксированном настоящем будущее не зависит от прошлого).

Пример 1. Состояние системы:

0 – не учится в колледже

1 – учится на первом курсе

2 – учится на втором курсе

3 – закончил колледж.

Во многих задачах, связанных с изучением цепей Маркова, множество значений случайных величин (ε _i, i = 0, 1,...), можно отождествить с подмножеством множества натуральных чисел (номерами состояний цепи).

Пусть в результате эксперимента может наступить какое–либо из не более, чем счетного множества исходов (ε₀, ε₁, …). Исход n–го эксперимента обозначим X_n. Если в n испытании осуществится исход ε_j, будем записывать это так: X_n = j.

Тогда определение (1) примет вид:

последовательность целочисленных случайных величин {X_n} образует цепь Маркова, если P(X_n = j / X₀ = i₀,…, X_n–2 = i_n–2, X_n–1 = i) = P(X_n = j / X_n–1 = i) = P .

(Вероятность P -- это вероятность перехода из состояния с номером «i» в состояние с номером «j» на n-м шаге.)

Определение 2. Матрица Р⁽ⁿ⁾ с элементами P называется матрицей вероятностей перехода на n-м шаге.

Итак, для цепи Маркова используются интерпретации:

· система с возможными состояниями

· последовательность зависимых случайных величин

· последовательность зависимых испытаний.

Определение 3. Марковская цепь {X_n} называется однородной, если вероятности P не зависят от n.

(P – вероятность перехода из ε_i в ε_j на n–ом шаге).

В этом случае матрица Р⁽ⁿ⁾ ≡ P и называется матрицей переходных вероятностей.

В матрице переходных вероятностей P любой элемент р_ij ≥ 0, = 1 "i. Такие матрицы называются стохастическими.

Пример 2. Блуждание с поглощением.

Рассмотрим блуждание частицы по целым точкам отрезка [0, а], а > 1. Если 0 < k < a, то из точки (k) с вероятностью p = можно перейти в (k–1) или (k+1). Если k = 0 или k = а, то система остается в этом состоянии с вероятностью 1.

Р =

Пример 3. Блуждание с отражением.

Рассмотрим блуждание частицы по целым точкам отрезка [0, а], а > 1. Если 0 < k < a, то из точки k с p = можно перейти в (k–1) или (k+1). Из точки k=0 система с р=1 переходит в точку а, а из точки k = a с р = 1 в точку 0.

Пример 4. (По условиям примера 1.) Пусть студента в конце года могут исключить с вероятностью r, оставить на второй год с вероятностью s, перевести на следующий курс с вероятностью р; вероятность поступления q, вероятность выпуска р. Тогда матрица переходных вероятностей имеет вид

Р =

Пример 5. Задача о наилучшем выборе.

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

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

Введём состояние ε_i, которое означает, что i–й по счёту предмет лучше всех предыдущих. Состояние ε_m+1 означает, что найден лучший среди всех предмет.

В рассмотренном примере последовательность состояний:

ε₁→ ε₄→ ε₆→ ε₁₀→ ε₁₃

Найдём p_ij. Очевидно, р_ij = 0 при i ≥ j, p_m+1,m+1 = 1.

Надо найти р_ij при i < j ≤ m

 

Рассчитаем вероятности для m=3.

p₁₂ = p₁₃ = p₁₄ = p₂₃ = p₂₄ = p₃₄ =

Вероятности переходов задаются таблицей:

Переходы за k шагов

Рассмотрим изменение состояния системы за k шагов. Введем обозначение

p_ij(k) = p(x_k = j/x₀ = i). При k > 1 по формуле полной вероятности получаем

p_ij(k) = (1)

Рассмотрим матрицу Р(k) = (p_ij(k)). Тогда равенство (1) можно записать как

Р(k) = P(k–1)∙P. Отсюда Р(2) = Р²,...,Р(3) = Р³,…,Р(k) = Р^k.

Пример 6. Рассмотрим последовательность независимых целочисленных величин. Они образуют цепь Маркова. При этом

P²=

Очевидно, и Р^k = Р, то есть матрица переходных вероятностей за k шагов совпадает с матрицей P.

 

Упражнения

 

1. Точки A₁,…,A_n представляют собой вершины правильного n–угольника. Некоторая частица совершает случайное блуждание по точкам A₁,…,A_n. Определить, является ли последовательность положений частицы цепью Маркова, если

а) частица совершает детерминированное движение по часовой стрелке;

б) частица в начальный момент случайно выбирает направление по или против часовой стрелки и далее постоянно движется в выбранном направлении;

в) из любой точки A_i (i не равно 1), частица с вероятностью р сдвигается по часовой стрелке, а с вероятностью q = 1 – p — против часовой стрелки в соседнюю точку. Попадая в точку A₁, частица возвращается в ту точку, из которой она пришла в А₁.

2. Частица совершает случайное блуждание в плоскости по целочисленным неотрицательным точкам (i, j), таким, что i, j не больше n. Из любой внутренней точки указанного квадрата частица с равными вероятностями, независимо от ее предыдущего движения, переходит в одну из соседних (по вертикали или горизонтали) точек. При выходе на границу квадрата частица далее:

а) движется по границе квадрата детерминированно по часовой стрелке;

б) возвращается в ту точку, из которой она вышла на границу;

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

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

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

4. В начальный момент времени в урне n белых и m черных шаров. Через каждую единицу времени из урны по схеме выбора без возвращения извлекается один шар. Пусть n_k — число белых, а m_k — число черных шаров в урне в момент времени k. Какие из указанных ниже последовательностей образуют цепь Маркова, а какие нет:

а) n_k, б) n_k– m_k, в) n_k + m_k, г) пара (n_k, m_k),

д) n_k –m_k +1/(n_k + m_k + 2)?

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

6. В условиях предыдущей задачи найти вероятности перехода за два шага.

7. Всякая ли стохастическая матрица может быть матрицей
вероятностей перехода за два шага некоторой однородной цепи Маркова?

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

9. Определить, при каких значениях с и d однородная цепь Маркова определяется однозначно начальным распределением и матрицей вероятностей перехода за два шага:

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

 

2. Классификация состояний

Определение 4. Состояние ε_i называется несущественным, если существует такое состояние ε_j и целое число t₀ > 0, что p_ij(t₀) > 0, p_ji(t) = 0 " целого t. В противном случае ε_i называется существенным состоянием.

Определение 5. Существенные состояния ε_i и ε_j называются сообщающимися, если существуют такие целые числа t > 0 и s > 0, что p_ij(t) > 0 и p_ji(s) > 0.

Пример 7.

Р =

Состояние ε₁ – несущественное, так как из ε₁ можно попасть в ε₃, а из ε₃ уже только в ε₃, ε₄. Состояние ε₂ – несущественное, так как р₂₄ > 0, p₄₂(t) = 0.

Состояния ε₃ и ε₄ – существенные и сообщающиеся, так как р₃₄ = р₄₃ > 0.

Классы состояний

 

Рассмотрим некоторую однородную цепь Маркова. Выделим класс S⁰ всех несущественных состояний. Пусть теперь ε_i – какое-либо существенное состояние. Обозначим Sⁱ класс состояний, включающий ε_i и все состояния, с ним сообщающиеся. Если ε_jÎ Sⁱ, то ε_j существенно сообщается с ε_i ε_iÎ S^j Sⁱ = S^j, таким образом, всё множество существенных состояний разбивается на непересекающиеся классы сообщающихся состояний S¹, S², …

Если система попала в состояние из класса Sⁱ, то она уже не выйдет из этого класса. Если класс Sⁱ состоит из одного состояния ε_i, то это состояние называется поглощающим. Это определение можно было дать и в другом виде:

Определение 6. Существенные несообщающиеся состояния называются поглощающим и.

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

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

P будет иметь вид:

Упражнения

11. Классифицировать состояния цепи, описанной в примере 2 (блуждание с поглощением).

12. Классифицировать состояния цепи, описанной в примере 3 (блуждание с отражением).

13. Классифицировать состояния цепи, описанной в примере 4 (колледж).

14. Классифицировать состояния цепи, описанной в примере 5 (задача о наилучшем выборе).

15. Пусть X₁, X₂,… – цифровая последовательность, в которой цифры появляются случайно, независимо друг от друга и равновероятно. Имеется счетчик, который показывает, сколько различных цифр встретилось среди первых n цифр последовательности {X_n}. Доказать, что показания счетчика образуют цепь Маркова. Найти матрицу вероятностей перехода за один шаг. Указать существенные и несущественные состояния.

16. Матрица вероятностей перехода за один шаг имеет вид

Указать все пары сообщающихся состояний.

17. Могут ли все состояния цепи Маркова со счетным числом состояний быть несущественными?

18. Могут ли все состояния цепи Маркова с конечным числом состояний быть несущественными?

19. Дана матрица вероятностей перехода за один шаг P. Классифицировать состояния.

P =

 

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

20. P =

21. P =

3. Классификация состояний в неразложимой цепи Маркова

 

Введём обозначения: f_j(n) = p(X_n = j, X_n–1 ≠ j,…, X₁ ≠ j / X₀ = j). (Условная вероятность f_j(n) есть вероятность того, что система, выйдя из j–го состояния, впервые вернётся в него через n шагов).

F_j= . (F_j есть вероятность того, что система, выйдя из j–го состояния, вновь когда–нибудь в него вернётся).

Определение 8. Состояние ε_j называется возвратным, если F_j = 1 и невозвратным, если F_j < 1.

Определение 9. Состояние ε_j называется нулевым, если

и ненулевым, если

Определение 10. Состояние ε_j называется периодическим с периодом d_j, если возвращение в ε_j возможно только за число шагов, кратное d_j > 1 и d_j есть наибольшее число, обладающее этим свойством. Другими словами,

d_j = НОД(n: P_jj(n) > 0).

Замечание. Если n ≠ 0(mod d_j), то Р_jj(n) = 0 и f_j(n) = 0.

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

Р_j,j+1 = ; Р_j,j = ; f_j(1) = p(x₁ = j / x₀ = j) = ; f_j(2) = p(x₂ = j, x₁ ≠ j / x₀ = j) = 0.

Для n > 2 также f_j(n) = 0. Таким образом, F _j = все состояния невозвратны.

все состояния нулевые.

Пример 9. Пусть Р_j,j+1 = ; Р_j,j–1 = (точка движется или влево или вправо на единицу).

P_jj(2k+1) = 0 цепь периодична с периодом d_j = 2.

Возвращения в состояние

 

Рассмотрим производящую функцию числовой последовательности {a_n}, n = 0,1,…

a(z) = z – комплексное, │z│<1.

Если │а_n│≤ с, то а(z) сходится и является аналитической функцией.

Обозначим Р_j = .

Теорема 1. Состояние ε_j возвратно тогда и только тогда, когда Р_j = . Если состояние ε_j невозвратно, то F_j = .

Доказательство. Напомним, что F_j = .

По формуле полной вероятности

P_jj(n) = f_j(1) P_jj(n–1) + f_j(2) P_jj(n–2) +…+ f_j(n) P_jj(0). (*)

Рассмотрим производящие функции последовательностей {p_jj(n)} и {f_j(n)}.

Р_j(z) = и

F_j(z) = .

P_jj и f_j – вероятности, следовательно, они ограничены, значит, оба ряда сходятся. Умножим (*) на zⁿ и просуммируем по n от 0 до ∞, полученную функцию обозначим P_j(z).

P_jj(1) = f_j(1) |∙z

P_jj(2) = f_j(1) P_jj(1) + f_j(2) |∙z² +

P_jj(3) = f_j(1) P_jj(2) + f_j(2) P_jj(1) + f_j(3) |∙z³

………………………………………

P_j(z) = = f_j(1)z(1+z P_jj(1) + z²P_jj(2) +…) + f_j(2) z² (1+P_jj(1)z +…) +…= (f_j(1)z+f_j(2)z²+…+ f_j(n)zⁿ +…)(1+ ) = ∙∙(1+ )=F_j(z) ∙ (1+P_j(z)), т.о.

P_j(z) = F_j(z)(1+P_j(z)).

Отсюда F_j(z) = ; P_j(z) = ;

P_j = ; F_j =

Пусть F_j = 1. Тогда F_j(z)↑1 => P_j(z)→ и P_j = . Пусть P_j = . Тогда P_j(z)↑ и F_j(z)→1 => F_j = 1. Если же F_j < 1, то F_j =

Замечание. P_j = можно рассматривать как среднее число попаданий в состояние ε_j.

= I_n(j). (I_n(j) – индикатор события {X_n = j}).

Следствие. Невозвратное состояние всегда является нулевым. Состояние является невозвратным тогда и только тогда, когда P_j < . Поскольку P_j = < , общий член ряда , т.е. невозвратное состояние является нулевым, ненулевое состояние является возвратным.