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

Что означает распределение, которое не меняет шаг Маркова

Как найти неизменный закон состояния по уравнению πP=π, зачем нужна нормировка и почему решение ещё не обещает сходимость из любого старта.

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

В теме Случайные величины и распределения · Учебная карта

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

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

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

Неизменным остаётся распределение, а не объект

У автомата два состояния, А и Б. За шаг из А в Б он переходит с вероятностью 0,2, а из Б в А — с вероятностью 0,5. Остальные вероятности соответствуют сохранению состояния. Ищем начальную смесь, которую такая таблица воспроизводит после одного перехода. Обозначим вес А через u, вес Б через 1−u.

Условие для А записывается u=0,8u+0,5(1−u). Получаем 0,7u=0,5, откуда u=5/7. Вес Б равен 2/7. Это не означает, что автомат навсегда застыл в одном состоянии. Даже при стационарном старте переходы между состояниями остаются возможными; неизменна только вероятность наблюдать каждое из них в фиксированный момент.

Проверяем решение и сохраняем нормировку

Прямое умножение даёт новую вероятность А: (5/7)·0,8+(2/7)·0,5=5/7. Для Б получается 2/7. Можно также сравнить вероятностные потоки: (5/7)·0,2=(2/7)·0,5=1/7. Для двух состояний этот баланс вместе с нормировкой быстро даёт нужное отношение, но в общей цепи попарный баланс не обязателен.

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

Пример

Почему вектор (10;4) не является стационарным распределением, хотя сохраняется при умножении?

Он имеет правильное отношение компонентов, но сумму 14. После деления на 14 получится распределение (5/7;2/7).

Отделяем сохранение закона от его достижения

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

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

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

А теперь — вы

Из А в Б переходят с вероятностью 0,3, из Б в А — с вероятностью 0,2. Какова стационарная вероятность А в двухсостоянийной цепи?

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

Должны ли все стационарные веса быть равными?

Нет. Они зависят от переходов; в разобранной цепи веса 5/7 и 2/7 различны.

Что означает старт из стационарного закона?

Начальное состояние случайно выбирается с его весами. Тогда на каждом шаге сохраняется тот же закон, а не обязательно то же значение.

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

Формула Каца: среднее время возврата и стационарная масса

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

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

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

Для конечной неприводимой цепи Tᵢ⁺=min{n≥1:Xₙ=i} при старте i имеет среднее 1/πᵢ. Это формула Каца; она отличается от времени достижения i, которое при старте i равно нулю.

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

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

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

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

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

Формула не говорит, что возвращение произойдёт через ровно 1/πᵢ шагов. Даже целое значение среднего не означает детерминированного срока; распределение длин циклов остаётся отдельной задачей.

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

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

Условие. У цепи P=((1/2,1/2),(1/4,3/4)) найдите среднее время положительного возврата в A.

  1. Стационарный баланс даёт π_A/2=π_B/4, поэтому π_B=2π_A.
  2. Нормировка даёт π_A=1/3, π_B=2/3; цепь неприводима.
  3. Формула возврата даёт E_AT_A⁺=1/(1/3)=3 перехода.
  4. Для прямой проверки среднее достижение A из B равно четырём: один шаг завершается успехом с вероятностью 1/4.

Ответ. Среднее время положительного возврата в A равно трём шагам.

Проверка. Разложение первого шага даёт 1/2·1+1/2·(1+4)=3. Эта проверка использует распределение первого выхода, а не стационарную формулу.

Где легко ошибиться. Время достижения при старте в цели равно нулю; положительное время возврата отсчитывается с первого шага.

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

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

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

Мешает ли период два?

Нет. В детерминированном двухцикле стационарная масса состояния равна половине, а возврат всегда происходит через два шага; формула выполняется точно.

Почему нельзя брать любую стационарную смесь?

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

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

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

  • Gordan Žitković: Stationary Distributions

    HTML главы8 прочитан: стационарный старт и связь стационарной массы со средним положительным возвратом по теореме Каца.

Чувствительность стационарной смеси к изменению одного перехода

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

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

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

Для матрицы ((1−a,a),(b,1−b)) при a,b>0 баланс даёт π_A=b/(a+b), π_B=a/(a+b). Увеличение a уменьшает долю A, хотя сам переход начинается именно в A.

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

Дифференцирование нормированной дроби даёт ∂π_A/∂a=−b/(a+b)². Нельзя дифференцировать только числитель: знаменатель тоже зависит от параметров перехода. Аналогично ∂π_A/∂b=a/(a+b)².

Для конечного изменения Δa точная разность равна −bΔa/((a+b)(a+b+Δa)). Линейная чувствительность заменяет второй знаменатель первым и потому требует малого изменения относительно a+b.

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

При a=b=0 матрица единичная и стационарное распределение не единственно; дробь не определена. При очень малой сумме переходов даже небольшое абсолютное изменение параметра может быть большим относительным возмущением.

Найденная чувствительность относится к неизменным вероятностям в каждом такте. Она не описывает краткосрочный ответ системы, в которой параметры меняются быстрее, чем происходит смешивание.

Для малого изменения a на одну сотую точная новая масса равна 25/51, а линейный прогноз равен 49/100. Точная разность составляет 1/5100: 25/51−49/100=1/5100. Ошибка положительна, поскольку функция b/(a+b) выпукла по a при положительном b. Касательная лежит ниже графика, поэтому линейный прогноз уменьшения здесь систематически занижает точное значение. Эта геометрическая проверка объясняет знак ошибки без повторения дробной подстановки. Если одновременно умножить a и b на один положительный коэффициент, стационарная смесь не изменится, хотя скорость переходов и время смешивания изменятся.

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

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

Условие. Пусть a=b=1/4. Увеличьте a до 1/2 при том же b. Сравните точную новую π_A с линейным прогнозом.

  1. Исходная доля A равна (1/4)/(1/2)=1/2.
  2. После изменения точная доля равна (1/4)/(3/4)=1/3.
  3. Исходная производная по a равна −(1/4)/(1/2)²=−1.
  4. Линейный прогноз равен 1/2−1·1/4=1/4; ошибка относительно точного ответа равна −1/12.

Ответ. Новая доля A равна 1/3; линейный прогноз 1/4 заметно занижает её.

Проверка. В новой матрице баланс потока проверяется напрямую: (1/3)(1/2)=(2/3)(1/4)=1/6. Прогноз 1/4 этот баланс не удовлетворяет.

Где легко ошибиться. Локальная производная не является точной конечной разностью, особенно при изменении, сравнимом с суммой переходных вероятностей.

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

При фиксированном a>0 увеличение b приводит к

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

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

Увеличивается вероятность выхода из A при неизменном возврате из B. Доля времени в A уменьшается, что согласуется с уравнением встречных потоков.

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

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

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

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

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

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

Квазистационарный закон при условии выживания

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

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

Сохраняются относительные доли выживших

Выделим конечный набор живых состояний и субстохастическую матрицу Q переходов между ними. Недостающая до единицы сумма каждой строки означает вероятность поглощения за один шаг. Для начального вероятностного вектора q ненормированная масса живых состояний через один шаг равна qQ, а её сумма qQ1 есть вероятность выживания.

Квазистационарность означает qQ=λq при 0<λ≤1 и Σqᵢ=1. После деления на вероятность выживания λ относительные доли снова равны q. Это левый собственный вектор: замена его правым собственным вектором обычно даёт другие числа и не описывает распределение состояний.

Условная неизменность не запрещает поглощение

Из qQ=λq следует qQᵗ=λᵗq на каждом целом горизонте. Поэтому P(T>t)=λᵗ при старте q, если T — первый поглощающий шаг и X₀ живо. Условный закон Xₜ при T>t остаётся q, хотя безусловная вероятность живого набора стремится к нулю при λ<1.

Для старта q длительность имеет геометрический закон с первым возможным поглощением на шаге один; её среднее равно 1/(1−λ). Из произвольного отдельного состояния эти формулы не обязаны выполняться. Условное равновесие и распределение времени жизни относятся к оговорённому начальному смешению.

Условия предела нужно проверять отдельно

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

При непосредственной проверке удобно умножить кандидат q на Q и сравнить все координаты с одной общей λ. Нормировка каждой координаты своим множителем уничтожила бы смысл собственного вектора. Также проверяют неотрицательность Q и остаточные вероятности поглощения, чтобы алгебраическая задача действительно описывала вероятностную модель.

Два живых состояния с разным риском поглощения

Условие. Живой блок равен Q=((1/2,1/8),(1/8,11/16)); остаток строки ведёт в поглощение. Проверьте q=(1/3,2/3), найдите вероятность выживания двух шагов и условный закон после них.

  1. Суммы строк равны 5/8 и 13/16. Вероятности поглощения 3/8 и 3/16 различны и неотрицательны.
  2. Умножение qQ даёт (1/4,1/2). Его сумма 3/4, а нормирование возвращает (1/3,2/3), поэтому λ=3/4.
  3. Через два шага ненормированная живая масса равна (3/4)²q=(3/16,3/8). Её сумма 9/16.
  4. Условный закон живых после двух шагов снова q. Для этого же начального смешения среднее время до поглощения равно 1/(1−3/4)=4 шага.

Ответ. Вероятность двухшагового выживания 9/16; условные доли (1/3,2/3), среднее время жизни 4.

Проверка. Прямая сумма масс всех живых путей длины два даёт (3/16,3/8) без использования собственного вектора. Полная цепь с единственным поглощающим состоянием имеет иной стационарный закон: вся масса находится в поглощении.

Где легко ошибиться. Нельзя нормировать живые строки Q по отдельности и считать полученную цепь исходной моделью при условии многократного выживания. Вероятность отбора живого состояния зависит от пути; последовательное условие на конечный срок обычно меняет переходы иначе.

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

Каков условный закон двух живых состояний после двух шагов при указанном старте q и условии выживания?

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

Почему общий спад не виден в условном распределении?

Условие оставляет только выживших и делит все живые массы на их общую сумму. Множитель λᵗ сокращается, хотя в безусловной модели он определяет быстро уменьшающуюся вероятность самого события.

Что означает λ=1?

При старте q потери живой массы нет. Это граничный случай без поглощения на носителе q, поэтому формула конечного среднего 1/(1−λ) уже не даёт конечного времени жизни.

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

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

  • Ferrari et al., Adv. Appl. Prob. 24 (1992), definition of quasi-stationarity

    Прочитан индексированный первичный фрагмент определения условного закона и левого собственного вектора. Прямой PDF дал timeout; вся статья и общий Yaglom-limit не заявлены прочитанными. Конечный пример проверен точным умножением и путями.

Стационарный закон из ориентированных остовных деревьев

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

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

Корень собирает направленные пути

Пусть конечная матрица P неприводима. Для корня j рассматриваем остовные деревья, в которых из каждой другой вершины выходит ровно одно ребро и движение по рёбрам приводит к j. У корня исходящего ребра нет. Цикл среди остальных вершин недопустим, поскольку он не позволяет достичь корня.

Вес дерева равен произведению вероятностей Pᵢₖ его направленных рёбер. Переход с нулевой вероятностью делает вес нулевым. Суммируем веса деревьев одного корня и получаем τⱼ. Теорема о деревьях марковской цепи утверждает, что нормированные τⱼ образуют её стационарный закон.

Вероятностная нормировка существенна

Формула имеет вид πⱼ=τⱼ/Στₖ. Число деревьев и сумма их весов совпали бы только при специальных одинаковых весах; произвольная матрица требует учитывать каждое произведение. Даже если один ненормированный вес меньше единицы, это ещё не делает его стационарной вероятностью.

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

Подстановка проверяет вероятностный результат

После вычисления деревьев нужно проверить πP=π и сумму координат. Такая проверка использует другую структуру вычисления: потоки по всем входящим переходам, а не перечень деревьев. Для трёх состояний обе процедуры легко выполнить точными дробями и обнаружить ошибку направления одного ребра.

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

Три корня с неравными стохастическими весами

Условие. Для P=((0,1/2,1/2),(1/4,0,3/4),(1/3,2/3,0)) найдите стационарный закон через ориентированные деревья, направленные к корню.

  1. Для первого корня три допустимых произведения равны 1/12,1/6,1/4. Их сумма τ₁=1/2.
  2. Для второго корня получаем 1/3,1/6,1/3, то есть τ₂=5/6. Для третьего — 3/8,3/8,1/8, поэтому τ₃=7/8.
  3. Общая нормировка равна 1/2+5/6+7/8=53/24. Деление даёт π=(12/53,20/53,21/53).
  4. Входящий поток первой координаты равен 20/(4·53)+21/(3·53)=12/53. Аналогично вторая получает 6/53+14/53=20/53, третья — 6/53+15/53=21/53.

Ответ. Стационарный закон равен (12/53,20/53,21/53).

Проверка. Проверка потоков не использует списки деревьев. Кроме того, π₁P₁₂=6/53 и π₂P₂₁=5/53: цепь действительно необратима, но её стационарность подтверждена отдельно.

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

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

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

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

Нужно ли включать петли в дерево?

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

Что делать с приводимой цепью?

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

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

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

  • Aldous–Fill, §9.2, Corollary 9.11

    Прочитаны определение направленных весов, теорема 9.10 и нормировка вероятностей корней в 9.11. Собственная трёхсостоянийная матрица проверена деревьями и отдельной подстановкой потоков.

Стационарный круговой ток: закон состояния без детального баланса

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

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

Поток имеет два направления

При стационарном старте совместная масса перехода i→j равна Fᵢⱼ=πᵢPᵢⱼ. Направленный ток Jᵢⱼ=Fᵢⱼ−Fⱼᵢ меняет знак при перестановке индексов. Стационарность означает ΣⱼJᵢⱼ=0: из каждой вершины выходит столько же вероятности, сколько входит. Она допускает ненулевой ток по контуру, потому что каждая вершина контура одновременно принимает и передаёт одну и ту же величину.

Обратимость проверяет каждое ребро

Детальный баланс требует Jᵢⱼ=0 для всех пар. Тогда конечные стационарные записи не различают направление времени. В трёх состояниях можно иметь одинаковые входящие и исходящие суммы, но разные вероятности кругового движения по часовой стрелке и против неё. Для положительных переходов произведения вероятностей вдоль контура и обратного контура должны совпадать у обратимой цепи. Нарушение этого необходимого условия сразу опровергает обратимость без решения всех попарных уравнений.

Что измеряет наблюдение переходов

Частоты состояний оценивают π и сами по себе не восстанавливают ток. Для его оценки нужны пары последовательных наблюдений с согласованным шагом времени. Одни и те же равномерные массы совместимы с симметричным случайным блужданием, направленным циклом и независимым выбором нового состояния. Конечная разность частот переходов содержит выборочный шум; точный нулевой ток модели нельзя объявлять нарушенным по любому единичному несовпадению счётчиков.

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

Условие. В трёх состояниях по кругу вероятность шага вперёд равна 1/2, назад 1/4, удержания 1/4. Найдите стационарный закон, ток ребра и отношение вероятностей полного прямого и обратного обходов из нуля.

  1. Циклическая симметрия даёт равномерную кандидатуру π=(1/3,1/3,1/3); каждый столбец P суммируется в один, подтверждая её.
  2. Прямой поток любого ориентированного ребра круга равен (1/3)(1/2)=1/6. Встречный поток равен (1/3)(1/4)=1/12.
  3. Ток вдоль круга равен 1/12. В каждой вершине один такой ток входит и один выходит, поэтому сумма токов нулевая.
  4. Вероятности трёхшаговых обходов при фиксированном старте равны (1/2)³ и (1/4)³. Их отношение равно восьми, что исключает обратимость.

Ответ. Стационарные массы равны 1/3; ток каждого ребра по кругу равен 1/12; прямой обход в восемь раз вероятнее обратного.

Проверка. Вычислим изменение массы нуля напрямую: вход от соседей равен 1/6+1/12, выход из нуля к ним равен той же четверти. Это проверяет стационарность независимо от отдельного токового вычисления.

Где легко ошибиться. Нулевая сумма токов у вершины не требует нуля каждого слагаемого. Проверка только πP=π поэтому недостаточна для вывода о детальном балансе или симметрии записей.

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

Что следует из стационарности в этой задаче?

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

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

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

Меняется ли ток при добавлении одинаковой вероятности остановки?

Если новая матрица равна aI+(1−a)P, стационарный закон сохраняется, а каждый внедиагональный ток умножается на 1−a. Направление остаётся прежним, интенсивность на шаг уменьшается.

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

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

  • Hao Wu, MIT 18.445, Lecture 3

    Стационарность и детальный баланс: равенство суммарных потоков не требует нулевого тока каждого ребра.

Необратимость пути: производство энтропии стационарного потока

Две цепи на четырёх вершинах могут иметь одинаковый стационарный ток 1/16 и разную KL-необратимость: (1/4)ln(5/3) против (1/4)ln3. Сравним полные вероятности прямых и обратных записей, не приписывая им автоматически физическое тепло.

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

Одинаковая частота состояний скрывает направление записи

Полностью наблюдаемая конечная цепь при стационарном старте с положительными массами; информационная KL-необратимость в натах на переход.

Рассмотрим кольцо из четырёх состояний. Вероятности движения вперёд и назад обозначим p и q, оставшаяся масса даёт удержание. При одинаковых строках с циклическим сдвигом стационарный закон равномерен. Ток одного направленного ребра равен (p−q)/4. Этот ток замечает асимметрию, но ещё не сообщает, насколько легко отличить длинную запись от той же записи в обратном порядке.

Для общей цепи положим Fᵢⱼ=πᵢPᵢⱼ. Это нормированное совместное распределение двух соседних состояний. Развёрнутая пара имеет закон Fⱼᵢ. Его KL-расхождение с прямой парой равно σ=ΣᵢⱼFᵢⱼln(Fᵢⱼ/Fⱼᵢ). Здесь натуральный логарифм задаёт наты на один переход. Это статистическая мера различимости; для отождествления с термодинамическим производством энтропии нужны дополнительные физические условия о наблюдаемом состоянии и локальном детальном балансе.

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

Неотрицательность σ следует из информационного неравенства для двух нормированных законов. Нуль возможен ровно при F=Fᵀ, то есть при детальном балансе на рассматриваемой поддержке. Можно также объединить встречные рёбра: вклад неупорядоченной пары равен (Fᵢⱼ−Fⱼᵢ)ln(Fᵢⱼ/Fⱼᵢ), который неотрицателен, поскольку разность и логарифм имеют одинаковый знак. Диагональные переходы вклада не дают.

Вероятность стационарного пути i₀,…,iₙ равна πᵢ₀∏Pᵢₖᵢₖ₊₁. Сравним её с вероятностью перевёрнутой последовательности при той же исходной модели P. Логарифм отношения содержит граничную разность lnπᵢ₀−lnπᵢₙ и сумму логарифмов встречных переходов. Стационарность зануляет среднее граничной разности. Каждый из n переходов имеет один закон F, поэтому KL полных записей в точности равно nσ. Независимость последовательных переходов для этого не требуется.

Ток и логарифмическая цена измеряют разное

При кольцевой симметрии суммирование всех направлений сокращается до σ=(p−q)ln(p/q). Разность вероятностей задаёт ток, а отношение задаёт второй множитель. Сохранив разность, можно изменить общий оборот встречных переходов и тем самым изменить σ. Значит из одного оценённого тока нельзя восстановить информационную необратимость без самих потоков.

Если прямой поток положителен, а встречный нулевой, некоторую прямую запись обратная модель считает невозможной и KL бесконечна. При нулевых обоих потоках пары просто не вносят вклад. Если видны лишь укрупнённые состояния, наблюдаемая последовательность может потерять марковское свойство: тогда расчёт по соседним парам не обязан описывать всю необратимость длинной записи. Формула nσ здесь относится к полностью наблюдаемой марковской модели с объявленным стационарным стартом.

Одинаковый ток, разные KL-скорости

Условие. В кольце 0–1–2–3 сравните стационарные цепи A: p=5/8,q=3/8,удержание 0 и B: p=3/8,q=1/8,удержание 1/2. Найдите ток каждого ребра, σ и KL для записи из четырёх переходов.

  1. Обе матрицы имеют единичные суммы столбцов, поэтому πᵢ=1/4. Разность p−q в обеих равна 1/4; ток ребра равен (1/4)(1/4)=1/16.
  2. У цепи A прямой поток равен 5/32, встречный 3/32. Вклад одной неупорядоченной пары равен (2/32)ln(5/3). На кольце четыре такие пары.
  3. Поэтому σA=(1/4)ln(5/3). У B потоки равны 3/32 и 1/32, давая σB=(1/4)ln3. Удержания не добавляют KL.
  4. Поскольку 3>5/3, вторая величина больше первой, хотя направления и величины токов совпадают. Необратимость не определяется только их разностью.
  5. Для четырёх переходов KL полных записей равно 4σ: ln(5/3) для A и ln3 для B. Временной горизонт здесь считает переходы, поэтому в записи пять последовательных состояний.

Ответ. Ток в обеих цепях равен 1/16. σA=(1/4)ln(5/3), σB=(1/4)ln3; для четырёх переходов KL равны ln(5/3) и ln3.

Проверка. Можно независимо перечислить все 4⁵ записей пяти состояний, назначить каждой массу (1/4)∏Pᵢⱼ, сравнить с массой обратного слова и сложить p·ln(p/q). Ненулевые встречные вероятности обеспечивают конечность; суммы дают соответственно ln(5/3) и ln3.

Где легко ошибиться. Не сравнивайте σ только с суммой токов: встречные токи меняют знак и могут сократиться, тогда как KL использует ещё логарифмические отношения. Кроме того, наты на переход без физической модели не являются джоулями или теплом.

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

Какая KL-необратимость на переход больше в двух цепях разобранного примера статьи?

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

Нужна ли апериодичность для равенства KL=nσ?

Нет. Достаточен уже заданный стационарный старт и марковское разложение пути. Цепь A на чётном кольце периодична, но равенство для её стационарных записей сохраняется.

Почему вторая цепь различима сильнее при более частых остановках?

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

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

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

  • Roldán–Parrondo, Entropy production and Kullback–Leibler divergence, §II

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

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

У трёхбитного окна все семь нетривиальных собственных значений нулевые. Тем не менее одно- и двухшаговая операторные нормы равны единице; полное забывание наступает только на третьем шаге. Причина находится в сохранённых битах, а не в усилении нормы.

Перед началом: Равномерный стационарный закон; Операторная норма и условное ожидание.

Каждый шаг стирает ровно один старый бит

Цепь всех двоичных слов фиксированной длины k≥1: сдвиг влево и независимый новый честный бит. Норма относится к центрированным функциям в равномерном L².

Состояние — слово(a₁,…,aₖ). За шаг выбрасывается первый бит, оставшиеся сдвигаются, справа добавляется независимый честный бит. У каждого слова два возможных продолжения с вероятностями по 1/2. Равномерный закон на 2ᵏ словах стационарен: к каждому слову ведут два предшественника, чьи последниеk−1 битов совпадают с его первымиk−1.

После k шагов все исходные биты заменены новыми независимыми, поэтому каждая строка Pᵏ равна равномерному распределению. Обозначим эту матрицу J. Получаем Pᵏ=J и Pᵗ=J при любом t≥k. Цепь неприводима, поскольку за k шагов можно построить любое слово, и апериодична, поскольку нулевое слово допускает самопереход. Но отсутствие периода не сообщает, сколько исходных координат ещё осталось на ранних датах.

Нулевой спектр не означает нулевое действие за один шаг

Постоянная функция имеет собственное значение один. На центрированном пространстве J действует нулём, поэтому ограничение P имеет k-ю степень ноль: все его собственные значения нулевые. Размер пространства равен 2ᵏ−1. Это спектральное утверждение не определяет норму каждого промежуточного произведения, поскольку оператор не обязан иметь ортогональный собственный базис.

Для любой стационарной цепи неравенство Йенсена даёт ‖Pf‖²π≤ΣᵢπᵢΣⱼPᵢⱼfⱼ²=‖f‖²π. Значит усиления здесь нет. Возьмём центрированную функцию f(a)=(-1)ᵃ¹ с нормой один. При t<k её условное среднее после t шагов равно(-1)ᵃᵗ⁺¹: соответствующий исходный бит ещё не выброшен. Норма результата тоже один. Поэтому точная норма Pᵗ на центрированных функциях равна 1 при t<k и 0 при t≥k. Включение t=0 соответствует единичному оператору.

Распределение из точки имеет собственную точную кривую

Если начальное слово известно, после t<k шагов остаётся заданный суффикс длиныk−t, а t новых битов равномерны. Достижимы 2ᵗ слов с массами 2⁻ᵗ каждое. Их общий равномерный вес равен 2ᵗ⁻ᵏ. Поэтому расстояние полной вариации до равномерного закона равно 1−2ᵗ⁻ᵏ. После k шагов оно нулевое. Этот расчёт относится к любому фиксированному начальному слову и тем самым даёт худший старт.

При произвольной начальной смеси возможны меньшие расстояния: стационарная смесь уже имеет нулевое расстояние в дату ноль. Операторная норма, худший старт и конкретный начальный закон — три разных объекта. Формулы не следует переносить на другое правило обновления, где биты лишь иногда заменяются. Здесь конечное полное забывание вытекает из точного сдвига окна; оно не является общим свойством матриц с малым спектральным радиусом.

Три бита, восемь состояний и три шага

Условие. Слова 000…111 пронумерованы 0…7 в двоичном порядке. За шаг добавляется честный новый бит. Старт 101. Найдите законы после одного, двух и трёх шагов, их TV до uniform и центрированные операторные нормы.

  1. Строки P с номерами 0 и 4 имеют по 1/2 в столбцах 0,1; строки 1 и 5 — в 2,3; строки 2 и 6 — в 4,5; строки 3 и 7 — в 6,7. Остальные элементы нулевые.
  2. Из 101 после одного шага возможны 010 и 011 с вероятностями по 1/2. Uniform даёт каждой из восьми точек 1/8, поэтому TV=1−2/8=3/4.
  3. После двух шагов сохраняется только последний исходный бит 1: состояния 100,101,110,111 имеют массы по 1/4. Получаем TV=1−4/8=1/2.
  4. После трёх шагов все восемь слов имеют массу 1/8; TV=0. Прямое матричное произведение P³=J проверяет, что это верно не только для старта 101.
  5. Функция первого бита переходит за один и два шага в функции второго и третьего битов с нормой 1. Значит центрированные нормы P и P² равны 1, а P³ равна 0. Все нетривиальные собственные значения при этом нулевые.

Ответ. Законы: uniform на{010,011}, затем на{100,101,110,111}, затем на всех восьми словах. TV:3/4,1/2,0. Центрированные L²-нормы:1,1,0.

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

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

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

Какова центрированная L²-норма P² у трёхбитной цепи разобранного примера статьи?

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

Почему TV уменьшается, когда операторная норма ещё равна единице?

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

Есть ли в этом примере временное усиление?

Нет. Стационарная марковская матрица сокращает L² по Йенсену. Здесь до срока сохраняется норма одного направления, затем оно стирается; это отличается от роста нормы в произвольной ненормальной или демографической матрице.

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

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

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

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

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

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

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