Oczekiwany numer będę włączony po wyciągnięciu kart, dopóki nie otrzymam asa, 2, 3 itd

12

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ć

  • Ti=first position of card whose value is i
  • Ui=last position of card whose value is i

Problem zasadniczo polega na ustaleniu prawdopodobieństwa, że ​​będziesz na gdy skończy się talia, a mianowicie:k

Pr(T1<<TkUk+1<Tk)

Rozumiem

Pr(T1<<Tk)=1/k!andPr(Uk+1<Tk)=1/70

ale nie mogłem dostać się dalej ...

rachunek
źródło
1
Co się stanie, jeśli wylosowałeś już wszystkie sekundy przed wylosowaniem pierwszego asa? 2
Gung - Przywróć Monikę
Czy „oczekiwana” liczba naprawdę oznacza „najbardziej prawdopodobną” liczbę?
whuber
Jest to interesujący problem, ale nie jestem pewien co do matematyki, którą piszesz po „problem w istocie”. Czy w pierwszym stwierdzeniu miałeś na myśli napisanie zamiast ? Jednak nawet wtedy nie jestem pewien, czy stwierdzenie jest poprawne. Rozważ początek sekwencji . Mamy a więc T 1 > T 2 , ale jeśli dobrze rozumiem twój opis tekstowy, nadal możemy wybrać Asa na drugiej pozycji, a następnie 2 na piątej pozycji? A zatem T 1 < T 2 nie jest warunkiem koniecznym? T 1 = 2 , T 2 = 12AAA2T1=2,T2=1T1>T2T1<T2
TooTone
@TooTone Och, miałem na myśli jak powiedziałeś, i masz rację; T 1 < T 2 nie jest warunkiem koniecznym ...T1<T2
rachunek
@gung W takim przypadku twoja talia się wyczerpie i nadal będziesz mieć 2.
rachunek

Odpowiedzi:

0

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

results
    2     3     4     5     6     7     8     9     J     K     Q     T 
 1406  7740 16309 21241 19998 15127  9393  4906   976   190   380  2334 

a oto kod R na wypadek, gdybyś chciał się nim bawić ..

# monte carlo card-drawing functions from here
# http://streaming.stat.iastate.edu/workshops/r-intro/lectures/5-Rprogramming.pdf

# create a straightforward deck of cards
create_deck <-
    function( ){
        suit <- c( "H" , "C" , "D" , "S" )
        rank <- c( "A" , 2:9 , "T" , "J" , "Q" , "K" )
        deck <- NULL
        for ( r in rank ) deck <- c( deck , paste( r , suit ) )
        deck
    }

# construct a function to shuffle everything
shuffle <- function( deck ){ sample( deck , length( deck ) ) }

# draw one card at a time
draw_cards <-
    function( deck , start , n = 1 ){
        cards <- NULL

        for ( i in start:( start + n - 1 ) ){
            if ( i <= length( deck ) ){
                cards <- c( cards , deck[ i ] )
            }
        }

        return( cards )
    }

# create an empty vector for your results
results <- NULL

# run your simulation this many times..
for ( i in seq( 100000 ) ){
    # create a new deck
    sdeck <- shuffle( create_deck() )

    d <- sdeck[ grep('A|2' , sdeck ) ]
    e <- identical( grep( "2" , d ) , 1:4 )

    # loop through ranks in this order
    rank <- c( "A" , 2:9 , "T" , "J" , "Q" , "K" )

    # start at this position
    card.position <- 0

    # start with a blank current.draw
    current.draw <- ""

    # start with a blank current rank
    this.rank <- NULL

    # start with the first rank
    rank.position <- 1

    # keep drawing until you find the rank you wanted
    while( card.position < 52 ){

        # increase the position by one every time
        card.position <- card.position + 1

        # store the current draw for testing next time
        current.draw <- draw_cards( sdeck , card.position )

        # if you draw the current rank, move to the next.
        if ( grepl( rank[ rank.position ] , current.draw ) ) rank.position <- rank.position + 1

        # if you have gone through every rank and are still not out of cards,
        # should it still be a king?  this assumes yes.
        if ( rank.position == length( rank ) ) break        

    }

    # store the rank for this iteration.
    this.rank <- rank[ rank.position ]

    # at the end of the iteration, store the result
    results <- c( results , this.rank )

}

# print the final results
table( results )

# make A, T, J, Q, K numerics
results[ results == 'A' ] <- 1
results[ results == 'T' ] <- 10
results[ results == 'J' ] <- 11
results[ results == 'Q' ] <- 12
results[ results == 'K' ] <- 13
results <- as.numeric( results )

# and here's your expected value after 100,000 simulations.
mean( results )
Anthony Damico
źródło
Dlaczego jest to Aniemożliwe? Rozważmy na przykład sekwencję 48 kart, po których następuje AAAA.
TooTone,
masz rację .. jest to jeden z 270725 - lub z kodem R1/prod( 48:1 / 52:5 )
Anthony Damico
1
Ta odpowiedź jest niepoprawna. Rozważmy liczbę „2”: ponieważ może to wynikać tylko wtedy, gdy wszystkie 2 zostaną napotkane przed którąkolwiek z 1, prawdopodobieństwo to jest równe 1 a zatem jego oczekiwanie w twojej symulacji wynosi105/ ( 8(84)=70ze standardowym błędem37,5. Twój wynik1660jest ponad sześć standardowych błędów za wysoki, co prawie na pewno jest błędne. Dokładna wartość średniej (na podstawie innej symulacji z106iteracjami) wynosi5,833±0,004. 105/(84)1428.637.516601065.833±0.004
whuber
1
Twój mocno udokumentowany kod jest niestety kilkakrotnie dłuższy i wolniejszy niż powinien. Wykazałem, że jego dane wyjściowe są niepoprawne; chociaż chciałbym mieć czas na debugowanie twojego kodu, nie robię tego i nie jest to moim zadaniem. Mój argument jest następujący: nadal będziesz pracował nad „2” na końcu, tylko wtedy, gdy wszystkie „2” poprzedzą wszystkie „A”. Wśród jednakowo prawdopodobnych sposobów ułożenia czterech „2” i czterech „A”, dokładnie jeden z nich spełnia to kryterium. Dlatego swoją wartośćw pozycji „2” powinna być zbliżona do105/70=1429, ale tak nie jest. (4+44)=70results105/70=1429
whuber
1
Nawet moderatorzy nie mogą usunąć głosów innych ludzi :-). Test chi-kwadrat sugeruje teraz, że twoje wyniki zgadzają się z moimi, ale byłoby miło wiedzieć, jak przetestowałeś swoją symulację, ponieważ poprawiłoby to pewność Twojej odpowiedzi. W rzeczywistości, zgodnie z edycją dokonaną w pierwszym akapicie w odpowiedzi, teraz oba nasze wyniki są błędne: ponieważ zinterpretowałem twoje pytanie, nadal nie można pracować nad asem, gdy wszystkie karty są wyczerpane.
whuber
7

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:

#
# Simulate one play with a deck of `n` distinct cards in `k` suits.
#
sim <- function(n=13, k=4) {
  deck <- sample(rep(1:n, k)) # Shuffle the deck
  deck <- c(deck, 1:n)        # Add sentinels to terminate the loop
  k <- 0                      # Count the cards searched for
  for (j in 1:n) {
    k <- k+1                          # Count this card
    deck <- deck[-(1:match(j, deck))] # Deal cards until `j` is found
    if (length(deck) < n) break       # Stop when sentinels are reached
  }
  return(k)                   # Return the number of cards searched
}

Zastosowanie tego w odtwarzalny sposób można wykonać za pomocą replicatefunkcji po ustawieniu zarodka liczb losowych, jak w

> set.seed(17);  system.time(d <- replicate(10^5, sim(13, 4)))
   user  system elapsed 
   5.46    0.00    5.46

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

> n <- length(d)
> mean(d)
[1] 5.83488

> sd(d) / sqrt(n)
[1] 0.005978956

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

Możemy również chcieć zobaczyć tabelę częstotliwości (i ich standardowych błędów). Poniższy kod trochę uwydatnia tabelę:

u <- table(d)
u.se <- sqrt(u/n * (1-u/n)) / sqrt(n)
cards <- c("A", "2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K")
dimnames(u) <- list(sapply(dimnames(u), function(x) cards[as.integer(x)]))
print(rbind(frequency=u/n, SE=u.se), digits=2)

Oto wynik:

                2       3      4      5      6      7       8       9       T       J       Q       K
frequency 0.01453 0.07795 0.1637 0.2104 0.1995 0.1509 0.09534 0.04995 0.02249 0.01009 0.00345 0.00173
SE        0.00038 0.00085 0.0012 0.0013 0.0013 0.0011 0.00093 0.00069 0.00047 0.00032 0.00019 0.00013

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:13n4k

draw <- function(deck) {
  n <- length(sentinels <- sort(unique(deck)))
  deck <- c(deck, sentinels)
  k <- 0
  for (j in sentinels) {
    k <- k+1
    deck <- deck[-(1:match(j, deck))]
    if (length(deck) < n) break
  }
  return(k)
}

(Można go używać drawzamiast simwszędzie, ale dodatkowa praca wykonana na początku drawpowoduje, ż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łę:

n <- 4 # Distinct cards
k <- 2 # Number of suits
d <- expand.grid(lapply(1:(n*k), function(i) 1:n))
e <- apply(d, 1, function(x) var(tabulate(x))==0)
g <- apply(d, 1, function(x) length(unique(x))==n)
d <- d[e & g,]

Teraz djest ramka danych, której wiersze zawierają wszystkie przetasowania. Zastosuj drawdo każdego wiersza i policz wyniki:

d$result <- apply(as.matrix(d), 1, draw)
    (counts <- table(d$result))

Wyjście (które chwilowo wykorzystamy w formalnym teście) to

   2    3    4 
 420  784 1316 

( 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)4202. Spośród2520różnych tasowania,2520/6=420mają tę właściwość).1/(2+22)=1/625202520/6=420

Możemy przetestować wyjście za pomocą testu chi-kwadrat. W tym celu stosuje się ja sim razy na tym przypadku n = 4 różne karty w k = 2 garniturach:10,000n=4k=2

>set.seed(17)
>d.sim <- replicate(10^4, sim(n, k))
>print((rbind(table(d.sim) / length(d.sim), counts / dim(d)[1])), digits=3)

         2     3     4
[1,] 0.168 0.312 0.520
[2,] 0.167 0.311 0.522

> chisq.test(table(d.sim), p=counts / dim(d)[1])

    Chi-squared test for given probabilities

data:  table(d.sim) 
X-squared = 0.2129, df = 2, p-value = 0.899

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 .psimnksimn=13k=4

Na koniec test chi-kwadrat z dwiema próbkami porównuje wynik z simwynikiem podanym w innej odpowiedzi:

>y <- c(1660,8414,16973,21495,20021,14549,8957,4546,2087,828,313,109)
>chisq.test(cbind(u, y))

data:  cbind(u, y) 
X-squared = 142.2489, df = 11, p-value < 2.2e-16

Ogromna statystyka chi-kwadrat daje wartość p, która jest zasadniczo zerowa: bez wątpienia simnie 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.

Whuber
źródło
4

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:

  1. Losowe tasowanie kart można wygenerować przez losowe tasowanie N kart, a następnie losowe przeplatanie pozostałych w nich kart k .N+kNk

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

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

  4. ith

5.83258855290199651/9

1982600579265894785026945331968939023522542569339917784579447928182134345929899510000000000

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

N=k1+k2++kmk1k213(4,4,,4)

NN!=N×(N1)××2×1Nk1k2k1!×k2!××km!

(Nk1,k2,,km)=N!k1!k2!km!,

nazywane są „kombinacjami” talii.

k1k1!/k1!=1k1+1k2k1_0k2

_____k1 stars

k2k1+k2(k1+k2k1,k2)=(k1+k2)!k1!k2!

k3((k1+k2)+k3k1+k2,k3)=(k1+k2+k3)!(k1+k2)!k3!k1+k2k1+k2+k3

1×(k1+k2)!k1!k2!×(k1+k2+k3)!(k1+k2)!k3!=(k1+k2+k3)!k1!k2!k3!.

kn(Nk1,k2,,km)

Proces miejsca

k1n=k1+k2++kj1p1nk=kj

_____p1 stars____np stars

pq1n+kpqp+1kq(n+kk)pq

Zaktualizujmy diagram, aby odzwierciedlał tę sytuację:

_____p1 starss stars | ____nps stars

||ssq

jkj1|

τn,k(s,p)=((p1)+jj)((nps)+(kj)1kj1)

|p+s+j+1

  • p
  • s|
  • j
  • |

τn,k(s,p)pq=p+s+j+1sqp

Prn,k(q|p)=(j(p1+jj)(n+kqkj1))/(n+kk)

j=max(0,q(n+1))j=min(k1,q(p+1)n,k,q,p

Algorytm

1102,3,,k1p1=(1,0,,0)

k2p1p2(Prk1,k2(q|p),1pk1,1qk2)k1+k2++kmjpj1jj


Realizacja

Rt.matrix(n+kk)

t.matrix <- function(q, p, n, k) {
  j <- max(0, q-(n+1)):min(k-1, q-(p+1))
  return (sum(choose(p-1+j,j) * choose(n+k-q, k-1-j))
}

transitionpj1pjp1p

#
# `p` is the place distribution: p[i] is the chance the place is `i`.
#
transition <- function(p, k) {
  n <- length(p)
  if (n==0) {
    q <- c(1, rep(0, k-1))
  } else {
    #
    # Construct the transition matrix.
    #
    t.mat <- matrix(0, nrow=n, ncol=(n+k))
    #dimnames(t.mat) <- list(p=1:n, q=1:(n+k))
    for (i in 1:n) {
      t.mat[i, ] <- c(rep(0, i), sapply((i+1):(n+k), 
                                        function(q) t.matrix(q, i, n, k)))
    }
    #
    # Normalize and apply the transition matrix.
    #
    q <- as.vector(p %*% t.mat / choose(n+k, k))
  }
  names(q) <- 1:(n+k)
  return (q)
}

Możemy teraz łatwo obliczyć prawdopodobieństwa nieoznaczone na każdym etapie dla dowolnej talii:

#
# `k` is an array giving the numbers of each card in order;
# e.g., k = rep(4, 13) for a standard deck.
#
# NB: the *complements* of the p-vectors are output.
#
game <- function(k) {
  p <- numeric(0)
  q <- sapply(k, function(i) 1 - sum(p <<- transition(p, i)))
  names(q) <- names(k)
  return (q)
}

Oto one dla standardowej talii:

k <- rep(4, 13)
names(k) <- c("A", 2:9, "T", "J", "Q", "K")
(g <- game(k))

Dane wyjściowe to

         A          2          3          4          5          6          7          8          9          T          J          Q          K 
0.00000000 0.01428571 0.09232323 0.25595013 0.46786622 0.66819134 0.81821790 0.91160622 0.96146102 0.98479430 0.99452614 0.99818922 0.99944610

0.99944611

> g[13] <- 1; diff(g)
          2           3           4           5           6           7           8           9           T           J           Q           K 
0.014285714 0.078037518 0.163626897 0.211916093 0.200325120 0.150026562 0.093388313 0.049854807 0.023333275 0.009731843 0.003663077 0.001810781

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

> sum(diff(g) * 2:13)
[1] 5.832589

k3


Uwagi

Związki z innymi sekwencjami

Kiedy jest jedna z każdej karty, rozkład jest sekwencją odwrotności liczb całkowitych:

> 1/diff(game(rep(1,10)))
[1]      2      3      8     30    144    840   5760  45360 403200

ii!+(i1)!i=1kik>1

Gra jako proces stochastyczny

ipjjigame

> sapply(1:13, function(i) game(rep(4,i)))

[[1]]
[1] 0

[[2]]
[1] 0.00000000 0.01428571

[[3]]
[1] 0.00000000 0.01428571 0.09232323

[[4]]
[1] 0.00000000 0.01428571 0.09232323 0.25595013

...

[[13]]
 [1] 0.00000000 0.01428571 0.09232323 0.25595013 0.46786622 0.66819134 0.81821790 0.91160622 0.96146102 0.98479430 0.99452614 0.99818922 0.99944610

1/(84)=1/70jthk1+k2++kj

j1j135.8333554×32

wyczucie czasu

m(k,k,,k)k2m3k=17n=10301/2O(k2n2.9)

k=4,n=301.31k=1,n=1001.31(1/4)2(100/30)2.92.72.87

Whuber
źródło
0

5.8329

#!/usr/bin/perl

use strict;

my @deck = (1..13) x 4;

my $N = 100000; # Monte Carlo iterations.

my $mean = 0;

for (my $i = 1; $i <= $N; $i++) {
    my @d = @deck;
    fisher_yates_shuffle(\@d);
    my $last = 0;
        foreach my $c (@d) {
        if ($c == $last + 1) { $last = $c }
    }
    $mean += ($last + 1) / $N;
}

print $mean, "\n";

sub fisher_yates_shuffle {
    my $array = shift;
        my $i = @$array;
        while (--$i) {
        my $j = int rand($i + 1);
        @$array[$i, $j] = @$array[$j, $i];
    }
}
Zen
źródło
Biorąc pod uwagę wyraźną rozbieżność między tą a wszystkimi poprzednimi odpowiedziami, w tym dwiema symulacjami i teoretyczną (dokładną), podejrzewam, że interpretujesz pytanie w inny sposób. Wobec braku jakiegokolwiek wyjaśnienia z Twojej strony musimy po prostu uznać to za błędne. (Podejrzewam, że możesz liczyć o jeden mniej, w takim przypadku twój 4.8 powinien być porównany z 5.83258 ...; ale nawet wtedy twoje dwie znaczące cyfry precyzji nie dają żadnego dodatkowego wglądu w ten problem.)
whuber
1
Tak! Był błąd „jeden po drugim”.
Zen,