When sampling without replacement from a given distribution, what's the total expected weight of the last k sampled items?

Question

We are given a probability distribution $p_1 \ge$ $p_2 \ge$ $p_3 \ge \cdots p_n$ on $n$ items. We sample from this distribution without replacement (re-scaling probabilities after each sample to account for the removed item). We discard the first $n-k$ sampled items and keep the last $k$ sampled items. What is the expected value of the sum of probabilities of the last $k$ sampled items?

I hope the problem statement is clear. Has there been any work on this problem or any related problem? Are any interesting upper/lower bounds known?

If there are no existing results, any ideas for computing lower/upper bounds will be very helpful.

Answer 1

This method for creating a random permutation is used by poker players for estimating their expected value in a tournament which pays prizes for places lower than first. It is called the Independent Chip Model or ICM. The probabilities don't simplify that much although you can do better than the naive summation. I'll give a few different ways to describe this random permutation.

• Choose a winner proportionally. Eliminate that player, and rescale the probabilities, then choose the second place finisher proportionally. Repeat until all places are assigned.

• Each player has some integer number of chips in the proportion $p_1 : p_2 : ... :p_k$. Randomly eliminate one chip at a time so that each chip has an equal chance to be removed. When a player's last chip is eliminated, the player is knocked out. Players are ranked in reverse order of being knocked out.

I don't think it is obvious that these generate the same distribution on permutations. The second requires rational ratios between the probabilities, and is it obvious that doubling the number of chips won't change the distribution? However, a third description connects the two.

• Each player has some integer number of chips in the proportion $p_1 : p_2 : ... :p_k$. Shuffle the chips. Sort the players by their highest chips. If you reveal the chips one by one from the bottom, you get the second method. If you reveal the chips from the top, you get the first.

Anyway, there are a few known results about the equities according to the ICM. For example, I proved that if prizes are nonincreasing, then the equity is concave, so players should be risk-averse in heads-up pots. Also, there are some ICM calculators, such as my program ICM Explorer, which you can download and use to calculate the finishing probabilities for up to $10$ players.

I haven't thought much about your particular problem, but I think the second description, eliminating chips to knock players out, may be helpful. I did look at the probabilities of finishing last, or the case of $k=1$, for some particular cases.

Answer 2

This may not be directly relevant if what you put as the question is the only thing that you are concerned with. However, if you in fact need to create an unequal probability sample, and you asked only for a small technical part of the process that you are struggling with, here's some broader context.

Sampling without replacement with unequal probabilities is an extremely messy procedure. Brewer and Hanif (1982) outlined about 50 algorithms to perform sampling of several units in a row in such a way that the ultimate probabilities of selection match the target $p_1 \ge p_2 \ge \ldots$ -- simply rescaling probabilities does not do the trick, and the "probabilities'' do not sum up to 1, as you've discovered the hard way. As a major innovation in this field of work, there's been papers in the second half of the 1990s (Tille 1996, Deville and Tille 1998) proposing elimination and sample splitting procedures that are arguably more straightforward than the procedures described by Brewer.