OberonCore

Так это одно и тоже: N!/N^N = (N-1)! * (1/N)^(N-1)

Так, ну их распределения, работаем с матожиданиями.
Пусть X(k) - количество совпадений.
X(1) =0.
X(k+1)= X(k)+(k-X(k))/n = X(k)(1-1/n)+k/n.
Разворачиваем и подставляем k=n.

X(n)=SUM(k/n*(1 - 1/n)^(n - k - 2), k= 1..n-1) = n*(1 - 1/n)^(n-1).

lim X(n)/n = 1/e.

Действительно.

Численный эксперимент для N=25, 50, 100 и 200. Распределение количества разных N случайных чисел из диапазона 1..N. Горизонтальная ось отнормирована на N, так что всё кучкуется к 0.63. Нормировка по вертикальной оси у меня хромает, её не уточняю.

Очень интересно!
У меня подтверждается опытным путем на другой задаче.
Есть решетка размером L*L. Случайным образом очередные координаты узла. L > 1000 всегда.
Опытным путем я отловил, что примерно до 0.6 можно особо не заморачиваться проверками на совпадение.
А вот после...
При том, что в качестве датчика случайных чисел использовался вихрь Мерсенна.
Спасибо за формулу!

Хотелось бы уточнить, есть ли возражения?
В случае если генерим N раз случайное число из диапазона 1..N то,
1. для любого из чисел 1..N вероятность того, что ни разу оно не выпадет будет выражаться формулой
((N-1)/N)^N или (1-(1/N))^N (кому как нравится)
и сразу же следует
2. отношения мат.ожидания кол-ва ни разу не выпавших чисел к N или, в другой формулировке,
отношения мат.ожидания кол-ва повторных выпадений чисел к N
будет выражаться той же самой формулой.
Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений.

Только помогите разобраться в формулировке: вероятность того, что оно ни разу не выпадет.
Вероятность выпадения любого числа из N равна 1/N - это очевидно.
Тогда вероятность невыпадения равна 1-1/N - я правильно рассуждаю?

Если вопрос ко мне, то - да ( при единичном "бросании")
N раз не выпало -соответственно в степени N

Ну, в степени - это понятно. Потом к пределу - и имеем отличное число 1/e
Спасибо!

Тогда получается, что вероятность НЕ повторения равна 0.36 (1/е), а вероятность повторения - 0.63.
А должно быть вроде наоборот по сообщениям Сергея.
Или я где-то не догоняю?
Ага!
Вероятность выпадения первых N неповторяющихся чисел P(N) = N!/N^N.
Или не так?

Надо разделить ситуации, итоговую, так сказать, и моментальную.
Если очень огрубить, то после 100 бросаний имеем 63 выпавших различных числа, 37 ни разу не выпавших ( а значит столько же повторов)
а вот если делать 101 бросок, то вероятность повтора в этом броске будет 0.63.
Сразу оговорюсь, я не мат.спец и потому все мои объяснения носят рабоче-крестьянский характер
PS.
это при N=100

Большое спасибо!
Но спецов хотелось бы послушать.
Иначе мои рабоче-крестьянские мозги в раскоряку: из 100 бросков выпало 63 и НЕ выпало 37! Это как?...
Может быть? потому, что считаем из N >> 100?

Это спасибо С.Губанову.

Не совсем.
Это было ответвление в теме. А какова вероятность, что все числа из диапазона 1..N будут различными при N бросаниях"

Рассматриваем генерацию N случайных чисел из диапазона 1..N
Некоторые числа из диапазона ни разу не сгенерились, некоторые один раз, а некоторые больше чем один раз.
Если в итоге K чисел (различных) ни разу не появились, то такое же кол-во K каких то других чисел были сгенерированы более чем один раз (повторы).
Для любого из N чисел можно утверждать, что вероятность того, что это число ни разу не будет сгенерировано равна (1-(1/N))^N
Помножив на N можно получить мат.ожидание (M) кол-ва ни разу не сгенерированных чисел (или повторов).
Или , в другом варианте того же, имеем формулу: отношение M/N=(1-(1/N))^N
Я понимаю, что здесь может быть нужны более строгие рассуждения, но это удел других людей.
Ну а насчет приведённых конкретных кол-в (63 и 37 в случае когда N=100) так это же что-то вроде упрощения (=вульгаризация).
Кстати, в случае N=2, мат.ожидание кол-ва повторов будет = 1/2
PS.
Чувствую, что время моё уже давно истекло, имеется явный перебор.
А что скажет начальник транспортного цеха?

Кажись дошло.
0.63 - это вероятность того, что среди первых 100 чисел не более 63 уникальных.

Боюсь, что не так.
В другой формулировке: вероятность того,что кол-во уникальных чисел не превысит мат.ожидание, даст другую величину (слёту ставлю на 1/2, но могу ошибаться, естественно)

Присоединяюсь.

Я так понимаю, что для диапазона 1..100 при генерации 100 случайных чисел наиболее вероятно, что 63 будет уникальных, и 37 повторятся. 0.63 - это наиболее вероятная доля уникальных чисел. Вероятность того, что доля уникальных чисел будет больше или меньше 63% сильно падает при удалении от этого значения. Т.е. вероятность получить 60% или 70% уникальных числе будет ниже, чем вероятность получить 63%.

Например, очень низка вероятность того, что все числа будут уникальными, или, наоборот, что все числа совпадут. Или что каждое число будет равно номеру броска (сначала выпало 1, затем 2 и т.д.). В общем, чем жёстче условия на последовательность, тем меньше вероятность соответствия ей, и вероятности эти надо по-разному высчитывать.

Вероятность появления любой конкретной последовательности чисел одинакова и равна (1/N)^N
PS.
Это только для уточнения, что равновероятно к примеру выпадение конкретного числа N раз и выпадение последовательности 1,2,3 ... N