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

Вот одна простая проверка, которую можно выполнить. Это использует сгенерированные случайные числа для оценки Pi. Это не доказательство случайности, но плохие RNGs обычно не преуспевают на нем (они возвратят что-то как 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 появляются в порядке). Таким образом, большой вопрос: который является правильным набором измерений для взятия? Здесь я должен признать, что не знаю лучший ответ. Однако при учитывании определенного приложения в виду можно выбрать хороший набор свойств/измерений, чтобы протестировать, и работать с теми - это, кажется, способ, которым шифровальщики обрабатывают вещи.

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

Объем 2 из Искусства Knuth Программирования дают много тестов, которые Вы могли использовать в разделах 3.3.2 (Эмпирические тесты) и 3.3.4 (Спектральный Тест) и теория позади них.

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

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

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

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

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

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

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

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

трудный вопрос - можно ли доверять RNG. Вот демонстрационная ссылка на людей, обсуждающих тот вопрос в определенном контексте.

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

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

Обдумывание его самостоятельно, что я сделал бы, является чем-то как:

Установка (Псевдо код)

// 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 указание, сколько раз карта закончилась в определенном положении. Повторите это большое количество времен (я запустил бы с 1 000, но люди лучше в статистике, чем я могут дать лучшее число).

Анализируют матрицу

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

statMatrix[position][card] / numberOfShuffle = 1/52.

, Таким образом, я вычислил бы, как далеко от того числа мы.