Вероятность и статистика · объяснение и практика

Почему двухшаговый переход суммирует промежуточные состояния

Почему вероятность двух переходов складывается по промежуточным состояниям и чем степень матрицы отличается от возведения её элементов в квадрат.

Рука ставит оранжевый столбик между двумя синими столбиками разной высоты.

В теме Случайные процессы и имитация: углубление · Учебная карта

В маршруте Состояния и случайные процессы · 10 тем

Главная мысль

Для двух шагов складывают произведения вероятностей по всем промежуточным состояниям. Поэтому двухшаговая матрица равна P² при обычном матричном умножении, а не при поклеточном возведении в квадрат.

Промежуточная остановка может быть разной

Пусть строки переходов между А и Б равны (0,7;0,3) и (0,4;0,6). Известен старт в А. Оказаться в Б через два шага можно по маршрутам А–А–Б и А–Б–Б. Первый имеет вероятность 0,7·0,3, второй — 0,3·0,6. Маршруты несовместимы из-за разного состояния после первого шага.

Сумма равна 0,39. Квадрат вероятности 0,3 дал бы 0,09, но он не соответствует поставленному событию. Второй переход из Б в Б имеет вероятность 0,6, а не 0,3. Кроме того, квадрат одного элемента вообще забывает маршрут через А. Ошибка появляется, когда таблицу воспринимают как список независимых чисел, а не как правило движения.

Восстанавливаем всю строку двухшагового закона

Вероятность вернуться в А через два шага равна 0,7·0,7+0,3·0,4=0,61. Вместе с найденными 0,39 получается единица. Для старта в Б аналогично получаем 0,4·0,7+0,6·0,4=0,52 для А и 0,48 для Б. Так складывается матрица P² с двумя полноценными распределениями в строках.

Общая формула имеет вид (P²)ij=Σk pik pkj. Буква k перечисляет промежуточные состояния, а i и j остаются фиксированными. Для трёх шагов можно сначала найти P², затем умножить на P. Закон начального состояния π переносится как πP²; он не превращает саму двухшаговую вероятность в условную вероятность отдельного пути.

Пример

Чему равна вероятность пути А–Б–А в этой модели?

Она равна 0,3·0,4=0,12. Это только один путь к А; общая двухшаговая вероятность А равна 0,61, поскольку включает также А–А–А.

Согласуем временной горизонт

Величина из P² отвечает на вопрос о состоянии ровно после двух переходов. Она не равна вероятности хотя бы раз побывать в Б за это время. Последнее событие включает траектории, закончившиеся обратно в А, и требует другого объединения путей. Слово «через» и выражение «за первые два шага» меняют математическую задачу.

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

От чтения к действию

А теперь — вы

Для однородной цепи строки А и Б равны (0,5;0,5) и (0,2;0,8). Какова вероятность Б ровно через два шага при старте в А?

Частые вопросы

Почему пути можно складывать?

У них различаются промежуточные состояния, поэтому при одном запуске они не происходят одновременно.

Можно ли получить отрицательный элемент P²?

У настоящей переходной матрицы нет: её элементы являются суммами произведений неотрицательных вероятностей.

Углублённый разбор

Марковский мост: условный промежуточный шаг при известном конце

Известный конец траектории меняет вероятности промежуточных переходов. Условный путь между двумя состояниями называется марковским мостом.

Перед началом: Условная вероятность и математическое ожидание; Стохастические матрицы и стационарный закон.

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

Для старта i и известного Xₙ=j вероятность Xₖ=a пропорциональна PᵏᵢₐPⁿ⁻ᵏₐⱼ. Первый множитель ведёт к промежуточному состоянию, второй продолжает путь к обязательному концу. Нормирующий знаменатель равен Pⁿᵢⱼ.

Вывод и вычислительный критерий

Пересечение событий Xₖ=a и Xₙ=j разбивается по прошлому и будущему в точке k. Марковское свойство позволяет перемножить указанные вероятности. Суммирование по a восстанавливает знаменатель, поэтому условные веса автоматически дают единицу.

Тот же расчёт задаёт неоднородный переход моста: P̃ₜ(a,b)=Pₐᵦhₜ₊₁(b)/hₜ(a), где hₜ(a)=Pⁿ⁻ᵗₐⱼ. Вероятность будущего завершения меняется с оставшимся временем, хотя исходная цепь однородна.

Условия и границы вывода

Условие допустимо только при положительной вероятности объявленного конца. Если знаменатель нулевой, обычное конечное условное распределение не определено. Нельзя исправлять это делением на малую произвольную константу.

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

Условную вероятность можно проверить и обратным вопросом. Если промежуточное состояние известно как A, шанс завершить в B равен одной четверти; если как B, шанс равен половине. Поэтому известный конец B усиливает относительный вес промежуточного B вдвое. До условия отношение весов A к B было три к одному, после условия стало три к двум. Полученный результат три пятых меньше исходных трёх четвертей, что согласуется с направлением отбора. При известном конце A веса путей были бы девять шестнадцатых и две шестнадцатых, поэтому промежуточный шанс A стал бы девятью одиннадцатыми. Разные концы создают разные мосты.

Разобранная задача

Условие. Старт A, P=((3/4,1/4),(1/2,1/2)). Известно, что после двух шагов получено B. Найдите вероятность промежуточного A.

  1. Путь A→A→B имеет вероятность 3/4·1/4=3/16.
  2. Путь A→B→B имеет вероятность 1/4·1/2=2/16.
  3. Полная вероятность конца B равна 5/16 и положительна, поэтому условие допустимо.
  4. Условная масса первого пути равна (3/16)/(5/16)=3/5; масса второго равна 2/5.

Ответ. Вероятность промежуточного A при известном конце B равна 3/5.

Проверка. Два совместимых пути имеют веса 3 и 2 после сокращения общего знаменателя. Нормировка непосредственно даёт 3/(3+2), независимо от матричного расчёта.

Где легко ошибиться. Нельзя оставлять промежуточную вероятность A равной 3/4: сведения о конце исключили часть первоначальных траекторий.

Проверьте понимание

Когда условие на конечное состояние нельзя нормировать обычной формулой?

Вопросы к этой главе

Остаётся ли мост однородной цепью?

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

Требуется ли знать весь путь?

Нет. Фиксируется лишь событие о конце. Оставшаяся неопределённость по промежуточным маршрутам и является предметом условного расчёта.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Sébastien Roch: конечные цепи, Chapter 1.1

    PDF с извлечённым текстом: §1.1.2, стохастические переходы, стационарность и условия сходимости; отдельные вычисления выполнены для данной главы.

Число посещений состояния: ожидание через индикаторы

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

Перед началом: Условная вероятность и математическое ожидание; Стохастические матрицы и стационарный закон.

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

Число N_A=ΣₜI{Xₜ=A} может принимать значения от нуля до числа наблюдаемых дат. Индикаторы зависимы, но их ожидания складываются без дополнительных условий. Поэтому EN_A=ΣₜP(Xₜ=A).

Вывод и вычислительный критерий

Чтобы считать посещения, сначала объявляют, входит ли начальное состояние и считаются ли самопереходы новым наблюдением. При учёте дат каждое пребывание в A добавляет единицу, даже если цепь не выходила из A.

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

Условия и границы вывода

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

В конечном горизонте расчёт всегда сводится к конечному числу распределений. Значение ожидания выше единицы законно: это средний счёт, а не вероятность события.

Если начальную дату исключить, счёт в примере уменьшится ровно на единицу и его ожидание станет единицей. При этом вероятность хотя бы одного позднего посещения равна трём четвертям: единственный запрещённый путь содержит B в обе поздние даты. Такой вариант подчёркивает различие даже без гарантированного начального успеха. Для счёта входов из B в A нужно использовать индикатор пары состояний. В примере вход в дату один невозможен, поскольку старт A; вход в дату два имеет вероятность одной четверти. Ожидание входов тогда равно четверти и не совпадает ни со счётом присутствий, ни с вероятностью посещения.

Разобранная задача

Условие. Цепь со строками (1/2,1/2),(1/2,1/2) стартует в A. Считайте посещения A в даты 0,1,2. Найдите ожидание и вероятность хотя бы одного посещения.

  1. В дату ноль индикатор A равен единице с достоверностью.
  2. В даты один и два вероятность A равна 1/2 каждая, поскольку строки матрицы одинаковы.
  3. Ожидаемый счёт равен 1+1/2+1/2=2. Он допускает повторные посещения.
  4. Хотя бы одно посещение гарантировано стартом в A, поэтому вероятность объединения равна единице.

Ответ. Среднее число посещений равно 2, вероятность хотя бы одного равна 1.

Проверка. Последующие два состояния независимо равновероятны. Счёт принимает 1,2,3 с вероятностями 1/4,1/2,1/4; взвешенная сумма равна двум.

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

Проверьте понимание

Что вычисляет сумма вероятностей присутствия в A по трём датам?

Вопросы к этой главе

Считается ли самопереход посещением?

В счёте по датам да. Если нужны именно входы из другого состояния, индикатор должен описывать пару соседних состояний, и формула изменится.

Может ли ожидание превышать единицу?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Sébastien Roch: конечные цепи, Chapter 1.1

    PDF с извлечённым текстом: §1.1.2, стохастические переходы, стационарность и условия сходимости; отдельные вычисления выполнены для данной главы.

Полное распределение числа посещений через маркированную матрицу

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

Перед началом: Конечная цепь Маркова; Условное ожидание и точные вероятности.

Сначала фиксируется, какие даты считаются

Пусть начальный закон μ относится к X₀, а Nₙ считает попадания в множество A на датах 1,…,n. Начальная дата в счётчик не входит. Определим диагональную матрицу D(z), у которой элемент равен z для состояния из A и единице для остальных. Каждый переход затем умножается на маркер нового состояния.

Производящая функция равна Fₙ(z)=μ(PD(z))ⁿ1, где последний вектор состоит из единиц. Степень z в произведении вдоль пути равна числу посещений, а коэффициент этого одночлена равен массе пути. Сложение всех конечных состояний объединяет пути с одинаковым счётчиком.

Коэффициенты являются конечным распределением

Можно хранить для каждого текущего состояния массив коэффициентов. Переход переносит массу в следующее состояние и, если оно принадлежит A, сдвигает индекс счётчика на единицу. Такое обновление не предполагает независимость посещений и работает при любом фиксированном начальном распределении.

Нужна отдельная формула, если считается также X₀: перед переходами появляется начальный множитель D(z). Перестановка P и D(z) обычно меняет задачу, поскольку умножение матриц некоммутативно. На горизонте ноль наша исходная функция равна единице: пустой счётчик всегда нулевой.

Моменты проверяют полином, но не заменяют его

Все коэффициенты Fₙ неотрицательны, а Fₙ(1)=1. Производная Fₙ′(1) равна ожидаемому числу визитов и должна совпасть с суммой вероятностей попадания на каждой учитываемой дате. Вторая производная даёт факториальный момент E[Nₙ(Nₙ−1)], из которого восстанавливается дисперсия.

Две модели могут иметь одинаковое среднее и разные коэффициенты. В частности, биномиальная замена требует независимых одинаково распределённых индикаторов, а не просто подходящего среднего количества посещений. Полный полином позволяет проверять конкретные хвосты и события, которые из одного среднего не восстанавливаются.

Посещения A за два перехода

Условие. Начальное состояние A известно. Матрица P равна ((1/2,1/2),(1/4,3/4)). Считаются посещения A на датах X₁ и X₂. Найдите распределение N₂ и его среднее.

  1. Пути по двум следующим состояниям AA,AB,BA,BB имеют массы 1/4,1/4,1/8,3/8 соответственно.
  2. Счётчики на этих путях равны 2,1,1,0. После объединения получаем P(N₂=0)=3/8, P(N₂=1)=3/8 и P(N₂=2)=1/4.
  3. Производящая функция равна 3/8+(3/8)z+(1/4)z². Её значение в единице равно единице, а производная в единице — 7/8.
  4. Независимо, вероятность A на первой дате равна 1/2, на второй — 3/8. Их сумма 7/8 подтверждает среднее, сохраняя отличие закона от биномиального.

Ответ. Распределение по значениям 0,1,2 равно (3/8,3/8,1/4); E[N₂]=7/8.

Проверка. Матричное умножение μPD(z)=(z/2,1/2), а ещё один переход даёт сумму компонент z²/4+3z/8+3/8. Это отдельно проверяет полином против прямого перечисления четырёх путей.

Где легко ошибиться. Не добавляйте гарантированный начальный визит A к счётчику, если вопрос начинается с X₁. Такой сдвиг увеличил бы каждый возможный результат на единицу. Также нельзя усреднить вероятности двух дат и объявить счётчик биномиальным без проверки зависимости.

Проверьте понимание

Какова вероятность ровно одного учтённого визита A в задаче?

Вопросы к этой главе

Нужна ли стационарность начального закона?

Нет. Конечное матричное произведение использует именно заданную μ. Стационарный старт может упростить отдельные моменты, но не является предпосылкой производящей функции.

Можно ли считать посещения нескольких разных множеств?

Да, при явном договоре каждому событию назначают свой маркер. Тогда получается многомерный полином и совместное распределение счётчиков; число коэффициентов и требования к хранению существенно увеличиваются.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Aldous–Fill, Chapter 2, §2.1

    Проверены первичные авторские определения конечной цепи и переходной матрицы. Маркированное конечное произведение и конкретный полином выведены непосредственно по путям здесь, а не заимствованы как пример источника.

Уравнение Пуассона: асимптотическая ошибка марковского среднего

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

Перед началом: Стационарный закон конечной цепи; Условное ожидание и ортогональные приращения.

Линейное уравнение вместо бесконечного ряда

Пусть конечная цепь неприводима и апериодична, старт имеет стационарный закон π. Центрируем наблюдаемую функцию: f=r−πr, так что πf=0. Для суммы Rₙ=Σₜ₌₀ⁿ⁻¹f(Xₜ) ищем предел σас²=lim Var(Rₙ)/n. Дисперсия среднего тогда асимптотически равна σас²/n; это не точная формула для каждого конечного n.

Уравнение Пуассона имеет вид (I−P)g=f. Матрица I−P вырождена, поскольку константы лежат в её ядре. Центрирование f обеспечивает совместимость, а условие πg=0 выбирает единственное решение. Обычное обращение I−P без нормировки неправомерно. В конечной неприводимой модели достаточно решить систему с одним заменённым уравнением или использовать I−P+1π.

Ортогональные приращения и граничный остаток

Обозначим Dₖ=g(Xₖ)−Pg(Xₖ₋₁), где Pg(i)=ΣⱼPᵢⱼg(j). Условное ожидание Dₖ по всей истории до k−1 равно нулю. Поэтому разные Dₖ ортогональны, хотя вовсе не обязаны быть независимыми. По телескопированию Rₙ=g(X₀)−g(Xₙ)+Σₖ₌₁ⁿDₖ.

В конечном пространстве g ограничена, значит дисперсия граничной разности ограничена независимо от n. Ковариация этой разности с мартингальной суммой по Коши имеет порядок не больше √n. После деления общей дисперсии на n оба граничных вклада исчезают. При стационарном старте получаем σас²=EπD₁²=π[g²−(Pg)²].

Что сообщает предельная константа

Используя Pg=g−f, ту же константу можно записать как 2π(fg)−π(f²). Обратимость для этого равенства не нужна. Разные функции одной цепи имеют разные g и разные σас²: качество цепи для одного наблюдаемого среднего не характеризует автоматически все остальные величины.

Число σас² может быть больше или меньше индивидуальной дисперсии πf². Их отношение описывает асимптотический коэффициент потери или выигрыша относительно IID-наблюдений при той же цене одного шага. Этот коэффициент не доказывает точный конечный эффективный размер выборки и не оценивает начальное смещение из произвольного старта. Для бесконечного пространства существование и интегрируемость g требуют отдельных условий; конечное доказательство ограниченным остатком туда автоматически не переносится.

Необратимый цикл с удержанием

Условие. Три состояния 0,1,2. Из i цепь остаётся в i с вероятностью 3/4 и переходит в i+1 modulo 3 с вероятностью 1/4. Старт равномерный, f=(1,−1,0). Найдите предел Var(Rₙ)/n через уравнение Пуассона и сравните с индивидуальной дисперсией.

  1. Каждая колонка переходной матрицы суммируется в единицу, поэтому π=(1/3,1/3,1/3). Среднее f нулевое, индивидуальная дисперсия равна (1+1+0)/3=2/3.
  2. Уравнения сводятся к g₀−g₁=4, g₁−g₂=−4, g₂−g₀=0. Вместе с g₀+g₁+g₂=0 они дают g=(4/3,−8/3,4/3).
  3. Получаем Pg=g−f=(1/3,−5/3,4/3). Стационарные средние квадратов равны πg²=32/9 и π(Pg)²=14/9.
  4. Разность равна двум, значит σас²=2. Отношение к индивидуальной дисперсии равно 2/(2/3)=3: для длинного среднего здесь появляется втрое больший коэффициент, чем при независимом равномерном выборе состояний.

Ответ. Асимптотическая константа дисперсии равна 2; Var(Rₙ/n)∼2/n. Индивидуальная дисперсия равна 2/3, коэффициент зависимости — три.

Проверка. По шести стационарным переходам D принимает 1,−3,−1,3,0,0 с массами 1/4,1/12,1/4,1/12,1/4,1/12. Их среднее нулевое, второй момент равен двум, независимо подтверждая формулу квадратов.

Где легко ошибиться. Уравнение Пуассона не связано здесь с распределением Пуассона. Это линейное уравнение оператора перехода; нецентрированный правый столбец в общем случае несовместим, а константу решения нужно зафиксировать отдельным условием.

Проверьте понимание

Чему равен предел Var(Rₙ)/n для указанного стационарного трёхсостоянийного цикла и f=(1,−1,0)?

Вопросы к этой главе

Почему не нужно перечислять все длинные пути?

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

Можно ли использовать 2/n как точную ошибку при n=1?

Нет. При одном наблюдении дисперсия среднего равна 2/3. Предельная формула описывает большие n; конечный остаток и ковариации ещё существенны на коротком отрезке.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Douc–Jacob–Lee–Vats: Poisson equation, §1.1

    Прочитаны PDF-страницы 2–3, уравнения 1.2–1.3: центрированное уравнение Пуассона и асимптотическая мартингальная дисперсия. Здесь конечное доказательство через ограниченную границу и собственный необратимый цикл; методы сопряжённых цепей статьи не пересказываются.

Сглаживание скрытого прошлого: обратная рекурсия будущих сигналов

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

Перед началом: Условная вероятность; Точная арифметика.

Две стороны одной даты

Пусть скрытые состояния Xₜ образуют конечную цепь с матрицей P, а сигналы условно независимы при заданном скрытом пути и имеют вероятности bⱼ(y). Прямые массы αₜ(j) описывают совместный префикс наблюдений и состояние j. Для прошлого состояния после получения всех T сигналов нужны также βₜ(j)=P(Yₜ₊₁=yₜ₊₁,…,Y_T=y_T|Xₜ=j). Этот множитель не является вероятностью самого состояния: он оценивает совместимость будущей записи с ним.

Рекурсия идёт от конца

На последней дате будущих сигналов уже нет, поэтому β_T(j)=1. Один обратный шаг имеет вид βₜ(i)=ΣⱼPᵢⱼbⱼ(yₜ₊₁)βₜ₊₁(j). Сначала предполагается следующий скрытый режим, затем его сигнал и оставшийся суффикс. После прохода назад перемножаем αₜ(j)βₜ(j) и нормируем по j. Сумма ненормированных масс равна полному правдоподобию всех сигналов и не зависит от выбранной даты t.

Сглаживание не является новым переходом

Будущие сигналы меняют условное знание прошлого, но не физически переписывают траекторию. Нельзя заменить обратную рекурсию стационарным обращением P: измерение входит отдельным множителем и обычно нарушает стационарность условного пути. Для длинных последовательностей допустимы положительные масштабирования β, если итог нормируют; нулевое полное правдоподобие требует сообщения о несовместимости данных, а не произвольного распределения.

Разобранная задача

Условие. Начальный закон состояний A,B равен (1/2,1/2), P=((3/4,1/4),(1/4,3/4)). Красный сигнал имеет вероятности (4/5,1/5). Получены два красных сигнала. Найдите вероятность первого состояния A после обоих измерений.

  1. После первого сигнала α₁=(2/5,1/10), поэтому обычный фильтр прошлой даты давал бы вероятность A=4/5.
  2. Конечный обратный вектор β₂=(1,1). Для первой даты β₁(A)=(3/4)(4/5)+(1/4)(1/5)=13/20.
  3. Аналогично β₁(B)=(1/4)(4/5)+(3/4)(1/5)=7/20. Произведения α₁β₁ равны 52/200 и 7/200.
  4. Нормируем на сумму 59/200: сглаженная вероятность первого A равна 52/59, первого B — 7/59.

Ответ. Вероятность первого состояния A с учётом второго сигнала равна 52/59, а не прежним 4/5.

Проверка. Прямой перебор AA,AB,BA,BB даёт массы 48/200,4/200,4/200,3/200. Для первого A складываем первые две; итог 52/59. В этой симметричной задаче последний A случайно имеет ту же массу, что не является общей теоремой.

Где легко ошибиться. Не считайте β распределением состояния: его координаты не обязаны складываться в один. Нормировать нужно произведение αβ, иначе пропадёт информация первого сигнала.

Проверьте понимание

Какой вектор перемножают с α₁ перед нормировкой?

Вопросы к этой главе

Можно ли использовать ещё не полученный сигнал для текущего управления?

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

Почему пример использует те же сигналы, что глава о фильтре?

Это позволяет сравнить временные вопросы на одной записи. Новая операция оценивает прошлую дату через backward-рекурсию; совпадение двух чисел здесь обусловлено симметрией и проверено отдельно.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Первое достижение и переход за n шагов: уравнение обновления

Переход в состояние за n шагов допускает ранний вход и последующие возвращения. Распределение первого достижения отделяет эти траектории и восстанавливается из уравнения обновления.

Перед началом: Условная вероятность; Точная арифметика.

Первый вход разбивает все пути

Пусть конечная однородная цепь стартует в i≠j. Обозначим fₖ=Pᵢ(Tj=k), где Tj — первый момент входа в j, а uₙ=Pᵢ(Xₙ=j). Если к дате n цепь находится в j, её первый вход произошёл в единственный момент k≤n. После входа дальнейшее движение от j не зависит от прежнего пути по сильному марковскому свойству. Поэтому uₙ=Σₖ₌₁ⁿ fₖvₙ₋ₖ, где vₘ=Pⱼ(Xₘ=j) и v₀=1.

Рекурсия удаляет уже объяснённые возвращения

Из коэффициента v₀=1 получаем fₙ=uₙ−Σₖ₌₁ⁿ⁻¹fₖvₙ₋ₖ. Это последовательное разложение одного закона на первый вход и последующий возврат. В точной вероятностной модели fₙ неотрицательны, а сумма первых n значений не превосходит единицы. Отрицательная вычисленная масса указывает на несогласованные переходные вероятности или существенное округление, а не на допустимую отрицательную вероятность. При поглощающем j все vₘ=1 и формула упрощается до разностей накопленных вероятностей.

Хвост достижения отличается от пребывания

Вероятность Tj≤n равна сумме fₖ, а вероятность Xₙ=j равна uₙ. Они совпадают лишь если после входа невозможно покинуть j до n, например при поглощении. Для обычного возвращающегося состояния первая вероятность может быть больше второй. Ожидание времени достижения, если оно конечно, определяется всем хвостом, а не одной n-шаговой вероятностью. Ниже используется краткая цепь, где распределение первого входа можно проверить напрямую и сопоставить с обновлением.

Разобранная задача

Условие. Два состояния A,B имеют матрицу P=((1/2,1/2),(1,0)), старт A. Найдите вероятности первого входа в B на шагах 1,2,3 и сравните P(TB≤3) с P(X₃=B).

  1. Первый вход происходит после k−1 удержаний в A и одного перехода в B. Поэтому f₁=1/2,f₂=1/4,f₃=1/8.
  2. Вероятность достичь B не позже третьего шага равна 1/2+1/4+1/8=7/8.
  3. Из B следующий шаг всегда ведёт в A, значит v₁=0. Через два шага возврат в B имеет вероятность v₂=1/2.
  4. Уравнение обновления даёт u₃=f₃v₀+f₂v₁+f₁v₂=1/8+0+1/4=3/8. Ранние входы не гарантируют пребывание в B на последней дате.

Ответ. Первые массы равны 1/2,1/4,1/8; накопленное достижение 7/8, но пребывание в B на третьем шаге — только 3/8.

Проверка. Скалярная рекурсия pₙ₊₁=(1−pₙ)/2 для pₙ=P(Xₙ=B),p₀=0 даёт p₁=1/2,p₂=1/4,p₃=3/8. Это независимо проверяет n-шаговое пребывание без разложения по первому входу.

Где легко ошибиться. Не называйте элемент Pⁿᵢⱼ вероятностью первого достижения на шаге n. Он уже включает пути с более ранними входами и возвращениями, которые нужно отделять.

Проверьте понимание

Какова вероятность пребывания в B на третьем шаге?

Вопросы к этой главе

Почему старт i≠j оговорён отдельно?

Если старт уже j, обычное первое достижение равно нулю. Первое возвращение требует определения Tj⁺≥1 и другой начальной конвенции.

Когда можно взять простую разность uₙ−uₙ₋₁?

При поглощающем целевом состоянии uₙ является накопленной вероятностью входа. В общей цепи оно может даже уменьшаться между датами.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Aldous–Fill, Reversible Markov Chains, §2.1

    Первое достижение состояния и обычные переходные вероятности различаются допустимостью ранних посещений.

Время поглощения целиком: производящая функция вместо одного среднего

Поглощение из A может произойти уже на первом шаге. Его среднее время равно 8/3, а вероятность чётного времени — 3/7. Второе число нельзя прочитать из первого: для него построим производящую функцию случайного срока.

Перед началом: Матричные переходы и первый шаг; Производящая функция целочисленной величины.

Маркер относится к длительности, а не к посещённой категории

Конечная поглощающая цепь; все промежуточные состояния временные, время считает переходы до первого поглощения.

В цепи A, B, D состояние D поглощает. Из A за такт переходят в A, B, D с вероятностями по 1/3. Из B идут в A или D с вероятностями по 1/2. Старт фиксирован в A. Пусть T — номер первого попадания в D. Значения T не ограничены сверху: самопереход A допускает долгие запуски. При этом поглощение происходит почти наверное, поскольку из любого внутреннего состояния есть положительный шанс завершиться за следующий такт.

Для старта i введём Fᵢ(z)=Eᵢ[zᵀ]. Коэффициент zⁿ равен Pᵢ(T=n), поэтому функция хранит целое распределение. При старте в D время нулевое и F_D(z)=1. Каждый первый переход добавляет один такт и множитель z независимо от того, куда он привёл. Это отличается от маркирования посещений выбранной категории за заранее назначенное число шагов.

Резольвента суммирует произвольное число незавершённых шагов

Пусть Q — блок переходов между внутренними состояниями, а r — столбец вероятностей поглощения за один шаг. Правило первого шага даёт F(z)=zQF(z)+zr. Следовательно F(z)=z(I−zQ)⁻¹r. Разложение обратной матрицы в ряд даёт Σₖ≥₀zᵏ⁺¹Qᵏr: сначала k переходов остаются внутри, затем следующий завершает путь. Коэффициенты не предполагают независимость длительностей в отдельных состояниях.

У конечной временной части спектральный радиус Q меньше единицы, поэтому ряд сходится при |z|≤1 и в некоторой большей окрестности. В частности, допустимы z=−1 и дифференцирование в единице. Если внутри есть замкнутый непоглощающий класс, это условие нужно проверить заново: нельзя обещать нормированное конечное время лишь по виду формальной обратной матрицы. Число F(1) тогда может отражать только вероятность конечного завершения.

Чётность и среднее читаются разными операциями

Значение F(1) равно единице для почти наверное конечного T. Значение F(−1)=P(T чётно)−P(T нечётно), откуда вероятность чётного времени равна [1+F(−1)]/2. Этот приём суммирует бесконечно много коэффициентов по их знакам. Производная F′(1), напротив, взвешивает коэффициент его номером и возвращает E[T]. Совпадение средних двух моделей не заставляет совпадать ни чётность, ни крайние сроки.

Знаменатель рациональной функции также позволяет вывести рекурсию для вероятностей. Это способ посчитать нужный участок распределения без перечисления всех путей. Но степень знаменателя не является максимальной длительностью, а полюс вне единичного круга не означает возможный отрицательный срок. Аналитические свойства описывают затухание коэффициентов, не меняя целочисленную поддержку часов.

Чётность первого поглощения

Условие. Строки переходов A→(A,B,D)=(1/3,1/3,1/3), B→(A,B,D)=(1/2,0,1/2), D поглощает. Из A найдите производящую функцию T, вероятность чётного T и среднее.

  1. Первый шаг даёт FA=z(FA/3+FB/3+1/3), FB=z(FA/2+1/2). Время при старте D равно нулю, поэтому его функция равна единице.
  2. Подставим FB в первое уравнение: FA(1−z/3−z²/6)=z/3+z²/6. Значит FA(z)=(2z+z²)/(6−2z−z²).
  3. Проверим нормировку: FA(1)=3/3=1. При z=−1 получаем −1/7, поэтому P(T чётно)=(1−1/7)/2=3/7.
  4. Для производной в единице числитель N=3, N′=4, знаменатель D=3, D′=−4. Поэтому FA′(1)=(4·3−3·(−4))/9=8/3.
  5. Начальные коэффициенты из (6−2z−z²)FA=2z+z² равны 1/3,5/18,4/27. Они положительны и совпадают с массами путей длительностей один, два и три.

Ответ. FA(z)=(2z+z²)/(6−2z−z²); P(T чётно)=3/7; E[T]=8/3 шага.

Проверка. Независимо обозначим eA,eB вероятности чётного остаточного времени. Тогда eA=(1−eA)/3+(1−eB)/3 и eB=(1−eA)/2. Решение даёт eA=3/7,eB=2/7. Уравнения средних tA=1+tA/3+tB/3 и tB=1+tA/2 дают tA=8/3.

Где легко ошибиться. Не путайте значение функции в минус единице с вероятностью чётности. Оно является разностью двух вероятностей; для нужной вероятности требуется ещё нормировка [1+F(−1)]/2.

Проверьте понимание

Какова вероятность чётного времени первого поглощения из A в разобранном примере статьи?

Вопросы к этой главе

Почему при z=0 функция из A равна нулю?

Из A невозможно закончить без перехода, поэтому постоянный коэффициент равен P(T=0)=0. Из поглощающего D функция была бы единицей.

Можно ли заменить распределение геометрическим с тем же средним?

Нет. Шанс завершения зависит от текущего состояния. Геометрическая замена меняет рекурсию и, в частности, вероятность чётного времени; совпадение одного среднего не исправляет это различие.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Levin–Peres–Wilmer, Markov Chains and Mixing Times, §10.1

    Определение первого достижения и отличие от первого возврата. Резольвента длительности, задача о чётности и проверки коэффициентов выведены здесь по первому шагу.

Доли времени и доли прыжков: стационарность полумарковской записи

В журнале посещений состояние B встречается с долей 2/5, но занимает половину физического времени. Причина — разные часы состояний. Одни и те же вероятности следующего имени ещё не задают распределение наблюдения в случайный момент.

Перед началом: Стационарный закон конечной цепи; Средняя награда на регенеративный цикл.

Счётчик записей и секундомер видят разные выборки

Конечная неприводимая вложенная цепь; положительные условно независимые длительности с конечными средними, зависящие от текущего состояния. Изучаются доли физического времени.

Пусть последовательность имён A,B,C задаётся вложенной цепью. Она говорит, какое состояние следует за очередной эпохой обновления. После входа в i процесс остаётся там случайное время H со средним μᵢ и только затем делает следующий переход. Условно по текущему i длительность независима от будущего перехода и остальных часов. Допускаются неэкспоненциальные распределения; положительность и конечные средние включены в модель.

Если ν — стационарный закон вложенной цепи, то среди большого числа записей доля i стремится к νᵢ. Но каждая такая запись приносит в среднем μᵢ секунд наблюдения. Поэтому длительные состояния чаще встречаются на фотографии, сделанной в равномерно выбранный момент большого временного интервала. Этот отбор по времени нельзя исправить простым подсчётом, сколько раз имя появилось в журнале.

Регенеративный цикл доказывает перевзвешивание

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

Пусть среднее число посещений i за цикл равно vᵢ. Средняя награда «время в i» равна vᵢμᵢ, а средняя длина цикла равна Σⱼvⱼμⱼ. Теорема о награде на цикл даёт долю времени πᵢ=vᵢμᵢ/Σⱼvⱼμⱼ. Нормированные v совпадают с ν, поэтому πᵢ=νᵢμᵢ/Σⱼνⱼμⱼ. Нужны именно средние длительности при соответствующем входе, а не средние обратных длительностей.

Предел доли времени не обещает предел каждого снимка

Полученная π описывает предел усреднения по физическому времени. При детерминированных арифметически согласованных часах распределение на фиксированной поздней дате может продолжать колебаться. Для утверждения о пределе такого распределения нужны дополнительные условия обновления либо корректный равновесный старт с возрастом текущего пребывания. Сам по себе стационарный выбор имени из ν не создаёт стационарного процесса в секундах.

Неэкспоненциальное пребывание также обычно лишает само имя состояния марковского свойства в непрерывном времени. Если известно, что процесс уже долго стоит в состоянии с ограниченной длительностью, остаточное время меняется. Возраст пребывания может стать дополнительной переменной описания. Это другая операция, чем цензурирование, которое удаляет часть имён и промежуточных тактов: здесь сохранены все имена, но изменена физическая шкала.

Один обязательный и один необязательный визит

Условие. Вложенная цепь: A→B всегда, B→A или C с вероятностями 1/2, C→A всегда. Часы A детерминированы 2с, B равномерны на[2,4]с, C экспоненциальны со средним 2с. Найдите доли посещений, доли времени и средний физический возврат в A.

  1. Баланс посещений даёт νB=νA, νC=νB/2. Нормировка приводит к ν=(2/5,2/5,1/5).
  2. Средние часы равны μ=(2,3,2)с. Перевзвешенные массы νᵢμᵢ равны(4/5,6/5,2/5)с, их сумма 12/5с.
  3. Деление на 12/5 даёт доли физического времени π=(1/3,1/2,1/6). Посещения B имеют долю 2/5, но его время —1/2.
  4. Цикл из A проходит A,B,A с вероятностью 1/2 и A,B,C,A с вероятностью 1/2. Его средние физические длины 5 и 7с, поэтому средний возврат равен 6с.
  5. Среднее число обновлений до возврата равно(2+3)/2=5/2, как и 1/νA. Физическое время 6с равно μA/πA=2/(1/3), а не безразмерному 1/πA=3.

Ответ. Доли посещений(2/5,2/5,1/5), доли времени(1/3,1/2,1/6); средний физический возврат в A равен 6с.

Проверка. В каждом цикле проводят в A ровно 2с, в B в среднем 3с, в C в среднем(1/2)·2=1с. Деление этих наград на среднюю длину 6с непосредственно даёт(1/3,1/2,1/6), независимо от вычисления ν.

Где легко ошибиться. Вероятность попасть в состояние на случайном переходе и вероятность увидеть его в случайную секунду — разные законы. Формулу Каца в числе переходов нельзя без единиц объявлять временем возврата в секундах.

Проверьте понимание

Какую долю физического времени занимает B в разобранном примере статьи?

Вопросы к этой главе

Нужна ли экспоненциальная форма всех часов?

Для приведённой формулы долей времени нет: достаточно объявленных конечных средних и условий обновления. Экспоненциальность понадобилась бы, чтобы само имя состояния описывало непрерывную марковскую цепь без возраста.

Сохранятся ли доли времени при умножении всех длительностей на два?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Robert Gallager, MIT6.262, Chapter6, §6.8 Semi-Markov processes

    Связь долей переходов со средними временами пребывания и различие временного усреднения и предела распределения. Вложенная трёхсостоянийная цепь и её часы заданы отдельно в примере.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться