Как проверить случайность (показательный пример — перетасовка)
https://stackoverflow.com/questions/56411
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Во-первых, этот вопрос вырван из этот вопрос.Я сделал это, потому что считаю, что эта часть больше, чем часть более длинного вопроса.Если это обидело, пожалуйста, простите меня.
Предположим, у вас есть алгоритм, генерирующий случайность.Как теперь это проверить?Или, если быть более прямым: предположим, что у вас есть алгоритм, который тасует колоду карт, как вы проверяете, что это совершенно случайный алгоритм?
Чтобы добавить некоторую теорию к проблеме - колода карт может быть перетасована в 52!(52 факториала) разными способами.Возьмите колоду карт, перетасуйте ее вручную и запишите порядок расположения всех карт.Какова вероятность того, что у вас получилась бы именно такая тасовка?Отвечать:1/52!.
Какова вероятность, что после перетасовки у вас выпадут A, K, Q, J...каждой масти в последовательности?Ответ 1/52!
Таким образом, просто перетасовав один раз и посмотрев на результат, вы не получите абсолютно никакой информации о случайности ваших алгоритмов перетасовки.Дважды — и информации больше, три — еще больше…
Как бы вы в «черном ящике» проверили алгоритм перетасовки на случайность?
Решение
Статистика.Де-факто стандартом тестирования ГСЧ является Люкс «Несгибаемый» (первоначально доступно по адресу http://stat.fsu.edu/pub/diehard).Альтернативно, Энт программа предоставляет тесты, которые проще интерпретировать, но они менее полны.
Что касается алгоритмов перетасовки, используйте известный алгоритм, такой как Фишер-Йейтс (также известный как «Кнут Шаффл»).Перетасовка будет равномерно случайной, пока основной ГСЧ является равномерно случайным.Если вы используете Java, этот алгоритм доступен в стандартной библиотеке (см. Коллекции.shuffle).
Вероятно, для большинства приложений это не имеет значения, но имейте в виду, что большинство ГСЧ не обеспечивают достаточных степеней свободы для создания всех возможных перестановок колоды из 52 карт (поясняется). здесь).
Другие советы
Вот одна простая проверка, которую вы можете выполнить.Он использует сгенерированные случайные числа для оценки Пи.Это не доказательство случайности, но плохие ГСЧ обычно с этим не справляются (они возвращают что-то вроде 2,5 или 3,8, а не ~3,14).
В идеале это был бы лишь один из многих тестов, которые вы могли бы провести для проверки случайности.
Еще кое-что, что вы можете проверить, это среднеквадратичное отклонение вывода.Ожидаемое стандартное отклонение для равномерно распределенной совокупности значений в диапазоне 0..n приближается к n/sqrt(12).
/**
* This is a rudimentary check to ensure that the output of a given RNG
* is approximately uniformly distributed. If the RNG output is not
* uniformly distributed, this method will return a poor estimate for the
* value of pi.
* @param rng The RNG to test.
* @param iterations The number of random points to generate for use in the
* calculation. This value needs to be sufficiently large in order to
* produce a reasonably accurate result (assuming the RNG is uniform).
* Less than 10,000 is not particularly useful. 100,000 should be sufficient.
* @return An approximation of pi generated using the provided RNG.
*/
public static double calculateMonteCarloValueForPi(Random rng,
int iterations)
{
// Assumes a quadrant of a circle of radius 1, bounded by a box with
// sides of length 1. The area of the square is therefore 1 square unit
// and the area of the quadrant is (pi * r^2) / 4.
int totalInsideQuadrant = 0;
// Generate the specified number of random points and count how many fall
// within the quadrant and how many do not. We expect the number of points
// in the quadrant (expressed as a fraction of the total number of points)
// to be pi/4. Therefore pi = 4 * ratio.
for (int i = 0; i < iterations; i++)
{
double x = rng.nextDouble();
double y = rng.nextDouble();
if (isInQuadrant(x, y))
{
++totalInsideQuadrant;
}
}
// From these figures we can deduce an approximate value for Pi.
return 4 * ((double) totalInsideQuadrant / iterations);
}
/**
* Uses Pythagoras' theorem to determine whether the specified coordinates
* fall within the area of the quadrant of a circle of radius 1 that is
* centered on the origin.
* @param x The x-coordinate of the point (must be between 0 and 1).
* @param y The y-coordinate of the point (must be between 0 and 1).
* @return True if the point is within the quadrant, false otherwise.
*/
private static boolean isInQuadrant(double x, double y)
{
double distance = Math.sqrt((x * x) + (y * y));
return distance <= 1;
}
Во-первых, невозможно знать наверняка, является ли определенный конечный результат «действительно случайным», поскольку, как вы указываете, возможен любой вывод.
Что можно сделать, так это взять последовательность выходных данных и сравнить различные измерения этой последовательности с тем, что более вероятно.Вы можете получить своего рода показатель уверенности в том, что алгоритм генерации работает хорошо.
Например, вы можете проверить результат 10 различных перетасовок.Присвойте каждой карте число от 0 до 51 и возьмите среднее значение карты в позиции 6 при перемешивании.Сходящееся среднее значение равно 25,5, поэтому вы будете удивлены, увидев здесь значение 1.Вы можете использовать центральную предельную теорему, чтобы получить оценку вероятности каждого среднего значения для данной позиции.
Но нам не следует останавливаться на достигнутом!Потому что этот алгоритм может быть обманут системой, которая чередует только два тасования, предназначенных для получения точного среднего значения 25,5 в каждой позиции.Как мы можем добиться большего?
Мы ожидаем равномерного распределения (равную вероятность для любой карты) в каждой позиции при разных тасованиях.Таким образом, среди 10 перетасовки мы могли бы попытаться убедиться, что выбор «выглядит равномерно». Это в основном просто уменьшенная версия оригинальной проблемы.Вы можете проверить, что стандартное отклонение выглядит разумным, что минимальное значение является разумным, а также максимальное значение.Вы также можете проверить, что другие значения, например две ближайшие карты (по нашим присвоенным номерам), также имеют смысл.
Но мы также не можем просто добавлять различные измерения, подобные этому, до бесконечности, поскольку при наличии достаточного количества статистических данных любая конкретная перетасовка по какой-то причине будет казаться крайне маловероятной (например,это одна из немногих тасовок, в которых карты X, Y, Z появляются по порядку).Итак, большой вопрос:какой набор измерений следует предпринять?Здесь я должен признать, что лучшего ответа я не знаю.Однако, если вы имеете в виду определенное приложение, вы можете выбрать хороший набор свойств/измерений для тестирования и работать с ними — похоже, именно так криптографы и поступают.
Существует много теорий по проверке случайности.Для очень простого теста алгоритма перетасовки карт вы можете сделать много перетасовок, а затем запустить тест хи-квадрат, чтобы убедиться, что вероятность того, что каждая карта выпадет в любой позиции, была одинаковой.Но это не означает, что последовательные карты не коррелируют, поэтому вам также следует провести тесты по этому поводу.
Во втором томе «Искусства компьютерного программирования» Кнута приведен ряд тестов, которые вы могли бы использовать в разделах 3.3.2 (Эмпирические тесты) и 3.3.4 (Спектральный тест), а также лежащая в их основе теория.
Перетасуйте много раз, а затем запишите результаты (если я правильно прочитал).Я помню, как видел сравнения «генераторов случайных чисел».Они просто тестируют это снова и снова, а затем отображают результаты.
Если это действительно случайный график, то график будет в основном четным.
Единственный способ проверить случайность — это написать программу, которая попытается построить прогностическую модель для проверяемых данных, а затем использовать эту модель, чтобы попытаться предсказать будущие данные, а затем показать, что неопределенность или энтропия ее предсказаний стремятся к максимуму (т.равномерное распределение) с течением времени.Конечно, вы всегда будете не уверены, уловила ли ваша модель весь необходимый контекст;Учитывая модель, всегда можно построить вторую модель, которая генерирует неслучайные данные, которые выглядят случайными по сравнению с первой.Но пока вы признаете, что орбита Плутона оказывает незначительное влияние на результаты алгоритма перетасовки, вы сможете убедиться, что его результаты являются приемлемо случайными.
Конечно, если вы сделаете это, вы также можете использовать свою модель порождающе, чтобы фактически создать нужные вам данные.И если вы это сделаете, то вы вернетесь на круги своя.
Я не полностью понимаю ваш вопрос.Ты говоришь
Предположим, у вас есть алгоритм, генерирующий случайность.Как теперь это проверить?
Что ты имеешь в виду?Если вы предполагаете, что можете генерировать случайность, нет необходимости ее проверять.
Если у вас есть хороший генератор случайных чисел, создать случайную перестановку несложно (например,Назовите свои карты 1-52.Сгенерируйте 52 случайных числа, по порядку назначая каждое из них карте, а затем отсортируйте их в соответствии с вашими 52 случайными числами).Вы не собираетесь разрушать случайность вашего хорошего ГСЧ, создавая свою перестановку.
Сложный вопрос: можете ли вы доверять своему ГСЧ? Вот пример ссылки на людей, обсуждающих эту проблему в конкретном контексте.
Тестирование 52!возможности, конечно, невозможны.Вместо этого попробуйте перетасовать меньшее количество карт, например 3, 5 и 10.Затем вы можете проверить миллиарды перетасовок и использовать гистограмму и статистический тест хи-квадрат, чтобы доказать, что каждая перестановка встречается «четное» количество раз.
Кода пока нет, поэтому копирую тестовую часть из мой ответ на исходный вопрос.
// ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout << "pos=" << j->first.first << " card=" << j->first.second
<< " freq=" << j->second << std::endl;
}
Этот код не проверяет случайность основного генератора псевдослучайных чисел.Проверка случайности ГПСЧ — это целая отрасль науки.
Для быстрой проверки вы всегда можете попробовать сжать его.Как только он не сжимается, вы можете перейти к другим тестам.
Я пробовал упорнее, но он отказывается работать в случайном порядке.Все тесты проваливаются.Это также очень утомительно, оно не позволит вам указать диапазон значений, который вы хотите, или что-то в этом роде.
Если подумать, я бы сделал что-то вроде:
Настройка (псевдокод)
// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
StatMatrix[Card.Position][Card.Number]++;
}
Это дает нам матрицу 52x52, показывающую, сколько раз карта оказывалась в определенной позиции.Повторите это большое количество раз (я бы начал с 1000, но люди, которые лучше меня разбираются в статистике, могут дать лучшее число).
Анализ матрицы
Если мы имеем идеальную случайность и выполняем тасование бесконечное количество раз, то для каждой карты и для каждой позиции количество раз, когда карта оказывалась в этой позиции, такое же, как и для любой другой карты.Сказать то же самое по-другому:
statMatrix[position][card] / numberOfShuffle = 1/52.
Поэтому я бы подсчитал, насколько мы далеки от этого числа.
