A probability question that I failed to answer in a job interview There are $N$ different sized targets, numbered $1, 2,\dots, N$.  A blindfolded shooter shoots towards random directions. Because target sizes are different, the hit probabilities of each target are different, say $p_1, p_2,\dots ,p_N$. A bullet hole is left on the target each time a target is hit. The shooter does not know whether a shot hit a target or not.
Note that a shoot could be "void", i.e., $p_1+p_2+\cdots+p_N\le1$. One shot at most hits one target.
The shooter keeps shooting until $X$ out of the $N$, $X<N$, targets have bullet holes. ( each of the $X$ targets is hit at least once). Then the shooter is told to stop.
The question is: at the end of the game, what is the probability that target $k$ has NOT been hit, $1\leq k\leq N$.
 A: We may as well suppose the game continues until all targets have been hit (which will happen eventually if all $p_j > 0$; we may as well remove any targets that have $p_j = 0$).
For each subset $S$ of $\{1,\ldots, N\}$, let $p_S = \sum_{s \in S} p_s$ be the probability that a shot hits a member of $S$, and let
$a_{i,t}(S)$ be the probability that target $i$ is one of the first  $t$ targets in set $S$ to be hit.  You want $1 - a_{i,X}(\{1,\ldots,N\})$. 
Of course $a_{i,t}(S) = 0$ if $i \notin S$, and we also take it to be $0$ if 
$t = 0$.
Otherwise, conditioning on the first target in $S$ to be hit,
$$ a_{i,t}(S) =  \dfrac{p_i}{p_S} + \sum_{j \in S \backslash \{i\}} \dfrac{p_j}{p_S} a_{i,t-1}(S \backslash \{j\}) $$
Now I claim that 
$$ a_{i,t}(S) = \sum_{T \subseteq S \backslash \{i\}} c(t,|T|,|S|) \frac{p_i}{p_{T \cup \{i\}}} $$
for some constants $c(t,m,n)$, $0 \le m \le n-1$.
I will prove this by induction on $t$.
In the case $t=1$ we have $a_{i,1}(S) = p_i/p_S$, so $c(1,m,n) = 1$ if
$m = n-1$, $0$ otherwise.
If $t >1$, we have (with $|S|=n$):
$$ \eqalign{a_{i,t}(S) &= \dfrac{p_i}{p_S} +  \sum_{j \in S \backslash \{i\}}
\dfrac{p_j}{p_S}
\sum_{T \subseteq S \backslash \{i,j\}} c(t-1, |T|,n-1) \dfrac{p_i}{p_{T \cup \{i\}}}\cr
&= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2} c(t-1,m,n-1) \sum_{T \subseteq S \backslash \{i\}: |T| = m} \sum_{j \in S \backslash (T \cup \{i\})} \dfrac{p_j p_i}{p_S p_{T \cup \{i\}}}\cr
&= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2}  c(t-1,m,n-1) \sum_{T \subseteq S \backslash \{i\}: |T| = m} \dfrac{p_{S \backslash (T \cup \{i\})} p_i}{p_S p_{T \cup \{i\}}}\cr
&= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2}  c(t-1,m,n-1) \sum_{T \subseteq S \backslash \{i\}: |T| = m} \dfrac{(p_S - p_{T \cup \{i\}}) p_i}{p_S p_{T \cup \{i\}}}\cr
&= \dfrac{p_i}{p_S} + \sum_{m=0}^{n-2}  c(t-1,m,n-1) \sum_{T \subseteq S \backslash \{i\}: |T| = m} \left(\dfrac{p_i}{p_{T \cup \{i\}}} - \dfrac{p_i}{p_S}\right)\cr
&= \sum_{T \subseteq S \backslash \{i\}} c(t,|T|,n) \dfrac{p_i}{p_{T \cup \{i\}}}
}$$
where $c(t, m,n) = c(t-1, m,n-1)$ if $m < n-1$ while
$$c(t, n-1, n) = 1 - \sum_{m=0}^{n-2} {n-1 \choose m} c(t-1,m,n-1)$$
Hmm: it looks like
$$ c(t, m, n) = \cases{1 & for $t=n,m=0$\cr
                      (-1)^{n+m+t} {m-1 \choose {t+m-n}} & $ n-m \le t \le n$\cr
    0 & otherwise\cr}$$
There ought to be an inclusion-exclusion proof for this.
A: At the risk of shooting myself in the foot, here's how I'd approach it:
The key principle is that we can ignore any action that doesn't produce a tangible result.  In particular, this includes missing a target, so we can start by normalizing the probabilities: write $\tilde{p_i} =\frac{p_i}{\sum_{1\leq k\leq N}p_k}$ so that we can work with values that have $\sum\tilde{p_i}=1$.
But from here, it should be clear that the process is just drawing without replacement - after our trial, we'll have some set of $X$ items, and the probability that those items are $i_0, i_1, \ldots, i_X$ is $\tilde{p}_{i_0}\cdot\tilde{p}_{i_1}\cdots\tilde{p}_{i_X}$.  So the probability that target $k$ is hit is just $\dfrac{\sum_{\{S:\left|S\right|=X \wedge k\in S\}} \mathbb{P}_S}{\sum_{\{S: \left|S\right|=X\}} \mathbb{P}_S}$, where the lower sum is over all $X$-element subsets $S$ of $1\ldots N$ and the upper sum is over all those subsets with $k\in S$, and $\mathbb{P}_S=\prod_{i\in S}\tilde{p}_i$ (and of course, the probability that $k$ isn't hit is just the complement of this value).
EDIT: as pointed out by Nate Eldredge in a comment below, the formula can't simplify to one independent of the other probabilities; let the below serve as a cautionary tale about making assumptions!
This formula itself should offer further simplification, I'm reasonably sure, but that will take a little bit of chewing.  (I strongly suspect that everything else is just a red herring and the final probability is a simple expression in $\tilde{p}_k$ and $\tilde{q}_k=1-\tilde{p}_k$, but I need to work through the details and have my ducks in a row before I'm certain of that.)
A: I don't think it's easy. Say we have p1 = p2 = 0.49, and p3 .. p22 = 0.01. For the first two objects, the chance of being the first object is 0.49, the chance of being first or second is a bit above 0,98, and then it gets close to 1 very, very quickly. 
For the other objects, the chance of being the first object is 0.01, the chance of being one of the first two is about 0.03, and to be among the first 2 + n the chance is about n/20. 
If the probabilities are less extreme then I think it gets quite difficult, for example 20 items with 0.03 ≤ pk ≤ 0.07. 
A: Guys please criticize the following answer to my own question.
Let variable $L$ be the number of shots by the end of the game. Then, clearly, the probability of the $k$-th target survives is $(1-p_k)^L$.
Then the real question is how to determine $L$ or the $E(L)$, the expectation of $L$.
Let $q_i=1-p_i$ be the probability of missing a target for one single shot.
With $L$ shots, the probability that the $i$-th target has been hit at least once is 
$1-q_i^L$. Then given a set of targets $S$, where $k\notin S$ and $|S|=X$, the probability that all targets in $S$ have been hit at least once, let's call it $S$ completed, is that
\begin{equation}
P_{\mbox{S completed}} = \prod_{i\in S} (1-q_i^L) 
\end{equation}
Note that there are $C_{N-1}^{X}$ target set $S$ satisfying $k\notin S$ and $|S|=X$, forming a set $\tilde{S} = \{S \mid k\notin S \mbox{ and }|S|=X \}$. As said, $|\tilde{S}|=C_{N-1}^{X}$.
Because the game is over when $L$ shots have been made, then the probability that at least one $S\in\tilde{S}$ completed equals to 1 (I'm not sure if I'm correct by saying this). Or 
\begin{equation}
\sum_{S\in\tilde{S}} P_{\mbox{S completed}} = 1
\end{equation}
With all of this, we have
\begin{equation}
\sum_{S\in\tilde{S}} \prod_{i\in S} (1-(1-p_i)^L) = 1
\end{equation}
Knowing $p_i$, $1\leq i \leq N$, $L$ can be obtained using computation tools like Matlab or R. (I haven't verified the solution with the tools yet)
