Załóżmy, że mam n-stronną kostkę obciążoną, w której każda strona k ma pewne prawdopodobieństwo, że p k wypadnie, gdy ją rzucę. Ciekawe, czy istnieje dobry algorytm do przechowywania tych informacji w sposób statyczny (tj. Dla ustalonego zestawu prawdopodobieństw), aby móc skutecznie zasymulować losowy rzut kostką.
Obecnie mam rozwiązanie O (lg n) dla tego problemu. Chodzi o to, aby zapisać tabelę skumulowanego prawdopodobieństwa pierwszych k stron dla wszystkich k, wygenerować losową liczbę rzeczywistą z zakresu [0, 1) i przeprowadzić wyszukiwanie binarne w tabeli, aby uzyskać największy indeks, którego skumulowany wartość nie jest większa niż wybrana wartość. Raczej podoba mi się to rozwiązanie, ale wydaje mi się dziwne, że środowisko wykonawcze nie bierze pod uwagę prawdopodobieństw. W szczególności w ekstremalnych przypadkach, gdy jedna strona zawsze się podnosi lub wartości są równomiernie rozłożone, możliwe jest wygenerowanie wyniku rzutu w O (1) przy użyciu naiwnego podejścia, chociaż moje rozwiązanie nadal będzie wymagało logarytmicznie wielu kroków.
Czy ktoś ma jakieś sugestie, jak rozwiązać ten problem w sposób, który jest w jakiś sposób „adaptacyjny” w jego środowisku wykonawczym?
EDYCJA : Na podstawie odpowiedzi na to pytanie napisałem artykuł opisujący wiele podejść do tego problemu wraz z ich analizami. Wygląda na to, że implementacja metody aliasów przez Vose'a daje Θ (n) czas przetwarzania wstępnego i O (1) czas na rzut kostką, co jest naprawdę imponujące. Mamy nadzieję, że jest to przydatne uzupełnienie informacji zawartych w odpowiedziach!
źródło
Odpowiedzi:
Szukasz metody aliasu, która zapewnia metodę O (1) do generowania stałego dyskretnego rozkładu prawdopodobieństwa (zakładając, że masz dostęp do wpisów w tablicy o długości n w stałym czasie) z jednorazową konfiguracją O (n) . Możesz go znaleźć w rozdziale 3 (PDF) książki „Non-Uniform Random Variate Generation” Luca Devroye'a.
Chodzi o to, aby wziąć tablicę prawdopodobieństw p k i utworzyć trzy nowe tablice n-elementowe, q k , a k i b k . Każde q k jest prawdopodobieństwem od 0 do 1, a każde a k i b k jest liczbą całkowitą od 1 do n.
Generujemy liczby losowe od 1 do n, generując dwie liczby losowe r i s, między 0 a 1. Niech i = podłoga (r * N) +1. Jeśli q i <s, to zwróć a i else return b i . Praca w metodzie aliasów polega na ustaleniu, jak utworzyć q k , a k i b k .
źródło
n
i wybranej liczby liczb losowych do wygenerowania ze względu na stałe czynniki związane z implementacją algorytmów.Użyj zrównoważonego drzewa wyszukiwania binarnego (lub wyszukiwania binarnego w tablicy) i uzyskaj złożoność O (log n). Miej jeden węzeł dla każdego wyniku na kości, a kluczami będą interwał, który wyzwoli ten wynik.
Zaletą tego rozwiązania jest to, że jest ono bardzo proste do wdrożenia, ale nadal ma dużą złożoność.
źródło
Myślę o granulowaniu twojego stołu.
Zamiast mieć tabelę ze skumulowaną wartością dla każdej wartości kości, możesz utworzyć tablicę liczb całkowitych o długości xN, gdzie x jest idealnie dużą liczbą, aby zwiększyć dokładność prawdopodobieństwa.
Wypełnij tę tablicę, używając indeksu (znormalizowanego przez xN) jako wartości skumulowanej i w każdym „gnieździe” tablicy zapisz przyszły rzut kostką, jeśli ten indeks się pojawi.
Może mógłbym łatwiej wyjaśnić na przykładzie:
Za pomocą trzech kości: P (1) = 0,2, P (2) = 0,5, P (3) = 0,3
Utwórz tablicę, w tym przypadku wybiorę prostą długość, powiedzmy 10. (czyli x = 3,33333)
Następnie, aby uzyskać prawdopodobieństwo, po prostu losuj liczbę od 0 do 10 i po prostu uzyskaj dostęp do tego indeksu.
Ta metoda może stracić dokładność, ale zwiększyć x, a dokładność będzie wystarczająca.
źródło
Istnieje wiele sposobów generowania losowej liczby całkowitej z niestandardową dystrybucją (znaną również jako dystrybucja dyskretna ). Wybór zależy od wielu rzeczy, w tym liczby liczb całkowitych do wyboru, kształtu rozkładu oraz tego, czy rozkład będzie się zmieniał w czasie.
Jednym z najprostszych sposobów wyboru liczby całkowitej z niestandardową funkcją wagi
f(x)
jest metoda próbkowania odrzucenia . W poniższym założeniu przyjęto, że najwyższa możliwa wartośćf
tomax
. Złożoność czasowa próbkowania odrzucania jest średnio stała, ale zależy w dużym stopniu od kształtu rozkładu i ma najgorszy przypadek ciągłego działania. Aby wybrać liczbę całkowitą w [1,k
] za pomocą próbkowania odrzucenia:i
w [1,k
].f(i)/max
wróći
. W przeciwnym razie przejdź do kroku 1.Inne algorytmy mają średni czas próbkowania, który nie zależy tak bardzo od rozkładu (zwykle jest to stały lub logarytmiczny), ale często wymagają wstępnego obliczenia wag w kroku konfiguracji i przechowywania ich w strukturze danych. Niektóre z nich są również ekonomiczne pod względem średniej liczby losowych bitów. Wiele z tych algorytmów zostało wprowadzonych po 2011 roku i obejmują one:
Inne algorytmy obejmują metodę aliasów (wspomnianą już w Twoim artykule), algorytm Knutha – Yao, strukturę danych MVN i nie tylko. Ankietę można znaleźć w mojej sekcji „ Uwaga na temat algorytmów ważonego wyboru ”.
źródło