Каплинг: две цепи, одна случайность и время перемешивания

Если различаешь маргинальные распределения и совместную зависимость цепей, листай до «Теперь сам».

Как думаешь, обязаны ли сравниваемые цепи быть независимыми

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

На что это похоже

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

Механизм: встреча ограничивает различие любых событий

Для распределений μ,ν на конечном множестве полная вариация равна max_A |μ(A)-ν(A)|, то есть наибольшему различию вероятностей события. Если случайные состояния X,Y построены совместно и имеют эти распределения, индикаторы любого события совпадают при X=Y. Поэтому |P(X∈A)-P(Y∈A)|≤P(X≠Y). Максимум по событиям сохраняет неравенство.

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

В обеих цепях выбираем одну координату и один бит. После обновления все различия в этой позиции исчезают. Для одной позиции вероятность не быть выбранной за t шагов равна (1-1/d)ᵗ. По объединению событий вероятность пропустить хоть одну позицию не больше d(1-1/d)ᵗ≤d·exp(-t/d). Такой же верхней границей ограничена полная вариация от стационарного распределения.

Правило

Сначала проверь закон перехода каждой цепи по отдельности; затем оцени вероятность, что их состояния ещё различны. Для точности ε достаточно t≥d·ln(d/ε) в показанной цепи. Это достаточная граница, а не утверждение о точном моменте смешивания.

Разбор: вычислим расстояние распределений точно

from math import exp

D = 4
SIZE = 1 << D


def step(distribution):
    result = [0.0] * SIZE
    for state, probability in enumerate(distribution):
        for bit in range(D):
            for value in (0, 1):
                target = state & ~(1 << bit)
                target |= value << bit
                result[target] += probability / (2 * D)
    return result


def total_variation(distribution):
    return sum(abs(x - 1/SIZE) for x in distribution) / 2


distribution = [1.0] + [0.0] * (SIZE - 1)
for t in range(21):
    exact = total_variation(distribution)
    upper = min(1.0, D * (1 - 1/D) ** t)
    assert exact <= upper + 1e-12
    assert abs(sum(distribution) - 1) < 1e-12
    if t in (0, 4, 8, 12, 20):
        print(t, f"{exact:.6f}", f"{upper:.6f}")
    distribution = step(distribution)
uniform = [1 / SIZE] * SIZE
assert step(uniform) == uniform
x, y = 0, SIZE - 1
for bit in (2, 0, 3, 1):
    value = bit % 2
    x = (x & ~(1 << bit)) | (value << bit)
    y = (y & ~(1 << bit)) | (value << bit)
assert x == y
print("Все позиции обновлены, состояния совпали:", x == y)

0 0.937500 1.000000
4 0.259766 1.000000
8 0.076546 0.400452
12 0.023849 0.126705
20 0.002379 0.012685
Все позиции обновлены, состояния совпали: True

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

Разбор: встреча и перемешивание не одно событие

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

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

Что ломается без этого

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

Зачем это в работе

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

Теперь сам

В цепи на восьми битах одна координата на каждом шаге заменяется общим честным битом. Какова верхняя граница вероятности, что конкретная координата не обновилась за t шагов? Что нужно добавить для границы по всем координатам?