§5. Равномерность по Вейлю: ровно, но без жребия

Метод Монте-Карло кидает случайные точки. Но возникает дерзкая мысль: а обязательно ли случайные? Что, если взять специальную неслучайную последовательность, которая заполняет отрезок так же ровно, как настоящий жребий, — и получить плюсы без возни со случайностью?

Оказывается, можно. Это понятие называется равномерностью по Вейлю.

Что значит «ровно заполняет»

Определение. Последовательность чисел $x_1, x_2, \dots$ из $[0,1]$ называется равномерной по Вейлю, если для любого отрезка $[a,b] \subseteq [0,1]$ частота попаданий в него стремится к его длине $b - a$ (при $n \to \infty$).

По-простому: куда ни ткни отрезок — доля точек, попавших в него, равна его длине. Нет любимых мест, нет пустот. Это ровно то поведение, которого мы ждём от честного равномерного датчика (и по закону больших чисел настоящие случайные равномерные числа этим свойством обладают с вероятностью 1).

Теорема Вейля: дробные части спасают

А вот и способ построить такую последовательность без всякой случайности:

Теорема (Вейль). Пусть $x_n = \{\alpha n\}$, где $\{\,\cdot\,\}$ — дробная часть числа, а $\alpha$ — любое иррациональное число. Тогда $x_1, x_2, \dots$ равномерна по Вейлю.

Разбираем по кирпичикам:

• $\{\,\cdot\,\}$ — дробная часть: отбрасываем целое, оставляем хвост после запятой ($\{3{,}71\} = 0{,}71$).
• $\{\alpha n\}$ — берём $\alpha$, умножаем на $n$, оставляем дробную часть. Шагаем по кругу $[0,1]$ шагом $\alpha$: дошёл до края — продолжил с другой стороны.
• Фишка в иррациональности $\alpha$: шаг никогда не укладывается ровно, поэтому точки не зацикливаются, а постепенно затыкают все дырки, распределяясь равномерно.

Если же $\alpha$ рациональное — всё ломается: шаг укладывается, последовательность зацикливается и бьёт лишь в несколько точек. Покрути виджет — сравни иррациональные ($\sqrt2$, $\pi$, золотое сечение) с рациональным $1/4$:

Зачем это надо: квази-Монте-Карло

Главная выгода: равномерную по Вейлю последовательность можно подставить вместо случайной в формулу интегрирования, и среднее всё равно сойдётся к интегралу:

Это называют квази-Монте-Карло: считаем жребий-методом, но точки берём не случайные, а хитрые детерминированные — и часто сходимся даже быстрее. Чистый выигрыш.

Подвох: одномерного мало

Но есть засада, прямо связанная с §4. Нельзя просто взять одну вейлевскую последовательность и нарезать её на пары $(x_1,x_2), (x_3,x_4), \dots$, чтобы заполнить квадрат — пары лягут на кривую, а не размажутся по площади (это мы докажем в задачах). Для многомерия нужна вполне равномерность: чтобы ровно ложились не только точки, но и их группы по $k$ штук в $k$-мерном кубе.

Красивый пример вполне равномерной последовательности — число Шампернауна:

— его знаки после запятой это просто подряд выписанные натуральные числа. У него любая группа из $k$ цифр встречается с частотой $\to 10^{-k}$ (а вот обладают ли этим свойством цифры $\pi$ и $e$ — до сих пор неизвестно).

Важная оговорка: вполне равномерность — свойство асимптотическое, про бесконечный хвост. Конечный кусок можно как угодно испортить (хоть все первые миллион членов занулить) — на итог это не влияет, но для коротких расчётов такую порчу надо держать в уме.

Проверь себя