Dan Romik (Weizmann I.)

will speak on

Probability distributions computable by random walks on graphs (joint work with Guy Kindler)

Abstract:

We study the random number generation model defined by Knuth and Yao, known as the finite-state generator (f.s.g.), namely that of a finite-state automaton driven by random unbiased bits, that outputs the binary expansion of a random variable X in [0,1] (alternatively, one may think of X as generated by a random walk on a graph). The question is for which distribution functions F does there exist an f.s.g. for which the output X has distribution F. Knuth and Yao showed that if F is real-analytic, it must be a polynomial with rational coefficients, and asked to characterize all polynomial distribution functions obtainable in this fashion. We solve this problem, and in addition weaken the analyticity assumption to that of smoothness.

To suggest a talk (yours, or someone elses), contact Jon. Aaronson:

Back to: Jon Aaronson's homepage.

Last update on 20/10/02.