Jak symulować kość przy danej uczciwej monecie

Załóżmy, że otrzymałeś uczciwą monetę i chciałbyś zasymulować rozkład prawdopodobieństwa wielokrotnego rzutu rzetelną (sześciostronną) kością. Mój początkowy pomysł jest taki, że musimy wybrać odpowiednie liczby całkowite , takie, że . Więc po odwróceniu razy monety , mapujemy liczbę zakodowaną przez ciąg bitów o długości k na wyjścia matrycy, dzieląc zakres [0,2 ^ k-1] na 6 przedziałów o długości m . Nie jest to jednak możliwe, ponieważ 2 ^ k ma dwa jako jedyny czynnik główny, ale czynniki pierwsze 6m obejmują trzy. Powinien istnieć inny prosty sposób, prawda?$k,m$$2^k = 6m$$k$$[0,2^k-1]$$m$$2^k$$6m$

Aby mieć nieco bardziej wydajną metodę niż ta wskazana przez @FrankW, ale używając tego samego pomysłu, możesz odwrócić monetę razy, aby uzyskać liczbę poniżej . Następnie zinterpretuj to jako partię rzutów, gdzie jest największą liczbą, tak że (jak już powiedziano, równość nigdy tu nie obowiązuje). Jeśli otrzymasz liczbę większą lub równą , musisz odrzucić tę wartość i powtórzyć wszystkie odwrotów.$n$$2^n$$m$$m$$6^m < 2^n$$6^m$$n$

Możesz zaimplementować funkcję, która zwraca pojedynczy rzut matrycą, wykonując $n$ rzutów monetą, a następnie buforuj wynik dla następujących żądań rzutu kostką $m-1$ .

Interesujące jest to, że niektóre wartości są lepsze niż inne, ponieważ mają mniejszy wskaźnik odrzucenia. Oto lista dobrych wartości (tj. Wartości, które mają niższy współczynnik odrzucenia niż poprzednie):$n$

n m r
3 1 0.25
8 3 0.15625
13 5 0.05078125
44 17 0.0378308072686
75 29 0.0247036782182
106 41 0.0113974522704
243 94 0.00933096248381
380 147 0.00726015308463
517 200 0.00518501504347
654 253 0.00310553931213
791 306 0.00102171682348

uzyskane za pomocą wzorów: .

Pierwszy wiersz odpowiada odpowiedzi @FrankW ze współczynnikiem odrzucenia wynoszącym 25%. Ładne są następujące liczby: zarówno i mogą być przechowywane w jednej zmiennej statycznej typu całkowitego. W szczególności wskaźnik odrzucenia wynoszący wynosi tylko 5%, co stanowi rozsądną poprawę w stosunku do 25% i czyni go dobrym kandydatem do ewentualnego wdrożenia.$n=8$$n=13$$n=13$

Co możesz zrobić, to zastosować metodę o nazwie próbkowanie odrzucenia :

• Odrzuć monetę 3 razy i zinterpretuj każdy rzut jako odrobinę (0 lub 1).
• Połącz 3 bity, podając liczbę binarną w .$[0,7]$
• Jeśli liczba jest w , weź ją jako rzut kości.$[1,6]$
• W przeciwnym razie, tj. Jeśli wynik wynosi lub 7 , powtórz odwrócenie.$0$$7$

Od możliwych wyników prowadzi do zakończenia w każdym zestawie, prawdopodobieństwo, że potrzeba więcej niż1zestawu rzutów, aby otrzymać rzut kostką, wynosi(1-$\frac 68$$l$ . Dlatego ta metoda jest skuteczna w praktyce.$(1-\frac 68)^l = \dfrac 1{4^l}$

Ulepszenia:

@ Odpowiedź Angel wskazuje, że liczba monet przewraca się w każdym zestawie, ale pierwszy można zmniejszyć z 3 do 2, stosując rozróżnienie między a 7 jako pierwszy bit dla następnego zestawu.$0$$7$

@Emanuele Paolini wyjaśnia, w jaki sposób możesz zmniejszyć liczbę powtórzeń, jeśli potrzebujesz wielu rzutów kostką.

Alternatywą dla próbkowania odrzucającego (jak opisano w odpowiedzi FrankW ) jest zastosowanie algorytmu skalowania, który bierze pod uwagę odpowiedź [7,8] tak, jakby to była kolejna rzut monetą.

Istnieje bardzo szczegółowe wyjaśnienie na stronie mathforum.org , w tym algorytm ( NextBit()byłoby to odwracanie twojej uczciwej monety).

Przypadek rzucenia kostką za pomocą uczciwej monety (próbkowanie 2 → 6) jest łatwiejszy niż ogólny algorytm. Po prostu bierzesz awarię (7 lub 8) jako kolejne wejście monety i wykonujesz jeszcze dwa rzuty.

Innym podejściem do symulacji rzutu dN przy użyciu dM (w przypadku konkretnego pytania zadanego d6 przy użyciu d2) jest podzielenie przedziału [0, 1) na N równych przedziałów o długości 1 / N, [0, 1 / N), [1 / N, 2 / N), ..., [(N-1) / N, N).

Użyj dM, aby wygenerować frakcję bazową M, 0.bbbb ... w [0, 1). Jeśli to mieści się w [(i-1) / N, i / N), weź i jako rzut dN. Zauważ, że wystarczy wygenerować wystarczającą liczbę cyfr M frakcji, aby określić, w jakim interwale się ona znajduje.

Prawdopodobnie prostsze wyjaśnienie ulepszonego próbkowania przy odrzucaniu.

Podaję to wyjaśnienie, ponieważ, mam nadzieję, może pomóc w uproszczeniu zrozumienia lub analizy prawdopodobieństwa w niektórych sytuacjach.

FrankW sugeruje zastosowanie próbkowania odrzucenia, trzykrotnego przewrócenia monety, utrzymania wyniku, jeśli jest w odpowiednim zakresie, lub powtórzenia trzech przewrotów w przeciwnym razie, aż do sukcesu.

Ángel sugeruje, aby zapisać jeden rzut na każdej próbie, zastępując go wyborem binarnym pozostałym z dwóch niewykorzystanych wartości z poprzedniego zestawu trzech.

Oznacza to naprawdę, że z trzema pierwszymi przerzutami wygenerowano jeden kawałek informacji, który nie musiał być wygenerowany. Dokładniej, powinieneś rzucić monetą tylko dwa razy, aby wiedzieć, czy aktualny zestaw rzutów zakończy się sukcesem.

Wiedza, czy bieżący zestaw klapek odniesie sukces, jest jedynym prawdopodobieństwem, które ma znaczenie , ponieważ interpretacja zestawu klapek jest niezależna od prawdopodobieństwa. Można to wiedzieć przed zakończeniem wszystkich rzutów dla tego zestawu.

Można to osiągnąć na co najmniej dwa sposoby, a dokładniej w dwóch różnych interpretacjach odwrotności. Mogą być inni.

Grupowanie wyników w pary

Chodzi o rozważenie tylko trzech wartości (1,2), (3,4) i (5,6) reprezentowanych przez dowolne trzy konfiguracje podwójnego przerzucenia, np. TT, TH, HT. Następnie można zastosować próbkowanie odrzucania z podwójnym odwróceniem, powtarzając za każdym razem, gdy pojawi się konfiguracja awarii HH.

Gdy zdobędziesz jedną z trzech udanych konfiguracji, po prostu jeszcze raz rzuć monetą, aby zdecydować, czy powinieneś wziąć pierwszą, czy drugą wartość odpowiedniej pary.

Wczesne wykrycie awarii zestawu typu flip-set

Chodzi o to, aby użyć nieco innego odczytu konfiguracji z trzema przerzuceniami. Jeśli Głowa i Ogon są interpretowane jako 1 i 0, konfiguracja powinna odpowiadać interpretacji binarnej plus jeden. To znaczy TTT (tj. 000) odpowiada 1, HTH (tj. 101) odpowiada 6, HHT (tj. 110), a HHH (tj. 111) odpowiada 7 i 8, lub cokolwiek poza [1,6].

Następnie wiemy, że zestaw klapek kończy się powodzeniem lub klęską tylko z dwoma pierwszymi klapkami. Jeśli produkują HH, zestaw klap kończy się niepowodzeniem niezależnie od ostatniego klapki. Więc można go pominąć.

Myślę, że wczesne wykrycie zawsze może być wykorzystane jako wyjaśnienie, ale w zależności od liczby twarzy na symulowanych kościach wykrywanie awarii może nastąpić po zmiennej liczbie rzutów.

Na przykład dla kości o 10 twarzach potrzebujesz zasadniczo zestawu 4 rzutów, z 6 konfiguracjami odpowiadającymi awarii. Sztuczka polega na tym, aby mieć wszystkie konfiguracje błędów na górnym końcu sekwencji wartości binarnych w następujący sposób:

TTTT  0000   1
HTTT  1000   9
HTTH  1001  10
HTHT  1001  11
HTHH  1011  12
HHTT  1100  13
HHHH  1111  16

Pomyślne konfiguracje odpowiadają zakresowi [1, 10], a niepowodzenia w zakresie [11,16].

Potem się nie udaje, gdy pierwsze dwa rzuty dają HH, lub gdy pierwsze trzy dają HTH, nawet bez próby wykonania brakujących rzutów zestawu.

Jeśli nie zawiedziesz, po prostu zakończ zestaw klapek.

Istnieją dwa dobrze znane podejścia do tego. Jednym z nich jest „próbkowanie odrzucenia”. Na przykład użyj trzech bitów, aby wybrać jedną z sześciu wartości, próbując ponownie dla dwóch dodatkowych próbek. Lub użyj 14 bitów (wartości 8192), aby wybrać 5 wartości od 1 do 6 (7776 możliwości), próbując ponownie w 13 z 256 przypadków.

Drugi wykorzystuje część dekompresyjną algorytmu kompresji / dekompresji: W przypadku kodowania arytmetycznego sekwencję losowych wartości od 1 do 6 można skompresować bez prawie żadnej nadmiarowości. Wygeneruj losowo skompresowaną sekwencję i rozpakuj ją. Jest to o wiele bardziej skomplikowane, ale praktycznie nie wymaga żadnych dodatkowych liczb losowych.

Przepraszamy z góry, jeśli wyjaśnienie jest zbyteczne. Nie byłam pewna, jak wiele szczegółów należy się dowiedzieć, ani jak łatwo było to zrozumieć.

Powiedz, że masz trzy monety (monety uczciwe). Jeśli stopniowo przypisujesz wartość do każdej strony każdej monety, otrzymasz sześć wartości.

W ten sposób: na pierwszej monecie główki wynoszą 1, a reszka 2. Na drugiej monecie główki mają 3, a reszka 4.

Odrzucenie monet pozostawi ci zestaw trzech liczb, twojego obecnego zestawu. Teraz twój bieżący zestaw stanie się poprzednim zestawem i powtórzysz proces, aby uzyskać nowy zestaw trzech liczb.

Kontynuuj tę czynność, aż jedna i tylko jedna liczba będzie pasować z bieżącego do poprzedniego zestawu. To twój numer.

Więc jeśli masz [głowy, ogony, głowy] dla bieżącego zestawu, byłoby to [1, 4, 5]. Teraz przerzucisz je ponownie, a twój obecny zestaw to [2, 4, 5]. Dwa mecze. Nie dobrze. Spróbuj ponownie. Dostajesz [2, 3, 6]. Tylko jeden mecz. Twój numer to dwa.

Będzie taka sama szansa na pojawienie się dowolnej liczby, ale nie jest to szczególnie opłacalne, biorąc pod uwagę, że istnieje tylko zmiana 3/32, że dana para zestawów odniesie sukces (tylko jeden mecz). Średnio algorytm musiałby powtórzyć około dziesięć razy. Ponadto, nie jest łatwo uogólniać na kości nieparzyste.

Przynajmniej może to jedzenie do namysłu. Bardzo interesujące pytanie.

Rzuciłem monetą trzy razy i zinterpretowałem wynik jako liczbę binarną, odrzucając wyniki poza zakresem.

Na przykład, niech głowy będą równe 1, a ogony będą wynosić 0. Jeśli przerzucisz go trzy razy i dostaniesz głowy, ogony, głowy, będziesz miał wartość binarną 101, czyli 5 w systemie dziesiętnym. HHT = 110b = 6. TTT = 000b = 0 i HHH = 111b = 7, z których oba są poza zakresem i zostaną odrzucone, a Ty powrócisz do wszystkich cyfr.

Niestety nie można (wiernie) symulować (uczciwej) kości przy użyciu (sekwencji) uczciwych monet.

Po prostu dlatego, że przestrzeń zdarzeń kości ma wymiar $6$ i nie można tego dokładnie dopasować siłą $2$ (co zapewnia przestrzeń na wydarzenie uczciwej monety).

Ale można to zrobić za pomocą uczciwej „monety trzyosobowej” (jeśli można użyć takiego terminu). Co oznacza monetę z 3 wynikami. I prosta 2-monetowa, więc łączna przestrzeń tych 2 monet odpowiada dokładnie przestrzeni zdarzenia kości.

Próbkowanie przy odrzuceniu (jak wspomniano w niektórych odpowiedziach) może rzeczywiście zapewnić przybliżoną symulację. Ale nadal będzie występować błąd lub niedopasowanie prawdopodobieństwa (w skończonym czasie). Jeśli więc ktoś chce dopasować przestrzeń zdarzeń tych 2 systemów, będą przypadki, że to nie zadziała.

W symulacji probabilistycznej (której przykładem jest próbka odrzucenia) wygenerowane typowe sekwencje rzeczywiście wykazują względne prawdopodobieństwa elementarne (w tym przypadku przestrzeń zdarzeń matrycy). Jednak (jak wspomniano w komentarzach) każda z tych typowych sekwencji może zawierać dowolnie długie podsekwencje o dokładnie takich samych wynikach. Oznacza to, że w celu zastosowania próbkowania odrzucającego (w niektórych przypadkach) może to zająć dowolnie długo lub wygenerowany rozkład będzie tendencyjny (tj. Niesprawiedliwy die) z powodu nadreprezentacji lub niedostatecznej reprezentacji niektórych części jego przestrzeni zdarzeń . gdyby tak nie było, to byłby możliwy algorytm deterministyczny, który dokładnie pasowałby do przestrzeni zdarzeń matrycy i monety (które nie pasują do wymiarów).