Czy istnieje jakiś rozkład jednowymiarowy, z którego nie możemy próbkować?

Mamy ogromną różnorodność metod losowego generowania z rozkładów jednowymiarowych (transformacja odwrotna, akceptacja-odrzucenie, Metropolis-Hastings itp.) I wydaje się, że możemy próbkować z dosłownie dowolnego prawidłowego rozkładu - czy to prawda?

Czy możesz podać jakiś przykład rozkładu jednowymiarowego, którego nie można losowo wygenerować? Wydaje mi się, że ten przykład, w którym jest to niemożliwe, nie istnieje (?), Więc powiedzmy, że przez „niemożliwe” rozumiemy także przypadki, które są bardzo drogie obliczeniowo, np. Które wymagają symulacji siłowych, takich jak narysowanie ogromnych ilości próbek, aby zaakceptować tylko kilka z nich.

Jeśli taki przykład nie istnieje, czy rzeczywiście możemy udowodnić, że możemy generować losowe losowania z dowolnego prawidłowego rozkładu? Jestem po prostu ciekawy, czy istnieje na to kontrprzykład.

Jeśli znasz funkcję rozkładu skumulowanego, , możesz ją odwrócić, analitycznie lub numerycznie, i użyć metody próbkowania z transformacją odwrotną do wygenerowania losowych próbek https://en.wikipedia.org/wiki/Inverse_transform_sampling .$F(x)$

Zdefiniuj . Będzie to obsługiwać każdą dystrybucję, zarówno ciągłą, dyskretną, jak i dowolną kombinację. Zawsze można to rozwiązać numerycznie i być może analitycznie. Niech U będzie próbką ze zmiennej losowej dystrybuowanej jako Uniform [0,1], tj. Z generatora liczb losowych [0,1]. Zatem , zdefiniowane jak powyżej, jest losową próbką ze zmiennej losowej o rozkładzie . F - 1 ( U ) F ( x $F^{-1}(y) = inf(x:F(x) \ge y)$$F^{-1}(U)$$F(x)$

To może nie być najszybszy sposób generowania losowych próbek, ale jest to sposób, zakładając, że F (x) jest znany.

Jeśli F (x) nie jest znane, to inna historia.

Gdy rozkład jest zdefiniowany tylko przez funkcję generowania momentu lub przez jego funkcję charakterystyczną , rzadko można znaleźć sposoby generowania z tych dystrybucji.$\phi(t)=\mathbb{E}[\exp\{tX\}]$$\Phi(t)=\mathbb{E}[\exp\{itX\}]$

Odpowiednim przykładem jest rozkład stabilny , który nie ma znanej postaci dla gęstości lub cdf, nie ma funkcji generowania momentu, ale funkcję charakterystyczną dla postaci zamkniętej.$\alpha$

W statystykach bayesowskich rozkłady tylne związane z trudnymi prawdopodobieństwami lub po prostu zestawami danych, które są zbyt duże, aby zmieściły się w jednym komputerze, można uznać za niemożliwe do (dokładnego) zasymulowania.

Zakładając, że odnosisz się do ciągłych dystrybucji. Korzystając z transformacji całkowej prawdopodobieństwa , można symulować z dowolnego rozkładu jednowymiarowego , symulując a następnie biorąc . Możemy więc symulować mundur, a następnie ta część jest wykonywana. Jedyną rzeczą, która może wykluczyć symulację z jest to, że nie można obliczyć jej odwrotności , ale musi to być związane z trudnościami obliczeniowymi, a nie czymś teoretycznym.$F$$u \sim (0,1)$$F^{-1}(u)$$F$$F^{-1}$

Teraz, gdy twoje pytanie przekształciło się w „trudne do próbkowania”, po prostu weź dowolny model z niewiarygodnym prawdopodobieństwem , przypisz wcześniejszą dystrybucję do parametrów modelu i załóżmy, że interesuje Cię marginalna tylna dystrybucja jednego z wpisów . Oznacza to, że musisz pobrać próbkę z tylnej części ciała, co jest trudne do rozwiązania ze względu na trudność prawdopodobieństwa.${\bf \theta} = (\theta_1,...,\theta_d)$$\theta_j$

W niektórych przypadkach istnieją metody przybliżenia próbki z tego tylnego odcinka, ale w tej chwili nie istnieje dokładna ogólna metoda.

Nie jestem pewien, czy tak naprawdę jest to odpowiedź ... Zgaduję (ale nie wiem), że nie można próbkować z tylko skończonej dystrybucji addytywnej. Przykładem może być równomierny rozkład liczb wymiernych, który może istnieć tylko jako rozkład skończony addytywny. Aby to zobaczyć, niech będzie wyliczeniem racjonalności. Ponieważ rozkład jest jednolity, dla każdego pojedynczego , więc ale .$(q_i)_{i=1}^\infty$$P(X=q_i)=0$$i$$\sum_{i=1}^\infty P(X=q_i)=0$$P(X\in \mathbb{Q})=1$

Jeśli ta odpowiedź wydaje się dziwna, a nawet nieistotna, spójrz na bardziej praktyczne przykłady, które czasami są używane w wnioskowaniu bayesowskim: Jednolity wcześniejszy rozkład rzeczywistego parametru, takiego jak średnia rozkładu normalnego, powiedzmy . Można to modelować za pomocą „gęstości” (nie rzeczywistej gęstości prawdopodobieństwa), która jest identyczna: . Taki uprzedni może być wykorzystany w analizie Bayesa (i czasami jest używany, patrz klasyczna książka Box & Tiao), ale nie możemy z niego próbkować. I zdefiniowany w ten sposób rozkład prawdopodobieństwa jest tylko skończony addytywnie, co można zobaczyć za pomocą argumentu podobnego do powyższego przykładu liczby wymiernej. $\mu$$\pi(\mu) = 1$

Czy możesz podać jakiś przykład rozkładu jednowymiarowego, którego nie można losowo wygenerować?

Niech będzie Stałą Chaitina i spróbuje (rozkład) zmiennej losowej, która jest stale .$c$$c$

Jeśli interesuje Cię tylko próbkowanie zmiennych losowych, których wartości można rozsądnie aproksymować 64-bitowymi liczbami zmiennoprzecinkowymi, lub masz podobną tolerancję na błąd skończony w wartości, a mimo to nie reprezentujesz swoich próbek jako maszyny Turinga , rozważ to:

Niech z i spróbuj go wypróbować. Wartości i są doskonale reprezentowalne (na przykład liczby zmiennoprzecinkowe 64-bitowe bez błędów), ale myślę , że wygenerujesz je na niewłaściwych częstotliwościach, chyba że rozwiążesz problem zatrzymania.$X \sim \text{Ber}(p)$$p = 1 - c$$0$$1$

Dwa CDF są fragmentarycznie stałe: jeden to na i na . Drugi to na , następnie na i na . Oznacza to, że jednym z nich istotna w -osiowy, drugi z -osiowy. Nie jestem pewien, co sprawia, że ​​próbkowanie jest najtrudniejsze, więc wybierz ten, który najbardziej lubisz ;-)$0$$(-∞, c)$$1$$[c, ∞)$$0$$(-∞, 0)$$c$$[0, 1)$$1$$[1, ∞)$$c$$x$$y$

powiedzmy, że przez „niemożliwe” rozumiemy także przypadki, które są bardzo drogie obliczeniowo, np. które wymagają symulacji siłowych, takich jak pobieranie ogromnych ilości próbek, aby zaakceptować tylko kilka z nich.

W tym przypadku oczywista odpowiedź wydaje się oczywista:

• Próbkuj równomiernie pierwsze czynniki gdzie jest duże (tj. Przełam RSA).$n$$n$
• Próbkuj preimages funkcji kryptograficznej funkcji skrótu (tj. Generuj bitcoiny i przełam git i merkurial).
• Wypróbuj zestaw optymalnych strategii Go (z chińskimi zasadami superko, które sprawiają, że wszystkie gry są skończone - o ile rozumiem).

Trochę bardziej formalnie: Daję ci duży przykład problemu z NP-zupełnym (lub EXP-zupełnym itp.) I proszę o jednolite próbkowanie zestawu rozwiązań dla mnie.

Prawdopodobnie powinienem zaakceptować jako rozwiązanie na brak instancji (i tylko na brak instancji, i byłoby to jedyne rozwiązanie). Powinienem również wymyślić biject między np. Liczbami całkowitymi (zakładając, że chcesz próbkować członków ) a rozwiązaniami - co jest często dość trywialne, po prostu traktuj reprezentacje bazy 2 jako przypisania prawdy dla mojej instancji SAT, na przykład: i może użyj aby przedstawić .$\bot$$\mathbb{R}$$-1$$\bot$

Możesz łatwo sprawdzić, czy jakieś przypisanie prawdy spełnia moją instancję SAT, a po sprawdzeniu ich wszystko wiesz, czy ktoś tak robi, więc w pełni określiłem CDF, podając ci formułę boolowską (lub obwód), ale jeszcze próbowałem odpowiednią dystrybucję musicie zasadniczo stać się czymś co najmniej tak potężnym jak wyrocznia rozwiązująca SAT.

Dałem ci więc niepoliczalną liczbę, która powinna wrzucić piasek na twoje koła zębate, i dałem ci CDF, którego obliczenia są powolne. Może następnym oczywistym pytaniem jest coś takiego: czy istnieje CDF reprezentowany w jakiejś wydajnej formie (np. Może być oceniany w czasie wielomianowym) tak, że trudno jest wygenerować próbki o takim rozkładzie? Nie znam odpowiedzi na to pytanie. Nie znam odpowiedzi na to pytanie.