К содержанию
Quantoros

Из n ключей подходит один. Сравните среднее и дисперсию числа попыток при случайном выборе с возвращением и при…

Quant ResearchУровень: ПрактикаSearch with and without replacement

Из n ключей подходит один. Сравните среднее и дисперсию числа попыток при случайном выборе с возвращением и при случайном порядке без повторений.

Подсказки
  • Определите распределения.
  • В обоих случаях считайте успешную попытку.

Ответ

С возвращением T геометрическое: E=n, Var=n(n-1). Без повторений место подходящего ключа равномерно на 1,…,n: E=(n+1)/2, Var=(n²-1)/12. Учёт прошлых неудач улучшает оба показателя.

Источник и лицензия: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы