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

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

Пара случайных величин Икс и Y находятся независимый тогда и только тогда, когда случайный вектор (Икс, 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]

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

Пример

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

Предполагать Икс и Y это два независимых подбрасывания честной монеты, где мы обозначаем 1 для орла и 0 для решки. Пусть третья случайная величина Z равняется 1, если ровно один из этих подбрасываний монеты завершился «орлом», и 0 в противном случае. Тогда совместно тройка (Икс, 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.}$

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

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

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

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

Границы вероятность что сумма Бернулли случайные переменные по крайней мере один, широко известный как связанный союз, предоставляются Буль – Фреше^[4][5] неравенства. Хотя эти границы предполагают только одномерный информация, несколько границ со знанием общих двумерный вероятности тоже были предложены. Обозначим через ${\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)}$. Куниас ^[6] получил следующие верхняя граница:

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

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

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

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

где вероятности сортируются в порядке возрастания как ${\displaystyle 0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1}$. Интересно отметить, что в обтяжку связанный в Уравнение 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)

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

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

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

Обобщение

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

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

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

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

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

1. Гут, А. (2005) Вероятность: аспирантура, Springer-Verlag. ISBN  0-387-27332-8. С. 71–72.
2. Хогг, Р. В., Маккин, Дж. У., Крейг, А. Т. (2005). Введение в математическую статистику (6 изд.). Река Аппер Сэдл, штат Нью-Джерси: Pearson Prentice Hall. ISBN  0-13-008507-3. Определение 2.5.1, стр. 109.
3. Хогг, Р. В., Маккин, Дж. У., Крейг, А. Т. (2005). Введение в математическую статистику (6 изд.). Река Аппер Сэдл, штат Нью-Джерси: Pearson Prentice Hall. ISBN  0-13-008507-3. Замечание 2.6.1, с. 120.
4. Буль, Г. (1854). Исследование законов мышления, на которых основаны математические теории логики и вероятностей. Уолтон и Маберли, Лондон. См. «Основные» и «второстепенные» пределы союза Буля на стр. 299.
5. Фреше, М. (1935). Généralisations du théorème des probabilités totales. Fundamenta Mathematicae 25: 379–387.
6. Э. Г. Куниас (1968). «Границы вероятности объединения с приложениями». Анналы математической статистики. 39: 2154–2158.
7. Д. Хантер (1976). «Верхняя граница вероятности объединения». Журнал прикладной теории вероятностей. 13 (3): 597–603.
8. К. Дж. Уорсли (1982). «Улучшенное неравенство Бонферрони и приложения». Биометрика. 69 (2): 297–302.
9. Э. Борос, А. Скоццари, Ф. Тарделла и П. Венециани (2014). «Полиномиально вычислимые оценки вероятности объединения событий». Математика исследования операций. 39 (4): 1311–1329.
10. А. Рамачандра, К. Натараджан (2020). «Тесные границы вероятностей с попарной независимостью». arXiv:2006.00516.