Discrepancy convergence for the drunkard's walk on the sphere

2001/02/27 by Francis Edward Su
Mathematics · #math.PR #math.RT #msc:60B15 #msc:43A85

paper · pdf

published as Electronic Journal of Probability 6 (2001) no. 2, 1-20. · 20 pages; to appear in Electron. J. Probab.; related work at http://www.math.hmc.edu/~su/papers.html

arxiv created 2001/02/27 · arxiv updated 2009/11/30

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²(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.

Related

• Random walks with badly approximable numbers
• Spectral decomposition of discrepancy kernels on the Euclidean ball, the special orthogonal group, and the Grassmannian manifold
• Random walks with different directions: Drunkards beware !
• On random walks and switched random walks on homogeneous spaces
• Random walks and contracting elements I: Deviation inequality and Limit laws