Послідовність із низькою розбіжністю

Послідовність з низькою розбіжністю — послідовність, яка має таку властивість, що за всіх значень $n$ її підпослідовність $s_{1},...,s_{n}$ має низьку розбіжність.

Грубо кажучи, розбіжність послідовності невелика, якщо частка її елементів, що потрапляють у довільну множину $B$, близька до того, щоб бути пропорційною мірі множини $B$, як це відбувалося б у середньому (але не для конкретних вибірок) у разі рівномірно розподіленої послідовності. Конкретні визначення розбіжності різняться залежно від вибору множини $B$ (гіперсфери, гіперкуба тощо), а також від того, як ця розбіжність обчислена (зазвичай нормалізовано) і скомбінована (зазвичай шляхом взяття найгіршого значення) для кожної множини $B$.

Послідовності з низькою розбіжністю також називають квазівипадковими послідовностями через поширене їх використання як заміни рівномірно розподілених випадкових чисел. Префікс «квазі» використовується для точнішого позначення того, що значення послідовності з низькою розбіжністю не є ні випадковими, ні псевдовипадковими. Але, разом з тим, такі послідовності мають деякі властивості випадкових величин, і в певних застосуваннях, таких як метод квазі-Монте-Карло, їхня низька розбіжність є важливою перевагою.

Деякі застосування

Квазівипадкові числа мають перевагу перед суто випадковими числами в тому, що вони швидко й рівномірно охоплюють потрібну ділянку.

Одне з корисних застосувань полягає у знаходженні характеристичної функції для густини ймовірності. Квазівипадкові числа дозволяють досить швидко обчислювати з високою точністю моменти довільних порядків. Застосування, які не включають сортування, можна використати для знаходження середнього значення, стандартного відхилення, асиметрії та ексцесу статистичних розподілів, для знаходження інтегралів, а також глобальних максимумів та мінімумів складних детермінованих функцій. Квазівипадкові числа також можна використати для забезпечення початкових точок для детермінованих алгоритмів, які працюють тільки локально, таких як ітерація Ньютона — Рафсона.

Квазівипадкові числа також використовують у алгоритмах пошуку та сортування. За допомогою алгоритмів пошуку квазівипадкові числа можна використати в статистиці для знаходження моди, медіани, довірчих інтервалів та функцій розподілу.

Див. також

• Рівномірно розподілена послідовність

Література

• Кейперс Л., Нидеррайтер Г. Равномерное распределение последовательностей. — М. : Наука, 1985. — 408 с.