Discrepancy Convergence For The Drunkard's Walk On The Sphere

• Main Author: Francis Edward Su
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2000
• Subjects: Consider the following random walk on the sphere S; North Pole
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8829; http://www.math.hmc.edu/~su/papers.dir/drunkard.ps

. Fix an angle `, and consider the random walk on S 2 that starts at the north pole, and at each step moves by an angle ` in any uniformly chosen direction. We show that C sin 2 ` steps are necessary and sufficient to make the discrepancy distance from the uniform distribution small. Methods are derived for handling the discrepancy of random walks on arbitrary Gelfand pairs generated by bi-invariant measures. 1. Introduction Consider the following random walk on the sphere S 2 . Fix an angle `, measured from the center of the sphere. The random walk starts at the north pole, and at each step moves along the surface of the sphere by an angle ` in any uniformly chosen direction from the current position (hence mimicking the behavior of a "drunkard"). In this paper, we derive sharps rate of convergence for this walk under the discrepancy metric for measures on S 2 . This metric metrizes weak-* convergence of measures on S 2 . We show that C sin 2 ` steps are both necessar.