Probability Commons^™

Discrepancy Convergence For The Drunkard's Walk On The Sphere, Francis E. Su

All HMC Faculty Publications and Research

We analyze the drunkard's walk on the unit sphere with step size θ and show that the walk converges in order C/sin²(θ) steps in the discrepancy metric (C a constant). 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.