Май 23

Немного про марковский анализ

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

Итак, в соответствии с ГОСТ Р ИСО/МЭК 31010-2011

В.24 Марковский анализ

В.24.1 Краткий обзор

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

В.24.2 Область применения

Марковский анализ может быть использован для систем с различной структурой (ремонтопригодных и неремонтопригодных), включая:
– системы с параллельными независимыми компонентами;
– системы с последовательными независимыми компонентами;
– системы с распределенной нагрузкой;
– резервированные системы, включая случай, когда может произойти отказ функций переключения;
– деградирующие системы.
Марковский анализ может быть использован для расчета эксплуатационной готовности, включая расчет необходимых компонентов запчастей для ремонта.

Там еще много умных и хороших слов, но они почему-то не вдохновляют студентов. Поэтому попробуем разобраться на простом примере.

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

Напоминаю, что такие картинки легко рисуются с помощью graphviz


# Здесь и далее граф строится с помощью команды dot из пакета graphviz

digraph x01 {
rankdir=LR;
Interested->Bored [ label = "0.2" ];
Bored->Interested [ label = "0.3" ];
}

Пусть в изначально всем было интересно, и мы имели ситуацию (интересно;скучно): (100%;0%)


Рассмотрим первую минуту. Скучно стало 0,2*100%=20%. Интересно стало 0%*0,3=0%. Таким образом, к концу первой минуты имеем ситуацию  (80%;20%).

Вторая минута. Скучно стало 80%*0,2=16%. Т.е. Интересно всё остается 64% студентов, но при этом обрело интерес 20%*0,3=6%. Таким образом 70% интересно.  Скучно осталось 14% и добавилось 16%, получилось 30%.

Так рассуждать, конечно, занимательно, но всё-таки перейдем на язык математики. Пусть имеется матрица начальных состояний:

\[\begin{bmatrix}
1  \\
0
\end{bmatrix} \]

и матрица перехода

I(t) B(t)
I(t+1) 0.8 0.3
B(t+1) 0.2 0.7

\[\begin{bmatrix}
0.8 & 0.3 \\
0.2 & 0.7
\end{bmatrix}\]
Их произведение даст нам:

\[\begin{bmatrix}
0.8 & 0.3 \\
0.2 & 0.7
\end{bmatrix} \begin{bmatrix}
1  \\
0
\end{bmatrix}=\begin{bmatrix}
0.8 \\
0.2
\end{bmatrix}\]

Попробуем сделать это же самое в R.

> p<-matrix(c(1,0),nrow=2) > p
     [,1]
[1,]    1
[2,]    0
> p<-matrix(c(1,0),nrow=2)
> p
 [,1]
[1,] 1
[2,] 0
> trans<-matrix(c(0.8,0.3,0.2,0.7),nrow=2,byrow=T)
> trans
 [,1] [,2]
[1,] 0.8 0.3
[2,] 0.2 0.7
> (p<- trans %*% p)
 [,1]
[1,] 0.8
[2,] 0.2
> (p<- trans %*% p)
 [,1]
[1,] 0.7
[2,] 0.3
> (p<- trans %*% p)
 [,1]
[1,] 0.65
[2,] 0.35
> (p<- trans %*% p)
 [,1]
[1,] 0.625
[2,] 0.375
> (p<- trans %*% p)
 [,1]
[1,] 0.6125
[2,] 0.3875
> (p<- trans %*% p)
 [,1]
[1,] 0.60625
[2,] 0.39375
> (p<- trans %*% p)
 [,1]
[1,] 0.603125
[2,] 0.396875
> (p<- trans %*% p)
 [,1]
[1,] 0.6015625
[2,] 0.3984375
> (p<- trans %*% p)
 [,1]
[1,] 0.6007813
[2,] 0.3992188
> (p<- trans %*% p)
 [,1]
[1,] 0.6003906
[2,] 0.3996094
> (p<- trans %*% p)
 [,1]
[1,] 0.6001953
[2,] 0.3998047
> (p<- trans %*% p)
 [,1]
[1,] 0.6000977
[2,] 0.3999023
> (p<- trans %*% p)
 [,1]
[1,] 0.6000488
[2,] 0.3999512
> (p<- trans %*% p)
 [,1]
[1,] 0.6000244
[2,] 0.3999756
> (p<- trans %*% p)
 [,1]
[1,] 0.6000122
[2,] 0.3999878
> (p<- trans %*% p)
 [,1]
[1,] 0.6000061
[2,] 0.3999939
> (p<- trans %*% p)
 [,1]
[1,] 0.6000031
[2,] 0.3999969
> (p<- trans %*% p)
 [,1]
[1,] 0.6000015
[2,] 0.3999985
> (p<- trans %*% p)
 [,1]
[1,] 0.6000008
[2,] 0.3999992
> (p<- trans %*% p)
 [,1]
[1,] 0.6000004
[2,] 0.3999996
> (p<- trans %*% p)
 [,1]
[1,] 0.6000002
[2,] 0.3999998
> (p<- trans %*% p)
 [,1]
[1,] 0.6000001
[2,] 0.3999999
> (p<- trans %*% p)
 [,1]
[1,] 0.6
[2,] 0.4
> (p<- trans %*% p)
 [,1]
[1,] 0.6
[2,] 0.4

Как мы видим, система оказалась в состоянии стохастического равновесия. Т.е. в каждый момент времени разным студентам интересно и скучно, но пропорция сохраняется: 60% интересно и 40% скучно. Собственно, на идее того, что системы такого вида стремятся к состоянию стохастического равновесия основано решение различных практических задач.

Например, прямая задача. Известны веростяности переходов, но неизвестно состояние равновесия. Заменяем конкретные числа на вероятности состояния в общем виде и имеем тождество:

\[ \begin{bmatrix}
0.8 & 0.3 \\
0.2 & 0.7
\end{bmatrix}\begin{bmatrix}
p \\ 1-p
\end{bmatrix} = \begin{bmatrix}
p \\ 1-p
\end{bmatrix} \]

Которое можно записать как систему уравнений:

\[\begin{cases}p\times0.8+(1-p)\times0.3=p \\
p\times0.2+(1-p)\times0.7=1-p \end{cases} \]

Из первого уравнения находим \( p=0.6 \), соответственно \( 1-p=0.4 \)

Тут любопытный студент возможно спросит, а что делать с тремя состояниями? Да абсолютно то же самое! Напишем в матричном виде

\[ \begin{bmatrix}
0.8 & 0.1 & 0.1\\
0.1 & 0.6 & 0.8 \\
0.1 & 0.3 & 0.1 \\
\end{bmatrix}\begin{bmatrix}
p \\ q \\ (1-p-q)
\end{bmatrix}=\begin{bmatrix}
p \\ q \\ (1-p-q)
\end{bmatrix} \]

Далее напишем систему уравнений решим и получим результат.

Решим обратную задачу. Пусть мы видим, что в каждый момет времени у нас интересно 70% студентам, а скучно 30%. Мы знаем, что в среднем студенту становится интересно через 5 минут слушания. Какова вероятность того, что ему станет скучно? Т.е. надо определить вероятности перехода из состояния “Интересно” в “Cкучно” – x. При этом вероятность перехода в обратную сторону (интенсивность восстановления системы) равен 1/5=0.2 (“интересно” через 5 минут, частота дискретизации 1 минута).

Имеем систему:

\[ \begin{bmatrix}
1-x & 0.2 \\
x & 0.8
\end{bmatrix}\begin{bmatrix}
0.7 \\ 0.3
\end{bmatrix}=\begin{bmatrix}
0.7 \\ 0.3
\end{bmatrix}\]

Откуда имеем: \( 0.7\times(1-x)+0.3\times 0.2=0.7 \) и \(x=0.086\) (или \(x=6/70\))

Проверяем в R:


> p<-matrix(c(0.7,0.3),nrow=2) > p
     [,1]
[1,]  0.7
[2,]  0.3
> trans<-matrix(c(1-6/70,6/70,0.2,0.8),nrow=2,byrow=F) > trans
           [,1] [,2]
[1,] 0.91428571  0.2
[2,] 0.08571429  0.8
> trans %*% p
     [,1]
[1,]  0.7
[2,]  0.3

Как видим, все верно. На всякий случай уточняю, что считать не обязательно в процентах от студентов. Можно и в студентах. Например, для группы в 20 человек имеем:


> p<-matrix(c(14,6),nrow=2) 
> p
     [,1]
[1,]   14
[2,]    6
> trans<-matrix(c(1-6/70,6/70,0.2,0.8),nrow=2,byrow=F) 
> trans
           [,1] [,2]
[1,] 0.91428571  0.2
[2,] 0.08571429  0.8
> trans %*% p
     [,1]
[1,]   14
[2,]    6

Теперь, предположим, мы улучшили  какой-то из показателей, например, студенту становится интересно не через 5 минут, а через 4. Что изменится в нашей системе, если считать, что интенсивность отказа (студенту становится скучно) не изменилось? Имеем снова прямую задачу на нахождение стохастического равновесия с известной матрицей переходов. Как её решать описано выше, на этом останавливаться не будем, а просто промоделируем пошагово изменение системы и построим график.

> p<-matrix(c(0.7,0.3),nrow=2) 
> p
 [,1]
[1,] 0.7
[2,] 0.3
> 
> trans<-matrix(c(1-6/70,6/70,0.25,0.75),nrow=2,byrow=F) 
> trans
 [,1] [,2]
[1,] 0.91428571 0.25
[2,] 0.08571429 0.75
> result<-rep(0,40)
> for(i in 1:40) {
+ result[i]<-p[1,1] 
+ p<-trans %*% p }
> plot(result,pch=19,xlab="Время, мин", ylab="Доля заинтересованных студентов")
> p
 [,1]
[1,] 0.7446808
[2,] 0.2553192

Таким образом, если у вас имеется система, которую можно свести к задаче такого вида не вижу, отчего бы не использовать её в вашей ВКР.

 


Метки: , ,

Опубликовано 23.05.2017 Тушавин В.А. в категории "Используем свободное ПО", "Пишем ВКР", "Статистика в качестве