Матрица стохастика - Википедия - Stochastic matrix

В математика, а стохастическая матрица это квадратная матрица используется для описания переходов Цепь Маркова. Каждая из его записей представляет собой неотрицательный настоящий номер представляющий вероятность.[1][2]:9–11 Его также называют матрица вероятностей, матрица перехода, матрица замещения, или же Матрица Маркова.[2]:9–11

Стохастическая матрица была впервые разработана Андрей Марков в начале 20 век, и нашла применение в самых разных областях науки, включая теория вероятности, статистика, математические финансы и линейная алгебра, а также Информатика и популяционная генетика.[2]:1–8

Существует несколько различных определений и типов стохастических матриц:[2]:9–11

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

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

Распространенным условием в англоязычной математической литературе является использование векторы-строки вероятностей и правых стохастических матриц, а не вектор-столбец вероятностей и левых стохастических матриц; эта статья следует этому соглашению.[2]:1–8

История

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

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

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

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

Стохастическая матрица описывает Цепь Маркова Икст через конечный пространство состояний S с мощность S.

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

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

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

Приведенная выше поэлементная сумма по каждой строке я из п можно более кратко записать как п1 = 1, куда 1 это S-мерный вектор всех единиц. Используя это, можно увидеть, что произведение двух правых стохастических матриц п и п′′ также является правым стохастиком: пп′′ 1 = п′ (п′′ 1) = п1 = 1. В целом k-я степень пk правой стохастической матрицы п также является правым стохастическим. Вероятность перехода с я к j в два этапа затем дается (я, j)-й элемент квадрата п:

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

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

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

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

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

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

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

Интуитивно стохастическая матрица представляет собой цепь Маркова; применение стохастической матрицы к распределению вероятностей перераспределяет вероятностную массу исходного распределения при сохранении его общей массы. Если этот процесс применяется неоднократно, распределение сходится к стационарному распределению для цепи Маркова.[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, и поэтому .

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

Независимо от начального состояния, кошка в конечном итоге поймает мышь (с вероятностью 1) и установит стационарное состояние π = (0,0,0,0,1) приближается к пределу.[2]:55–59 Для вычисления долгосрочного среднего или ожидаемого значения стохастической переменной Y для каждого состояния Sj и время tk есть вклад Yj, k· P (S = Sj, t = tk). Выживание можно рассматривать как двоичную переменную с Y = 1 для выжившего состояния и Y = 0 для завершенного состояния. Состояния с Y = 0 не вносят вклад в долгосрочное среднее.

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

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

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

и

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

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

Моменты высшего порядка даются

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

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

  1. ^ Асмуссен, С. Р. (2003). «Цепи Маркова». Прикладная вероятность и очереди. Стохастическое моделирование и прикладная вероятность. 51. С. 3–8. Дои:10.1007/0-387-21525-5_1. ISBN  978-0-387-00211-8.
  2. ^ а б c d е ж грамм час я j k л Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 9–11. ISBN  978-1-119-38755-8.
  3. ^ а б Хейс, Брайан (2013). «Первые звенья в цепи Маркова». Американский ученый. 101 (2): 92–96. Дои:10.1511/2013.101.92.
  4. ^ Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в вероятность. American Mathematical Soc. С. 464–466. ISBN  978-0-8218-0749-1.
  5. ^ Kendall, D.G .; Бэтчелор, Г. К .; Bingham, N.H .; Hayman, W. K .; Hyland, J.M.E .; Lorentz, G.G .; Moffatt, H.K .; Парри, W .; Разборов, А. А .; Robinson, C.A .; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества. 22 (1): 33. Дои:10.1112 / blms / 22.1.31.
  6. ^ Солоу, Роберт (1952-01-01). «О структуре линейных моделей». Econometrica. 20 (1): 29–46. Дои:10.2307/1907805. JSTOR  1907805.
  7. ^ Ситтлер, Р. (1956-12-01). «Системный анализ дискретных марковских процессов». IRE-транзакции по теории цепей. 3 (4): 257–266. Дои:10.1109 / TCT.1956.1086324. ISSN  0096-2007.
  8. ^ Эванс, Селби (1967-07-01). «Варгус 7: Вычисленные паттерны из марковских процессов». Поведенческая наука. 12 (4): 323–328. Дои:10.1002 / bs.3830120407. ISSN  1099-1743.
  9. ^ Гингерич, П. Д. (1969-01-01). «Марковский анализ циклических аллювиальных отложений». Журнал осадочных исследований. 39 (1): 330–332. Bibcode:1969JSedR..39..330G. Дои:10.1306 / 74d71c4e-2b21-11d7-8648000102c1865d. ISSN  1527-1404.
  10. ^ Krumbein, W. C .; Дейси, Майкл Ф. (1969-03-01). «Цепи Маркова и вложенные цепи Маркова в геологии». Журнал Международной ассоциации математической геологии. 1 (1): 79–96. Дои:10.1007 / BF02047072. ISSN  0020-5958.
  11. ^ Вулф, Гарри Б. (1967-05-01). «Модели кондиционирования старения жилых конструкций». Журнал Американского института проектировщиков. 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. ^ Бек, Дж Роберт; Паукер, Стивен Г. (1983-12-01). «Марковский процесс в медицинском прогнозе». Принятие медицинских решений. 3 (4): 419–458. Дои:10.1177 / 0272989X8300300403. ISSN  0272-989X. PMID  6668990.
  14. ^ Gotz, Glenn A .; Макколл, Джон Дж. (1983-03-01). «Последовательный анализ решения о пребывании / отпуске: офицеры ВВС США». Наука управления. 29 (3): 335–351. Дои:10.1287 / mnsc.29.3.335. ISSN  0025-1909.
  15. ^ Камусоко, Мужество; Ания, Масаму; Ади, Бонго; Манджоро, Мунярадзи (01.07.2009). «Устойчивость сельских районов под угрозой в Зимбабве - Моделирование будущих изменений землепользования / растительного покрова в районе Биндура на основе модели марковско-клеточных автоматов». Прикладная география. 29 (3): 435–447. Дои:10.1016 / j.apgeog.2008.10.002.