4
$\begingroup$

Suppose I have a deck of N=1,000 cards where each card is a unique number from 1 to 1,000.


  • Draw 1: draw n=10 cards at random. Put them back

  • Draw 2: draw n=10 cards at random. Put them back

  • ...

  • Draw i: draw n=10 cards at random. Put them back


On the ith draw, what is the probability that any of the 10 cards was selected at least once in previous draws?

I've solved this problem through simulation. But I can't figure out the probabilistic approach.


Update

Thank you for all your contributions. My original question was not properly articulated, resulting on two different interpretations.

What I'm seeking is 1-P[drawing distinct cards on each draw]

$\endgroup$
  • $\begingroup$ You are only considering the 10 cards in the last draw right? $\endgroup$ – Lii Sep 7 at 4:03
  • $\begingroup$ Put them back and reshuffle (assuming perfectly random reshuffling)? Or put them at the base of the deck? That in my opinion should have been specified in the body of the question, because it is relevant if you draw from the top. With regard to the latter point: are you drawing from the top? Or just extracting a card from a random point along the height of the deck? That should have been specified as well maybe. $\endgroup$ – Fr1 Sep 9 at 18:05
  • $\begingroup$ Put them back and reshuffle. That of the deck of card is an analogy, as I cannot disclose the real problem. Needless to say, this is not about cards. $\endgroup$ – Thomas Speidel Sep 10 at 14:43
  • $\begingroup$ Given that you have received two different answers based on two different interpretations of your question, please clarify which interpretation is the one you intend. $\endgroup$ – whuber Sep 11 at 15:59
  • $\begingroup$ My original question was not properly articulated. The answer provided by Danial Kaviani addresses the interpretation I'm seeking, namely, 1-P[drawing distinct cards on each draw]. I've been struggling to translate the question in plain English $\endgroup$ – Thomas Speidel Sep 11 at 16:14
1
$\begingroup$

Below is my code that regenerates the results of my analytical solution: $$ 1- \Pi_{j=1}^{j=i-1} \frac{\binom{N-n\times j}{n}}{\binom{N}{n}} $$. The results of simulation and the analytical formula are close enough. For example at i= 6, the simulation gives 0.789 and the analytical formula gives 0.785.

n_runs <- 5000
N <- 1000
d <- data.frame(id = 1:N)
n_draws <- 6
n_samples <- 10

draw_sim <- c()

for(j in 1:n_runs){
  draw_all <- c()

  for (i in 1:n_draws){
    temp_draw <- sample_n(d, n_samples, replace = FALSE)
    draw_all <- bind_rows(draw_all, temp_draw)

  }

  all_repeats <- draw_all %>% 
    group_by(id) %>% 
    mutate(freq = n()) 

  repeats <- all_repeats %>% 
    filter(freq>1)   


  repeats <- length(unique(repeats$id))  %>% 
    as.data.frame() %>%
    rename( Freq = '.')

  draw_sim <- bind_rows(draw_sim,repeats)

}

# Probability: 
prob_draw <-  nrow(filter(draw_sim,Freq>0)) / nrow(draw_sim)
$\endgroup$
3
$\begingroup$

Let's say we are in the $i$-th draw, and chose 10 cards. In the previous $i-1$ draws, we want any of them to be selected at least once. We'll find the probability of those cards not being selected in any of the previous $i-1$ draws, and subtract from $1$. The probability of choosing $10$ cards that doesn't contain any of the $10$ cards we specified is $p={990 \choose 10}/{1000 \choose 10}$. If we assume independent draws as usual, not choosing any of the cards we specified in total $i-1$ draws become $p^{i-1}$. The probability we ask for is $1-p^{i-1}$.

Numerically, we have $p\approx 0.904$, and if we are talking about e.g. $5$ draws, the probability we want is $\approx 0.332$.

$\endgroup$
1
$\begingroup$

The answer provided by "gunes" is a good start. If the question is to determine the probability that only the ones at draw $i$ to be repeated from the previous ones the answer would be correct. However, if we want to see the probability that draw $i$ and any draws before have any repeated cards, the solution will be slightly different. At $i = 2$ the solution will be the same as above: $$ 1-\left [ \frac{\binom{N-n}{n}}{\binom{N}{n}} \right ]$$ However, for $i=3$ it will be $$ 1-\left [ \frac{\binom{N-n}{n}}{\binom{N}{n}} \right ]. \left [ \frac{\binom{N-2\times n}{n}}{\binom{N}{n}} \right ]$$ because during the third draw, we should exclude the ones that have been selected in first two draws and not repeated. Thus, the choices we will have are among the ones that have not been selected before ($N-2\times n$). With these, the general formula after pulling $i$ samples will be $$ 1- \Pi_{j=1}^{j=i-1} \frac{\binom{N-n\times j}{n}}{\binom{N}{n}} $$

$\endgroup$
  • 1
    $\begingroup$ This is incorrect. Consider a simpler problem with smaller values in place of 1000 and 10, or else run a simulation. $\endgroup$ – whuber Sep 8 at 14:24
  • $\begingroup$ Would you please elaborate more on your comment? I did not understand it. I ran a simulation and got the same result. By the way, I have just edited my comment to clarify what I mean. $\endgroup$ – Danial Kaviani Sep 9 at 17:52
  • 1
    $\begingroup$ Yes. I am trying to describe the chance that the first i draws consist of distinct cards. With the formula that I provided, we reach to that point (some cards to be repeated) much earlier: after 20 draws the chance of having distinct cards is $ 4.95 \times 10^{-10} $. At $ N/n $ (for this case 100 draw), the chance is $ 1.67 \times 10^{-224}$. $\endgroup$ – Danial Kaviani Sep 9 at 21:47
  • 1
    $\begingroup$ But that is patently wrong: for $i\gt 1$ your formula can never equal zero but the Pigeonhole Principle shows that at $N/n+1$ the chance is exactly zero. $\endgroup$ – whuber Sep 10 at 12:47
  • 2
    $\begingroup$ You are correct on this. I am wondering what the correct analytical formula is. $\endgroup$ – Danial Kaviani Sep 10 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.