Symulowanie prawdopodobieństwa 1 z 2 ^ N przy mniej niż N losowych bitach

Powiedz, że muszę zasymulować następujący rozkład dyskretny:

P (X = k) = {\begin{cases} \frac{1}{2^{N}}, & if k = 1 \\ 1 - \frac{1}{2^{N}}, & if k = 0 \end{cases}

$P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases}$

Najbardziej oczywistym sposobem jest narysowanie losowych bitów i sprawdzenie, czy wszystkie są równe (lub ). Jednak teoria informacji mówi $N$ $0$ $1$

\begin{aligned} S & = - \sum_{i} P_{i} \log P_{i} \\ = - \frac{1}{2^{N}} \log \frac{1}{2^{N}} - (1 - \frac{1}{2^{N}}) \log (1 - \frac{1}{2^{N}}) \\ = \frac{1}{2^{N}} \log 2^{N} + (1 - \frac{1}{2^{N}}) \log \frac{2^{N}}{2^{N} - 1} \\ \to 0 \end{aligned}

$\begin{align} S & = - \sum_{i} P_i \log{P_i} \\ & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\ & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\ & \rightarrow 0 \end{align}$

Tak więc minimalna liczba wymaganych bitów losowych faktycznie maleje, gdy staje się duże. Jak to jest możliwe? $N$

Załóżmy, że działamy na komputerze, na którym bity są twoim jedynym źródłem losowości, więc nie możesz po prostu naciągnąć stronniczej monety.

algorithms information-theory randomness pseudo-random-generators entropy nalzok
źródło

Jest to ściśle związane z teorią kodowania i złożonością Kołmogorowa, jeśli szukasz słów kluczowych do głębszego kopania. Często

Brian Gordon

Odpowiedzi:

Wow, świetne pytanie! Pozwól mi spróbować wyjaśnić rozdzielczość. To zajmie trzy wyraźne kroki.

Pierwszą rzeczą do zapamiętania jest to, że entropia skupia się bardziej na średniej liczbie bitów potrzebnych na losowanie, a nie na maksymalnej liczbie potrzebnych bitów.

W procedurze próbkowania maksymalna liczba losowych bitów potrzebnych na losowanie wynosi bitów, ale średnia potrzebna liczba bitów wynosi 2 bity (średnia rozkładu geometrycznego przy ) - dzieje się tak, ponieważ istnieje prawdopodobieństwa, że potrzebujesz tylko 1 bitu (jeśli pierwszy bit okaże się 1), prawdopodobieństwa, że potrzebujesz tylko 2 bitów (jeśli pierwsze dwa bity okażą się 01), a prawdopodobieństwo, że potrzebujesz tylko 3 bitów (jeśli pierwsze trzy bity okażą się 001) i tak dalej. $N$ $p=1/2$ $1/2$ $1/4$ $1/8$

Drugą rzeczą do odnotowania jest to, że entropia tak naprawdę nie przechwytuje średniej liczby bitów potrzebnych do pojedynczego losowania. Zamiast tego, przechwytuje entropii zamortyzowany liczba bitów potrzebnych do próbki $m$ IID czerpie z tej dystrybucji. Załóżmy, że potrzebujemy $f(m)$ bitów do próbkowania $m$ losowań; wówczas entropia jest granicą $f(m)/m$ jako $m \to \infty$ .

Trzecią rzeczą, aby pamiętać, jest to, że z tej dystrybucji, można spróbować $m$ iid czerpie z mniejszej liczby bitów niż potrzeba do jednego wielokrotnie próbki remisem. Załóżmy, że naiwnie postanowiłeś narysować jedną próbkę (średnio bierze 2 losowe bity), a następnie narysuj inną próbkę (średnio o 2 więcej losowych bitów) i tak dalej, aż powtórzysz to $m$ razy. Wymagałoby to średnio około $2m$ losowych bitów.

Ale okazuje się, że istnieje sposób na próbkowanie z $m$ losowań przy użyciu mniej niż $2m$ bitów. Trudno w to uwierzyć, ale to prawda!

Pozwól, że dam ci intuicję. Załóżmy, że zapisałeś wynik losowania $m$ losowań, gdzie $m$ jest naprawdę duży. Następnie wynik można określić jako ciąg $m$ bitowy. Ten $m$ bitowy ciąg będzie w większości wynosił 0, z kilkoma 1: w szczególności średnio będzie miał około $m/2^N$ 1 (może być mniej więcej, ale jeśli $m$ jest wystarczająco duży, zwykle liczba będzie blisko tego). Długość odstępów między jedynkami jest losowa, ale zwykle będzie nieco mniej więcej w pobliżu $2^N$ (może z łatwością być o połowę mniejszy lub dwa razy większy lub nawet większy, ale o tej wielkości). Oczywiście zamiast zapisywać cały ciąg $m$ bitowy, moglibyśmy zapisać go bardziej zwięźle, zapisując listę długości przerw - która zawiera wszystkie te same informacje, w bardziej skompresowanym formacie. O ile bardziej zwięzły? Cóż, zwykle potrzebujemy około $N$ bitów do przedstawienia długości każdej przerwy; i będzie około $m/2^N$ luk; więc potrzebujemy w sumie około $mN/2^N$ bitów (może być nieco więcej, może być nieco mniej, ale jeśli jest wystarczająco duży, zwykle będzie to bliskie). To o wiele krótsze niż $m$ $m$ bitowy ciąg.

A jeśli istnieje sposób, aby zapisać zwięźle tak zwięźle, być może nie będzie to zaskakujące, jeśli oznacza to, że istnieje sposób na wygenerowanie ciągu przy użyciu liczby losowych bitów porównywalnych z długością ciągu. W szczególności losowo generujesz długość każdej przerwy; jest to próbkowanie z rozkładu geometrycznego z , i można to zrobić przy pomocy średnio losowych bitów z grubsza (nie ). Będziesz potrzebował około losowań z tego rozkładu geometrycznego, więc będziesz potrzebował w przybliżeniu losowych bitów. (Może to być mały stały współczynnik większy, ale nie za dużo większy.) I zauważ, że jest to znacznie mniej niż bity. $p=1/2^N$ $\sim N$ $2^N$ $m/2^N$ $\sim Nm/2^N$ $2m$

Można więc próbka IID wciąga z rozkładu, z zastosowaniem tylko przypadkowych bitów (w przybliżeniu). Przypomnij sobie, że entropia to . Więc oznacza to, że należy spodziewać się entropia (w przybliżeniu) . Trochę to nie działa, ponieważ powyższe obliczenia były pobieżne i prymitywne - ale mam nadzieję, że daje to intuicję, dlaczego entropia jest tym, czym jest i dlaczego wszystko jest spójne i rozsądne. $m$ $f(m) \sim Nm/2^N$ $\lim_{m \to \infty} f(m)/m$ $N/2^N$

DW
źródło

Wow, świetna odpowiedź! Ale czy mógłbyś wyjaśnić, dlaczego próbkowanie z rozkładu geometrycznego za pomocą zajmuje średnio bitów? Wiem, że taka losowa zmienna miałaby średnią , więc przechowywanie zajmuje średnio bitów, ale przypuszczam, że nie oznacza to, że możesz wygenerować jedną z bitów.

p = \frac{1}{2^{N}}

$p=\frac{1}{2^N}$

N

$N$

2^{N}

$2^N$

N

$N$

N

$N$

nalzok

@nalzok, sprawiedliwe pytanie! Czy mógłbyś zadać to jako osobne pytanie? Widzę, jak to zrobić, ale pisanie w tej chwili jest trochę nieporządne. Jeśli zapytasz, ktoś może odpowiedzieć szybciej niż ja. Podejście, o którym myślę, jest podobne do kodowania arytmetycznego. Zdefiniuj (gdzie jest geometrycznym rv), a następnie wygeneruj liczbę losową przedziale i znajdź tak, że . Jeśli piszesz w dół bity binarnym expension jednym na raz, zazwyczaj po spisując bitów , będzie w pełni określony.

q_{i} = Pr [X \leq i]

$q_i = \Pr[X\le i]$

X

$X$

r

$r$

[0, 1)

$[0,1)$

i

$i$

q_{i} \leq r < q_{i + 1}

$q_i \le r < q_{i+1}$

r

$r$

N + O (1)

$N+O(1)$

r

$r$

i

$i$

Więc w zasadzie używasz odwrotnej metody CDF do konwersji równomiernie rozmieszczonej zmiennej losowej na dowolną dystrybucję, w połączeniu z ideą podobną do wyszukiwania binarnego? Będę musiał przeanalizować funkcję kwantylową rozkładu geometrycznego, aby się upewnić, ale ta wskazówka wystarczy. Dzięki!

nalzok

@nalzok, ahh, tak, jest to lepszy sposób, aby o tym myśleć - cudownie. Dziękuję za sugestię. Tak, właśnie to miałem na myśli.

Możesz pomyśleć o tym wstecz: weź pod uwagę problem kodowania binarnego zamiast generowania. Załóżmy, że masz źródło, które emituje symbole zp , . Na przykład, jeśli , otrzymamy . Tak więc (mówi nam Shannon) istnieje unikatowo dekodowalne kodowanie binarne , gdzie (bity danych), tak że potrzebujemy średnio około bitów danych dla każdego oryginalnego symbolu . $X\in \{A,B\}$ $p(A)=2^{-N}$ $p(B)=1-2^{-N}$ $N=3$ $H(X)\approx 0.54356$ $X \to Y$ $Y \in \{0,1\}$ $0.54356$ $X$

(Jeśli zastanawiasz się, jak takie kodowanie może istnieć, biorąc pod uwagę, że mamy tylko dwa symbole źródłowe, i wydaje się, że nie możemy zrobić lepiej niż trywialne kodowanie, , , z jednym bitem na symbol, musisz zrozumieć, że aby zbliżyć się do granicy Shannona, musimy wziąć „rozszerzenia” źródła, to znaczy zakodować sekwencje danych wejściowych jako całości. Zobacz w szczególności kodowanie arytmetyczne). $A\to 0$ $B\to 1$

Gdy powyższe stanie się jasne, jeśli założymy, że mamy odwracalne odwzorowanie , i zauważając, że w granicy Shannona musi mieć maksymalną entropię (1 bit informacji na bit danych), tj. , ma statystyki uczciwej monety, a następnie mamy pod ręką schemat generowania: narysuj losowych bitów (tutaj nie ma związku z ) z uczciwą monetą, zinterpretuj to jako wyjście enkodera i dekoduj z niego . W ten sposób będzie miał pożądany rozkład prawdopodobieństwa i musimy (średnio) monety do wytworzenia każdej wartości . $X^n \to Y^n$ $Y^n$ $Y^n$ $n$ $n$ $N$ $Y^n$ $X^n$ $X^n$ $H(X)<1$ $X$

leonbloy
źródło