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

Перемешайте много, а затем запишите результаты (если я правильно это прочитал). Я помню, как видел сравнения «генераторов случайных чисел». Они просто тестируют это снова и снова, а затем наносят на график результаты.

Если это действительно случайный график, то в большинстве случаев он будет четным.

Единственный способ проверить случайность - написать программу, которая попытается построить прогнозирующую модель для тестируемых данных, а затем использовать эту модель, чтобы попытаться предсказать будущие данные, а затем показать, что неопределенность или энтропия ее прогнозов стремятся к максимуму (т.е. равномерному распределению) с течением времени. Конечно, вы всегда будете не уверены, охватила ли ваша модель весь необходимый контекст; учитывая модель, всегда можно будет построить вторую модель, которая генерирует неслучайные данные, которые выглядят случайными для первой. Но до тех пор, пока вы соглашаетесь с тем, что орбита Плутона имеет незначительное влияние на результаты алгоритма перетасовки, вы должны быть в состоянии убедиться, что его результаты достаточно случайны.

Конечно, если вы это сделаете, вы также можете использовать свою модель генеративно, чтобы на самом деле создать нужные вам данные. И если вы это сделаете, то вы вернетесь на круги своя.

Статистика. Фактическим стандартом для тестирования ГСЧ является Люкс Diehard (изначально доступный по адресу http://stat.fsu.edu/pub/diehard). В качестве альтернативы Ent программа предоставляет тесты, которые проще интерпретировать, но менее полны.

Что касается алгоритмов перетасовки, используйте хорошо известный алгоритм, такой как Фишер-Йейтс (он же «Knuth Shuffle»). Перемешивание будет равномерно случайным до тех пор, пока базовый ГСЧ будет равномерно случайным. Если вы используете Java, этот алгоритм доступен в стандартной библиотеке (см. Collections.shuffle).

Вероятно, это не имеет значения для большинства приложений, но имейте в виду, что большинство ГСЧ не обеспечивают достаточных степеней свободы для создания всех возможных перестановок колоды из 52 карт (объяснено здесь).

Я не полностью понимаю ваш вопрос. Ты говоришь

Assume that you have a algorithm that generates randomness. Now how do you test it?

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

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

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

Во-первых, невозможно точно узнать, является ли определенный конечный результат «действительно случайным», поскольку, как вы указываете, возможен любой выход.

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

Например, вы можете проверить результат 10 различных перемешиваний. Присвойте каждой карте номер 0-51 и возьмите среднее значение карты в позиции 6 по тасованиям. Сходящееся среднее составляет 25,5, поэтому вы будете удивлены, увидев здесь значение 1. Вы можете использовать центральную предельную теорему, чтобы оценить, насколько вероятно каждое среднее значение для данной позиции.

Но мы не должны останавливаться на достигнутом! Потому что этот алгоритм может обмануть система, которая чередует только два тасования, которые предназначены для получения точного среднего значения 25,5 для каждой позиции. Как мы можем добиться большего?

Мы ожидаем равномерного распределения (равная вероятность для любой данной карты) в каждой позиции при разных тасованиях. Таким образом, среди 10 перетасовок мы могли бы попытаться убедиться, что варианты «выглядят одинаково». По сути, это просто сокращенная версия исходной проблемы. Вы можете проверить, что стандартное отклонение выглядит разумным, что минимальное значение является разумным, а также максимальное значение. Вы также можете проверить, что другие значения, такие как две ближайшие карты (по нашим присвоенным номерам), также имеют смысл.

Но мы также не можем просто добавлять различные измерения, такие как это до бесконечности, поскольку, учитывая достаточную статистику, любая конкретная перетасовка по какой-то причине будет казаться маловероятной (например, это одна из очень немногих перетасовок, в которых карты X, Y, Z появляются в порядок). Итак, большой вопрос: какой набор измерений следует проводить? Здесь я должен признать, что не знаю лучшего ответа. Однако, если вы имеете в виду определенное приложение, вы можете выбрать хороший набор свойств / измерений для тестирования и работать с ними - похоже, именно так работают криптографы.

Существует множество теорий о проверке случайности. Для очень простого теста алгоритма перетасовки карт вы можете сделать много перетасовок, а затем запустить проверку хи-квадрат, чтобы убедиться, что вероятность того, что каждая карта окажется в любом положении, была одинаковой. Но это не проверка того, что последовательные карты не коррелированы, поэтому вы также захотите провести тесты на этом.

В томе 2 книги Кнута «Искусство компьютерного программирования» приводится ряд тестов, которые вы могли бы использовать в разделах 3.3.2 (Эмпирические тесты) и 3.3.4 (Спектральный тест), а также лежащую в их основе теорию.

Тестирование 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;    
  }

Этот код не проверяет случайность основного генератора псевдослучайных чисел. Проверка случайности ГПСЧ - это целая отрасль науки.

Вот одна простая проверка, которую вы можете выполнить. Он использует сгенерированные случайные числа для оценки Pi. Это не доказательство случайности, но плохие ГСЧ обычно не справляются с этим (они возвращают что-то вроде 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;
}

Размышляя над этим сам, я бы сделал что-то вроде:

Настройка (псевдокод)

// 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.

Я бы посчитал, насколько мы далеки от этого числа.

Для быстрой проверки вы всегда можете попробовать сжать его. Как только он не сжимается, вы можете переходить к другим тестам.

Я пробовал упорнее, но он отказывается работать в случайном порядке. Все тесты терпят неудачу. Это также действительно утомительно, он не позволяет вам указывать диапазон значений, которые вы хотите, или что-то в этом роде.