10.3: Звичайні ланцюги Маркова

Last updated
Save as PDF

Page ID: 67119

$ \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}}$

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

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

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

В кінці Розділу 10.1 ми розглянули матрицю переходу Т для професора Саймонса, що ходить і їздить на велосипеді на роботу. Коли ми обчислювали вищі та вищі потужності T, матриця почала стабілізуватися, і нарешті вона досягла свого сталого стану або стану рівноваги. Коли це сталося, всі вектори рядків стали однаковими, і ми назвали один такий вектор рядка фіксованим вектором ймовірності або вектором рівноваги Е. Крім того, ми виявили, що ET = E.

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

Чи досягає кожен ланцюг Маркова стану рівноваги? Чи є спосіб визначити, чи досягає ланцюг Маркова стану рівноваги?
Чи завжди добуток вектора рівноваги і його матриці переходу дорівнює вектору рівноваги? Тобто, чи є ET = E?
Чи можна знайти вектор рівноваги Е, не піднімаючи матрицю до вищих потужностей?
Чи залежить довгостроковий розподіл частки ринку для ланцюга Маркова від початкової частки ринку?

Вправа$\PageIndex{1}$

Чи досягає кожен ланцюг Маркова стану рівноваги?

Відповідь

Ні. Деякі ланцюги Маркова досягають стану рівноваги, а деякі - ні. Деякі переходи ланцюгів Маркова не осідають до фіксованого або рівноважного малюнка. Тому ми хотіли б мати спосіб ідентифікувати ланцюги Маркова, які досягають стану рівноваги.

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

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

На щастя, нам не потрібно вивчати занадто багато повноважень матриці переходу T, щоб визначити, чи є ланцюг Маркова регулярним; ми використовуємо технології, калькулятори або комп'ютери, щоб зробити розрахунки. Існує теорема, яка говорить, що якщо матриця$n \times n$ переходу представляє$n$ стани, то нам потрібно лише вивчити повноваження T ^m до$m = ( n-1)^2 + 1$.
Якщо якась потужність матриці переходу T ^m буде мати тільки позитивні записи, то це буде відбуватися для деякої потужності$m \leq(n-1)^{2}+1$.

Наприклад, якщо T - матриця$3 \times 3$ переходу, то

\[m = ( n-1)^2 + 1= ( 3-1)^2 + 1=5 . \nonumber \]

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

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

Визначте, чи є наступні ланцюги Маркова регулярними.

\ (\ mathrm {A} =\ left [\ begin {масив} {ll}
0 & 1\\
.4 & .6
\ end {масив}\ праворуч]\)
\ (\ mathrm {B} =\ left [\ begin {масив} {ll}
1 & 0\
3 & 7
\ end {масив}\ праворуч]\)

Рішення

а.) Матриця переходу A не має всіх позитивних записів. Але це звичайна марковська ланцюг, тому що

\ [A^ {2} =\ лівий [\ begin {масив} {ll}
.40 & .60\\
.24 & .76
\ end {масив}\ праворуч]\ nonumber\]

має тільки позитивні записи.

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

\ [\ mathrm {B} =\ лівий [\ почати {масив} {ll}
1 & 0\\
.3 & .7
\ кінець {масив}\ справа]\ квадратний\ текст {і}\ quad\ mathrm {B} ^ {2} =\ лівий [\ початок {масив} {cc}
1 & 0\\
.3 & .7
\ кінець {масив}\ праворуч]\ лівий [\\ почати масив}} {cc}
1 & 0\\
.3 & .7
\ end {масив}\ праворуч] =\ лівий [\ begin {масив} {cc}
1 & 0\\
.51 & .49
\ end {масив}\ праворуч]\ nonumber\]

Так як B -$2 \times 2$ матриця,$m = (2-1)^2+1= 2$. Ми розглянули B і B ² і виявили, що жоден не має всіх позитивних записів. Нам не потрібно вивчати будь-які вищі сили Б; Б не є звичайним ланцюгом Маркова.

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

\ [\ begin {масив} {l}
\ mathrm {M} =\ лівий [\ begin {масив} {ll}
\ mathrm {a} & 0
\\ mathrm {b} &\ mathrm {c}
\ кінець {масив}\ праворуч]
\\ mathrm {M} ^ {2} =\ лівий [\ почати {масив} {ll}
a & 0\\
b & c
\ кінець { масив}\ праворуч]\ лівий [\ почати {масив} {ll}
a & 0\\
b & c
\ кінець {масив}\ справа] =\ лівий [\ початок {масив} {ll}
\ mathrm {a}\ cdot\ mathrm {a} +0\ cdot\ mathrm {b} &\ mathrm {a}\ cdot\ mathrm {c}\
\ mathrm {b}\ cdot\ mathrm {a} +\ mathrm {c} \ cdot\ mathrm {b} &\ mathrm {b}\ cdot 0+\ mathrm {c}\ cdot\ mathrm {c}
\ end {масив}
\ справа]\ кінець {масив}\ номер\]

Зверніть увагу, що перший рядок, запис другого стовпця$a \cdot 0 + 0 \cdot c$, завжди буде нульовим, незалежно від того, до якої потужності ми піднімаємо матрицю.

Вправа$\PageIndex{2}$

Чи завжди добуток вектора рівноваги і його матриці переходу дорівнює вектору рівноваги? Тобто, чи є ET = E?

Відповідь

На даний момент читач, можливо, вже здогадався, що відповідь «так», якщо матриця переходу - це звичайна марковський ланцюжок. Спробуємо проілюструвати на наступному прикладі з розділу 10.1.

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

Матриця переходу наведена нижче.

$10.3.2.png$

Якщо початкова частка ринку для BestTV становить 20%, а для CableCast - 80%, ми хотіли б знати довгострокову частку ринку для кожної компанії.

Нехай матриця T позначає матрицю переходу для цього ланцюга Маркова, а V ₀ позначає матрицю, яка представляє початкову частку ринку. Тоді V ₀ і T виглядають наступним чином:

\ [\ mathrm {V} _ {0} =\ лівий [\ почати {масив} {ll}
.20 & .80
\ кінець {масив}\ праворуч]\ квадратний\ текст {і}\ quad\ mathrm {T} =\ лівий [\ початок {масив} {ll}
.60\\
.30 & .70
\ кінець {масив}\ праворуч]\ nonumber\]

Так як кожен рік люди переходять за матрицею переходу T, то через рік розподіл по кожній компанії виглядає наступним чином:

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

Через два роки частка ринку для кожної компанії становить

\ [\ mathrm {V} _ {2} =\ mathrm {V} _ {1}\ mathrm {T} =\ лівий [\ begin {масив} {lll}
.36 & .64
\ кінець {масив}\ вправо]\ лівий [\ begin {масив} {ll}
.60\
.30 & .70
\ кінець {масив}\ праворуч] =\ лівий [почати {масив} {ll}
. 408 & .592
\ кінець {масив}\ праворуч]\ nonumber\]

Через три роки розподіл

\ [\ mathrm {V} _ {3} =\ mathrm {V} _ {2}\ mathrm {T} =\ лівий [\ почати {масив} {ll}
.408 & .592
\ кінець {масив}\ вправо]\ лівий [\ begin {масив} {ll}
.60 & .40\
.30 & .70
\ end {масив}\ праворуч] =\ лівий [\ begin {масив} {lll}
.4224 & .5776
\ кінець {масив}\ праворуч]\ nonnumber\]

Через 20 років частка ринку задається\ (\ mathrm {V} _ {20} =\ mathrm {V} _ {0}\ mathrm {T} ^ {20} =\ left [\ begin {масив} {ll}
3/7 & 4/7
\ end {масив}\ право]\).

Через 21 рік$\mathrm{V}_{21}=\mathrm{V}_{0} \mathrm{T}^{21}=[3 / 7 \quad 4 / 7]$; частки ринку стабільні і не змінювалися.

Частка ринку через 20 років стабілізувалася до\ (\ left [\ begin {array} {ll}
3/7 & 4/7
\ end {array}\ right]\). Це означає, що

\ [\ left [\ begin {масив} {lll}
3/7 & 4/7
\ кінець {масив}\ праворуч]\ лівий [\ begin {масив} {ll}
.60 & .40\
.30 & .70
\ end {масив}\ праворуч] =\ left [\ begin {масив} {lll}
3/7 & 4/7
\ кінець {масив}\ право]\ nonumber\]

Як тільки частка ринку досягає рівноважного стану, вона залишається колишньою, тобто ET = E.

Це допомагає нам відповісти на наступне питання.

Вправа$\PageIndex{3}$

Чи можна знайти вектор рівноваги E, не піднімаючи матрицю переходу T до великих потужностей?

Відповідь

Відповідь на друге питання дає нам спосіб знайти вектор рівноваги Е. Відповідь полягає в тому, що ET = E.

Так як у нас є матриця T, ми можемо визначити Е з твердження ET = E.

Припустимо,\ (\ mathrm {E} =\ left [\ begin {масив} {ll}
\ mathrm {e} & 1-\ mathrm {e}
\ end {масив}\ право]\), то ET = E дає нам

\ [\ left [\ begin {масив} {ll}
\ mathrm {e} & 1-\ mathrm {e}
\ кінець {масив}\ праворуч]\ лівий [\ початок {масив} {ll}
.60\\
.30 & .70
\ end {масив}\ праворуч [\ почати {масив} {lll}
\ mathrm {e} & 1-\ mal терм { e}
\ end {масив}\ право]\ nonumber\]

\ [\ left [\ begin {масив} {ll}
(.60)\ mathrm {e} +.30 (1-\ mathrm {e}) & (.40)\ mathrm {e} +.70 (1-\ mathrm {e})
\ кінець {масив}\ справа] =\ лівий [\ почати {масив} {ll}
\ mathrm {e} & 1-\ mathrm {e}
\ end {масив}\ право]\ nonumber\]

\ [\ left [\ begin {масив} {ll}
.30\ mathrm {e} +.30 & -.30\ mathrm {e} +.70
\ кінець {масив}\ справа] =\ лівий [\ begin {масив} {ll}
\ mathrm {e} & 1-\ mathrm {e}
\ end {масив}\ праворуч]\ nonumber\]

\[.30\mathrm{e}+.30 = \mathrm{e} \nonumber \]

\[\mathrm{e} = 3/7 \nonumber \]

Тому\ (\ mathrm {E} =\ left [\ begin {масив} {ll}
3/7 & 4/7
\ end {масив}\ право]\)

В результаті нашої роботи в Вправи$\PageIndex{2}$ і$\PageIndex{3}$, ми бачимо, що у нас є вибір методів пошуку вектора рівноваги.

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

На питання про те, що таке досить висока потужність Т, немає «точної» відповіді.
Виберіть «високу потужність», наприклад$n=30$, або$n=50$, або$n=98$. Оцініть T ⁿ на своєму калькуляторі або за допомогою комп'ютера. Перевірте, чи T ⁿ⁺¹ = T ⁿ. Якщо T ⁿ⁺¹ = T ⁿ і всі рядки T ⁿ однакові, то ми знайшли рівновагу. Вектор рівноваги - один ряд T ⁿ. Але якщо ви ще не знайшли рівноваги для звичайної ланцюга Маркова, спробуйте використовувати вищу силу Т.

Спосіб 2: Ми можемо вирішити матричне рівняння ET=E.

Недоліком цього методу є те, що він трохи складніше, особливо якщо матриця переходу більше ніж$2 \times 2$. Однак це не так важко, як здається, якщо T не надто велика матриця, тому що ми можемо використовувати методи, які ми вивчили в розділі 2, щоб вирішити систему лінійних рівнянь, а не робити алгебру вручну.
Перевага розв'язання ET = E, як у методі 2, полягає в тому, що його можна використовувати з матрицями, які не є регулярними. Якщо матриця регулярна, вона гарантовано матиме рівноважне рішення. Якщо матриця не є регулярною, то вона може мати або не мати рівноважного рішення, а рішення ET = E дозволить довести, що вона має рівноважне рішення, навіть якщо матриця не є регулярною. (У математиці ми говоримо, що бути регулярною матрицею - це «достатня» умова для рівноваги, але не є необхідною умовою.)

Вправа$\PageIndex{4}$

Чи залежить довгострокова частка ринку ланцюга Маркова від початкової частки ринку?

Відповідь

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

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

Розглянемо початкову частку ринку\ (\ mathrm {V} _ {0} =\ left [\ begin {масив} {ll}
.20 & .80
\ end {масив}\ право]\), і матрицю переходу\ (\ mathrm {T} =\ left [\ begin {масив} {ll}
.60 & .40\
.30 & .70
\ end {масив}\ право]\) для BestTV і CableCast у наведеному вище прикладі.

Нагадаємо, ми знайшли T ⁿ, для дуже великих$n$, бути\ (\ left [\ begin {масив} {ll}
3/7 & 4/7\
3/7 & 4/7 & 4/7
\ end {масив}\ право]\).

Використовуючи наші калькулятори, ми можемо легко переконатися, що для досить великих$n$ (ми використовували$n = 30$),

\ [\ mathrm {V} _ {0}\ mathrm {T} ^ {\ mathrm {n}} =\ лівий [\ begin {масив} {ll}
.20 & .80
\ end {масив}\ праворуч [\ почати {масив} {ll}
3/7\
3/7 & 4/7 & 4/7
\ end {масив}\ праворуч] =\ лівий [\ begin {масив} {lll}
3/7 & 4/7
\ end {масив}\ праворуч]\ nonumber\]

Незалежно від того, яка початкова частка ринку, продукт є\ (\ left [\ begin {array} {ll}
3/7 & 4/7
\ end {array}\ right]\). Якщо замість цього початкова частка дорівнює\ (\ mathrm {W} _0=\ left [\ begin {array} {ll}
.10 & .90
\ end {array}\ right]\), то для досить великих$n$

\ [\ mathrm {W} _ {0}\ mathrm {T} ^ {\ mathrm {n}} =\ лівий [\ початок {масив} {lll}
.10 & .90
\ end {масив}\ вправо]\ лівий [\ begin {масив} {ll}
3/7\\ 3/7 & 4/7 & 4/7 & 4/7 & 4/7
\ 7\ end {масив}\ праворуч] =\ [\ begin {масив} {ll}

3/7 & 4/7
\ end {масив}\ праворуч]\ nonumber\]

Для будь-якого дистрибутива\ (A=\ left [\ begin {масив} {ll}
a & 1-a
\ end {масив} |\ справа.\), наприклад,

\ [\ left [\ begin {масив} {ll}
a & 1-a
\ end {масив}\ праворуч]\ лівий [\ begin {масив} {ll}
3/7\
3/7 & 4/7\ end {масив}
\ праворуч] =\ left [\ begin {масив} {ll}
3/7 (a) +3/7 (1-a) & 4/7 (a) +4/7 (a) +4/7/ 7 (1-a)
\ end {масив}\ право]\ nonumber\]

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

Це має сенс; запис$3/7(a) + 3/7(1 - a)$, наприклад, завжди дорівнюватиме 3/7.

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

Три компанії, A, B і C, конкурують один з одним. Матриця переходу T для людей, що переходять кожен місяць серед них, задається наступною матрицею переходу.

Наступний місяць

$Приклад 10.3.2 PNG$

Якщо початкова частка ринку для компаній A, B і C дорівнює\ (\ left [\ begin {array} {lll}
.25 & .35 & .40
\ end {array}\ right]\), що таке довгостроковий розподіл?

Рішення

Оскільки довгострокова частка ринку не залежить від початкової частки ринку, ми можемо просто підняти частку ринку переходу до великої потужності та отримати розподіл.

\ [\ mathrm {T} ^ {20} =\ лівий [\ begin {масив} {lll}
13/55 & 3/11 & 27/55
\ кінець {масив}\ праворуч]\ nonumber\]

У довгостроковій перспективі компанія А має 13/55 (близько 23,64%) частки ринку, Компанія Б має 3/11 (близько 27,27%) частки ринку, а компанія С має 27/55 (близько 49,09%) частки ринку.

Підсумовуємо наступним чином:

Звичайні ланцюги Маркова

Ланцюг Маркова, як кажуть, є регулярним ланцюгом Маркова, якщо якась сила має лише позитивні записи.

Нехай T - матриця переходу для регулярного ланцюга Маркова.

У міру прийняття вищих ступенів T, T ⁿ, як$n$ стає великим, наближається до стану рівноваги.
Якщо V ₀ є будь-яким вектором розподілу, а E - вектором рівноваги, то V ₀ T ⁿ = E.
Кожен рядок матриці рівноваги T ⁿ є унікальним вектором рівноваги E таким, що ET = E.
Вектор розподілу рівноваги E можна знайти, дозволивши ET = E.

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

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

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

Звичайні ланцюги Маркова