2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 17:37 
Нужна ли высшая математика для прикладных задач? Оказывается, нужна. Особенно если увлекаешься теорией алгоритмов. Вот задача, которая, (хотя это кажется невероятным), но имеет практическое значение, точнее, влияет на выбор переборного алгоритма.

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

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

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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 17:52 
Аватара пользователя
Skipper в сообщении #1412729 писал(а):
Одну формулу для подсчёта кажется, я сам вижу, но она длинная и никуда негодная для подсчета на калькуляторе.

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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 17:54 
Ну вроде как,

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

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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 17:59 
Аватара пользователя
Я бы взял для начала гораздо меньшие числа и поискал закономерности.

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 18:04 
Аватара пользователя
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})$
Последний множитель неправильный.

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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 18:19 
Someone в сообщении #1412739 писал(а):
Последний множитель неправильный.


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

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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 18:26 
Аватара пользователя
ozheredov в сообщении #1412740 писал(а):
неправильно понял условие задачи?
Неправильно. Была бы перестановка если бы было $N = M$.

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 18:56 
Цитата:
Ну то есть случайно выбирается $10^{12}$ чисел, из $10^{38}$ чисел. Т.е. мощность вашей выборки на $26$ порядков меньше мощности генеральной совокупности. Я правильно понял?


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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 19:08 
Skipper в сообщении #1412750 писал(а):
только слово "выбираются" здесь не совсем корректное . Они генерируются независимо от того что было раньше снегерировано.
Для такого вполне принято говорить «выбираются с возвращением».

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 19:12 
Someone в сообщении #1412739 писал(а):
то её нужно прологарифмировать, в получившейся сумме логарифмов каждый логарифм заменить по формуле $\ln(1-\alpha)=-\alpha+o(\alpha^2)$, просуммировать.


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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 19:19 
А, понял

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 19:26 
Skipper в сообщении #1412750 писал(а):
Пусть будет,
$10^{12}$ чисел, из $10^{38}$

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

 
 
 
 Re: Как посчитать вероятность всех разных чисел на промежутке?
Сообщение29.08.2019, 19:36 
wrest в сообщении #1412761 писал(а):
А ну тогда искомая вероятность получится около $ 10^{-(38-2 \cdot 12 + 1)}=10^{-15}$ плюс-минус порядок.


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

 
 
 [ Сообщений: 45 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group