Вероятность повторения результатов с помощью rand.Next ()

Question

Глядя на другой мой вопрос Я понял, что технически ничто не мешает этому алгоритму работать в течение бесконечного периода времени. (IE: он никогда не возвращается)

Из-за вероятности, что rand.Next(1, 100000); теоретически может генерировать одно и то же значение.

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

Код с другого вопроса:

Random rand = new Random();
List<Int32> result = new List<Int32>();
for (Int32 i = 0; i < 300; i++)
{
    Int32 curValue = rand.Next(1, 100000);
    while (result.Exists(value => value == curValue))
    {
        curValue = rand.Next(1, 100000);
    }
    result.Add(curValue);
} 

Answer 1

В ОДНОМ заданном тираже случайного числа вероятность повторения значения, легко найденного в списке результатов, составляет

P(Collision) = i * 1/100000   where i is the number of values in the list.

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

Вероятность такого «столкновения» с числами из списка несколько раз подряд составляет

P(n Collisions) = P(Collision) ^ n    
   where n is the number of times a collision happens

Это потому, что рисунки независимы.

Numerically...
   when the list is half full, i = 150 and
                 P(Collision) = 0.15% = 0.0015  and
                 P(2 Collisions) = 0.00000225
                 P(3 Collisions) - 0.000000003375
                 P(4 Collisions) = 0.0000000000050265
   when the list is all full but for the last one, i = 299 and
                 P(Collision) = 0.299% = 0.00299   and
                 P(2 Collisions) = 0.0000089401   (approx)
                 P(3 Collisions) = 0.00000002673  (approx)
                 P(4 Collisions) = 0.000000000079925  (approx)

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

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

Answer 2

Эта программа не остановится, если:

1. Выбрано случайное число, которое находится в наборе результатов
2. Это число генерирует цикл (то есть цикл) в случайном числеалгоритм генератора (все они делают)
3. Все числа в цикле уже находятся в наборе результатов

Все генераторы случайных чисел в конечном итоге возвращаются обратно в себя, из-за ограниченного числа целых чиселвозможный ==> для 32-разрядных, только 2 ^ 32 возможных значений.

«Хорошие» генераторы имеют очень большие циклы.«Плохие» алгоритмы дают короткие циклы для определенных значений.Проконсультируйтесь с Кнутом Искусство компьютерного программирования для генераторов случайных чисел.Это увлекательное чтение.

Теперь предположим, что существует цикл из (n) чисел.Для вашей программы, которая повторяется 300 раз, это означает, что (n) <= 300. Кроме того, число попыток, которые вы пытаетесь выполнить, прежде чем нажмете число в этом цикле, плюс продолжительность цикла, не должно превышать 300.Поэтому, если сначала попытаться нажать на цикл, то цикл может длиться 300.Если со второй попытки вы попадаете в цикл, он может длиться всего 299. </p>

Если предположить, что большинство алгоритмов генерации случайных чисел имеют достаточно равномерное распределение вероятностей, вероятность попадания в 300-цикл в первый раз равна (300/2 ^ 32), умноженное на вероятность наличия 300-тактного цикла (это зависит от алгоритма ранда), плюс вероятность попадания в 299-тактный цикл в первый раз (299/2 ^ 32) x вероятность наличия299-цикл и т. Д. И т. Д. И т. П.Затем сложите вторую попытку, третью попытку, вплоть до 300-й попытки (которая может быть только 1-циклом).

Теперь это предполагает, что любое число может взять на себя все 2^ 32 пространства генератора.Если вы ограничиваете его только до 100000, то, по сути, вы увеличиваете вероятность иметь более короткие циклы, потому что несколько чисел (в пространстве 2 ^ 32) могут отображаться на одно и то же число в «реальном» пространстве 100000.

В действительности, большинство алгоритмов генератора случайных чисел имеют минимальную длину цикла> 300. Реализация генератора случайных чисел, основанная на простейшем LCG (линейный конгруэнтный генератор, wikipedia ), может иметь "полныйпериод »(т.е. 2 ^ 32) с правильным выбором параметров.Поэтому можно с уверенностью сказать, что минимальная длина цикла определенно> 300. Если это так, то от алгоритма отображения генератора зависит преобразование 2 ^ 32 чисел в 100000 чисел.Хорошие картостроители не будут создавать 300-циклов, плохие картографы могут создавать короткие циклы.

Answer 3

Для PRNG вполне возможно генерировать один и тот же номер в ограниченном диапазоне при последовательных вызовах.Вероятность будет зависеть от размера в битах необработанного PRNG и метода, используемого для уменьшения этого размера до требуемого числового диапазона (в данном случае 1 - 100000).

Answer 4

Чтобы точно ответить на ваш вопрос, нет, он не очень мал, вероятность того, что он будет продолжаться в течение бесконечного периода времени, равна «0». Я говорю «есть», потому что на самом деле он стремится к 0, когда числоитерации стремятся к бесконечности.

Как сказал бы Бдарес, он будет стремиться к 0 с (1 / диапазон) ˆn, где n будет числом итераций, если мы можем предположить равномерное распределение ( this говорит, что мы вроде как можем).

Answer 5

При условии равномерного распределения (я полагаю, это не плохое предположение) вероятность получения числа n раз подряд составляет (0,00001) ^ n.