Consider random sampling from a collection of N labeled objects,
without replacement. We draw the first object according to a
nonuniform distribution p_1, ..., p_N. Call the result X_1. We draw
the second object among the remaining N-1, from the obviously
renormalized distribution p_j / (sum_{k not X_1} p_k). And so forth
similarly until K objects are drawn, with K <= N. Can we show that the
probability of any particular object being drawn after K draws is
greater than K * p_min, where p_min is the minimum of the original
p_j?

This looks like a problem that could be covered in some textbooks, but
I haven't found it so far. A naive induction in K fails for some
reason, and the expression I get for the desired probability is too
complex for me to analyze. Any help would be greatly appreciated and
duly acknowledged.