Задачка с финалов яндекса

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

Условие
100 дверей, все изначально закрыты. Каждый ход случайно и равновероятно выбирается одна дверь. Если выбранная дверь закрыта, она открывается. Если выбранная дверь уже открыта, ничего не происходит. Требуется найтиматожидание количества ходов до момента, когда будет открыто ровно 50 дверей.

Решение
Решим более простую задачу, посчитаем ожидание количества бросков до открытия новой двери на момент, когда уже k дверей открыто. Вероятность открыть новую дверь с учетом того что k дверей открыто - p = (100 - k) / 100. Остаётся посчитать матожидания количества ходов с учетом такой вероятности. Переформулировав эти открытия дверей - это испытания бернулли, а реализуются они до того момента пока не настанет успех, а значит это геометрическое распределение, матожидание которого 1 / p = 100 / (100 - k).
Тогда можно разложить исходную величину на сумму 50 таких получившихся по линейности матожидания:
E[T] = E[T_0 + T_1 .. + T_49] = E[T_0] + E[T_1] + .. + E[T_49]
E[T] = 100 / (100 - 0) + 100 / (100 - 1) + ... + 100 / (100 - 49)
E[T] = 100 / 100 -+ 100 / 99 + ... + 100 / 51
Заметим, что если вынести 100 то в скобках останется отрезок суммы гармоничесого ряда с 51 по 100 элемент.
E[T] = 100 * (H_100 - H_50)~ 100 * ln2, где H_n— n-ое гармоническое число.

@ProdAnalysis