Random sampling: billiard walk algorithm

DOI10.1016/J.EJOR.2014.03.041zbMATH Open1338.60190OpenAlexW2104963735MaRDI 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

• Approximate methods for solving chance-constrained linear programs in probability measure space
• A general purpose sampling algorithm for continuous distributions (the t-walk)
• Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies
• 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
• 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)