5.2. Марковские цепи с поглощением

Рассмотрим следующую модель пьяницы: пьяница ходит только по прямой линии и с вероятностью 1/3 идет влево, либо 2/3 вправо. Всего он может сделать 4 шага, с обеих сторон от пьяного стоят полицейские. Как только он доходит до одного из них, так его забирают в участок. Обозначим состояние пьяного 0, 1, 2, 3, 4. Состояние 0 и 4 называются поглощающими, так как, попав в них, пьяница уже не возвращается. Матрица переходов имеет вид:

	0	1	2	3	4
0	1	0	0	0	0
1	1/3	0	2/3	0	0
2	0	1/3	0	2/3	0
3	0	0	1/3	0	2/3
4	0	0	0	0	1

Такие марковские цепи называются цепями с поглощением.

Для них интересуются ответами на следующие вопросы:

а) какова вероятность того, что процесс завершится переходом в конкретное поглощающее состояние;

б) сколько в среднем шагов потребуется, чтобы попасть в поглощающее состояние;

в) сколько в среднем раз проходит процесс через каждое непоглощающее состояние?

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

		поглощение	Непоглощение
P=	Поглощающее	I	0
	Непоглощающее	R	Q

где I - единичная матрица, 0 - нулевая, Q и R - неотрицательные матрицы. В теории марковских цепей показано, что процесс обязательно попадет в поглощающее состояние, т.е. Qⁿ_n_®¥®0 и бесконечный ряд N = I + Q + Q²_+....сходится к пределу, равному обратной матрице (I - Q)^-1, т.е. N=(I-Q)^-1.

Матрица N называется фундаментальной матрицей. Тогда обозначим 1 - вектор столбец из 1, t - вектор сумм по строкам N матрицы равный N*1. n_ij дает среднее время пребывания в состоянии S_j при начальном состоянии S_i (где S_i и S_j - непоглощающие, t_i - среднее число шагов до поглощения, при начальном S_j, т.е. i - й элемент вектора t. b_ik - вероятность того, что при начальном S_i процесс будет поглощен в состояние S_k , равна ik – ому элементу матрицы B = NR). Для нашего примера канонический вид

		0	4	1	2	3
	0	1	0	0	0	0
	4	0	1	0	0	0
P=	1	1/3	0	0	2/3	0
	2	0	0	1/3	0	2/3
	3	0	2/3	0	1/3	0

Тогда

					-1			1	2	3
		1	-2/3	0			1	7/5	6/5	4/5
N =	(I – Q)^-1 =	-1/3	1	-2/3		=	2	3/5	4/5	6/5
		0	-1/3				3	1/5	3/5	7/5

		7/5	6/5	4/5		1		17/5
t=	N * 1 =	3/5	4/5	6/5	*	1	=	18/5
		1/5	3/5	7/5		1		11/5

										0	4
		7/5	6/5	4/5		1/3	0		1	7/15	8/15
B =	N * R =	3/5	9/5	6/5	*	0	0	=	2	1/15	9/15
		1/5	3/5	7/5		0	2/3		3	1/15	14/15

Таким образом, среднее время пребывания в состоянии 2 при начальном состоянии 1 равно 7/5 согласно матрице N.

Среднее число шагов до поглощения из состояния 1 равно 3 и вероятность поглощения из состояния 3 правым полицейским равна 14/15.

Задачи на самостоятельную работу

1. Пусть в стране ОЗ если начался дождь, то он длится всегда, определите T, t и B.

2. Пусть вероятность перехода влево равна 1/3, а вправо 2/3 для пьяницы. Определите T, t и B.

3. Число Х случайно выбирается из чисел 1 ,2, 3, 4 и 5. После того как оно выбрано, следующее число выбирается случайным образом среди тех чисел, которые больше Х. Процесс завершается, когда выбранным числом оказывается 1. Состояние марковского процесса задаются числами, которые могут быть выбраны.

Покажите, что

	1	0	0	0
T=	1	1/2	0	0	+I
	1	1/2	1/3	0
	1	1/2	1/3	¼

где: I - единичная матрица 4-го порядка.

Каково среднее число выборов? (Ответ 25/12)

Три танка ведут бой, каждый с двумя другими. Танк А уничтожает танк, по которому ведет огонь с вероятностью 1/3, танк B - с вероятностью 1/3, танк C- с вероятностью 1/6. Открывают огонь одновременно и каждый стреляет сильнейшему из не уничтоженных к этому моменту танку. Найдите T, t и B.