Парная независимость

Набор случайных величин, из которых любые две независимы

В теории вероятностей попарно независимый набор случайных величин представляет собой набор случайных величин, любые две из которых независимы . ^[1] Любой набор взаимно независимых случайных величин попарно независим, но некоторые попарно независимые наборы не являются взаимно независимыми. Попарно независимые случайные величины с конечной дисперсией некоррелированы .

Пара случайных величин X и Y независимы тогда и только тогда , когда случайный вектор ( X , Y ) с совместной кумулятивной функцией распределения (CDF) удовлетворяет ${\displaystyle F_{X,Y}(x,y)}$

${\displaystyle F_{X,Y}(x,y)=F_{X}(x)F_{Y}(y),}$

или, что то же самое, их совместная плотность удовлетворяет ${\displaystyle f_{X,Y}(x,y)}$

${\displaystyle f_{X,Y}(x,y)=f_{X}(x)f_{Y}(y).}$

То есть совместное распределение равно произведению предельных распределений. ^[2]

Если это не ясно из контекста, на практике модификатор «взаимный» обычно опускается, так что независимость означает взаимную независимость . Такое утверждение, как « X , Y , Z являются независимыми случайными величинами», означает, что X , Y , Z взаимно независимы.

Пример

Попарная независимость не предполагает взаимной независимости, как показывает следующий пример, приписываемый С. Бернштейну. ^[3]

Предположим, X и Y — два независимых броска честной монеты, где мы обозначаем 1 для орла и 0 для решки. Пусть третья случайная величина Z равна 1, если ровно в одном из этих бросков монеты выпал «орел», и 0 в противном случае (т. е. ). Тогда совместно тройка ( X , Y , Z ) имеет следующее распределение вероятностей : ${\displaystyle Z=X\oplus Y}$

${\displaystyle (X,Y,Z)=\left\{{\begin{matrix}(0,0,0)&{\text{with probability}}\ 1/4,\\(0,1,1)&{\text{with probability}}\ 1/4,\\(1,0,1)&{\text{with probability}}\ 1/4,\\(1,1,0)&{\text{with probability}}\ 1/4.\end{matrix}}\right.}$

Здесь предельные распределения вероятностей идентичны: и Двумерные распределения также согласуются: где ${\displaystyle f_{X}(0)=f_{Y}(0)=f_{Z}(0)=1/2,}$ ${\displaystyle f_{X}(1)=f_{Y}(1)=f_{Z}(1)=1/2.}$ ${\displaystyle f_{X,Y}=f_{X,Z}=f_{Y,Z},}$ ${\displaystyle f_{X,Y}(0,0)=f_{X,Y}(0,1)=f_{X,Y}(1,0)=f_{X,Y}(1,1)=1/4.}$

Поскольку каждое из попарных совместных распределений равно произведению соответствующих им предельных распределений, переменные попарно независимы:

• X и Y независимы, и
• X и Z независимы, и
• Y и Z независимы.

Однако X , Y и Z не являются взаимно независимыми , поскольку левая часть равна, например, 1/4 для ( x , y , z ) = (0, 0, 0), а правая часть равна 1/8 для ( x , y , z ) = (0, 0, 0). Фактически любое из полностью определяется двумя другими (любое из X , Y , Z является суммой (по модулю 2) остальных). Это настолько далеко от независимости, насколько это возможно для случайных величин. ${\displaystyle f_{X,Y,Z}(x,y,z)\neq f_{X}(x)f_{Y}(y)f_{Z}(z),}$ ${\displaystyle \{X,Y,Z\}}$

Вероятность объединения попарно независимых событий

Оценки вероятности того, что сумма случайных величин Бернулли равна хотя бы одной, широко известные как граница объединения , определяются неравенствами Буля–Фреше ^{[4] [5]} . Хотя эти границы предполагают только одномерную информацию, было также предложено несколько границ со знанием общих двумерных вероятностей. Обозначим через множество событий Бернулли с вероятностью появления каждого . Предположим, что двумерные вероятности заданы для каждой пары индексов . Куниас ^[6] получил следующую верхнюю оценку : ${\displaystyle \{{A}_{i},i\in \{1,2,...,n\}\}}$ ${\displaystyle n}$ ${\displaystyle \mathbb {P} (A_{i})=p_{i}}$ ${\displaystyle i}$ ${\displaystyle \mathbb {P} (A_{i}\cap A_{j})=p_{ij}}$ ${\displaystyle (i,j)}$

${\displaystyle \mathbb {P} (\displaystyle {\cup }_{i}A_{i})\leq \displaystyle \sum _{i=1}^{n}p_{i}-{\underset {j\in \{1,2,..,n\}}{\max }}\sum _{i\neq j}p_{ij},}$

который вычитает максимальный вес звездчатого остовного дерева на полном графе с узлами (где веса ребер заданы ) из суммы маргинальных вероятностей . Хантер-Уорсли ^{[7] [8]} ужесточил эту верхнюю границу , оптимизировав следующим образом: ${\displaystyle n}$ ${\displaystyle p_{ij}}$ ${\displaystyle \sum _{i}p_{i}}$
${\displaystyle \tau \in T}$

${\displaystyle \mathbb {P} (\displaystyle {\cup }_{i}A_{i})\leq \displaystyle \sum _{i=1}^{n}p_{i}-{\underset {\tau \in T}{\max }}\sum _{(i,j)\in \tau }p_{ij},}$

где – множество всех остовных деревьев графа. Эти границы не являются максимально точными для общих двумерных переменных , даже если осуществимость гарантирована, как показано в Boros et.al. ^[9] Однако, когда переменные попарно независимы ( ), Рамачандра-Натараджан ^[10] показал, что граница Куниаса-Хантера-Уорсли ^{[6] [7] [8] является} точной , доказав, что максимальная вероятность объединения события допускают выражение закрытой формы , заданное как: ${\displaystyle T}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{ij}=p_{i}p_{j}}$

где вероятности отсортированы в порядке возрастания как . Интересно отметить, что жесткая граница в уравнении. 1 зависит только от суммы наименьшей вероятности и наибольшей вероятности . Таким образом, хотя порядок вероятностей играет роль при получении оценки, порядок среди наименьших вероятностей несущественен, поскольку используется только их сумма . ${\displaystyle 0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1}$ ${\displaystyle n-1}$ ${\displaystyle \sum _{i=1}^{n-1}p_{i}}$ ${\displaystyle p_{n}}$ ${\displaystyle n-1}$ ${\displaystyle \{p_{1},p_{2},...,p_{n-1}\}}$

Сравнение с границей объединения Буля – Фреше

Полезно сравнить наименьшие границы вероятности объединения при произвольной зависимости и попарной независимости соответственно. Самая точная верхняя граница объединения Буля – Фреше (при условии только одномерной информации) задается как:

Как показано в работе Рамачандра-Натараджана ^[10] , можно легко проверить, что соотношение двух жестких границ в уравнении 2 и уравнение. 1 ограничен сверху тем , где достигается максимальное значение, когда ${\displaystyle 4/3}$ ${\displaystyle 4/3}$

${\displaystyle \sum _{i=1}^{n-1}p_{i}=1/2}$, ${\displaystyle p_{n}=1/2}$

где вероятности отсортированы в порядке возрастания как . Другими словами, в лучшем случае граница попарной независимости в уравнении 1 обеспечивает улучшение по сравнению с одномерной границей в уравнении. 2 . ${\displaystyle 0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1}$ ${\displaystyle 25\%}$

Обобщение

В более общем смысле мы можем говорить о независимости по k для любого k  ≥ 2. Идея аналогична: набор случайных величин является независимым по k , если каждое подмножество этих переменных размером k независимо. k -мудрая независимость использовалась в теоретической информатике, где она использовалась для доказательства теоремы о проблеме MAXEkSAT .

k -зависимость используется для доказательства того, что k-независимые хэш- функции являются безопасными и неподдельными кодами аутентификации сообщений .

Смотрите также

• Попарно
• Непересекающиеся множества

Рекомендации

1. Гут, А. (2005) Вероятность: аспирантура , Springer-Verlag. ISBN  0-387-27332-8 . стр. 71–72.
2. Хогг, Р.В., Маккин, Дж.В., Крейг, AT (2005). Введение в математическую статистику (6-е изд.). Река Аппер-Сэддл, Нью-Джерси: Пирсон Прентис Холл. ISBN 0-13-008507-3.{{cite book}}: CS1 maint: multiple names: authors list (link)Определение 2.5.1, стр. 109.
3. Хогг, Р.В., Маккин, Дж.В., Крейг, AT (2005). Введение в математическую статистику (6-е изд.). Река Аппер-Сэддл, Нью-Джерси: Пирсон Прентис Холл. ISBN 0-13-008507-3.{{cite book}}: CS1 maint: multiple names: authors list (link)Замечание 2.6.1, с. 120.
4. Буль, Г. (1854). Исследование законов мышления, на которых основаны математические теории логики и вероятности. Уолтон и Маберли, Лондон. См. «большие» и «второстепенные» пределы союза Буля на стр. 299.
5. Фреше, М. (1935). Обобщения теории общих вероятностей. Fundamenta Mathematicae 25 : 379–387.
6. EG Куниас (1968). «Оценки вероятности объединения с приложениями». Анналы математической статистики . 39 (6): 2154–2158. дои : 10.1214/aoms/1177698049 .
7. Д. Хантер (1976). «Верхняя оценка вероятности союза». Журнал прикладной вероятности . 13 (3): 597–603. дои : 10.2307/3212481. JSTOR  3212481.
8. К. Дж. Уорсли (1982). «Улучшенное неравенство Бонферрони и его приложения». Биометрика . 69 (2): 297–302. дои : 10.1093/biomet/69.2.297.
9. Борос, Эндре ; Скоццари, Андреа; Тарделла, Фабио; Венециани, Пьерангела (2014). «Полиномиально вычислимые оценки вероятности объединения событий». Математика исследования операций . 39 (4): 1311–1329. дои : 10.1287/moor.2014.0657.
10. Рамачандра, Арджун Кодагехалли; Натараджан, Картик (2023). «Жесткие границы вероятности с попарной независимостью». SIAM Journal по дискретной математике . 37 (2): 516–555. arXiv : 2006.00516 . дои : 10.1137/21M140829.