Матрица стохастика - Stochastic matrix

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

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

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

История

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

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

В дальнейшем стохастические матрицы были разработаны такими учеными, как Андрей Колмогоров , которые расширили свои возможности, допустив марковские процессы с непрерывным временем. К 1950-м годам в области эконометрики и теории цепей появились статьи, использующие стохастические матрицы . В 1960-х годах стохастические матрицы появились в еще более широком спектре научных работ, от поведенческой науки до геологии и планирования жилых домов . Кроме того, за эти десятилетия была проделана большая математическая работа по расширению диапазона использования и функциональности стохастической матрицы и марковских процессов в целом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Интуитивно стохастическая матрица представляет собой цепь Маркова; применение стохастической матрицы к распределению вероятностей перераспределяет вероятностную массу исходного распределения при сохранении его общей массы. Если этот процесс применяется повторно, распределение сходится к стационарному распределению для цепи Маркова.

Пример: кот и мышка

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

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

Независимо от начального состояния, кошка в конечном итоге поймает мышь (с вероятностью 1), и стационарное состояние π = (0,0,0,0,1) будет приближаться к пределу. Чтобы вычислить долгосрочное среднее или ожидаемое значение стохастической переменной , для каждого состояния и времени существует вклад в размере . Выживание можно рассматривать как двоичную переменную для состояния выживания и состояния завершения. Состояния с не вносят вклад в долгосрочное среднее значение.

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

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

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

и

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

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

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

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

использованная литература