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

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

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

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

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

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

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

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

Пример

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

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

$(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.$

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

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

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

$\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},$

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

$\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},$

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

$\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 )

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

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

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

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

Как показано в «Рамачандра-Натараджане», можно легко проверить, что соотношение двух жестких границ в уравнении 2 и уравнение. 1 ограничен сверху ​ $4/3$ где максимальное значение $4/3$ достигается, когда

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

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

Обобщение

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

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

См. также

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