Вероятность и статистика · объяснение и практика
Как таблица переходов задаёт следующий закон состояния
Как читать направления в таблице переходов, проверять сумму каждой строки и получать закон следующего состояния из смешанного начального распределения.

В теме Случайные процессы и имитация: углубление · Учебная карта
В маршруте Состояния и случайные процессы · 10 тем
Главная мысль
Если строка i содержит вероятности перехода из i, закон следующего шага равен строковому вектору πP. Перед умножением проверяют неотрицательность элементов и единичные суммы строк.
Таблица описывает условие, а не готовый общий закон
Рассмотрим учебный автомат с состояниями А и Б. Из А он остаётся в А с вероятностью 0,8, а из Б переходит в А с вероятностью 0,3. Полная матрица имеет строки (0,8;0,2) и (0,3;0,7). Номер строки задаёт текущее состояние, номер столбца — следующее. Это соглашение необходимо объявить до вычислений.
Каждая строка описывает все возможности при одном фиксированном условии. Поэтому её элементы неотрицательны и складываются в единицу. Столбцы складываться в единицу не обязаны: здесь их суммы равны 1,1 и 0,9. Это не ошибка таблицы, поскольку разные строки относятся к разным исходным условиям, а не к несовместимым исходам одного опыта.
Смешиваем строки с весами текущего состояния
Пусть в начале вероятность А равна 0,4, Б — 0,6. Для следующего А возможны два несовместимых пути: стартовать в А и остаться либо стартовать в Б и перейти. Их вероятности равны 0,4·0,8 и 0,6·0,3. Складывая их, получаем 0,5. Аналогично для Б выходит 0,4·0,2+0,6·0,7=0,5.
Это взвешенное среднее строк, поэтому итог снова является распределением. Простое среднее строк подошло бы только при равных начальных весах. Выбор одной строки допустим, когда начальное состояние известно точно. Умножение матрицы на столбец начальных вероятностей без транспонирования описывает другое соглашение и здесь даст неверный расчёт.
Пример
Начальное состояние автомата точно Б. Каков закон через один шаг?
Берём строку Б целиком: (0,3;0,7). Никакого усреднения со строкой А нет: вероятность начального А равна нулю.
Когда такой переход можно повторять
Одной таблицы достаточно для всех шагов однородной марковской модели: при известном текущем состоянии дополнительная история не меняет следующий закон. Это предположение модели, а не следствие любого наблюдения последовательности. Например, если скрытый режим автомата меняет вероятности после длительного простоя, состояния А и Б могут оказаться недостаточным описанием.
Если таблица зависит от номера шага, используют соответствующую матрицу для каждого момента. Если однородность принята, вычисленный вектор становится начальным для следующего умножения. Полезная проверка результата — диапазон от нуля до единицы и общая сумма один. Однако эти свойства сами по себе ещё не доказывают правильность выбранного направления переходов.
От чтения к действию
А теперь — вы
Частые вопросы
Почему суммы столбцов здесь не равны единице?
Условие фиксируется строкой. Для каждого исходного состояния нормируются именно вероятности всех выходов из него.
Что изменится при записи распределений столбцами?
Для тех же вероятностей понадобится транспонированная матрица: новый столбец равен Pᵀπ. Смешивать два соглашения нельзя.
Углублённый разбор
Коэффициент Добрушина: потеря памяти об исходном распределении
Коэффициент сжатия связывает различие начальных законов с различием после перехода. Он оценивает забывание старта без решения стационарной системы.
Перед началом: Условная вероятность и математическое ожидание; Стохастические матрицы и стационарный закон.
Определение и постановка
Для стохастической матрицы P положим δ(P)=maxᵢⱼ ½Σₖ|Pᵢₖ−Pⱼₖ|. Это наибольшее расстояние полной вариации между двумя строками. Полная вариация двух законов равна максимальному расхождению вероятностей одного события; на конечном множестве она совпадает с половиной суммы модулей разностей координат.
Вывод и вычислительный критерий
Любой начальный закон образует выпуклую смесь строк P. Разность двух таких смесей ограничивается диаметром множества строк, причём TV(μP,νP)≤δ(P)TV(μ,ν). Последовательное применение даёт множитель δ(P)ⁿ для n одинаковых шагов.
В двух состояниях достаточно сравнить первые координаты строк: вторые разности противоположны и удваивают ту же абсолютную величину. Поэтому вычисление коэффициента не требует находить собственные векторы. Положительное перекрытие строк позволяет сопрячь часть переходов в одно состояние.
Условия и границы вывода
Условие δ(P)<1 достаточно для геометрического сжатия, но не необходимо для сходимости. У некоторой степени P коэффициент может оказаться меньше единицы, хотя у самой P он равен единице. Для неоднородной цепи используются произведения коэффициентов отдельных матриц.
Граница относится к различию распределений, а не к расстоянию между названиями состояний. Переименование A и B не меняет результата; произвольное числовое кодирование состояний также не должно появляться в формуле.
Перекрытие двух строк можно вычислить без модулей: сумма минимумов равна единице минус их полной вариации. Для строк примера общая масса равна половине. Это означает, что половину следующего шага удаётся организовать одинаково при любых двух исходных состояниях. Остаточная половина несёт всю память о старте. Повторение конструкции оставляет после трёх шагов не более одной восьмой несовпавших запусков. В более длинной цепи максимальную пару строк надо искать среди всех состояний; проверка только соседних имён не даёт общей гарантии. Если одна пара строк имеет непересекающиеся носители, коэффициент одного шага равен единице, хотя остальные пары могут перекрываться почти полностью.
Разобранная задача
Условие. Строки P равны (3/4,1/4) и (1/4,3/4). Сравните старты A и B через три перехода и найдите точную полную вариацию.
- Расстояние строк равно (|3/4−1/4|+|1/4−3/4|)/2=1/2; это коэффициент δ.
- Для разности вероятностей A имеем рекурсию dₙ₊₁=(1/2)dₙ с начальным d₀=1.
- Последовательные различия равны 1/2, 1/4 и 1/8; оба закона нормированы.
- Симметрия даёт законы (9/16,7/16) и (7/16,9/16); половина суммы их различий равна 1/8.
Ответ. Через три шага TV=1/8; оценка δ³ достигается точно.
Проверка. Независимое возведение матрицы в третью степень даёт строки (9/16,7/16) и (7/16,9/16). Их перекрывающаяся масса равна 7/8, дополнение равно 1/8.
Где легко ошибиться. Сумма модулей без множителя 1/2 вдвое завышает полную вариацию и может дать число больше единицы.
Проверьте понимание
Вопросы к этой главе
Обязательно ли сжатие строгое за один шаг?
Нет. Достаточно, чтобы оно стало строгим после нескольких шагов. Проверка степени матрицы обнаруживает перекрытие, возникающее через промежуточные состояния.
Доказывает ли малое TV совпадение траекторий?
Нет. Оно ограничивает вероятности событий в фиксированный момент. Совместную конструкцию траекторий надо задавать отдельно; она не определяется двумя маргинальными законами.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sébastien Roch: сопряжение и смешивание, Chapter 4
PDF с извлечённым текстом: §4.1 и §4.3, неравенство сопряжения, сохранение маргиналей и оценка смешивания; упражнение4.17 определяет транспортную стоимость.
Марковское вознаграждение: накопленный результат за конечный срок
Накопленное вознаграждение требует сложить результаты по всем датам. Награда в конечном состоянии учитывает только один момент наблюдения.
Перед началом: Условная вероятность и математическое ожидание; Стохастические матрицы и стационарный закон.
Определение и постановка
Пусть r(i) есть награда за состояние i перед очередным переходом. За n тактов сумма равна Σₜ₌₀ⁿ⁻¹r(Xₜ). Выбор начала счёта существенен: при начислении после перехода набор дат сдвигается на единицу.
Вывод и вычислительный критерий
Обозначим vₙ(i) ожидаемой суммой из i. Уравнение первого шага имеет вид vₙ=r+Pvₙ₋₁ при v₀=0. Раскрывая рекурсию, получаем r+Pr+…+Pⁿ⁻¹r. Здесь награды образуют столбец, хотя распределения записываются строками.
Линейность ожидания не требует независимости наград в разные даты. Зависимость состояний уже учтена законами μPᵗ. Если награда зависит от перехода i→j, сначала усредняют её по строке: r̃(i)=ΣⱼPᵢⱼg(i,j).
Условия и границы вывода
Ожидаемая сумма может расти неограниченно даже при существовании стационарного распределения. Для средней награды изучают сумму, делённую на n; для дисконтированной — вводят множитель βᵗ при 0≤β<1. Это разные показатели.
Награда способна быть отрицательной, хотя вероятности переходов обязаны оставаться неотрицательными. Проверять сумму наград на равенство единице бессмысленно: её размерность задаётся предметом задачи.
Для той же цепи можно отдельно вычислить награду после переходов. Тогда даты начисления равны один, два и три; ожидания составляют 1, половину и четверть, а сумма равна семи четвертям. Получилось ровно вдвое меньше исходного ответа, хотя матрица и число переходов совпадают. Разница вызвана потерей достоверного начального начисления и добавлением позднего начисления с малой вероятностью. Если награда начисляется за сам выход из A, её ожидаемая сумма равна вероятности успеть выйти к сроку, умноженной на фиксированную плату. Это уже другая функция перехода и не должно смешиваться с оплатой пребывания.
Разобранная задача
Условие. Матрица имеет строки (1/2,1/2),(0,1). Старт A. Награды r(A)=2, r(B)=0 начисляются перед каждым из трёх переходов. Найдите ожидаемую сумму.
- В дату ноль цепь точно в A; награда равна двум.
- Вероятность A в дату один равна 1/2, поэтому ожидаемая награда этой даты равна 1.
- Вероятность A в дату два равна 1/4; вклад третьего начисления равен 1/2.
- Суммируем три начисления: 2+1+1/2=7/2. Состояние после третьего перехода награды уже не получает.
Ответ. Ожидаемая сумма за три начисления равна 7/2.
Проверка. Прямой перебор моментов первого выхода из A даёт суммы 2,4,6 с вероятностями 1/2,1/4,1/4. Их взвешенное среднее равно 7/2.
Где легко ошибиться. Умножение ожидаемой конечной награды на число тактов неверно: распределения промежуточных состояний различаются.
Проверьте понимание
Вопросы к этой главе
Нужна ли независимость наград?
Для их математического ожидания нет. Для дисперсии суммы понадобятся ковариации наград разных дат; считать их нулевыми без основания нельзя.
Можно ли начислять за последний переход?
Можно, но тогда надо изменить объявленные даты и условие задачи. Формула должна соответствовать фактическому правилу учёта, а не привычной записи суммы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sébastien Roch: конечные цепи, Chapter 1.1
PDF с извлечённым текстом: §1.1.2, стохастические переходы, стационарность и условия сходимости; отдельные вычисления выполнены для данной главы.
Метрополис—Гастингс: поправка на несимметричное предложение
Нужен заданный стационарный закон, но доступный генератор предлагает направления с разными вероятностями. Принятие только по отношению целевых масс тогда даёт неверную цепь. Построим правильный переход вместе с вероятностью остаться на месте.
Перед началом: Конечная цепь Маркова; Условное ожидание и точные вероятности.
Предложение ещё не является итоговым переходом
Пусть целевые массы πᵢ строго положительны на конечном наборе состояний, а q — стохастическая матрица предложений. Из состояния i сначала разыгрывается кандидат j по строке qᵢ. Затем отдельное решение принимает либо отклоняет кандидата. Событие предложения перехода и событие фактической смены состояния различны.
Для i≠j с qᵢⱼ>0 задаём αᵢⱼ=min(1,πⱼqⱼᵢ/(πᵢqᵢⱼ)). Если обратное предложение невозможно, принятие такого движения равно нулю. Отсутствующее прямое предложение вообще не требует вычисления отношения: соответствующий итоговый переход нулевой. Ненормированные положительные целевые веса подходят тоже, поскольку общий множитель сокращается.
Отклонения входят в диагональ
Вне диагонали Pᵢⱼ=qᵢⱼαᵢⱼ. Диагональ определяем как единицу минус сумму этих фактических выходов. Она включает и исходное предложение остаться, и отклонённые движения. Если забыть вторую часть, строка перестанет суммироваться в единицу, а траектория перестанет описывать выбранный алгоритм.
Прямой стационарный поток по ребру равен min(πᵢqᵢⱼ,πⱼqⱼᵢ). Это симметричное выражение доказывает детальный баланс одновременно для обоих направлений. Суммирование потоков удостоверяет πP=π. Здесь баланс не проверяется случайно после подгонки: правило принятия специально построено для его выполнения.
Стационарность и качество моделирования различаются
Связность графа взаимно положительных предложений обеспечивает неприводимость итоговой цепи. Для сходимости из любого старта дополнительно нужна апериодичность; положительный самопереход в неприводимой конечной цепи достаточен. Формально правильное целевое распределение не означает быстрой потери памяти или независимости соседних выходов.
У слишком несогласованного предложения многие движения отклоняются. Поэтому доля принятий полезна для диагностики, но сама не измеряет точность среднего. Можно часто принимать очень короткие движения и медленно исследовать пространство. Проверку целевого потока следует дополнять изучением зависимости и выбранного горизонта наблюдений.
Два несимметричных предложения
Условие. Целевые массы двух состояний равны (1/3,2/3). Предложение q имеет строки (0,1) и (1/4,3/4). Постройте матрицу Метрополиса—Гастингса и проверьте целевой закон.
- Из первого состояния второе предлагается всегда. Принятие равно min(1,[(2/3)(1/4)]/[(1/3)·1])=1/2.
- Обратное предложение имеет вероятность 1/4 и принимается с вероятностью один. Значит фактические внедиагональные переходы равны 1/2 и 1/4.
- Восстанавливаем диагональ: получаем P=((1/2,1/2),(1/4,3/4)). Потоки между разными состояниями равны (1/3)(1/2)=(2/3)(1/4)=1/6.
- Если ошибочно убрать отношение предложений, принятия станут 1 и 1/2. Итоговые переходы 1 и 1/8 дадут стационарные массы (1/9,8/9), а не требуемую пару.
Ответ. Правильная матрица: ((1/2,1/2),(1/4,3/4)); целевые массы сохраняются.
Проверка. Независимая подстановка даёт первую координату πP: 1/6+1/6=1/3; вторая равна 2/3. Прямое решение двух уравнений стационарности для ошибочной матрицы подтверждает альтернативный закон (1/9,8/9).
Где легко ошибиться. Упрощение α=min(1,πⱼ/πᵢ) допустимо при симметричном предложении. В задаче q₁₂=1 и q₂₁=1/4, поэтому это упрощение нарушает поток. Нельзя компенсировать ошибку последующим нормированием строк: строки уже нормированы, неверен их стационарный закон.
Проверьте понимание
Вопросы к этой главе
Нужно ли знать нормирующую константу целевого закона?
Нет, когда известны все положительные веса с одним общим множителем: он сокращается в каждом отношении. Поддержку целевого закона и нулевые предложения всё равно требуется определить явно.
Становятся ли результаты независимыми после правильного принятия?
Нет. Алгоритм создаёт марковскую последовательность, часто с повторами текущего состояния. Детальный баланс доказывает стационарность, а независимость и погрешность среднего требуют отдельного анализа.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- University of Iowa, STAT 7400, §10.7
Прочитан авторский университетский раздел 10.7: несимметричное предложение, поправка Hastings, отклонение с сохранением состояния и симметрия потока. Числа и контрпример здесь собственные.
Скрытое состояние: прямой фильтр по последовательности наблюдений
Красный сигнал может исходить из двух скрытых режимов с разной вероятностью. После второго сигнала нельзя просто повторить первый байесовский ответ: между наблюдениями скрытый режим мог измениться. Прямой фильтр учитывает оба механизма по порядку.
Перед началом: Конечная цепь Маркова; Условное ожидание и точные вероятности.
Скрытая динамика и измерение задаются отдельно
Пусть Xₜ — конечная марковская цепь с известной матрицей P, а Yₜ — наблюдаемый сигнал. Вероятность сигнала y в состоянии j обозначим bⱼ(y). Предполагаем, что при всей траектории состояний сигналы независимы и закон текущего сигнала зависит только от текущего состояния. Без этого предположения произведение локальных вероятностей не описывает наблюдаемую последовательность.
Начальное распределение задаётся до первого сигнала. Если первый сигнал относится к X₁, начальная совместная масса равна α₁(j)=μⱼbⱼ(y₁). Важно не добавлять перед этим лишний переход, если μ уже относится к первой измеряемой дате. Другой договор времени допустим, но должен быть записан явно.
Предсказание предшествует следующему условию
Величина αₜ(j) означает совместную вероятность всех сигналов до t и последнего состояния j. Для следующей даты сначала суммируем возможные предшествующие состояния: Σᵢαₜ(i)Pᵢⱼ. Затем умножаем на bⱼ(yₜ₊₁). Внутри суммы складываются взаимоисключающие скрытые пути, поэтому максимум вместо суммы решал бы другую задачу.
Сумма всех αₜ даёт вероятность наблюдённого префикса. Нормированные значения составляют фильтрующее распределение последнего состояния при уже полученных сигналах. Это не наиболее вероятный полный путь и не сглаженный закон прошлой даты с использованием будущих измерений.
Нулевые и малые массы требуют разного обращения
Если вероятность всего наблюдаемого префикса нулевая, обычное условное распределение не определено. Если она только очень мала, полезно нормировать после каждого шага и отдельно сохранять множители нормировки. Произведение этих множителей восстанавливает правдоподобие последовательности, тогда как вектор состояний остаётся удобного масштаба.
Независимая проверка короткого примера перечисляет все скрытые пути и вычисляет массу каждого напрямую. Она обнаруживает переставленные индексы P, лишний переход до первого сигнала или ошибочное использование эмиссии предыдущего состояния. При длинной записи число путей растёт экспоненциально, а фильтр сохраняет только текущий вектор.
Два красных сигнала
Условие. Первое состояние A или B имеет вероятность 1/2. Матрица переходов равна ((3/4,1/4),(1/4,3/4)); вероятность красного сигнала равна 4/5 в A и 1/5 в B. Наблюдаются два красных сигнала на первой и второй датах. Найдите вероятность второго состояния A.
- После первого красного сигнала совместные массы равны (2/5,1/10), сумма 1/2. Условный вектор равен (4/5,1/5).
- Предсказываем вторую дату до сигнала: вероятность A равна (4/5)(3/4)+(1/5)(1/4)=13/20, вероятность B — 7/20.
- Умножаем на вероятности второго красного сигнала. Ненормированные условные массы равны 13/25 и 7/100, их сумма 59/100.
- Нормируем: вероятность A становится 52/59, B — 7/59. Полное правдоподобие двух красных равно (1/2)(59/100)=59/200.
Ответ. После обоих сигналов P(X₂=A|красный,красный)=52/59; вероятность записи сигналов равна 59/200.
Проверка. Полный список путей AA,AB,BA,BB имеет массы 48/200,4/200,4/200,3/200. Для последнего A складываются первая и третья массы, то есть 52/200; деление на общий итог даёт тот же ответ.
Где легко ошибиться. Не используйте 4/5 повторно как окончательный результат после любого количества красных сигналов. Это закон после первой даты в данной задаче. Между датами работает переходная матрица, а новое измерение снова меняет уже предсказанное распределение.
Проверьте понимание
Вопросы к этой главе
Почему сигналы не обязаны быть марковскими?
Наблюдаемый сигнал обычно не раскрывает точное скрытое состояние. Более ранние сигналы уточняют его условный состав и тем самым влияют на прогноз следующего сигнала даже при одинаковом последнем наблюдении.
Можно ли заменить суммирование наиболее вероятным путём?
Так получится максимальная масса одного пути, а не вероятность всех наблюдений. В фильтре разные допустимые предшествующие пути складываются; выбор одного пути относится к отдельной задаче декодирования.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Rabiner 1989, §III.A, equations 18–21
Вебом прочитан индексированный фрагмент первичной статьи с определением α и прямой рекурсией 18–21. Прямой PDF этого зеркала дал timeout, зеркало UBC — PDF без извлекаемого текста; весь документ не заявлен прочитанным.
Обращение времени в стационарной цепи: восстановление прошлого по настоящему
Циклический переход может сохранять равномерные массы и всё же различать прошлое и будущее. Восстановим закон предыдущего состояния по текущему, а затем проверим его на всей паре соседних дат.
Перед началом: Условная вероятность; Точная арифметика.
Какая случайность уже наблюдена
Пусть цепь конечна, стартует в стационарном распределении π, причём каждая его масса положительна. Мы знаем текущее состояние i и спрашиваем о прошлом j. Совместная вероятность предыдущего j и нынешнего i равна πⱼPⱼᵢ. Деление на массу наблюдаемого i даёт P*ᵢⱼ=πⱼPⱼᵢ/πᵢ. Это применение определения условной вероятности, а не изменение направления стрелки на рисунке. Если старт не стационарен, в формуле нужны распределения соответствующих двух дат, и обратная матрица обычно меняется со временем.
Почему строки остаются вероятностями
Сумма числителей по j равна (πP)ᵢ. Именно стационарность превращает эту сумму в πᵢ, поэтому обратная строка имеет итог один. Кроме того, πᵢP*ᵢⱼ=πⱼPⱼᵢ: обращение переставляет направления совместных потоков. После суммирования по исходному i получаем сохранение того же π. Двойное обращение возвращает P. Равенство P*=P является дополнительным свойством обратимости и эквивалентно детальному балансу всех пар.
Какие траектории сравниваются
Вероятность стационарного пути i₀,…,iₙ есть πᵢ₀Pᵢ₀ᵢ₁⋯Pᵢₙ₋₁ᵢₙ. Подставив обратные переходы вдоль пути в противоположном порядке, получим телескопическое сокращение масс π и ту же вероятность. Поэтому речь идёт об обращении распределения записи процесса. Оно не утверждает физической обратимости каждой реализации. При нулевой стационарной массе соответствующее условие невозможно; состояние сначала исключают из наблюдаемой поддержки, а не делят на ноль.
Разобранная задача
Условие. Три состояния пронумерованы 0,1,2. Из каждого с вероятностью 1/4 остаются на месте и с вероятностью 3/4 идут в следующее по кругу. Старт равномерный. Найдите обратную матрицу и вероятность предыдущего состояния 2 при текущем 0.
- Все столбцы исходной матрицы суммируются в единицу, значит π=(1/3,1/3,1/3) действительно стационарно.
- При равных массах отношение πⱼ/πᵢ равно единице; только в этом частном случае обращение совпадает с транспонированием.
- Обратные строки равны (1/4,0,3/4), (3/4,1/4,0), (0,3/4,1/4). Направление кругового движения сменилось.
- Для события прошлое 2, настоящее 0 совместная масса равна (1/3)(3/4)=1/4. Деление на P(Xₜ=0)=1/3 даёт 3/4.
Ответ. Искомая условная вероятность равна 3/4. Обратная цепь движется преимущественно в противоположном направлении.
Проверка. Перечисление всех трёх возможных предшественников нуля даёт совместные массы 1/12,0,1/4. Их сумма 1/3 и нормированные значения 1/4,0,3/4 независимо воспроизводят первую строку.
Где легко ошибиться. Простое транспонирование не нормирует строки при неравномерном π. Даже у стационарной цепи сохранение распределения не означает равенства прямых и обратных условных переходов.
Обратные переходы стационарной цепи
2–5 состояний. Строки матрицы через переводы строк; элементы — дроби или десятичные числа. Все массы π строго положительны, πP=π; проверка точная, поэтому используйте точные дроби. Неравномерный старт не поддерживается.
Проверьте понимание
Вопросы к этой главе
Нужна ли неприводимость для этой формулы?
Достаточно заданного стационарного закона, положительного на рассматриваемых состояниях. Неприводимость удобна для его единственности, но не используется в самом условном вычислении.
Можно ли восстановить прошлое из произвольного старта?
Да, если известны законы обеих соседних дат. Вместо постоянного π подставляют прежний закон в числитель и текущий в знаменатель; универсальной однородной обратной цепи тогда может не быть.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Hao Wu, MIT 18.445, Lecture 3
Обращённый переход при стационарном законе и условие детального баланса для пары соседних состояний.
Переходные пути: прошлая граница, будущая цель и стационарный поток
Вероятность будущего успеха не сообщает, из какой границы пришла наблюдаемая траектория. Для стационарного ансамбля переходов A→B нужны оба направления времени. Их совместное использование отделяет частоту новых переходных путей от времени, которое они проводят внутри промежуточных состояний.
Перед началом: Стационарный закон и обращённые переходы; Граничные вероятности конечной цепи.
Два коммиттора отвечают на разные вопросы
Конечная неприводимая однородная цепь рассматривается в стационарном двустороннем режиме с положительным законом π. Непустые непересекающиеся множества A и B — источник и цель; они не поглощающие. Переходный путь начинается в последнюю дату пребывания в A перед достижением B и заканчивается первой датой в B без промежуточного возврата в A. Длина — число переходов между этими датами: прямой A→B имеет длину 1; предыдущее ожидание внутри A не включается.
Для внутреннего состояния i обозначим q⁺i вероятность следующей встречи с B раньше A. Она удовлетворяет q⁺i=ΣPijq⁺j, с граничными значениями 0 на A и 1 на B. Обратный коммиттор q⁻i — вероятность того, что последней посещённой границей была A, а не B. Его находят в обращённой цепи P*ij=πjPji/πi: внутри q⁻i=ΣP*ijq⁻j, на A он равен 1, на B — 0.
Обращение здесь служит восстановлению происхождения текущего участка, а не изменению физической динамики. У обратимой цепи P*=P, поэтому q⁻=1−q⁺. Без детального баланса такая подмена неверна: направленная циркуляция может одновременно сделать вероятными приход из A и дальнейшее движение к B. Неприводимость гарантирует достижение границ в обоих направлениях времени и единственность граничных решений.
Условная независимость прошлого и будущего даёт плотность и поток
При фиксированном Xi=i прошлое и будущее стационарной марковской цепи независимы. Значит, ненормированная вероятность застать процесс во внутреннем i на пути A→B равна ρi=πiq⁻iq⁺i. Сумма ρ — доля календарных дат внутри переходных участков, а не частота их начала. На самих A,B эта плотность нулевая из-за граничных значений.
Для разных i,j совместная масса переходного шага i→j равна fij=πiq⁻iPijq⁺j. Умножение учитывает происхождение до i, сам шаг и будущее после j. В транспортной матрице положим fii=0; массу реактивных удержаний πiq⁻iPiiq⁺i храним отдельно. Удаление диагонали из транспортного рисунка не удаляет время удержаний из плотности ρ.
Внутри поток сохраняется: Σjfij=Σjfji. Выход из A равен входу в B; их общая величина k — среднее число новых путей A→B на один календарный такт. Прямые рёбра A→B обязательно входят в k, хотя не дают внутренних дат и не отражаются в сумме ρ.
От частоты и занятости к средней длине
Каждый завершённый путь длины L содержит ровно L−1 внутренних дат, включая повторные удержания. За длинную стационарную запись число таких дат, делённое на число путей, поэтому стремится к E(L−1)=Σρ/k. В принятом соглашении E L=1+Σρ/k. Это длительность отдельного переходного участка, а не среднее время ожидания B из произвольного старта в A.
Число 1/k тоже отвечает другому вопросу: это календарный интервал между завершениями переходов в среднем, включающий пребывание вне текущего успешного участка. Для применения к наблюдаемым данным ещё нужно обосновать стационарность и марковское описание. Ни одна из этих величин не является автоматически физической скоростью реакции или показателем риска.
Циркуляция делает оба коммиттора большими
Условие. Три состояния 0,1,2 имеют строки P=(1/5,3/5,1/5), (1/5,1/5,3/5), (3/5,1/5,1/5). Возьмите A={0},B={2}. Найдите ρ, транспортный поток, частоту k и среднюю длину пути в указанном соглашении.
- Матрица положительна и дважды стохастична: π=(1/3,1/3,1/3). Поэтому P*=Pᵀ. Единственное внутреннее состояние — 1.
- Прямое уравнение q⁺1=q⁺1/5+3/5 даёт 3/4. В обращённой цепи P*10=3/5, поэтому q⁻1=q⁻1/5+3/5=3/4. Это не 1−q⁺1=1/4.
- Получаем ρ1=(1/3)(3/4)²=3/16. Ненулевые транспортные рёбра: f01=f12=(1/3)(3/5)(3/4)=3/20 и f02=(1/3)(1/5)=1/15. Диагональ транспортного потока нулевая; отдельная масса удержания в 1 равна (1/3)(3/4)(1/5)(3/4)=3/80.
- Частота выходов из A равна k=3/20+1/15=13/60; вход в B даёт ту же сумму. Внутренняя средняя занятость на путь равна (3/16)/(13/60)=45/52. Следовательно E L=1+45/52=97/52.
- Независимо классифицируем успешные последние выходы из 0: прямой 0→2 имеет исходную массу 1/5, путь через 1 — (3/5)(3/4)=9/20. Среди этих выходов доли равны 4/13 и 9/13. Во втором случае число дат в 1 геометрическое с вероятностью выхода 4/5 и средним 5/4. Поэтому E L=(4/13)·1+(9/13)·(1+5/4)=97/52.
Ответ. ρ1=3/16; транспортные потоки f01=f12=3/20,f02=1/15; k=13/60 пути за такт. Средняя длина от последней даты в A до первой в B равна 97/52 перехода, без предшествующего ожидания в A.
Проверка. Поток через внутренний узел имеет одинаковые вход и выход 3/20. Полный явный ряд путей 0→1→…→1→2 имеет массы (9/25)(1/5)^j и длины j+2; вместе с прямой массой 1/5 он даёт общую массу 13/20 и взвешенную сумму длин 97/80. Их отношение снова 97/52.
Где легко ошибиться. Не заменяйте обратный коммиттор на 1−q⁺ без обратимости и не теряйте прямые A→B пути при делении внутренней плотности на частоту.
Переходные пути: прошлый источник и будущая цель
2–8 состояний, точные суммы строк 1. Стационарный режим требует неприводимую цепь: A — источник, B — цель, оба множества непусты и не пересекаются. Показаны два коммиттора, поток без диагонали и средняя длина от последнего состояния A до первого B; ожидание в A исключено. Выделенное состояние меняет локальные q± и плотность, а не общий стационарный поток. Поглощающий режим отдельно требует поглощающие A,B и считает условный успешный запуск из начального состояния.
Проверьте понимание
Вопросы к этой главе
Почему средняя длина не равна 1/k?
1/k=60/13 включает календарное ожидание между разными завершениями. Длина 97/52 относится только к одному последнему выходу из A, который достигает B до возврата; ожидание внутри A перед этим выходом исключено.
Почему в транспортной матрице нет удержания, а в длительности оно есть?
Диагональный шаг не переносит массу между разными состояниями, поэтому его рисуют отдельно. Однако он занимает целый такт и создаёт ещё одну внутреннюю дату; плотность ρ и геометрический ряд удержаний сохраняют этот вклад.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Helfmann et al.: Extending Transition Path Theory, стационарный случай §3
Определяет два коммиттора, плотность и поток стационарных переходных путей. Здесь отдельно задан счёт длины с прямым ребром и построен собственный трёхсостоянийный пример с независимой суммой путей.
- deeptime: flux_matrix, соглашение о транспортной диагонали
Для транспортной матрицы использует нулевую диагональ. В главе масса удержаний выделена отдельно, чтобы этот способ изображения потока не удалял календарное время из расчёта длины.
Когда остановиться: обратная рекурсия оболочки Снелла
При старте L можно получить ожидаемую выплату 43/16, выбирая момент выхода по текущему состоянию. Лучшая заранее назначенная дата даёт 41/16, а подсматривание в будущее — недостижимые 47/16. Построим допустимое оптимальное правило.
Перед началом: Условное ожидание и момент остановки; Умножение конечной матрицы на столбец выплат.
Награда выплачивается один раз по выбранной дате
Конечная цепь и конечный горизонт 0,1,2; выплата только при выбранной остановке, наблюдается текущее состояние без будущего.
Состояния L и H имеют строки переходов (3/4,1/4) и (1/2,1/2). На датах ноль и один остановка приносит 1 в L и 4 в H. На последней дате два выплаты равны 1 и 6; тогда остановиться обязательно. Стартуем в L. Заранее зафиксировать дату, выбрать её после наблюдения текущего состояния и выбрать лучший момент после просмотра будущего — три разных множества допустимых решений.
Пусть rₜ(i) — выплата при остановке, Vₜ(i) — лучшая ожидаемая выплата, если до даты t ещё не остановились и видят i. Условие V₂=r₂ задаётся концом горизонта. Затем Vₜ(i)=max{rₜ(i),ΣⱼPᵢⱼVₜ₊₁(j)}. В первом варианте деньги забирают сейчас; во втором делают ровно один переход и продолжают уже оптимально. Будущее решение не фиксируется сегодня как одна обязательная дата.
Максимум локальных решений имеет глобальное доказательство
Вдоль цепи процесс Zₜ=Vₜ(Xₜ) доминирует доступную выплату rₜ(Xₜ). Из рекурсии E[Zₜ₊₁|Fₜ]≤Zₜ, то есть Z является супермартингалом. Для любой допустимой остановки τ≤2 получаем E[rτ(Xτ)]≤E[Zτ]≤Z₀. Это верхний сертификат сразу для всех правил, включая те, которые зависят от всей уже наблюдённой истории.
Остановимся при первом равенстве Vₜ(Xₜ)=rₜ(Xₜ). До него выбрана ветвь продолжения, где условное ожидание следующего Z равно текущему Z. Поэтому остановленный Z является мартингалом. На моменте выхода его значение совпадает с выплаченной наградой, достигая верхней границы V₀. На конечном горизонте равенство обязательно наступит не позже последней даты. При ничьей можно выбрать раннюю остановку; единственность правила из этого не следует.
Фиксированная дата и доступ к будущему дают другие ответы
Эта рекурсия не складывает награды всех посещённых состояний. Прежняя задача накопленной оплаты использовала линейную сумму по датам; здесь выплата ровно одна, а операция максимума создаёт выбор. С другой стороны, теорема об ограниченной остановке честного мартингала не обещает нулевой выигрыш для произвольной системы наград: сами rₜ(Xₜ) могут не быть мартингалом.
Подсматривание позволяет выбирать максимум реализованных наград всего пути. Такой индекс обычно не является моментом остановки, поскольку решение уйти сейчас зависит от ещё не увиденного исхода. Его среднее может служить верхней оценкой, но не достижимой стратегией. Проверка требует перечислить именно остановленные ветви, сохранив раннее решение даже на тех путях, где будущая награда задним числом оказалась выше.
Два разрешённых решения до последней даты
Условие. Даны строки L→(L,H)=(3/4,1/4), H→(L,H)=(1/2,1/2). На датах 0,1 выплата(L,H)=(1,4), на дате 2 — (1,6). Старт L. Найдите оптимальное правило и ожидаемую выплату.
- На последней дате V₂=(1,6). На дате 1 продолжение из L стоит (3/4)·1+(1/4)·6=9/4, что больше немедленной единицы.
- Из H продолжение стоит (1/2)·1+(1/2)·6=7/2, что меньше немедленных 4. Значит V₁=(9/4,4): продолжаем из L, останавливаемся из H.
- На дате 0 из L продолжение стоит (3/4)(9/4)+(1/4)4=43/16>1. Поэтому оптимальная начальная команда — продолжать.
- Из начального L остановленные исходы: H на дате 1 с массой 1/4 и выплатой 4; L,H с массой 3/16 и выплатой 6; L,L с массой 9/16 и выплатой 1. Их среднее равно 1+18/16+9/16=43/16.
- Если дату выбрать заранее, значения для 0,1,2 равны 1,7/4,41/16. Их максимум 41/16 ниже 43/16. Полный будущий максимум по четырём двухшаговым путям дал бы 47/16, но требует недоступной информации.
Ответ. Продолжить из начального L; на дате 1 остановиться в H и продолжить в L; на дате 2 выйти обязательно. Ожидаемая выплата 43/16.
Проверка. Полный перебор всех детерминированных решений на конечном дереве даёт максимум 43/16; рандомизация не улучшает максимум линейной ожидаемой выплаты. Супермартингальный сертификат V одновременно ограничивает все такие правила сверху.
Где легко ошибиться. Не заменяйте условное среднее будущей оптимальной выплаты средним максимумом всех будущих реализованных выплат. Последний максимум использует информацию, которой в момент решения ещё нет.
Проверьте понимание
Вопросы к этой главе
Почему нельзя в H на дате 1 дождаться шести?
Шесть возможны, но не гарантированы: из H половина переходов заканчивается в L с выплатой 1. Среднее ожидание 7/2 меньше доступных сейчас 4.
Разве оптимальное правило обязано зависеть только от состояния?
Здесь да, после включения номера даты в состояние: переходы марковские, награда задана через дату и текущее имя. Если выплата зависит от ранее достигнутого максимума или иной истории, эту информацию сначала добавляют к состоянию.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Davis–Karatzas, A Deterministic Approach to Optimal Stopping, формула(6)
Конечная обратная рекурсия оболочки Снелла и первое достижение области остановки. Двухсостоянийная выплата, сравнение фиксированных дат и перебор дерева составлены здесь.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему двухшаговый переход суммирует промежуточные состояния
Почему вероятность двух переходов складывается по промежуточным состояниям и чем степень матрицы отличается от возведения её элементов в квадрат.
Открыть темуКак совместная таблица задаёт маргинальные и условные законы
Как одна таблица вероятностей пары восстанавливает отдельные законы, события по нескольким клеткам и условное распределение после фиксации одного признака.
Открыть тему