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

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ć

• $T_i = \text{first position of card whose value is }i$
• $U_i = \text{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(T_1<\cdots<T_k \cap U_{k+1} < T_k)$$

Rozumiem

$$Pr(T_1<\cdots<T_k) = 1/k! \\ \text{and} \\ Pr(U_{k+1} < T_k) = 1/70$$

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

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 )

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

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:$13$n$4$k

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 + $420$$2$. Spośród2520różnych tasowania,2520/6=420mają tę właściwość).$1/\binom{2+2}{2} = 1/6$$2520$$2520/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,000$$n = 4$$k = 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 .$p$sim$n$$k$sim$n=13$$k=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.

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+k$$N$$k$

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. $i^\text{th}$

$5.8325885529019965$$1/9$

$$\frac{1982600579265894785026945331968939023522542569}{339917784579447928182134345929899510000000000}$$

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 = k_1+k_2+\cdots+k_m$$k_1$$k_2$$13$$(4,4,\ldots,4)$

$N$$N! = N\times(N-1)\times\cdots\times 2\times 1$$N$$k_1$$k_2$$k_1!\times k_2!\times \cdots \times k_m!$

$$\binom{N}{k_1,k_2,\ldots,k_m} = \frac{N!}{k_1!k_2!\cdots k_m!},$$

nazywane są „kombinacjami” talii.

$k_1$$k_1!/k_1! = 1$$k_1+1$$k_2$$*$$k_1$$\_$$0$$k_2$

$$\underbrace{\_*\_*\_\cdots\_*\_}_{k_1\text{ stars}}$$

$k_2$$k_1+k_2$$\binom{k_1+k_2}{k_1,k_2} = \frac{(k_1+k_2)!}{k_1!k_2!}$

$k_3$$\binom{(k_1+k_2)+k_3}{k_1+k_2,k_3}= \frac{(k_1+k_2+k_3)!}{(k_1+k_2)!k_3!}$$k_1+k_2$$k_1+k_2+k_3$

$$1\times\frac{(k_1+k_2)!}{k_1!k_2!}\times\frac{(k_1+k_2+k_3)!}{(k_1+k_2)!k_3!} = \frac{(k_1+k_2+k_3)!}{k_1!k_2!k_3!}.$$

$k_n$$\binom{N}{k_1,k_2,\ldots,k_m}$

Proces miejsca

$k_1$$n = k_1 + k_2 + \cdots + k_{j-1}$$p$$1$$n$$k=k_j$

$$\underbrace{\_*\_*\_\cdots\_*\_}_{p-1\text{ stars}}\odot\underbrace{\_*\_\cdots\_*\_}_{n-p\text{ stars}}$$

$\odot$$p$$q$$1$$n+k$$p$$q\ge p+1$$k$$q$$\binom{n+k}{k}$$p$$q$

Zaktualizujmy diagram, aby odzwierciedlał tę sytuację:

$$\underbrace{\_*\_*\_\cdots\_*\_}_{p-1\text{ stars}}\odot\underbrace{**\cdots*}_{s\text{ stars}}\ \vert\ \underbrace{\_*\_\cdots\_*\_}_{n-p-s\text{ stars}}$$

$\vert$$\odot$$\vert$$s$$s$$q$

$j$$\odot$$k-j-1$$\vert$

$$\tau_{n,k}(s,p) = \binom{(p-1)+j}{j}\binom{(n-p-s) + (k-j)-1}{k-j-1}$$

$\vert$$p+s+j+1$

• $p$
• $s$$\vert$
• $j$
• $\vert$

$\tau_{n,k}(s,p)$$p$$q=p+s+j+1$$s$$q$$p$

$${\Pr}_{n,k}(q|p) = \left(\sum_j \binom{p-1+j}{j}\binom{n+k-q}{k-j-1}\right) / \binom{n+k}{k}$$

$j=\max(0, q-(n+1))$$j=\min(k-1, q-(p+1)$$n, k, q,$$p$

Algorytm

$1$$1$$0$$2, 3, \ldots, k_1$$p_1 = (1, 0, \ldots, 0)$

$k_2$$p_1$$p_2$$(\Pr_{k_1,k_2}(q|p), 1\le p\le k_1, 1\le q\le k_2)$$k_1+k_2+\cdots+k_m$$j$$p_j$$1$$j$$j$

---

Realizacja

Rt.matrix$\binom{n+k}{k}$

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

transition$p_{j-1}$$p_j$$p_1$p

#
# `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.9994461$$1$

> 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

$k$$3$

---

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

$i$$i! + (i-1)!$$i=1$$k_i$$k\gt 1$

Gra jako proces stochastyczny

$i$$p_j$$j\ge i$game

> 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/\binom{8}{4}=1/70$$j^\text{th}$$k_1+k_2+\cdots+k_j$

$j$$1$$j$$13$$5.833355$$4 \times 32$

wyczucie czasu

$m$$(k,k, \ldots, k)$$k^2$$m^3$$k=1$$7$$n=10$$30$$1/2$$O(k^2 n^{2.9})$

$k=4, n=30$$1.31$$k=1, n=100$$1.31(1/4)^2(100/30)^{2.9}\approx 2.7$$2.87$

$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];
    }
}