Задача о выборке по теории вероятности. Помогите решить.

Question

Задача о выборке по теории вероятности. Помогите решить.

Алексей Флусов Профи (732), на голосовании 5 месяцев назад

Из n различных предметов случайным образом выбирают k с возвращением. Пусть k(n) - максимальное такое k, что вероятность того, что все выбранные предметы различны, не меньше 1/3. Доказать, что при n -> бесконечности выполняется соотношение k(n) = C*n^a + o(n^a). Найти константу C и показатель a.

Answer 1

Я очень надеюсь, что правильно понял условие. Если так, то задачка на самом деле по матанализу. Итак, сначала давайте посчитаем, с какой вероятностью все выбранные k чисел будут различны. Я обозначу ее так (формула для нее получается из стандартных школьных соображений)

К сожалению, вот так сразу понять, при каких k она больше 1/3, достаточно затруднительно. Теперь, чтобы дело пошло проще, я прологарифмирую эту вероятность и разложу логарифм по формуле Маклорена до квадрата (тут k понимается каким-то фиксированным)

Эту сумму можно расклеить на две -- первая будет содержать сумму натуральных чисел j до k-1, а вторая -- их квадратов. Погрешность я оценю так: слагаемых в сумме явно не больше n, поэтому порядок роста ошибки будет явно не больше o(1/n). Тогда получаем

Ну а теперь можно спокойно искать, при каких k = k(n) этот логарифм достаточно большой. Получаем квадратное неравенство (далее [x] означает целую часть x) и его решение:

Ясно, что взятие целой части, добавление 1/2 к корню и добавление единицы и о-малого внутри корня никак не влияют на асимптотику, поэтому итого получаем