Простой действительно генератор случайных чисел

Question

Существует много исследований, связанных с генерацией "действительно" случайных чисел.

Есть очень простой метод, изобретенный давно. Метод приписан фон Нейману [1].

В самой простой форме это можно представить как генерирование случайных битов из смещенного источника 0 или 1. Учитывая, что вероятность последовательности 01 такая же, как и 10, можно использовать 01 - для представления действительно случайных "0" и 10 как действительно случайного "1" бита (комбинации 00 и 11 просто отбрасываются).

Довольно просто. Кто-нибудь может указать, почему такой метод не генерирует случайную последовательность (и, таким образом, решает проблему генерации случайных чисел на компьютерах)?

Answer 1

Позвольте мне объяснить, что означают "случайное" и "действительно случайное". "Случайный" просто означает, что числа одинаково распределены и выбираются независимо от всего остального (то есть числа iid). А "действительно случайный" просто означает iid и uniform (см. Также Frauchiger et al. 2013.)

Если источником входных битов является iid, но имеется смещение, то метод фон Неймана устранит это смещение - числа останутся iid, но теперь несмещены, а именно, каждое число будет равно 0 или 1 с равной вероятностью. В общем, если исходные числа изначально не были заданы, метод фон Неймана не сделает эти числа "действительно случайными"; даже фон Нейман (1951) предполагает "независимость от последовательных подбрасываний [монеты]". Метод фон Неймана - один из множества доступных экстракторов случайности (и я обсуждаю некоторые из них), и это обсуждение применимо к этим другим экстракторам так же, как и к методу фон Неймана.

В любом случае, различие между "псевдослучайными" и "истинно случайными" числами - это не то, что волнует приложения (и вы на самом деле не указали, какое приложение вы имеете в виду). Вместо этого в целом:

• Приложения безопасности заботятся о том, сложно ли угадать числа; в этом случае только криптографический ГСЧ может выполнить это требование (даже тот, который полагается на генератор псевдослучайных чисел). Примером Python является secrets модуль или random.SystemRandom.
• Научное моделирование заботится о том, ведут ли числа как независимые однородные случайные числа, и часто заботится о том, воспроизводятся ли числа в более позднее время. Пример Python: numpy.random.Generator.

РЕКОМЕНДАЦИИ:

• Фраучигер, Д., Реннер, Р., Тройер, М., "Истинная случайность от реалистичных квантовых устройств", 2013.
• фон Нейман, Дж., "Различные методы, используемые в связи со случайными цифрами", 1951.