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

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

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

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

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

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

История [ править ]

Андрей Марков в 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 т$ над конечным пространством состояний S с мощностью $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, S} \\ P_ {2, 1} & P_ {2,2} & \ dots & P_ {2, j} & \ dots & P_ {2, S} \\\ vdots & \ vdots & \ ddots & \ vdots & \ ddots & \ vdots \\ P_ {i , 1} & P_ {i, 2} & \ dots & P_ {i, j} & \ dots & P_ {i, S} \\\ vdots & \ vdots & \ ddots & \ vdots & \ ddots & \ vdots \\ P_ { S, 1} & P_ {S, 2} & \ dots & P_ {S, j} & \ dots & P_ {S, S} \\\ end {matrix}} \ right].}

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

{\ Displaystyle \ сумма _ {j = 1} ^ {S} P_ {i, j} = 1; \,}

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

Выше сумма поэлементно по каждой строке $I$ из $P$ может быть более кратко записать в виде $P 1 = 1$ , где $1$ является $S$ - мерный вектор из всех единиц. Используя это, можно видеть, что произведение двух правых стохастических матриц $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,\dots, n},$ которое также является собственным вектором- строкой матрицы вероятностей, связанной с собственным значением 1:

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

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

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

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

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

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

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

Пример: кошка и мышка [ править ]

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

Цепь Маркова , которая представляет эту игру содержит следующие пять состояний , указанных в комбинации позиций (кошки, мыши). Обратите внимание, что хотя наивное перечисление состояний перечислит 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 и, следовательно . $P$ $P_{11}=0$ $P_{12}=0$ $P_{14}=0$ $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) будет приближаться к пределу. ^[2]^{: 55–59} Для вычисления долгосрочного среднего или ожидаемого значения стохастической переменной Y для каждого состояния S _j и времени t _k есть вклад Y _{j, k} · 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} \,.

См. Также [ править ]

Матрица плотности
Дискретно-фазовое распределение
Двойная стохастическая матрица
Марковское ядро , эквивалент стохастической матрицы над непрерывным пространством состояний
Модели эволюции ДНК
Неравенство Мюрхеда
Теорема Перрона – Фробениуса
Вероятностный автомат
Матрица замещения

Ссылки [ править ]

^ Асмуссен, SR (2003). «Цепи Маркова». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная вероятность. 51 . С. 3–8. DOI : 10.1007 / 0-387-21525-5_1 . ISBN 978-0-387-00211-8.
^ a b c d e f g h i j k l Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: John Wiley & Sons. С. 9–11. ISBN 978-1-119-38755-8.
^ a b Хейс, Брайан (2013). «Первые звенья в цепи Маркова». Американский ученый . 101 (2): 92–96. DOI : 10.1511 / 2013.101.92 .
^ Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в вероятность. American Mathematical Soc. С. 464–466. ISBN 978-0-8218-0749-1 .
^ Кендалл, DG; Бэтчелор, ГК; Bingham, NH; Hayman, WK; Хайленд, JME; Lorentz, GG; Моффатт, Гонконг; Парри, W .; Разборов А.А.; Робинсон, Калифорния; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 33. DOI : 10,1112 / БЛМ / 22.1.31 .
^ Солоу, Роберт (1952-01-01). «О структуре линейных моделей». Econometrica . 20 (1): 29–46. DOI : 10.2307 / 1907805 . JSTOR 1907805 .
^ Ситтлер, Р. (1956-12-01). «Системный анализ дискретных марковских процессов». Сделки IRE по теории цепей . 3 (4): 257–266. DOI : 10.1109 / TCT.1956.1086324 . ISSN 0096-2007 .
^ Эванс, Селби (1967-07-01). «Варгус 7: Вычисленные паттерны из марковских процессов». Поведенческая наука . 12 (4): 323–328. DOI : 10.1002 / bs.3830120407 . ISSN 1099-1743 .
^ Gingerich, PD (1969-01-01). «Марковский анализ циклических аллювиальных отложений». Журнал осадочных исследований . 39 (1): 330–332. Bibcode : 1969JSedR..39..330G . DOI : 10,1306 / 74d71c4e-2b21-11d7-8648000102c1865d . ISSN 1527-1404 .
^ Крамбейн, WC; Дейси, Майкл Ф. (1969-03-01). «Цепи Маркова и вложенные цепи Маркова в геологии». Журнал Международной ассоциации математической геологии . 1 (1): 79–96. DOI : 10.1007 / BF02047072 . ISSN 0020-5958 .
^ Вулф, Гарри Б. (1967-05-01). «Модели кондиционирования старения жилых конструкций». Журнал Американского института проектировщиков . 33 (3): 192–196. DOI : 10.1080 / 01944366708977915 . ISSN 0002-8991 .
^ Кренк, С. (ноябрь 1989 г.). «Марковская матрица для моделирования усталостной нагрузки и оценки диапазона дождевых потоков». Структурная безопасность . 6 (2–4): 247–258. DOI : 10.1016 / 0167-4730 (89) 90025-8 .
^ Бек, Дж Роберт; Паукер, Стивен Г. (1983-12-01). «Марковский процесс в медицинском прогнозе». Принятие медицинских решений . 3 (4): 419–458. DOI : 10.1177 / 0272989X8300300403 . ISSN 0272-989X . PMID 6668990 .
^ Gotz, Glenn A .; Макколл, Джон Дж. (1983-03-01). «Последовательный анализ решения о пребывании / отпуске: офицеры ВВС США». Наука управления . 29 (3): 335–351. DOI : 10.1287 / mnsc.29.3.335 . ISSN 0025-1909 .
^ Камусоко, Мужество; Ания, Масаму; Ади, Бонго; Манджоро, Мунярадзи (01.07.2009). «Устойчивость сельских районов под угрозой в Зимбабве - Моделирование будущих изменений землепользования / растительного покрова в районе Биндура на основе модели марковско-клеточных автоматов». Прикладная география . 29 (3): 435–447. DOI : 10.1016 / j.apgeog.2008.10.002 .

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

[Gagniuc2017-2] ^ a b c d e f g h i j k l Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: John Wiley & Sons. С. 9–11. ISBN 978-1-119-38755-8.

[:0-3] Хейс, Брайан (2013). «Первые звенья в цепи Маркова». Американский ученый . 101 (2): 92–96. DOI : 10.1511 / 2013.101.92 .

[4] Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в вероятность. American Mathematical Soc. С. 464–466. ISBN 978-0-8218-0749-1 .

[5] Кендалл, DG; Бэтчелор, ГК; Bingham, NH; Hayman, WK; Хайленд, JME; Lorentz, GG; Моффатт, Гонконг; Парри, W .; Разборов А.А.; Робинсон, Калифорния; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 33. DOI : 10,1112 / БЛМ / 22.1.31 .

[6] Солоу, Роберт (1952-01-01). «О структуре линейных моделей». Econometrica . 20 (1): 29–46. DOI : 10.2307 / 1907805 . JSTOR 1907805 .

[7] Ситтлер, Р. (1956-12-01). «Системный анализ дискретных марковских процессов». Сделки IRE по теории цепей . 3 (4): 257–266. DOI : 10.1109 / TCT.1956.1086324 . ISSN 0096-2007 .

[8] Эванс, Селби (1967-07-01). «Варгус 7: Вычисленные паттерны из марковских процессов». Поведенческая наука . 12 (4): 323–328. DOI : 10.1002 / bs.3830120407 . ISSN 1099-1743 .

[9] Gingerich, PD (1969-01-01). «Марковский анализ циклических аллювиальных отложений». Журнал осадочных исследований . 39 (1): 330–332. Bibcode : 1969JSedR..39..330G . DOI : 10,1306 / 74d71c4e-2b21-11d7-8648000102c1865d . ISSN 1527-1404 .

[10] Крамбейн, WC; Дейси, Майкл Ф. (1969-03-01). «Цепи Маркова и вложенные цепи Маркова в геологии». Журнал Международной ассоциации математической геологии . 1 (1): 79–96. DOI : 10.1007 / BF02047072 . ISSN 0020-5958 .

[11] Вулф, Гарри Б. (1967-05-01). «Модели кондиционирования старения жилых конструкций». Журнал Американского института проектировщиков . 33 (3): 192–196. DOI : 10.1080 / 01944366708977915 . ISSN 0002-8991 .

[12] Кренк, С. (ноябрь 1989 г.). «Марковская матрица для моделирования усталостной нагрузки и оценки диапазона дождевых потоков». Структурная безопасность . 6 (2–4): 247–258. DOI : 10.1016 / 0167-4730 (89) 90025-8 .

[13] Бек, Дж Роберт; Паукер, Стивен Г. (1983-12-01). «Марковский процесс в медицинском прогнозе». Принятие медицинских решений . 3 (4): 419–458. DOI : 10.1177 / 0272989X8300300403 . ISSN 0272-989X . PMID 6668990 .

[14] Gotz, Glenn A .; Макколл, Джон Дж. (1983-03-01). «Последовательный анализ решения о пребывании / отпуске: офицеры ВВС США». Наука управления . 29 (3): 335–351. DOI : 10.1287 / mnsc.29.3.335 . ISSN 0025-1909 .

[15] Камусоко, Мужество; Ания, Масаму; Ади, Бонго; Манджоро, Мунярадзи (01.07.2009). «Устойчивость сельских районов под угрозой в Зимбабве - Моделирование будущих изменений землепользования / растительного покрова в районе Биндура на основе модели марковско-клеточных автоматов». Прикладная география . 29 (3): 435–447. DOI : 10.1016 / j.apgeog.2008.10.002 .

[1]