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].