Обычное число

редактировать
несколько случайное число

В математике вещественное число называется просто нормальным в целом с основанием b, если его бесконечная последовательность цифр распределена равномерно в том смысле, что каждая из bцифровые значения имеют одинаковую естественную плотность 1/b. Число называется нормальным в базе b, если для каждого положительного целого числа nвсе возможные строки nцифр имеют плотность b.

Интуитивно понятно, что число, являющееся просто нормальным, означает, что никакая цифра не встречается чаще, чем любая другая. Если число является нормальным, никакая конечная комбинация цифр заданной длины не встречается чаще, чем любая другая комбинация такой же длины. Нормальное число можно представить как бесконечную последовательность подбрасываний монеты (двоичный ) или бросков кубика (основание 6 ). Даже если будут такие последовательности, как 10, 100 или более последовательных решек (двоичные) или пятерок (основание 6) или даже 10, 100 или более повторений последовательности, такой как хвост-голова (два последовательных подбрасывания монеты) или 6 -1 (два последовательных броска кубика), также будет столько же любой другой последовательности равной длины. Никакая цифра или последовательность не приветствуются.

Число называется абсолютно нормальным, если оно нормально во всех основаниях целых чисел, больших или равных 2.

Хотя общее доказательство может быть дано, что почти все действительные числа являются нормальными (это означает, что набор ненормальных чисел имеет меру Лебега ноль), это доказательство не является конструктивным, и только несколько конкретных чисел оказались нормальными. Например, константа Чейтина является нормальной (и невычислимой ). Широко распространено мнение, что (вычислимые) числа √2, π и e нормальны, но доказательства остаются неуловимыми.

Содержание

  • 1 Определения
  • 2 Свойства и примеры
    • 2.1 Необычные числа
    • 2.2 Свойства
  • 3 Подключение к конечным автоматам
  • 4 Подключение к равнораспределенным последовательностям
  • 5 Примечания
  • 6 См. Также
  • 7 Ссылки
  • 8 Дополнительная литература
  • 9 Внешние ссылки

Определения

Пусть Σ будет конечным алфавитом из b- цифр, а Σ набор всех последовательностей, которые могут быть взяты из этого алфавита. Пусть S ∈ Σ - такая последовательность. Для каждого a в Σ пусть N S (a, n) обозначает, сколько раз цифра a встречается в первых n цифрах последовательности S. Мы говорим, что S просто нормальный если предел

lim n → ∞ NS (a, n) n = 1 b {\ displaystyle \ lim _ {n \ to \ infty} {\ frac {N_ {S} (a, n) } {n}} = {\ frac {1} {b}}}\ lim _ {n \ to \ infty} {\ frac {N_ {S} (a, n)} {n}} = {\ frac {1} {b}}

для каждого a. Теперь пусть w - любая конечная строка в Σ, и пусть N S (w, n) - количество раз, когда строка w появляется как подстрока в первые n цифр последовательности S. (Например, если S = ​​01010101..., то N S (010, 8) = 3.) S является нормальным, если для все конечные строки w ∈ Σ,

lim n → ∞ NS (w, n) n = 1 b | w | {\ displaystyle \ lim _ {n \ to \ infty} {\ frac {N_ {S} (w, n)} {n}} = {\ frac {1} {b ^ {| w |}}}}\ lim _ {n \ to \ infty} {\ frac {N_ {S} (w, n)} {n}} = {\ frac {1} {b ^ {| w |}}}

где | w | обозначает длину строки w. Другими словами, S является нормальным, если все строки одинаковой длины встречаются с одинаковой асимптотической частотой. Например, в нормальной двоичной последовательности (последовательность в алфавите {0,1}) 0 и 1 встречаются с частотой ⁄ 2 ; 00, 01, 10 и 11 встречаются с частотой ⁄ 4 ; 000, 001, 010, 011, 100, 101, 110 и 111 встречаются с частотой ⁄ 8 и т. Д. Грубо говоря, вероятность нахождения строки w в любом заданном позиция в S в точности такая, как ожидалось, если бы последовательность была создана в random.

. Предположим теперь, что b - это целое число больше 1, а x - действительное число. Рассмотрим расширение бесконечной последовательности цифр S x, b числа x в позиционной системе счисления с основанием b (мы игнорируем десятичную точку). Мы говорим, что x просто нормален по основанию b, если последовательность S x, b просто нормален, и что x нормален по основанию b, если последовательность S x, b нормально. Число x называется нормальным числом (или иногда абсолютно нормальным числом ), если оно является нормальным по основанию b для каждого целого числа b больше 1.

A заданная бесконечная последовательность является либо нормальной, либо ненормальной, тогда как действительное число, имеющее различное расширение base-b для каждого целого числа b ≥ 2, может быть нормальным в одной базе, но не в другой (в этом случае это не нормальное число). Для оснований r и s с log r / log s рациональным (так что r = b и s = b) каждое число, нормальное по основанию r, является нормальным по основанию s. Для оснований r и s с иррациональными log r / log s существует несчетное количество нормальных чисел в каждой базе, но не в другом.

A дизъюнктивная последовательность - это последовательность, в которой появляется каждая конечная строка. Нормальная последовательность дизъюнктивна, но дизъюнктивная последовательность не обязательно должна быть нормальной. Богатое число с основанием b - это число, расширение которого по основанию b дизъюнктивно: число, которое дизъюнктивно по отношению к любому основанию, называется абсолютно дизъюнктивным или называется лексиконом . Число, нормальное по основанию b, богато основанием b, но не обязательно наоборот. Действительное число x богато основанием b тогда и только тогда, когда множество {xb mod 1: n ∈ N} плотно в единичном интервале.

Мы определили число как просто нормальное в основании b, если каждая отдельная цифра появляется с частотой 1 / b. Для данного основания b число может быть просто нормальным (но не нормальным или b-плотным), b-плотным (но не просто нормальным или нормальным), нормальным (и, таким образом, просто нормальным и b-плотным), или ни одним из этих. Число является абсолютно ненормальным или абсолютно ненормальным, если оно не просто нормальное для любой базы.

Свойства и примеры

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

Концепция нормального числа была введена Эмилем Борелем (1909). Используя лемму Бореля – Кантелли, он доказал, что почти все действительные числа являются нормальными, установив существование нормальных чисел. Вацлав Серпинский (1917) показал, что можно указать конкретное такое число. Бехер и Фигейра (2002) доказали, что существует вычислимое абсолютно нормальное число. Хотя эта конструкция не дает напрямую цифр построенных чисел, она показывает, что в принципе возможно перечислить все цифры конкретного нормального числа.

Набор ненормальных чисел, несмотря на то, что он «большой» в смысле несчетности, также является нулевым набором (как его мера Лебега как подмножество действительных чисел равно нулю, поэтому оно практически не занимает места внутри действительных чисел). Кроме того, ненормальные числа (как и нормальные числа) плотны в действительных числах: набор ненормальных чисел между двумя различными действительными числами не пуст, поскольку он содержит каждое рациональное число ( на самом деле, это несчетное число бесконечных и даже сходится ). Например, существует несчетное количество чисел, десятичные разложения которых (с основанием 3 или выше) не содержат цифры 1, и ни одно из этих чисел не является нормальным.

Константа Чамперноуна

0,1234567891011121314151617181920212223242526272829...,

, полученная путем объединения десятичных представлений натуральных чисел по порядку, является нормальной по основанию 10. Аналогичным образом, различные варианты постоянной Шамперноу ( выполняются путем выполнения такой же конкатенации в других базах) являются нормальными в своих соответствующих базах (например, постоянная Чамперноуна по основанию 2 нормальна в базе 2), но не было доказано, что они нормальны в других базах.

Константа Коупленда – Эрдеша

0,23571113171923293137414347535961677173798389...,

, полученная путем конкатенации простых чисел по основанию 10, нормальна по основанию 10, как доказано А. Х. Коупленд и Пол Эрдеш (1946). В более общем плане последние авторы доказали, что действительное число, представленное в основании b конкатенацией

0. f (1) f (2) f (3)...,

, где f (n) - это n простое число, выраженное в основании b, нормально в основании b. Безикович (1935) доказал, что число, представленное тем же выражением, с f (n) = n,

0,149162536496481100121144...,

полученное путем конкатенации квадратные числа в базе 10, нормально в базе 10. Гарольд Дэвенпорт и Эрдеш (1952) доказали, что число, представленное тем же выражением, где f - любое непостоянный многочлен, значения положительных целых чисел которого являются положительными целыми числами, выраженными по основанию 10, нормален по основанию 10.

Накай и Шиокава (1992) доказали, что если f (x) - любой непостоянный многочлен с действительными коэффициентами, такой что f (x)>0 для всех x>0, тогда действительное число, представленное конкатенацией

0. [f (1)] [f (2)] [f (3)]...,

где [f (n)] - целая часть числа f (n), выраженная по основанию b, является нормальным по основанию b. (Этот результат включает в качестве частных случаев все вышеупомянутые результаты Чамперноуна, Безиковича, Дэвенпорта и Эрдеша.) Авторы также показывают, что тот же результат имеет место даже в более общем случае, когда f является любой функцией вида

f ( x) = α · x + α 1 · x +... + α d · x,

где αs и βs - действительные числа с β>β 1>β2>...>β d ≥ 0 и f (x)>0 для всех x>0.

Бейли и Крэндалл (2002) показывают явный бесчисленно бесконечный класс b-нормальных чисел, возмущая числа Стоунхема.

Это было неуловимо цель доказать нормальность чисел, которые не построены искусственно. Хотя √2, π, ln (2) и e строго предполагаются как нормальные, до сих пор не известно, являются ли они нормальными или нет. Не было даже доказано, что все цифры на самом деле встречаются бесконечно много раз в десятичных разложениях этих констант (например, в случае π популярное утверждение «каждая строка чисел в конечном итоге встречается в π» не является истинным.). Также было высказано предположение, что каждое иррациональное алгебраическое число абсолютно нормально (что означало бы, что √2 нормально), и контрпримеры не известны ни в какой базе. Однако ни одно иррациональное алгебраическое число не оказалось нормальным ни в какой базе.

Ненормальные числа

Никакое рациональное число не является нормальным в любом основании, поскольку последовательности цифр рациональных чисел в конечном итоге периодичны. Однако рациональное число может быть просто нормальным в определенной базе. Например, 13,717,421 1,111,111,111 = 123, 456, 789 9, 999, 999, 999 = 0. 0123456789 ¯ {\ displaystyle {\ frac {13 {,} 717 {,} 421} {1 {,} 111 {,} 111 {,} 111}} = {\ frac {123, \! 456, \! 789} {9, \! 999, \! 999, \! 999}} = 0. {\ Overline {0123456789}} }{\ displaystyle {\ frac {13 {,} 717 {,} 421} {1 {,} 111 {,} 111 {,} 111}} = {\ frac {123, \! 456, \! 789} {9, \! 999, \! 999, \! 999}} = 0. {\ overline {0123456789}}} просто нормально в базе 10.

Мартин (2001) привел простой пример иррационального числа, которое абсолютно ненормально. Пусть f (2) = 4 и

f (n) = nf (n - 1) n - 1, n ∈ Z ∩ [3, ∞) {\ displaystyle f \ left (n \ right) = n ^ { \ frac {f \ left (n-1 \ right)} {n-1}}, \, n \ in \ mathbb {Z} \ cap \ left [3, \ infty \ right)}{\ displaystyle f \ left (n \ right) = n ^ { \ frac {f \ left (n-1 \ right)} {n-1}}, \, n \ in \ mathbb {Z} \ cap \ left [3, \ infty \ right)}
α = ∏ m = 2 ∞ (1 - 1 f (м)) = (1 - 1 4) (1 - 1 9) (1 - 1 64) (1 - 1 152587890625)… = 0,6562499999956991 99999… 99999 ⏟ 23, 747, 291, 559 8528404201690728… {\ displaystyle \ alpha = \ prod _ {m = 2} ^ {\ infty} \ left ({1 - {\ frac {1} {f \ left (m \ right)}}} \ right) = \ left (1 - {\ frac {1} {4}} \ right) \ left (1 - {\ frac {1} {9}} \ right) \ left (1 - {\ frac {1} {64 }} \ right) \ left (1 - {\ frac {1} {152587890625}} \ right) \ ldots = 0.6562499999956991 \ underbrace {99999 \ ldots 99999} _ {23,747,291,559} 8528404201690728 \ ldots}{\ displaystyle \ alpha = \ prod _ {m = 2} ^ {\ infty} \ left ({ 1 - {\ frac {1} {f \ left (m \ right)}}} \ right) = \ left (1 - {\ frac {1} {4}} \ right) \ left (1 - {\ frac {1} {9}} \ right) \ left (1 - {\ frac {1} {64}} \ right) \ left (1 - {\ frac {1} {152587890625}} \ right) \ ldots = 0.6562499999956991 \ underbrace {99999 \ ldots 99999} _ {23,747,291,559} 8528404201690728 \ ldots}

Тогда α - это Число Лиувилля и абсолютно ненормально.

Свойства

Дополнительные свойства нормальных чисел включают:

  • Каждое ненулевое действительное число может быть записано как произведение двух нормальных чисел. Например, если a - любое ненулевое действительное число, а x - ненулевое действительное число, которое выбирается равномерно случайным образом из любого конечного интервала, то почти наверняка x и a / x нормальны.
  • Если x нормальное число по основанию b и a ≠ 0 является рациональным числом, то x ⋅ a {\ displaystyle x \ cdot a}{\ displaystyle x \ cdot a} также является нормальным по основанию b.
  • Если A ⊆ N {\ displaystyle A \ substeq \ mathbb {N}}A \ substeq \ mathbb {N} плотно (для каждого α < 1 {\displaystyle \alpha <1}\ alpha <1и для всех достаточно большой n, | A ∩ {1,…, n} | ≥ n α {\ displaystyle | A \ cap \ {1, \ ldots, n \} | \ geq n ^ {\ alpha}}| A \ cap \ {1, \ ldots, n \} | \ geq n ^ {\ alpha} ) и a 1, a 2, a 3,… {\ displaystyle a_ {1}, a_ {2}, a_ {3}, \ ldots}a_ { 1}, a_ {2}, a_ {3}, \ ldots - основание-b разложения элементов A, то число 0. a 1 a 2 a 3… {\ displaystyle 0.a_ {1} a_ {2} a_ {3} \ ldots}0.a_ {1} a_ {2} a_ {3} \ ldots , образованный конкатенацией элементов A, нормален по основанию b (Copeland и Erdős 1946). Из этого следует, что число Чамперноуна нормально по основанию 10 (поскольку множество всех положительных целых чисел, очевидно, плотно) и что константа Коупленда – Эрдеша нормальна по основанию 10 (поскольку теорема о простых числах означает, что набор простых чисел является плотным).
  • Последовательность нормальна тогда и только тогда, когда каждый блок одинаковой длины появляется с одинаковой частотой. (Блок длины k - это подстрока длины k, появляющаяся в позиции в последовательности, кратной k: например, первый блок длины k в S - это S [1..k], второй блок длины k S [k + 1..2k] и т. д.). Это подразумевается в работах Зива и Лемпеля (1978) и явно выражено в работах Бурка, Хичкока и Винодчандрана (2005).
  • Число нормально по основанию b тогда и только тогда, когда оно просто нормально по основанию b для всех k ∈ Z + {\ displaystyle k \ in \ mathbb {Z} ^ {+}}{\ displaystyle k \ in \ mathbb {Z} ^ {+}} . Это следует из предыдущей блочной характеристики нормальности: поскольку n блоков длины k в его расширении по основанию b соответствует n цифре в его расширении по основанию b, число просто нормальное в базовом b тогда и только тогда, когда блоки длины k появляются в его расширении по основанию b с одинаковой частотой.
  • Число является нормальным тогда и только тогда, когда оно просто нормальное в каждой базе. Это следует из предыдущей характеристики нормальности по основанию b.
  • Число является b-нормальным тогда и только тогда, когда существует набор натуральных чисел m 1 < m 2 < m 3 < ⋯ {\displaystyle m_{1}м_ {1} <m_ {2} <m_ {3} <\ cdots , где число просто нормальное по основанию b для всех m ∈ {m 1, m 2,…}. {\ displaystyle m \ in \ {m_ {1}, m_ {2}, \ ldots \}.}m \ in \ {m_ {1}, m_ {2}, \ ldots \}. Никакого конечного набора недостаточно, чтобы показать, что число является b-нормальным.
  • Все нормальные последовательности закрыты при конечных вариантах : добавление, удаление или изменение конечного числа цифр в любой нормальной последовательности оставляет его нормальным. Точно так же, если конечное число цифр добавлено, удалено или изменено в любой простой нормальной последовательности, новая последовательность все еще будет просто нормальной.

Подключение к конечным автоматам

Агафонов показал ранний связь между конечными автоматами и нормальными последовательностями: каждая бесконечная подпоследовательность, выбранная из нормальной последовательности с помощью обычного языка, также является нормальной. Другими словами, если кто-то запускает конечный автомат в нормальной последовательности, где каждое из состояний конечного автомата помечено либо «выход», либо «нет выхода», и машина выводит цифру, которую он читает следующей после ввода "output" состояние, но не выводит следующую цифру после входа в "no output state", тогда последовательность, которую он выводит, будет нормальной.

Существует более глубокая связь с игроками с конечным числом состояний (FSG) и информацией Конечные компрессоры без потерь (ILFSC).

  • A конечный игрок (также известный как конечный мартингейл ) - конечный автомат над конечным алфавитом Σ {\ displaystyle \ Sigma}\ Sigma , каждое из состояний которого помечено процентным соотношением денег для ставки на каждую цифру в Σ {\ displaystyle \ Sigma}\ Sigma . Например, для FSG по двоичному алфавиту Σ = {0, 1} {\ displaystyle \ Sigma = \ {0,1 \}}\ Sigma = \ {0,1 \} текущее состояние q ставит некоторый процент q 0 ∈ [0, 1] {\ displaystyle q_ {0} \ in [0,1]}q_ {0} \ in [0,1] денег игрока на бите 0, а оставшиеся q 1 = 1 - q 0 {\ displaystyle q_ {1} = 1-q_ {0}}q_ {1} = 1-q_ {0} доля денег игрока на бит 1. Денежная ставка на цифру, которая идет следующей во входных данных (общее количество денег, умноженное на процент ставка) умножается на | Σ | {\ displaystyle | \ Sigma |}| \ Sigma | , а остальные деньги потеряны. После того, как бит считан, FSG переходит в следующее состояние в соответствии с полученными входными данными. FSG d преуспевает в на бесконечной последовательности S, если, начиная с $ 1, она делает неограниченные денежные ставки на эту последовательность; то есть, если
lim sup n → ∞ d (S ↾ n) = ∞, {\ displaystyle \ limsup _ {n \ to \ infty} d (S \ upharpoonright n) = \ infty,}\ limsup _ {n \ to \ infty} d (S \ upharpoonright n) = \ infty,
где d (S ↾ n) {\ displaystyle d (S \ upharpoonright n)}d (S \ upharpoonright n) - сумма денег, которую игрок d имеет после прочтения первых n цифр S (см. верхний предел ).
  • A Конечный компрессор - это конечный автомат с выходными строками, обозначающими его переходы между состояниями, включая, возможно, пустую строку (поскольку одна цифра считывается из входной последовательности для каждого перехода между состояниями, необходимо иметь возможность выводить пустую строку, чтобы достичь любого сжатия вообще). Конечный компрессор без потерь информации - это конечный компрессор, вход которого может быть однозначно восстановлен из его выхода и конечного состояния. Другими словами, для конечного компрессора C с набором состояний Q, C не имеет потерь информации, если функция f: Σ ∗ → Σ ∗ × Q {\ displaystyle f: \ Sigma ^ {*} \ to \ Sigma ^ {* } \ times Q}f: \ Sigma ^ {*} \ to \ Sigma ^ {*} \ times Q , отображение входной строки C для выходной строки и конечного состояния C: 1–1. Такие методы сжатия, как кодирование Хаффмана или кодирование Шеннона – Фано, могут быть реализованы с помощью ILFSC. ILFSC C сжимает бесконечную последовательность S, если
lim inf n → ∞ | C (S ↾ n) | n < 1, {\displaystyle \liminf _{n\to \infty }{\frac {|C(S\upharpoonright n)|}{n}}<1,}\ liminf _ {n \ to \ infty} {\ frac {| C (S \ upharpoonright n) |} {n}} <1,
, где | C (S ↾ n) | {\ displaystyle | C (S \ upharpoonright n) |}| C ( S \ upharpoonright n) | - количество цифр, выводимых C после чтения первых n цифр S. Степень сжатия (limit inferior выше) всегда можно сделать равным 1 с помощью ILFSC с 1 состоянием, который просто копирует свои входные данные в выходные.

Шнорр и Стимм показали, что ни один FSG не может преуспеть в любой нормальной последовательности, а Bourke, Hitchcock и Винодчандран показал обратное. Следовательно:

Последовательность нормальна тогда и только тогда, когда нет игрока с конечным числом состояний, который преуспел в ней.

Зив и Лемпель показали:

Последовательность нормальна тогда и только тогда, когда она несжимаема какой-либо информацией Конечный компрессор без потерь

(они фактически показали, что оптимальная степень сжатия последовательности по всем ILFSCs является в точности ее скоростью энтропии, количественной мерой ее отклонения от нормальности, которая равна 1 именно тогда, когда последовательность обычный). Поскольку алгоритм сжатия LZ сжимает асимптотически так же, как и любой ILFSC, это означает, что алгоритм сжатия LZ может сжимать любую ненормальную последовательность.

Эти характеристики нормальных последовательностей можно интерпретировать как означающие что "нормальный" = "случайный с конечным числом состояний"; т.е. нормальные последовательности - это в точности те, которые кажутся случайными для любого конечного автомата. Сравните это с алгоритмически случайными последовательностями, которые представляют собой те бесконечные последовательности, которые кажутся случайными для любого алгоритма (и на самом деле имеют аналогичные характеристики азартных игр и сжатия с машинами Тьюринга, заменяющими конечные автоматы).

Связь с равнораспределенными последовательностями

Число x нормально в основании b тогда и только тогда, когда последовательность (bkx) k = 0 ∞ {\ displaystyle { \ left (b ^ {k} x \ right)} _ {k = 0} ^ {\ infty}}{\ left (b ^ {k} x \ right)} _ {k = 0} ^ {\ infty} является равнораспределенным по модулю 1 или, что эквивалентно, с использованием Вейля критерий, если и только если

lim n → ∞ 1 n ∑ k = 0 n - 1 e 2 π imbkx = 0 для всех целых чисел m ≥ 1. {\ displaystyle \ lim _ {n \ rightarrow \ infty } {\ frac {1} {n}} \ sum _ {k = 0} ^ {n-1} e ^ {2 \ pi imb ^ {k} x} = 0 \ quad {\ text {для всех целых чисел} } m \ geq 1.}\ lim _ {n \ rightarrow \ infty} {\ frac {1} {n}} \ sum _ {k = 0} ^ {n-1} e ^ {2 \ pi imb ^ {k} x} = 0 \ quad {\ text {для всех целых чисел}} m \ geq 1.

Эта связь приводит к терминологии, согласно которой x является нормальным по основанию β для любого действительного числа β, если последовательность (x β k) k = 0 ∞ {\ displaystyle \ left ({ x \ beta ^ {k}} \ right) _ {k = 0} ^ {\ infty}}\ left ({x \ beta ^ {k}} \ right) _ {k = 0} ^ {\ infty} равнораспределено по модулю 1.

Примечания

См. также

Ссылки

Дополнительная литература

Внешние ссылки

Последняя правка сделана 2021-05-31 12:39:21
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте