Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Discrepancy (5)
- Random walk (4)
- Probability (3)
- Bounds (2)
- Blackjack (1)
-
- Boolean (1)
- Chemical Engineering (1)
- Continued fractions (1)
- Cootie (1)
- Counting Cards (1)
- Erdös-Turán inequality (1)
- Expected Value (1)
- Expected time (1)
- Gelfand pairs (1)
- Haar measure (1)
- Hellinger distance (1)
- Homogeneous spaces (1)
- Irrational rotation (1)
- Kronecker sequences (1)
- LeVeque (1)
- Legendre polynomials (1)
- Noise (1)
- Numerical solution (1)
- Probability metrics (1)
- Prokhorov metric (1)
- Rate of convergence (1)
- Rates of convergence (1)
- Relative entropy (1)
- Systems (1)
- Theory of Computation (1)
Articles 1 - 9 of 9
Full-Text Articles in Statistics and 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 Rational Solution To Cootie, Arthur T. Benjamin, Matthew T. Fluet '99
A Rational Solution To Cootie, Arthur T. Benjamin, Matthew T. Fluet '99
All HMC Faculty Publications and Research
No abstract provided in this article.
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.
Why The Player Never Wins In The Long Run At La Blackjack, Arthur T. Benjamin, Michael Lauzon '00, Christopher Moore '00
Why The Player Never Wins In The Long Run At La Blackjack, Arthur T. Benjamin, Michael Lauzon '00, Christopher Moore '00
All HMC Faculty Publications and Research
No abstract provided in this article.
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 …
Optimization In Chemical Kinetics, Arthur T. Benjamin, Gordon J. Hogenson '92
Optimization In Chemical Kinetics, Arthur T. Benjamin, Gordon J. Hogenson '92
All HMC Faculty Publications and Research
No abstract provided in this article.
Reliable Computation In The Presence Of Noise, Nicholas Pippenger
Reliable Computation In The Presence Of Noise, Nicholas Pippenger
All HMC Faculty Publications and Research
This talk concerns computation by systems whose components exhibit noise (that is, errors committed at random according to certain probabilistic laws). If we aspire to construct a theory of computation in the presence of noise, we must possess at the outset a satisfactory theory of computation in the absence of noise.
A theory that has received considerable attention in this context is that of the computation of Boolean functions by networks (with perhaps the strongest competition coming from the theory of cellular automata; see [G] and [GR]). The theory of computation by networks associates with any two sets Q and …