Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Discrepancy (5)
- Random walk (4)
- Bounds (2)
- Probability (2)
- Best choice (1)
-
- Coin flipping (1)
- Continued fractions (1)
- Controllability (1)
- Cootie (1)
- Erdös-Turán inequality (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)
- Probabilistic simple temporal networks (1)
- Probability metrics (1)
- Prokhorov metric (1)
- Rate of convergence (1)
- Rates of convergence (1)
- Relative entropy (1)
- Scheduling (1)
- Simple temporal networks with uncertainty (1)
- Temporal planning (1)
- Uniform distribution of sequences (1)
- Wasserstein distance (1)
Articles 1 - 9 of 9
Full-Text Articles in Probability
Quantifying Controllability In Temporal Networks With Uncertainty, James C. Boerkoel Jr., Lindsay Popowski, Michael Gao, Hemeng Li, Savana Ammons, Shyan Akmal
Quantifying Controllability In Temporal Networks With Uncertainty, James C. Boerkoel Jr., Lindsay Popowski, Michael Gao, Hemeng Li, Savana Ammons, Shyan Akmal
All HMC Faculty Publications and Research
Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We provide new insights inspired by a geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability - continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods …
Dynamic Control Of Probabilistic Simple Temporal Networks, James C. Boerkoel Jr., Michael Gao, Lindsay Popowski
Dynamic Control Of Probabilistic Simple Temporal Networks, James C. Boerkoel Jr., Michael Gao, Lindsay Popowski
All HMC Faculty Publications and Research
The controllability of a temporal network is defined as an agent’s ability to navigate around the uncertainty in its schedule and is well-studied for certain networks of temporal constraints. However, many interesting real-world problems can be better represented as Probabilistic Simple Temporal Networks (PSTNs) in which the uncertain durations are represented using potentially-unbounded probability density functions. This can make it inherently impossible to control for all eventualities. In this paper, we propose two new dynamic controllability algorithms that attempt to maximize the likelihood of successfully executing a schedule within a PSTN. The first approach, which we call MIN-LOSS DC, finds …
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.
What's Best?, Arthur T. Benjamin, Matthew T. Fluet '99
What's Best?, Arthur T. Benjamin, Matthew T. Fluet '99
All HMC Faculty Publications and Research
No abstract provided in this article.
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.
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 …