Discrepancy Convergence for the Drunkard's Walk on the Sphere

Authors

Francis E. Su, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

2-2001

Abstract

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.

Rights Information

© 2001 Francis Su

Terms of Use & License Information

This work is licensed under a Creative Commons Attribution 3.0 License.

DOI

10.1214/EJP.v6-75

Recommended Citation

Francis Edward Su. Discrepancy convergence for the drunkard's walk on the sphere. Electron. J. Probab., 6:no. 2, 20 pp. (electronic), 2001.