Niezależność parami - Pairwise independence

W teorii prawdopodobieństwa , A parami niezależne zbiór zmiennych losowych jest zbiorem zmiennych losowych z których dowolne dwa są niezależne . Każdy zbiór wzajemnie niezależnych zmiennych losowych jest niezależny od par, ale niektóre kolekcje niezależne od siebie nie są od siebie niezależne. Zmienne losowe niezależne parami ze skończoną wariancją są nieskorelowane .

Para zmiennych losowych X i Y są niezależne wtedy i tylko wtedy, gdy losowy wektor ( X , Y ), z wspólny dystrybuantę (CDF) spełnia ${\ Displaystyle F_ {X, Y} (x, y)}$

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

lub równoważnie, ich gęstość połączenia jest zadowalająca ${\displaystyle f_{X,Y}(x,y)}$

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

Oznacza to, że łączny rozkład jest równy iloczynowi rozkładów krańcowych.

O ile nie jest to jasne w kontekście, w praktyce zwykle odrzuca się modyfikator „wzajemne”, aby niezależność oznaczała wzajemną niezależność . Zdanie takie jak „ X , Y , Z są niezależnymi zmiennymi losowymi” oznacza, że X , Y , Z są od siebie niezależne.

Przykład

Niezależność parami nie oznacza wzajemnej niezależności, jak pokazuje poniższy przykład przypisywany S. Bernsteinowi.

Załóżmy, że X i Y to dwa niezależne rzuty uczciwą monetą, gdzie oznaczamy 1 dla orłów i 0 dla reszek. Niech trzecia zmienna losowa Z będzie równa 1, jeśli dokładnie jeden z tych rzutów monetą skutkował „orzełami”, a 0 w przeciwnym razie. Wtedy łącznie trójka ( X , Y , Z ) ma następujący rozkład prawdopodobieństwa :

${\ Displaystyle (X, Y, Z) = \ lewo \ {{\ rozpocząć {macierz} (0,0,0) i {\ tekst {z prawdopodobieństwem}} \ 1/4 \ \ (0,1,1 )&{\text{z prawdopodobieństwem}}\ 1/4,\\(1,0,1)&{\text{z prawdopodobieństwem}}\ 1/4,\\(1,1,0)&{\ tekst{z prawdopodobieństwem}}\ 1/4.\end{macierz}}\prawo.}$

Tutaj marginalne rozkłady prawdopodobieństwa są identyczne: i The dwuwymiarowe rozkłady również zgodzić: gdzie${\ 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.}$

Ponieważ każdy z rozkładów łączonych parami jest równy iloczynowi ich odpowiednich rozkładów krańcowych, zmienne są parami niezależne:

• X i Y są niezależne i
• X i Z są niezależne i
• Y i Z są niezależne.

Jednak X , Y i Z nie są od siebie niezależne , ponieważ lewa strona równa się na przykład 1/4 dla ( x , y , z ) = (0, 0, 0) podczas gdy prawa strona równa się 1/8 dla ( x , y , z ) = (0, 0, 0). W rzeczywistości każdy z nich jest całkowicie określony przez pozostałe dwa (każdy z X , Y , Z jest sumą (modulo 2) pozostałych). To jest tak dalekie od niezależności, jak tylko mogą być zmienne losowe. ${\ Displaystyle f_ {X, Y, Z} (x, y, z) \ neq f_ {X} (x) f_ {Y} (y) f_ {Z} (z)}$${\ Displaystyle \ {X, Y, Z \}}$

Prawdopodobieństwo zjednoczenia parami niezależnych zdarzeń

Granice prawdopodobieństwa, że suma zmiennych losowych Bernoulliego jest co najmniej jedna, powszechnie znana jako związek graniczny , są dostarczane przez nierówności Boole'a-Frécheta . Chociaż te ograniczenia zakładają tylko jednowymiarowe informacje, zaproponowano również kilka ograniczeń z wiedzą o ogólnych dwuwymiarowych prawdopodobieństwach. Oznaczmy zbiorem zdarzeń Bernoulliego z prawdopodobieństwem wystąpienia dla każdego . Załóżmy, że prawdopodobieństwa dwuwymiarowe są podane przez dla każdej pary wskaźników . Kounias wyprowadził następującą górną granicę :${\ Displaystyle \ {{A} _ {i}, ja \ w \ {1,2,..., n \} \}}$${\ Displaystyle n}$ ${\ Displaystyle \ mathbb {P} (A_ {i}) = p_ {i}}$${\displaystyle i}$${\ Displaystyle \ mathbb {P} (A_ {i} \ czapka A_ {j}) = p_ {ij}}$${\ Displaystyle (i, j)}$

${\ Displaystyle \ mathbb {P} (\ Displaystyle {\ filiżanka} _ {i} A_ {i}) \ leq \ Displaystyle \ suma _ {i = 1} ^ {n} p_ {i} - {\ niedomiar {j} \in \{1,2,..,n\}}{\max }}\sum _{i\neq j}p_{ij},}$

która odejmuje maksymalną wagę drzewa opinającego gwiazdy na kompletnym grafie z węzłami (gdzie wagi krawędzi są podane przez ) od sumy prawdopodobieństw krańcowych . Hunter-Worsley zaostrzył tę górną granicę , optymalizując ją w następujący sposób:${\ Displaystyle n}$${\displaystyle p_{ij}}$${\ Displaystyle \ suma _ {i} p_ {i}}$
${\ Displaystyle \ tau \ w T}$

${\ Displaystyle \ mathbb {P} (\ Displaystyle {\ filiżanka} _ {i} A_ {i}) \ leq \ Displaystyle \ suma _ {i = 1} ^ {n} p_ {i} - {\ niedomiar {\ tau \in T}{\max }}\sum _{(i,j)\in \tau }p_{ij},}$

gdzie jest zbiorem wszystkich drzew opinających na wykresie. Te granice nie są ciasnych możliwe z ogólnymi bivariates nawet gdy wykonalność gwarantowane jest, jak pokazano na Boros et.al. Jednak gdy zmienne są parami niezależne ( ), Ramachandra-Natarajan wykazał, że powiązanie Kouniasa-Huntera-Worsleya jest ścisłe , udowadniając, że maksymalne prawdopodobieństwo zjednoczenia zdarzeń dopuszcza wyrażenie w formie zamkniętej podane jako:${\ Displaystyle T}$ ${\displaystyle p_{ij}}$${\ Displaystyle p_ {ij} = p_ {i} p_ {j}}$

${\ Displaystyle \ max \ mathbb {P} (\ Displaystyle {\ filiżanka} _ {i} A_ {i}) = \ Displaystyle \ min \ lewo (\ suma _ {i = 1} ^ {n} p_ {i} -p_{n}\left(\sum _{i=1}^{n-1}p_{i}\right),1\right)}$

( 1 )

gdzie prawdopodobieństwa są posortowane w porządku rosnącym jako . Warto zauważyć, że ciasne ograniczenie w równaniu. 1 zależy tylko od sumy najmniejszych prawdopodobieństw i największego prawdopodobieństwa . Tak więc, podczas zamawiania z prawdopodobieństw odgrywa rolę w wyprowadzeniu z związana, zamawianie wśród najmniejszych prawdopodobieństw jest nieistotne, ponieważ tylko ich suma jest używany. ${\ Displaystyle 0 \ równoważnik p_ {1} \ równoważnik p_ {2} \ równoważnik \ ldots \ równoważnik p_ {n} \ równoważnik 1}$${\displaystyle n-1}$ ${\ Displaystyle \ suma _ {i = 1} ^ {n-1} p_ {i}}$${\displaystyle p_{n}}$${\displaystyle n-1}$ ${\displaystyle \{p_{1},p_{2},...,p_{n-1}\}}$

Porównanie z unią Boole-Fréchet związane

Przydatne jest porównanie najmniejszych granic prawdopodobieństwa związku odpowiednio z arbitralną zależnością i niezależnością parami . Ciasnych Boole-Fréchet górnej związek związany (przy założeniu, że tylko jednowymiarowego informacje) wyrażony jako:

${\ Displaystyle \ Displaystyle \ max \ mathbb {P} (\ Displaystyle {\ filiżanka} _ {i} A_ {i}) = \ Displaystyle \ min \ lewo (\ suma _ {i = 1} ^ {n} p_ { ja},1\prawo)}$

( 2 )

Jak pokazuje Ramachandra-Natarajan, można łatwo zweryfikować, że stosunek dwóch ścisłych granic w równaniu. 2 i równ. 1 jest górną granicą przez gdzie maksymalna wartość jest osiągnięta, gdy${\ Displaystyle 4/3}$${\ Displaystyle 4/3}$

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

gdzie prawdopodobieństwa są posortowane w porządku rosnącym jako . Innymi słowy, w najlepszym przypadku niezależność parami powiązana w równaniu. 1 zapewnia poprawę w stosunku do ograniczenia jednowymiarowego w równaniu. 2 . ${\ Displaystyle 0 \ równoważnik p_ {1} \ równoważnik p_ {2} \ równoważnik \ ldots \ równoważnik p_ {n} \ równoważnik 1}$${\displaystyle 25\%}$

Uogólnienie

Mówiąc bardziej ogólnie, możemy mówić o k -wise niezależności, dla dowolnego k  ≥ 2. Pomysł jest podobny: zbiór zmiennych losowych jest k -wise niezależny, jeśli każdy podzbiór o wielkości k tych zmiennych jest niezależny. Niezależność k- mądra została wykorzystana w informatyce teoretycznej, gdzie posłużyła do udowodnienia twierdzenia o problemie MAXEkSAT .

Niezależność k- wise jest wykorzystywana w dowodzie, że k-niezależne funkcje mieszające są bezpiecznymi, niepodrabialnymi kodami uwierzytelniania wiadomości .

Zobacz też

• Parami
• Para rozłączny

Bibliografia