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

Question

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

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

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

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

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

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

Answer 1

Статистика. Де-факто стандартом для тестирования ГСЧ является Diehard suite (изначально доступен на http://stat.fsu.edu/pub/diehard).. Альтернативно, программа Ent предоставляет тесты, которые проще интерпретировать, но менее полны.

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

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

Answer 8

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

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

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

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

Answer 9

Пока нет кода, поэтому я копирую и вставляю часть теста из моего ответа в исходный вопрос.

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

Этот код не проверяет случайность базового генератора псевдослучайных чисел. Проверка случайности PRNG - целая отрасль науки.

Answer 10

Тестирование 52! возможности, конечно, невозможны. Вместо этого попробуйте свой случайный порядок на меньшем количестве карточек, например на 3, 5 и 10. Затем вы можете проверить миллиарды случайных чисел и использовать гистограмму и статистический тест хи-квадрат, чтобы доказать, что каждая перестановка подходит к «четному» числу. раз.