Как эффективно провести ряд случайных испытаний?

Question

Допустим, событие имеет вероятность P для успеха. (0 < P < 1 ) и я должен сделать N тестов, чтобы увидеть, если это произойдет, и я хочу общее количество успехов:

Я мог бы пойти

int countSuccesses = 0;
while(N-- > 0)
{
   if(Random.NextDouble()<P) countSuccesses++; // NextDouble is from 0.0 to 1.0
}

Но нет ли более эффективного способа сделать это? Я хочу иметь одну формулу, поэтому я могу использовать ОДИН розыгрыш случайное число , чтобы определить общее количество успехов. ( РЕДАКТИРОВАТЬ Идея использования только одного розыгрыша состояла в том, чтобы получить значение ниже O (n))

Я хочу иметь возможность вызывать метод

GetSuccesses( n, P)

и это будет O (1)

UPDATE
Я постараюсь пойти с MathNet.Numerics.Distributions.Binomial.Sample(P, n) даже если он может использовать более одного случайного числа, я думаю, это будет быстрее, чем O(n), даже если это не O(1). Я сравню это. Большое спасибо Дэвиду и Ричи.

UPDATE
Биномиальный образец выше был O (n), поэтому он мне не помог. Но благодаря комментарию Фреда я просто переключился на
MathNet.Numerics.Distributions.Normal.Sample(mean, stddev) где
mean = n * P
stddev = Math.Sqrt(n * P * (1 - P)); а сейчас это O(1)!

Answer 1

@ Дэвид и @ Ричи указали мне на
MathNet.Numerics.Distributions.Binomial.Sample(P, n)
Тест показал мне, что он также O(n) и соответствует моему оригинальному

int countSuccesses = 0;
while(N-- > 0)
{
   if(Random.NextDouble()<P) countSuccesses++; // NextDouble is from 0.0 to 1.0
}

Но благодаря комментарию Фреда:

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

Я только что перешел на
MathNet.Numerics.Distributions.Normal.Sample(mean, stddev) где
mean = n * P
stddev = Math.Sqrt(n * P * (1 - P)); а теперь это O(1)!

и функция, которую я хотел, должна быть:

    private int GetSuccesses(double p, int n)
    {
        double mean = n * p;
        double stddev = Math.Sqrt(n * p * (1 - p));
        double hits = MathNet.Numerics.Distributions.Normal.Sample(Random, mean, stddev);
        return (int)Math.Round(hits, 0);
    }

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

Answer 2

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

Вероятность каждого исхода можно определить по формуле Бернулли https://en.wikipedia.org/wiki/Bernoulli_trial

Что вам нужно сделать, это рассчитать биноминальный коэффициент, тогда вычисление вероятности станет довольно простым - умножьте биноминальный коэффициент на p и q в соответствующих степенях. Заполните массив P [0..n], который содержит вероятность для каждого результата - количество именно i успехов.

После настройки перейдите от 0 до n и рассчитайте скользящую сумму вероятностей. Проверьте нижние / верхние границы для случайного значения и, как только оно окажется в текущем интервале, верните результат.

Итак, решающая часть будет выглядеть так:

sum=0;
for (int i = 0; i <= n; i++)
  if (sum-eps < R && sum+P[i]+eps > R)
    return i;
  else
    sum+=P[i];

Здесь eps - небольшое значение с плавающей запятой для преодоления проблем с округлением с плавающей запятой, R - случайное значение, P - массив вероятностей, о которых я упоминал ранее.

К сожалению, этот метод не подходит для больших N (20 или 100+):

• вы получите довольно большое влияние ошибок округления

• генератор случайных чисел может быть недостаточно детерминированным, чтобы охватить все возможные результаты с надлежащим распределением вероятностей

Answer 3

Для @rici для малых N вы можете использовать CDF или PMF биномиального распределения и просто сравнивать случайный вход с вероятностями для 0,1,2..N успехов.

Что-то вроде:

  static void Main(string[] args)
    {

        var trials = 10;
        var trialProbability = 0.25;
        for (double p = 0;  p <= 1; p += 0.01)
        {
            var i = GetSuccesses(trials, trialProbability, p);
            Console.WriteLine($"{i} Successes out of {trials} with P={trialProbability} at {p}");
        }
        Console.ReadKey();

    }
    static int GetSuccesses(int N, double P, double rand)
    {
        for (int i = 0; i <= N; i++)
        {
            var p_of_i_successes = MathNet.Numerics.Distributions.Binomial.PMF(P, N, i);
            if (p_of_i_successes >= rand)
                return i;

            rand -= p_of_i_successes;

        }
        return N;


    }

Answer 4

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

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

Даже если бы вы использовали два случайных числа, где вас ожидают одна голова и один хвост; этот тест потерпит неудачу в 50% всех случаев (потому что вы можете получить две головы или два хвоста).

---

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

LLN важен, потому что он гарантирует стабильные долгосрочные результаты для средних значений некоторых случайных событий. Например, в то время как казино может потерять деньги за одно вращение колеса рулетки, его прибыль будет стремиться к предсказуемому проценту за большое количество вращений. Любая победная серия игрока будет в конечном итоге преодолена параметрами игры. Важно помнить, что закон применяется (как видно из названия), когда рассматривается большое количество наблюдений. Нет принципа, что небольшое количество наблюдений совпадет с ожидаемым значением или что полоса одного значения будет немедленно "сбалансирована" другими (см. Ошибку игрока).

---

Когда я спросил это как комментарий; Вы ответили:

@ Flater Нет, я делаю N фактических розыгрышей, но с одним случайным числом.

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

---

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

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

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

Однако ваши явно упомянутые ожидания, похоже, опровергают это предположение. Вы хотите сделать что-то вроде:

GetSuccesses( n, P, Random.NextDouble())

и вы также ожидаете получить операцию O(1), что противоречит закону больших чисел.

Если вы на самом деле говорите об одном случайном семени; тогда ваши ожидания не верны.

• Если вы сделаете N розыгрышей, операция все равно будет иметь сложность O(N). Независимо от того, рандомизированы ли вы после каждого розыгрыша или нет, это не имеет значения, всегда O(N).
• GetSuccesses( n, P, Random.NextDouble()) даст вам одну ничью , а не одно семя . Независимо от используемой терминологии ваше ожидание кода не связано с использованием одного и того же начального числа для нескольких розыгрышей.

---

Поскольку вопрос в настоящее время сформулирован; то, что вы хотите, невозможно. Повторные комментарии для пояснения нескольких комментаторов еще не дали более четкой картины.

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