Random sampling: billiard walk algorithm

DOI10.1016/J.EJOR.2014.03.041zbMATH Open1338.60190arXiv1211.3932OpenAlexW2104963735MaRDI QIDQ296789FDOQ296789

Authors: Elena Gryazina, Boris T. Polyak 

Publication date: 23 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1211.3932

Recommendations

• Hit-and-run mixes fast
• Hit-and-Run from a Corner
• Convergence properties of hit–and–run samplers
• Stochastic Billiards for Sampling from the Boundary of a Convex Set
• Super-uniformity of the typical billiard path

zbMATH Keywords

samplingMonte-Carlo methodbilliardshit-and-run

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Markov chain Monte Carlo revolution
• Simulation and the Monte Carlo Method
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Title not available (Why is that?)
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Dynamical systems with elastic reflections
• Stochastic billiards on general tables
• Hit-and-run enables efficient weight generation for simulation-based multiple criteria decision analysis
• A randomized cutting plane method with probabilistic geometric convergence
• Stochastic Billiards for Sampling from the Boundary of a Convex Set
• Hit-and-run from a corner
• BILLIARD TRAJECTORIES IN A POLYHEDRAL ANGLE
• Shake-and-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra
• Computational results of an \(O^{\ast }(n^{4})\) volume algorithm
• Title not available (Why is that?)
• On the Computation of Multidimensional Integrals by the Monte-Carlo Method
• Randomized methods based on new Monte Carlo schemes for control and optimization

Cited In (9)

• Approximate methods for solving chance-constrained linear programs in probability measure space
• A general purpose sampling algorithm for continuous distributions (the t-walk)
• Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo
• Investigation of feasible and marginal operating regimes of electric power systems
• Mixed robustness: analysis of systems with uncertain deterministic and random parameters by the example of linear systems
• Short-run characteristics of samples drawn by random walks
• Billiard walk
• Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies
• Super-uniformity of the typical billiard path

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)