Discrepancy Convergence for the Drunkard's Walk on the Sphere

Francis Edward Su (Harvey Mudd College)

Abstract


We analyze the drunkard's walk on the unit sphere with step size $\theta$ and show that the walk converges in order $C/\sin^2(\theta)$ steps in the discrepancy metric ($C$ a constant). This is an application of techniques we develop for bounding the discrepancy of random walks on Gelfand pairs generated by bi-invariant measures. In such cases, Fourier analysis on the acting group admits tractable computations involving spherical functions. We advocate the use of discrepancy as a metric on probabilities for state spaces with isometric group actions.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-20

Publication Date: February 19, 2001

DOI: 10.1214/EJP.v6-75

References

  1. Beck, J. and Chen, W. Irregularities of Distribution, Cambridge Univ. Press, Cambridge, 1987. Math. Reviews number MR88m:11061
  2. Bloom, W. R. and Heyer, H. Harmonic Analysis of Probability Measures on Hypergroups, Walter de Gruyter & Co., Berlin, 1995. deGruyter, Berlin, 1994. Math. Reviews number MR96a:43001
  3. Brocker, T. and tom Dieck, T. Representations of Compact Lie Groups. Springer-Verlag, 1985. Math. Reviews number MR86i:22023
  4. Diaconis, P. Group Representations in Probability and Statistics. IMS Lecture Notes-Monograph Series, vol. 11, 1988. Math. Reviews number MR90a:60001
  5. Diaconis, P. and Shahshahani, M. Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM J. Math. Analysis, 18 (1987), 208-218. Math. Reviews number MR88e:60014
  6. Dieudonne, J. Treatise on Analysis, vol. VI, Academic Press, 1978. Math. Reviews number MR58:29825b
  7. Dieudonne, J. Special Functions and Linear Representations of Lie Groups, CBMS Regional Conf. Ser., no. 42, AMS, 1980. Math. Reviews number MR81b:22002
  8. Drmota, M. and Tichy, R. F. Sequences, Discrepancies and Applications, Lecture Notes in Math. 1651, Springer-Verlag, Berlin, 1997. Math. Reviews number MR98j:11057
  9. Dym, H. and McKean, H. P. Fourier Series and Integrals, Academic Press, New York, 1972. Math. Reviews number MR56:945
  10. Gibbs, A.L. and Su, F. E. On choosing and bounding probability metrics, preprint. Math. Reviews number not available
  11. Greenhalgh, A. Random walks on groups with subgroup invariance properties. Ph.D. Thesis, Stanford University, 1987. Math. Reviews number not available
  12. Hensley, D. and Su, F. E. Random walks with badly approximable numbers, in Unusual Applications of Number Theory, M. Nathanson, ed., DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, to appear. Math. Reviews number not available
  13. Hewitt, E. and Ross, K. Abstract Harmonic Analysis, Vol. II. Springer-Verlag, 1970. Math. Reviews number MR41:7378
  14. Jackson, D. Fourier Series and Orthogonal Polynomials. The Carus Mathematical Monographs, No. 6. MAA, 1941. Math. Reviews number MR3:230f
  15. Letac, G. Problemès classiques de probabilité sur un couple de Gelfand. pp. 93-120, Lecture Notes in Math., no. 861, Springer-Verlag, 1981. Math. Reviews number MR83k:60019
  16. L. Kuipers and H. Neiderreiter, Uniform Distribution of Sequences, Wiley, New York, 1974. Math. Reviews number MR54:7415
  17. Porod, U. Time to stationarity for random walks on compact Lie groups. Ph.D. Thesis, Division of Math. Sciences, Johns Hopkins University, 1993. Math. Reviews number not available
  18. Porod, U. The cutoff phenomenon for random reflections, Ann. Probab. 24, (1996), 74-96. Math. Reviews number MR97e:60012
  19. Rosenthal, J. S. Random rotations: characters and random walks on SO(n). Ann. Probab., 22, (1994), 398-423. Math. Reviews number MR95c:60008
  20. Su, F. E. Methods for quantifying rates of convergence for random walks on groups. Ph.D. Thesis, Harvard University, 1995. Math. Reviews numbernot available
  21. Su, F. E. Convergence of random walks on the circle generated by an irrational rotation. Trans. Amer. Math. Soc., 350, (1998), 3717-3741. Math. Reviews number MR98k:60120
  22. Su, F. E. A LeVeque-type lower bound for discrepancy, in Monte Carlo and Quasi-Monte Carlo Methods 1998, H. Niederreiter and J. Spanier, eds., Springer-Verlag, 2000, 448-458. Math. Reviews number not available
  23. Voit, M. A central limit theorem for isotropic random walks on n-spheres for n -> infinity, J. Math. Anal. Appl. 189 (1995), 215-224. Math. Reviews number MR96e:60016
  24. Voit, M. Limit theorems for compact two-point homogeneous spaces of large dimensions, J. Theoret. Probab., a 9(1996), 353-370. Math. Reviews number MR98g:43001
  25. Voit, M. Rate of convergence to Gaussian measures on n-spheres and Jacobi Hypergroups, Ann. Probab., 25 (1997), 457-477. Math. Reviews number MR98f:60138
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.