Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need help with a problem about classic probability and possible extensions to it. Suppose you have an urn with $N$ distinguishable balls. Every time you draw $k$ balls out of $N$. Some possible questions I haven't figured out yet are

  • what is the probability that two given balls never appear in two consecutive draws, out of, say, $5$ draws (or $M$ draws, more broadly)?
  • what is the probability that this is true for any pair of balls?
share|cite|improve this question
Could you please clarify your question. Every time you draw $k$ balls out of $n$, with replacement? Given two balls, say A and B, you do not want both of them occurring in any each of any two consecutive draws? It is a little confusing. – Sasha May 22 '12 at 23:24
up vote 2 down vote accepted

I'll assume you draw $k$ balls, put them back in the urn, draw $k$ balls, put them back, etc., etc.

The number of $k$-sets of balls is $N\choose k$.

Now suppose you've made your 17th draw, and you're about to make your 18th. How many ways can you make that 18th draw and not have two balls that were in the 17th draw?

Well, you might have none of the balls from the 17th draw. There are $N-k\choose k$ ways to do that (note that this is interpreted as zero if $N\lt2k$). Or, you might have exactly one of the balls from the 17th draw. There are ${k\choose1}{N-k\choose k-1}$ ways to do that (zero, if $N\lt2k-1$). All told, $${N-k\choose k}+{k\choose1}{N-k\choose k-1}$$ ways to make the 18th draw and not have two balls from the 17th draw.

So, the probability of not having two balls from the 17th draw in the 18th draw is $$\left({N-k\choose k}+{k\choose1}{N-k\choose k-1}\right)\div{N\choose k}$$ Let's call this quantity $P=P(N,k)$. It follows that if you draw balls $r$ times, the probability that you never have two balls in common in two consecutive draws is $P^{r-1}$. This answer the second question.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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