Na entropii sumy

Szukam oprawionego na entropii $H(X+Y)$ sumy dwóch niezależnych dyskretnych zmiennych losowych i . Oczywiście, Jednak zastosowane do sumy niezależnych zmiennych losowych Bernoulliego , daje to Innymi słowy, granica rośnie liniowo z przy wielokrotnym stosowaniu. Jednak jest obsługiwany na zestawie rozmiaru , więc jego entropia jest co najwyżej $X$ $Y$

H (X + Y) \leq H (X) + H (Y) (*)

$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$

n

$n$

Z_{1}, \dots, Z_{n}

$Z_1, \ldots, Z_n$

H (Z_{1} + Z_{2} + \dots + Z_{n}) \leq n H (Z_{1})

$H(Z_1 + Z_2 + \cdots + Z_n) \leq n H(Z_1)$

n

$n$

Z_{1} + \dots Z_{n}

$Z_1 + \cdots Z_n$

n

$n$

\log n

$\log n$ . W rzeczywistości, według centralnego twierdzenia o limicie, domyślam się, że ponieważ jest zasadniczo obsługiwany na zestawie wielkości .

H (Z_{1} + \dots + Z_{n}) \approx (1 / 2) \log n

$H(Z_1 + \cdots + Z_n) \approx (1/2) \log n$

\sqrt{n}

$\sqrt{n}$

W skrócie, bound w tej sytuacji nieco przewyższa. Po przeczytaniu tego postu na blogu , zbieram wszelkiego rodzaju ograniczenia na są możliwe; czy istnieje granica, która daje właściwe asymptotyki (lub przynajmniej bardziej rozsądne asymptotyki) przy wielokrotnym stosowaniu do sumy zmiennych losowych Bernoulliego? $(*)$ $H(X+Y)$

it.information-theory shannon-entropy robinson
źródło

Nie jestem pewien, o co tak naprawdę pytasz. Jeśli chcesz górnej granicy H (X + Y) w kategoriach H (X) i H (Y), która ma zastosowanie do dowolnych dwóch niezależnych dyskretnych zmiennych losowych X i Y, to H (X + Y) ≤H (X ) + H (Y) jest wyraźnie najlepszym, co możesz uzyskać; rozważmy przypadek, w którym sumy x + y są różne, gdy zakresy x powyżej podparcia zakresów X i y ponad podparcie Y. Jeśli zastosujesz to ogólne ograniczenie do bardzo szczególnego przypadku, to naturalne, że otrzymasz bardzo luźno związany.

Tsuyoshi Ito

@TsuyoshiIto - cóż, jedną z możliwości odpowiedzi, która byłaby świetna, jest nierówność taka jak

gdzie wyrażenia po minusie są równe zero w opisywanym przypadku i sumują się, aby uzyskać lepsze skalowanie za pomocą

przypadku sumy zmiennych losowych Bernoulliego ...

H (X + Y) \leq H (X) + H (Y) - \dots

$H(X+Y) \leq H(X) + H(Y) - \ldots$

n

$n$

robinson

... wydaje mi się, że istnienie nierówności takich jak

sprawia, że przynajmniej prawdopodobne jest, że odpowiedź, której szukam, istnieje .

H (X + Y) \leq 3 H (X - Y) - H (X) - H (Y)

$H(X+Y) \leq 3 H(X-Y) - H(X) - H(Y)$

robinson

Oznacza to, że to, czego szukasz, nie jest górną granicą H (X + Y) pod względem H (X) i H (Y) . Edytuj pytanie.

Tsuyoshi Ito

myślę, że w przypadku, gdy wariancja każdego

jest niewielka w porównaniu do

twoje przypuszczenie jest właściwą odpowiedzią i nie jest trudne do sprecyzowania przy użyciu twierdzenia Berry'ego-Esseena

Z_{i}

$Z_i$

n

$n$

Sasho Nikolov

Odpowiedzi:

W przypadku takich pytań często uzyskuje się właściwą intuicję, myśląc o „płaskich” zmiennych losowych. Oznacza to, że z jako rozkład jednolity na zbiorze o wielkości i jako rozkład jednolity na zbiorze o rozmiarze . $X$ $A$ $2^{H(X)}$ $Y$ $B$ $2^{H(Y)}$

Więc pytanie, które zadajesz, to (z grubsza), co możesz powiedzieć o rozmiarze w porównaniu do i . Ogólnie (np. Jeśli byłyby to zestawy losowe), wtedy rzeczywiście będziesz miał co odpowiada . $|A+B|$ $|A|$ $|B|$ $|A+B| \sim |A|\cdot |B|$ $H(X+Y) \sim H(X)+H(Y)$

Istnieją pewne szczególne przypadki, kiedy , szczególnie gdy i są przedziałami (lub bardziej ogólnie postępami arytmetycznymi). Istnieją wyniki, które mówią, że (przynajmniej pod pewnymi warunkami i jeśli jest prawie tak mały, jak to możliwe), jest to jedyny przypadek. Obszar, w którym badane są takie pytania, jest znany jako „kombinatoryka addytywna”, a niektóre wyniki mają smak, który w grupie jeśli $|A+B| \ll |A|\cdot |B|$ $A$ $B$ $|A+B|$ $(G,+)$ a następnie są w przybliżeniu podgrupami (jak wspominasz w swoim pytaniu, blog Terence Tao omawia niektóre takie wyniki, ogólnie mówiąc, wyniki rozmiaru zestawu można przenieść do ustawienia entropii). $|A+B|=O(|A|+|B|)$ $A,B$ $G$

$A$ $[a..b]$ $B$ $[0..c]$ $(1/2)\log n$ $c=1$ $a=0$ $b=k$ $k=1,...,n-1$ $a \sim k-\sqrt{k}$ $b \sim k+ \sqrt{k}$ $|A+B| \leq |A|+c$

Boaz Barak
źródło

$n$ $Z_1,Z_2,...,Z_n$ $p$ $Z_1+Z_2+...+Z_n$ $np$ $np$ $\frac{1}{2}\log n + O(\log n)$

VSJ
źródło

Może mógłbyś użyć równania:

H (Z_{1} + Z_{2} + \dots + Z_{n}) = H (Z_{1}) + H (Z_{2}) + \dots + H (Z_{n}) - H (Z_{1} | Z_{1} + Z_{2} + \dots + Z_{n}) - H (Z_{2} | Z_{2} + Z_{3} + \dots + Z_{n}) - \dots - H (Z_{n - 1} | Z_{n - 1} + Z_{n})

$H(Z_1+Z_2+\cdots+Z_n)=H(Z_1)+H(Z_2)+\cdots+H(Z_n)-H(Z_1|Z_1+Z_2+\cdots+Z_n)-H(Z_2|Z_2+Z_3+\cdots+Z_n)-\cdots-H(Z_{n-1}|Z_{n-1}+Z_n)$

To mogłoby wyglądać jak termin, który wspomniałeś w komentarzach, niestety nie znam wyników dotyczących liczności negatywnych warunków lub wnikliwych ograniczeń.

Stóg
źródło