Примеры использования Марковских цепей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Условие)
(Источники информации)
(не показано 10 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
== Обозначения ==
 
== Обозначения ==
  
Предположим, что проводится серия экспериментов с возможными исходами <tex>s_1,s_2,s_3,...s_n</tex>. Назовём эти исходы '''состояниями'''.  
+
Предположим, что проводится серия экспериментов с возможными исходами <tex>s_1,s_2,s_3,\ldots s_n</tex>. Назовём эти исходы '''состояниями'''.  
 
*<tex>p_i^{(0)}  </tex> — вероятность того, что мы начинаем в состоянии <tex>s_i</tex>;
 
*<tex>p_i^{(0)}  </tex> — вероятность того, что мы начинаем в состоянии <tex>s_i</tex>;
 
*<tex>p_{ij} </tex> —    вероятность того, что в результате эксперимента состояние было изменено от состояния <tex>s_i</tex> к состоянию <tex>s_j</tex>;  
 
*<tex>p_{ij} </tex> —    вероятность того, что в результате эксперимента состояние было изменено от состояния <tex>s_i</tex> к состоянию <tex>s_j</tex>;  
 
Если <tex>p_i^{(1)}</tex> вероятность того, что исходом эксперимента будет состояние <tex>s_i</tex>. Тогда
 
Если <tex>p_i^{(1)}</tex> вероятность того, что исходом эксперимента будет состояние <tex>s_i</tex>. Тогда
  
<tex>p_i^{(1)} = p_1^{(0)}p_{1i} + p_2^{(0)}p_{2i} + p_3^{(0)}p_{3i} + ... +p_n^{(0)}p_{ni}</tex> . <tex> (*) </tex>
+
<tex>p_i^{(1)} = p_1^{(0)}p_{1i} + p_2^{(0)}p_{2i} + p_3^{(0)}p_{3i} + \ldots +p_n^{(0)}p_{ni}</tex> . <tex> (*) </tex>
  
  
Строка 12: Строка 12:
 
Также заметим, что:
 
Также заметим, что:
  
<tex>p_{j1}+p_{j2}+p_{j3}+ ... +p_{jn} = 1</tex>.
+
<tex>p_{j1}+p_{j2}+p_{j3}+ \ldots +p_{jn} = 1</tex>.
*Матрица T называется матрицей перехода. В общем случае она имеет вид:
+
*Матрица <tex>T</tex> называется матрицей перехода. В общем случае она имеет вид:
  
 
<tex>
 
<tex>
 
\begin{bmatrix}
 
\begin{bmatrix}
p_{11} & p_{12} & p_{13} & ... & p_{1n} \\
+
p_{11} & p_{12} & p_{13} & \ldots & p_{1n} \\
p_{21} & p_{22} & p_{23} & ... & p_{2n} \\
+
p_{21} & p_{22} & p_{23} & \ldots & p_{2n} \\
p_{31} & p_{32} & p_{33} & ... & p_{3n} \\
+
p_{31} & p_{32} & p_{33} & \ldots & p_{3n} \\
p_{41} & p_{42} & p_{43} & ... & p_{4n} \\
+
p_{41} & p_{42} & p_{43} & \ldots & p_{4n} \\
. & . & . & ... & .\\
+
\vdots & \vdots & \vdots & \vdots & \vdots \\
. & . & . & ... &  .\\
+
 
. & . & . & ... &  .\\
+
p_{n1} & p_{n2} & p_{n3} & \ldots & p_{nn} \\
p_{n1} & p_{n2} & p_{n3} & ... & p_{nn} \\
 
  
  
Строка 32: Строка 31:
  
 
Пусть   
 
Пусть   
<tex> p^{(0)}=</tex> <tex>(p_1^{(0)},p_2^{(0)},p_3^{(0)},... ,p_n^{(0)})</tex> и  
+
<tex> p^{(0)}=</tex> <tex>(p_1^{(0)},p_2^{(0)},p_3^{(0)},\ldots ,p_n^{(0)})</tex> и  
<tex> p^{(1)}=</tex> <tex>(p_1^{(1)},p_2^{(1)},p_3^{(1)},...,p_n^{(1)})</tex>
+
<tex> p^{(1)}=</tex> <tex>(p_1^{(1)},p_2^{(1)},p_3^{(1)},\ldots,p_n^{(1)}),</tex>
  
, тогда  
+
тогда  
<tex> (p_1^{(1)},p_2^{(1)},p_3^{(1)}... ,p_n^{(1)})=</tex>
+
<tex> (p_1^{(1)},p_2^{(1)},p_3^{(1)} \ldots ,p_n^{(1)})=</tex>
<tex>(p_1^{(0)},p_2^{(0)},p_3^{(0)}.. ,p_n^{(0)})</tex>
+
<tex>(p_1^{(0)},p_2^{(0)},p_3^{(0)} \ldots ,p_n^{(0)})</tex>
 
<tex>
 
<tex>
 
\begin{bmatrix}
 
\begin{bmatrix}
p_{11} & p_{12} & p_{13} & ... & p_{1n} \\
+
p_{11} & p_{12} & p_{13} & \ldots & p_{1n} \\
p_{21} & p_{22} & p_{23} & ... & p_{2n} \\
+
p_{21} & p_{22} & p_{23} & \ldots & p_{2n} \\
p_{31} & p_{32} & p_{33} & ... & p_{3n} \\
+
p_{31} & p_{32} & p_{33} & \ldots & p_{3n} \\
p_{41} & p_{42} & p_{43} & ... & p_{4n} \\
+
p_{41} & p_{42} & p_{43} & \ldots & p_{4n} \\
. & . & . & ... &  .\\
+
\vdots & \vdots & \vdots & \vdots &  \vdots\\
. & . & . & ... .\\
+
p_{n1} & p_{n2} & p_{n3} & \ldots & p_{nn} \\
. & . & . & ... &  .\\
 
p_{n1} & p_{n2} & p_{n3} & ... & p_{nn} \\
 
 
\end{bmatrix}
 
\end{bmatrix}
 
</tex>.
 
</tex>.
  
Использование матриц приводит к более компактной записи условий. По своей сути, перемножение строки <tex> p_i^{(0)} </tex> с матрицей <tex> T </tex> эквивалентно уравнению <tex>  (*)  </tex> , рассмотренному ранее.
+
Использование матриц приводит к более компактной записи условий. По своей сути, перемножение строки <tex> p_i^{(0)} </tex> с матрицей <tex> T </tex> эквивалентно уравнению <tex>  (*)  </tex>, рассмотренному ранее.
  
 
== Прогноз погоды ==
 
== Прогноз погоды ==
Строка 115: Строка 112:
 
Пусть <tex>p_i^{(m)} </tex> —  вероятность, что исходом m-го проведения эксперимента будет состояние <tex>s_i</tex> и  
 
Пусть <tex>p_i^{(m)} </tex> —  вероятность, что исходом m-го проведения эксперимента будет состояние <tex>s_i</tex> и  
  
<tex>p^{(m)} =</tex>  <tex>(p_1^{(m)},p_2^{(m)},p_3^{(m)},...,p_n^{(m)}).</tex>
+
<tex>p^{(m)} =</tex>  <tex>(p_1^{(m)},p_2^{(m)},p_3^{(m)},\ldots,p_n^{(m)}).</tex>
  
 
{{Теорема
 
{{Теорема
 
|id=идентификатор (необязательно), пример: th1.   
 
|id=идентификатор (необязательно), пример: th1.   
  
|statement=Для любого положительного целого числа m выполняется <tex>p^{(m)} =</tex> <tex>p^{(0)} \times T^{(m)}</tex>.
+
|statement=Для любого положительного целого числа <tex>m</tex> выполняется <tex>p^{(m)} =</tex> <tex>p^{(0)} \times T^{(m)}</tex>.
 
|proof=Докажем теорему, используя индукцию. Было показано (в примере про погоду), что для <tex> m = 1 </tex> утверждение справедливо. Предположим, что оно справедливо для <tex>n=k</tex> , так что <tex>p^{(k)} =</tex> <tex>p^{(0)} \times T^{(k)}.</tex>Поскольку
 
|proof=Докажем теорему, используя индукцию. Было показано (в примере про погоду), что для <tex> m = 1 </tex> утверждение справедливо. Предположим, что оно справедливо для <tex>n=k</tex> , так что <tex>p^{(k)} =</tex> <tex>p^{(0)} \times T^{(k)}.</tex>Поскольку
  
Строка 130: Строка 127:
 
}}
 
}}
  
 +
== Оценка будущих продаж ==
  
 
+
[[Марковская цепь|Цепи Маркова]] также применяются при оценке будущих продаж. Например, сделав опрос среди покупателей той или иной марки автомобиля о их следующем выборе, можно составить матрицу <tex> T </tex>.  
== Оценка будущих продаж ==
 
Цепи Маркова также применяются при оценке будущих продаж. Например, сделав опрос среди покупателей той или иной марки автомобиля о их следующем выборе, можно составить матрицу <tex> T </tex>.  
 
 
=== Условие ===
 
=== Условие ===
 
В процессе опроса владельцев автомобилей трех американских марок: марки <tex>A</tex>, марки <tex>B</tex>, марки <tex>C</tex>, им был задан вопрос о том, какую торговую марку они бы выбрали для следующей покупки.
 
В процессе опроса владельцев автомобилей трех американских марок: марки <tex>A</tex>, марки <tex>B</tex>, марки <tex>C</tex>, им был задан вопрос о том, какую торговую марку они бы выбрали для следующей покупки.
Строка 170: Строка 166:
 
<tex>(0.2,0.5,0.3)</tex>.
 
<tex>(0.2,0.5,0.3)</tex>.
  
Вероятность того, что вторая машина будет марки С, равна 0.3. Для ответа на второй вопрос требуется найти  
+
Вероятность того, что вторая машина будет марки <tex>C</tex>, равна <tex>0.3</tex>. Для ответа на второй вопрос требуется найти  
  
 
<tex>T^{(2)} = </tex>
 
<tex>T^{(2)} = </tex>
Строка 181: Строка 177:
 
</tex>.
 
</tex>.
  
Для (2) имеем <tex>p^{(2)} = </tex> <tex> (0,0.5,0.5) </tex> и  
+
Для <tex>(2)</tex> имеем <tex>p^{(2)} = </tex> <tex> (0,0.5,0.5) </tex> и
  
 
<tex>p^{(2)} = </tex> <tex>(0,0.5,0.5) \times</tex>
 
<tex>p^{(2)} = </tex> <tex>(0,0.5,0.5) \times</tex>
Строка 193: Строка 189:
 
<tex> = </tex>
 
<tex> = </tex>
 
<tex>(0.225,0.55,0.225)</tex>
 
<tex>(0.225,0.55,0.225)</tex>
поэтому вероятность того, что второй автомобиль будет марки A равна 0.225.
+
поэтому вероятность того, что второй автомобиль будет марки <tex>A</tex> равна <tex>0.225</tex>.
  
 
+
==См. также==
 
+
*[[Марковская цепь]]
+
*[[Эргодическая марковская цепь]]
 +
*[[Регулярная марковская цепь]]
 +
*[[Фундаментальная матрица]]
  
 
== Источники информации ==
 
== Источники информации ==
Строка 203: Строка 201:
 
* ''Kemeny J. G., Snell J. L.'', Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960 (перевод: ''Кемени Дж. Дж., Снелл Дж. Л.'' Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.)
 
* ''Kemeny J. G., Snell J. L.'', Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960 (перевод: ''Кемени Дж. Дж., Снелл Дж. Л.'' Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.)
  
[[Категория:Дискретная математика, алгоритмы и структуры данных]]
+
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Марковские цепи ]]
 
[[Категория:Марковские цепи ]]

Версия 15:04, 14 ноября 2018

Обозначения

Предположим, что проводится серия экспериментов с возможными исходами [math]s_1,s_2,s_3,\ldots s_n[/math]. Назовём эти исходы состояниями.

  • [math]p_i^{(0)} [/math] — вероятность того, что мы начинаем в состоянии [math]s_i[/math];
  • [math]p_{ij} [/math] — вероятность того, что в результате эксперимента состояние было изменено от состояния [math]s_i[/math] к состоянию [math]s_j[/math];

Если [math]p_i^{(1)}[/math] вероятность того, что исходом эксперимента будет состояние [math]s_i[/math]. Тогда

[math]p_i^{(1)} = p_1^{(0)}p_{1i} + p_2^{(0)}p_{2i} + p_3^{(0)}p_{3i} + \ldots +p_n^{(0)}p_{ni}[/math] . [math] (*) [/math]


Это означает, что вероятность исхода в состоянии [math]s_i[/math] равна сумме вероятностей начать эксперимент в некотором другом состоянии и окончить в [math]s_i[/math]. Также заметим, что:

[math]p_{j1}+p_{j2}+p_{j3}+ \ldots +p_{jn} = 1[/math].

  • Матрица [math]T[/math] называется матрицей перехода. В общем случае она имеет вид:

[math] \begin{bmatrix} p_{11} & p_{12} & p_{13} & \ldots & p_{1n} \\ p_{21} & p_{22} & p_{23} & \ldots & p_{2n} \\ p_{31} & p_{32} & p_{33} & \ldots & p_{3n} \\ p_{41} & p_{42} & p_{43} & \ldots & p_{4n} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ p_{n1} & p_{n2} & p_{n3} & \ldots & p_{nn} \\ \end{bmatrix} [/math].


Пусть [math] p^{(0)}=[/math] [math](p_1^{(0)},p_2^{(0)},p_3^{(0)},\ldots ,p_n^{(0)})[/math] и [math] p^{(1)}=[/math] [math](p_1^{(1)},p_2^{(1)},p_3^{(1)},\ldots,p_n^{(1)}),[/math]

тогда [math] (p_1^{(1)},p_2^{(1)},p_3^{(1)} \ldots ,p_n^{(1)})=[/math] [math](p_1^{(0)},p_2^{(0)},p_3^{(0)} \ldots ,p_n^{(0)})[/math] [math] \begin{bmatrix} p_{11} & p_{12} & p_{13} & \ldots & p_{1n} \\ p_{21} & p_{22} & p_{23} & \ldots & p_{2n} \\ p_{31} & p_{32} & p_{33} & \ldots & p_{3n} \\ p_{41} & p_{42} & p_{43} & \ldots & p_{4n} \\ \vdots & \vdots & \vdots & \vdots & \vdots\\ p_{n1} & p_{n2} & p_{n3} & \ldots & p_{nn} \\ \end{bmatrix} [/math].

Использование матриц приводит к более компактной записи условий. По своей сути, перемножение строки [math] p_i^{(0)} [/math] с матрицей [math] T [/math] эквивалентно уравнению [math] (*) [/math], рассмотренному ранее.

Прогноз погоды

Условие

Погода классифицируется в прогнозах как ясная, умеренно пасмурная и пасмурная.

  1. Если погода ясная, то вероятность, что она будет ясной на следующий день, составляет [math]0.5[/math]; вероятность, что она будет умеренно пасмурной, равна [math]0.4[/math]; а вероятность пасмурной погоды на следующий день составляет [math]0.1[/math].
  2. Если погода умеренно пасмурная, то вероятность, что на следующий день она будет ясной, равна [math]0.3[/math]; вероятность, что погода останется умеренно пасмурной, равна [math]0.5[/math]; а вероятность пасмурной погоды на следующий день составляет [math]0.2[/math].
  3. Если же погода пасмурная, то вероятность, что она будет ясной на следующий день составляет [math]0.2[/math]; вероятность что она станет умеренно пасмурной, равна [math]0.4[/math]; вероятность что на следующий день она останется пасмурной, равна [math]0.4[/math].


Вопрос 1 : Если вероятность ясной погоды в воскресенье равна [math]0.6[/math], а вероятность умеренно пасмурной — [math]0.4[/math], то какова вероятность, что погода в понедельник будет ясной?

Вопрос 2 : Какова вероятность, что во вторник погода будет умеренно пасмурной?

Решение

Если порядок, в котором перечисляются погодные условия, таков: ясно, умеренно пасмурно и пасмурно, то:

[math]p^{(0)} =[/math] [math](0.6,0.4,0)[/math],

[math] T = \begin{bmatrix} 0.5 & 0.4 & 0.1 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.4 & 0.4 \end{bmatrix} [/math].

Следовательно, [math]p^{(1)} = [/math] [math](0.6,0.4,0) \times[/math] [math] \begin{bmatrix} 0.5 & 0.4 & 0.1 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.4 & 0.4 \end{bmatrix} [/math] [math] = [/math] [math](0.42,0.44,0.14)[/math] и вероятность, что в понедельник будет ясная погода, равна [math]0.42[/math].

Пусть [math]p_1^{(2)} [/math] — вероятность того, что во вторник будет ясная погода, [math]p_2^{(2)} [/math] — вероятность того, что во вторник будет умеренно пасмурно и [math]p_3^{(2)} [/math] — вероятность того, что во вторник будет пасмурно.

Пусть [math]p^{(2)} = [/math] [math] (p_1^{(2)},p_2^{(2)},p_3^{(2)})[/math].

Тогда [math]p^{(2)} = [/math] [math] (0.42,0.44,0.14) \times[/math] [math] \begin{bmatrix} 0.5 & 0.4 & 0.1 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.4 & 0.4 \end{bmatrix} [/math] [math] = [/math] [math](0.37,0.444,0.186)[/math].

Следовательно, вероятность того, что во вторник будет умеренно пасмурная погода равна [math]0.444[/math].


Пусть [math]p_i^{(m)} [/math] — вероятность, что исходом m-го проведения эксперимента будет состояние [math]s_i[/math] и

[math]p^{(m)} =[/math] [math](p_1^{(m)},p_2^{(m)},p_3^{(m)},\ldots,p_n^{(m)}).[/math]

Теорема:
Для любого положительного целого числа [math]m[/math] выполняется [math]p^{(m)} =[/math] [math]p^{(0)} \times T^{(m)}[/math].
Доказательство:
[math]\triangleright[/math]

Докажем теорему, используя индукцию. Было показано (в примере про погоду), что для [math] m = 1 [/math] утверждение справедливо. Предположим, что оно справедливо для [math]n=k[/math] , так что [math]p^{(k)} =[/math] [math]p^{(0)} \times T^{(k)}.[/math]Поскольку

[math]p_j^{(k+1)} = [/math] [math]p_1^{(k)}p_{1j} +[/math] [math]p_2^{(k)}p_{2j} +[/math] [math]p_3^{(k)}p_{3j} +[/math] [math]p_n^{(k)}p_{nj} [/math] , то

[math]p^{(k+1)} = [/math] [math]p^{(k)} T =[/math] [math]p^{(0)} T^k T =[/math] [math]p^{(0)} T^{k+1}.[/math]
[math]\triangleleft[/math]

Оценка будущих продаж

Цепи Маркова также применяются при оценке будущих продаж. Например, сделав опрос среди покупателей той или иной марки автомобиля о их следующем выборе, можно составить матрицу [math] T [/math].

Условие

В процессе опроса владельцев автомобилей трех американских марок: марки [math]A[/math], марки [math]B[/math], марки [math]C[/math], им был задан вопрос о том, какую торговую марку они бы выбрали для следующей покупки.

  1. Среди владельцев автомобилей марки [math]A[/math] [math]20 \%[/math] сказали что выберут опять эту же марку, [math]50 \%[/math] сказали, что они бы перешли на марку [math]B \%[/math], а [math]30 \%[/math] заявили, что предпочли бы марку [math]C[/math].
  2. Среди владельцев автомобилей марки [math]B[/math] [math]20 \%[/math] сказали, что перейдут на марку [math]A[/math], в то время как [math]70 \%[/math] заявили, что приобрели бы опять автомобиль марки [math]B[/math], а [math]10 \%[/math] заявили, что в следующий раз предпочли бы марку [math]C[/math].
  3. Среди владельцев автомобилей [math]C[/math] [math]30 \%[/math] ответили, что перешли бы на марку [math]A[/math], [math]30 \%[/math] сказали, что перешли бы на марку [math]B[/math], а [math]40 \%[/math] заявили, что остались бы верны той же марке [math]C[/math].

Вопрос 1 : Если некто приобрел автомобиль марки [math]A[/math], то какова вероятность, что его второй машиной будет автомобиль марки [math]C ?[/math]

Вопрос 2 : Если при покупке первой машины покупатель подбросил монету, выбирая между автомобилями марки [math]B[/math] и [math]C[/math], то какова вероятность, что его третьей машиной станет автомобиль марки [math]B ?[/math]

Решение

Матрица перехода для этого события имеет вид:

[math] \begin{bmatrix} 0.2 & 0.5 & 0.3 \\ 0.2 & 0.7 & 0.1 \\ 0.3 & 0.3 & 0.4 \end{bmatrix} [/math].

Для ответа на первый вопрос имеем: [math]p^{(0)} =[/math] [math](1,0,0)[/math] , поэтому

[math]p^{(1)} = [/math] [math](1,0,0) \times[/math] [math] \begin{bmatrix} 0.2 & 0.5 & 0.3 \\ 0.2 & 0.7 & 0.1 \\ 0.3 & 0.3 & 0.4 \end{bmatrix} [/math] [math] = [/math] [math](0.2,0.5,0.3)[/math].

Вероятность того, что вторая машина будет марки [math]C[/math], равна [math]0.3[/math]. Для ответа на второй вопрос требуется найти

[math]T^{(2)} = [/math] [math] \begin{bmatrix} 0.23 & 0.54 & 0.23 \\ 0.21 & 0.62 & 0.17 \\ 0.24 & 0.48 & 0.28 \end{bmatrix} [/math].

Для [math](2)[/math] имеем [math]p^{(2)} = [/math] [math] (0,0.5,0.5) [/math] и

[math]p^{(2)} = [/math] [math](0,0.5,0.5) \times[/math] [math] \begin{bmatrix} 0.23 & 0.54 & 0.23 \\ 0.21 & 0.62 & 0.17 \\ 0.24 & 0.48 & 0.28 \end{bmatrix} [/math] [math] = [/math] [math](0.225,0.55,0.225)[/math] поэтому вероятность того, что второй автомобиль будет марки [math]A[/math] равна [math]0.225[/math].

См. также

Источники информации

  • Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
  • Kemeny J. G., Snell J. L., Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960 (перевод: Кемени Дж. Дж., Снелл Дж. Л. Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.)