Convergence of random walks on the circle generated by an irrational rotation
10.1090/s0002-9947-98-02152-7
Crossref journal-article
American Mathematical Society (AMS)
Transactions of the American Mathematical Society (14)
Abstract

Fix α ∈ [ 0 , 1 ) \alpha \in [0,1) . Consider the random walk on the circle S 1 S^1 which proceeds by repeatedly rotating points forward or backward, with probability 1 2 \frac 12 , by an angle 2 π α 2\pi \alpha . 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 ξ = 2 α \xi =2\alpha . We obtain bounds for rates when ξ \xi is any irrational, and a sharp rate when ξ \xi is a quadratic irrational. In that case the discrepancy falls as k − 1 2 k^{-\frac 12} (up to constant factors), where k k 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 ξ \xi which allows for tighter bounds on terms which appear in the Erdős-Turán inequality.

Bibliography

Su, F. (1998). Convergence of random walks on the circle generated by an irrational rotation. Transactions of the American Mathematical Society, 350(9), 3717–3741. Portico.

Authors 1
  1. Francis Su (first)
References 21 Referenced 11
  1. 10.1137/0906011 / SIAM J. Sci. Statist. Comput. / The grand tour: a tool for viewing multidimensional data by Asimov, Daniel (1985)
  2. 10.1007/BFb0086177 / Group representations in probability and statistics / Institute of Mathematical Statistics Lecture Notes---Monograph Series by Diaconis, Persi (1988)
  3. {'issue': '4', 'key': '3', 'first-page': '2131', 'article-title': 'Comparison techniques for random walk on finite groups', 'volume': '21', 'author': 'Diaconis, Persi', 'year': '1993', 'journal-title': 'Ann. Probab.', 'ISSN': 'http://id.crossref.org/issn/0091-1798', 'issn-type': 'print'} / Ann. Probab. / Comparison techniques for random walk on finite groups by Diaconis, Persi (1993)
  4. 10.2307/2371336 / Amer. J. Math. / Ring homomorphisms which are also lattice homomorphisms by Ward, Morgan (1939)
  5. B.M. Kloss, Limiting distributions on bicompact topological groups, Th. Probab. Appl. 4(1959), 237-270. (10.1137/1104026)
  6. {'key': '6', 'volume-title': 'Continued fractions', 'author': 'Khinchin, A. Ya.', 'year': '1964'} / Continued fractions by Khinchin, A. Ya. (1964)
  7. {'key': '7', 'series-title': 'Pure and Applied Mathematics', 'volume-title': 'Uniform distribution of sequences', 'author': 'Kuipers, L.', 'year': '1974'} / Uniform distribution of sequences / Pure and Applied Mathematics by Kuipers, L. (1974)
  8. 10.1007/978-1-4612-4220-8 / Introduction to Diophantine approximations by Lang, Serge (1995)
  9. {'key': '9', 'first-page': '22', 'article-title': 'An inequality connected with Weyl’s criterion for uniform distribution', 'author': 'Leveque, W. J.', 'year': '1965'} / An inequality connected with Weyl’s criterion for uniform distribution by Leveque, W. J. (1965)
  10. 10.1002/cpa.3160390710 / Comm. Pure Appl. Math. / Hecke operators and distributing points on the sphere. I by Lubotzky, A. (1986)
  11. {'key': '11', 'volume-title': 'Elementary classical analysis', 'author': 'Marsden, Jerrold E.', 'year': '1974'} / Elementary classical analysis by Marsden, Jerrold E. (1974)
  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. 10.1215/S0012-7094-73-04055-6 / Duke Math. J. / Berry-Esseen bounds and a theorem of Erdős and Turán on uniform distribution 𝑚𝑜𝑑1 by Niederreiter, H. (1973)
  15. 10.1214/aop/1042644708 / Ann. Probab. / The cut-off phenomenon for random reflections by Porod, Ursula (1996)
  16. 10.2307/2118575 / Ann. of Math. (2) / The pinwheel tilings of the plane by Radin, Charles (1994)
  17. E. Rains, personal communication, 1995.
  18. {'issue': '1', 'key': '18', 'first-page': '398', 'article-title': 'Random rotations: characters and random walks on 𝑆𝑂(𝑁)', 'volume': '22', 'author': 'Rosenthal, Jeffrey S.', 'year': '1994', 'journal-title': 'Ann. Probab.', 'ISSN': 'http://id.crossref.org/issn/0091-1798', 'issn-type': 'print'} / Ann. Probab. / Random rotations: characters and random walks on 𝑆𝑂(𝑁) by Rosenthal, Jeffrey S. (1994)
  19. {'key': '19', 'series-title': 'Lecture Notes in Mathematics', 'isbn-type': 'print', 'volume-title': 'Diophantine approximation', 'volume': '785', 'author': 'Schmidt, Wolfgang M.', 'year': '1980', 'ISBN': 'http://id.crossref.org/isbn/3540097627'} / Diophantine approximation / Lecture Notes in Mathematics by Schmidt, Wolfgang M. (1980)
  20. 10.1007/3-540-39466-4_6 / Encrypting by random rotations by Sloane, N. J. A. (1983)
  21. F.E. Su, Methods for Quantifying Rates of Convergence for Random Walks on Groups, Ph.D. Thesis, Harvard University, 1995.
Dates
Type When
Created 23 years, 1 month ago (July 26, 2002, 6:17 p.m.)
Deposited 3 years, 9 months ago (Dec. 6, 2021, 9:35 a.m.)
Indexed 1 year, 1 month ago (July 9, 2024, 11:10 p.m.)
Issued 27 years, 8 months ago (Jan. 1, 1998)
Published 27 years, 8 months ago (Jan. 1, 1998)
Published Online 27 years, 8 months ago (Jan. 1, 1998)
Funders 0

None

@article{Su_1998, title={Convergence of random walks on the circle generated by an irrational rotation}, volume={350}, ISSN={1088-6850}, url={http://dx.doi.org/10.1090/s0002-9947-98-02152-7}, DOI={10.1090/s0002-9947-98-02152-7}, number={9}, journal={Transactions of the American Mathematical Society}, publisher={American Mathematical Society (AMS)}, author={Su, Francis}, year={1998}, pages={3717–3741} }