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

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

Как чередование состояний мешает предельному закону при определённом старте и почему это совместимо с существованием стационарной смеси.

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

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

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

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

Цепь может иметь стационарное распределение, но не сходиться к нему из отдельного состояния. При обязательном чередовании А и Б закон зависит от чётности шага, хотя смесь (1/2;1/2) сохраняется.

Проверяем законы на чётных и нечётных шагах

Пусть автомат всегда переводит А в Б, а Б в А. Переходная матрица имеет строки (0;1) и (1;0). Если стартовать в А, после первого шага состояние точно Б, после второго — точно А. Затем всё повторяется. Вероятность А равна единице на чётных шагах и нулю на нечётных, поэтому общего предела у неё нет.

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

Период задают возможные времена возврата

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

Добавим вероятность 0,1 остаться на месте и 0,9 перейти в другое состояние. Теперь возврат возможен уже через один шаг, период становится единицей. Равная стационарная смесь сохранится, но отклонение от неё за шаг умножается на −0,8. Знак продолжает чередоваться, а модуль отклонения уменьшается; это затухающие колебания, а не прежнее вечное переключение.

Пример

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

Пути А–А–А и А–Б–А дают 0,1²+0,9²=0,82. Значение ещё далеко от половины, но последовательные отклонения постепенно уменьшаются.

Среднее по времени отвечает на другой вопрос

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

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

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

А теперь — вы

Автомат движется строго А→Б→В→А. Старт точно в А. Какова вероятность А после 8 переходов?

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

Периодическая цепь обязательно не имеет стационарного закона?

Нет. У строгого чередования закон (1/2;1/2) стационарен, хотя определённый старт не даёт сходимости распределения.

Достаточно ли назвать число состояний, чтобы узнать период?

Нет. Период определяется общим делителем разрешённых времён возврата, поэтому зависит от переходов.

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

Скелет периодической цепи: число классов через наибольший общий делитель

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

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

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

Скелет с шагом m — последовательность Yₖ=Xₘₖ. Его переходная матрица равна Pᵐ. Хотя исходная цепь может связывать все состояния, пропуск промежуточных дат способен разделить наблюдаемое движение на недоступные друг другу классы.

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

Для детерминированного цикла длины d каждый скелетный переход прибавляет m по модулю d. Достижимые остатки образуют подгруппу, порождённую m. Её размер равен d/gcd(d,m), а число разных смежных классов равно gcd(d,m).

Равенство jm≡0 mod d впервые выполняется при j=d/gcd(d,m). Поэтому это одновременно длина нового цикла и положительное время возврата в скелетных тактах. Умножение на m переводит срок в исходные такты, но пропущенные возвращения при этом не наблюдаются.

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

Для общей неприводимой цепи периода d матрица Pᵐ также делится на gcd(d,m) неприводимых классов; детерминированный пример делает механизм видимым без дополнительных переходов внутри фаз. У каждого класса может быть собственный нормированный стационарный закон.

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

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

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

Условие. Исходная цепь идёт по циклу 0→1→2→3→4→5→0. Наблюдайте каждое четвёртое исходное состояние. Найдите классы скелета и средний положительный возврат из нуля.

  1. Шаг скелета прибавляет четыре по модулю шесть. Наибольший общий делитель шести и четырёх равен двум.
  2. Из нуля получаем последовательность 0→4→2→0; первый класс равен {0,2,4}.
  3. Из единицы получаем 1→5→3→1; второй класс равен {1,3,5}. Между классами переходов нет.
  4. Возврат в ноль занимает ровно три скелетных такта, то есть двенадцать исходных тактов наблюдаемого горизонта.

Ответ. Есть два класса по три состояния; положительный возврат занимает три скелетных такта.

Проверка. Прямое перечисление остатков 4j mod6 при j=0,1,2,3 даёт 0,4,2,0. Ни одна нечётная метка не появляется; отдельный нечётный старт покрывает оставшиеся три метки.

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

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

Сколько классов имеет скелет детерминированного цикла длины d с шагом m?

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

Сохранилось ли равномерное распределение?

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

Что будет при наблюдении каждого пятого шага?

Общий делитель пяти и шести равен единице. Все шесть меток останутся в одном цикле, который обходится в обратном по сравнению с исходным порядке.

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

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

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

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

Автоковариация стационарной цепи: периодический режим и ошибка среднего

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

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

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

В двухсостоянийной стационарной цепи обозначим Iₜ=1 при Xₜ=A. Пусть π=P(Xₜ=A), а λ=1−a−b для матрицы ((1−a,a),(b,1−b)). Тогда Cov(I₀,Iₖ)=π(1−π)λᵏ.

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

Условное среднее Iₖ при известном I₀ равно π+λᵏ(I₀−π). Умножение центрированных величин и усреднение даёт формулу ковариации. Отрицательный λ порождает чередующиеся знаки, поэтому соседние наблюдения способны уменьшать дисперсию среднего.

Для среднего из n дат дисперсия равна π(1−π)[n+2Σₖ₌₁ⁿ⁻¹(n−k)λᵏ]/n². Множитель n−k считает пары дат на расстоянии k. Простое деление индивидуальной дисперсии на n выбрасывает все эти пары.

Стационарная таблица двух последовательных состояний
ПараВероятностьСредний индикатор
AA1/81
AB3/81/2
BA3/81/2
BB1/80

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

Формула требует стационарного старта. Из фиксированного состояния средние и ковариации ранних дат зависят от времени, и стационарное выражение применять нельзя без поправки. При |λ|<1 и большом n асимптотический множитель ошибки равен (1+λ)/(1−λ).

В точном двухцикле λ=−1 этот предельный вывод по сходящемуся геометрическому ряду неприменим. Тем не менее конечная формула сохраняется. Среднее по чётному числу дат тогда может иметь нулевой разброс, хотя каждое отдельное состояние случайно при стационарной смеси. Это различает зависимость данных и изменчивость их среднего.

Для стационарной симметричной цепи с вероятностью смены три четверти имеем π=1/2 и λ=−1/2. Ковариация соседних индикаторов равна минус одной восьмой, а через два шага — одной шестнадцатой. Нулевой общий средний сдвиг не устраняет эти связи. Если отбирать лишь каждую вторую дату, отрицательная соседняя связь сменится положительной, потому что новый множитель равен λ². Поэтому прореживание временной последовательности способно ухудшить эффективность среднего при таком чередующемся режиме.

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

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

  1. Симметрия даёт стационарную массу A, равную половине; дисперсия отдельного индикатора равна 1/4.
  2. Вероятность двух A равна (1/2)(1/4)=1/8, поэтому ковариация равна 1/8−1/4=−1/8.
  3. Дисперсия суммы двух индикаторов равна 1/4+1/4+2(−1/8)=1/4.
  4. Деление суммы на два уменьшает дисперсию вчетверо; окончательный результат равен 1/16.

Ответ. Дисперсия среднего двух стационарных индикаторов равна 1/16.

Проверка. Четыре пары AA,AB,BA,BB имеют вероятности 1/8,3/8,3/8,1/8. Среднее индикаторов принимает 1,1/2,1/2,0; прямой центральный момент равен 1/16.

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

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

Какой множитель учитывает число пар дат с лагом k в выборке из n дат?

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

Почему отрицательная связь помогает среднему?

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

Что даст независимая формула?

Она дала бы 1/8 вместо 1/16 и завысила бы дисперсию. При положительной автоковариации такая же подмена обычно занизила бы неопределённость.

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

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

  • Sébastien Roch: спектральные методы, Chapter 5

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

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

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

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

Независимость является частью определения

Пусть π — стационарный закон цепи, а T — допустимое рандомизированное время остановки. Требование записывается как P(X_T=j,T=t)=πⱼP(T=t) для всех состояний j и времён t. Оно одновременно задаёт закон X_T и независимость X_T от T. Одной формулы P(X_T=j)=πⱼ недостаточно.

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

Неостановившаяся масса ограничивает separation

При T≤t последующее развитие из стационарного закона сохраняет π. Поэтому P(X_t=j,T≤t)=πⱼP(T≤t), а полная вероятность X_t=j не меньше этой массы. Получаем P(X_t=j)≥(1−P(T>t))πⱼ одновременно для всех j.

Если все πⱼ положительны, separation определяется как 1−minⱼ P(X_t=j)/πⱼ. Предыдущее неравенство даёт separation≤P(T>t). Это покоординатная нижняя гарантия, отличная от суммы абсолютных отклонений в полной вариации. В конкретной модели равенство устанавливают отдельным состоянием, достигающим минимума.

Случайный сброс может прервать периодическое движение

Рассмотрим перемешивание двух механизмов: с вероятностью a выполняется независимый сброс по π, а иначе применяется перестановка R, сохраняющая π. Первый сброс является сильным стационарным временем. Его номер зависит только от последовательности признаков сброса, а новое состояние разыгрывается независимо по π.

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

Перестановка двух состояний и независимый сброс

Условие. Есть состояния A,B,C и π=(1/4,1/4,1/2). На каждом шаге с вероятностью 1/3 независимо выполняется сброс по π; иначе A и B меняются местами, C остаётся C. Начало A. Пусть T — первый сброс. Найдите P(T>3), закон X₃ и P(X_T=B,T=3).

  1. Перестановка сохраняет π, поскольку массы A и B равны. Независимый сброс также сохраняет π, значит их смесь имеет заданный стационарный закон.
  2. Три отсутствия сброса имеют вероятность (2/3)³=8/27. На этой ветви X₃=B; на всех остальных ветвях последнее состояние имеет закон π.
  3. Поэтому закон X₃ равен (19/27)π+(8/27)δ_B=(19/108,51/108,38/108). Минимальное отношение к π равно 19/27, separation равна 8/27.
  4. Первый сброс на третьем шаге имеет вероятность (2/3)²(1/3)=4/27. Независимый выбор B при сбросе даёт совместную вероятность (4/27)(1/4)=1/27.

Ответ. P(T>3)=8/27; закон X₃=(19,51,38)/108; P(X_T=B,T=3)=1/27.

Проверка. Полный перебор трёх признаков сброса и значений новых состояний отдельно подтверждает распределение. Равенство совместной массы произведению 4/27 и 1/4 проверяет независимость именно для события T=3, а формула первого сброса доказывает её для всех t.

Где легко ошибиться. Не называйте сильным временем любую остановку, после которой маргинальный результат случайно имеет π. Если длительность сообщает информацию о конечном состоянии, разложение уже остановившейся массы на каждой дате не следует и указанная граница separation не обоснована.

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

Какова совместная вероятность X_T=B и T=3 в задаче?

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

Обязано ли T быть видимым только по текущему состоянию?

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

Почему оставшаяся часть в примере сосредоточена в B?

При отсутствии всех трёх сбросов выполняется ровно три перестановки A↔B. Из начального A нечётное число таких перестановок приводит в B, без дополнительной неопределённости.

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

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

  • Aldous–Fill, §9.1.1 Strong stationary times

    Прочитаны определение с независимостью X_T и T и separation-tail theorem. Собственная смесь перестановки трёх состояний и неравномерного сброса проверена непосредственно.

Цензурированная цепь: последовательность возвращений в выбранное подмножество

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

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

Удаляются моменты наблюдения, а не состояния пути

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

Предполагаем, что из исключаемой части цепь возвращается в A с вероятностью один. Для конечного разбиения достаточно спектрального радиуса P_BB меньше единицы. Тогда геометрический ряд матриц Σₖ≥₀P_BBᵏ сходится и равен (I−P_BB)⁻¹. Без возврата цензурированная запись может закончиться, поэтому стохастичность нельзя обещать автоматически.

Экскурсии суммируются по их длине

Следующий записанный переход либо сразу остаётся в A, либо начинается переходом в B, проводит там k шагов и впервые возвращается в A. Сумма этих взаимоисключающих возможностей даёт S=P_AA+P_AB(I−P_BB)⁻¹P_BA. Порядок блоков следует направлению траектории и существенен.

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

Стационарные доли и время имеют разные шкалы

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

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

Два записываемых состояния и одно скрытое

Условие. Исходные строки для состояний A,B,C равны (1/4,1/4,1/2), (1/2,1/4,1/4), (1/4,1/4,1/2). Записываются только посещения A или B, все такты C удаляются. Найдите матрицу следующего записанного состояния.

  1. Из C каждый шаг возвращает в A с вероятностью 1/4, в B с вероятностью 1/4 или снова даёт C с вероятностью 1/2. Итоговые вероятности первого возвращения равны 1/2 и 1/2.
  2. Из A следующий записанный A получается немедленно с вероятностью 1/4 либо после ухода в C: (1/2)(1/2). Сумма равна 1/2; вероятность следующего B также 1/2.
  3. Из B следующий записанный A имеет вероятность 1/2+(1/4)(1/2)=5/8. Оставшаяся вероятность следующего B равна 3/8.
  4. Матрица S=((1/2,1/2),(5/8,3/8)). Простое нормирование сохраняемого блока дало бы во второй строке (2/3,1/3), исключив положительную массу скрытых экскурсий.

Ответ. Цензурированная матрица равна ((1/2,1/2),(5/8,3/8)).

Проверка. Первоначальная стационарная мера равна (5/16,4/16,7/16). Её нормирование на A,B даёт (5/9,4/9), что прямым умножением сохраняется матрицей S. Расчёт вероятности возврата через геометрический ряд 1/4+1/8+…=1/2 независимо проверяет вклад C.

Где легко ошибиться. Нельзя считать новый шаг одним исходным тактом. В частности, переход A→C→C→B даёт один записанный переход A→B, хотя занимает три исходных шага. Цензурирование меняет временную шкалу и требует отдельного учёта длительностей для временных показателей.

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

Какова вероятность следующего записанного A после записанного B в задаче?

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

Что если из скрытого состояния можно никогда не вернуться?

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

Достаточно ли удалить скрытую строку и нормировать остальные?

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

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

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

  • Meyer: Stochastic complementation, uncoupling Markov chains

    Прочитан индексированный фрагмент первичного авторского текста с формулой стохастического дополнения и цензурированной интерпретацией. Прямой PDF дал timeout; полного чтения статьи нет. Возвратная формула и пример выведены по экскурсиям здесь.

Оптимальное удержание: минимакс двух спектральных краёв

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

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

Сначала задайте, что именно минимизируется

Пусть P — матрица конечной неприводимой обратимой цепи со стационарным законом π. Обратимость означает πᵢPᵢⱼ=πⱼPⱼᵢ. На функциях состояний используем скалярное произведение ⟨f,g⟩π=Σᵢπᵢfᵢgᵢ и норму, заданную его квадратным корнем. Центрированными называем функции с Σᵢπᵢfᵢ=0. Постоянная функция исключена: она всегда сохраняется и потому сделала бы полную операторную норму равной единице.

Выбираем a из закрытого отрезка [0,1] и заменяем переход на Pₐ=aI+(1−a)P. Каждый такт включает возможное удержание. Цель — минимизировать ρ(a)=sup ‖Pₐf‖π/‖f‖π по ненулевым центрированным f. Это худшее однократное сжатие в L²(π), а не стоимость вычислений, не дисперсия выбранного среднего и не точное время достижения заданного расстояния полной вариации.

Два края дают глобальный сертификат

Из обратимости P самосопряжён в выбранном скалярном произведении. У него есть ортогональный базис собственных функций с вещественными значениями. Обозначим наибольшее нетривиальное значение через s<1, наименьшее через t≥−1. Одна и та же функция после удержания получает множитель a+(1−a)λ. Модуль аффинной функции от λ достигает максимума на краях [t,s], поэтому ρ(a)=max(|s+(1−s)a|,|t+(1−t)a|). Промежуточные моды не требуют отдельного подбора параметра.

Если s+t<0, уравняйте верхний край u=s+(1−s)a с противоположным нижним краем −l=−t−(1−t)a. Получим a*=−(s+t)/(2−s−t) и ρ*=(s−t)/(2−s−t). Это допустимый параметр. При a<a* нижний край строго меньше −ρ*, следовательно его модуль больше ρ*. При a>a* верхний край строго больше ρ*. Так доказан единственный глобальный минимум, а не только найдено пересечение двух графиков.

Если s+t≥0, то s≥0 и исходное худшее значение равно s. При любом a>0 верхний край становится s+(1−s)a>s. Поэтому оптимально a*=0. Удержание здесь ухудшает выбранный критерий. Вывод включает обе границы допустимого отрезка; оптимизация только среди положительных вероятностей остановки пропустила бы этот случай.

Реализуемый цикл показывает конфликт мод

Рассмотрим неориентированный цикл 0–1–2–3–0. Из каждой вершины переходят к каждому из двух соседей с вероятностью 1/2. Матрица симметрична, π=(1/4,1/4,1/4,1/4). Векторы (1,0,−1,0) и (0,1,0,−1) имеют собственное значение ноль, а (1,−1,1,−1) — минус единица. Вместе с постоянным вектором они образуют ортогональный базис. Поэтому все нетривиальные множители Pₐ равны a,a,2a−1.

На малых a мешает чередующаяся мода; на больших a мешают бывшие нулевые моды. Привычное удержание наполовину уничтожает первую, но оставляет две другие с множителем 1/2. Равновесие худших мод даёт меньшую норму. Обратимость существенна: для несимметричного в соответствующем весе оператора собственные направления могут быть неортогональны, и максимум модулей собственных значений уже не обязан равняться однократной операторной норме.

Выбор удержания на цикле из четырёх вершин

Условие. Для описанного симметричного четырёхцикла выберите a∈[0,1], минимизирующее норму Pₐ на центрированных функциях в L²(π). Найдите минимум и сравните с a=1/2. Подтвердите собственные направления непосредственно матрицей.

  1. Запишем строки P: (0,1/2,0,1/2), (1/2,0,1/2,0), (0,1/2,0,1/2), (1/2,0,1/2,0). Все суммы равны единице; симметрия даёт обратимость относительно равномерной π.
  2. Умножение P на v=(1,−1,1,−1) даёт −v. Умножение на w=(1,0,−1,0) и z=(0,1,0,−1) даёт нулевые векторы. Они центрированы, ортогональны и заполняют трёхмерное пространство центрированных функций.
  3. Значит ρ(a)=max(a,|2a−1|). На [0,1/2] сравниваем a и 1−2a: равенство даёт a=1/3. На [1/2,1] имеем |2a−1|≤a, поэтому ρ(a)=a≥1/2.
  4. При a<1/3 величина 1−2a>1/3, а при a>1/3 величина a>1/3. Это глобальный сертификат и единственность минимума. При a*=1/3 три множителя равны 1/3,1/3,−1/3.
  5. Минимальная норма равна 1/3. При a=1/2 она равна 1/2, так что стандартное удержание наполовину не оптимально для данного критерия.

Ответ. Единственный оптимум a*=1/3; худшее однократное L²(π)-сжатие равно 1/3. При a=1/2 оно равно 1/2.

Проверка. При a=1/3 у Pₐ диагональ и два соседних элемента каждой строки равны 1/3, противоположный элемент нулевой. Прямое перемножение даёт Pₐ²=(1/9)I+(8/9)J, где все элементы J равны 1/4. Для центрированной f имеем Jf=0; самосопряжённость даёт ‖Pₐf‖π²=⟨f,Pₐ²f⟩π=‖f‖π²/9. Это проверяет норму без использования найденного собственного базиса.

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

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

Какое удержание минимизирует худшую норму центрированных функций для четырёхцикла из разобранного примера?

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

Почему нельзя просто уничтожить отрицательную моду при a=1/2?

Такой выбор обнуляет 2a−1, но одновременно увеличивает две нулевые моды до 1/2. Минимакс учитывает их вместе и предпочитает три одинаковых модуля по 1/3.

Что означает оптимум a=0 в общем случае s+t≥0?

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

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

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

  • Aldous–Fill, Reversible Markov Chains, §2.1

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

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

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

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

Что означает снимок непрерывного процесса

Конечная однородная непрерывная цепь с конечными интенсивностями; наблюдения разделены известным положительным временем Δ.

Пусть за три секунды переход из A в B наблюдается с вероятностью 3/10, а из B в A — с вероятностью 1/5. Эти числа не являются интенсивностями за секунду. Между двумя наблюдениями процесс может сменить состояние несколько раз и даже вернуться. Требуется найти постоянные скорости, которые после всех таких скрытых переходов воспроизведут объявленную матрицу.

Генератор G имеет неотрицательные внедиагональные элементы и нулевые суммы строк. Для временного интервала Δ переходная матрица равна P=exp(ΔG). Её определитель равен exp(ΔtrG)>0. Поэтому неположительный определитель сразу исключает вложение при конечных скоростях и положительном конечном Δ. Это необходимое условие в любой конечной размерности. Положительность определителя сама по себе в больших матрицах не проверяет нужные знаки возможного генератора.

В двух состояниях условие становится достаточным

Запишем P=((1−a,a),(b,1−b)), где a,b неотрицательны. Генератор имеет вид G=((−α,α),(β,−β)). При α+β>0 стационарная масса B равна α/(α+β), а отклонение от стационарного закона за время Δ умножается на exp[−(α+β)Δ]. Следовательно a=α[1−exp(−kΔ)]/k и b=β[1−exp(−kΔ)]/k, где k=α+β.

Суммирование даёт a+b=1−exp(−kΔ). Если 0<a+b<1, положим k=−ln(1−a−b)/Δ, α=ka/(a+b), β=kb/(a+b). Эти числа неотрицательны и точно возвращают P, что доказывает достаточность и единственность двух скоростей. Одна из них может быть нулевой: поглощение не нарушает критерий. Если a=b=0, матрица единичная и в двух состояниях соответствует нулевому генератору.

Нулевая и отрицательная мода имеют разные причины отказа

При a+b=1 нетривиальное собственное значение P равно нулю. Чтобы получить его из exp(−kΔ), потребовалась бы бесконечная скорость или бесконечное время. Конечная однородная модель не обнуляет эту моду точно, хотя способна сделать её очень малой. При a+b>1 собственное значение отрицательно и определитель отрицателен: это другое, ещё более явное препятствие.

Например, вероятность удержания 1/10 и смены 9/10 в обоих состояниях уже устраняет дискретный период. Но сумма смен равна 9/5>1, поэтому такой апериодический шаг не вкладывается в однородную непрерывную двухсостоянийную цепь. Добавить случайные часы к дискретному правилу можно, однако полученная экспонента не обязана совпасть с самой исходной P. Не переносите двухсостоянийный запрет отдельного отрицательного значения без проверки на произвольную размерность: там возможны комплексные моды генератора.

Две интенсивности по снимку через три секунды

Условие. За Δ=3 с дана P=((7/10,3/10),(1/5,4/5)). Проверьте непрерывное однородное вложение и найдите α=A→B, β=B→A в с⁻¹.

  1. Имеем a=3/10,b=1/5 и a+b=1/2. Нетривиальная мода 1−a−b=1/2 положительна; точный двухсостоянийный критерий выполнен.
  2. Суммарная интенсивность k=−ln(1/2)/3=ln2/3 с⁻¹. Деление на три относится к известному интервалу наблюдения.
  3. Доля α в суммарной интенсивности равна a/(a+b)=3/5, поэтому α=ln2/5 с⁻¹. Аналогично β=(2/5)k=2ln2/15 с⁻¹.
  4. Вернём вероятности: exp(−3k)=1/2; α(1−1/2)/k=(3/5)(1/2)=3/10 и β(1−1/2)/k=(2/5)(1/2)=1/5.
  5. Определитель исходной P равен 1/2. Определитель exp(3G) равен exp[−3(α+β)]=1/2, давая отдельную общую проверку. Значения α≈0,138629 и β≈0,092420 с⁻¹ не равны a/3 и b/3.

Ответ. Вложение существует и единственно в двухсостоянийной модели: α=ln2/5 с⁻¹, β=2ln2/15 с⁻¹.

Проверка. Решение скалярного уравнения u′=β−(α+β)u имеет вид u(t)=2/5+[u(0)−2/5]exp(−kt). Подстановка отдельно старта A и старта B при t=3 даёт обе строки заданной P, а не только их определитель.

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

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

Чему равна сумма интенсивностей α+β в разобранном примере статьи с Δ=3 с?

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

Достаточно ли апериодичности наблюдаемой P?

Нет. Приведённый шаг с удержанием 1/10 апериодичен, но имеет отрицательный определитель. Существование непрерывного генератора — отдельное ограничение.

Что означает почти нулевая, но положительная мода?

Она даёт большую конечную k=−ln(λ)/Δ. Точный нуль исключает конечную скорость, а малая положительная величина её допускает; точность оценки при таком восстановлении требует отдельного анализа.

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

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

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

    Генератор непрерывной цепи и полугруппа Hₜ=exp(tG). Критерий двухсостоянийного вложения и восстановление обеих интенсивностей выведены здесь.

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

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

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