Abstract: Hit-and-Run is known to be one of the best random sampling algorithms, its mixing time is polynomial in dimension. Nevertheless, in practice the number of steps required to achieve uniformly distributed samples is rather high. We propose new random walk algorithm based on billiard trajectories. Numerical experiments demonstrate much faster convergence to uniform distribution.
Recommendations
Cites work
- scientific article; zbMATH DE number 47098 (Why is no real title available?)
- scientific article; zbMATH DE number 525209 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 840151 (Why is no real title available?)
- A random polynomial-time algorithm for approximating the volume of convex bodies
- A randomized cutting plane method with probabilistic geometric convergence
- BILLIARD TRAJECTORIES IN A POLYHEDRAL ANGLE
- Computational results of an \(O^{\ast }(n^{4})\) volume algorithm
- Dynamical systems with elastic reflections
- Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
- Hit-and-run enables efficient weight generation for simulation-based multiple criteria decision analysis
- Hit-and-run from a corner
- On the Computation of Multidimensional Integrals by the Monte-Carlo Method
- Random walks in a convex body and an improved volume algorithm
- Randomized methods based on new Monte Carlo schemes for control and optimization
- Shake-and-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra
- Simulation and the Monte Carlo Method
- Stochastic Billiards for Sampling from the Boundary of a Convex Set
- Stochastic billiards on general tables
- The Markov chain Monte Carlo revolution
Cited in
(9)- Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies
- Mixed robustness: analysis of systems with uncertain deterministic and random parameters by the example of linear systems
- Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo
- Short-run characteristics of samples drawn by random walks
- Investigation of feasible and marginal operating regimes of electric power systems
- Approximate methods for solving chance-constrained linear programs in probability measure space
- Super-uniformity of the typical billiard path
- A general purpose sampling algorithm for continuous distributions (the t-walk)
- Billiard walk
This page was built for publication: Random sampling: billiard walk algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q296789)
