Odwróć technikę Boxa-Muellera : z każdej pary normalnych można zbudować dwa niezależne mundury jako atan2 ( Y , X ) (w przedziale [ - π , π ] ) i exp ( - ( X 2 + Y 2 ) / 2 ) (w przedziale [ 0 , 1 ] ).(X,Y)atan2(Y,X)[−π,π]exp(−(X2+Y2)/2)[0,1]
Podjąć normalne w grupach po dwa, a suma ich kwadratów, aby uzyskać sekwencję zmiennych towarzyszących Y 1 , Y 2 , ... , Y i , ... . Wyrażenia uzyskane z parχ22Y1,Y2,…,Yi,…
Xi=Y2iY2i−1+Y2i
będzie miał rozkład , który jest jednolity.Beta(1,1)
Że wymaga to tylko podstawowej, prostej arytmetyki, powinno być jasne.
Ponieważ dokładny rozkład współczynnika korelacji Pearsona dla czteroparowej próbki ze standardowej dwuwymiarowej Rozkład normalny jest równomiernie rozłożony na , możemy po prostu wziąć normalne w grupach po cztery pary (to znaczy, osiem wartości w każdego zestawu) i zwraca współczynnik korelacji tych par. (Obejmuje to prostą arytmetykę plus dwie operacje pierwiastkowe).[−1,1]
Od czasów starożytnych wiadomo, że cylindryczny rzut kuli (powierzchnia w trzech przestrzeniach) ma równą powierzchnię . Oznacza to, że w rzucie równomiernego rozkładu na kulę zarówno współrzędna pozioma (odpowiadająca długości geograficznej), jak i współrzędna pionowa (odpowiadająca szerokości geograficznej) będzie miała równomierne rozkłady. Ponieważ trójwartościowy standardowy rozkład normalny jest sferycznie symetryczny, jego rzut na kulę jest jednorodny. Uzyskanie długości geograficznej jest zasadniczo tym samym obliczeniem co kąt w metodzie Boxa-Muellera ( qv ), ale rzutowana szerokość geograficzna jest nowa. Rzut na sferę normalizuje jedynie potrójną współrzędną iw tym punkcie z jest rzutowaną szerokością geograficzną. Zatem weź zmienne Normalne w grupach trzyosobowych, X 3 i - 2 , X 3 i - 1 , X 3 i , i oblicz(x,y,z)zX3i−2,X3i−1,X3i
X3iX23i−2+X23i−1+X23i−−−−−−−−−−−−−−−−√
dla .i=1,2,3,…
Ponieważ większość systemów komputerowych reprezentacji liczb w formacie binarnym , jednolity numer generacji zazwyczaj zaczyna się od produkcji równomiernie rozłożonych liczb całkowitych pomiędzy i 2 32 - 1 (lub wysokiej mocy 2 związane z długością słowa komputer) i przeskalowanie je w razie potrzeby. Takie liczby całkowite są reprezentowane wewnętrznie jako ciągi 32 cyfr binarnych. Możemy uzyskać niezależne losowe bity poprzez porównanie zmiennej Normal z jej medianą. Wystarczy zatem podzielić zmienne normalne na grupy wielkości równe pożądanej liczbie bitów, porównać każdą ze średnią i złożyć wynikowe sekwencje wyników prawda / fałsz w liczbę binarną. Pisanie k0232−1232kdla liczby bitów i dla znaku (to znaczy H ( x ) = 1 gdy x > 0 i H ( x ) = 0 w przeciwnym razie) możemy wyrazić wynikową znormalizowaną jednolitą wartość w [ 0 , 1 ) za pomocą wzoruHH(x)=1x>0H(x)=0[0,1)
∑j=0k−1H(Xki−j)2−j−1.
Zmienne można wyciągnąć z dowolnego ciągłego rozkładu, którego mediana wynosi 0 (na przykład standardowa Normalna); są przetwarzane w grupach k, przy czym każda grupa wytwarza jedną taką pseudo-jednolitą wartość.Xn0k
Próbkowanie przy odrzuceniu jest standardowym, elastycznym i potężnym sposobem rysowania zmiennych losowych z dowolnych rozkładów. Załóżmy, że rozkład docelowy ma format PDF . Wartość Y jest rysowana zgodnie z innym rozkładem w formacie PDF g . W etapie odrzucania rysowana jest jednolita wartość U leżąca między 0 a g ( Y ) niezależnie od Y i porównywana z f ( Y ) : jeśli jest mniejsza, YfYgU0g(Y)Yf(Y)Yzostaje zachowany, ale w przeciwnym razie proces się powtarza. To podejście wydaje się jednak okrągłe: w jaki sposób generujemy zmienną jednolitą z procesem, który wymaga na początku zmiennego jednolitego?
Odpowiedź jest taka, że tak naprawdę nie potrzebujemy jednolitej wariacji, aby wykonać krok odrzucenia. Zamiast tego (zakładając ), możemy rzucić uczciwą monetą, aby uzyskać losowo 0 lub 1 . Będzie to interpretowane jako pierwszy bit w binarnej reprezentacji zmiennej zmiennej U w przedziale [ 0 , 1 ) . Gdy wynik jest 0 , to znaczy 0 ≤ U < 1 / 2 ; w przeciwnym razie, 1 / 2 ≤ U < 1 . g(Y)≠001U[0,1)00≤U<1/21/2≤U<1Połowę czasu, to wystarczy, aby zdecydować, etap odrzucenia: jeśli a moneta jest 0 , Y należy przyjąć; jeśli f ( T ) / g ( Y ) < 1 / 2 a moneta jest 1 , Y należy odrzucić; w przeciwnym razie, musimy ponownie odwrócić monetę w celu uzyskania następny bit U . Ponieważ - bez względu na wartość f ( Yf(Y)/g(Y)≥1/20Yf(Y)/g(Y)<1/21YU posiada - nie jest 1 / 2 szansa zatrzymania po każdej klapki, oczekiwana liczba koziołki jest tylko 1 / 2 ( 1 ) + 1 / 4 ( 2 ) + 1 / 8 ( 3 ) + ⋯ + 2 - n ( n ) + ⋯ = 2 .f(Y)/g(Y)1/21/2(1)+1/4(2)+1/8(3)+⋯+2−n(n)+⋯=2
Pobieranie próbek odrzucenia może być opłacalne (i wydajne), pod warunkiem, że spodziewana liczba odrzuceń jest niewielka. Możemy to osiągnąć, dopasowując największy możliwy prostokąt (reprezentujący jednolity rozkład) pod normalnym plikiem PDF.
Korzystanie Rachunek zoptymalizować obszar prostokąta, można zauważyć, że jego punkty końcowe powinny leżeć w , gdzie jego wysokość jest równa exp ( - 1 / 2 ) / √±1, co czyni jego powierzchnię nieco większą niż0,48. Dzięki zastosowaniu tego standardowego gęstość zwykle Jakg, odrzucając wszystkie wartości spoza przedziału[-1,1],automatycznie lub w inny sposób, stosując procedurę odrzucenia, otrzymamy w jednolity zmiennych towarzyszących[-1,1]skutecznie:exp(−1/2)/2π−−√≈0.2419710.48g[−1,1][−1,1]
W ułamku czasu, Zmienna normalna leży poza [ - 1 , 1 ] i jest natychmiast odrzucana. ( Φ jest standardowym normalnym CDF.)2Φ(−1)≈0.317[−1,1]Φ
W pozostałym ułamku czasu należy zastosować procedurę odrzucenia binarnego, wymagającą średnio dwóch dodatkowych zmiennych normalnych.
Ogólna procedura wymaga średnio kroki.1/(2exp(−1/2)/2π−−√)≈2.07
Oczekiwana liczba zmiennych normalnych potrzebnych do uzyskania każdego jednolitego wyniku działa
2eπ−−−√(1−2Φ(−1))≈2.82137.
Chociaż jest to dość wydajne, należy pamiętać, że (1) obliczenie normalnego PDF wymaga obliczenia wykładniczego i (2) wartość musi zostać obliczona raz na zawsze. To wciąż trochę mniej obliczeń niż metoda Boxa-Muellera ( qv ).Φ(−1)
Te statystyki zamówień o równomiernym rozkładzie mają wykładnicze luk. Ponieważ suma kwadratów dwóch normalnych (średniej zerowej) jest wykładnicza, możemy wygenerować realizację niezależnych mundurów przez zsumowanie kwadratów par takich normalnych, obliczenie skumulowanej ich sumy, przeskalowanie wyników w celu uzyskania przedziału [ 0 , 1 ] i upuszczenie ostatniego (który zawsze będzie równy 1 ). Jest to przyjemne podejście, ponieważ wymaga tylko podniesienia do kwadratu, zsumowania i (na końcu) pojedynczego podziału.n[0,1]1
Wartości będą automatycznie rosły w porządku rosnącym. Jeśli takie sortowanie jest pożądane, metoda ta jest lepsza pod względem obliczeniowym od wszystkich innych, o ile pozwala uniknąć kosztu O ( n log ( n ) ) . Jeśli jednak potrzebna jest sekwencja niezależnych mundurów, losowe posortowanie tych n wartości załatwi sprawę. Ponieważ (jak widać w metodzie Boxa-Muellera, qv ) stosunki każdej pary normalnych są niezależne od sumy kwadratów każdej pary, mamy już środki do uzyskania tej losowej permutacji: uporządkuj skumulowane sumy według odpowiednich stosunków . (Jeśli nnO(nlog(n))nnjest bardzo duży, proces ten można przeprowadzić w mniejszych grupach przy niewielkiej utracie wydajności, ponieważ każda grupa potrzebuje tylko 2 ( k + 1 ) normałów, aby utworzyć k jednolitych wartości. W przypadku ustalonego k asymptotyczny koszt obliczeniowy wynosi zatem O ( n log ( k ) ) = O ( n ) , wymagając 2 n ( 1 + 1 / k ) Zmiennych normalnych w celu wygenerowania n jednolitych wartości.)k2(k+1)kkO(nlog(k))O(n)2n(1+1/k)n
W doskonałym przybliżeniu każda zmienna Normal z dużym odchyleniem standardowym wygląda jednolicie w zakresach o wiele mniejszych wartości. Po zwinięciu tego rozkładu do zakresu (biorąc tylko ułamkowe części wartości), uzyskujemy w ten sposób rozkład, który jest jednolity dla wszystkich praktycznych celów. Jest to niezwykle wydajne, wymagające jednej z najprostszych operacji arytmetycznych ze wszystkich: wystarczy zaokrąglić każdą wartość normalną do najbliższej liczby całkowitej i zatrzymać nadmiar. Prostota tego podejścia staje się przekonująca, gdy przeanalizujemy praktyczne wdrożenie:[0,1]R
rnorm(n, sd=10) %% 1
niezawodnie wytwarza n
jednolite wartości w przedziale kosztem tylko zmiennych normalnych i prawie żadnych obliczeń.[0,1]n
(Nawet jeśli odchylenie standardowe wynosi , plik PDF z tym przybliżeniem różni się od jednolitego pliku PDF, jak pokazano na poniższym rysunku, o mniej niż jedną część na 10 8 ! Aby to niezawodnie wykryć wymagałoby próbki 10 16 wartości - to już nie jest w stanie wykonać żadnego standardowego testu losowości. Przy większym odchyleniu standardowym niejednorodność jest tak mała, że nie można jej nawet obliczyć. Na przykład przy SD 10 jak pokazano w kodzie, maksymalne odchylenie od jednolitości PDF ma tylko 10 - 857 ).110810161010−857
W każdym przypadku zmienne normalne „ze znanymi parametrami” można łatwo zaktualizować i przeskalować do przyjętych wyżej norm normalnych. Następnie powstałe równomiernie rozłożone wartości można zaktualizować i przeskalować w celu uwzględnienia dowolnego pożądanego przedziału. Wymagają one jedynie podstawowych operacji arytmetycznych.
You can use a trick very similar to what you mention. Let's say thatX∼N(μ,σ2) is a normal random variable with known parameters. Then we know its distribution function, Φμ,σ2 , and Φμ,σ2(X) will be uniformly distributed on (0,1) . To prove this, note that for d∈(0,1) we see that
The above probability is clearly zero for non-positived and 1 for d≥1 . This is enough to show that Φμ,σ2(X) has a uniform distribution on (0,1) as we have shown that the corresponding measures are equal for a generator of the Borel σ -algebra on R . Thus, you can just tranform the normally distributed data by the distribution function and you'll get uniformly distributed data.
źródło