Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mce.biophys.msu.ru/archive/doc174331/eng.pdf Дата изменения: Sat Mar 22 23:53:23 2014 Дата индексирования: Sat Mar 22 23:53:23 2014 Кодировка:

BILLIARD WALK ­ NEW SAMPLING ALGORITHM Gryazina E. 1, Polyak B.
1

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 QR (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 [1]. One of the most famous and effective algorithms of this type is Hit-and-Run [2]. 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 x0 IntQ is given; i = 0, x = x0. 2. Generate the length of the trajectory l = ­ log , being uniform random in [0,1], is a specified parameter of the algorithm. 3. Pick random direction dRn uniformly distributed on the unit sphere. Construct billiard trajectory starting at xi and with initial direction d = di. When the trajectory meets a boundary with internal normal s, ||s|| = 1 the direction is changed as d d ­ 2(d,s)s.
n

4. Calculate the end of the trajectory of length l. 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 xi+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. References 1. Diaconis P. The Markov chain Monte Carlo revolution // Bull. Of the AMS Vol. 46, No. 2, 2009. Pp. 175-205. 2. Smith R. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions // Operations Research Vol. 32, No. 6, 1984. Pp. 1296-1308.