Как проверить случайность (в данном случае - Shuffling)

Question

Во-первых, этот вопрос вырван из этого вопроса. Я сделал это, потому что я думаю, что эта часть больше, чем часть более длинного вопроса. Если это оскорбляет меня, прошу прощения.

Предположим, у вас есть алгоритм, который генерирует случайность. Теперь, как вы это тестируете? Или, чтобы быть более прямым - предположим, у вас есть алгоритм, который перетасовывает колоду карт, как вы проверяете, что это совершенно случайный алгоритм?

Чтобы добавить некоторую теорию к проблеме - Колода карт может быть перетасована в 52! (52 факториала) по-разному. Возьмите колоду карт, перемешайте ее вручную и запишите порядок всех карт. Какова вероятность того, что вы бы получили именно эту случайность? Ответ: 1/52!.

Какова вероятность того, что после перетасовки вы получите A, K, Q, J ... каждой масти в последовательности? Ответ 1/52!

Итак, просто перетасовав один раз и посмотрев на результат, вы не получите абсолютно никакой информации о случайности ваших алгоритмов перетасовки. Дважды и у тебя будет больше информации, еще три больше ...

Как бы вы проверили алгоритм случайности в чёрном ящике?

Answer 1

Я не совсем слежу за вашим вопросом. Вы говорите

Предположим, у вас есть алгоритм, который генерирует случайность. Теперь, как вы это тестируете?

Что ты имеешь в виду? Если вы предполагаете, что можете генерировать случайность, нет необходимости проверять это.

Если у вас есть хороший генератор случайных чисел, легко создать случайную перестановку (например, позвоните в свои карты 1-52. Создайте 52 случайных числа, назначая каждое из них по порядку, а затем сортируйте в соответствии с 52 случайностями). Вы не собираетесь разрушать случайность вашего хорошего RNG, генерируя вашу перестановку.

Сложный вопрос: можете ли вы доверять своему ГСЧ? Вот пример ссылки на людей, обсуждающих эту проблему в определенном контексте.