On distributions computable by random walks on graphs

ABSTRACT

We answer a question raised by Donald E. Knuth and Andrew C. Yao, concerning the class of polynomials on [0, 1] that can be realized as the distribution function of a random variable, whose binary expansion is the output of a finite state automaton driven by unbiased coin tosses. The polynomial distribution functions which can be obtained in this way are precisely those with rational coefficients, whose derivative has no irrational roots on [0, 1].We also show, strengthening a result of Knuth and Yao, that all smooth distribution functions which can be obtained by such automata are polynomials.

REFERENCES

• 1: S. Karlin, L. S. Shapley, Geometry of Moment Spaces, Memoirs of the Amer. Math. Soc. 12, 1953.
• 2: P. J. Kelly, M. L. Weiss, Geometry and Convexity, Wiley, 1979.
• 3: D. E. Knuth, A. C. Yao, The complexity of nonuniform random number generation. Algorithms and Complexity: New Directions and Recent Results, ed. J. F. Traub, Addison-Wesley, 1976.
• 4: E. Mossel, Y. Peres, New coins from old: computing with unknown bias. To appear.
• 5: A. C. Yao, Context-free grammars and random number generation. Combinatorial Algorithms on Words, ed. A. Apostolico and Z. Galil, NATO ASI SERIES, Springer-Verlag 1985.