Ograniczone wzajemne informacje ograniczają się do punktowej wzajemnej informacji

18

Załóżmy, że mam dwa zbiory X i oraz łączny rozkład prawdopodobieństwa dla tych zbiorów . Niech i oznaczają brzegowe rozkładu ponad i odpowiednio.Yp(x,y)p(x)p(y)XY

Wspólna informacja między i jest zdefiniowana jako: XY

I(X;Y)=x,yp(x,y)log(p(x,y)p(x)p(y))

tzn. jest to średnia wartość punktowej wzajemnej informacji pmi .(x,y)log(p(x,y)p(x)p(y))

Załóżmy, że znam górną i dolną granicę dla pmi : tj. Wiem, że dla wszystkich następujące blokady: (x,y)x,y

klog(p(x,y)p(x)p(y))k

Jaka górna granica oznacza to dla . Oczywiście oznacza to , ale chciałbym ściślej związać, jeśli to możliwe. Wydaje się prawdopodobne, aby mnie, bo p określa rozkład prawdopodobieństwa i PMI nie może zająć jego maksymalną wartość (lub nawet być nieujemna) dla każdej wartości i .I(X;Y)I(X;Y)k(x,y)xy

Florian
źródło
1
Kiedy prawdopodobieństwa łączne i krańcowe są jednakowe, pmi ( , ) jest równomiernie zerowe (a zatem nieujemne, najwyraźniej zaprzecza twojemu ostatniemu stwierdzeniu, ale tylko nieznacznie). Wydaje mi się, że jeśli się nie mylę, zaburzanie tej sytuacji przez małe podzbiory wskazuje, że granice pmi nie mówią prawie nic o samym . xyX×YI(X;Y)
whuber
1
W rzeczywistości, jeśli i są niezależne, to jest stały, niezależnie od rozkładów krańcowych. Tak jest cała grupa rozkładów , dla których uzyskuje swoją maksymalną wartość dla każdego i . XYpmi(x,y)p(x,y)pmi(x,y)xy
kardynał
Tak, z pewnością jest prawdą, że pmi może być równe dla wszystkich i , ale to nie wyklucza ściślejszej granicy. Na przykład nie jest trudno udowodnić, że . Jest to gdy , i jest nietrywialnym wzmocnieniem związanego gdy . Zastanawiam się, czy istnieją trywialne granice, które mają bardziej ogólny charakter. (x,y)xyI(X;Y)k(ek1)k2k<1kk<1
Florian
1
Wątpię, aby uzyskać lepszą granicę niż dla . Jeśli chcesz się bardziej przyjrzeć, spróbuj ponownie sformułować swoje pytanie pod względem rozbieżności KL między p (x) p (y) i p (x, y). Nierówność Pinskera stanowi dolną granicę MI, która może potwierdzić moje przeczucie. Zobacz także sekcję 4 ajmaa.org/RGMIA/papers/v2n4/relog.pdf . O(k2)k0
vqv

Odpowiedzi:

5

Mój wkład składa się z przykładu. Ilustruje pewne ograniczenia, w jaki sposób można ograniczyć wzajemne informacje, biorąc pod uwagę granice wzajemnej informacji punktowej.

Wziąć X=Y={1,,n} i p(x)=1/n dla wszystkich xX . Dla dowolnego m{1,,n/2} niech k>0 będzie rozwiązaniem równania

mek+(nm)ek=n.
Następnie umieszczamy masę punktową ek/n2 in nm punktów w przestrzeni produktu {1,,n}2 w taki sposób, że w każdym rzędzie i każdej kolumnie znajduje się m tych punktów. (Można to zrobić na kilka sposobów. Zacznij na przykład od pierwszych m punktów w pierwszym rzędzie, a następnie wypełnij pozostałe rzędy, przesuwając m punkty o jeden w prawo z warunkiem cyklicznej granicy dla każdego rzędu). Masę punktową ek/n2 w pozostałych punktów. Suma tych mas punktowych wynosi n mn2nm więc dają miarę prawdopodobieństwa. Wszystkie prawdopodobieństwa punktu krańcowego są m
nmn2ek+n2nmn2ek=mek+(nm)ekn=1,
więc oba rozkłady krańcowe są jednolite.
mn2ek+mnn2ek=1n,

Z konstrukcji jasno wynika, że dla wszystkich x , y { 1 , , n } i (po niektórych obliczeniach) I ( X ; Y ) = k n mpmi(x,y){k,k},x,y{1,,n} z wzajemnego informowania zachowują się tak,k2/2dlak0i jakokdlak.

I(X;Y)=knmn2ekkn2nmn2ek=k(1ekekek(ek+ek)ek),
k2/2k0kk

NRH
źródło
1

Nie jestem pewien, czy tego właśnie szukasz, ponieważ jest to głównie algebraiczne i nie do końca wykorzystuje właściwości p będące rozkładem prawdopodobieństwa, ale tutaj możesz spróbować.

Ze względu na granice pmi, wyraźnie p(x,y)p(x)p(y)ek and thus p(x,y)p(x)p(y)ek. We can substitute for p(x,y) in I(X;Y) to get I(X;Y)x,yp(x)p(y)eklog(p(x)p(y)ekp(x)p(y))=x,yp(x)p(y)ekk

I'm not sure if that's helpful or not.

EDIT: Upon further review I believe this is actually less useful than the original upper bound of k. I won't delete this though in case it might hint at a starting point.

Michael McGowan
źródło
The value of this bound becomes apparent after you note x,yp(x)p(y)=1 and (since k0) that ek1.
whuber
Yes, when I realized that I made my edit.
Michael McGowan