A frequent criticism of average-case analysis of algorithms is that the probabilistic model used is often not realistic. Here we present an approach based on average-case analysis with respect to a large class of probabilistic models rather than a fixed model. Good performance in many models provides greater evidence of efficiency. In particular, we investigate ball and urn models and the transform techniques required to analyze algorithms on these models.
In the most familiar ball and urn model, distinguishable balls are uniformly distributed into distinguishable urns. If is the number of balls occupying urn , has a multinomial distribution. Applying the Poisson transform [GM84] to any occupancy statistic (i.e., a statistic which is a function of the joint distribution of ) gives a function which may be regarded as an occupancy statistic in a model with independent, Poisson-distributed random variables of mean . We consider other cases where balls may not be uniformly distributed and the urns may not be distinguishable. For each of these cases there is an associated distribution and transform. Our main results are Tauberian theorems that allow us to determine the asymptotic behavior of an occupancy statistic (for certain functions ) from the behavior of its transform. As an example we show that a crucial step in Gosper's algorithm from computer algebra has an average-case time which is much better than worst-case time in a variety of ball and urn models.
These results are from [Mil02].
Back to the Index