Программирование жемчуга - алгоритм случайного выбора

Question

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

Установлено, что ожидаемое число испытаний членов меньше, чем 2M, до тех пор, как M < N/2.

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

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

Теперь, если M < N/2, то последний элемент этого суммирования ограничен сверху на 2. ((N/N/2) == 2)). Это также, очевидно, самый большой элемент во всем суммировании. Поэтому, если самый большой элемент - два выбора, и есть M элементов, которые суммируются, EV всего времени выполнения ограничено выше на 2M.

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

Answer 2

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

Так что если 2M < N, мы ожидаем, что он примет менее двух попыток получить каждый элемент.