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

Имеется выборка объемом M из равномерно распределенных в диапозоне [1-N] целых чисел (M < N). Если M не слишком мало, то существует достаточно большая вероятность, что в выборке найдутся совпадающие числа.

Найти среднее количество совпадающих с кем-либо чисел. Например, в выборке 1 2 1 3 таких чисел два, 1 2 3 4 — ни одного.
Т.к. задача из реальной жизни, то вполне сойдут приближенные решения.

P.S. К сожалению, работа не позволяет мне серьезно заняться этой задачей.

Здравствуйте, MichaelP, Вы писали:

MP>Имеется выборка объемом M из равномерно распределенных в диапозоне [1-N] целых чисел (M < N). Если M не слишком мало, то существует достаточно большая вероятность, что в выборке найдутся совпадающие числа.
MP>Найти среднее количество совпадающих с кем-либо чисел.

Сам сомневаюсь, но почему бы не так?

Пусть p — вероятность того, что стоящее на 1-м месте число совпадает с каким-нибудь другим.
Тогда число различных чисел в наборе M*(1-p)
Но разделив это число на N, мы получим как раз p.

p=M*(1-p)/N

отсюда

p=M/(N+M)

а для среднего числа чисел имеющих повторы

M*p = M*M/(N+M)

При малых M и больших N стремится к нулю.
При M=N — половина чисел неуникальны.
Надо прогой проверить кому-то...

Здравствуйте, Pushkin, Вы писали:

P>p=M/(N+M)

P>а для среднего числа чисел имеющих повторы

P>M*p = M*M/(N+M)

Что-то меня смущает, что при M=1 вероятность ненулевая...

Здравствуйте, MichaelP, Вы писали:

MP>Реальная жизнь ставит иногда интересные задачи...
MP>Буквально сегодня по работе возникла.

MP>Имеется выборка объемом M из равномерно распределенных в диапозоне [1-N] целых чисел (M < N). Если M не слишком мало, то существует достаточно большая вероятность, что в выборке найдутся совпадающие числа.

MP>Найти среднее количество совпадающих с кем-либо чисел. Например, в выборке 1 2 1 3 таких чисел два, 1 2 3 4 — ни одного.

Матожидание того, что пара чисел совпадает — 1/N. Всего пар — M(M-1)/2. Итого, матожидание пар — M(M-1)/(2N).

Если тебя интересует именно кол-во неуникальных, то считать это лучше от противного. Т.е. считать число уникальных.
Вероятность, что одно число уникально равно ((N-1)/N)^(M-1) . Матожидание уникальных — M((N-1)/N)^(M-1), неуникальных — M(1-((N-1)/N)^(M-1)).

Здравствуйте, mihoshi, Вы писали:

M> M((N-1)/N)^(M-1), неуникальных — M(1-((N-1)/N)^(M-1)).

Очень похоже на верный ответ.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, mihoshi, Вы писали:

M>> M((N-1)/N)^(M-1),

отсюда следует, что для M=N>>1 доля уникальных чисел 1/e=37%
что подтверждается программным экспериментом

Здравствуйте, mihoshi, Вы писали:

M>Вероятность, что одно число уникально равно ((N-1)/N)^(M-1) . Матожидание уникальных — M((N-1)/N)^(M-1), неуникальных — M(1-((N-1)/N)^(M-1)).

Посмотрел... Подумал... Попроверял...

Теперь было бы интересно, какую-либо красивую формулировку придумать