панков практикум. Панков Практикум по АСП 21.05 (1). Практикум по дисциплине анализ случайных процессов Версия от 11. 05. 2021 Учебное пособие для обучающихся в бакалавриате по направлении

• Название: Практикум по дисциплине анализ случайных процессов Версия от 11. 05. 2021 Учебное пособие для обучающихся в бакалавриате по направлении
• Анкор: панков практикум
• Дата: 06.04.2022
• Размер: 0.64 Mb.
• Имя файла: Панков Практикум по АСП 21.05 (1).pdf
• Тип: Практикум; #449321
• страница: 2 из 4

Раздел № 2 Дискретные цепи Маркова
2.1
Точки
,
,...,
1 2
A A
A
n
представляют собой вершины правильного N- угольника. Некоторая частица совершает случайное блуждание по точкам
, 1
A
i
N
i
 
. Определить, является ли последовательность положений частицы в моменты времени
0,1,2,...
t 
цепью Маркова для следующих случайных блужданий: a. частица совершает детерминированное движение по часовой стрелке? b. частица в начальный момент времени получает случайный толчок по или против часовой стрелки и далее постоянно движется в направлении толчка? c. из любой точки
,
1
A i
i
 частица с вероятностью
p
сдвигается по часовой стрелке, а с вероятностью
1
q
p
 
- против часовой стрелки в соседнюю точку. Попадая в точку
1
A , частица в следующий момент возвращается в ту точку, из которой она пришла в
1
A .
2.2
Частица совершает случайное блуждание в плоскости по целочисленным точкам
( , )
i j таким, что
0,
i
j
N


. Из любой внутренней точки указанного квадрата частица с равными вероятностями независимо от её предыдущего дви- жения переходит в одну из соседних ( по вертикали или горизонтали) точек.
При выходе на границу квадрата частица далее: a. движется по границе квадрата детерминировано по часовой стрелке; b. возвращается в ту точку, из которой она вышла на границу; c. выбирает случайно направление на границе и движется по границе в выбранном направлении. Для каждого из указанных случаев решить, будет ли последовательность положений, занимаемых частицей, цепью
Маркова.
2.3
В условиях предыдущей задачи частица из каждой внутренней точки с равной вероятностью может переходить в одну из соседних (по вертикали, горизонтали или диагонали). Будет ли последовательность положений частицы

19
цепью Маркова для каждого из трех, указанных в задаче 2, условий движения после выхода на границу?
2.4
Случайные величины
, (
0,1, 2,...)
n
n


независимы и принимают каждая одно издвух значений +1 или -1 с вероятностями, соответственно р и q
(
1)
p
q


. Будет ли цепью Маркова последовательность случайных величин
1
n
n
n

 


2.5
Последовательные состояния некоторой системы образуют цепь Маркова с матрицей переходных вероятностей  . Исследователь может наблюдать состояния системы не всегда, а только при появлении некоторого благоприятного для наблюдения события А. Последовательность появлений и непоявлений события А представляет собой бернулиевскую случайную последовательность с вероятностью успеха
,0 1,
p
p

 . Показать, что последовательность наблюдаемых состояний системы образует цепь Маркова.
Можно ли, зная матрицу переходных вероятностей этой последней цепи, определить матрицу  ?
2.6
В условиях предыдущей задачи моменты наблюдений определяются из условия, что
1 2
,
,...
 
, где
1
k
k






- последовательность не зависимых целочисленных положительных величин.
Будет ли последовательность наблюденных состояний системы цепью Маркова?
2.7
Пусть
1 2
,
,...
 
- цифровая последовательность, вкоторой цифры появляются случайно, независимо друг от друга и равновероятно. Имеется счетчик, который вмомент nпоказывает сколько различных цифр встретилось среди первых n цифр
1 2
,
,...,
n
 

- последовательности. Показать, что показания счетчика образуют цепь Маркова. Написать матрицу переходных вероятностей этой цепи и классифицировать состояния.
2.8
Имеется система, последовательные состояния которой связаны в цепь
Маркова. Вторая система следит за переходами первой системы из одного состояния в другое таким образом, что если первая система переходит из состояния 1 в момент n-1в состояние j вмомент n, то вторая система в момент n находится в состоянии (i,j). Показать, что последовательные состояния второй системы связаны в цепь Маркова; написать для неё матрицу переходных ве- роятностей. Классифицировать состояния второй системы в зависимости от классификации состояний в первой.
2.9
Рассматривается система с дискретными состояниями и дискретным временем, переходы которой из одного состояния в другое протекают под воздействием марковского процесса с дискретным временем. Задана матрица переходных вероятностей  . Требуется: а) построить размеченный граф состояний, б) найти распределение вероятностей после первых 3-х шагов, если известны начальные вероятности состояний
 
0
j
p
, в) найти предельное стационарное распределение.

20 0.9 0
0 0.1 0
0.5 0.1 0.4 0.6 0.2 0.2 0
0.9 0
0 0.1






 






 
2 0
0.7
p

,
 
4 0
0.3
p

Решение. Согласно матрице переходных вероятностей, в системе имеется 4 состояния (обозначим состояния Si как i), а размеченный граф выглядит следующим образом.
В соответствии с теоремой Маркова распределение вероятностей состояний после первых 3-х шагов
 
 
 
 


30 1
2 3
4 3 ;
3 ;
3 ;
3
p
p
p
p
p

равно
3 3
0
p
p


, где
 
 
 
 




0 1
2 3
4 0 ;
0 ;
0 ;
0 0;0,7;0;0,3
p
p
p
p
p


Легко находим, что
3 0.9 0
0 0.1 0.756 8
0.63 0
6 0.14 2
9 0.041 1
0.174 0.0 2
.0 6 0. 36 0.9 0
0 0.1






 






Тогда
 
 
 
 




1 2
3 4
0.636 0
0.149 0.04 3
1
,
0
;
;
1
,
7 0
4
.9 0
0 0.1 3 ;
3 ;
;
3 0;0 7 0 0 3 0.756 0.082 0.026 0.136 0.9 0
0.1
p
p
p
p
















8
;
;
0.7152 0.1043 0.0287 0
; .151

Для нахождения предельного стационарного распределения


1 2
3 4
; ; ;
s
s s s s

для цепи Маркова с N=4 состояниями используем систему
1 1
N
k
k
s
s
s





  


, которая эквивалентна системе

21

  
1
E
0 1
T
T
N
k
k
s
s


 







, решением которой является вектор

 

1 2
3 4
; ; ;
0.9;0;0;0.1
s
s s s s


2.10 Классифицировать, построив графы переходов, состояния в цепях
Маркова со следующими матрицами переходных вероятностей:
0 1
1 0 1
0 1 / 2 1 / 2 1 / 2 1 / 2
;
; .
;
; .
1 0
1 0 0
1 0
1 1
0
a
b
c
d
e






























2.11 Вероятности перехода за один ход в цепи Маркова задаются матрицей:
1 / 3 1 / 3 1 / 3 0
1 / 2 1 / 2 0
0 1 / 4 1 / 4 0
1 / 2 0
1 / 2 0
1 / 2












Классифицировать состояние этой цепи, построив граф переходов, и найти стационарное распределение.
2.12 Матрица перехода цепи Маркова имеет следующий вид:
0 1 / 2 0
0 1 / 2 0
0 1
0 0
1 / 5 1 / 5 1 / 5 1 / 5 1 / 5 0
1 / 2 0
0 1 / 2 0
1 / 2 1 / 2 0
0
















Классифицировать состояние этой цепи, построив граф переходов, и найти стационарное распределение.
2.13 Исследователь наблюдает за системой, изменяющей свои состояния по закону цепи Маркова с матрицей переходных вероятностей, указанной в задаче
10. При этом исследователь не может различать состояния 2 и 4 и они воспринимаются им как одно состояние, обозначаемое символом *. Можно ли считать, что последовательность состояний 1, 3, 5, *, наблюдаемая исследователем, является цепью Маркова?
2.14 Матрица вероятностей перехода однородной цепи
Маркова, описывающая систему
S
, имеет вид:
1 / 2 1 / 2 0
0 3 / 4 1 / 4 1 / 4 1 / 4 1 / 2




 






Нарисовать граф состояний системы
S
. Начальное распределение вероятностей по состояниям в момент
0
t 
определяется вектором
(0.5, 0.1, 0.4) . Найти вероятности состояний за два шага, и предельные вероятности состояний цепи
Маркова.

22 2.15 Рассматривается система с дискретными состояниями и дискретным временем. Задана матрица переходных вероятностей
1 / 2 1 / 2 0
0 3 / 4 1 / 4 1 / 4 1 / 4 1 / 2




 






Требуется: a. построить размеченный граф состояний, b. найти распределение вероятностей после первых 3-х шагов, если известны начальные вероятности состояний
 
0
j
p
:
 
2 0
0.8
p

,
 
3 0
0.2
p

c. найти предельное стационарное распределение.
2.16 Матрица вероятностей перехода однородной цепи
Маркова, описывающая систему
S
, представляющую собой ЭВМ с возможными состояниями:
0
s
– полностью исправна;
1
s
– значительные неисправности, позволяющие решать ограниченное число задач;
2
s
– полностью неисправна., имеет вид:
0,6 0,3 0,1 0,6 0,2 0,2 0
0.9 0.1




 






Нарисовать граф состояний системы
S
. Начальное распределение вероятностей по состояниям в момент
0
t 
определяется вектором
(0.8; 0.2; 0) . Найти вероятности состояний ЭВМ после трех шагов и предельное стационарное распределение.
2.17 Три танка ведут бой, каждый с двумя другими. Танк A уничтожает танк, по которому он ведёт огонь, с вероятностью 2/3, танк B – с вероятностью 1/2, танк C – с вероятностью 1/3. Танки открывают огонь одновременно, и каждый стреляет по сильнейшему из не уничтоженных к этому моменту противников.
Написать матрицу вероятностей перехода за один шаг марковской цепи, состояниями которой будут множества танков, которые еще действуют в данный момент.
2.18 Рассматривается система с дискретными состояниями и дискретным временем. Задана матрица переходных вероятностей
0.8 0.2 0
0 0.2 0.5 0.1 0.2 0.2 0.1 0.5 0.2 0
0.5 0
0.5






 






Требуется: a. построить размеченный граф состояний, \ b. найти распределение вероятностей после первых 3-х шагов, если известны начальные вероятности состояний
 
0
j
p
:
 
2 0
0.4
p

,
 
3 0
0.6
p

c. найти предельное стационарное распределение.

23 2.19 . Три танка ведут бой, танк А стреляет в танк В, танк В – в танк С, танк С
– в танк А. Танк А уничтожает танк В с вероятностью 2/3, танк В уничтожает танк С с вероятностью 1/2, танк С уничтожает танк А с вероятностью 1/3.
Танки открывают огонь одновременно. Написать матрицу вероятностей перехода за один шаг марковской цепи, состояниями которой будут множества танков, которые еще действуют в данный момент.
2.20 Рассматривается система с дискретными состояниями и дискретным временем. Задана матрица переходных вероятностей
1 / 2 1 / 4 1 / 4 1 / 4 1 / 2 1 / 4 0
1 / 4 3 / 4




 






Требуется: a. построить размеченный граф состояний, b. найти распределение вероятностей после первых 3-х шагов, если известны начальные вероятности состояний
 
0
j
p
:
 
1 0
0.5
p

,
 
3 0
0.5
p

c. найти предельное стационарное распределение.
2.21 Эскадрилья бомбардировщиков состоит из четырех самолетов. Боевое задание она получает один раз в день. Если к концу дня из-за потерь, нанесенных противником, наличный состав самолетов уменьшается до нуля, одного или двух, то командир эскадрильи получает один самолет из резерва; этот самолет доставляется ночью. Если наличный состав равен трем или четырем самолетам, то командир не имеет права на пополнение. На следующий день, если в наличии имеется три или четыре самолета, то задание эскадрилье дается; в противном случае задание отменяется. Во время выполнения задания каждый самолет может быть выведен из строя с вероятностью р. Ввести понятие состояния эскадрильи так, чтобы функционирование эскадрильи можно было описать с помощью цепи Маркова, построить матрицу Р и исследовать ее на регулярность.
2.22 Рассматривается система с дискретными состояниями и дискретным временем. Задана матрица переходных вероятностей
0.6 0.1 0.2 0.1 0.8 0.1 0
0.1 0.7 0.2 0.1 0
0.4 0.1 0.4 0.1






 






Требуется: a. построить размеченный граф состояний, b. найти распределение вероятностей после первых 3-х шагов, если известны начальные вероятности состояний
 
0
j
p
:
 
1 0
0.7
p

,
 
3 0
0.3
p

c. найти предельное стационарное распределение.
2.23 Точки
,
,...,
1 2
A A
A
N
представляют собой вершины правильного N- угольника. Частица совершает случайное блуждание по этим точкам таким образом, что в каждый момент времени она с вероятностью p сдвигается на

24
один шаг по часовой стрелке или с вероятностью q=1-p - на один шаг против часовой стрелки. Показать, что последовательность положений частицы представляет собой цепь Маркова (циклическое блуждание). Написать для неё матрицу переходных вероятностей и классифицировать состояния; определить стационарное распределение и пределы переходных вероятностей.
2.24 Частица случайно блуждает на прямой по целочисленным точкам
0,1, 2,..., N
. Из любой внутренней точки частица сдвигается с вероятностью p на один шар вправо или с вероятностью q=1-p на один шаг влево. Попадая в точки
0и N, частица остается в них навсегда (поглощающие экраны). Написать матрицу переходных вероятностей и классифицировать состояния. Найти стационарное распределение.
2.25 В условиях задачи 2.15 для каждого несущественного состояния определить вероятность того, что частица, начав движение из этого состояния, поглотится в нуле.
2.26 В условиях задачи 2.15 вычислить математическое ожидание времени до поглощения частицы на одном из экранов, если частица начинает свое движение из точки
, 1 1
i
i
N
 
 .
2.27 Частица случайно блуждает на прямой по целочисленным точкам
0,1, 2,..., N
. Из любой внутренней точки частица сдвигается с вероятностью p на один шаг вправо или с вероятностью q=1-p, на один шаг влево. Попадая в точки
0 и N частица в следующий момент времени с вероятностью 1 переходит, соответственно, в точки 1 или N-1 (отражающие экраны). Написать матрицу переходных вероятностей и классифицировать состояния.
2.28 В условиях задачи 2.18 найти стационарное распределение и вычислить пределы переходных вероятностей за n шагов при n   .
2.29 В двух урнах находится Nшаров. Состояние системы определяется числом шаров в первой урне. Для перехода к следующему состоянию случайно выбирается один из шаров и перекладывается из той урны, в которой он находится, в другую. Последовательность состояний такой степени связана в цепь Маркова (модель Эренфеста). Написать матрицу переходных вероятностей для этой цепи и классифицировать состояния. Найти стационарное распределение.
2.30 N чёрных и N белых шаров размещены в двух урнах так, что в каждой урне находится по N шаров. Число чёрных шаров в первой урне определяет состояние системы. Для перехода к следующему состоянию наудачу выбирается по одному шару в каждой из урн и эти шары меняются местами.
Последовательность состояний системы связана в цепь Маркова. Написать матрицу переходных вероятностей для этой цепи и классифицировать состояния. Показать, что стационарное распределение - гипергеометрическое.
2.31 Цепь Маркова с двум состояниями имеет матрицу переходных вероятностей
1 1
a
a
b
b



  




,
0
,
1
a b

 . Найти матрицу переходных вероятностей за n шагов

25 2.32 Цепь Маркова с тремя состояниями имеет матрицу переходных вероятностей
1 / 2 0
1 / 2 0
1 / 2 1 / 2 1 / 4 1 / 4 1 / 2










Вычислить матрицу переходных вероятностей за n шагов.
2.33 Найти вероятности перехода за n шагов для цепи Маркова, описанной в задаче 2.14.
2.34 Классифицировать состояния и найти стационарное распределение для цепи Маркова с 10 состояниями и с матрицей переходных вероятностей, в которой
1,3 1,7 2,9 8,8 9,3 9,6 10,6 10.7 1
2
p
p
p
p
p
p
p
p








,
4,2 4,7 5,9 1
10
p
p
p



,
2,10 4,6 5,1 5,3 5,4 8,4 1
5
p
p
p
p
p
p






,
3,2 6,2 7,2 1
p
p
p


 ,
2,1 5,5 8,5 3
10
p
p
p



,
4,8 3
5
p

, а все остальные переходные вероятности равны нулю.
2.35 В условиях задачи 2.25 найти математические ожидания времени до поглощения в эргодическом классе, если система начинает свое движение из несущественных состояний.
2.36 В условиях задачи найти функцию распределения времени до поглощения в эргодическом классе, если система начинает свое движение из несущественных состояний.
2.37 В условиях задачи 2.25 найти вероятности того, что система, отправляясь из несущественных состояний, перейдет в эргодический класс таким образом, что будет находиться в циклическом классе, которому принадлежит состояние
«2» в моменты времени сравнимые с r по модулю d, где d - период эргодического класса и
0,1,...,
1
r
d


2.38 Переходные вероятности цепи Маркова с 15 состояниями имеют следующие значения:
1,10 1,15 2,5 2,11 3,6 3,13 4,3 4,9 5,8 5,11
p
p
p
p
p
p
p
p
p
p










6,1 6,12 7,3 7,14 8, 2 8,11 9, 2 9, 4 10,6 10,13
p
p
p
p
p
p
p
p
p
p











1 12,10 12,14 13, 7 13,12 15,6 15,13 2
p
p
p
p
p
p







,
1 11, 2 14,6
p
p

 , остальные переходные вероятности равны нулю. Классифицировать состояния; найти стационарные распределения для каждого эргодического класса.
2.39 В условиях задачи 2.29 пусть
1
E
-эргодический класс, содержащий состояние «1» и
1

- матрица переходных вероятностей между состояниями из
1
E
. Вычислить предельные матрицы


1 1
lim
kd
r
n



, где
1
d – период класса
1
E
, и
0
r
d
 
.

26 2.40 В условиях задачи 2.29 пусть
2
E
- эргодический класс, которому принадлежит состояние «2» и
2

- матрица переходных вероятностей между состояниями из
2
E
. Найти матрицу переходных вероятностей за n шагов для класса
2
E
2.41 В условиях задачи 2.29 найти вероятности поглощения в классах
1
E
и
2
E
для всех случаев, когда система начинает движение из несущественных состояний.
2.42 В условиях задачи 2.29 найти вероятности того, что система, выйдя из какого-либо несущественного состояния, перейдет в эргодический класс
1
E
и притом в моменты времени
1
, 0
kd
r
r
d

 
будет находиться в циклическом подклассе, содержащем состояние «1».
2.43 В условиях задачи 2.29 вычислить пределы вероятностей перехода из несущественных состояний в состояние «1» по последовательностям моментов времени вида
1
, 0
,
kd
r
r
d k

 
 
2.44 Всякая ли стохастическая матрица может быть матрицей перехода за 2 шага некоторой цепи Маркова?
2.45 40.
Пусть
0 1
, ,...
 
- последовательность случайных величин, образующих однородную цепь Маркова. Доказать, что для того, чтобы случайные величины
0 1
, ,...
 
были независимыми, необходимо и достаточно, чтобы все строки матрицы вероятностей перехода за один шаг были одинаковыми.
2.46 В начальный момент времени в урне n
0
белых и m
0
чёрных шаров. Через каждую единицу времени из урны по схеме выбора без возвращения извлекается один шар. Пусть n k
- число белых, m k
- число чёрных шаров в урне в момент времени k . Какие из указанных ниже последовательностей образуют цепь Маркова, а какие нет:


1
; .
; .
;
;
; .
2
k
k
k
k
k
k
k
k
k
k
k
n
m
a n
b n
m
c n
m
d n m
e
n
m






2.47 Могут ли все состояния цепи Маркова с конечным числом состояний быть несущественными?
2.48 Могут ли все состояния цепи Маркова со счетным числом состояний быть несущественными?
2.49 44.
Имеется схема Бернулли с вероятностью успеха p, и вероятностью неудачи q=1-p.
Рассматривается последовательность всевозможных комбинаций из успехов и неудач, образующих состояния некоторой системы.
Будем считать, что система в момент n находится в состоянии E
k
, k=1,2,…, если в каждом из испытаний с номерами n, n-1, n-2,…, n-k+1 был успех, а в испытании с номером n-k была неудача. Система в момент n находится в состоянии E
0
, если в испытании с номером n была неудача. Показать, что последовательность состояний системы образует цепь Маркова. Найти матрицы переходных вероятностей за один шаг и за n шагов.

27 2.50 В некоторой области пространства находятся однородные частицы.
Состояние изучаемой системы - это число частиц в области в данный момент времени. В течение единицы времени каждая из имевшихся в области частиц может покинуть её с вероятностью q. Кроме того, в области могут появиться новые частицы. Вероятность того, что появится rчастиц (r=0,1,2,3,…) равна
!
r
e
r



. Показать, что последовательность состояний системы образует цепь
Маркова. Составить матрицу переходных вероятностей за один шаг. Показать, что эта цепь эргодическая. Найти стационарное распределение.
2.51 Пусть последовательность


0
,
t
t

 
случайных величин связана в цепь
Маркова.
Положим события


0 0
1 1
PAST
,...,
t
t
i
i







-
«прошлое»,


PRESENT
t
t
i



- «настоящее»,


1 1
FUTURE
t
t
i





- «будущее».
Показать, что






PAST FUTURE | PRESENT =
PAST | PRESENT
FUTURE | PRESENT
P
P
P


, т.е. прошлое и будущее независимы при фиксированном настоящем).
2.52 Пусть случайные величины
0 1
, ,...
 
независимы и каждая принимает значения 1

с вероятностями 1/2. a.
Образует ли образует ли последовательность случайных величин
1
,
0,1, 2,...
2
n
n
n
n







цепь Маркова? b.
Образует ли образует ли последовательность случайных величин
1
,
n
n
n

 


0,1, 2,...
n 
, цепь Маркова?
2.53 Пусть


0
,
n
n

 
есть цепь Маркова с множеством состояний


1, 2,3
E 
и матрицей переходных вероятностей
0 1
0 1
1 / 3 1 / 3 1 / 3









 







. Определим последовательность
,
0,1, 2,...
n
n


, полагая
1,
3 2,
3
n
n
n





 


. Показать, что последовательность


,
0,1, 2,...
n
n


образует цепь Маркова.
2.54 В N ячейках последовательно независимо друг от друга равновероятно размещаются частицы. Пусть
 
0
n

- число ячеек, оставшихся пустыми после размещения n частиц. Показать, что последовательность
 


0
,
1, 2,...
n n


образует цепь Маркова. Найти переходные вероятности этой цепи.
2.55 В городе N каждый житель имеет одну из 3 профессий: A, B, C. Дети отцов, имеющих профессии A, B, C, сохраняют профессии отцов с вероятностями
3 / 5, 2 / 3, 1 / 4 , соответственно, а если не сохраняют, то с равными вероятностями выбирают любую из двух других профессий. Найти: a.
Распределение по профессиям в следующем поколении, если в данном поколении профессию A имело 20% жителей, B – 30%, C – 50%.

28
b.
Предельное распределение по профессиям, когда число поколений неограниченно растёт.

29