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.


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]

  • $\begingroup$ You are only considering the 10 cards in the last draw right? $\endgroup$
    – Lii
    Commented Sep 7, 2019 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
    Commented Sep 9, 2019 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$ Commented Sep 10, 2019 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
    Commented Sep 11, 2019 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$ Commented Sep 11, 2019 at 16:14

3 Answers 3


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 %>% 

  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)

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


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

  • 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
    Commented Sep 8, 2019 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$ Commented Sep 9, 2019 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$ Commented Sep 9, 2019 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
    Commented Sep 10, 2019 at 12:47
  • 2
    $\begingroup$ You are correct on this. I am wondering what the correct analytical formula is. $\endgroup$ Commented Sep 10, 2019 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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