Algorytm losowania z prawdopodobieństwem

Question

Ma ktoś może w zasięgu wiedzy algorym losujący liczbę z tablicy z określonym prawdopodobieństwem?

tzn mam tablicę integerów z wartościami od 0 do 1000 im większa liczba tym większe prawdopodobieństwo że na nią padnie.

Answer 1

Zrozumiałem to tak, że liczba 1 jest losowana z prawdopodobieństwem 1/1000, liczba 2 z prawdopodobieństwem 2/1000, potem mamy 3/1000, 4/1000 itd. ale to chyba nie o to chodzi.

Answer 2

Metoda nazywa się chyba metodą eliminacji (tak mi się wydaje, ale to chyba mało istotne). Losujesz najpierw jedną liczbę z przedziału od x1 do Xn (w twoim przypadku od 0 do 1000). Losujesz drugą, z przedziału od 0 do prawdopodobieństwa wylosowania najbardziej prawdopodobnej liczby (wydaje mi się, że brzmi skomplikowanie, ale w twoim przypadku będziesz losował tę drugą liczbę, z przedziału od 0 do prawdopodobieństwa wylosowania 1000), patrząc na wykres, prawa ograniczenie przedziału to będzie P(x4). Ważnym jest też, że suma wszystkich prawdopodobieństw musi być być równa 1. 

Ponieważ zaczynasz liczyć od 0, prawdopodobieństwa wylosowania poszczególnych liczb wyznaczasz dzieląc (indeks liczby +1) przez sumę wszystkich liczb. Czyli u ciebie prawdopodobieństwo wylosowania jedynki to 2/(suma od 1 do 1001), prawdopodobieństwo wylosowania 100 to 101/(suma od 1 do 1001), prawdopodobieństwo 0 to 1/(suma od 1 do 1001). 

Najwygodniej będzie ci trzymać prawdopodobieństwa poszczególnych liczb w tablicy - pod indeksem 0 będziesz miał prawdopodobieństwo wylosowania 0, pod id 5, P(5) itd. Pierwsza wylosowana liczba określi, który element wybierasz. druga wylosowana liczba to jakieś prawdopodobieństwo. Sprawdzasz czy druga liczba, którą wylosowałeś, jest mniejsza lub równa od liczby która znajduje się w tablicy. Jeżeli jest mniejsza lub równa, zwracasz tę liczbę. Jeżeli nie, od nowa losujesz i pierwszą i drugą liczbę.

Może w postaci jakiegoś kodu 

tablica_prawdopodobieństw - tablica z prawdopodobieństwami poszczególnych liczb. 
id - liczba określająca id w tablica_prawdopodobieństw 
prawd - określa, czy zwracamy wylosowaną liczbę, czy nie.
sum = suma od 0 do 1000

do:
          id = rand(0,1000)
          prawd = rand(0, sum)
while ( tablica_prawdopodobieństw[id] < prawd ) 

 

Jakby któraś część była niezrozumiała, pisz, postaram się rozwiać wątpliwości. 

 

Tak mnie naszło, że istnieje też taki łopatologicznie prosty sposób, żeby uzyskać niemal identyczny efekt, jak opisałem: 
Przygotowujesz sobie bardzo dużą tablicę i na jej kolejne komórki wpisujesz:
0 - jeden raz
1 - dwa razy
3 - trzy razy
itd. 
Potem losujesz sobie jakąś liczbę z tablicy.