Struktura danych dla załadowanych kości?

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!

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 .

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.

function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        // start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)

Zaletą tego rozwiązania jest to, że jest ono bardzo proste do wdrożenia, ale nadal ma dużą złożoność.

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)

arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3

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.

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ść fto max. 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:

1. Wybierz jednolitą losową liczbę całkowitą iw [1, k].
2. Z prawdopodobieństwem f(i)/maxwróć 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:

• zwięzłą strukturę danych Bringmanna-Larsena („Succinct Sampling from Discrete Distributions”, 2012),
• Wielopoziomowe wyszukiwanie Yunpeng Tanga („An Empirical Study of Random Sampling Methods for Changing Discrete Distributions”, 2019) oraz
• Szybka Loaded Dice Roller (2020).

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 ”.