Discrepancy convergence for the drunkard's walk on the sphere
Abstract
Description
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
20 pages; to appear in Electron. J. Probab.; related work at http://www.math.hmc.edu/~su/papers.html