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

[wrest]

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

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

Ну вот как-то так... видимо, надо честно просуммировать логарифмы и увидеть что так оно примерно и есть.

[Someone]

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

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

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

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

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

и почему?

Неправильный вопрос. Правильный вопрос: зачем? Ответ: чтобы получить выражение, которое легко считается на калькуляторе.

[Skipper]

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

Раз видите, то напишите её.

Всё что я вижу, - при условии

Цитата:

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

искомая вероятность,

$$(1 - 1/10^{38}) \cdot (1 - 2/10^{38}) \cdot (1 - 3/10^{38}) \cdot ... \cdot (1 - 999999999999 /10^{38})$ $

и почему это якобы, равно

$ около $ 10^{-(38-2 \cdot 12 + 1)}=10^{-15}$ плюс-минус порядок.$

я не вижу.

[Someone]

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

и почему это якобы, равно

$ около $ 10^{-(38-2 \cdot 12 + 1)}=10^{-15}$ плюс-минус порядок.$

я не вижу.

Я же Вам написал,что нужно делать.

Кстати, только что заметил: здесь на одну девятку меньше, чем надо.

-- Чт авг 29, 2019 20:11:29 --

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

и почему это якобы, равно

около $10^{-(38-2 \cdot 12 + 1)}=10^{-15}$ плюс-минус порядок.

я не вижу.

Я же Вам написал,что нужно делать.

Кстати, только что заметил: здесь на одну девятку меньше, чем надо. И знаки доллара неправильно стоят.

[mihaild]

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

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

Неправильно. Что легко видеть, если заменить $12$ на $0$: получится, что вероятность того, что все из одного числа попарно совпадают, очень маленькая.

[Skipper]

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

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

Я такое короткое объяснение не понимаю. Мне нужно подробнее "разжевать", зачем здесь логарифмировать и что это даёт?
Я же не такой специалист по высшей математике, как вы.

[mihaild]

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

зачем здесь логарифмировать и что это даёт?

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

Ответ: чтобы получить выражение, которое легко считается на калькуляторе

Вы прологарифмируйте, напишите получившееся выражение (и выпишите его здесь). У вас там получатся какие-то логаримфы. Каждый из логарифмов запишите в виде $\ln(1 - \alpha)$, напишите явно, какие получаются $\alpha$. Потом сделайте подстановку по указанной формуле и напишите здесь, что получилось. Потом посмотрите внимательно на то, что получилось, и сравните с некоторой известной школьной формулой.

[wrest]

Skipper
Когда надо умножить много чисел, то вместо произведения можно вычислять логарифм произведения, а потом спотенцировать взад.
Логарифм произведения равен сумме логарифмов сомножителей.
Каждый логарифм в сумме логарифмов приближенно равен тому что вам написали.
Такшта считайте приближенно сумму логарифмов (по формуле арифметической прогрессии, ага), затем потенцируйте чтобы вернуться к искомому произведению.

Вы знакомы с термином "потенцировать"?

Я вот, кажись спотенцировать-то и забыл
....

(Оффтоп)

P.S. Ой, перепутал вас с Sicker-ом, смотрю, что-то не так и удивляюсь что же случилось...

[Someone]

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

Я такое короткое объяснение не понимаю. Мне нужно подробнее "разжевать", зачем здесь логарифмировать и что это даёт?
Я же не такой специалист по высшей математике, как вы.

Извините, но от "высшей математики" тут только приближённая формула для логарифма $\ln(1-\alpha)\approx-\alpha$, а всё остальное — стопроцентно школьная математика. Может быть, я сильно отстал в своём образовании от современной школы, но в мои школьные годы логарифмированию и потенциированию учили всех школьников, а не только самых выдающихся. И суммировать всякие прогрессии тоже учили всех.
Кстати, если я не ошибаюсь, в справочной информации к четырёхзначным таблицам Брадиса, которыми стандартно пользовались школьники, и приближённая формула для логарифма была.

А выкладывать полные решения простых учебных задач на этом форуме запрещено правилами.

[wrest]

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

но в мои школьные годы логарифмированию и потенциированию учили всех школьников, а не только самых выдающихся.

Так вы и логарифмическую линейку видели не только на картинках. И таблицы Брадиса...
Эх... было время...

[Skipper]

Переформулирую задачу.
Сгенерируем $(N+1)$ рандомных (случайных) чисел на отрезке от $1$ до $M$ .
$M>N$ . Это значит, что каждое генерируемое число, может оказаться равновероятно любым на этом отрезке.
Вопрос - какова вероятность того, что найдётся хотя бы одна пара, в которой числа совпадут?

----------------
Решение.
Выше выяснили, что вероятность того что - все эти числа окажутся разными равна

$P = $

$(1 - 1/M) \cdot (1 - 2/M) \cdot (1 - 3/M) \cdot ... \cdot (1 - N/M)$

Найдём логарифм этого числа $P$.

$\ln P = $

$\ln ( (1 - 1/M) \cdot (1 - 2/M) \cdot (1 - 3/M) \cdot ... \cdot (1 - N/M) ) = $

$\ln (1 - 1/M) + \ln (1 - 2/M) + \ln (1 - 3/M) + ... + \ln (1 - N/M) $

при $$N\ll M $ , все альфа очень малые, и примерно $\ln(1-\alpha)=-\alpha+o(\alpha^2)$, т.е.
$ \ln(1-\alpha)\approx-\alpha$, (проверил, так и есть), далее получаем,
$\ln P = -( 1/M + 2/M + 3/M -... + N/M ) $, и в скобках арифметическая прогрессия, с первым членом
$1/M $, и $d = 1/M$ , сумма первых $N $членов арифметической прогрессии равна
в данном случае, $N ( 1/M + N/M ) / 2 = 0.5 \cdot ( N / M + N^2 / M )$ , значит

$\ln P = - 0.5 \cdot ( N + N^2 ) / M $, и таким образом,

$P = e ^ { - 0.5 \cdot ( N + N^2 ) / M }$ , и наконец,

вероятность что найдётся хотя бы одна пара, в которой числа совпадут

$V = 1 - e ^ { - 0.5 \cdot ( N + N^2 ) / M }$ ,

Так что ли? Тогда получается,

---------------------------

при генерации $N = 100 $ миллиардов случайных чисел, если отрезок $M = 2^{128} $ , (это мат.языком примерно $340$ ундециллионов), то искомая вероятность, что найдётся хотя бы одна пара чисел которые совпадут, будет равна примерно :
$1.46936 \cdot 10^{-17} $ .

при генерации $N = 100 $ миллиардов случайных чисел, если отрезок $M = 2^{75} $ , (это примерно $37$ секстиллионов) то искомая вероятность, что найдётся хотя бы одна пара чисел которые совпадут, будет равна примерно :
$0.123$ (примерно $12.3 $ % )

Дальше, уменьшая степень двойки видим, что эти вероятности начинают стремительно расти. При генерации $N = 100 $ миллиардов случайных чисел, если отрезок $M = 2^{66} $ , (это примерно $73$ квинтиллиона) то искомая вероятность, что найдётся хотя бы одна пара чисел которые совпадут, будет равна примерно :
$0.9999999999999999999999999999962281$...

при генерации $N = 100 $ миллиардов случайных чисел, если отрезок $M = 2^{64} $ , (это мат.языком примерно $18$ квинтиллионов), то искомая вероятность, что найдётся хотя бы одна пара чисел которые совпадут, будет равна примерно :
$1 - 2.0239 \cdot 10^{-118}$ .

Последний случай вообще поражает воображение. Практически стопроцентная вероятность, что такие пары найдутся, хотя отрезок на котором числа генерируются, на много порядков больше чем количество генерируемых чисел.

Всё вроде, правильно рассчитал?

[Skipper]

Хорошую точность даёт также формула,

$V = 1 - e ^ { - 0.5 \cdot N^2 / M }$ ,

[Yadryara]

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

Всё вроде, правильно рассчитал?

А теперь попробуйте без округления $\ln(1-\alpha)\approx-\alpha$, на меньших числах. Временно оставьте в покое эти $100$ миллиардов. Внимательно посчитайте для $10$, $100$, $1000$...

[Евгений Машеров]

Замечание практическое. "Рандомные" скорее всего окажутся результатом работы ГСЧ. Вероятность того, что будет задействовать физический генератор (на тепловом шуме, распаде ядер и пр.) существует, но достаточно скромна. А наиболее популярны мультипликативные ГСЧ. Для них, и вообще для всех, для которых $x_{i+1}=f(x_i)$ существует длина периода N, которую для мультипликативных можно найти теоретически, а вообще просто определить "двойными шагами". И если длина искомой последовательности $M<N$, то вероятность нулевая, а если $M\ge N$, то единичная.

[Евгений Машеров]

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

Мне нужно подробнее "разжевать", зачем здесь логарифмировать и что это даёт?

Логарифм произведения равен сумме логарифмов слагаемых. Это упрощает жизнь, поскольку сложение проще умножения (когда считали вручную, это было настолько очевидно, что изобретатель логарифмов хвалился, что "продлил жизнь астрономов", в смысле они меньше тратили времени на вычисления; считающему на компьютере или калькуляторе может показаться, что упрощения нет, но это неверный взгляд, просто оно в другом месте, не в процедуре счёта, а в свободе работы с выражениями). В данном случае упрощение состоит в том, что можно рассмотреть вклад каждого слагаемого в отдельности, а потом просуммировать. Под логарифмом стоит величина, очень близкая к единице. Это прямо приглашает разложить $\ln(1+x)$ в ряд. Вот это уже некая "высшая математика", в смысле выход за элементарную школьную программу, но очень недалеко, даже не выход, а так, за забор заглянули. Во всяком случае, в справочниках для школьников по математике это приближение давалось (без доказательства). Оказывается, что первый член разложения попросту сам икс, а последующие - иксы во всё возрастающих степенях, и если икс мал, то последующие пренебрежимо малы.
И ограничиваясь лишь первым - получим, что логарифм этого выражения равен сумме этих маленьких частных, а они образуют арифметическую прогрессию (вот это уж точно школьный курс) и их легко просуммировать. А что получилось - потенцировать, получая из логарифма вероятности её, болезную. Сумма прогрессии квадратична по отношению к числу членов, и выражение растёт достаточно быстро, чтобы появились дубли, даже если число испытаний крайне мало сравнительно с общим числом возможных чисел. Собственно, это известный "парадокс дней рождения".
Но повторюсь - требуется "истинная случайность". Обычный ГСЧ даст либо гарантированную бесповторность, либо гарантированный повтор, в зависимости от того, как соотносятся длина получаемой последовательности и период ГСЧ. Нужен либо "физический ГСЧ", либо ГСЧ, у которого выход зависит не от одного предшествующего значения, так что возможны повторения выдаваемых чисел, но так как следующее зависит от нескольких, то повтор одного не даст повторения последующих. Приближением может быть использование не одной серии чисел, выдаваемых ГСЧ, а последовательности серий, между которыми начальная установка ГСЧ вместо того, чтобы использовать последнее ранее полученное значение, рандомизируется (это возможно и без физического "истинно случайного" генератора, а, скажем, инициализируя значениями микросекунд часов, с добавлением температуры процессора, напряжения питания и т.п. неконтролируемых параметров; впрочем, сейчас доступны и физические ГСЧ на материнской плате, порождающие "истинную случайность", но слишком медленно, чтобы использовать их непосредственно, однако пригодные для рандомизации начальных установок генераторов псевдослучайных чисел)