Дискретные марковские цепи

Задачи.

1. Пусть последовательность случайных величин , , образует цепь Маркова. Доказать, что для :

а) ;

б) ;

в)

2. Пусть последовательность случайных величин , , образует цепь Маркова. Положим П т.е. «прошлое» т.е. «настоящее»/ и т.е. «будущее»/. Доказать, что Р(ПБ/Н)=Р(П/Н)*Р(Б/Н).

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

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

5. Если , , цепь Маркова, то последовательность , , где натуральное, тоже образует цепь Маркова. Доказать.

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

7. Если , , цепь Маркова, то последовательность , , где натуральное, тоже образует цепь Маркова. Доказать.

8. Пусть - номер состояния в цепи Маркова в момент времени , матрица вероятностей перехода равна и начальное распределение . Положим Доказать, что последовательность , является цепью Маркова, и найти для этой цепи матрицу Р.

9. Пусть последовательность случайных величин , , является цепью Маркова с матрицей и множеством состояний {1, 2, 3}. Положим При каком условии последовательность случайных величин , также является однородной цепью Маркова?

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

11. Пусть , , последовательность независимых одинаково распределенных случайных величин, принимающих значения 1 и -1 с вероятностями p и q=1-р соответственно. Положим а) , ; б) , ; в) , . Будет ли последовательность , , цепью Маркова?

12. Пусть , , последовательность независимых одинаково распределенных случайных величин, принимающих значения 1 и -1 с вероятностями p и q=1-р соответственно. Доказать, что последовательность , , где φ (-1, -1)=1, φ (-1, 1)=2, φ (1, -1)=3, φ (1, 1)=4, является цепью Маркова и построить матрицу Р для нее.

13. Пусть , последовательность случайных величин, принимающих значение в множестве Х. Если для любого и любых выполняется соотношение

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

14. На стоянку такси через единичные моменты времени прибывают машины (по одной в каждый момент). Если на стоянке нет ожидающих, то машина сразу уезжает. Обозначим через число пассажиров, приходящих в момент k на стоянку, и будем считать, что - независимые случайные величины. Пусть длина очереди в момент времени k, =0. Будет ли последовательность случайных величин , марковской цепью?

15. В начальный момент в урне белых и черных шаров. Через каждую единицу времени из урны (без возвращения) извлекается один шар. Пусть – число белых, а – число чёрных шаров в урне в момент времени k. Какие из указанных ниже последовательностей образуют цепь Маркова:

а) , ;

б) , ?

16. К рабочему, стоящему на контроле, через минуту поступают изделия, причём каждое из них независимо от других может оказаться дефектным с вероятностью p, 0< p< 1. Поступившие изделия рабочий одно за другим проверяет, затрачивая на проверку каждого по одной минуте. Если изделие оказывается дефектным, то он прекращает проверку других изделий и исправляет дефектное, на что уходит ещё 5 минут. Пусть – число изделий, скопившихся у рабочего через n минут после начала работы. Будет ли последовательность случайных величин , , цепью Маркова?

17. Три танка ведут бой, каждый с двумя другими. Танк A уничтожает танк, по которому он ведёт огонь, с вероятностью 2/3, танк B – с вероятностью 1/2, танк C – с вероятностью 1/3. Танки открывают огонь одновременно, и каждый стреляет по сильнейшему из не уничтоженных к этому моменту противников. Написать матрицу вероятностей перехода за один шаг марковской цепи, состояниями которой будут множества танков, которые еще действуют в данный момент.

18. Три танка ведут бой, танк А стреляет в танк В, танк В – в танк С, танк С – в танк А. Танк А уничтожает танк В с вероятностью 2/3, танк В уничтожает танк С с вероятностью 1/2, танк С уничтожает танк А с вероятностью 1/3. Танки открывают огонь одновременно. Написать матрицу вероятностей перехода за один шаг марковской цепи, состояниями которой будут множества танков, которые еще действуют в данный момент.

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

20. Пусть , , последовательность независимых одинаково распределенных случайных величин, принимающих значения 1 и 0 с вероятностями p и q=1-p соответственно. Доказать, что последовательность пар , , образует цепь Маркова и найти матрицу Р вероятностей перехода за один шаг.

21. Эскадрилья бомбардировщиков состоит из четырех самолетов. Боевое задание она получает один раз в день. Если к концу дня из-за потерь, нанесенных противником, наличный состав самолетов уменьшается до нуля, одного или двух, то командир эскадрильи получает один самолет из резерва; этот самолет доставляется ночью. Если наличный состав равен трем или четырем самолетам, то командир не имеет права на пополнение. На следующий день, если в наличии имеется три или четыре самолета, то задание эскадрилье дается; в противном случае задание отменяется. Во время выполнения задания каждый самолет может быть выведен из строя с вероятностью р.

Ввести понятие состояния эскадрильи так, чтобы функционирование эскадрильи можно было описать с помощью цепи Маркова, построить матрицу Р и исследовать ее на регулярность.

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

1) 2) .

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

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

24. Для конечной цепи Маркова, состоящей из одного класса несущественных состояний и одного класса существенных состояний, доказать, что:

а) из несущественного состояния можно перейти в любое существенное с положительной вероятностью;

б) из существенного состояния нельзя перейти в несущественное с положительной вероятностью.

25. Доказать, что несущественное состояние не может быть возвратным.

26. Два состояния i и j марковской цепи отнесем к одному классу K, если существуют такие целые , , что . Введем на множестве классов состояний отношение «<»: будем говорить, что , если существуют состояния и целое такие, что . Доказать, что:

а) различные классы не пересекаются;

б) если , то не может быть ;

в) если и , то .

27. Состояния цепи Маркова - неотрицательные целые числа. Из состояния j, , за один шаг цепь переходит в состояние j+1 с вероятностью и в состояние ноль с вероятностью 1- . Доказать, что для того чтобы состояния цепи были возвратными, необходимо и достаточно, чтобы ряд расходился и > 0, .

28. Доказать, что если j невозвратное состояние, то для любого состояния i марковской цепи .

29. Доказать, что если состояние j несущественное, то для любого состояния i при .

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

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

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

33. Пусть все состояния двух цепей Маркова с матрицами вероятностей перехода за один шаг и возвратны. Будут ли возвратны состояния цепи Маркова с матрицей вероятностей перехода за один шаг ?

34. Доказать, что в конечной цепи Маркова состояние возвратно тогда и только тогда, когда оно существенно.

35. Доказать, что цепь Маркова не является эргодической, если:

а) в ней имеется по крайней мере одно несущественное состояние;

б) в ней имеется по крайней мере два не сообщающихся состояния.

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

37. Доказать, что для любого состояния цепи Маркова вероятность возвращения в него бесконечное число раз равна 0 или 1, причем в первом случае состояние невозвратно, а во втором возвратно.

38. По виду матрицы переходных вероятностей за один шаг:

1) восстановить недостающие вероятности;

2) построить граф переходов;

3) выделить классы несущественных и существенных состояний;

4) найти возвратные, периодические, нулевые состояния;

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

6) выяснить, является ли марковская цепь эргодической, и найти предельные вероятности;

7) Задав начальное распределение, найти вероятность за три шага попасть в третье состояние:

а) ; б) ; в) ;

г) ; д) ; е) ; ж) ;

з) ; и) ;

к) ; л) ;

м) ; н) ; о) ;

п) .

39. Дать классификацию состояний марковской цепи, для неприводимых классов найти предельные вероятности, если переходные матрицы за один шаг имеют вид:

а) ;

б) ;

в) ;

г) ;

д) .

40. Пусть каждый человек, услышавший новость, может передать ее другому; при этом вероятность искажения смысла на противоположный постоянна и равна р =0, 000001. Какова вероятность услышать новость в неискаженном виде после того, как она «побывала» у большого числа людей?

41. У профессора три излюбленных вопроса, один из которых он задает на каждом экзамене. Он никогда не задает какой-либо из этих вопросов два раза подряд. Если в прошлый раз был задан вопрос А, то он бросает монету и задает вопрос В, если выпал герб. Если был задан вопрос В, то он бросает две монеты и задает вопрос С, если выпадет два герба. Если был задан вопрос С, то он бросает три монеты и задает вопрос А, если выпадет три герба. Какой вопрос он задает чаще всего?

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

43. Пусть имеется три карты с номерами 1, 2, 3. Состоянием системы назовем последовательность номеров этих карт . Предположим, что с вероятностями ½ состояние переходит в состояния и . Показать, что эта система будет марковской цепью. Построить матрицу переходных вероятностей за один шаг и найти финальное распределение.

44. Вернувшись после долгого отсутствия в родной город, вы решили позвонить по телефону всем вашим старым друзьям и сообщить о своем приезде. Под руками у вас оказались две устаревшие телефонные книги, причем вас предупредили, что в одной из них неверно уже около трети всех номеров, а в другой – около четверти, но, в какой именно, неизвестно. Можно избрать две такие тактики поведения:

1) книга выбирается наугад и, если указанный в ней номер нужного вам телефона оказался правильным, вы продолжаете ею пользоваться, если нет – берете другую книгу;

2) метод двух проб: в случаях «правильный – правильный», «правильный – неправильный» и «неправильный – правильный» книга не меняется, в случае «неправильный – неправильный» надо перейти к другой книге.

При какой тактике поведения вероятность правильных телефонных показателей выше?

45. N черных и N белых шаров размещены в двух урнах по N шаров в каждой. Число черных шаров в первой урне определяет состояние системы. На каждом шаге случайно выбирается по одному шару из каждой урны, и эти выбранные шары меняются местами. Построить матрицу Р и найти стационарное распределение.

46. Шахматист А каждую партию независимо от исходов предыдущих партий выигрывает с вероятностью р, проигрывает с вероятностью q и ничья с вероятностью r=1-p-q. Шахматист В менее уравновешен: выигрывает с вероятностями p+ε, p, p-ε соответственно, если предыдущая партия им выиграна, сыграна в ничью, проиграна. Аналогично вероятность проигрыша: она равна в этих трех случаях соответственно q-ε, q, q+ε. Кто наберет в длительном турнире больше очков?

47. Игральная кость последовательно перекладывается с одной грани равновероятно на любую из четырех соседних независимо от предыдущего. К какому пределу при стремиться вероятность того, что при n-м перекладывании кость окажется на грани 6, если сначала она находилась в этом же положении? (Сумма цифр на противоположных гранях равна 7).

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

49. На окружности расположены шесть точек, равноудаленных друг от друга. Частица из данной точки перемещается в одну из ближайших соседних с вероятностью ¼ или в диаметрально противоположную с вероятностью ½. Построить граф, написать матрицу вероятностей переходов за один шаг. Будет ли эта марковская цепь регулярной?

50. Пусть первая строка стохастической матрицы Р; > 0, . В следующих строках , остальные элементы матрицы равны нулю. Классифицировать состояния марковской цепи и найти предельное распределение.

51. Доказать, что все состояния конечной цепи Маркова не могут быть несущественными.

52. Пусть , последовательность независимых целочисленных случайных величин и d> 0 целое число. Доказать, что случайные величины , , образуют цепь Маркова. При каком условии она будет однородной?