Czy ktoś może mi powiedzieć, jak symulować , gdzie , za pomocą rzutu monetą (tyle razy, ile potrzebujesz) z ?
Myślałem o użyciu próbkowania odrzucenia, ale nie mogłem tego dopracować.
Czy ktoś może mi powiedzieć, jak symulować , gdzie , za pomocą rzutu monetą (tyle razy, ile potrzebujesz) z ?
Myślałem o użyciu próbkowania odrzucenia, ale nie mogłem tego dopracować.
[self-study]
tag i przeczytaj jego wiki . Pamiętaj, że na końcu pytania nie musisz prosić o pomoc - wiemy, że każdy, kto tu zamieszcza, ma nadzieję na pomoc!Odpowiedzi:
Ponieważ istnieje niezliczona ilość rozwiązań, znajdźmy skuteczne .
Idea tego zaczyna się od standardowego sposobu implementacji zmiennej Bernoulliego: porównaj jednolitą zmienną losowąU do parametru a/b . KiedyU<a/b , powrót 1 ; w przeciwnym razie wróć0 .
Możemy użyćp -coin jako jednolity generator liczb losowych . Aby wygenerować liczbęU równomiernie w dowolnym przedziale czasowym [ x , y) , rzuć monetą. Kiedy jest to głowa, rekurencyjnie generuj jednolitą wartośćX na początku p część przedziału; gdy są to ogony, generuj rekurencyjnieX od ostatniego 1 - p część przedziału. W pewnym momencie przedział docelowy stanie się tak mały, że tak naprawdę nie ma znaczenia, jak wybierzesz z niego liczbę: tak zaczyna się rekurencja. Oczywiste jest, że ta procedura generuje jednolite zmienne (do dowolnej pożądanej precyzji), co łatwo udowodnić indukcyjnie.
Ten pomysł nie jest skuteczny, ale prowadzi do wydajnej metody. Ponieważ na każdym etapie będziesz losować liczbę z określonego przedziału[ x , y) , dlaczego najpierw nie sprawdzić, czy trzeba go narysować? Jeśli wartość docelowa leży poza tym przedziałem, znasz już wynik porównania między wartością losową a wartością docelową. Dlatego algorytm ten szybko się kończy. (Można to interpretować jako procedurę próbkowania odrzucenia wymaganą w pytaniu.)
Możemy dalej optymalizować ten algorytm. Na każdym etapie faktycznie mamy dwie monety, których możemy użyć: poprzez zmianę etykiety naszej monety możemy przekształcić ją w monetę, która jest szansą1 - p . Dlatego jako wstępne obliczenie możemy rekurencyjnie wybrać, które ponowne etykietowanie prowadzi do niższej oczekiwanej liczby przerzutów potrzebnych do zakończenia. (To obliczenie może być kosztownym krokiem.)
Na przykład nieefektywne jest używanie monetyp = 0,9 naśladować Bernoulliego( 0,01 ) zmienna bezpośrednio: średnio zajmuje prawie dziesięć rzutów. Ale jeśli użyjemyp = 1 - 0,0 = 0,1 monetą, to już po dwóch rzutach na pewno się zakończymy, a oczekiwana liczba rzutów jest po prostu 1.2 .
Oto szczegóły.
Podziel dowolny podany półotwarty przedziałja= [ x , y) w odstępach
To definiuje dwie transformacjes(∗,H) i s(∗,T) które działają w okresach półotwartych.
Jeśli chodzi o terminologię, jeśliI to dowolny zestaw liczb rzeczywistych, niech wyrażenie
znaczy żet jest dolną granicą dla I : t<x dla wszystkich x∈I . Podobnie,t>I znaczy t jest górną granicą dla ja .
pisaća / b = t . (W rzeczywistości nie ma znaczenia, czyt jest rzeczywisty zamiast racjonalnego; wymagamy tylko tego0 ≤ t ≤ 1 .)
Oto algorytm tworzenia wariacjiZ z żądanym parametrem Bernoulli:
Zestawn = 0 i jan=ja0= [ 0 , 1 ) .
Podczas( t ∈jan) {Rzuć monetą, aby wyprodukować Xn + 1 . Zestawjan + 1= S(jan,Xn + 1) . Przyrost n .}
Gdybyt >jan + 1 następnie ustaw Z= 1 . W przeciwnym razie ustawZ= 0 .
Realizacja
Aby to zilustrować, otot i interwał [ x , y) , początkowo [ 0 , 1 ) . Wykorzystuje s . Chociaż nie musi, śledzi także liczbę rzutów monetą. Zwraca losową zmienną, liczbę rzutów i ostatni sprawdzony interwał.
R
implementacja alorithm jako funkcjidraw
. Jego argumenty są wartością docelowąs
implementację funkcji pomocniczejJako przykład jego zastosowania i sprawdzenia jego dokładności weźmy przykładt = 1 / 100 i p = 0,9 . Porysujmy10 , 000 wartości przy użyciu algorytmu, zgłaszają średnią (i jej błąd standardowy) oraz wskazują średnią liczbę zastosowanych przerzutów.
W tej symulacji0,0095 klapki były główkami. Chociaż niższy niż cel0,01 , wynik Z na poziomie - 0,5154 nie jest znaczący: to odchylenie można przypisać przypadkowi. Średnia liczba przerzutów wyniosła9,886 - trochę mniej niż dziesięć. Gdybyśmy skorzystali z1 - p monety, średnia byłaby 0,0094 - nadal nie różni się znacząco od celu, ale tylko 1.177 przerzuty byłyby potrzebne średnio.
źródło
Oto rozwiązanie (trochę niechlujne, ale to moje pierwsze dźgnięcie). Możesz faktycznie zignorowaćP.( H) = p i WLOG zakłada P.( H) = 1 / 2 . Dlaczego? Istnieje sprytny algorytm do generowania obiektywnego rzutu monetą z dwóch stronniczych rzutów monetą. Możemy więc założyćP.( H) = 1 / 2 .
Aby wygenerowaćBernoulli (zab) , Mogę wymyślić dwa rozwiązania (pierwsze nie jest moje, ale drugie jest uogólnieniem):
Rozwiązanie 1
Odwróć obiektywną monetęb czasy. Gdybyza głowy nie są obecne, zacznij od nowa. Gdybyza głowice są obecne, zwróć, czy pierwsza moneta jest głowicą, czy nie (ponieważP.( pierwsza moneta to głowy | a główki w monetach b ) =zab )
Rozwiązanie 2
Można to rozszerzyć na dowolną wartośćBernoulli ( p ) . pisaćp w formie binarnej. Na przykład,0,1 = 0,0001100110011001100110011 ... podstawa 2
Stworzymy nowy numer binarny za pomocą rzutów monetą. Zacząć od0. i dodawaj cyfry w zależności od tego, czy pojawią się głowice (1) czy ogony (0). Przy każdym odwróceniu porównaj swój nowy numer binarny z reprezentacją binarnąp do tej samej cyfry . W końcu obie się rozejdą i wrócą, jeślib i n ( p ) jest większy niż liczba binarna.
W Pythonie:
Niektóre dowody:
wynosi około 0,4 (jednak nie szybko)
źródło
Widzę proste rozwiązanie, ale bez wątpienia istnieje wiele sposobów na zrobienie tego, niektóre prawdopodobnie łatwiejsze niż to. To podejście można podzielić na dwa etapy:
Generowanie z dwóch zdarzeń z jednakowym prawdopodobieństwem przy nieuczciwej procedurze losowania monet (połączenie konkretnej monety i metody jej rzucania generuje głowę z prawdopodobieństwemp ). Możemy nazwać te dwa równie prawdopodobne zdarzeniaH.∗ , i T.∗ . [Jest na to proste podejście, które wymaga pary rzutówH∗=(H,T) i T∗=(T,H) aby uzyskać dwa równie prawdopodobne wyniki, przy czym wszystkie inne wyniki prowadzą do wygenerowania nowej pary rzutów, aby spróbować ponownie.]
Teraz generujesz losowy spacer z dwoma stanami pochłaniania za pomocą symulowanej uczciwej monety. Wybierając odległość stanów pochłaniania od źródła (jeden powyżej i jeden poniżej niego), możesz ustawić szansę absorpcji, mówiąc, że górny stan pochłaniania jest pożądanym stosunkiem liczb całkowitych. W szczególności, jeśli umieścisz górną barierę pochłaniającą wa i niższy o −(b−a) (i rozpocznij proces od początku) i uruchom losowy spacer aż do absorpcji, prawdopodobieństwo absorpcji przy górnej barierze wynosi aa+(b−a)=ab .
(Aby to pokazać, należy wykonać pewne obliczenia, ale można dość łatwo wyliczyć prawdopodobieństwa, pracując z relacjami powtarzalności ... lub możesz to zrobić, sumując nieskończone szeregi ... lub istnieją inne sposoby.)
źródło