Convergence of random walks on the circle

generated by an irrational rotation

Author:
Francis Edward Su

Journal:
Trans. Amer. Math. Soc. **350** (1998), 3717-3741

MSC (1991):
Primary 60J15, 60B15; Secondary 11K38, 11J70

DOI:
https://doi.org/10.1090/S0002-9947-98-02152-7

MathSciNet review:
1467478

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Fix . Consider the random walk on the circle which proceeds by repeatedly rotating points forward or backward, with probability , by an angle . This paper analyzes the rate of convergence of this walk to the uniform distribution under ``discrepancy'' distance. The rate depends on the continued fraction properties of the number . We obtain bounds for rates when is any irrational, and a sharp rate when is a quadratic irrational. In that case the discrepancy falls as (up to constant factors), where is the number of steps in the walk. This is the first example of a sharp rate for a discrete walk on a continuous state space. It is obtained by establishing an interesting recurrence relation for the distribution of multiples of which allows for tighter bounds on terms which appear in the Erdös-Turán inequality.

**1.**D. Asimov,*The grand tour*, SIAM Jour. Sci. Statist. Comp.**6**(1983), 128-143. MR**86h:62087****2.**P. Diaconis,*Group Representations in Probability and Statistics*, Institute of Mathematical Statistics Lecture Notes, Vol. 11, Hayward, CA, 1988. MR**90a:60001****3.**P. Diaconis and L. Saloff-Coste,*Comparison Techniques for Random Walks on Finite Groups*, Ann. Probab.**21**(1993), 2131-2156. MR**95a:60009****4.**P. Erd\H{o}s and P. Turán,*On a problem in the theory of uniform distribution I*, Indag. Math.**10**(1948), 370-378. MR**10:372c****5.**B.M. Kloss,*Limiting distributions on bicompact topological groups*, Th. Probab. Appl.**4**(1959), 237-270.**6.**A.Ya. Khinchin,*Continued Fractions*, Univ. of Chicago Press, 1964. MR**28:5037****7.**L. Kuipers and H. Neiderreiter,*Uniform Distribution of Sequences*, Wiley, New York, 1974. MR**54:7415****8.**S. Lang,*Introduction to Diophantine Approximations*, Springer-Verlag, 1995. MR**96h:11067****9.**W.J. LeVeque,*An inequality connected with Weyl's criterion for uniform distribution*, Proc. Symp. Pure Math.**8**(1965), 22-30. MR**31:3401****10.**A. Lubotsky, R. Phillips, and P. Sarnak,*Hecke Operators and Distributing Points on the Sphere, I*, Comm. Pure. Appl. Math.**39**(1986), S149-S186. MR**88m:11025a****11.**J. Marsden,*Elementary Classical Analysis*, W.H. Freeman and Co., 1974. MR**50:10161****12.***Mathematica*, version 2. Wolfram Research, Inc., 1991.**13.**P. Matthews,*Covering problems for random walks on spheres and finite groups*, Ph.D. Thesis, Dept. of Statistics, Stanford Univ., 1985.**14.**H. Niederreiter and W. Philipp,*Berry-Esseen bounds and a theorem of Erd\H{o}s and Turán on uniform distribution mod 1*, Duke Math. J.**40**(1973), 633-649. MR**49:2642****15.**U. Porod,*The cut-off phenomenon for random reflections*, Ann. Probab.**24**(1996), 74-96. MR**97e:60012****16.**C. Radin,*The pinwheel tilings of the plane*, Annals of Math.**139**(1994), 661-702. MR**95d:52021****17.**E. Rains, personal communication, 1995.**18.**J.S. Rosenthal,*Random rotations: characters and random walks on*, Ann. Probab.**22**(1994), 398-423. MR**95c:60008****19.**W.M. Schmidt,*Diophantine Approximation*. Lecture Notes in Math. No. 785, Springer-Verlag, 1980. MR**81j:10038****20.**N.J.A. Sloane,*Encrypting by Random Rotations*, in*Cryptography*, Lecture Notes in Computer Science, no. 149. T.Beth, editor. Berlin, 1983. MR**85i:94017****21.**F.E. Su,*Methods for Quantifying Rates of Convergence for Random Walks on Groups*, Ph.D. Thesis, Harvard University, 1995.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (1991):
60J15,
60B15,
11K38,
11J70

Retrieve articles in all journals with MSC (1991): 60J15, 60B15, 11K38, 11J70

Additional Information

**Francis Edward Su**

Affiliation:
Department of Mathematics, Harvey Mudd College, Claremont, California 91711

Email:
su@math.hmc.edu

DOI:
https://doi.org/10.1090/S0002-9947-98-02152-7

Keywords:
Random walk,
rate of convergence,
discrepancy,
Erdös-Turán inequality,
continued fractions,
irrational rotation,
uniform distribution of sequences

Received by editor(s):
October 18, 1996

Additional Notes:
Supported in part by an NSF Graduate Fellowship

Article copyright:
© Copyright 1998
American Mathematical Society