10.1: Вступ до ланцюгів Маркова

Last updated
Save as PDF

Page ID: 67141

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Цілі навчання

У цьому розділі ви навчитеся:

Запишіть матриці переходів для задач ланцюга Маркова.
Використовуйте матрицю переходу і вектор початкового стану, щоб знайти вектор стану, який дає розподіл після заданої кількості переходів.

Зараз ми вивчимо стохастичні процеси, експерименти, в яких результати подій залежать від попередніх результатів; стохастичні процеси включають випадкові результати, які можуть бути описані ймовірностями. Такий процес або експеримент називають марковським ланцюгом або марковським процесом. Процес вперше вивчив російський математик на ім'я Андрій Олександрович Марков на початку 1900-х років.

Близько 600 міст по всьому світу мають програми обміну велосипедами. Зазвичай людина платить плату за приєднання до програми і може позичити велосипед з будь-якої станції спільного використання велосипедів, а потім може повернути його в ту ж або іншу систему. Щодня розподіл велосипедів на станціях змінюється, оскільки велосипеди повертаються на різні станції, звідки вони запозичені.

Для простоти розглянемо дуже просту програму обміну велосипедом лише з 3 станціями: A, B, C. припустимо, що всі велосипеди повинні бути повернуті на станцію в кінці дня, щоб кожен день був час, скажімо опівночі, що всі велосипеди знаходяться на якійсь станції, і ми можемо оглянути всі станції в цей час день, кожен день. Ми хочемо моделювати рух велосипедів з півночі даного дня до півночі наступного дня. Ми виявляємо, що протягом 1 денного періоду,

з велосипедів, запозичених зі станції А, 30% повертаються на станцію А, 50% опиняються на станції B, а 20% - на станції C.
велосипедів, запозичених зі станції B, 10% опиняються на станції A, 60% повернуті на станцію B, а 30% - на станції C
з велосипедів, запозичених зі станції C, 10% опиняються на станції А, 10% опиняються на станції B, а 80% повертаються на станцію C.

Ми можемо намалювати діаграму зі стрілками, щоб показати це. Стрілки вказують станцію, де був запущений велосипед, називається його початковим станом, а станції, на яких він може бути розташований через день, називаються кінцевими станами. Цифри на стрілках показують ймовірність знаходження в кожному із зазначених станів терміналу.

$Розділ 10.1. PNG$

Оскільки наш приклад спільного використання велосипедів простий і має лише 3 станції, діаграма стрілок, яку також називають орієнтованим графіком, допомагає нам візуалізувати інформацію. Але якби у нас був приклад з 10, або 20, або більше станцій спільного використання велосипедів, схема стала б настільки складною, що було б важко зрозуміти інформацію на схемі.

Ми можемо використовувати матрицю переходу для організації інформації,

Кожен рядок в матриці представляє початковий стан. Кожен стовпець представляє стан терміналу.
Ми присвоїмо рядки для станцій A, B, C, а стовпці в тому ж порядку станціям A, B, C. Тому матриця повинна бути квадратною матрицею, з такою ж кількістю рядків, як і стовпці. Наприклад, запис у рядку 2 стовпці 3 покаже ймовірність того, що велосипед, який спочатку знаходиться на станції B, буде на станції C через день: цей запис дорівнює 0.30, що є ймовірністю на діаграмі для стрілки, яка вказує від B до C. Ми використовуємо цю букву T для матриці переходу.

$Розділ 10.1 B.PNG$

Дивлячись на перший рядок, який представляє велосипеди спочатку на станції А, ми бачимо, що 30% велосипедів, запозичених зі станції А, повертаються на станцію А, 50% - на станції B, а 20% - на станції C, через один день.

Відзначимо деякі властивості матриці переходу:

$t_{ij}$представляє запис у$i$ стовпці рядків$j$
$t_{ij}$= ймовірність переходу зі стану, представленого рядком,$i$ до стану, представленого рядком$j$ за один перехід

$t_{ij}$це умовна ймовірність, яку ми можемо записати як:
$t_{ij}$ = P (наступний стан - стан у стовпці$j$ | поточний стан - стан у рядку$i$)
Кожен ряд додає до 1
Усі записи знаходяться від 0 до 1 включно, оскільки вони є ймовірностями.
Матриця переходу являє собою зміну протягом одного перехідного періоду; у цьому прикладі один перехід є фіксованою одиницею часу одного дня.

Приклад$\PageIndex{1}$

Місто обслуговується двома компаніями кабельного телебачення, BestTV і CableCast.

Завдяки агресивній тактиці продажів, щороку 40% клієнтів BestTV переходять на CableCast; інші 60% клієнтів BestTV залишаються з BestTV.
З іншого боку, 30% клієнтів CableCast переходять на Best TV.

Два держави в цьому прикладі - це BestTV і CableCast. Висловіть інформацію вище як матрицю переходу, яка відображає ймовірності переходу з одного стану в інший стан.

Рішення

Матриця переходу буває:

$Приклад 10.1.1.PNG$

Як зазначалося раніше, читач повинен зауважити, що матриця переходу - це завжди квадратна матриця, оскільки всі можливі стани повинні мати як рядки, так і стовпці. Всі записи в матриці переходу є невід'ємними, оскільки вони представляють ймовірності. І, оскільки всі можливі результати розглядаються в марковському процесі, сума записів рядків завжди дорівнює 1.

З більшою матрицею переходу ідеї в прикладі$\PageIndex{1}$ можуть бути розширені, щоб представити ринок з більш ніж 2 компаніями кабельного телебачення. Поняття лояльності до бренду та перемикання між брендами, продемонстровані на прикладі кабельного телебачення, застосовуються до багатьох видів продукції, таких як носії стільникових телефонів, бренди регулярних покупок, таких як продукти харчування або пральний порошок, основні покупки брендів, такі як автомобілі чи техніка, авіакомпанії, які вибирають мандрівники, коли бронювання авіаквитків або мережі готелів, в яких мандрівники вирішують залишитися.

Матриця переходу показує ймовірності переходів між станами в два рази поспіль. Нам потрібен спосіб представити розподіл між державами в конкретний момент часу. Для цього ми використовуємо матрицю рядків, яка називається вектором стану. Вектор стану — це матриця рядків, яка містить лише один рядок; вона має один стовпець для кожного стану. Записи показують розподіл за станом у заданий момент часу. Всі записи знаходяться в діапазоні від 0 до 1 включно, а сума записів дорівнює 1.

Для прикладу спільного використання велосипеда з 3 станціями спільного використання велосипедів, вектор стану - це$1 \times 3$ матриця з 1 рядком та 3 стовпцями. Припустимо, що коли ми починаємо спостерігати нашу програму частки велосипедів, 30% велосипедів знаходяться на станції А, 45% велосипедів знаходяться на станції B, а 25% - на станції C. Початковий вектор стану

$Розділ 10.1 c.png$

Індекси 0 вказує на те, що це початковий розподіл, перш ніж відбуватимуться будь-які переходи.

Якщо ми хочемо визначити розподіл після одного переходу, нам потрібно буде знайти новий вектор стану, який ми будемо називати V ₁. Індекси 1 вказує, що це розподіл після 1 переходу відбувся.

Знаходимо V ₁ шляхом множення V ₀ на матрицю переходу T, наступним чином:

\ [\ begin {масив} {l}
\ mathrm {V} _ {1} =\ mathrm {V} _ {0}\ mathrm {T}\
=\ лівий [\ begin {масив} {lll}
0.30 & 0.45 & 0.25
\ кінець {масив}\ праворуч [\ почати {масив} {lll}
0.3 & 0.5\
0.1 & 0.6 & 0,3\\
0.1 & 0.8
\ кінець {масив}\ праворуч]\
= [.30 (.3) +.45 (.1) +.25 (.1)\ квадрад .30 (.5) +.45 (.6) +.25 (.6) +.25 (.8) +.25 (.8)]\
=\ лівий [\ почати {масив} {lll}
.16 & .445 & .395
\ кінець {масив}\ праворуч]
\ кінець { масив}\ nonumber\]

Після 1 дня (1 перехід) 16% велосипедів знаходяться на станції А, 44.5% - на станції B і 39,5% - на станції C.

Ми показали покрокову роботу для множення матриць вище. У майбутньому ми взагалі будемо використовувати технологію, таку як матричні можливості нашого калькулятора, щоб виконувати будь-які необхідні множення матриць, а не показувати поетапну роботу.

Припустимо, тепер, коли ми хочемо дізнатися про розподіл велосипедів на станціях через два дні. Нам потрібно знайти V ₂, вектор стану після двох переходів. Щоб знайти V ₂, множимо вектор стану після одного переходу V ₁ на матрицю переходу T.

\ [\ mathrm {V} _ {2} =\ mathrm {V} _ {1}\ mathrm {T} =\ лівий [\ почати {масив} {lll}
.16 & .445 & .395
\ end {масив}\ вправо]\ лівий [\ begin {масив} {lll}
0,3 & 0.5 & 0.2\
0.1 & 0.1 & 0.1 &
0.1 & 0.1 & 0.1
\ кінець { масив}\ праворуч] =\ лівий [\ почати {масив} {lll}
.132 & .3865 & .4815
\ кінець {масив}\ праворуч]\ nonumber\]

Відзначимо, що$\mathrm{V}_{1}=\mathrm{V}_{0} \mathrm{T}, \text { so } \mathrm{V}_{2}=\mathrm{V}_{1} \mathrm{T}=\left(\mathrm{V}_{0} \mathrm{T}\right) \mathrm{T}=\mathrm{V}_{0} \mathrm{T}^{2}$

Це дає еквівалентний метод розрахунку розподілу велосипедів на 2 день:

\ [\ почати {масив} {l}
\ mathrm {V} _ {2} =\ mathrm {V} _ {0}\ mathrm {T} ^ {2} =\ лівий [\ begin {масив} {lll}
0.30 & 0.45 & 0.25
\ кінець {масив}\ праворуч]\ лівий [\ почати {масив} {lll}
0.3 & 0.5 & 0.5\
0.1 & 0.6 & 0,3\\
0.1 & 0 .1 & 0.8
\ кінець {масив}\ праворуч] ^ {2}\\
=\ left [\ begin {масив} {llll}
0.30 & 0.45 & 0.25
\ кінець {масив}\ праворуч]\ left [\ begin {масив} {lll}
0.16 &
0.47\\ 0.12 & 0.44\\
0.12 & ; 0.19 & 0.69
\ кінець {масив}\ праворуч]\\ mathrm {V} _ {2} =
\ mathrm {V} _ {0}\ mathrm {T} ^ {2} =\ лівий [\ почати {масив} {llll}
.132 & .3865 & .4815\ кінець {масив}\ праворуч]\ кінець {масив}\ кінець {масив}\ кінець {масив}\ кінець {масив}
\ кінець {масив}\ кінець {масив}
\ кінець {масив}\ кінець {масив}\ nonumber\]

Через 2 дні (2 переходи) 13,2% велосипедів знаходяться на станції А, 38,65% - на станції B і 48,15% - на станції С.

Потрібно вивчити наступне: У чому сенс записів в матриці T ²?

\ [\ mathrm {T} ^ {2} =\ mathrm {TT} =\ лівий [\ почати {масив} {ccc}
0,3 & 0,5 &
0,2\ 0.1 & 0.3\
0.1 & 0.1 & 0.8
\ end {масив}\ праворуч [\ почати {масив} {ccc}
0,3 & 0.5 & 0.2\
0.1 & 0.6 & 0. 3\\
0.1 & 0.1 & 0.8
\ кінець {масив}\ праворуч] =\ лівий [\ begin {масив} {ccc}
0.16 & 0.47 &
0.37\\ 0.12 & 0.44\\
0.12 & 0.19 & 0.69
\ кінець {масив}\ праворуч]\ nonumber\]

Записи в T ² говорять нам про ймовірність того, що велосипед знаходиться на певній станції після двох переходів, враховуючи його початкову станцію.

Введення t ₁₃ в рядку 1 стовпчик 3 говорить нам, що велосипед, який спочатку запозичений зі станції А, має ймовірність 0,37 перебування в станції С після двох переходів.
Вхід t ₃₂ в рядку 3 стовпець 2 говорить нам, що велосипед, який спочатку запозичений зі станції C, має ймовірність 0. 19 перебування на станції B після двох переходів.

Аналогічно, якщо ми піднімаємо матрицю переходу T до n-ої потужності, записи в T ⁿ повідомляють нам про ймовірність того, що велосипед знаходиться на певній станції після n переходів, враховуючи його початкову станцію.

А якщо помножити початковий вектор стану V ₀ на T ⁿ, то отримана матриця рядків Vn=V ₀ T ⁿ - розподіл велосипедів після$n$ переходів.

Приклад$\PageIndex{2}$

Див. приклад$\PageIndex{1}$ матриці переходу частки ринку для абонентів двох компаній кабельного телебачення.

Припустимо, що сьогодні 1/4 клієнтів підписуються на BestTV і 3/4 клієнтів підписуються на CableCast. Через 1 рік, який відсоток підписується на кожну компанію?
Припустимо замість цього, що сьогодні 80% клієнтів підписуються на BestTV і 20% підписуються на CableCast. Через 1 рік, який відсоток підписується на кожну компанію?

Рішення

a.Початковий розподіл, заданий початковим вектором стану, є$1\times2$ матрицею

\ [\ mathrm {V} _ {0} =\ лівий [\ почати {масив} {lll}
1/4 & 3/4
\ кінець {масив}\ справа] =\ лівий [\ begin {масив} {ll}
.25 & .75
\ кінець {масив}\ праворуч]\ nonumber\]

і матриця переходу

\ [\ mathrm {T} =\ left [\ begin {масив} {ll}
.60 & .40\\
.30 & .70
\ end {масив}\ праворуч]\ nonumber\]

Через 1 рік розподіл клієнтів

\ [\ mathrm {V} _ {1} =\ mathrm {V} _ {0}\ mathrm {T} =\ лівий [\ begin {масив} {ll}
.25 & .75
\ кінець {масив}\ вправо]\ лівий [\ begin {масив} {ll}
.60 & .40\\
.30 & .70
\ кінець {масив}\ праворуч] =\ лівий\\ початок [{масив} {lll}
.375 & .625
\ end {масив}\ право]\ nonumber\]

Через 1 рік 37,5% клієнтів підписуються на BestTV і 62,5% на CableCast.

b. початковий розподіл, заданий початковим вектором стану\ (\ mathrm {V} _ {0} =\ left [\ begin {array} {l}
.8 & .2
\ end {array}\ right]\). Тоді

\ [\ mathrm {V} _ {1} =\ mathrm {V} _ {0}\ mathrm {T} =\ лівий [\ початок {масив} {ll}
.8 & .2
\ end {масив}\ вправо]\ лівий [\ begin {масив} {ll}
.60\\
.30 & .70
\ кінець {масив}\ праворуч] =\ left [{begin} масив} {ll}
.54 & .46
\ end {масив}\ право]\ nonumber\]

При цьому через 1 рік 54% клієнтів підписуються на BestTV і 46% на CableCast.

Зауважте, що розподіл після одного переходу залежить від початкового розподілу; розподіли по частинам (a) і (b) відрізняються через різні вектори початкового стану.

Приклад$\PageIndex{3}$

Професор Саймонс або ходить до школи, або їздить на велосипеді. Якщо він буде ходити в школу одного дня, то на наступний день він буде ходити або їздити на велосипеді з однаковою ймовірністю. Але якщо він один день велосипедів, то ймовірність того, що він буде ходити на наступний день, дорівнює 1/4. Висловіть цю інформацію в матриці переходу.

Рішення

Отримаємо наступну матрицю переходу, правильно розмістивши записи рядків і стовпців. Відзначимо, що якщо, наприклад, професор Саймонс велосипедів одного разу, то ймовірність того, що він буде ходити на наступний день, становить 1/4, а значить, ймовірність того, що він буде їздити на велосипеді на наступний день, дорівнює 3/4.

$Приклад 10.1.3.PNG$

Приклад$\PageIndex{4}$

У прикладі$\PageIndex{3}$, якщо передбачається, що початковим днем є понеділок, напишіть матрицю, яка дає ймовірності переходу з понеділка на середу.

Рішення

Якщо сьогодні понеділок, то середа - це два дні відтепер, представляючи собою два переходи. Нам потрібно знайти квадрат T ² вихідної матриці переходу T, використовуючи множення матриці.

\ [T=\ left [\ begin {масив} {ll}
1/2 & 1/2\
1/4 & 3/4
\ end {масив}\ праворуч]\ nonumber\]

\ begin {вирівняний}
\ mathrm {T} ^ {2} =\ mathrm {T}\ раз\ mathrm {T} &=\ лівий [\ почати {масив} {lll}
1/2\
1/4 & 3/4
\ end {масив}\ праворуч]\ лівий [\ почати {масив} {l}
1/2\
1/4 & 1/2/
\ кінець { масив}\ праворуч]\\
&=\ лівий [\ почати {масив} {cc}
1/4+1/8 & 1/4+3/8\\
1/8+3/16 & 1/8+9/16
\ кінець {масив}\ праворуч]\\
&=\ лівий [\ почати {масив} {cc}
3/8 & 5/8\
5/16 & 11/ 16
\ end {масив}\ праворуч]
\ кінець {вирівняний}

Нагадаємо, що ми отримуємо не$T^2$ шляхом квадратизації кожного запису в матриці$T$, а отримуємо$T^2$ шляхом множення матриці$T$ на себе за допомогою множення матриці.

Наведемо результати в наступній матриці.

$Приклад 10.1.4.PNG$

Тлумачимо ймовірності з матриці Т ² наступним чином:

P (Пішов середу | Йшов понеділок) = 3/8.
P (Велосипедна середа | Ходів понеділок) = 5/8.
P (Ходів середу | Велосипедний понеділок) = 5/16.
P (Велосипедна середа | Велосипедний понеділок) = 11/16.

Приклад$\PageIndex{5}$

Матриця переходу для Прикладу$\PageIndex{3}$ наведена нижче.

$Приклад 10.1.5.PNG$

Запишіть матрицю переходу з

З понеділка по четвер
З понеділка по п'ятницю.

Рішення

а.) При написанні матриці переходу з понеділка на четвер ми переходимо від одного стану до іншого в три етапи. Тобто нам потрібно обчислити Т ³.

\ [\ mathrm {T} ^ {3} =\ лівий [\ почати {масив} {ll}
11/32 & 21/32\\
21/64 & 43/64
\ кінець {масив}\ праворуч]\ nonumber\]

б) Щоб знайти матрицю переходу з понеділка на п'ятницю, переходимо з одного стану в інший в 4 кроки. Тому обчислюємо Т ⁴.

\ [\ mathrm {T} ^ {4} =\ лівий [\ почати {масив} {ll}
43/128 & 85/128\
85/256 & 171/256
\ кінець {масив}\ праворуч]\ nonumber\]

Важливо, щоб учень зміг правильно інтерпретувати вищевказану матрицю. Наприклад, запис 85/128 говорить, що якщо професор Саймонс ходив до школи в понеділок, то існує 85/128 ймовірність того, що він буде їздити на велосипеді до школи в п'ятницю.

Є певні ланцюги Маркова, які мають тенденцію стабілізуватися в довгостроковій перспективі. Ми розглянемо їх більш глибоко пізніше в цьому розділі. Матриця переходу, яку ми використовували в наведеному вище прикладі, якраз така ланцюжок Маркова. Наступний приклад стосується довгострокової тенденції або стабільної ситуації для цієї матриці.

Приклад$\PageIndex{6}$

Припустимо, професор Саймонс продовжує ходити і їздити на велосипеді відповідно до матриці переходу, наведеної в прикладі$\PageIndex{3}$. Зрештою, як часто він буде ходити в школу, і як часто буде їздити на велосипеді?

Рішення

Якщо розглядати вищі потужності матриці переходу T, то виявимо, що вона стабілізується.

\ [\ mathrm {T} ^ {5} =\ лівий [\ почати {масив} {ll}
.333984 & 666015\
.333007 & .666992
\ кінець {масив}\ справа]\ квадратний\ матхрм {T} ^ {10} =\ лівий [\ почати {масив} {ll}
.33333397 & .66666603\
.333333301 & .66666698
\ кінець {масив}\ праворуч]\ nonumber\]

\ [\ текст {І}\ квадратний\ mathrm {T} ^ {20} =\ лівий [\ почати {масив} {ll}
1/3\
1/3 & 2/3\ 3
\ end {масив}\ справа]\ квад\ текст {і}\ mathrm {T} ^ {\ mathrm {n}}} =\ лівий [\ почати {масив} {cc}
{cc}/3 & 2/3\\
1/3 & 2/3
\ end {масив}\ право]\ текст {для}\ mathrm {n} >20\ nonumber\]

Матриця показує, що в довгостроковій перспективі професор Саймонс буде ходити до школи 1/3 часу і велосипед 2/3 часу.

Коли це відбувається, ми говоримо, що система знаходиться в сталому стані або стані рівноваги. У цій ситуації всі вектори рядків рівні. Якщо вихідна матриця є матрицею n на n, ми отримуємо n рядкових векторів, які всі однакові. Ми називаємо цей вектор фіксованим вектором ймовірності або вектором рівноваги Е. У наведеній вище задачі фіксований вектор ймовірності E дорівнює [1/3 2/3]. Крім того, якщо вектор рівноваги E помножити на вихідну матрицю T, то результатом буде вектор рівноваги Е.

ET = E, або\ (\ left [\ begin {масив} {lll}
1/3 & 2/3
\ кінець {масив}\ праворуч]\ лівий [\ початок {масив} {cc}
1/2\
1/4 & 3
\ end {масив}\ праворуч] =\ лівий [\ почати {масив} {ll}
1/3
\ кінець {масив} }\ праворуч]\)

Цілі навчання

Приклад\(\PageIndex{1}\)

Приклад\(\PageIndex{2}\)

Приклад\(\PageIndex{3}\)

Приклад\(\PageIndex{4}\)

Приклад\(\PageIndex{5}\)

Приклад\(\PageIndex{6}\)