Элементы иеории. Задача с какой вероятностью лягушка будет в каждой из вершин через a два прыжка б три прыжка в четыре прыжка
 Скачать 126.11 Kb.
|
|
Цепи Маркова. Листок АИ. Буфетов, ЯМ. Наприенко Пусть лягушка сидит на вершине 1 следующего треугольника и готовится к прыжку. Марковской цепью назовём ориентированный граф с вероятностями на ребрах (сумма вероятностей на выходящих из любой вершины ребрах должна равняться единице). Лягушка прыгнет в вершину 3 c вероятностью 2/3, в вершину 2 с вероятностью 0 (так как нет ребра, ас вероятность 1/3 она прыгнет на месте (числа на ребрах указывают на вероятность прыжка вдоль ребра. Когда лягушка оказывается в новой вершине, она снова принимает решение прыгать, но уже смотрит на ребра, выходящие из новой вершины. Задача 1. С какой вероятностью лягушка будет в каждой из вершин через a) два прыжка б) три прыжка в) четыре прыжка? Квадратной матрицей порядка n называется таблица из чисел с n строками и n столбцами. Квадратные матрицы порядка n умножаются следующим образом a 21 a 22 a 2n a n1 a n2 a nn · b 11 b 12 b 1n b 21 b 22 b 2n b n1 b n2 b nn = c 11 c 12 c 1n c 21 c 22 c 2n c n1 c n2 c где c ij = a i1 b 1j + a i2 b 2j + · · · + a in b nj . Например 5 3 8 −6 7 −3 −5 1 · 7 9 3 −3 5 2 7 2 2 = 1 · 7 − 5 · 3 + 3 · 7 1 · 9 + 5 · 5 + 3 · 2 1 · 3 + 5 · 2 + 3 · 2 8 · 7 + 6 · 3 + 7 · 7 8 · 9 − 6 · 5 + 7 · 2 8 · 3 − 6 · 2 + 7 · 2 −3 · 7 + 5 · 3 + 1 · 7 −3 · 9 − 5 · 5 + 1 · 2 −3 · 3 − 5 · 2 + 1 · Рассмотрим матрицу P , на пересечении той строки иго столбца которой стоит вероятность попасть из вершины i в вершину j: P = 1/3 0 2/3 1/2 0 1/2 0 3/4 1/4 1 Задача 2. Найдите матрицы P 2 = P · P , P 3 = P · P · P и P 4 = P · P · P · P . Как связаны вероятности из задачи 1 с элементами этих матриц Почему так получается? Задача 3. Каким условиям должна удовлетворять матрица Q, чтобы по ней можно было построить корректную марковскую цепь? Задача 4. Постройте марковскую цепь по матрице = 1/3 0 0 2/3 2/5 1/5 1/5 1/5 0 0 1/3 2/3 1/8 1/8 Если для какого-то n все элементы матрицы P n положительны, то матрица P (и задаваемая ею цепь) называется регулярной. Это означает, что можно выбрать такое число что ровно через n шагов мы можем попасть в любую вершину. Не стоит путать это свойство с более слабым свойством неприводимости матрицы (цепи, при котором в любую вершину можно попасть за какое-то число шагов. Задача 5. Придумайте неприводимую, ноне регулярную марковскую цепь и напишите её матрицу. Задача 6. Регулярная матрица марковской цепи с двумя состояниями имеет вид = 1 − a a b 1 − для каких-то a и b таких, что 0 < a + b < а) Докажите, чтоб) Что будет происходить с матрицей A n при увеличении n (в пределе)? Задача 7. Зависит ли предельная вероятность от начального положения в задаче Попробуйте объяснить причину |