Jak generować liczby na podstawie arbitralnej dystrybucji dyskretnej?

Jak generować liczby na podstawie dowolnego dyskretnego rozkładu?

Na przykład mam zestaw liczb, które chcę wygenerować. Powiedzmy, że są oznaczone od 1-3 w następujący sposób.

1: 4%, 2: 50%, 3: 46%

Zasadniczo odsetki to prawdopodobieństwa, że ​​pojawią się na wyjściu generatora liczb losowych. Mam generator liczb pesudorandom, który wygeneruje jednolity rozkład w przedziale [0, 1]. Czy jest na to jakiś sposób?

Nie ma ograniczeń co do liczby elementów, które mogę mieć, ale% doda do 100%.

Jednym z najlepszych algorytmów próbkowania z rozkładu dyskretnego jest metoda aliasowa .

Metoda aliasowa (efektywnie) oblicza dwuwymiarową strukturę danych w celu podziału prostokąta na obszary proporcjonalne do prawdopodobieństw.

W tym schemacie z wymienionej stronie, prostokąt wysokość urządzenia został podzielony na cztery rodzaje regionów - w odróżnieniu od koloru - w proporcji , 1 / 3 , 1 / 12 i 1 / 12 , w aby próbkować wielokrotnie z rozkładu dyskretnego z tymi prawdopodobieństwami. Pionowe paski mają stałą szerokość (jednostkę). Każda z nich jest podzielona na jedną lub dwie części. Tożsamości elementów i lokalizacje pionowych podziałów są przechowywane w tabelach dostępnych za pośrednictwem indeksu kolumny.$1/2$$1/3$$1/12$$1/12$

Tabela może być próbkowana w dwóch prostych krokach (po jednym dla każdej współrzędnej), wymagających wygenerowania tylko dwóch niezależnych jednolitych wartości i obliczenia . Poprawia to obliczenia O ( log ( n ) ) potrzebne do odwrócenia dyskretnego CDF, jak opisano w innych odpowiedziach tutaj.$O(1)$$O(\log(n))$

Możesz to łatwo zrobić w R, po prostu określ potrzebny rozmiar:

sample(x=c(1,2,3), size=1000, replace=TRUE, prob=c(.04,.50,.46))

W swoim przykładzie powiedz, że narysowałeś swoją pseudolosową wartość Uniform [0,1] i nazwałeś ją U. Następnie wypisz:

1, jeśli U <0,04

2, jeśli U> = 0,04 i U <0,54

3, jeśli U> = 0,54

Jeśli określone% to a, b, ..., po prostu wyjdź

wartość 1, jeśli U

wartość 2, jeśli U> = a i U <(a + b)

itp.

Zasadniczo odwzorowujemy% na podzbiory [0,1] i wiemy, że prawdopodobieństwo, że jednolita losowa wartość przypada na dowolny zakres, jest po prostu długością tego zakresu. Uporządkowanie zakresów wydaje się najprostszym, jeśli nie niepowtarzalnym, sposobem na zrobienie tego. Zakłada się, że pytasz tylko o dystrybucje dyskretne; dla ciągłego, może zrobić coś takiego jak „próbkowanie odrzucenia” ( wpis na Wikipedii ).

Załóżmy, że istnieją możliwe nieciągłe wyniki. Dzielenie [ 0 , 1 ] dzieli się na podinterwały na podstawie skumulowanej funkcji masy prawdopodobieństwa F , aby dać przedział podzielony na partycje ( 0 , 1 $m$$[0,1]$$F$$(0,1)$

gdzie i F ( 0 ) ≡ 0 . W twoim przykładzie m = 3 i$I_{j} = (F(j-1), F(j))$$F(0) \equiv 0$$m = 3$

ponieważ i F ( 2 ) = .54 i F ( 3 ) = 1 .$F(1) = .04$$F(2) = .54$$F(3) = 1$

Następnie możesz wygenerować z rozkładem F przy użyciu następującego algorytmu:$X$$F$

(1) tworzą $U \sim {\rm Uniform}(0,1)$

(2) Jeśli , to X = j .$U \in I_{j}$$X = j$

• Ten krok można wykonać, sprawdzając, czy jest mniejsze niż każde z kumulatywnych prawdopodobieństw, i sprawdzając, gdzie występuje punkt zmiany (od do ), co powinno być kwestią użycia operatora logicznego w dowolnym języku programowania i znalezienie miejsca pierwszego w wektorze.$U$TRUEFALSEFALSE

Zauważ, że będzie dokładnie w jednym z przedziałów I j ponieważ są rozłączne i partycji [ 0 , 1 ] .$U$$I_{j}$$[0,1]$

Jednym prostym algorytmem jest rozpoczęcie od jednolitej liczby losowej, a następnie w pętli odjęcie pierwszego prawdopodobieństwa, jeśli wynik jest ujemny, wówczas zwracana jest pierwsza wartość, jeśli nadal dodatnia, to przechodzi się do następnej iteracji i odejmuje następne prawdopodobieństwo , sprawdź, czy negatywne itp.

Jest to miłe, ponieważ liczba wartości / prawdopodobieństw może być nieskończona, ale prawdopodobieństwa należy obliczać tylko, gdy zbliżysz się do tych liczb (na przykład generowanie z rozkładu Poissona lub ujemnego rozkładu dwumianowego).

Jeśli masz skończony zestaw prawdopodobieństw, ale generujesz z nich wiele liczb, wtedy bardziej efektywne może być sortowanie prawdopodobieństw, aby odjąć największą, a następnie drugą największą i tak dalej.

Po pierwsze, pozwólcie, że zwrócę uwagę na bibliotekę Pythona z gotowymi klasami do generowania liczb losowych całkowitych lub zmiennoprzecinkowych, które następują po dowolnej dystrybucji.

Ogólnie rzecz biorąc, istnieje kilka podejść do tego problemu. Niektóre są liniowe w czasie, ale wymagają dużej pamięci, inne działają w czasie O (n log (n)). Niektóre są zoptymalizowane pod kątem liczb całkowitych, a niektóre są zdefiniowane dla okrągłych histogramów (na przykład: generowanie losowych miejsc w czasie w ciągu dnia). W wyżej wymienionej bibliotece użyłem tego artykułu dla liczb całkowitych i tego przepisu na liczby zmiennoprzecinkowe. Nie ma (nadal) obsługi okrągłego histogramu i ogólnie jest niechlujny, ale działa dobrze.

I had the same problem. Given a set where each item has a probability and whose items' probabilities sum up to one, I wanted to draw a sample efficiently, i.e. without sorting anything and without repeatedly iterating over the set.

The following function draws the lowest of $N$ uniformly distributed random numbers within the interval $[a,1)$. Let $r$ be a random number from $[0,1)$.

You can use this function to draw an ascending series $(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_0 = \text{next}(10, 0)$
$a_1 = \text{next}(9, a_0)$
$a_2 = \text{next}(8, a_1)$
$\dots$
$a_9 = \text{next}(1, a_8)$

While drawing that ascending series $(a_i)$ of uniformly distributed numbers, iterate over the set of probabilities $P$ which represents your arbitraty (yet finite) distribution. Let $0 \leq k < |P|$ be the iterator and $p_k \in P$. After drawing $a_i$, increment $k$ zero or more times until $\sum p_0 \dots p_k > a_i$. Then add $p_k$ to your sample and move on with drawing $a_{i+1}$.

Example with the op's set $\{(1, 0.04), (2, 0.5), (3, 0.46)\}$ and sample size $N = 10$:

i  a_i    k  Sum   Draw
0  0.031  0  0.04  1
1  0.200  1  0.54  2
2  0.236  1  0.54  2
3  0.402  1  0.54  2
4  0.488  1  0.54  2
5  0.589  2  1.0   3
6  0.625  2  1.0   3
7  0.638  2  1.0   3
8  0.738  2  1.0   3
9  0.942  2  1.0   3

Sample: $(1, 2, 2, 2, 2, 3, 3, 3, 3, 3)$

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.