Файл: Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие.pdf

42
Рис. 13. Графическое представление матрицы переходов
В теории марковских цепей показано, что вероятность того, что система через
n
шагов перейдет в состояние
a
j
из состояния
a
i
определяется матрицей перехода
0
n
P
 
 
 
n
n
j
n
j
j
P
a
P f
a
P







(30)
В случае, если

-вектор–строка, компоненты которого задают ве- роятности пребывания в соответствующих состояниях в данный момент, то

P
задает эти вероятности на следующем шаге, а
n
P

– через
n
шагов. Тогда ответ на поставленный выше вопрос дается матрицей/
3 0
26 64 13 64 25 64 13 32 6 32 13 32 25 64 13 64 26 64
дождь
ясно
снег
дождь
ясно
снег
P

Из нее видно, что вероятность хорошей погоды через 3 дня после дождя равна 13/64. Для получения степеней матрицы Р можно ис- пользовать Mathcad.
Задачи на самостоятельную работу
1. Эскадрилья истребителей имеет 4 самолета и получает боевое задание один раз в день утром. Если к концу дня число самолетов из-за потерь уменьшается до 0, 1, 2 самолетов, то она получает из резерва 1 самолет ночью. На следующий день, если в наличии 3 или 4 самолета, то задание дается, иначе – отменяется. Каждый са-

43 молет может быть выведен из строя с вероятностью р. Если на за- дание посылается n самолетов, то вероятность того, что k из них будут выведены из строя, задается биномиальным распределением




!
!
!
k
n k
n
p q
k n k



,
(31) где
1
q
p
 
Матрица вероятностей переходов имеет вид
3 2
2 3
4 3
2 2
3 4
0 1
0 0
0 0
1 0
3 3
0 4
6 4
P
p
p q
pq
q
p
p q
p q
pq
q



Первая строка матрицы относится к случаю, когда в момент
i
име- ется один самолет, тогда в момент
1
i

будет два самолета, так как ночью будет получено пополнение – один самолет и не будет вы- лета. Вторая строка – два самолета в момент
i
– нет вылета и три самолета в момент
1
i

. Третья строка – в момент i имеется три самолета – будет вылет, вероятность того, что в момент
1
i

будет один самолет соответствует случаю, что все три самолета будут сбиты, т.е.
3 31
p
p

. Вероятность того, что к моменту
1
i

будет два самолета соответствует тому, что один самолет вернулся, т.е.
2 32 3
p
p q

. Вероятность того, что в момент
1
i

будет три само- лета равна сумме вероятностей того, что вернулись два или три са- молета, т.е.
2 3
33 3
p
pq
q


. Аналогичные рассуждения применя- ются и для четвертой строки. При рассуждениях имеется в виду тот факт, что число самолетов определяется утром после возможного пополнения по схеме
Вылет на задание или отдых
Пополнение
Вылет на задание или отдых
Пополнение
Вылет на задание или отдых момент
i

момент
1
i
 
Постройте график, представляющий матрицу переходов в этом случае.

44 2. В каждом заезде на скачках определенная лошадь выигрывает заезд с вероятностью 2/5, делит первое и второе место с вероятно- стью 1/5 и проигрывает с вероятностью 2/5 независимо от исхода любого предыдущего заезда. Постройте матрицы Р, Р
2
и Р
3 3. 80% сыновей выпускников Гарвардского университета посту- пают в Гарвард, остальные в Иелл, 40% выпускников Иеллского университета поступают в Иелл, остальные разделяются поровну между Гарвардом и Дортмундом и, наконец, 70% сыновей выпуск- ников Дортмундского университета поступают в Дортмунд, 20% в
Гарвард и 10% в Иелл. Постройте матрицу Р. Определите вероят- ность, с которой внук выпускника Гарвардского университета по- ступает в Гарвард.
4. Рассмотрим процесс наследования признаков, когда признак определяется одной парой генов типа G и g. Каждый индивид мо- жет иметь генные признаки типа GG, gg, Gg. Для типов Gg и gG говорят, что ген G доминирует над геном g. Тип GG называется доминантным, gg называется рецессивным, Gg называется гибрид- ным. При скрещивании от потомков выбираются по одному гену случайным образом. Тогда
GG + GG = GG, gg + gg = gg, GG+gg=Gg.
При скрещивании типов GG+Gg от первого и от второго берется G с вероятностью 1/2 и g с вероятностью 1/2. Поэтому
GG + Gg = 1/2GG + 1/2Gg.
Аналогично gg+Gg=1/2Gg+1/2gg. Для Gg+Gg потомство с вероят- ностью 1/2 получает гены каждого типа от каждого из родителей, поэтому Gg+Gg = 1/4GG+1/2Gg+1/2gg. Определите матрицу Р для скрещивания индивидуума с неизвестными генными признаками и гибридным. Определите матрицы Р, Р
2
, Р
3
, если начинаем с гиб- рида.
5.2. Марковские цепи с поглощением [5]
Рассмотрим следующую модель пьяницы: пьяница ходит только по прямой линии и с вероятностью 1/3 идет влево, либо 2/3 вправо.
Всего он может сделать 4 шага, с обеих сторон от пьяного стоят полицейские. Как только он доходит до одного из них, так его за- бирают в участок. Обозначим состояние пьяного 0, 1, 2, 3, 4. Со-

45 стояние 0 и 4 называются поглощающими, так как, попав в них, пьяница уже не возвращается. Матрица переходов имеет вид:
0 1
2 3
4 0
1 2
3 4
1 0
0 0
0 1 3 0
2 3 0
0 0
1 3 0
2 3 0
0 0
1 3 0
2 3 0
0 0
0 1
Такие марковские цепи называются цепями с поглощением. Для них интересуются ответами на следующие вопросы: а) какова вероятность того, что процесс завершится переходом в конкретное поглощающее состояние; б) сколько в среднем шагов потребуется, чтобы попасть в по- глощающее состояние; в) сколько в среднем раз проходит процесс через каждое непо- глощающее состояние?
Для ответа на эти вопросы приведем матрицу переходов в кано- нический вид, выписывая первыми поглощающие состояния
0
поглощение
непоглощение
поглощающее
непоглощающее
I
P
R
Q

где I – единичная матрица, 0 – нулевая, Q и R – неотрицательные матрицы. В теории марковских цепей показано, что процесс обяза- тельно попадет в поглощающее состояние, т.е.
0
n
n
Q


и беско- нечный ряд
2
N
I
Q Q
  

сходится к пределу, равному об- ратной матрице


1
I
Q


, т.е.


1
N
I
Q



Матрица N называется фундаментальной матрицей. Тогда обо- значим 1 – вектор столбец из 1,

– вектор сумм по строкам N мат- рицы, равный
1
N

ij
n
дает среднее время пребывания в состоя- нии S
j
при начальном состоянии S
i
(где S
i
и S
j
– непоглощающие,
t
i
– среднее число шагов до поглощения, при начальном S
j
, т.е. i-й элемент вектора

ik
b
– вероятность того, что при начальном S
i

46 процесс будет поглощен в состояние S
k
, равна ik-ому элементу матрицы B = NR). Для нашего примера канонический вид
0 4
1 2
3 0
4 1
2 3
1 0
0 0
0 0
1 0
0 0
1 3 0 0 2 3 0 0
0 1 3 0 2 3 0 2 3 0 1 3 0
P

Тогда


1 1
1 2 3 0
7 5 6 5 4 5 1 3 1
2 3 3 5 4 5 6 5 0
1 3 1 5 3 5 7 5
N
I
Q





 



,
7 5 6 5 4 5 1 17 5 1
3 5 4 5 6 5 1 18 5 1 5 3 5 7 5 1 11 5
N
   
 
,
7 5 6 5 4 5 1 3 0
7 15 8 15 3 5 4 5 6 5 0
0 1 15 9 15 1 5 3 5 7 5 0
2 3 1 15 14 15
B
N R
  


Таким образом, среднее время пребывания в состоянии 2 при начальном состоянии 1 равно 7/5 согласно матрице N.
Среднее число шагов до поглощения из состояния 1 равно 3 и вероятность поглощения из состояния 3 правым полицейским рав- на 14/15.

47 зом среди тех чисел, которые больше Х. Процесс завершается, ко- гда выбранным числом оказывается 1. Состояние марковского про- цесса задаются числами, которые могут быть выбраны.
Покажите, что
1 0
0 0
1 1 2 0
0 1 1 2 1 3 0
1 1 2 1 3 1 4
T
I


, где I – единичная матрица 4-го порядка.
Каково среднее число выборов? (Ответ 25/12).
4. Три танка ведут бой, каждый с двумя другими. Танк А уни- чтожает танк, по которому ведет огонь с вероятностью 1/3, танк B
– с вероятностью 1/3, танк C – с вероятностью 1/6. Открывают огонь одновременно, и каждый стреляет по сильнейшему из неуни- чтоженных к этому моменту танку. Найдите T,

и B.
5.3. Цепи Маркова в социологии [5]
Испытуемый среди других 7 человек участвует в эксперименте по зрительному восприятию: необходимо выбрать из 3-х сравнива- емых линий ту, которая равна эталонной. Испытуемый отвечает последним после 7 одинаковых неправильных ответов. С одной стороны он должен ответить согласно своему восприятию, а с дру- гой стороны согласиться с единодушным мнением группы. В экс- перименте исследуется последовательность ответов в серии испы- таний. Можно построить вероятностную модель, которая предска- жет некоторые средние свойства. Каждый из 33 испытуемых под- вергается 35 испытаниям, и ответы могут быть такого вида
aaabbаааbbbааааb..........аааааааа
начальный отрезок конечный, где а – правильный ответ, b – неправильный. Конечным ответом (а или b) назовем последний 35-й ответ и конечным отрезком – по- следовательность совпадающих с последним ответов. Какие вели- чины пригодны для наблюдения в такой серии? Начнем с подсчета переходов, пусть
aa
n
– число переходов от а к а в начальном отрез-

48 ке,
ab
n
– число переходов от а к b, аналогичное значение имеют
ba
n
и
bb
n
Эти величины однозначны за исключением первого ответа, его будем классифицировать как аа переход, добавляя нулевой ответ а спереди. Тогда в приведенной последовательности
8
aa
n

,
3
ab
n

,
3
ba
n

и
3
bb
n

. Зная эти соотношения, можно опреде- лить другие. Например, если
a
n
– общее число случаев, когда в начальном отрезке дается ответ а и
b
n
– общее число, когда в нача- ле ответ b, имеются соотношения
,
a
aa
ab
b
ba
bb
n
n
n
n
n
n




, длина начального отрезка равна
a
b
n
n

, длина конечного отрезка равна


36
a
b
n
n


. Чтобы знать общее число ответов а, нужно знать, что если
ab
ba
n
n

, то конечный ответ должен быть а, если
1
ab
ba
n
n


, то конечный ответ – b. Рассмотрим теперь всех 33 испытуемых. Пусть
aa
n
– общее число а–а переходов для всех ис- пытуемых, тогда первые 2 соотношения остаются справедливыми, только
a
n
теперь обозначает общее количество всех ответов а во всех начальных отрезках,
b
n
– то же для b и их сумма есть общая длина всех отрезков. Пусть n – число всех испытуемых (n = 33), t
а
– число конечных ответов а, t
b
– число конечных ответов b. Тогда
b
ab
ba
t
n
n


и
a
b
t
n t
 
Задачей нашей модели является описание и предсказание таких наблюдаемых величин. В эксперименте Коэна было получено
196,
117,
106,
102,
313,
208,
22,
11,
33.
aa
ab
ba
bb
a
b
a
b
n
n
n
n
n
n
t
t
n









Поскольку выбор n произволен, а результат сильно меняется, то целью будет предсказание усредненных величин
b
t n
и
aa
n
n
Для интерпретации эксперимента предполагается гипотеза, что ис- пытуемый может находиться в одном из 4 психических состояний:
1) нонконформизм, 2) временный нонконформизм, 3) временный конформизм, 4) конформизм. В начальном состоянии испытуемый

49 предполагается находящимся в состоянии 2. При последователь- ных испытаниях изменение состояния может быть описано с по- мощью цепи Маркова с четырьмя состояниями и матрицей вероят- ностей переходов вида
1 2
3 4
1 2
21 22 23 3
32 33 34 4
1 0
0 0
0 0
0 0
1
p
p
p
P
p
p
p

Переходы из состояния 2 в 4 и из 3 в 1 исключены. Из состояний 1 и 4 нет переходов, так как они являются поглощающими. Испыту- емый дает нонконформные ответы а, находясь в состоянии 1 и 2 и конформные ответы b – в состоянии 3 и 4. Мы не знаем точно, где на конечном отрезке испытуемый достигает состояние 1 или 4. Мы знаем лишь, что он точно придет в одно из этих состояний и для этого достаточно 35 испытаний. Приводя матрицу Р к канониче- скому виду, можно показать, что матричные элементы
ij
p
связаны с математическими ожиданиями введенных выше величин следу- ющим образом:





21 1
1
ab
ab
ba
aa
ab
ba
M
M
M
p
M
M
M





,


22
aa
aa
ab
M
p
M
M


,



2 23 1
ab
aa
ab
ba
M
p
M
M
M



,


2 32
ba
ab
ba
bb
M
p
M
M
M


,


33
bb
ba
bb
M
p
M
M


,




34
ba
ab
ba
ab
ba
bb
M
M
M
p
M
M
M



, где








,
,
,
ab
ab
aa
aa
ba
ba
bb
bb
M
M n
n
M
M n
n
M
M n
n
M
M n
n




,
Считая, что при больших n величина
ab
n
n
должна быть близка к
Мав и т.д., можно вычислить из экспериментальных данных
Маа=196/33,Мав=117/33, Мва=106/33, Мвв=102/33, что дает следующую матрицу Р.

50 1
0 0
0 0, 06 0, 63 0, 31 0
0 0, 46 0, 49 0, 05 0
0 0
1
P

Приводя матрицу к каноническому виду, получим
4 3
2 1
23 22 21 34 33 12 1
4 2
3 0
0 0
1 1
0 0
0 0
0 0
I
P
p
p
R
Q
p
p
p
p


Тогда фундаментальная матрица N будет


2 3
1 2
1 32 23 33 23 3
32 33 32 22 1
1 1
1
p
p
p
p
P
I
Q
p
p
p
p
















, где



22 33 23 32 1
1
p
p
p p
  


. Матрица вероятностей погло- щения B = NR будет равна




1 4
2 23 34 21 33 3
34 22 32 21 1
1
p p
p
p
B
p
p
p p







Согласно вышеизложенной теории вероятность поглощения в со- стояние 4 из начального состояния 2 равна
24
b
, а в состояние
1 –
21
b
. Так как процесс начинается в состоянии 2, коэффициент
23
n
матрицы N дает среднее значение общего числа опытов, при которых испытуемый находится в психическом состоянии 3 во время эксперимента.
Сделаем предсказание о числе случаев, когда испытуемый ме- няет ответы от правильного к неправильному и наоборот. Среднее число таких случаев равно
ab
ba
M
M

. Мы можем вычислить веро- ятность ровно 2k изменений, которая дается формулой
 





21 22 23 32 22 33 2
1 1
1
k
P
k
p
p
p p
p
p





 


 

(32)