24 февраля 2014 г.

   Е.Н.  Грязина (ИПУ РАН, Москва)

"Случайные блуждания в ограниченных областях для получения асимптотически равномерно распределённых точек"

      Рассматриваются методы генерации последовательностей точек, асимптотически равномерно заполняющие заданную область в Rⁿ. Предложен новый метод бильярдного блуждания (Billiard Walk). В основе метода лежит кинетическая модель идеального газа, равномерно заполняющего заданный объем. Отражение от границ области происходит по правилам геометрической оптики. Такие траектории описываются в рамках теории математических бильярдов, что объясняет название метода. В бильярдную траекторию вносится случайность, а именно, достигнув определенной длины, траектория прерывается, а далее продолжается в случайном направлении.

       Доказано, что метод бильярдного блуждания порождает множество точек, асимптотически равномерно распределенных в сложных областях. Область предполагается связной и имеющей кусочно-гладкую границу, для невыпуклых областей дополнительно требуется выполнение ограничения на минимальное число звеньев ломаной, соединяющей две произвольные точки области.

       Численные эксперименты подтверждают предположение о более быстрой скорости сходимости к равномерному распределению по сравнению с другими известными методами, основанными на марковских цепях – в частности, с методом  Hit-and-Run. Рассмотрены типовые области – как выпуклые (куб, симплекс), так и невыпуклые (тороид), для которых сравнение с равномерным распределением можно провести со всей наглядностью.

Наверх