Я придумал 2 метода для создания относительно коротких случайных строк - один намного быстрее и проще, а другой намного медленнее, но я думаю, что более случайный. Есть ли не супер-сложный метод или способ измерения того, насколько случайными могут быть данные из каждого метода?
Я попытался сжимать выходные строки (через zlib), вычисляя более по-настоящему случайные данные, тем меньше он будет сжиматься, но это не так много.
Вы используете стандартное сжатие как прокси для бескомпромиссного Kolmogorov Complexity, которое является "правильной" математической основой для количественной оценки случайности (но, к сожалению, не является вычислимой).
Вы также можете попробовать несколько измерений entropy, если вы готовы принять какое-то распределение по строкам.
Вы можете использовать некоторое сопоставление для преобразования строк в числовые, а затем применять стандартные тесты, такие как Diehard и TestU01. Обратите внимание, что требуются длинные последовательности выборок (как правило, несколько файлов MB)
Результат считается случайным, если его нельзя предсказать заранее с уверенностью. Если это можно предсказать с уверенностью, то оно считается детерминированным. Это двоичная категоризация, результаты либо детерминированные, либо случайные, то нет степеней случайности. Существуют, однако, степени предсказуемости. Одним из показателей предсказуемости является энтропия, о чем упоминается EMS.
Рассмотрим две игры. Вы не знаете, в какой игре вы проиграете или проиграете. В игре 1 вероятность выигрыша равна 1/2, т.е. Вы выигрываете примерно половину времени в долгосрочной перспективе. В игре 2 шансы на победу составляют 1/100. Обе игры считаются случайными, потому что результат не является мертвой уверенностью. Игра 1 имеет большую энтропию, чем игра 2, потому что результат менее предсказуем - в то время как есть шанс выиграть, вы уверены, что проиграете в любом испытании.
Объем сжатия, который может быть достигнут (с помощью хорошего алгоритма сжатия) для последовательности значений, связан с энтропией последовательности. У английского языка довольно низкая энтропия (много избыточной информации как в относительной частоте букв, так и в последовательности слов, которые встречаются как группы), и, следовательно, имеет тенденцию к сжатию довольно хорошо.