Вероятность и статистика · объяснение и практика
Сравнить распределения через совместный эксперимент: неравенство сопряжения
Построить сопряжение двух дискретных распределений с правильными маргинальными суммами и ограничить полную вариацию вероятностью несовпадения.

В теме Случайные величины и распределения · Учебная карта
Главная мысль
Сопряжение — совместное распределение пары с заранее заданными маргинальными распределениями. Для любой такой пары полная вариация между маргинальными не превышает вероятность несовпадения. Хорошая конструкция делает пару одинаковой как можно чаще.
Метод и постановка
Исходная задача задаёт два закона, но не говорит, как их случайные величины наблюдаются вместе. Независимое совместное моделирование — только один возможный выбор. Сопряжение позволяет специально связать координаты, сохранив каждое отдельное распределение. Поэтому сначала проверяются суммы строк и столбцов совместной таблицы.
Для любого события A индикаторы попадания двух координат могут различаться только тогда, когда сами координаты не совпали. Модуль разности вероятностей события поэтому не больше вероятности несовпадения. Взятие максимума по событиям даёт неравенство для полной вариации. В конечном пространстве ту же дистанцию можно независимо вычислить как половину суммы абсолютных разностей соответствующих вероятностей.
Проверка и границы вывода
Чтобы построить особенно удачную пару, на диагональ совместной таблицы поставьте минимумы двух вероятностей в каждой категории. Это максимально возможная масса совпадения по каждой метке. Оставшиеся массы первой и второй координат распределите вне диагонали так, чтобы восстановить маргинальные суммы. В конечном случае такая максимальная конструкция достигает полной вариации своей вероятностью несовпадения.
Не следует объявлять равенство для произвольного сопряжения: независимая пара обычно совпадает реже оптимальной. Не следует также менять названия категорий отдельно в одном распределении, если метки имеют общий смысл: это изменило бы сравниваемую задачу. Метод даёт оценку различимости распределений по событиям, а не среднюю численную разность значений. Для расстояния между числами понадобился бы другой функционал совместной пары и, возможно, другой способ оптимизации.
Масса диагонали не может превысить минимум двух маргинальных масс в каждой категории. Суммирование этих ограничений даёт верхнюю границу возможного совпадения. Построенная таблица достигает каждой такой границы одновременно, поэтому её оптимальность подтверждается отдельно от общего неравенства для любых сопряжений.
Пример
Пусть P=(1/2,1/3,1/6), Q=(1/3,1/2,1/6) на метках a,b,c. Положим на диагональ 1/3,1/3,1/6, а оставшуюся массу 1/6 — в пару (a,b).
Маргинальные суммы совпадают с P и Q. Вероятность несовпадения равна 1/6. Половина суммы модулей разностей также равна (1/6+1/6)/2=1/6, поэтому конструкция максимальна по совпадению.
От чтения к действию
А теперь — вы
Частые вопросы
Обязательна независимость координат пары?
Нет. Намеренная зависимость и позволяет получить полезную оценку.
Зачем проверять маргинальные суммы?
Без них совместная таблица могла бы сравнивать совсем другие исходные распределения.
Углублённый разбор
Транспортная стоимость сопряжения: минимум среднего расстояния
Сопряжение можно оптимизировать по среднему расстоянию, а не по вероятности точного совпадения. Разные стоимости приводят к разным задачам транспортировки.
Перед началом: Совместные и условные законы; Ожидание, дисперсия и условная независимость.
Определение и постановка
Для числовых меток xᵢ,yⱼ и совместных масс γᵢⱼ требуется минимизировать Σγᵢⱼ|xᵢ−yⱼ| при фиксированных суммах строк pᵢ и столбцов qⱼ. Минимум называют расстоянием Вассерштейна первого порядка.
Вывод и вычислительный критерий
На прямой оптимальное сопряжение можно построить общим квантильным аргументом U: X=F⁻¹(U),Y=G⁻¹(U). Массы перемещаются в одинаковом порядке, поэтому пересекающиеся перевозки не нужны. Перестановочное неравенство для четырёх упорядоченных точек доказывает, что устранение пересечения не увеличивает суммарный модуль расстояния.
Другой сертификат использует любую функцию f с липшицевой константой не больше единицы: |Ef(X)−Ef(Y)|≤E|X−Y|. Если построенный план достигает такого нижнего ограничения, его оптимальность доказана без полного перебора транспортных таблиц.
Условия и границы вывода
Стоимость зависит от числовой геометрии меток. Одновременное переименование категорий сохраняет полную вариацию, но может изменить транспортное расстояние, если меняются числовые расстояния между ними.
Не всякое максимальное по совпадению сопряжение обязательно минимизирует выбранную геометрическую стоимость в многомерном пространстве. Условия линейного порядка в квантильном построении существенны. Для неограниченных законов нужно существование первых моментов, иначе стоимость может быть бесконечной.
Смена единицы измерения умножает транспортную стоимость на тот же положительный масштаб. Полная вариация при этом остаётся прежней, поскольку она сравнивает вероятности событий. Это даёт простой способ понять практическое различие функционалов: малая масса, перенесённая очень далеко, может давать небольшую полную вариацию и большую среднюю транспортную стоимость. Выбор показателя должен соответствовать тому, допустимо ли считать дальние и близкие ошибки одинаковыми.
Разобранная задача
Условие. X равновероятно принимает 0 и 2, Y равновероятно принимает 1 и 3. Найдите минимальное E|X−Y| и сравните с независимым сопряжением.
- Квантильный план связывает 0 с 1 и 2 с 3, каждому маршруту отдавая половину массы.
- Обе длины равны единице, поэтому средняя стоимость плана равна 1.
- Любой план имеет E|X−Y|≥|EX−EY|=|1−2|=1; построенный план оптимален.
- При независимости четыре пары равновероятны и имеют расстояния 1,3,1,1. Их среднее равно 3/2.
Ответ. Минимальная стоимость равна 1; независимый выбор имеет стоимость 3/2.
Проверка. Все совместные таблицы задаются параметром t в клетке (0,1), с 0≤t≤1/2. Стоимость равна 2−2t и минимальна при t=1/2, что независимо подтверждает квантильный план.
Где легко ошибиться. Вероятность совпадения здесь нулевая при любом сопряжении, но средняя стоимость существенно зависит от совместного плана.
Проверьте понимание
Вопросы к этой главе
Почему полная вариация не различает эти планы?
Носители двух законов не пересекаются, поэтому точное совпадение невозможно. Геометрическая стоимость дополнительно учитывает, на какое расстояние переносятся несовпавшие значения.
Когда достаточно сравнить средние?
Разность средних всегда даёт нижнюю границу для модульной стоимости. Она становится точной лишь если выбранный план не создаёт компенсирующих переносов в противоположных направлениях.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sébastien Roch: сопряжение и смешивание, Chapter 4
PDF с извлечённым текстом: §4.1 и §4.3, неравенство сопряжения, сохранение маргиналей и оценка смешивания; упражнение4.17 определяет транспортную стоимость.
Время встречи совместных цепей и оценка смешивания
Совместный запуск двух цепей оценивает смешивание через время их встречи. После встречи цепи необходимо заставить двигаться вместе.
Перед началом: Совместные и условные законы; Ожидание, дисперсия и условная независимость.
Определение и постановка
Если маргинальные переходы обеих координат равны P и после времени T координаты совпадают навсегда, то TV(μPⁿ,νPⁿ)≤P(T>n).
Вывод и вычислительный критерий
Для любого события A разность индикаторов принадлежности двух координат равна нулю при совпадении и по модулю не больше единицы иначе. Усреднение даёт оценку разности вероятностей через вероятность несовпадения.
Если вторую цепь начать из стационарного π, её закон остаётся π. Тогда хвост времени встречи первой цепи со стационарной копией непосредственно ограничивает расстояние до равновесия.
Условия и границы вывода
Первая встреча недостаточна, если после неё координаты снова расходятся. Можно определять временем T начало вечного совпадения либо специально использовать одинаковые случайные команды после встречи.
Нельзя выбирать совместные переходы так, чтобы улучшить встречу ценой нарушения хотя бы одного маргинального закона. Тогда сравнивались бы уже другие процессы.
Для сравнения независимые команды при тех же одинаковых строках давали бы вероятность совпадения лишь пять девятых за один шаг: одна девятая для общего A и четыре девятых для общего B. Это сопряжение тоже сохраняет маргинали, но при продолжении независимых команд цепи могут снова разойтись. Если после первой встречи перейти на общие команды, получится корректное слияние с геометрическим временем ожидания. Такая оценка была бы слабее мгновенной встречи, хотя оба построения относятся к одной матрице. Выбор совместного эксперимента влияет на силу доказательства, но не на действительное расстояние между законами: оно уже равно нулю после одного шага независимо от выбранной проверки.
Разобранная задача
Условие. Матрица двухсостоянийной цепи имеет обе строки (1/3,2/3). Две копии стартуют в разных состояниях. Постройте сопряжение и оцените расстояние после одного шага.
- Используем одно общее равномерное U для обеих координат.
- Если U≤1/3, обе переходят в A; иначе обе переходят в B.
- Каждая координата имеет верный переход независимо от своего старта, поскольку строки одинаковы.
- Встреча происходит в первый шаг с вероятностью единица; при дальнейших общих U координаты больше не расходятся.
Ответ. После одного шага расстояние полной вариации равно нулю; время встречи T=1 почти наверное.
Проверка. Прямое умножение любого начального распределения на P даёт строку (1/3,2/3). Поэтому равенство законов подтверждено независимо от совместной конструкции.
Где легко ошибиться. Совместные случайные числа допустимы, только если каждый отдельный процесс сохраняет исходную матрицу переходов.
Проверьте понимание
Вопросы к этой главе
Обязательно ли сопряжение оптимально?
Нет. Любое корректное сохраняющее маргинали сопряжение даёт верхнюю оценку. Более быстрое гарантированное слияние делает оценку сильнее.
Почему стационарный старт удобен?
Он фиксирует второй маргинальный закон во времени. Тогда сравнение двух динамических копий превращается в оценку отклонения первой от одного постоянного распределения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sébastien Roch: сопряжение и смешивание, Chapter 4
PDF с извлечённым текстом: §4.1 и §4.3, неравенство сопряжения, сохранение маргиналей и оценка смешивания; упражнение4.17 определяет транспортную стоимость.
Все максимальные сопряжения: свобода остаточной таблицы и границы событий
Максимальная вероятность совпадения не определяет весь совместный закон. Опишем полное семейство оптимальных таблиц, найдём число свободных параметров и установим, какие вероятности отдельных несовпадений остаются неопределёнными.
Перед началом: Маргинальные суммы совместной таблицы; Ранг линейных ограничений и относительная внутренняя точка.
Максимальность фиксирует каждую диагональную клетку
На одном конечном наборе меток заданы распределения p и q. Считаем известным основной результат: наибольшая масса диагонали равна c=Σmin(pᵢ,qᵢ). Теперь требуется описать не одну достигающую таблицу, а все такие таблицы. Если γ максимальна, каждая разность min(pᵢ,qᵢ)−γᵢᵢ неотрицательна, а сумма этих разностей равна нулю. Следовательно, все они нулевые по отдельности: γᵢᵢ=min(pᵢ,qᵢ).
После удаления обязательной диагонали остаются положительные строки aᵢ=pᵢ−qᵢ на множестве I={i:pᵢ>qᵢ} и положительные столбцы bⱼ=qⱼ−pⱼ на J={j:qⱼ>pⱼ}. Их общая сумма r=1−c. Множества I,J не пересекаются, поэтому любой допустимый остаток уже лежит вне диагонали. Все максимальные сопряжения получаются добавлением к фиксированной диагонали произвольной неотрицательной таблицы R с этими суммами строк и столбцов. Это полная классификация: оба направления следуют из маргинальных равенств.
Размерность и критерий единственности
Пусть r>0, m=|I|, n=|J|. У остатка mn клеток. Равенства строк и столбцов имеют ранг m+n−1: сумма строк совпадает с суммой столбцов, а других зависимостей нет. Последнее видно, если выбрать произвольно первые (m−1)(n−1) клетки, восстановить последние столбец и строку и получить последнее равенство автоматически.
Неравенства не уменьшают размерность всего семейства: таблица Rᵢⱼ=aᵢbⱼ/r строго положительна и удовлетворяет всем равенствам. В достаточно малой окрестности внутри их аффинного пространства клетки остаются положительными. Поэтому размерность равна (m−1)(n−1). Максимальная таблица единственна ровно при m=1 или n=1. Если обе величины не меньше двух, малый знакопеременный перенос по прямоугольнику даёт разные допустимые таблицы. При r=0 остатка нет, p=q и единственная максимальная таблица целиком диагональна.
Один и тот же оптимум оставляет интервалы вероятностей
Неопределённость остатка имеет наблюдаемый смысл. Можно знать минимальную вероятность любой ошибки, но не знать, какой именно ошибочный переход случается. Для события, включающего одну остаточную клетку, нужны дополнительные ограничения на совместный механизм либо диапазон по всему допустимому многограннику. Выбор независимых условных остатков является одним внутренним решением, а не следствием максимальности.
Для остатка двух строк и двух столбцов достаточно одного параметра. Его допустимость проверяется четырьмя неравенствами неотрицательности, а крайние значения дают точные границы любого линейного события. Условная вероятность при несовпадении получается делением на фиксированное r; поэтому её границы также достижимы. Изменять функционал на среднее расстояние здесь не требуется: исследуется не новый транспортный минимум, а неоднозначность полного закона при уже закреплённом оптимуме совпадения.
Одна максимальная масса, целый отрезок механизмов
Условие. На метках a,b,c,d заданы p=(4,3,2,1)/10 и q=(1,2,3,4)/10. Опишите все максимальные таблицы. Найдите диапазоны P(X=a,Y=c) и P(X=a,Y=d | X≠Y).
- Обязательная диагональ равна (1,2,2,1)/10 и имеет массу 3/5. Остаточные строки a,b равны 3/10,1/10; столбцы c,d равны 1/10,3/10. Значит r=2/5, а размерность (2−1)(2−1)=1.
- Обозначим R_ac=t. Из сумм строк и столбцов вынужденно R_ad=3/10−t, R_bc=1/10−t, R_bd=t. Других положительных остаточных клеток нет.
- Четыре клетки неотрицательны ровно при 0≤t≤1/10. Каждый параметр этого интервала вместе с фиксированной диагональю восстанавливает исходные маргиналы и достигает оптимального совпадения 3/5.
- Поэтому P(X=a,Y=c) принимает все значения от 0 до 1/10. Условная вероятность второго события равна (3/10−t)/(2/5) и изменяется от 3/4 до 1/2; её точный диапазон [1/2,3/4].
- Независимый выбор на условной остаточной ветви дал бы R_ac=(3/10)(1/10)/(2/5)=3/40. Это внутренняя точка допустимого отрезка и только один из максимальных механизмов.
Ответ. Все максимальные таблицы задаются 0≤t≤1/10. Вероятность ошибки типа (a,c) лежит в [0,1/10], а P(a,d | несовпадение) — в [1/2,3/4].
Проверка. При t=0 и t=1/10 прямое сложение полных строк даёт p, столбцов — q, диагонали — 3/5. Эти две допустимые таблицы достигают противоположных границ событий, независимо удостоверяя точность интервалов.
Где легко ошибиться. Не выдавайте произведение условных остатков за единственную максимальную таблицу. Максимальность фиксирует диагональ и общую ошибку, но не выбирает зависимость внутри остатка.
Проверьте понимание
Вопросы к этой главе
Когда остаточная таблица всё же единственна?
При ненулевом остатке достаточно и необходимо, чтобы положительной была только одна остаточная строка или только один столбец. Тогда все клетки вынуждены их суммами; при r=0 остаётся одна диагональ.
Почему нельзя произвольно уменьшить одну диагональную клетку и увеличить другую?
Каждая уже равна своему индивидуальному максимуму min(pᵢ,qᵢ). Увеличить другую сверх этой границы невозможно, поэтому потерянное совпадение не компенсируется.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Lawler and Limic: Random Walk, section12.4.2
Опорный результат — максимальное совпадение через общую массу распределений. Полная классификация остаточных таблиц, их размерность, критерий единственности и диапазоны событий доказаны в главе отдельно.
Проверять только соседей: путевое сопряжение и сжатие метрики
Вместо построения совместной цепи для каждой пары достаточно контролировать соседей в подходящей геометрии. Склейка соседних сопряжений переносит локальную оценку на кратчайший путь, а затем на любые начальные распределения. Важно, что длина измеряется после перехода исходной метрикой.
Перед началом: Сопряжение и транспортная стоимость; Метрика кратчайшего пути.
Граф проверки может отличаться от графа переходов
Конечное пространство состояний снабжено связным вспомогательным графом и метрикой кратчайшего пути с единичными рёбрами. Для соседей заданы корректные одноступенчатые сопряжения строк одной матрицы P.
Вспомогательный граф определяет, какие пары удобно считать соседними. Он должен соединять все состояния, но его рёбра не обязаны совпадать с разрешёнными переходами P. Обозначим расстояние d. Если для каждого ребра существует сопряжение строк P(x,·),P(y,·) со средним расстоянием не больше βd(x,y), где 0≤β<1, проверка касается лишь локальных пар.
Здесь контролируется транспортное расстояние W_d — наименьшее среднее d по всем совместным законам с нужными маргиналями. Это не требование максимального совпадения в каждой паре и не классификация всех оптимальных таблиц. Цель — превратить небольшое число локальных конструкций в единую оценку динамики.
Соседние совместные таблицы склеиваются через общую маргиналь
Возьмём кратчайший путь x₀,…,xᵣ между произвольными x,y. У соседних сопряжений общая промежуточная маргиналь P(xᵢ,·). Их можно склеить: если таблицы γ(a,b),η(b,c) имеют общую массу μ(b), положим совместную тройку γ(a,b)η(b,c)/μ(b) при μ(b)>0. Нулевой промежуточной массе соответствуют нулевые клетки, делить на неё не нужно.
Полученная тройка сохраняет обе исходные парные таблицы. Неравенство треугольника даёт E d(U₀,Uᵣ)≤ΣE d(Uᵢ₋₁,Uᵢ)≤βΣd(xᵢ₋₁,xᵢ)=βd(x,y). Так соседняя проверка охватывает все стартовые пары. Затем усредняем эти сопряжения по оптимальному совместному закону исходных распределений и получаем W_d(μP,νP)≤βW_d(μ,ν).
Сжатие распределений переносится на много шагов
Итерация даёт множитель βᵗ. Если π стационарно, то W_d(δₓPᵗ,π)≤βᵗdiam. Так как d(u,v)≥1 при u≠v, полная вариация не превосходит транспортной стоимости; следовательно, TV(Pᵗ(x,·),π)≤min(1,βᵗdiam). Единица расстояния существенна: при другом минимальном положительном расстоянии нужно деление на него.
Оценка может быть грубой. Она не утверждает, что выбранные локальные таблицы дают лучший возможный темп или что геометрическая граница равна фактической полной вариации. Проверять полезно и общие инварианты — суммы строк, стационарность, предельное уменьшение — и одну небольшую задачу прямым умножением матриц.
Локальные проверки цепи с общим обновлением
Условие. На состояниях0,1,2 используйте линейный граф0—1—2 и P со строками(7/15,2/5,2/15),(2/15,11/15,2/15),(2/15,2/5,7/15). Это P=(1/3)I+(2/3)Π, где все строкиΠ равныπ=(1/5,3/5,1/5). Оцените расстояние из0 доπ после3 шагов.
- Для соседей0 и1 положим общую массу(2/3)π на диагональные клетки(0,0),(1,1),(2,2), а остаток1/3 — в(0,1). Суммы строк и столбцов восстанавливают P(0,·),P(1,·); средняя длина1/3.
- Для соседей1 и2 общая диагональ та же, остаток1/3 помещаем в(1,2). Оба ребра имеют длину1, поэтому β=1/3.
- Склейка соседних таблиц даёт допустимое сопряжение крайних строк со стоимостью не больше2/3. Разность средних этих строк равна2/3, так что найденная стоимость точна.
- ИзπΠ=π следуетπP=π. Диаметр линейного графа2, поэтому путевая граница после3 шагов равна2(1/3)³=2/27.
- Так какΠ²=Π, имеем P³=(1/27)I+(26/27)Π. Его строка0 равна(31/135,26/45,26/135). Разности сπ равны(4,−3,−1)/135, поэтому точная TV=4/135.
Ответ. Локальное сжатие β=1/3 даёт трёхшаговую границу2/27; точное расстояние из0 равно4/135.
Проверка. ИдемпотентностьΠ независимо даёт формулу всех степеней Pᵗ=3^(−t)I+(1−3^(−t))Π. Для t=3 она возвращает строку из прямого матричного умножения. Для крайних строк разность средних2/3 даёт нижний транспортный сертификат, совпадающий со склеенной стоимостью.
Где легко ошибиться. Нельзя проверять только соседей для произвольной функции расстояния без свойства кратчайшего пути. Именно сумма длин по минимальному пути делает локальный коэффициент глобальным.
Проверьте понимание
Вопросы к этой главе
Должны ли все соседние сопряжения существовать на одном общем случайном пространстве заранее?
Нет. Совпадающие промежуточные маргинали позволяют построить нужную склейку для выбранного пути. Не требуется одна универсальная случайная команда, одновременно реализующая все локальные таблицы.
Можно ли объявить β точным темпом смешивания?
Нет. Он удостоверяет верхнюю оценку для выбранной метрики и конструкций. В примере фактическая полная вариация существенно меньше полученной границы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Levin, Peres и Wilmer, Markov Chains and Mixing Times, §14.2
Поддерживает перенос соседних сопряжений на метрику кратчайшего пути и сжатие распределений. Трёхсостоянийный пример с общим обновлением, его таблицы и точная третья степень проверены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Вероятность когда-нибудь пересечь порог: максимальное неравенство Дуба
Ограничить вероятность достижения положительного порога неотрицательным субмартингалом за конечный горизонт и отличить максимум траектории от конечного значения.
Открыть темуХвостовое событие нельзя изменить конечным началом: где действует закон нуля или единицы
Распознать хвостовое событие независимой последовательности, применить закон Колмогорова и отделить этот вывод от вычисления конкретной вероятности.
Открыть темуРазделение пуассоновского потока: независимость возникает после снятия условия на общий счёт
Доказать независимость двух потоков после независимой маркировки пуассоновских событий и отличить её от отрицательной зависимости при фиксированном общем числе.
Открыть тему