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

В теории вероятностей попарно независимый набор случайных величин — это набор случайных величин, любые две из которых независимы . [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}

( Х , И , З ) = { ( 0 , 0 , 0 ) с вероятностью   1 / 4 , ( 0 , 1 , 1 ) с вероятностью   1 / 4 , ( 1 , 0 , 1 ) с вероятностью   1 / 4 , ( 1 , 1 , 0 ) с вероятностью   1 / 4. {\displaystyle (X,Y,Z)=\left\{{\begin{matrix}(0,0,0)&{\text{с вероятностью}}\ 1/4,\\(0,1,1)&{\text{с вероятностью}}\ 1/4,\\(1,0,1)&{\text{с вероятностью}}\ 1/4,\\(1,1,0)&{\text{с вероятностью}}\ 1/4.\end{matrix}}\right.}

Здесь предельные распределения вероятностей идентичны: и Двумерные распределения также совпадают: где ф Х ( 0 ) = ф И ( 0 ) = ф З ( 0 ) = 1 / 2 , {\displaystyle f_{X}(0)=f_{Y}(0)=f_{Z}(0)=1/2,} ф Х ( 1 ) = ф И ( 1 ) = ф З ( 1 ) = 1 / 2. {\displaystyle f_{X}(1)=f_{Y}(1)=f_{Z}(1)=1/2.} ф Х , И = ф Х , З = ф И , З , {\displaystyle f_{X,Y}=f_{X,Z}=f_{Y,Z},} ф Х , И ( 0 , 0 ) = ф Х , И ( 0 , 1 ) = ф Х , И ( 1 , 0 ) = ф Х , И ( 1 , 1 ) = 1 / 4. {\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] вывел следующую верхнюю границу : { А я , я ∈ { 1 , 2 , . . . , н } } {\displaystyle \{{A}_{i},i\in \{1,2,...,n\}\}} н {\displaystyle n} П ( А я ) = п я {\displaystyle \mathbb {P} (A_{i})=p_{i}} я {\displaystyle i} P ( A i ∩ A j ) = p i j {\displaystyle \mathbb {P} (A_{i}\cap A_{j})=p_{ij}} ( i , j ) {\displaystyle (i,j)}

P ( ∪ i A i ) ≤ ∑ i = 1 n p i − max j ∈ { 1 , 2 , . . , n } ∑ i ≠ j p 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] сузили эту верхнюю границу , оптимизировав следующим образом: n {\displaystyle n} p i j {\displaystyle p_{ij}} ∑ i p i {\displaystyle \sum _{i}p_{i}}
τ ∈ T {\displaystyle \tau \in T}

P ( ∪ i A i ) ≤ ∑ i = 1 n p i − max τ ∈ T ∑ ( i , j ) ∈ τ p i j , {\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},}

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

max P ( ∪ i A i ) = min ( ∑ i = 1 n p i − p n ( ∑ i = 1 n − 1 p i ) , 1 ) {\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 зависит только от суммы наименьших вероятностей и наибольшей вероятности . Таким образом, хотя упорядочение вероятностей играет роль в выводе границы, упорядочение среди наименьших вероятностей несущественно, поскольку используется только их сумма. 0 ≤ p 1 ≤ p 2 ≤ … ≤ p n ≤ 1 {\displaystyle 0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1} n − 1 {\displaystyle n-1} ∑ i = 1 n − 1 p i {\displaystyle \sum _{i=1}^{n-1}p_{i}} p n {\displaystyle p_{n}} n − 1 {\displaystyle n-1} { p 1 , p 2 , . . . , p n − 1 } {\displaystyle \{p_{1},p_{2},...,p_{n-1}\}}

Сравнение сБуль–Фреше союз связан

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

max P ( ∪ i A i ) = min ( ∑ i = 1 n p i , 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 ограничено сверху соотношением , при котором максимальное значение достигается, когда 4 / 3 {\displaystyle 4/3} 4 / 3 {\displaystyle 4/3}

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

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

Обобщение

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

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

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

Ссылки

  1. ^ Гут, А. (2005) Вероятность: курс для аспирантов , Springer-Verlag. ISBN  0-387-27332-8 . С. 71–72.
  2. ^ Хогг, Р. В., Маккин, Дж. В., Крейг, А. Т. (2005). Введение в математическую статистику (6-е изд.). Аппер Сэддл Ривер, Нью-Джерси: Pearson Prentice Hall. ISBN 0-13-008507-3.{{cite book}}: CS1 maint: multiple names: authors list (link)Определение 2.5.1, стр. 109.
  3. ^ Хогг, Р. В., Маккин, Дж. В., Крейг, А. Т. (2005). Введение в математическую статистику (6-е изд.). Аппер Сэддл Ривер, Нью-Джерси: Pearson Prentice Hall. 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. ^ ab EG Kounias (1968). «Границы вероятности объединения с приложениями». Анналы математической статистики . 39 (6): 2154–2158. doi : 10.1214/aoms/1177698049 .
  7. ^ ab D. Hunter (1976). «Верхняя граница вероятности объединения». Journal of Applied Probability . 13 (3): 597–603. doi :10.2307/3212481. JSTOR  3212481.
  8. ^ ab KJ Worsley (1982). «Улучшенное неравенство Бонферрони и его применение». Biometrika . 69 (2): 297–302. doi :10.1093/biomet/69.2.297.
  9. ^ Борос, Эндре ; Скоццари, Андреа; Тарделла, Фабио; Венециани, Пьеранджела (2014). «Полиномиально вычислимые границы для вероятности объединения событий». Математика исследования операций . 39 (4): 1311–1329. doi :10.1287/moor.2014.0657.
  10. ^ ab Ramachandra, Arjun Kodagehalli; Natarajan, Karthik (2023). «Жесткие границы вероятности с попарной независимостью». SIAM Journal on Discrete Mathematics . 37 (2): 516–555. arXiv : 2006.00516 . doi : 10.1137/21M140829.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pairwise_independence&oldid=1212685336"