Дискретные марковские цепиЗадачи. 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 целое число. Доказать, что случайные величины , , образуют цепь Маркова. При каком условии она будет однородной?
|