Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 5 of 5
Full-Text Articles in Probability
Random Walks On The Torus With Several Generators, Timothy Prescott '02, Francis E. Su
Random Walks On The Torus With Several Generators, Timothy Prescott '02, Francis E. Su
All HMC Faculty Publications and Research
Given n vectors {i} ∈ [0, 1)d, consider a random walk on the d-dimensional torus d = ℝd/ℤd generated by these vectors by successive addition and subtraction. For certain sets of vectors, this walk converges to Haar (uniform) measure on the torus. We show that the discrepancy distance D(Q*k) between the kth step distribution of the walk and Haar measure is bounded below by D(Q*k) ≥ C1k−n/2, where C1 = C(n, d) is …
On Choosing And Bounding Probability Metrics, Alison L. Gibbs, Francis E. Su
On Choosing And Bounding Probability Metrics, Alison L. Gibbs, Francis E. Su
All HMC Faculty Publications and Research
When studying convergence of measures, an important issue is the choice of probability metric. We provide a summary and some new results concerning bounds among some important probability metrics/distances that are used by statisticians and probabilists. Knowledge of other metrics can provide a means of deriving bounds for another one in an applied problem. Considering other metrics can also provide alternate insights. We also give examples that show that rates of convergence can strongly depend on the metric chosen. Careful consideration is necessary when choosing a metric.
Discrepancy Convergence For The Drunkard's Walk On The Sphere, Francis E. Su
Discrepancy Convergence For The Drunkard's Walk On The Sphere, Francis E. Su
All HMC Faculty Publications and Research
We analyze the drunkard's walk on the unit sphere with step size θ and show that the walk converges in order C/sin2(θ) 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.
A Leveque-Type Lower Bound For Discrepancy, Francis E. Su
A Leveque-Type Lower Bound For Discrepancy, Francis E. Su
All HMC Faculty Publications and Research
A sharp lower bound for discrepancy on R / Z is derived that resembles the upper bound due to LeVeque. An analogous bound is proved for discrepancy on Rk / Zk. These are discussed in the more general context of the discrepancy of probablity measures. As applications, the bounds are applied to Kronecker sequences and to a random walk on the torus.
Convergence Of Random Walks On The Circle Generated By An Irrational Rotation, Francis E. Su
Convergence Of Random Walks On The Circle Generated By An Irrational Rotation, Francis E. Su
All HMC Faculty Publications and Research
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 …