Conference publications

Abstracts

XX conference

Billiard walk – new sampling algorithm

Gryazina E., Polyak B.

Institute for Control Sciences RAS, 65, Profsoyuznaya st., Moscow, 117997, Russia, +7 (495) 334 7641, gryazina@gmail.com

Generating points uniformly distributed in an arbitrary bounded (measurable) region $Q\in R^n$ (sampling) finds applications in many computational problems. Among most common it is worth mentioning multidimensional integration, volume estimation and calculation of the center of gravity. However these problems are trivial for simple sets, in general they remain hard. Straightforward sampling techniques are usually based on one of three approaches: rejection, transformation and composition. The other sampling procedures use modern versions of Monte Carlo technique, based on Markov Chain Monte Carlo (MCMC) approach. One of the most famous and effective algorithms of this type is Hit-and-Run. However the results are unsatisfactory for “bad” sets, such as level sets of ill-posed functions. Here we propose new random walk algorithm – Billiard Walk – based on billiard trajectories. The algorithm combines ideas of Hit-and-Run technique with ergodic properties of billiards. A mathematical billiard consist of a domain (a billiard table) and a point-mass that moves inside the domain along a straight line until it hits the boundary, reflects subject to a law: the angle of incidence equals the angle of reflection and continues its motion infinitely.

Algorithm of Billiard Walk

1. Starting point $x^0 \in IntQ$ is given; $i = 0$, $x = x^0$.

2. Generate the length of the trajectory $\ell = –\tau \text{log} \xi$, $\xi$ being uniform random in [0,1], $\tau$ is a specified parameter of the algorithm.

3. Pick random direction $d\in R^n$ uniformly distributed on the unit sphere. Construct billiard trajectory starting at $x^i$ and with initial direction $d = d^i$. When the trajectory meets a boundary with internal normal $s$, $||s|| = 1$ the direction is changed as

$$d \rightarrow d – 2(d,s)s.$$

4. Calculate the end of the trajectory of length $\ell$. If the point with nonsmooth boundary is met or the number of reflections exceeds 10n go to step 3.

5. $i = i+1$, take the end point as $x^{i+1}$ and go to step 2.

Billiard Walk is applicable for sampling in nonconvex domains and domains described by linear matrix inequalities. Numerical tests demonstrate much faster convergence to uniform distribution for Billiard Walk compare to Hit-and-Run.

• view as PDF (in English) (PDF)