Jak symulować kość przy danej uczciwej monecie


21

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,m2k=6mk[0,2k1]m2k6m


Zobacz to pytanie, w którym problem jest rozwiązany w bardziej ogólny sposób.
Raphael

Oto artykuł na ten temat . Wyjaśnia, jak używać próbkowania odrzucania i jak ponownie wykorzystać „zmarnowane” bity, aby przyspieszyć dalsze rzuty.
ZeroUltimax

Odpowiedzi:


12

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.n2nmm6m<2n6mn

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ą m1 .

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

m=nlog32r=13m2n

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=8n=13n=13


Nie potrzebujesz 6 ^ m, wystarczy 6 * m. Możesz więc użyć 5 rzutów, aby uzyskać 5-bitową liczbę odrzucającą tylko 1/16 przypadków.
Taemyr

Odrzucenie 5% dla 13 rzutów jest okropne, w porównaniu do 25% dla 3 rzutów. Ponieważ 25% dla 3 rzutów odrzuci tylko 4 razy (tj. Wyda więcej niż 12 rzutów) w 0,390625% przypadków.
Taemyr

@Taemyr 5-bitowa liczba może reprezentować 32 różne wartości, co pozwala reprezentować jedną kostkę (ponieważ dwie kostki mają 36 możliwości). Tak więc dopuszczalne są tylko wartości 6/32 przy współczynniku odrzucania wynoszącym 27/32 = 84%
Emanuele Paolini

@Taemyr: współczynnik odrzucenia na n rzutów oznacza, że ​​średnio każda partia n rzutów jest odrzucana z prawdopodobieństwem r . Tak więc średnio każde podrzucenie jest odrzucane z tą samą szybkością r (nie zależnie od n ). rnnrrn
Emanuele Paolini,

Tak. Korzystając z metody FrankW, która ma współczynnik powtórki 25% dla partii 3 rzutów, istnieje prawdopodobieństwo 1-0.00390625 do przyjęcia nie później niż w czwartej partii.
Taemyr

29

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

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-668l . Dlatego ta metoda jest skuteczna w praktyce.(1-68)l=14l

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

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


Czy ta metoda nie dałaby większej tendencji centralnej niż prawdziwa d6?
Red_Shadow

3
@ Red_Shadow Nie. Pamiętaj, że nie dodajesz rzutów monetą (wtedy trzy nie wystarczyłyby), ale wybierasz każdy bit w bitowej liczbie binarnej za monetę. Zatem próbkujesz równomiernie z [ 0..2 k - 1 ] i odrzucasz liczby nie z przedziału docelowego; może to zapewnić tylko równomierny rozkład w docelowym przedziale. k[0..2k-1]
Raphael

Jeśli jesteś sprytny z odrzuconym zakresem, w tym przypadku naprawdę łatwo jest użyć go, aby zmniejszyć liczbę niezbędnych rzutów monetą w przypadku odrzucenia.
Mooing Duck

@MooingDuck możesz zdecydować, czy chcesz odrzucić swój wynik po 2 rzutach: jeśli jest to 0,0 0,1 lub 1,0, a następnie ponownie rzuć ostatnim bitem, w przeciwnym razie zacznij od nowa
maniak zapadkowy

1
@NikosM. Prawdopodobieństwo, że zajmie to więcej niż kroków, maleje wykładniczo w kierunku zera, więc odpowiedź nie zawiera żadnego błędnego twierdzenia: jest skuteczna w praktyce i faktycznie stosowana szeroko. (W przypadku bardziej skomplikowanych dystrybucji jest to często jedyna znana metoda. W ogóle.)k
Raphael

7

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.


2

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.


Warunek zakończenia musi być bardziej precyzyjny. Jeśli raz odwrócę monetę, skończę z ułamkiem binarnym 0,0 lub 0,1 (tj. ½), z których oba mieszczą się w przedziale (odpowiednio w tym przypadku odpowiednio 0 i 3). Wygenerowaną frakcję należy traktować jako zakres i zatrzymuje się, gdy cały zakres znajduje się w jednym przedziale. Jestem pewien, że to właśnie zamierzałeś, ale nie sądzę, żeby to było jasne.
rici

1

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.


1

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.


0

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.


4
lognn12)n2)n/2)n

0

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.


1
To tylko odpowiedź Franka.
Raphael

2
@Raphael Właściwie, ścisły podzbiór odpowiedzi Franka , ponieważ Frank odnosi się do oczekiwanego czasu działania.
David Richerby,

0

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


Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Gilles 'SO - przestań być zły'

@Gilles, pomimo złych wyjaśnień i rozmów (co do poprawności), które nadal trwały, nadal jest zbyt zły głos negatywny: p
Nikos M.
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.