Random walks on the torus with several generators

2003/09/30 by Timothy Prescott, Francis Edward Su
Mathematics · #math.PR #msc:60B15 #msc:11J13 #msc:11K38

paper · pdf · doi:10.1002/rsa.20029

published as Random Structures and Algorithms 25 (2004), 336-345. · 10 pages; related work at http://www.math.hmc.edu/~su/papers.html

arxiv created 2004/04/27 · arxiv updated 2009/12/01

Abstract

Our paper gives bounds for the rate of convergence for a class of random walks on the d-dimensional torus generated by a set of n vectors in R^d/Z^d. We give bounds on the discrepancy distance from Haar measure; our lower bound holds for all such walks, and if the generators arise from the rows of a "badly approximable" matrix, then there is a corresponding upper bound. The bounds are sharp for walks on the circle.

Related

• Random walks with badly approximable numbers
• Loop-erased random walk on a torus in dimensions 4 and above
• Linear random walks on the torus
• Central limit theorem and law of the iterated logarithm for the linear random walk on the torus
• Affine random walks on the torus