Все формулы РФ

Математика / Вероятность и статистика

Фундаментальная матрица поглощения и среднее число шагов

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

Опубликовано: Обновлено:

Распределения, матожиданиеЛинейная алгебраСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$N=(I-Q)^{-1}=\sum_{n=0}^{\infty}Q^n,\qquad t=N\mathbf1$$
Схема Посещения и первый шаг
Посещения и первый шаг12погл.1/41/21/4петля 1/2петля 1/2t₁=1+t₁/2+t₂/4=3; t₂=2

Из 1: петля 1/2, переход к 2 с 1/4, поглощение с 1/4. Из 2: петля 1/2 и поглощение с 1/2.

Обозначения

$Q$
блок переходов между переходными состояниями, безразмерная
$Nᵢⱼ$
ожидаемое число посещений j при старте i, безразмерная
$I$
единичная матрица размерности Q, безразмерная
$tᵢ$
ожидаемое число шагов до поглощения при старте i, шаг
$1$
столбец единиц, безразмерная

Условия применения

Состояния конечной цепи разделены на переходные и поглощающие; из каждого переходного состояния поглощение происходит с вероятностью 1. Тогда спектральный радиус Q меньше 1 и I−Q обратима. Начальный момент n=0 включается в счёт посещений переходных состояний.

Ограничения

Полную матрицу P нельзя подставлять вместо Q: из-за поглощающих строк I−P вырождена. Если существует замкнутый непоглощающий класс среди выбранных состояний, среднее время может быть бесконечным. Посещения измеряются в дискретных шагах, а не в секундах без отдельной временной модели.

Подробное объяснение

Элемент(Qⁿ)ᵢⱼ — вероятность после n переходов находиться в j, ещё не покинув переходную часть. Ожидаемое число посещений j равно сумме вероятностей всех таких моментов. Поэтому N=I+Q+Q²+…; член I учитывает стартовый визит в собственное состояние при n=0.

Геометрический ряд матриц сходится при ρ(Q)<1. Умножение на I−Q телескопически оставляет I, откуда N=(I−Q)⁻¹. Численно обычно удобнее решать линейные системы, чем вычислять обратную матрицу явно, особенно если требуется только среднее время t.

Каждый момент до поглощения приходится ровно на одно переходное состояние. Сумма ожидаемых посещений всех временных состояний поэтому равна числу сделанных шагов до первого поглощения: t=N1. То же равенство следует из первого шага t=1+Qt, то есть(I−Q)t=1.

Число Nᵢⱼ может превышать 1: повторные визиты не запрещены. Оно не является вероятностью события «когда-нибудь посетить j». Аналогично конечность среднего времени не превращает его в гарантированный срок: отдельная траектория может оказаться намного длиннее среднего.

Как пользоваться формулой

  1. Переставьте состояния так, чтобы временные узлы шли отдельным блоком; выпишите Q без переходов к поглощающим состояниям.
  2. Убедитесь, что из каждой временной части есть путь к поглощению и не осталось замкнутого непоглощающего класса внутри Q.
  3. Для полной N решите(I−Q)N=I; для одного среднего времени достаточно системы(I−Q)t=1 с правой частью из единиц.
  4. Подставьте результат в уравнение первого шага и объясните единицы: ожидаемые посещения и число переходов, а не вероятность финала.

Историческая справка

Теория поглощающих цепей переводит вопросы о случайной длительности в линейные уравнения. Название «фундаментальная матрица» относится к тому, что одна матрица ожидаемых посещений позволяет получить несколько характеристик процесса: длительности, исходы и награды за пребывание в состояниях.

Классическое изложение Kemeny и Snell «Finite Markov Chains» первоначально опубликовано в 1960 году; переиздание Springer1976 года содержит приложение об обобщении фундаментальной матрицы. Эта библиографическая история подтверждает роль понятия в систематической матричной теории, а не указывает единственную дату изобретения каждого следствия.

В разделе 11.2 Grinstead и Snell поглощающая цепь разбирается через переходный блок Q и сумму матричного геометрического ряда. Современный численный расчёт часто решает систему с I−Q напрямую. При этом смысл каждого элемента остаётся ожидаемым числом посещений с учётом начального момента.

Историческая линия формулы

Фундаментальная матрица относится к матричной теории конечных цепей, подробно изложенной Kemeny и Snell. Приведённая формула выводится из суммы вероятностей визитов; она не объявляется новым авторским законом или единоличным открытием по одному учебному источнику.

Пример

Возьмём Q=((1/2,1/4),(0,1/2)). Недостающие суммы строк 1/4 и 1/2 ведут к поглощению. I−Q=((1/2,−1/4),(0,1/2)); обратная матрица N=((2,1),(0,2)). Проверка произведением даёт единичную матрицу: первый внедиагональный элемент(1/2)·1−(1/4)·2=0. Суммы строк равны t=(3,2). Из первого временного состояния ожидаются 2 посещения самого себя и 1 посещение второго, всего 3 шага до поглощения. Независимая проверка: t₂=1+(1/2)t₂ даёт 2; t₁=1+(1/2)t₁+(1/4)·2 даёт 3. Нулевой элемент N₂₁ показывает невозможность вернуться из второго состояния в первое.

Частая ошибка

Не удаляйте I из ряда: стартовый визит тогда теряется. Не требуйте, чтобы суммы строк N были 1. Не обращайте I−P для полной поглощающей матрицы. Не называйте ожидаемое число посещений вероятностью; значение 2 допустимо именно как среднее количество, а не как шанс события.

Практика

Задачи с решением

Одно временное состояние

Условие. Самопереход имеет вероятность 3/4, оставшаяся 1/4 ведёт к поглощению. Найдите N и t.

Решение. Q=(3/4), N=1/(1−3/4)=4. Здесь одна строка и одно состояние, так что t=4.

Ответ. 4 посещения и 4 шага в среднем.

Детерминированная цепочка

Условие. Временные состояния 1→2→поглощение, без петель. Найдите N.

Решение. Q=((0,1),(0,0)), Q²=0. N=I+Q=((1,1),(0,1)); суммы строк 2 и 1.

Ответ. t₁=2, t₂=1 шаг.

Дополнительные источники

  • https://math.dartmouth.edu/~prob/prob/prob.pdf
  • https://link.springer.com/book/9780387901923

Связанные формулы

Математика

Вероятности конечных исходов поглощающей цепи: B=NR

$B=(I-Q)^{-1}R=NR,\qquad B=R+QB$

Матрица B показывает вероятность каждого поглощающего исхода при каждом временном старте. Она получается из фундаментальной матрицы посещений N и блока прямых выходов R; сумма каждой строки B равна 1 при неизбежном поглощении.

Математика

Распределение цепи Маркова через n шагов: матрица переходов

$p_n=p_0P^n,\qquad p_{n+1,j}=\sum_i p_{n,i}P_{ij}$

Распределение конечной однородной цепи после n шагов получается умножением начальной строки вероятностей на степень матрицы переходов. Элементы Pⁿ суммируют вероятности всех траекторий нужной длины между состояниями.

Математика

Среднее время первого возвращения: обратная стационарная доля

$T_i^+=\min\{n\ge1:X_n=i\},\qquad \mathbb E_iT_i^+=\frac1{\pi_i}$

В конечной неприводимой цепи среднее число шагов до первого возвращения в состояние i равно 1/πᵢ. Самопереход на первом шаге считается возвращением; апериодичность для этого равенства не требуется.