Регистрация Войти
Рейтинг:0
Tom avatar Crypto

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

флаг tf
Tom

Для улучшения качества генераторов случайных чисел в генераторы Middle Square (Widynski) и Xorshift (Marsaglia) были добавлены последовательности Вейля:

https://arxiv.org/abs/1704.00358

https://www.jstatsoft.org/article/view/v008i14

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

У меня также есть генератор, который работает как случайное отображение. Длины циклов n-битного генератора близки к $\sqrt{\pi \frac{2^{n}}{8}}$ (хотя обычно несколько короче, видимо из-за несовершенства генератора). Теперь я добавляю к выходу последовательность Вейля, которая стала новым входом для генератора. И теперь генератор достигает максимальной длины цикла для разных ключей (он закодирован) и семян.

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

30
0 + 0
kodlu avatar
флаг sa
kodlu
они на самом деле доказали это в своей статье? обратите внимание, что отображение по модулю составного $n$ может иметь предпериод, т. е. итерацию типа ро.
0
Ответить
Tom avatar
флаг tf
Tom
@kodlu Если я правильно понимаю работу Видынски, он доказал это только для своей Средней площади. Марсалья не упомянул о доказательствах. Поэтому я не уверен, существуют ли такие доказательства для (не идеального) случайного отображения.Что касается препериодов, то я их не только наблюдаю, но и числа могут появляться несколько раз, прежде чем попадут в цикл. Рассмотрим 10-битный генератор. Число 311 может появиться через 433, 122, 479 шагов и затем войти в цикл, но не всегда тривиально. Его можно достичь через 111 607 417 111 607 417,... шагов (но вся последовательность повторяется через 1024 шага).
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.