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

12

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.

— Tim
źródło

6

Myślę, że to naprawdę sprowadza się do tego, co rozumiesz przez „nie można / niemożliwe”. Zdarzają się przypadki, gdy ocena cdf i pdf jest bardzo kosztowna, na przykład, co sprawiłoby, że większość metod jest zabroniona, i nie jest trudno wymyślić kształty dystrybucyjne, w których dobre obwiednie koperty na pdf (dla akceptacji-odrzucenia to przede wszystkim unika oceny funkcji) nie są łatwo dostępne. Nie udałoby się to w przypadku, który już wykluczasz, a my możemy sprawić, że nawet droższy (średnio na odchylenie) do obliczenia niż przy użyciu opcji akceptowania-odrzucania (co wykluczałoby próbę użycia odwrotności numerycznej pliku cdf)

F

$F$

— Glen_b -Reinstate Monica

3

Nie możemy narysować jednorodnych losowych próbek z zestawu liczb niewymiernych w przedziale (0,1) za pomocą komputera. Dowód pozostaje jako ćwiczenie dla czytelnika.

— Cliff AB,

2

@Cliff AB Można temu zaradzić za pomocą arytmetyki interwałów. Zdefiniuj (najmniejszy) odstęp wokół każdego możliwego do oszacowania przez komputer (racjonalnego) punktu, tak aby całość [0,1] była objęta tymi przedziałami. Dla każdego narysowanego przez komputer „jednolitego” narysowanego oszacuj t (z zaokrągleniem na zewnątrz) przedział odwrotny do funkcji rozkładu skumulowanego na tym argumencie przedziału. Spowoduje to wygenerowanie próbki losowej zmiennej losowej, przy 100% gwarancji, że będzie zawierać prawdziwą próbkę.

— Mark L. Stone,

2

Mam na myśli to, że już uznajesz za wystarczająco nieefektywne przyjęcie odrzucenia jako „niemożliwe”, jeśli uczynisz je wystarczająco drogimi, aby każde inne podejście, o którym wiesz, było gorsze (wymaga więcej obliczeń), prawdopodobnie uznałbyś je również za „niemożliwe”. Konstruowanie kosztownych i trudnych do oszacowania wartości F i F nie jest takie trudne, a uczynienie ich tak, że oczywiste sposoby unikania faktycznego obliczania przez większość czasu są również nieefektywne, wydaje się możliwe ,,, ctd

— Glen_b -Reinstate Monica

1

ctd ... (ale ogólnie ludzie są dość pomysłowi, więc to, co wydaje się bardzo trudne, może być wykonalne, jeśli wpadniesz na dobry pomysł, który obejdzie większość problemu). Jeśli mówimy, że „przybliżenie do takiej a takiej dokładności jest w porządku”, wówczas wiele z tych trudności można obejść w wielu przypadkach (na przykład można zbudować duże tabele odnośników / generowanie z histogramów, powiedzmy, takie że przez większość czasu generujesz przybliżone wartości dość szybko).

— Glen_b

15

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}(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.

— Mark L. Stone
źródło

2

Jeśli nie jest znane, to co jest znane? Oczywiście to jest istotne. Jeśli nic nie wiesz, nie będziesz w stanie nic zrobić. Jeśli coś wiesz, to zależy od tego, co to jest.

F (x

$F(x$

— Mark L. Stone,

@Tim W rzeczywistości dość często nie znamy F (X), ale możemy generować z niego próbki. Jest to typowy scenariusz w symulacji stochastycznej Monte Carlo.

— Mark L. Stone,

@Tim: Jeśli nie jesteś zainteresowany tą historią, nie jest jasne, jaką historią jesteś zainteresowany. W odpowiedzi na komentarz Glen_b powiedziałeś, że nie zajmujesz się nieefektywnym próbkowaniem. Ta metoda, choć nieefektywna, pozwala na próbkowanie z dowolnego pliku pdf (przy założeniu, że nie jest tak źle zachowana, że integracja numeryczna kończy się niepowodzeniem, ale nie sądzę, aby ktokolwiek dbał o stosowanie takich dystrybucji). Więc jeśli nie interesują Cię, powiedzmy, dystrybucje, które są nieciągłe w nieskończonej liczbie miejsc, powinna to być odpowiedź na twoje pytanie: tak, możemy.

— Cliff AB

W rzeczywistości, jeśli jest znany, ale nie , jest to problem.

F

$F$

F^{- 1}

$F^{-1}$

— Xi'an

1

To zależy, co masz na myśli przez problem. Jeśli jest znany, to według mojej odpowiedzi jest zawsze dobrze zdefiniowany i można go rozwiązać numerycznie. To może nie być tak szybkie, jak chcesz, więc jeśli masz na myśli problem, ok. Jeśli nie to masz na myśli, to na czym polega problem?

F

$F$

F^{- 1} (y) = i n f (x : F (x) \geq y)

$F^{-1}(y) = inf(x:F(x) \ge y)$

— Mark L. Stone,

7

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.

— Xi'an
źródło

Jeśli znasz tylko funkcję generowania momentu, możesz użyć przybliżenia saddlepoint, a następnie przeprowadzić z niego symulację.

— kjetil b halvorsen

1

@ Xi'an Pominąłeś słowo „sprawnie”. W najgorszym przypadku można odwrócić liczbowo odwrócenie liczbowe transformacji. To wykona zadanie, może nie „skutecznie”, ale to zrobi.

— Mark L. Stone,

3

@kjetilbhalvorsen: przybliżenie saddlepoint jest rozwiązaniem zaproponowanym w linku, który umieszczam. Ale jest to przybliżenie!

— Xi'an

2

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}$

— Conti
źródło

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.

— Noah
źródło

... ale pytanie dotyczy dystrybucji jednowymiarowych. Istnieje wiele przykładów skomplikowanych modeli, w których MCMC nie zbiega się nawet po ogromnej liczbie iteracji.

— Tim

@Tim I właśnie dlatego powiedziałem marginalnie a posteriori , co oznacza jednowymiarowe ... Wydaje mi się, że nie masz jasności, o co pytasz. Dwie pierwsze odpowiedzi są jasne, że teoretycznie można próbkować z dowolnej dystrybucji, o ile ją znasz.

— Noah

1

Głosuję za postawieniem tego pytania [ON HOLD], dopóki OP nie wyjaśni, o co pyta, i przestanę zmieniać pytanie za każdym razem, gdy pojawi się nowa odpowiedź, aby odpowiedzi nie były możliwe.

— Noah

Ja nie zmienia moje pytanie „Za każdym razem pojawia się nowy odpowiedź” ... Oczywiście model statystyczny z prawdopodobieństwa i przed nie jest jednowymiarowy, ponieważ jest zadeklarowana pod względem rozkładu warunkowego. Jest to jedno zmienne, jeśli próbkujesz od tyłu, ale sądzę, że zakładasz, że mamy już rozkład krańcowy, więc nie ma problemu z intracable tylnym.

— Tim

1

Mylimy marginalną z jednowymiarową , gdy te dwa pojęcia nie mają związku. Jednowymiarowa oznacza, że zmienna losowa znajduje się w , natomiast marginalna oznacza, że rozkład można przedstawić jako całkę względem innej gęstości. W rzeczywistości użycie tej integralnej reprezentacji oznacza, że jednoznaczną wartość rv można symulować, najpierw symulując wartość zmiennej wieloczynnikowej rv.

R

$\mathbb{R}$

— Xi'an

1

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$

— kjetil b halvorsen
źródło

0

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.

— Jonas Kölker
źródło