Программирование Жемчуг - алгоритм произвольного выбора

Question

Страница 120 из Programming Pearls 1-е издание представляет этот алгоритм для выбора M одинаково вероятных случайных элементов из совокупности из N целых чисел.

InitToEmpty
Size := 0
While Size < M do
  T := RandInt(1,N)
  if not Member(T)    
     Insert(T)
     Size := Size + 1

Утверждается, что ожидаемое количество тестов членов меньше2M, пока M

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

Я понимаю, что ближе MN, тем больше времени займет программа, потому что набор результатов будет иметь больше элементов, и вероятность того, что RandInt выберет существующий, будет пропорционально увеличена.

Можете ли вы помочь мне выяснить это доказательство?

Answer 1

Я не волшебник по математике, но я сделаю это с точностью. Это НЕ гарантирует, что все будет правильно.

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

http://en.wikipedia.org/wiki/Geometric_distribution

Итак, вы проводите M геометрических испытаний. Каждое испытание имеет ожидаемое значение 1 / p, поэтому потребуется 1 / p попыток получить число, которого еще нет в M. p - N минус число чисел, которое мы уже добавили из M, деленное на N (то есть, сколько не выбранных элементов / всего предметов). Таким образом, для четвертого числа p = (N -3) / N, которое является вероятностью выбора неиспользованного числа, поэтому ожидаемое количество выборов для третьего числа равно N / N-3.

Ожидаемое значение времени выполнения - все это суммируется. Так что-то вроде

E (время выполнения) = N / N + N / (N -1) + N / (N -2) ... + N / (N-M)

Теперь, если M

Спроси меня, если что-то из этого неясно. Поправьте меня, если что-то из этого не так:)

Answer 2

Скажем, мы выбрали K элементов из N. Тогда наша следующая попытка имеет вероятность (NK) / N успеха, поэтому число попыток найти K + 1-й элемент геометрически распределено со средним значением N / (NK).

Таким образом, если 2M