Czy próbka odrzucenia jest jedynym sposobem na uzyskanie prawdziwie jednolitego rozkładu liczb losowych?

Załóżmy, że mamy generator losowy, który generuje liczby w zakresie $[0..R-1]$ o rozkładzie równomiernym i musimy wygenerować liczby losowe w zakresie $[0..N-1]$ o rozkładzie równomiernym.

Załóżmy, że $N < R$ i $N$ nie dzielą równomiernie $R$ ; aby uzyskać naprawdę jednolity rozkład , możemy zastosować metodę próbkowania odrzucania :

jeśli $k$ jest największą liczbą całkowitą taką, że $k N < R$
wybrać liczbę losową $r$ w $[0..R-1]$
jeśli $r < k N$ to wyślij , w przeciwnym razie próbuj z innymi liczbami losowymi r ', r ", ... aż warunek zostanie spełniony $r \mod N$

Czy próbka odrzucenia jest jedynym sposobem na uzyskanie prawdziwie jednolitego rozkładu dyskretnego?

Jeśli odpowiedź brzmi tak, dlaczego?

Uwaga: jeśli $N > R$ pomysł jest taki sam: wygeneruj liczbę losową $r'$ w $[0..R^m-1], R^m >= N$ , na przykład $r' = R(...R(R r_1 + r_2)...)+r_m$ gdzie $r_i$ jest liczbą losową z zakresu $[0..R-1]$

— Vor
źródło

Zobacz to powiązane pytanie na cstheory.SE .

— Raphael

Odpowiedzi:

Tak i nie, w zależności od tego, co rozumiesz przez „jedyny sposób”. Tak, ponieważ nie ma metody, która gwarantowałaby zakończenie, najlepszym, co możesz zrobić (dla ogólnych wartości i ), jest algorytm, który kończy się z prawdopodobieństwem 1. Nie, dzięki czemu „marnotrawstwo” jest tak małe jak chcesz $N$ $R$

Dlaczego gwarantowane zakończenie jest ogólnie niemożliwe

Załóżmy, że masz silnik obliczeniowy (deterministyczny maszynę Turinga czy cokolwiek pływa łodzią), plus wyrocznię, który generuje losowe elementy -elementowe zestawu . Celem jest, aby wygenerować element -elementowe zestawu . Moc twojego silnika zależy tylko od sekwencji wartości zwracanych przez wyrocznię; jest funkcją tej potencjalnie nieskończonej sekwencji . $R$ $[0..R-1]$ $N$ $[0,N-1]$ $f$ $(r_0, r_1, r_2, \ldots)$

Załóżmy, że twój silnik woła wyrocznię co najwyżej razy. Mogą istnieć ślady, dla których wyrocznia jest nazywana mniej niż razy; jeśli tak, wywołanie dodatkowego czasu wyroczni, aby zawsze było wywoływane dokładnie razy, nie zmienia wyniku. Zatem bez utraty ogólności zakładamy, że wyrocznia nazywana jest dokładnie razy. Zatem prawdopodobieństwo wyniku jest liczbą sekwencji takich, że . Ponieważ wyrocznia jest jednorodnym generatorem losowym, każda sekwencja jest równoważna i ma prawdopodobieństwo . Stąd prawdopodobieństwo każdego wyniku ma postać $m$ $m$ $m$ $m$ $x$ $(r_0, \ldots, r_{m-1})$ $f(r_0, \ldots, r_{m-1}) = x$ $1/R^m$ $A/R^m$ gdzie jest liczbą całkowitą od do . $A$ $0$ $R^m$

Jeśli dzieli na część , możesz wygenerować równomierny rozkład na elementów, wywołując generator losowy razy (pozostawia się to jako ćwiczenie dla czytelnika). W przeciwnym razie jest to niemożliwe: nie ma sposobu, aby uzyskać wynik z prawdopodobieństwem . Zauważ, że warunek jest równoważny stwierdzeniu, że wszystkie czynniki pierwsze są również czynnikami (jest to bardziej liberalne niż to, co napisałeś w pytaniu; na przykład możesz wybrać losowy element spośród 4 z 6-stronnym fair umrzeć, mimo że 4 nie dzieli 6). $N$ $R^m$ $m$ $N$ $m$ $1/N$ $N$ $R$

Zmniejszenie ilości odpadów

W swojej strategii, gdy , nie musisz ponownie losować od razu. Intuicyjnie pozostało trochę entropii w którą możesz zachować w miksie. $r \ge k\,N$ $[k\,N .. R-1]$

Załóżmy, że przez cały czas będziesz generował losowe liczby poniżej , a ty generujesz ich liczby naraz, wykonując losowania. Jeśli wykonasz proste próbkowanie odrzucenia dla tej zgrupowanej generacji, marnotrawstwo nad losuje to , tj. Reszta podzielone przez liczbę losowań. Może to być tak mały jak . Kiedy i są pierwszymi pierwszymi, możesz zmniejszyć odpady dowolnie, wybierając odpowiednio duże wartości . Dla ogólnych wartości i $N$ $u$ $d$ $d$ $\dfrac{R^d - k\,N^u}{d}$ $R^d \mathbin{\mathrm{mod}} N^u$ $\gcd(R,N)$ $R$ $N$ $d$ $R$ $N$ , obliczenia są bardziej skomplikowane, ponieważ musisz wziąć pod uwagę generowanie i osobno, ale znowu możesz zmniejszyć odpady dowolnie, używając wystarczająco dużych grup. $\gcd(R,N)$ $N/\gcd(R,N)$

W praktyce, nawet przy stosunkowo nieefektywnych liczbach losowych (np. W kryptografii), rzadko warto robić nic prócz prostego próbkowania odrzucenia, chyba że jest małe. Na przykład w kryptografii, gdzie jest zwykle potęgą 2, a jest zwykle setkami lub tysiącami bitów, jednolite generowanie liczb losowych zwykle przebiega przez próbkowanie z bezpośrednim odrzuceniem w pożądanym zakresie. $N$ $R$ $N$

— Gilles „SO- przestań być zły”
źródło

Pierwszy dowód jest wadliwy: istnienie jest zbyt silne. Możemy mieć maszynę, która zużywa dowolnie wiele elementów, ale zawsze się kończy. Zasadniczo chcemy wykluczyć jedną sekwencję (nigdy nie kończącą się), ale wykluczamy wszystkie oprócz skończonych wielu.

m

$m$

— Raphael

@ Rafael Nie jestem pewien, czy rozumiem, co masz na myśli. Czy możesz podać przykład takiej maszyny?

— Gilles „SO- przestań być zły”

Ach, moje obawy były zbyt ogólne. Tutaj - biorąc pod uwagę brak danych wejściowych - masz rację. Jeśli wszystkie obliczenia zakończą się, jest skończonych wiele (brak danych wejściowych, skończona liczba decyzji na krok, ergo skończone drzewo), dlatego istnieje najdłuższa, która daje ci .

m

$m$

— Raphael

@Raphael Twój komentarz sprawia, że myślę o lepszej prezentacji dla odbiorców TCS: ustaw RNG na wejście TM zamiast wyroczni. Zakładamy, że TM się kończy (w przeciwnym razie algorytm jest niepoprawny). Jeśli istnieje takie , że cokolwiek to wejściowe, TM patrzy na co najwyżej komórek wejściowych, wtedy <bla bla podzielne przez bla nie może mieć możliwych do uzyskania wyników>. W przeciwnym razie dla wszystkich prawdopodobieństwo zażądania co najmniej losowania wynosi co najmniej .

m

$m$

m

$m$

R^{m}

$R^m$

N

$N$

m

$m$

m

$m$

R^{- m}

$R^{-m}$

— Gilles „SO- przestań być zły”

@Raphael: Lemat Königa pokazuje, że jeśli maszyna zawsze kończy pracę, to w rzeczywistości istnieje górna granica jej czasu działania. Działa to tak długo, jak zestaw wyjściowy RNG jest skończony (a poza tym jest trywialnie fałszywy).

— Yuval Filmus,

Twierdzenie Shannona o kodzie źródłowym pokazuje, że w pewnym sensie potrzebujesz próbek (średnio) typu aby wygenerować losową liczbę typu . Dokładniej, Shannon podaje (nieefektywny) algorytm, który dał próbki pierwszego typu, wyprowadza próbki drugiego typu, z dużym prawdopodobieństwem. Pokazuje także, że wysyłanie próbek z dużym prawdopodobieństwem jest niemożliwe. $\log N/\log R$ $[0,\ldots,R-1]$ $[0,\ldots,N-1]$ $m$ $m(\log N/\log R - \epsilon)$ $m(\log N/\log R + \epsilon)$

Twierdzenie Shannona działa również w bardziej ogólnym przypadku przekrzywionego rozkładu wejściowego (i prawdopodobnie również przekrzywionego rozkładu wyjściowego). W takim przypadku musisz zastąpić logarytm entropią. Podczas gdy algorytm podany w twierdzeniu jest definiowany losowo, w niektórych przypadkach można go derandomizować (kosztem nieco gorszej wydajności).

— Yuval Filmus
źródło

W rzeczywistości nie, próbka odrzucenia jest daleka od jedynego sposobu postępowania. Niestety, biorąc pod uwagę, że komputery przechowują wszystkie informacje jako bity, a zatem mogą manipulować tylko losowymi bitami informacji, każdy algorytm narysujący jednolitą losową zmienną z zakresu będzie nieskończony, jeśli rozwój binarnej bazy będzie nieskończony. $N$ $N$

Twierdzenie to jest klasycznym wynikiem Knutha i Yao (1976), którzy opracowali strukturę drzew DDG (drzewa generujące rozkład dyskretny).

Metody ujawnione przez Gillesa są typowym rodzajem działania, które zostało zrobione w celu zmniejszenia marnotrawstwa powstałego w wyniku odrzucenia, ale oczywiście, jeśli można wygenerować po drzewach Knutha i Yao, jest to znacznie, znacznie bardziej wydajne - średnio 96% losowych bitów są zapisane.

Podałem więcej informacji na ten temat w następującym poście CStheory .

— Jérémie
źródło