Как получить репрезентативное случайное число из набора псевдослучайных чисел?

Question

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

Answer 1

Ну, есть подход, называемый энтропийным экстрактором, который позволяет получать (хорошие) случайные числа из не совсем случайных источников.

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

Предположим, у вас есть три генератора, дающие вам по одному байту каждый, тогда равномерный вывод будет

t = X*Y + Z

, где сложение и умножение выполняются за GF (2 ⁸ ) конечное поле .

Некоторый код (Python)

def RNG1():
    return ... # single random byte

def RNG2():
    return ... # single random byte

def RNG3():
    return ... # single random byte

from pyfinite import ffield

def muRNG():
    X = RNG1()
    Y = RNG2()
    Z = RNG3()

    GF = ffield.FField(8)
    return GF.Add(GF.Multiply(X, Y), Z)

Paper где эта идея была высказана

Answer 2

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

Во-первых, мысленный эксперимент. Если вы думаете, что три значения дают больше случайности, не будет ли еще лучше? Оказывается, что если вы берете либо среднее, либо медиану из n равномерных (0,1) значений, при n → ∞ они оба сходятся к 0,5, точка. Также бывает, что замена распределений «представительной» константой, как правило, плохая идея, если вы хотите понять стохастические c системы. В качестве крайнего примера рассмотрим очереди. По мере того, как скорость поступления клиентов / организаций приближается к скорости, с которой они могут обслуживаться, сточасти c очередей в среднем постепенно увеличиваются. Однако, если распределение поступлений и услуг является постоянным, очереди остаются на нулевой длине, пока скорость поступления не превысит скорость обслуживания, и в этот момент они go до бесконечности. Когда скорости равны, очередь стохастики c будет иметь бесконечные очереди, тогда как очередь детерминированных c останется на своей первоначальной длине (обычно предполагаемой равной нулю). Бесконечность и ноль примерно настолько различны, насколько это возможно, иллюстрируя, что замена распределений в модели массового обслуживания их средствами не даст вам понимания того, как на самом деле работают очереди.

Далее, эмпирическое доказательство. Ниже гистограммы средних и средних построены из 10000 образцов трех униформ. Как вы можете видеть, они имеют разные формы распределения, но явно больше не являются однородными. Значения сгруппированы в середине и постепенно реже приближаются к конечным точкам диапазона (0,1).

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

Answer 3

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

Вы можете найти больше информации о том, как случайные числа в C ++ из этого SO? тоже: Генерация случайных чисел в C ++ 11: как генерировать, как это работает? [Закрыто] . Оказывается, случайные числа в C ++ не всегда такие случайные: Все, что вы никогда не хотели знать о C ++ random_device ; поэтому поиск хорошего способа посева, т. е. передача времени в мс до srand() и вызов rand(), может быть быстрым и грязным путем к go.