Стохастическая матрица

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

В математике стохастическая матрица — это квадратная матрица, используемая для описания переходов цепи Маркова . Каждая из его записей представляет собой неотрицательное действительное число , представляющее вероятность . ^{[1] [2] : 9–11} Ее также называют матрицей вероятности , матрицей перехода , матрицей замены или матрицей Маркова . ^{[2] : 9–11} Стохастическая матрица была впервые разработана Андреем Марковым в начале 20 века и нашла применение в самых разных научных областях, включая теорию вероятностей , статистику, математические финансы и линейную алгебру , а также как информатика и популяционная генетика . ^{[2] : 1–8} Существует несколько различных определений и типов стохастических матриц: ^{[2] : 9–11.}

Правая стохастическая матрица — это действительная квадратная матрица, сумма каждой строки которой равна 1.

Левая стохастическая матрица представляет собой действительную квадратную матрицу, сумма каждого столбца которой равна 1.

Двойная стохастическая матрица — это квадратная матрица неотрицательных действительных чисел, сумма каждой строки и столбца которой равна 1.

Точно так же можно определить стохастический вектор (также называемый вектором вероятности ) как вектор , элементами которого являются неотрицательные действительные числа, сумма которых равна 1. Таким образом, каждая строка правой стохастической матрицы (или столбец левой стохастической матрицы) равна стохастический вектор. ^{[2] : 9–11} В англоязычной математической литературе принято использовать векторы-строки вероятностей и правые стохастические матрицы, а не векторы-столбцы вероятностей и левые стохастические матрицы; эта статья следует этому соглашению. ^{[2] : 1–8} Кроме того, субстохастическая матрица представляет собой действительную квадратную матрицу, все суммы строк которой равны ${\displaystyle \leq 1.}$

История

Андрей Марков в 1886 году.

Стохастическая матрица была разработана наряду с цепью Маркова Андреем Марковым , русским математиком и профессором Санкт-Петербургского университета , который впервые опубликовал эту тему в 1906 году. ^{[2] : 1–8  [3]} Первоначально он предполагал использовать ее для лингвистического анализа. и другие математические предметы, такие как перетасовка карт , но и цепи Маркова, и матрицы быстро нашли применение в других областях. ^{[2] : 1–8  [3] [4]}

Стохастические матрицы были далее развиты такими учеными, как Андрей Колмогоров , которые расширили их возможности, допустив марковские процессы с непрерывным временем. ^[5] К 1950-м годам статьи с использованием стохастических матриц появились в области эконометрики ^[6] и теории цепей . ^[7] В 1960-х годах стохастические матрицы появились в еще более широком спектре научных работ, от поведенческой науки ^[8] до геологии ^{[9] [10]} и планирования жилых помещений . ^[11] Кроме того, за эти десятилетия была проделана большая математическая работа по расширению диапазона использования и функциональности стохастической матрицы и марковских процессов в целом.

С 1970-х годов по настоящее время стохастические матрицы нашли применение практически во всех областях, требующих формального анализа, от структурной науки ^[12] до медицинской диагностики ^[13] и управления персоналом . ^[14] Кроме того, стохастические матрицы нашли широкое применение в моделировании изменений земель , обычно под термином «матрица Маркова». ^[15]

Определение и свойства

Стохастическая матрица описывает цепь Маркова X _t над конечным пространством состояний S мощности α .

Если вероятность перехода от i к j за один временной шаг равна Pr( j | i ) = Pi _{, j} , стохастическая матрица P задается с использованием _Pi , _{j в} качестве _{элемента} i -й строки и j -го столбца. , например,

${\displaystyle P=\left[{\begin{matrix}P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots &P_{1,\alpha }\\P_{2,1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,\alpha }\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,\alpha }\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{\alpha ,1}&P_{\alpha ,2}&\dots &P_{\alpha ,j}&\dots &P_{\alpha ,\alpha }\\\end{matrix}}\right].}$

Поскольку общая вероятность перехода из состояния i во все остальные состояния должна быть равна 1,

${\displaystyle \sum _{j=1}^{\alpha }P_{i,j}=1;\,}$

таким образом, эта матрица является правой стохастической матрицей. ^{[2] : 1–8}

Вышеупомянутую поэлементную сумму по каждой строке i из P можно более кратко записать как P 1 = 1 , где 1 представляет собой α -мерный вектор-столбец всех единиц. Используя это, можно видеть, что произведение двух правых стохастических матриц P ′ и P ” также является правым стохастическим: P ′ P ” 1 = P ′ ( P “ 1 ) = P ′ 1 = 1 . В общем, k -я степень P ^k правой стохастической матрицы P также является правостохастической. Тогда вероятность перехода от i к j за два шага определяется ( i , j ) -м элементом квадрата P :

${\displaystyle \left(P^{2}\right)_{i,j}.}$

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

Начальное распределение вероятностей состояний, определяющее, где система может находиться изначально и с какими вероятностями, задается в виде вектора-строки .

Стационарный вектор вероятности π определяется как распределение, записанное в виде вектора-строки, которое не изменяется при применении матрицы перехода ; то есть оно определяется как распределение вероятностей на множестве {1,…, n } , которое также является собственным вектором строки матрицы вероятностей, связанным с собственным значением 1:

${\displaystyle {\boldsymbol {\pi }}P={\boldsymbol {\pi }}.}$

Можно показать, что спектральный радиус любой стохастической матрицы равен единице. По теореме Гершгорина о круге все собственные значения стохастической матрицы имеют абсолютные значения, меньшие или равные единице. Кроме того, каждая правая стохастическая матрица имеет «очевидный» собственный вектор-столбец, связанный с собственным значением 1: использованный выше вектор 1 , все координаты которого равны 1. Поскольку левые и правые собственные значения квадратной матрицы одинаковы, каждая стохастическая матрица имеет , по крайней мере, собственный вектор строки , связанный с собственным значением 1, и наибольшее абсолютное значение всех его собственных значений также равно 1. Наконец, теорема Брауэра о неподвижной точке (применяется к компактному выпуклому множеству всех вероятностных распределений конечного набора {1, …, n } ) подразумевает, что существует некоторый левый собственный вектор, который также является стационарным вектором вероятности.

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

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

${\displaystyle \lim _{k\rightarrow \infty }\left(P^{k}\right)_{i,j}={\boldsymbol {\pi }}_{j},}$

где π _j — j -й элемент вектора-строки π . Помимо прочего, это говорит о том, что долговременная вероятность пребывания в состоянии j не зависит от начального состояния i . То, что оба этих вычисления дают один и тот же стационарный вектор, является формой эргодической теоремы , которая в целом верна для широкого спектра диссипативных динамических систем : система со временем переходит в стационарное состояние .

Интуитивно стохастическая матрица представляет собой цепь Маркова; применение стохастической матрицы к распределению вероятностей перераспределяет вероятностную массу исходного распределения, сохраняя при этом его общую массу. Если этот процесс применяется неоднократно, распределение сходится к стационарному распределению цепи Маркова. ^{[2] : 55–59}

Пример: Кошка и Мышка.

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

Цепь Маркова , представляющая эту игру, содержит следующие пять состояний, определяемых комбинацией позиций (кошка, мышь). Обратите внимание: хотя при простом перечислении состояний можно было бы перечислить 25 состояний, многие из них невозможны либо потому, что у мыши никогда не может быть индекс ниже, чем у кошки (поскольку это означало бы, что мышь заняла кошачий ящик и выжила, чтобы пройти мимо него), либо потому, что сумма двух индексов всегда будет иметь четность . При этом 3 возможных состояния, приводящие к гибели мыши, объединены в одно:

• Состояние 1: (1,3)
• Состояние 2: (1,5)
• Состояние 3: (2,4)
• Состояние 4: (3,5)
• Состояние 5: игра окончена: (2,2), (3,3) и (4,4).

Мы используем стохастическую матрицу (ниже) для представления вероятностей перехода этой системы (строки и столбцы в этой матрице индексируются возможными состояниями, перечисленными выше, причем состояние перед переходом является строкой, а состояние после перехода — состоянием столбец). ^{[2] : 1–8} Например, начиная с состояния 1 – 1-я строка – система не может оставаться в этом состоянии, поэтому ; система также не может перейти в состояние 2 – потому что кошка осталась бы в том же ящике – таким образом , и по аналогичному аргументу для мыши, . Переходы в состояния 3 или 5 разрешены, и, таким образом , . ${\displaystyle P}$ ${\displaystyle P_{11}=0}$ ${\displaystyle P_{12}=0}$ ${\displaystyle P_{14}=0}$ ${\displaystyle P_{13},P_{15}\neq 0}$

${\displaystyle P={\begin{bmatrix}0&0&1/2&0&1/2\\0&0&1&0&0\\1/4&1/4&0&1/4&1/4\\0&0&1/2&0&1/2\\0&0&0&0&1\end{bmatrix}}.}$

Долгосрочные средние значения

Независимо от начального состояния, кошка в конечном итоге поймает мышь (с вероятностью 1), и стационарное состояние π = (0,0,0,0,1) рассматривается как предел. ^{[2] : 55–59} Чтобы вычислить долгосрочное среднее или ожидаемое значение стохастической переменной , для каждого состояния и времени необходимо внести вклад . Выживание можно рассматривать как двоичную переменную для состояния выживания и состояния завершения. Государства с не вносят вклад в долгосрочный средний показатель. ${\displaystyle Y}$ ${\displaystyle S_{j}}$ ${\displaystyle t_{k}}$ ${\displaystyle Y_{j,k}\cdot P(S=S_{j},t=t_{k})}$ ${\displaystyle Y=1}$ ${\displaystyle Y=0}$ ${\displaystyle Y=0}$

Представление фазового типа

Функция выживания мыши. Мышь переживет хотя бы первый временной шаг.

Поскольку состояние 5 является поглощающим состоянием, распределение времени до поглощения является дискретным по фазовому типу . Предположим, что система запускается в состоянии 2, представленном вектором . Состояния, в которых мышь погибла, не влияют на среднее значение выживаемости, поэтому пятое состояние можно игнорировать. Начальное состояние и матрица перехода могут быть сведены к ${\displaystyle [0,1,0,0,0]}$

${\displaystyle {\boldsymbol {\tau }}=[0,1,0,0],\qquad T={\begin{bmatrix}0&0&{\frac {1}{2}}&0\\0&0&1&0\\{\frac {1}{4}}&{\frac {1}{4}}&0&{\frac {1}{4}}\\0&0&{\frac {1}{2}}&0\end{bmatrix}},}$

и

${\displaystyle (I-T)^{-1}{\boldsymbol {1}}={\begin{bmatrix}2.75\\4.5\\3.5\\2.75\end{bmatrix}},}$

где - единичная матрица и представляет собой матрицу-столбец всех единиц, которая действует как сумма по состояниям. ${\displaystyle I}$ ${\displaystyle \mathbf {1} }$

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

${\displaystyle E[K]={\boldsymbol {\tau }}\left(I+T+T^{2}+\cdots \right){\boldsymbol {1}}={\boldsymbol {\tau }}(I-T)^{-1}{\boldsymbol {1}}=4.5.}$

Моменты более высокого порядка определяются выражением

${\displaystyle E[K(K-1)\dots (K-n+1)]=n!{\boldsymbol {\tau }}(I-{T})^{-n}{T}^{n-1}\mathbf {1} \,.}$

Смотрите также

• Матрица плотности
• Ядро Маркова , эквивалент стохастической матрицы в непрерывном пространстве состояний.
• Матричное разностное уравнение
• Модели эволюции ДНК
• Неравенство Мюрхеда
• Вероятностный автомат
• Матрица скорости перехода , используемая для обобщения стохастической матрицы на непрерывное время.

Рекомендации

1. Асмуссен, СР (2003). «Цепи Маркова». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная теория вероятности. Том. 51. С. 3–8. дои : 10.1007/0-387-21525-5_1. ISBN 978-0-387-00211-8.
2. Ганюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: Джон Уайли и сыновья. стр. 9–11. ISBN 978-1-119-38755-8.
3. Хейс, Брайан (2013). «Первые звенья цепи Маркова». Американский учёный . 101 (2): 92–96. дои : 10.1511/2013.101.92.
4. Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в вероятность. Американское математическое соц. стр. 464–466. ISBN 978-0-8218-0749-1 . 
5. Кендалл, генеральный директор; Бэтчелор, ГК; Бингем, Нью-Хэмпшир; Хейман, ВК; Хайланд, JME; Лоренц, Г.Г.; Моффатт, Гонконг; Парри, В.; Разборов А.А.; Робинсон, Калифорния; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 33. doi :10.1112/blms/22.1.31.
6. Солоу, Роберт (1 января 1952 г.). «О структуре линейных моделей». Эконометрика . 20 (1): 29–46. дои : 10.2307/1907805. JSTOR  1907805.
7. Ситтлер, Р. (1 декабря 1956 г.). «Системный анализ дискретных марковских процессов». IRE Транзакции по теории цепей . 3 (4): 257–266. дои : 10.1109/TCT.1956.1086324. ISSN  0096-2007.
8. Эванс, Селби (1 июля 1967 г.). «Варгус 7: Вычисленные закономерности марковских процессов». Поведенческая наука . 12 (4): 323–328. дои : 10.1002/bs.3830120407. ISSN  1099-1743.
9. Джинджерич, PD (1 января 1969 г.). «Марковский анализ циклических аллювиальных отложений». Журнал осадочных исследований . 39 (1): 330–332. Бибкод : 1969JSedR..39..330G. дои : 10.1306/74d71c4e-2b21-11d7-8648000102c1865d. ISSN  1527-1404.
10. Крумбейн, WC; Дейси, Майкл Ф. (1 марта 1969 г.). «Цепи Маркова и встроенные цепи Маркова в геологии». Журнал Международной ассоциации математической геологии . 1 (1): 79–96. дои : 10.1007/BF02047072. ISSN  0020-5958.
11. Вулф, Гарри Б. (1 мая 1967 г.). «Модели кондиционирования старения жилых построек». Журнал Американского института планировщиков . 33 (3): 192–196. дои : 10.1080/01944366708977915. ISSN  0002-8991.
12. Кренк, С. (ноябрь 1989 г.). «Марковская матрица для моделирования усталостных нагрузок и оценки диапазона дождевых осадков». Структурная безопасность . 6 (2–4): 247–258. дои : 10.1016/0167-4730(89)90025-8.
13. Бек, Дж. Роберт; Паукер, Стивен Г. (1 декабря 1983 г.). «Марковский процесс в медицинском прогнозе». Принятие медицинских решений . 3 (4): 419–458. дои : 10.1177/0272989X8300300403. ISSN  0272-989X. ПМИД  6668990.
14. Гоц, Гленн А.; МакКолл, Джон Дж. (1 марта 1983 г.). «Последовательный анализ решения об пребывании/отпуске: офицеры ВВС США». Наука управления . 29 (3): 335–351. дои : 10.1287/mnsc.29.3.335. ISSN  0025-1909.
15. Камусоко, Мужество; Ания, Масаму; Ади, Бонго; Манджоро, Муньярадзи (1 июля 2009 г.). «Устойчивость сельских районов под угрозой в Зимбабве - Моделирование будущих изменений землепользования / покрова в районе Биндура на основе модели марково-клеточных автоматов». Прикладная география . 29 (3): 435–447. doi :10.1016/j.apgeog.2008.10.002.