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

Пусть у нас есть некоторая конечная последовательность чисел и мы имеем итератор, указывающий на первый элемент. Мы можем при помощи итератора посмотреть значение текущего элемента и перейти к следующему элементу. Требуется построить такой алгоритм выбора случайного элемента из этой последовательности, чтобы каждый элемент мог оказаться выбранным с равной вероятностью.

Ограничения: мы можем использовать O(1) дополнительной памяти и не можем создавать новый итератор. Можно пользоваться функцией генерации случайного числа от [0;1).

Решение:

Создадим некоторую переменную, обозначим ее — x. Будем идти по последовательности и по ходу хранить номер элемента последовательности. Пусть мы сейчас находимся на элементе номер i, нумерация с 1. С вероятностью 1/i присвоим переменной x значение текущего элемента. Чтобы сделать действие с вероятностью p можем сгенерировать случайное число в диапазоне [0;1) и если сгенерированное число меньше p, то делаем действие, иначе не делаем.

Почему это работает?

Осталось доказать несложное утверждение: в переменной x после выполненных действий может оказаться любой элемент последовательности равновероятно, то есть каждый с вероятностью 1/n, где n число элементов последовательности.

Доказательство:

Будем доказывать по индукции. Для n=1 утверждение очевидно. Предположим, что утверждение верно для n=k, докажем его для n=k+1. После того, как мы выполним указанные действия для k первых элементов в переменной x находится одно из k чисел равновероятно, то есть с вероятностью 1/k каждое, по предположению индукции. После обработки (k+1)-го элемента вероятность того что в переменной x находится (k+1)-й элемент – 1/(k+1). Следовательно, вероятность того что в переменной x находится не (k+1)-й элемент – k/(k+1), а поскольку все k первых элементов были сохранены в переменной x равновероятно до обработки (k+1)-го элемента, то вероятность появления в переменной x любого из первых k элементов 1/(k+1). Таким образом утверждение доказано.

Если вам понравилась эта задачка, возможно, вам также понравится:

• Вы должны выбрать одну из двух ставок. При первом варианте вы должны забросить баскетбольный мяч в корзину. Если попадёте, то получите 50 тыс. рублей. Во втором варианте вам надо попасть два раза из трёх бросков, и тогда вы также получите те же 50 тыс. рублей. Какой из этих вариантов вы предпочтёте?
  Разбор решения