Draw balls from a set of color balls: the probability of drawing a color seen before?

Question

Recently I am studying a probability problem related to the multivariate hypergeometric distribution. The problem is stated as:

Given well-mixed $n$ balls of $m$ colors, and assume that $n_i$ is the number of balls with color $i$, where $i \in {1, ..., m}$. So we have $\sum_{i=1}^{m}n_i = n$

Do $k$ random draws without replacement. What's the probability that the $k$-th draw is a color which has been drawn from the previous $(k-1)$ draws?

My naive solution is like this: the total possible ball sequences for $i$ draws would be:

$P(n, k)$

where $P(n, k)$ is the permutation of $k$ items from $n$ items.

And among these sequences, only the ones with at least one occurrence of the last ball's color satisfy the requirement. So the possible sequences would be the all sequences except for the cases where none of the $(k-1)$ draws contain the last ball's color:

$P(n, k) - \sum_{i=1}^{m}n_i*P(n-n_i, k-1)$

So the probability can be calculated as:

$1 - {{\sum_{i=1}^{m}n_i*P(n-n_i, k-1)}\over{P(n, K)}}$

Now my questions are:

1. Is my naive solution correct, or there are cases missing or overlapping?
2. I tried to write a computer program to calculate the probability given $n, m$ and $k$, however it turns out to be very slow for large inputs, thanks to the permutations. Is there any simpler (so fast on computation) formula for this probability, like a closed form formula?

Any hints would be appreciated, and let me know if the question is too hard to understand~

Answer 1

Your method is essentially correct. You wrote $\sum_{i=1}^k$ where you should have $\sum_{i=1}^m.$

I doubt there is much of a simplification possible. It's just a single sum over terms which are single products, so it should evaluate almost instantly unless your parameters are huge. My guess is that you are probably computing $P(n,k)$ inefficiently if you are getting performance issues, although another possibility is that you are computing each probability quickly but you are looping over all possible counts $\lbrace n_i \rbrace$ and there are many of those. If you have a large number of colors but there are repetitions in the counts $n_i$ then you could collect the identical terms. You could also memoize the values of $P(n,k),$ but are you really dealing with values of $n$ and $k$ where this would be necessary? If so, perhaps you would want to use an approximation like Stirling's formula $m! \sim \sqrt{2 \pi m} (\frac m e)^m$ instead of computing the exact value of $P(n,k)= n!/(n-k)!$.