I wrote:
So the theorem says we can make a deterministic choice that makes the counts #{i: 1 leq i leq k and s_i = s} stay within 1 of their expected values under random choice, and achieves this simultaneously for all k geq 1 and all s in S.
In fact, the theorem says that we can achieves this result by making choices in a particular (and particularly simple) way. That is, we present an algorithm, not an existence proof. I'll describe the algorithm intuitively, since it may make some bells go off in someone's head: For intuition, think of k as time, and imagine that S is a set of people each of whom has an appetite-level (pi_1 (s) + ... + pi_k (s)) - #{i: 1 leq i leq k and s_i = s} at time k. That is, your appetite goes up by pi_k (s) at time k unless you're the lucky person who gets a biscuit at time k, in which case your appetite goes down by 1 - pi_k (s). Everyone starts out with appetite 0. You die of hunger if your appetite ever rises above 1, and die of overfeeding if your appetite ever falls below -1. The person you should feed next is the person who'll die of hunger soonest if left unfed, not including those people who can't be fed right now (because they'll die of overfeeding if you do). Proving that this works isn't hard (though it also isn't hard to flail around for a while and not succeed in proving it if you don't have the right idea). But the problem and the algorithm and the proof are sufficiently simple that I'm sure this is all old stuff. I also wrote:
If you like, you can take pi_1 = pi_2 = ... = some fixed distribution pi; this special case is not any easier than the general result (which is a little tricky but is not in the end very deep).
In fact, pi_1 = pi_2 = ... is the case we are most interested in (even though our construction works for the general case). So even if you know of prior work on this special case alone (not the general case), we'd be very interested. Whoa, it's 10 a.m., and thinking about all these people getting fed is making me hungry; gotta go get some breakfast! Maybe some muffins? :-) Jim Propp