Average-Case Analysis of an Algorithm from Computer Algebra

Algorithms for symbolic integration and summation are now standard in computer algebra systems such as Maple and Mathematica. However, many of these algorithms have not been analyzed, and, in others, performance is much better than one would expect from the worst-case analysis. Average-case analysis does not seem to be a good alternative since the probability distribution on input instances is usually not readily ascertained. However, good average-case performance on a variety input distributions does provide evidence of the robustness of an algorithm. We will illustrate this with one of the first symbolic summation algorithms, Gosper\'s algorithm, which gives closed form solutions (when they exist) for a simple type summation known as hypergeometric summation. We will give distributions on input instances of this algorithm using well known ball and urn models from probability theory and show how to use probabilistic transforms to analyze average-case behavior. This is joint work with Olgica Milenkovic.