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

В теории вероятностей , попарно независимы совокупность случайных величин представляет собой набор случайных величин любые два из которых являются независимыми . ^[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 (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]} является точной , доказав, что максимальная вероятность объединения events допускает выражение в закрытой форме, заданное как:${\displaystyle T}$ ${\displaystyle p_{ij}}$${\displaystyle p_{ij}=p_{i}p_{j}}$

${\displaystyle \max \mathbb {P} (\displaystyle {\cup }_{i}A_{i})=\displaystyle \min \left(\sum _{i=1}^{n}p_{i}-p_{n}\left(\sum _{i=1}^{n-1}p_{i}\right),1\right)}$

( 1 )

где вероятности отсортированы в порядке возрастания как . Интересно отметить, что жесткая граница в уравнении. 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}\}}$

Сравнение с оценкой объединения Буля – Фреше [ править ]

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

${\displaystyle \displaystyle \max \mathbb {P} (\displaystyle {\cup }_{i}A_{i})=\displaystyle \min \left(\sum _{i=1}^{n}p_{i},1\right)}$

( 2 )

Как показано в Ramachandra-Natarajan, ^[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 хеш- функции являются безопасными кодами аутентификации, которые невозможно подделать .

См. Также [ править ]

• Попарно
• Попарно непересекающиеся

Ссылки [ править ]