不放回采样的边缘分布

282842712474

设有$n$元概率分布$p=(p_1,p_2,\cdots,p_n)$，定义不放回采样为：

1、先从$p$中随机采样一个$i_1$；
2、将剩下的$\{p_i|\forall i \ne i_1\}$重新归一化，然后从中随机采样一个$i_2$；
3、依此类推，每次都排除掉已经采样过的结果，然后重新归一化采样新的。

容易得到联合分布为：
$$p(i_1,i_2,\cdots,i_k) = p_{i_1}\times \frac{p_{i_2}}{1 - p_{i_1}} \times \frac{p_{i_3}}{1 - p_{i_1} - p_{i_2}}\times  \frac{p_{i_k}}{1 - p_{i_1} - p_{i_2} - \cdots - p_{i_{k-1}}}$$

问题：$i_k$的边缘分布，有线性的精确计算方法吗？最好效率至多是$\mathcal{O}(nk)$。