Probability of selecting a particular set, by sampling without replacement from a categorical distribution

Question

Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p_i$ to item $i$. I now repeatedly sample from this distribution, until I have obtained $k$ unique objects. I'd like to compute the probability that the set of objects obtained is exactly $\{1,\dots,k\}$.

Is there an efficient way to compute this probability, given $p_1,\dots,p_n$ and $k$?

I can see that the probability has the form

$$p = \sum_\sigma \prod_{i=1}^k {p_{\sigma(i)} \over (1-p_{\sigma(1)}) \cdots (1-p_{\sigma(1)}-\dots-p_{\sigma(i-1)})},$$ where the sum is over all permutations $\sigma \in S_k$ on $\{1,\dots,k\}$. (Here $\sigma$ represents the order in which the items $1,\dots,k$ are selected.) However, this formula for the probability involves $k!$ terms, so computing the probability in this way would take time exponential in $k$. Is there a more efficient way to compute it?

Of course, without loss of generality we can assume $n=k+1$.

Answer 1

For each $\Sigma \subseteq [k+1]$, you can compute the probability $q(\Sigma)$ that the first $|\Sigma|$ elements to appear are $\Sigma$ using the following recurrence: $q(\emptyset) = 1$ and when $\Sigma \neq \emptyset$, $$ q(\Sigma) = \sum_{\sigma \in \Sigma} q(\Sigma-\sigma) \frac{p_\sigma}{p_\sigma + \sum_{\tau \notin \Sigma} p_\tau}. $$ You are interested in $q([k])$. The total computation time is $O(k2^k)$ (ignoring arithmetic), if you compute the sum in the denominator in tandem. Perhaps this could be improved to $O(2^k)$.