sloan@uicbert.eecs.uic.edu (Bob Sloan) (06/28/91)
I'm looking for information on the Cupon Collector's problem: How many times do you have to draw with replacement from an urn with N distinct balls until you've seen all N of them (alternatively, if there are N different cupons being put in cereal boxes with equal probability, how many boxes of cereal do you have to buy to get one of each cupon?) It's easy to show that the expected number of tries is very close to N ln N. What I need, however, is the probability distribution. More precisely, I want to be able to guarantee that my probability of having seen all N cupons is greater than p if I draw f(p,N) times. It's fine if f is in big theta terms, but I'd like a tolerably "nice" function. (I've worked out an expression that has a really nasty sum in it.) I'd appreciate email; our connections to net news are, alas, nondeterministic. Robert Sloan, Asst. Prof. EECS Dept. (M/C 154) University of Illiois at Chicago Box 4348 Chicago, IL 60680 Internet: sloan@turing.eecs.uic.edu