Discrepancy convergence for the drunkard's walk on the sphere
arXiv:math/0102205
Abstract
We analyze the drunkard's walk on the unit sphere with step size theta and show that the walk converges in order constant/sin^2(theta) steps in the discrepancy metric. This is an application of techniques we develop for bounding the discrepancy of random walks on Gelfand pairs generated by bi-invariant measures. In such cases, Fourier analysis on the acting group admits tractable computations involving spherical functions. We advocate the use of discrepancy as a metric on probabilities for state spaces with isometric group actions.
20 pages; to appear in Electron. J. Probab.; related work at http://www.math.hmc.edu/~su/papers.html