Mam problem z rozwiązaniem poniższych problemów.
Dobierasz karty ze standardowej talii 52 kart bez wymiany, dopóki nie otrzymasz asa. Dobierasz z tego, co pozostało, dopóki nie dostaniesz 2. Kontynuujesz z 3. Jakiej oczekiwanej liczby będziesz się spodziewać po wyczerpaniu całej talii?
To było naturalne pozwolić
Problem zasadniczo polega na ustaleniu prawdopodobieństwa, że będziesz na gdy skończy się talia, a mianowicie:
Rozumiem
ale nie mogłem dostać się dalej ...
2AAA2
Odpowiedzi:
zgodnie z pomysłem @ gunga, uważam, że oczekiwana wartość wyniesie 5,84? i z mojej interpretacji komentarzy zakładam, że „A” jest wartością prawie niemożliwą (chyba że wszystkie cztery ostatnie karty w talii to asy). Oto wyniki 100 000 iteracyjnych symulacji Monte Carlo
a oto kod R na wypadek, gdybyś chciał się nim bawić ..
źródło
A
niemożliwe? Rozważmy na przykład sekwencję 48 kart, po których następujeAAAA
.1/prod( 48:1 / 52:5 )
results
W przypadku symulacji ważne jest, aby być poprawnym, a także szybko. Oba te cele sugerują pisanie kodu ukierunkowanego na podstawowe możliwości środowiska programistycznego, a także kodu, który jest tak krótki i prosty, jak to możliwe, ponieważ prostota zapewnia klarowność, a klarowność sprzyja poprawności. Oto moja próba osiągnięcia obu w
R
:Zastosowanie tego w odtwarzalny sposób można wykonać za pomocą
replicate
funkcji po ustawieniu zarodka liczb losowych, jak wJest to powolne, ale wystarczająco szybkie, aby kilkakrotnie przeprowadzać dość długie (a zatem precyzyjne) symulacje bez czekania. Istnieje kilka sposobów pokazania wyniku. Zacznijmy od jego średniej:
Ten ostatni jest błędem standardowym: oczekujemy, że symulowana średnia mieści się w zakresie dwóch lub trzech SE rzeczywistej wartości. To stawia prawdziwe oczekiwania gdzieś pomiędzy a 5,8535.817 5.853 .
Możemy również chcieć zobaczyć tabelę częstotliwości (i ich standardowych błędów). Poniższy kod trochę uwydatnia tabelę:
Oto wynik:
Skąd możemy wiedzieć, że symulacja jest nawet poprawna? Jednym ze sposobów jest wyczerpujące przetestowanie go pod kątem mniejszych problemów. Z tego powodu ten kod został napisany w celu zaatakowania niewielkiego uogólnienia problemu, zastępując odrębnych kart i 4 kolorami . Jednak do testowania ważne jest, aby móc podać kod talii w ustalonej kolejności. Napiszmy nieco inny interfejs do tego samego algorytmu:13 4
n
k
(Można go używać
draw
zamiastsim
wszędzie, ale dodatkowa praca wykonana na początkudraw
powoduje, że jest on dwa razy wolniejszy niżsim
.)Możemy tego użyć, stosując go do każdego wyraźnego przetasowania danej talii. Ponieważ celem jest tutaj tylko kilka jednorazowych testów, wydajność w generowaniu tych losowań nie jest ważna. Oto szybki sposób na brutalną siłę:
Teraz
d
jest ramka danych, której wiersze zawierają wszystkie przetasowania. Zastosujdraw
do każdego wiersza i policz wyniki:Wyjście (które chwilowo wykorzystamy w formalnym teście) to
( mówiąc, wartość 420 jest łatwa do zrozumienia: nadal pracowalibyśmy nad kartą 2 tylko wtedy, gdyby wszystkie dwójki poprzedzały wszystkie asy. Szansa na to (z dwoma kolorami) wynosi 1 / ( 2 + 2)420 2 . Spośród2520różnych tasowania,2520/6=420mają tę właściwość).1/(2+22)=1/6 2520 2520/6=420
Możemy przetestować wyjście za pomocą testu chi-kwadrat. W tym celu stosuje się ja10,000 n=4 k=2
sim
razy na tym przypadku n = 4 różne karty w k = 2 garniturach:Ponieważ jest tak wysokie, nie znajdujemy znaczącej różnicy między tym , co mówi, a wartościami obliczonymi przez wyczerpujące wyliczenie. Powtórzenie tego ćwiczenia dla niektórych innych (małych) wartości n i k daje porównywalne wyniki, dając nam wystarczający powód do zaufania, gdy zastosujemy je do n = 13 i k = 4 .p n k n=13 k=4
sim
sim
Na koniec test chi-kwadrat z dwiema próbkami porównuje wynik z
sim
wynikiem podanym w innej odpowiedzi:Ogromna statystyka chi-kwadrat daje wartość p, która jest zasadniczo zerowa: bez wątpienia
sim
nie zgadza się z drugą odpowiedzią. Istnieją dwa możliwe rozwiązania sporu: jedna (lub obie!) Z tych odpowiedzi jest niepoprawna lub wprowadzają różne interpretacje pytania. Na przykład, mam interpretować „po talia zabraknie” oznacza po Obserwując ostatnią kartę, a jeśli dopuszczalna, aktualizując „numer pojawi się na” przed zakończeniem procedury. Możliwe, że ten ostatni krok nie miał być wykonany. Być może jakaś subtelna różnica w interpretacji wyjaśni nieporozumienie, w którym momencie możemy zmodyfikować pytanie, aby wyjaśnić, o co jest pytany.źródło
Dokładna odpowiedź (w postaci iloczynu matrycowego, przedstawiona w punkcie 4 poniżej). Istnieje dość wydajny algorytm do jego obliczenia, wynikający z następujących obserwacji:
Losowe tasowanie kart można wygenerować przez losowe tasowanie N kart, a następnie losowe przeplatanie pozostałych w nich kart k .N+k N k
Tasując tylko asy, a następnie (stosując pierwszą obserwację) przeplatając dwójki, potem trójki itd., Problem ten można postrzegać jako łańcuch trzynastu kroków.
Musimy śledzić więcej niż wartość szukanej karty. Robiąc to, nie musimy jednak uwzględniać pozycji znaku względem wszystkich kart, a jedynie jego pozycję w stosunku do kart o takiej samej lub mniejszej wartości.
Wyobraź sobie, że umieszczasz znak na pierwszym asie, a następnie zaznaczasz pierwsze dwa znalezione po nim i tak dalej. (Jeśli na którymś etapie talia się skończy bez wyświetlania karty, której aktualnie szukamy, nie zaznaczymy wszystkich kart.) Niech „miejscem” każdego znaku (jeśli istnieje) jest liczba kart o takiej samej lub niższej wartości, zostały rozdane, gdy znak został wykonany (w tym sama karta oznaczona). Miejsca zawierają wszystkie niezbędne informacje.
Pozostała część tego postu zawiera szczegółowe informacje, przedstawia działającą implementację (in
R
) i kończy się komentarzami na temat pytania i wydajności rozwiązania.Generowanie losowych przetasowań talii
nazywane są „kombinacjami” talii.
Proces miejsca
Zaktualizujmy diagram, aby odzwierciedlał tę sytuację:
Algorytm
Realizacja
R
t.matrix
transition
p
Możemy teraz łatwo obliczyć prawdopodobieństwa nieoznaczone na każdym etapie dla dowolnej talii:
Oto one dla standardowej talii:
Dane wyjściowe to
(Porównaj to z wynikami, które zgłaszam w osobnej odpowiedzi opisującej symulację Monte-Carlo: wydają się być takie same, do oczekiwanych wielkości losowych zmian).
Oczekiwana wartość jest natychmiastowa:
Uwagi
Związki z innymi sekwencjami
Kiedy jest jedna z każdej karty, rozkład jest sekwencją odwrotności liczb całkowitych:
Gra jako proces stochastyczny
game
...
wyczucie czasu
źródło
źródło