Probabilistic problem on sampling items without replacement with different probabilities We have a set $S$ of $n$ items $i_1, i_2, \ldots, i_n$ that we select and remove (i.e., without replacement) from $S$ in a sequential fashion. The probability to select each of them at the beginning of the process is known and respectively equal to $p_1, p_2, \ldots, p_n$. Without loss of generality, assume $p_1\ge p_2\ge \ldots \ge p_n$. Let $S_t$ be the set of items at trial $t$, i.e., after having selected (and removed) $t-1$ items. The probability to select each item $i_j\in S_t$ at trial $t$ is equal to $\frac{p_j}{\sum_{k\in S_t} p_k}$.

Questions: Let $X_k\in\{i_1,i_2,\ldots,i_n\}$ be the $k$-th selected item. Let $K_j\in\{1,2,\ldots,n\}$ be the unique trial where $i_j$ is selected, i.e., $X_{K_j}=i_j$. Finally, let $M_j\in\{1,2,\ldots,n\}$ be the first trial where $i_1, i_2,\ldots, i_j$ are all selected. How can we find $\mathbb{E}[K_j]$ and $\mathbb{E}[M_j]$?
 A: There is no nice closed form for $\mathbb E[K_j]$ and $\mathbb E[M_j]$, but we can write them down explicitly. Since it makes no difference, I assume that $\{i_1,\dots,i_n\}=[n]$, using $[n]=\{1,\dots,n\}$.
Now, let $i\in\mathbb Z\cap[0,n]$ and take distinct $x=(x_1,\dots,x_i)$ from $[n]$. Let $\mathcal X_m=\{x_k:k\in[m]\}$ for $m\in\mathbb Z\cap[0,i]$ be the set of items taken up to step $m$. Then we have
$$\mathbb P(X_1=x_1,\dots,X_i=x_i)=\prod_{m=1}^i\frac{p_{x_m}}{1-\sum_{y\in\mathcal X_{m-1}}p_y}.$$
As an example, we have $\mathbb P(X_1=x_1,X_2=x_2)=\frac{p_{x_1}p_{x_2}}{1-p_{x_1}}$.
Expanding the defnition, we have
$$\mathbb E[K_j]=\sum_{i=1}^n\mathbb P(K_j=i)i=\sum_{i=1}^n\sum_{x\in\mathcal K_{j,i}}\mathbb P(X_1=x_1,\dots,X_i=x_i)i,$$
where $\mathcal K_{j,i}$ is the set of all distinct $x=(x_1,\dots,x_i)\in[n]^i$ with $x_i=j$. Plugging in the product for the probability gives an explicit form. We can also consider atoms, that is for $n$ distinct $x=(x_1,\dots,x_n)$ (i.e. a permutation) let $P_j(x)\in[n]$ be the position of $j$ in $x$, meaning $x_{P_j(x)}=j$. Then we can consider the sum
$$\mathbb E[K_j]=\sum_x\mathbb P(X_1=x_1,\dots,X_n=x_n)P_j(x)$$
over all outcomes $x$. The discussion for $M_j$ is similar. Here, we would just consider the first position $P^*_j(x)$ where all $[j]$ have been selected, and write $\mathbb E[M_j]=\sum_x\mathbb P(X_1=x_1,\dots,X_n=x_n)P^*_j(x)$. Alternatively, we can define $\mathcal K^*_{j,i}$ analogous to the above, meaning the set over all distinct $x\in[n]^i$ such that $x_i\in[j]$ and $[j]\subseteq\mathcal X_i$ for the given $x$. Then we recover the other form as well. But, unfortunately, the actual answer is: There is no satisfying, closed form for these expectations.
