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

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

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

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

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

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

В том же ключе можно определить вектор вероятности как вектор , элементы которого являются неотрицательными действительными числами, сумма которых равна 1. Таким образом, каждая строка правой стохастической матрицы (или столбец левой стохастической матрицы) является вектором вероятности. Правые стохастические матрицы действуют на векторы-строки вероятностей путем умножения справа, а левые стохастические матрицы действуют на векторы-столбцы вероятностей путем умножения слева. В этой статье мы придерживаемся предыдущего соглашения. Кроме того, субстохастическая матрица является действительной квадратной матрицей, все суммы строк которой равны ${\displaystyle \leq 1.}$

История

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

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

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

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

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

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

Если вероятность перехода от i к j за один временной шаг равна Pr( j | i ) = P _{i , j} , то стохастическая матрица P задается путем использования P _{i , 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;\,}$

таким образом, эта матрица является правой стохастической матрицей.

Вышеуказанная поэлементная сумма по каждой строке 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] : 14–17  [16] : 116}

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

Пример: Кошки-мышки

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

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

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

Мы используем стохастическую матрицу (ниже) для представления вероятностей перехода этой системы (строки и столбцы в этой матрице индексируются возможными состояниями, перечисленными выше, причем состояние до перехода является строкой, а состояние после перехода — столбцом). Например, начиная с состояния 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) приближается к пределу. Чтобы вычислить долгосрочное среднее или ожидаемое значение стохастической переменной , для каждого состояния и времени есть вклад . Выживание можно рассматривать как бинарную переменную с для выжившего состояния и для завершенного состояния. Состояния с не вносят вклад в долгосрочное среднее. ${\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. Asmussen, SR (2003). «Цепи Маркова». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная вероятность. Том 51. С. 3–8. doi :10.1007/0-387-21525-5_1. ISBN 978-0-387-00211-8.
2. Лоулер, Грегори Ф. (2006). Введение в стохастические процессы (2-е изд.). CRC Press. ISBN 1-58488-651-X.
3. Hayes, Brian (2013). «Первые звенья в цепи Маркова». American Scientist . 101 (2): 92–96. doi :10.1511/2013.101.92.
4. Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в теорию вероятностей. Американское математическое общество. стр. 464–466. ISBN 978-0-8218-0749-1 . 
5. Кендалл, Д. Г.; Бэтчелор, Г. К.; Бингем, Н. Х.; Хейман, В. К.; Хайленд, Дж. М. Э.; Лоренц, Г. Г.; Моффат, Х. К.; Парри, В.; Разборов, А. А.; Робинсон, К. А.; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 33. doi :10.1112/blms/22.1.31.
6. Солоу, Роберт (1 января 1952 г.). «О структуре линейных моделей». Econometrica . 20 (1): 29–46. doi :10.2307/1907805. JSTOR  1907805.
7. Ситтлер, Р. (1 декабря 1956 г.). «Системный анализ дискретных марковских процессов». Труды IRE по теории цепей . 3 (4): 257–266. doi :10.1109/TCT.1956.1086324. ISSN  0096-2007.
8. Эванс, Селби (1 июля 1967 г.). «Vargus 7: Вычисляемые закономерности из марковских процессов». Behavioral Science . 12 (4): 323–328. doi :10.1002/bs.3830120407. ISSN  1099-1743.
9. Gingerich, PD (1 января 1969). «Марковский анализ циклических аллювиальных осадков». Journal of Sedimentary Research . 39 (1): 330–332. Bibcode : 1969JSedR..39..330G. doi : 10.1306/74d71c4e-2b21-11d7-8648000102c1865d. ISSN  1527-1404.
10. Krumbein, WC; Dacey, Michael F. (1 марта 1969 г.). «Цепи Маркова и вложенные цепи Маркова в геологии». Журнал Международной ассоциации математической геологии . 1 (1): 79–96. doi :10.1007/BF02047072. ISSN  0020-5958.
11. Вулф, Гарри Б. (1 мая 1967 г.). «Модели кондиционирования старения жилых зданий». Журнал Американского института планировщиков . 33 (3): 192–196. doi :10.1080/01944366708977915. ISSN  0002-8991.
12. Кренк, С. (ноябрь 1989 г.). «Марковская матрица для моделирования усталостной нагрузки и оценки диапазона дождевого потока». Structural Safety . 6 (2–4): 247–258. doi :10.1016/0167-4730(89)90025-8.
13. Бек, Дж. Роберт; Паукер, Стивен Г. (1 декабря 1983 г.). «Процесс Маркова в медицинском прогнозировании». Принятие медицинских решений . 3 (4): 419–458. doi :10.1177/0272989X8300300403. ISSN  0272-989X. PMID  6668990.
14. Гетц, Гленн А.; Макколл, Джон Дж. (1 марта 1983 г.). «Последовательный анализ решения о пребывании/отпуске: офицеры ВВС США». Management Science . 29 (3): 335–351. doi :10.1287/mnsc.29.3.335. ISSN  0025-1909.
15. Камусоко, Мужество; Ания, Масаму; Ади, Бонго; Манджоро, Муньярадзи (1 июля 2009 г.). «Устойчивость сельских районов под угрозой в Зимбабве - Моделирование будущих изменений землепользования / покрова в районе Биндура на основе модели марковских клеточных автоматов». Прикладная география . 29 (3): 435–447. doi :10.1016/j.apgeog.2008.10.002.
16. Кардар, Мехран (2007). Статистическая физика полей . Cambridge University Press . ISBN 978-0-521-87341-3. OCLC  920137477.