1
$\begingroup$

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?
  • 1
    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.2012-05-22

1 Answers 1

2

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.