Равнораспределенная последовательность - Equidistributed sequence

В математика, а последовательность (s₁, s₂, s₃, ...) из действительные числа как говорят равнораспределенный, или равномерно распределены, если доля терминов, попадающих в подынтервал, пропорциональна длине этого подынтервала. Такие последовательности изучаются в Диофантово приближение теории и имеют приложения к Интеграция Монте-Карло.

Определение

Последовательность (s₁, s₂, s₃, ...) из действительные числа как говорят равнораспределенный на невырожденном интервал [а, б] если для любого подынтервала [c, d ] из [а, б] у нас есть

${\displaystyle \lim _{n\to \infty }{\left|\{\,s_{1},\dots ,s_{n}\,\}\cap [c,d]\right| \over n}={d-c \over b-a}.}$

(Здесь обозначение | {s₁,...,s_п} ∩ [c, d ] | обозначает количество элементов из первого п элементы последовательности, находящиеся между c и d.)

Например, если последовательность равнораспределена в [0, 2], поскольку интервал [0,5, 0,9] занимает 1/5 длины интервала [0, 2], как п становится больше, доля первых п члены последовательности от 0,5 до 0,9 должны приближаться к 1/5. Грубо говоря, можно сказать, что каждый член последовательности с одинаковой вероятностью попадет в любую точку своего диапазона. Однако это не означает, что (s_п) представляет собой последовательность случайные переменные; скорее, это определенная последовательность действительных чисел.

Несоответствие

Мы определяем несоответствие D_N для последовательности (s₁, s₂, s₃, ...) относительно интервала [а, б] так как

${\displaystyle D_{N}=\sup _{a\leq c\leq d\leq b}\left\vert {\frac {\left|\{\,s_{1},\dots ,s_{N}\,\}\cap [c,d]\right|}{N}}-{\frac {d-c}{b-a}}\right\vert .}$

Таким образом, последовательность является равнораспределенной, если невязка D_N стремится к нулю как N стремится к бесконечности.

Равнораспределение - довольно слабый критерий для выражения того факта, что последовательность заполняет сегмент без пропусков. Например, рисунки случайной величины, однородной по сегменту, будут равномерно распределены в сегменте, но будут большие промежутки по сравнению с последовательностью, которая сначала перечисляет кратные ε в сегменте для некоторого малого ε соответствующим образом выбранным способом. , а затем продолжает делать это для все меньших и меньших значений ε. Более строгие критерии и конструкции последовательностей, которые распределены более равномерно, см. последовательность с низким расхождением.

Интегральный критерий Римана для равнораспределения

Напомним, что если ж это функция иметь Интеграл Римана в интервале [а, б], то его интеграл является пределом Суммы Римана взято путем выборки функции ж в набор точек, выбранных из тонкого разбиения интервала. Следовательно, если некоторая последовательность равнораспределена в [а, б], ожидается, что эту последовательность можно использовать для вычисления интеграла от интегрируемой по Риману функции. Это приводит к следующему критерию^[1] для равнораспределенной последовательности:

Предположим (s₁, s₂, s₃, ...) - последовательность, содержащаяся в интервале [а, б]. Тогда следующие условия эквивалентны:

1. Последовательность равнораспределена на [а, б].
2. Для всякого интегрируемого по Риману (комплексный ) функция ж : [а, б] → ℂ имеет место следующий предел:

${\displaystyle \lim _{N\to \infty }{\frac {1}{N}}\sum _{n=1}^{N}f\left(s_{n}\right)={\frac {1}{b-a}}\int _{a}^{b}f(x)\,dx}$

Доказательство

Прежде всего отметим, что определение равнораспределенной последовательности эквивалентно интегральному критерию всякий раз, когда ж это индикаторная функция интервала: Если ж = 1[c, d], то левая часть - это доля точек последовательности, попадающих в интервал [c, d], а правая часть в точности равна ${\displaystyle \textstyle {\frac {d-c}{b-a}}.}$ Это означает 2 ⇒ 1 (поскольку индикаторные функции интегрируемы по Риману) и 1 ⇒ 2 для ж являясь индикаторной функцией интервала. Осталось предположить, что интегральный критерий выполняется для индикаторных функций, и доказать, что он верен и для общих функций, интегрируемых по Риману. Отметим, что обе части интегрального критериального уравнения равны линейный в ж, а значит, критерий выполняется для линейные комбинации интервальных индикаторов, то есть пошаговые функции. Чтобы показать, что это справедливо для ж будучи общей интегрируемой по Риману функцией, сначала предположим ж имеет реальную ценность. Затем, используя Определение Дарбу интеграла для любого ε> 0 имеем две ступенчатые функции ж1 и ж2 такой, что ж1 ≤ ж ≤ ж2 и ${\displaystyle \textstyle \int _{a}^{b}(f_{2}(x)-f_{1}(x))\,dx\leq \varepsilon (b-a).}$ Заметь: ${\displaystyle {\frac {1}{b-a}}\int _{a}^{b}f_{1}(x)\,dx=\lim _{N\to \infty }{\frac {1}{N}}\sum _{n=1}^{N}f_{1}(s_{n})\leq \liminf _{N\to \infty }{\frac {1}{N}}\sum _{n=1}^{N}f(s_{n})}$ ${\displaystyle {\frac {1}{b-a}}\int _{a}^{b}f_{2}(x)\,dx=\lim _{N\to \infty }{\frac {1}{N}}\sum _{n=1}^{N}f_{2}(s_{n})\geq \limsup _{N\to \infty }{\frac {1}{N}}\sum _{n=1}^{N}f(s_{n})}$ Вычитая, мы видим, что ограничивать высшее и ограничивать низшее из ${\displaystyle \textstyle {\frac {1}{N}}\sum _{n=1}^{N}f(s_{n})}$ отличаются не более чем на ε. Поскольку ε произвольно, мы имеем существование предела и, согласно определению интеграла Дарбу, это правильный предел. Наконец, для комплекснозначных функций, интегрируемых по Риману, результат снова следует из линейности и того факта, что каждая такая функция может быть записана как ж = ты + vi, где ты, v действительнозначны и интегрируемы по Риману.∎

Этот критерий приводит к идее Интеграция Монте-Карло, где интегралы вычисляются путем выборки функции по последовательности случайных величин, равнораспределенных в интервале.

Невозможно обобщить интегральный критерий на класс функций, больший, чем просто интегрируемые по Риману. Например, если Интеграл Лебега считается и ж принято быть в L¹, то этот критерий не выполняется. В качестве контрпримера возьмем ж быть индикаторная функция некоторой равнораспределенной последовательности. Тогда в критерии левая часть всегда равна 1, тогда как правая часть равна нулю, потому что последовательность счетный, так ж ноль почти всюду.

Фактически, Де Брейн – Посттеорема утверждает обратное вышеупомянутому критерию: если ж - функция такая, что указанный выше критерий выполняется для любой равнораспределенной последовательности в [а, б], тогда ж интегрируема по Риману в [а, б].^[2]

Равнораспределение по модулю 1

Последовательность (а₁, а₂, а₃, ...) действительных чисел называется равнораспределенный по модулю 1 или равномерно распределенный по модулю 1 если последовательность дробные части из а_п, обозначаемый (а_п) или а_п − ⌊а_п⌋, равнораспределена в интервале [0, 1].

Примеры

Иллюстрация заполнения единичного интервала (Икс-axis), используя первый п члены последовательности Ван дер Корпута, для п от 0 до 999 (у-ось). Градация цвета происходит из-за наложения спектров.

• В теорема о равнораспределении: Последовательность всех кратных иррациональный α,

0, α, 2α, 3α, 4α, ...

равнораспределена по модулю 1.^[3]

• В более общем смысле, если п это многочлен с хотя бы одним коэффициентом, отличным от постоянного члена иррационального, то последовательность п(п) равномерно распределена по модулю 1.

Это было доказано Вейлем и является применением разностной теоремы Ван дер Корпута.^[4]

• Журнал последовательности (п) является нет равномерно распределены по модулю 1.^[3] Этот факт связан с Закон Бенфорда.
• Последовательность всех кратных иррациональной α последовательными простые числа,

2α, 3α, 5α, 7α, 11α, ...

равнораспределена по модулю 1. Это известная теорема аналитическая теория чисел, опубликовано Виноградов И. М. в 1948 г.^[5]

• В последовательность ван дер Корпута равнораспределен.^[6]

Критерий Вейля

Критерий Вейля утверждает, что последовательность а_п равнораспределена по модулю 1 тогда и только тогда, когда для всех ненулевых целые числа ℓ,

${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{j=1}^{n}e^{2\pi i\ell a_{j}}=0.}$

Критерий назван в честь и был впервые сформулирован: Герман Вейль.^[7] Это позволяет свести вопросы о равнораспределении к границам экспоненциальные суммы, фундаментальный и общий метод.

Эскиз доказательства

Если последовательность равнораспределена по модулю 1, то мы можем применить интегральный критерий Римана (описанный выше) к функции ${\displaystyle \textstyle f(x)=e^{2\pi i\ell x},}$ имеющая целое число нуль на интервале [0, 1]. Это сразу дает критерий Вейля. Наоборот, предположим, что критерий Вейля выполняется. Тогда интегральный критерий Римана выполняется для функций ж как и выше, и в силу линейности критерия это справедливо для ж быть любым тригонометрический полином. Посредством Теорема Стоуна – Вейерштрасса и аргумент приближения, это распространяется на любой непрерывный функция ж. Наконец, пусть ж - индикаторная функция интервала. Можно связать ж сверху и снизу двумя непрерывными на отрезке функциями, интегралы которых отличаются на произвольное ε. Рассуждениями, аналогичными доказательству интегрального критерия Римана, можно распространить результат на любой индикатор интервала функция ж, тем самым доказывая равнораспределение по модулю 1 данной последовательности.∎

Обобщения

• Количественную форму критерия Вейля дает Неравенство Эрдеша – Турана.
• Критерий Вейля естественным образом распространяется на более высокие Габаритные размеры, предполагая естественное обобщение определения эквираспределения по модулю 1:

Последовательность v_п векторов в р^k равнораспределена по модулю 1 тогда и только тогда, когда для любого ненулевого вектора ℓ ∈Z^k,

${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{j=0}^{n-1}e^{2\pi i\ell \cdot v_{j}}=0.}$

Пример использования

Критерий Вейля можно использовать, чтобы легко доказать теорема равнораспределения, утверждая, что последовательность кратных 0, α, 2α, 3α, ... некоторого реального числа α равнораспределена по модулю 1 тогда и только тогда, когда α иррационально.^[3]

Предположим α иррационально и обозначим нашу последовательность через а_j = jα (куда j начинается с 0, чтобы позже упростить формулу). Позволять ℓ ≠ 0 - целое число. поскольку α иррационально, ℓα никогда не может быть целым числом, поэтому ${\textstyle e^{2\pi i\ell \alpha }}$ никогда не может быть 1. Используя формулу суммы конечных геометрическая серия,

${\displaystyle \left|\sum _{j=0}^{n-1}e^{2\pi i\ell j\alpha }\right|=\left|\sum _{j=0}^{n-1}\left(e^{2\pi i\ell \alpha }\right)^{j}\right|=\left|{\frac {1-e^{2\pi i\ell n\alpha }}{1-e^{2\pi i\ell \alpha }}}\right|\leq {\frac {2}{\left|1-e^{2\pi i\ell \alpha }\right|}},}$

конечная оценка, не зависящая от п. Следовательно, после деления на п и позволяя п стремятся к бесконечности, левая часть стремится к нулю, и критерий Вейля выполняется.

И наоборот, обратите внимание, что если α является рациональный то эта последовательность не является равнораспределенной по модулю 1, потому что существует только конечное число вариантов дробной части а_j = jα.

разностная теорема ван дер Корпута

Теорема Йоханнес ван дер Корпут^[8] заявляет, что если для каждого час последовательность s_п+час − s_п равномерно распределена по модулю 1, то так же s_п.^[9][10][11]

А набор van der Corput это набор ЧАС целых чисел такие, что если для каждого час в ЧАС последовательность s_п+час − s_п равномерно распределена по модулю 1, то s_п.^[10][11]

Метрические теоремы

Метрические теоремы описывают поведение параметризованной последовательности для почти все значения некоторого параметра α: то есть для значений α не лежащий в каком-то исключительном множестве Мера Лебега нуль.

• Для любой последовательности различных целых чисел б_п, последовательность (б_пα) равнораспределена по модулю 1 почти для всех значений α.^[12]
• Последовательность (α^п) равнораспределена по модулю 1 почти для всех значений α > 1.^[13]

Неизвестно, являются ли последовательности (е^п) или (π^п) равнораспределены по модулю 1. Однако известно, что последовательность (α^п) является нет равнораспределенный модуль 1, если α это Номер PV.

Хорошо распределенная последовательность

Последовательность (s₁, s₂, s₃, ...) действительных чисел называется хорошо распределенный на [а, б] если для любого подынтервала [c, d ] из [а, б] у нас есть

${\displaystyle \lim _{n\to \infty }{\left|\{\,s_{k+1},\dots ,s_{k+n}\,\}\cap [c,d]\right| \over n}={d-c \over b-a}}$

равномерно в k. Ясно, что каждая хорошо распределенная последовательность равномерно распределена, но обратное неверно. Определение хорошо распределенного по модулю 1 аналогично.

Последовательности, равнораспределенные по произвольной мере

Для произвольного пространство меры вероятности ${\displaystyle (X,\mu )}$, последовательность точек ${\displaystyle (x_{n})}$ называется равнораспределенным относительно ${\displaystyle \mu }$ если среднее значение точечные меры сходится слабо к ${\displaystyle \mu }$:^[14]

${\displaystyle {\frac {\sum _{k=1}^{n}\delta _{x_{k}}}{n}}\Rightarrow \mu \ .}$

В любой Борель вероятностная мера на отделяемый, метризуемый в пространстве существует равнораспределенная последовательность по мере; действительно, это сразу следует из того факта, что такое пространство стандарт.

Общее явление равнораспределения часто возникает для динамических систем, связанных с Группы Ли, например, в решении Маргулиса Гипотеза Оппенгейма.

Смотрите также

• Теорема о равнораспределении
• Последовательность с низким расхождением
• Неравенство Эрдеша – Турана

Примечания

1. Kuipers & Niederreiter (2006), стр. 2–3
2. http://math.uga.edu/~pete/udnotes.pdf, Теорема 8
3. Kuipers & Niederreiter (2006) стр. 8
4. Kuipers & Niederreiter (2006) стр. 27
5. Kuipers & Niederreiter (2006) стр. 129
6. Kuipers & Niederreiter (2006) стр. 127
7. Вейль, Х. (Сентябрь 1916 г.). "Über die Gleichverteilung von Zahlen mod. Eins" [О распределении чисел по модулю единицы] (PDF). Математика. Анна. (на немецком). 77 (3): 313–352. Дои:10.1007 / BF01475864.
8. ван дер Корпут, Дж. (1931), "Diophantische Ungleichungen. I. Zur Gleichverteilung Modulo Eins", Acta Mathematica, Springer Нидерланды, 56: 373–456, Дои:10.1007 / BF02545780, ISSN  0001-5962, JFM  57.0230.05, Zbl  0001.20102
9. Kuipers & Niederreiter (2006) стр. 26
10. Монтгомери (1994) стр.18
11. Монтгомери, Хью Л. (2001). «Гармонический анализ в аналитической теории чисел» (PDF). В Бирнсе, Джеймс С. (ред.). Гармонический анализ ХХ века - праздник. Труды Института перспективных исследований НАТО, Иль Чокко, Италия, 2–15 июля 2000 г.. НАТО Sci. Сер. II, Матем. Phys. Chem. 33. Дордрехт: Kluwer Academic Publishers. С. 271–293. Дои:10.1007/978-94-010-0662-0_13. ISBN  978-0-7923-7169-4. Zbl  1001.11001.
12. Увидеть Бернштейн, Феликс (1911), "Über eine Anwendung der Mengenlehre auf ein aus der Theorie der säkularen Störungen herrührendes Problem", Mathematische Annalen, 71 (3): 417–439, Дои:10.1007 / BF01456856.
13. Коксма, Я.Ф. (1935), "Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins", Compositio Mathematica, 2: 250–258, JFM  61.0205.01, Zbl  0012.01401
14. Kuipers & Niederreiter (2006) с.171.

использованная литература

• Kuipers, L .; Нидеррайтер, Х. (2006) [1974]. Равномерное распределение последовательностей. Dover Publications. ISBN  0-486-45019-8.
• Kuipers, L .; Нидеррайтер, Х. (1974). Равномерное распределение последовательностей. John Wiley & Sons Inc. ISBN  0-471-51045-9. Zbl  0281.10001.
• Монтгомери, Хью Л. (1994). Десять лекций о взаимодействии аналитической теории чисел и гармонического анализа. Серия региональных конференций по математике. 84. Провиденс, Род-Айленд: Американское математическое общество. ISBN  0-8218-0737-4. Zbl  0814.11001.

дальнейшее чтение

• Гранвиль, Эндрю; Рудник, Зеев, ред. (2007). Равное распределение в теории чисел, введение. Труды Института перспективных исследований НАТО по равнораспределению в теории чисел, Монреаль, Канада, 11–22 июля 2005 г.. Наука НАТО II: математика, физика и химия. 237. Дордрехт: Springer-Verlag. ISBN  978-1-4020-5403-7. Zbl  1121.11004.
• Тао, Теренс (2012). Анализ Фурье высшего порядка. Аспирантура по математике. 142. Провиденс, Род-Айленд: Американское математическое общество. ISBN  978-0-8218-8986-2. Zbl  1277.11010.

внешняя ссылка

• Вайсштейн, Эрик В. «Равнораспределенная последовательность». MathWorld.
• Вайсштейн, Эрик В. «Критерий Вейля». MathWorld.
• Критерий Вейля в PlanetMath.
• Конспект лекций с доказательством критерия Вейля