Random walks with badly approximable numbers

2001/02/27 by Doug Hensley, Francis Edward Su
Mathematics · #math.PR #math.NT #msc:60B15 #msc:11J13 #msc:11K38 #msc:11K60

paper · pdf

published as DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 64 (2004), 95-101. · 7 pages; to appear in DIMACS volume "Unusual Applications of Number Theory"; related work at http://www.math.hmc.edu/~su/papers.html

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

Abstract

Using the discrepancy metric, we analyze the rate of convergence of a random walk on the circle generated by d rotations, and establish sharp rates that show that badly approximable d-tuples in R^d give rise to walks with the fastest convergence. We use the discrepancy metric because the walk does not converge in total variation. For badly approximable d-tuples, the discrepancy is bounded above and below by (constant)k^(-d/2), where k is the number of steps in the random walk. We show how the constants depend on the d-tuple.

Related

• Random walks on the torus with several generators
• Discrepancy convergence for the drunkard's walk on the sphere
• Invariant measures and error bounds for random walks in the quarter-plane based on sums of geometric terms
• Random walks with different directions: Drunkards beware !
• Simulating a Random Walk with Constant Error