Kevin Compton: Probabilistic Transforms in the Analysis of Algorithms

This is a joint work with Olgica Milenkovic.

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, $n$ distinguishable balls are uniformly distributed into $m$ distinguishable urns. If $X_i$ is the number of balls occupying urn $i$, $X_1,...,X_m$ has a multinomial distribution. Applying the Poisson transform [GM84] to any occupancy statistic $f(n,m)$ (i.e., a statistic which is a function of the joint distribution of $X_1,...,X_m$) gives a function $F(x,m)$ which may be regarded as an occupancy statistic in a model with independent, Poisson-distributed random variables $Z_1,...,Z_m$ of mean $x$. 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 $f(n,a(n))$ (for certain functions $a(n)$) 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].

Bibliography

GM84

Gaston H. Gonnet and J. Ian Munro.
The analysis of linear probing sort by the use of a new mathematical transform.
J. Algorithms, 5(4):451-470, 1984.

Mil02

Olgica Milenkovic.
Probabilistic Transforms in the Analysis of Algorithms.
PhD thesis, University of Michigan, 2002.

Back to the Index