Как посчитать вероятность всех разных чисел на промежутке?

[Skipper]

Нужна ли высшая математика для прикладных задач? Оказывается, нужна. Особенно если увлекаешься теорией алгоритмов. Вот задача, которая, (хотя это кажется невероятным), но имеет практическое значение, точнее, влияет на выбор переборного алгоритма.

Сгенерируем $100$ миллиардов (т.е. $100.000.000.000$ ) рандомных чисел на отрезке от $1$ до $2^{128}$ . Это значит, что каждое генерируемое число, может оказаться равновероятно любым на этом отрезке. Вопрос - какова вероятность того, что все эти числа окажутся разными ? (если эта вероятность $P$, то $(1-P)$ - будет вероятность события, что найдётся хотя бы одна пара , чисел которые совпадут. Ну или более одной пары, тройка и т.п. варианты).

Одну формулу для подсчёта кажется, я сам вижу, но она длинная и никуда негодная для подсчета на калькуляторе. А можно ли вывести формулу, которая будет пригодна для подсчета на калькуляторе, для любых $N$ и $M$, где $N<M$, у меня в задаче $N$ это $100$ миллиардов рандомных чисел, а $M$ - это отрезок , на котором они задаются.

Заранее, спасибо.

[Yadryara]

Skipper в сообщении #1412729 писал(а):

Одну формулу для подсчёта кажется, я сам вижу, но она длинная и никуда негодная для подсчета на калькуляторе.

И всё ж таки формулу в студию, плиз. Здесь же ПР/Р.

[Skipper]

Ну вроде как,

$(1 - 1/2^{128}) \cdot (1 - 2/2^{128}) \cdot (1 - 3/2^{128}) \cdot ... \cdot (1 - 100000000000 /2^{128})$

?
И как такое посчитать на калькуляторе?

[Yadryara]

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

[Someone]

Skipper в сообщении #1412729 писал(а):

рандомных чисел

По-русски — случайных чисел.

Skipper в сообщении #1412729 писал(а):

Одну формулу для подсчёта кажется, я сам вижу, но она длинная и никуда негодная для подсчета на калькуляторе.

Раз видите, то напишите её. Если это та формула, о которой я думаю, и $N\ll M$, то её нужно прологарифмировать, в получившейся сумме логарифмов каждый логарифм заменить по формуле $\ln(1-\alpha)=-\alpha+o(\alpha^2)$, просуммировать.

-- Чт авг 29, 2019 18:06:52 --

Skipper в сообщении #1412735 писал(а):

$(1 - 1/2^{128}) \cdot (1 - 2/2^{128}) \cdot (1 - 3/2^{128}) \cdot ... \cdot (1 - 100000000000 /2^{128})$

Последний множитель неправильный.

[ozheredov]

Skipper
У вас сгенерировано некоторое количество чисел. Если они все разные, то ваша реализация -- это перестановка. Число всех перестановок факториал, вероятность получить перестановку такая же как любую другую комбинацию. Или я туплю и неправильно понял условие задачи?

[Skipper]

Someone в сообщении #1412739 писал(а):

Последний множитель неправильный.

$$(1 - 1/2^{128}) \cdot (1 - 2/2^{128}) \cdot (1 - 3/2^{128}) \cdot ... \cdot (1 - 99999999999 /2^{128})$ $

[wrest]

Ну то есть случайно выбирается $10^{12}$ чисел, из $10^{38}$ чисел. Т.е. мощность вашей выборки на $26$ порядков меньше мощности генеральной совокупности. Я правильно понял?

[mihaild]

ozheredov в сообщении #1412740 писал(а):

неправильно понял условие задачи?

Неправильно. Была бы перестановка если бы было $N = M$.

[Skipper]

Цитата:

Ну то есть случайно выбирается $10^{12}$ чисел, из $10^{38}$ чисел. Т.е. мощность вашей выборки на $26$ порядков меньше мощности генеральной совокупности. Я правильно понял?

Пусть будет,
$ $10^{12}$ чисел, из $10^{38}$ $
только слово "выбираются" здесь не совсем корректное . Они генерируются независимо от того что было раньше снегерировано. Есть даже ничтожная вероятность, что все сгенерированные $10^{12}$ чисел - окажутся одинаковыми числами.
Эта вероятность $1/10^{38}$ в $10^{12}$ степени

[arseniiv]

Skipper в сообщении #1412750 писал(а):

только слово "выбираются" здесь не совсем корректное . Они генерируются независимо от того что было раньше снегерировано.

Для такого вполне принято говорить «выбираются с возвращением».

[Skipper]

Someone в сообщении #1412739 писал(а):

то её нужно прологарифмировать, в получившейся сумме логарифмов каждый логарифм заменить по формуле $\ln(1-\alpha)=-\alpha+o(\alpha^2)$, просуммировать.

Недопонял, что именно нужно логарифмировать, и почему?

[ozheredov]

А, понял

[wrest]

Skipper в сообщении #1412750 писал(а):

Пусть будет,
$10^{12}$ чисел, из $10^{38}$

А ну тогда искомая вероятность получится около $ 10^{-(38-2 \cdot 12 + 1)}=10^{-15}$ плюс-минус порядок.

[Skipper]

wrest в сообщении #1412761 писал(а):

А ну тогда искомая вероятность получится около $ 10^{-(38-2 \cdot 12 + 1)}=10^{-15}$ плюс-минус порядок.

Почему именно такая формула?