Последовательность Эренфойхта – Мицельского - это рекурсивно определенная последовательность двоичных цифр с псевдослучайными свойствами, определенная Анджеем Эренфойхтом и Яном Мицельски ( 1992 ).
Определение
Последовательность начинается с единственного бита 0; каждая последующая цифра формируется путем нахождения самого длинного суффикса последовательности, который также встречается раньше в последовательности, и дополнения бита, следующего за самым последним более ранним появлением этого суффикса. (Пустая строка является суффиксом и префиксом каждой строки.) Например, первые несколько шагов этого процесса построения:
- 0: начальный бит
- 01: суффикс "" из "0" встречается раньше, за последним следует 0, поэтому добавьте 1
- 010: суффикс "" в "01" встречается раньше, за последним следует 1, поэтому добавьте 0
- 0100: суффикс «0» из «010» встречается раньше, за последним следует 1, поэтому добавьте 0
- 01001: суффикс «0» из «0100» встречается раньше, за последним следует 0, поэтому добавьте 1
- 010011: суффикс «01» из «01001» встречается раньше, за последним последним следует 0, поэтому добавьте 1
- 0100110: суффикс «1» из «010011» встречается раньше, за последним следует 1, поэтому добавьте 0
Первые несколько цифр последовательности:
Алгоритмы
Наивный алгоритм, который генерирует каждый бит в последовательности, сравнивая каждый суффикс со всей предыдущей последовательностью, может занять до время создать первый биты последовательности. Однако, как показывают Герман и Солтис (2009), используя структуру данных, относящуюся к суффиксному дереву , последовательность может быть сгенерирована гораздо более эффективно, за постоянное время на каждую сгенерированную цифру.
Универсальность
Последовательность является дизъюнктивной , что означает, что каждая конечная подпоследовательность битов происходит непрерывно, бесконечно часто в пределах последовательности ( Ehrenfeucht & Mycielski 1992 ). Более точно, позиция, по которой каждая подпоследовательность длины можно гарантировать, что произошло по крайней мере раз самое большее где - функция Аккермана ( Herman & Soltys 2009 ). Экспериментально, однако, каждая подпоследовательность появляется в этой последовательности намного раньше, чем можно было бы предположить по этой верхней границе: позиция, по которой все длины - последовательности происходят, вплоть до предела экспериментальных испытаний, близка к минимально возможному значению, которое может быть, , позиция, по которой последовательность де Брейна содержит всю длину -подстроки ( Сатнер 2003 ).
Нормальность
Ehrenfeucht & Mycielski (1992) предполагают, что числа из 0 и 1 бит каждое сходятся к предельной плотности 1/2. То есть, если обозначает количество 0 бит в первом положения последовательности Эренфойхта – Мицельского, то должно быть так, что
Более того, И. Дж. Гуд предполагает, что скорость сходимости этого предела должна быть значительно выше, чем скорость сходимости случайной двоичной последовательности , для которой (по закону повторного логарифма )
( Ehrenfeucht & Mycielski 1992 ). Гипотеза баланса Эренфойхта-Микельски предполагает, что двоичное число 0,01001101 ... (число, имеющее последовательность Эренфойхта-Микельского в качестве последовательности двоичных цифр после двоичной точки) может быть нормальным числом с основанием 2. По состоянию на 2009 год эта гипотеза остается недоказан ( Herman & Soltys 2009 ); однако известно, что каждая предельная точка последовательности значенийнаходится между 1/4 и 3/4 включительно ( Kieffer & Szpankowski 2007 ).
Рекомендации
- Эренфойхт, Анджей ; Майкельски, Ян (1992), Гай, Ричард К. (ред.), «Псевдослучайная последовательность: насколько она случайна?» , Нерешенные проблемы, American Mathematical Monthly , 99 (4): 373-375, DOI : 10,2307 / 2324917 , JSTOR 2324917
- Герман, Гжегож; Солтыс, Майкл (2009), "О последовательности эренфойхтова-Мицельского", журнал дискретных алгоритмов , 7 (4): 500-508, DOI : 10.1016 / j.jda.2009.01.002
- Киффер, Джон С .; Шпанковски, Войцех (2007), "О гипотезе баланса Эренфойхта – Микельского " , Proc. Конф. Анализ алгоритмов (AofA 2007) , Дискретная математика и теоретическая информатика, стр. 19–28.
- Сатнер, Клаус (2003), «Последовательность Эренфойхта-Мицельски» (PDF) , в Ибарре, Огайо ; Данг, З. (ред.), Proc. Конф. Реализация и применение автоматов (CIAA 2003) , конспект лекций по информатике, 2759 , Springer-Verlag, стр. 73–82, doi : 10.1007 / 3-540-45089-0_26
Внешние ссылки
- Пропп, Джим (16 октября 2019 г.), «Угадай снова: последовательность Эренфойхта – Микельского» , « Математические чары»