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

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

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

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

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

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

История

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

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

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

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

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

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

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,

\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 к$ правой стохастической матрицы $P$ также является правостохастической. Тогда вероятность перехода от $i$ к $j$ за два шага определяется $(i, j)$ -м элементом квадрата $P$ :

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

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

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

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

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

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

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

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

\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).

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

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) рассматривается как предел. Чтобы вычислить долгосрочное среднее или ожидаемое значение стохастической переменной. $Y$ , для каждого штата $S_{j}$ и время $t_{k}$ есть вклад $Y_{j,k}\cdot P(S=S_{j},t=t_{k})$ . Выживание можно рассматривать как двоичную переменную с $Y=1$ за выживающее государство и $Y=0$ для прекращенного состояния. Государства с $Y=0$ не вносят вклад в долгосрочный средний показатель.

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

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

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

{\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}},

и

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

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

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

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

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

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

См. также

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

Ссылки

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

[1] Асмуссен, СР (2003). «Цепи Маркова». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная теория вероятности. Том. 51. С. 3–8. дои : 10.1007/0-387-21525-5_1 . ISBN 978-0-387-00211-8 .

[:1-2] Jump up to: ^а ^б Лоулер, Грегори Ф. (2006). Введение в случайные процессы (2-е изд.). ЦРК Пресс. ISBN 1-58488-651-Х .

[:0-3] Jump up to: ^а ^б Хейс, Брайан (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] Джинджерич, П.Д. (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. дои : 10.1016/j.apgeog.2008.10.002 .

[Kardar2007-16] Кардар, Мехран (2007). Статистическая физика полей . Издательство Кембриджского университета . ISBN 978-0-521-87341-3 . OCLC 920137477 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v т и Матричные классы
Явно ограниченные записи	Чередование Антидиагональ антиэрмитовский Антисимметричный наконечник стрелы Группа двуугольный Бисимметричный Блок-диагональ Блокировать Блок трехдиагональный логическое значение Коши Центросимметричный Конференция Комплекс Адамара Сопозитивный Диагональная доминанта Диагональ Дискретное преобразование Фурье элементарный Эквивалент Фробениус Обобщенная перестановка Адамар Приобретение эрмитовский Хессенберг Пустой Целое число Логический Матричный блок Мецлер Мур Неотрицательный Пятиугольный перестановка Персимметричный Полиномиальный кватернионный Подпись косо-эрмитовский Кососимметричный Горизонт Редкий Сильвестр Симметричный Тёплиц Треугольный Трехдиагональный Вандермонде Уолш С
Постоянный	Обмен Гильберт Личность Лемер Из них Паскаль Паули Редхеффер Сдвиг Ноль
Условия на собственные значения или собственные векторы	Компаньон Конвергентный Дефектный Определенный Диагонализуемый Гурвиц Положительно-определенный Стилтьес
Выполнение условий на изделия или инверсы	Конгруэнтный Идемпотент или проекция Обратимый Инволютивный Нильпотентный Нормальный Ортогональный Унимодульный Одномогущий Унитарный Полностью унимодульный Взвешивание
С конкретными приложениями	Адъюгат знак чередования Дополненный Безу Карл Великий Картан циркулирующий Кофактор коммутация Путаница Коксетер Расстояние Дублирование и устранение Евклидово расстояние Фундаментальное (линейное дифференциальное уравнение) Генератор Грамм Гессен Домохозяин якобиан Момент Расплачиваться Выбирать Случайный Вращение Зейферт сдвиг Сходство симплектический Полностью позитивный Трансформация
Используется в статистике	Центрирование Корреляция Ковариация Дизайн Двойной стохастический Информация о Фишере Имеет Точность Стохастический Переход
Используется в теории графов	Смежность Бисмежность Степень Эдмондс Заболеваемость лапласиан Соседство Зайделя Все
Используется в науке и технике	Кабиббо – Кобаяши – Маскава Плотность Фундаментальный (компьютерное зрение) Нечеткая ассоциативность Гамма Гелл-Манн гамильтониан Нерегулярный Перекрывать С Государственный переход Замена З (химия)
Связанные термины	Джордан в нормальной форме Линейная независимость Матричная экспонента Матричное представление конических сечений Идеальная матрица Псевдообратный Форма эшелона строк Вронскиан
Математический портал Список матриц Категория:Матрицы