Последовательность Эренфойхта – Мицельского - Ehrenfeucht–Mycielski sequence

В Последовательность Эренфойхта – Мицельского рекурсивно определенная последовательность двоичные цифры с участием псевдослучайный свойства, определенные Анджей Эренфойхт и Ян Мыцельски  (1992 ).

Определение

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

1. 0: начальный бит
2. 01: суффикс "" из "0" встречается раньше, за последним следует 0, поэтому добавьте 1
3. 010: суффикс "" в "01" встречается раньше, за последним следует 1, поэтому добавьте 0
4. 0100: суффикс «0» из «010» встречается раньше, за последним последним следует 1, поэтому добавьте 0
5. 01001: суффикс «0» из «0100» встречается раньше, за последним последним следует 0, поэтому добавьте 1
6. 010011: суффикс "01" в "01001" встречается раньше, за последним последним следует 0, поэтому добавьте 1
7. 0100110: суффикс «1» из «010011» встречается раньше, за последним последним следует 1, поэтому добавьте 0

Первые несколько цифр последовательности:

010011010111000100001111 ... (последовательность A038219 в OEIS ).

Алгоритмы

Наивный алгоритм, который генерирует каждый бит в последовательности, сравнивая каждый суффикс со всей предыдущей последовательностью, может занять до ${\displaystyle O(n^{3})}$ время для создания первого ${\displaystyle n}$ биты последовательности. Однако, как Герман и Солтис (2009) показать с использованием структуры данных, связанной с суффиксное дерево, последовательность может быть сгенерирована намного эффективнее, в постоянное время на сгенерированную цифру.

Универсальность

Последовательность дизъюнктивный, означающее, что каждая конечная подпоследовательность битов встречается непрерывно, бесконечно часто в последовательности (Эренфойхт и Микельски 1992 ). Более конкретно, позиция, по которой каждая подпоследовательность длины ${\displaystyle i}$ можно гарантировать, что произошло по крайней мере ${\displaystyle j}$ раз самое большее ${\displaystyle A(4i,j)}$ где ${\displaystyle A}$ это Функция Аккермана (Герман и Солтис 2009 ). Экспериментально, однако, каждая подпоследовательность появляется в этой последовательности намного раньше, чем можно было бы предположить по этой верхней границе: позиция, по которой все длины -${\displaystyle i}$ последовательности происходят, вплоть до предела экспериментальных испытаний, близка к минимально возможному значению, которое может быть, ${\displaystyle 2^{i}+i}$, позиция, по которой последовательность де Брейна содержит всю длину${\displaystyle i}$ подстроки (Сатнер 2003 ).

Нормальность

Эренфойхт и Микельски (1992) предположить, что числа из 0 и 1 бит каждое сходятся к предельной плотности 1/2. То есть, если ${\displaystyle f(i)}$ обозначает количество 0 бит в первом ${\displaystyle i}$ положения последовательности Эренфойхта – Мицельского, то должно быть, что

${\displaystyle \lim _{i\rightarrow \infty }{\frac {f(i)}{i}}={\frac {1}{2}}.}$

Сильнее, И. Дж. Хорошо предполагает, что скорость сходимости этого предела должно быть значительно быстрее, чем у случайная двоичная последовательность, для которого (по закон повторного логарифма )

${\displaystyle {\frac {f(i)}{i}}={\frac {1}{2}}+O({\sqrt {\frac {\log \log i}{i}}})}$

(Эренфойхт и Микельски 1992 ). Гипотеза баланса Эренфойхта – Микельского предполагает, что двоичное число 0,01001101 ... (число, имеющее последовательность Эренфойхта – Микельского в качестве последовательности двоичных цифр после двоичной точки) может быть нормальный номер в базе 2. По состоянию на 2009 г. это предположение остается недоказанным (Герман и Солтис 2009 ); однако известно, что каждая предельная точка последовательности значений ${\displaystyle f(i)/i}$ находится между 1/4 и 3/4 включительно (Киффер и Шпанковски 2007 ).

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

• Эренфойхт, Анджей; Мыцельски, Ян (1992), Гай, Ричард К. (ред.), «Псевдослучайная последовательность: насколько она случайна?», Нерешенные проблемы, Американский математический ежемесячный журнал, 99 (4): 373–375, Дои:10.2307/2324917, JSTOR  2324917
• Герман, Гжегож; Солтыс, Майкл (2009), «О последовательности Эренфойхта – Мицельского», Журнал дискретных алгоритмов, 7 (4): 500–508, Дои:10.1016 / j.jda.2009.01.002
• Киффер, Джон С .; Шпанковски, Войцех (2007), "О гипотезе баланса Эренфойхта – Мицельского", Proc. Конф. Анализ алгоритмов (AofA 2007), Дискретная математика и теоретическая информатика, стр. 19–28.
• Сатнер, Клаус (2003), "Последовательность Эренфойхта – Мицельского" (PDF), в Ибарра, О.; Данг, З. (ред.), Proc. Конф. Внедрение и применение автоматов (CIAA 2003), Конспект лекций по информатике, 2759, Springer-Verlag, стр. 73–82, Дои:10.1007/3-540-45089-0_26

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

• Пропп, Джим (16 октября 2019 г.), "Угадай снова: последовательность Эренфойхта-Мицельского", Математические чары