Из 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