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

[Skipper]

Yadryara в сообщении #1412836 писал(а):

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

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

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

Ну там уже не будет эта формула точной. На меньших данных, походу, другую, более точную формулу надо использовать.
$M ! / ( M ^ N \cdot (M - N) ! ) $

При $M = 2^{128}$ , формула выше никуда не годится. Я не знаю калькулятора, который выдал бы мне значение факториала от такого числа..

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

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

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

Э, а я и круглую логарифмическую линейку видел, наподобие карманных часов, и специализированные (артиллерийский ПРК, по сути - логлинейку без движка, вместо этого штрихи карандашом ставили, и РЛ-1, одна из шкал размечена до 10 мегатрупов...)

-- 30 авг 2019, 10:49 --

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

Ну там уже не будет эта формула точной. На меньших данных, походу, другую, более точную формулу надо использовать.
$M ! / ( M ^ N \cdot (M - N) ! ) $

При $M = 2^{128}$ , формула выше никуда не годится. Я не знаю калькулятора, который выдал бы мне значение факториала от такого числа..

А уж логарифмической линейки... Вот, кстати, и польза от логарифмов помимо замены умножения сложением при ручном счёте. Они позволяют думать в терминах "порядка величины".
Формула через разложение логарифма в ряд
$\ln(1+x)=x-\frac{x^2} 2+\frac{x^3} 3-\frac{x^4} 4+\frac{x^5} 5-\cdots$
даёт понять, что относительная ошибка при ограничении первым членом будет меньше этого самого члена, то есть для данной задачи пренебрежима.
Что до расчёта через факториалы - был такой добрый человек Стирлинг, придумал замечательную формулу, потом ей и Эйлер занимался, и Гаусс, и ещё многие, но тут хватит и самого простого варианта.
$n!\approx \sqrt{2\pi n}\frac {n^n} {e^n}$
И посмотреть, что тут сокращается, и что за скобки выносится.

[Skipper]

Евгений Машеров в сообщении #1412856 писал(а):

Сумма прогрессии квадратична по отношению к числу членов, и выражение растёт достаточно быстро, чтобы появились дубли, даже если число испытаний крайне мало сравнительно с общим числом возможных чисел. Собственно, это известный "парадокс дней рождения".
Но повторюсь - требуется "истинная случайность". Обычный ГСЧ даст либо гарантированную бесповторность, либо гарантированный повтор,

Спасибо. Если интересно о практической цели данной задачи, о цель такая..

У меня переборная задача. Есть "позиция" ( игры), у которой одна стратегия перебора.
Из корневой позиции, последуют $N$ позиций, в дереве перебора "на 1-м этаже".
Из этих $N$ позиций, последуют $N \cdot M$ позиций, в дереве перебора "на 2-м этаже".
И так далее, перебор ведём в ширину, выстраивая слой за слоей, это дерево, до тех пор пока не будет найдено кратчайшее решение.

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

Такой достигается выигрыш по памяти. Позиция занимает $64$ байта. Это полная информация, которую надо хранить на последнем этаже дерева перебора, чтобы строить следующий этаж. В среднем, каждый следующий этаж больше по числу позиций всего лишь в $1.3 - 1.5$ раза от предыдущего.
Позже подумал - а зачем на все этажи выше - хранить полную информацию о каждой позиции, т.е. все $64$ байта?
Можно преобразовать это в некий более короткий хэш-код, который будет например, $16$ байт (а значит и позиций сможем хранить в $4$ раза больше, и углубится дальше по дереву перебора). Хэш-код - некая укороченная информация о позиции, которая вообще говоря, может дать коллизии, т.е. для разных позиций выдать одинаковый хэш-код. Но если этот хэш-код $16$ байт, то количество его возможных значений, равно $2^{128}$ , и даже если в процессе перебора встретятся $100$ миллиардов позиций, то вероятность хотя бы одной коллизии, как выше выяснилось, очень малая,

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

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

Но преобразование $64$ байт в хэш-код $16$ байт - должно иметь , так сказать, равновероятное распределение по всем возможным $16$-байтовым значениям. $64$-байтные значения могут совсем чуть-чуть отличаться, и недопустимо чтобы для двух таких значений, $16$-байтный хэш-код часто, тоже чуть-чуть отличался. Это вносит большое увеличение вероятности коллизий.

Поэтому, для этого, я планирую рассмотреть исходное $64$-байтное значение, просто как $ 64$-байтное длинное число.
Затем линейно-конгруэнтным методом, построить из него другое $ 64$-байтное длинное число. (уже здесь при небольшом отличии 2-х исходных чисел, допустим будут отличаться лишь в нескольких битах - два числа после преобразования линейно-конгруэнтным методом будут сильно отличаться ).
И затем каким нибудь $XOR$ - м , получу из них $16$ - байтное число, которое и может иметь $2^{128}$ разных значений.
Это и будет "extended hash Code" .

[Someone]

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

$(1 - 1/M) \cdot (1 - 2/M) \cdot (1 - 3/M) \cdot ... \cdot (1 - N/M)$
…
Всё вроде, правильно рассчитал?

Вы опять делаете ту же ошибку, на которую я Вам указывал.
Я, в свою очередь, тоже наврал в приближённой формуле: там должно быть не o-малое, а O-большое, то есть, $\ln(1-\alpha)=-\alpha+O(\alpha^2)$.
Формулу можно продолжить: $\ln(1-\alpha)=-\alpha-\frac{\alpha^2}2+O(\alpha^3)$.

[wrest]

(Евгений Машеров)

Евгений Машеров в сообщении #1412864 писал(а):

Э, а я и круглую логарифмическую линейку видел, наподобие карманных часов,

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

[Skipper]

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

Вы опять делаете ту же ошибку, на которую я Вам указывал

Эта ошибка как раз, на точность особо не влияет, потому что главный член в формуле $V = 1 - e ^ { - 0.5 \cdot ( N + N^2 ) / M }$ , - это $N^2$ а будет в числителе $+ N$ или $-N$ (что очень малое значение по сравнению с $ N^{2}$ ) , если и $N$ достаточно большое, и $N$ намного меньше чем $M$ , на точность особо не повлияет.

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

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

И насколько сильно это может повлиять если $ N = 100$ миллиардов, а $M = 2^{64}$ например?

[mihaild]

Евгений Машеров в сообщении #1412856 писал(а):

Обычный ГСЧ даст либо гарантированную бесповторность, либо гарантированный повтор, в зависимости от того, как соотносятся длина получаемой последовательности и период ГСЧ.

У ГСЧ состояние вполне может быть больше, чем размер выхода. И на практике обычно так и бывает.

[wrest]

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

И насколько сильно это может повлиять если $ N = 100$ миллиардов, а $M = 2^{64}$ например?

$2^{64} \approx 10^{19}$
100 миллиардов $=10^{11}$
Ошибка будет в примерно в 8 или 9 значащей цифре.

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

Достаточно много ГСЧ с периодом $2^{32}$ или даже $2^{31}$. А в данном случае и $2^{64}$ не спасает.
https://en.wikipedia.org/wiki/Linear_co ... _generator
Есть и с действительно большим, какой-нибудь мерсенновский твистер, но они не всеми используются.

[Someone]

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

Эта ошибка как раз, на точность особо не влияет

Это так, но ошибка должна быть исправлена. По принципиальным соображениям, а не по степени влияния. Потому что неизвестно, при каких значениях параметров формула будет использоваться в следующий раз.
По этой же причине хорошо было бы иметь оценку погрешности. В данном случае можно исходить из того, что абсолютная погрешность формулы $\ln(1-\alpha)\approx-\alpha$ при $0\leqslant\alpha<1$ оценивается сверху величиной $\frac{\alpha^2}{2(1-\alpha)}$. Погрешности для всех логарифмов нужно просуммировать. Более точную информацию даёт неравенство

$$-\alpha-\frac{\alpha^2}{2(1-\alpha)}<\ln(1-\alpha)<-\alpha\text{ при }0<\alpha<1.$$

При суммировании величину $\alpha$ в знаменателе дроби можно заменить её наибольшим значением, то есть, $\frac{N-1}M$; тогда всё сведётся к вычислению суммы квадратов (готовую формулу можно найти в справочниках).

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

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

$1.46936 \cdot 10^{-17} $ .

Кстати, наврали в $100$ раз.

[arseniiv]

Евгений Машеров
Есть варианты того же Xorshift (отличающегося тем, что его весьма просто написать на коленке), которым приписывается наибольшая длина цикла и до $2^{1024}-1$. Только они не криптографически стойкие и некоторые тесты из распространённых пакетов не проходят (конкретнее по ссылке).

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

В незапамятные времена захотел я сделать Лучший-в-Мире-Генератор-Нормально-Распределённых...
16 мультипликативных с разными периодами и все взаимно простые (как и у прочих ГСЧ). Выход подвергается простому нелинейному преобразованию, чтобы второй момент был 0.25, четвёртый 0.75, а первый и третий нули (то есть "походит на нормальное"). Генератор на сдвиговых регистрах меняет знаки, если выдаёт 1, генератор на середине квадрата даёт вспомогательную последовательность для перетасовки, затем опять сдвиговый меняет знаки, после чего преобразование Адамара - "нормализация", поскольку суммы и разности, опять знаки сдвиговым, опять тасовка, но уже ГСЧ Фибоначчи, опять смена знаков. 16 чисел. Выдаётся по одному, как кончится - опять такой же расчёт.
В общем, юноша читал 2 том Кнута с интересом и пользой, и в 3 том заглядывал ;)
Правда, особых преимуществ перед тупым Боксом-Мюллером видно не было. Но круто!

[wrest]

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

Хорошую точность даёт также формула,
$V = 1 - e ^ { - 0.5 \cdot N^2 / M }$ ,

Эту формулу можно немного преобразовать.
Из предыдущего открытия (где для близких к нулю иксов $x \ll 1$ получается что $\ln(1-x)\approx -x$), следует, что $1-x \approx e^{-x} $ и следовательно, $1-e^{-x} \approx x$, так что

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

что само по себе уже сильно упрощает оценку искомой вероятности.
Далее, пусть $N=10^n;M=10^m$
Тогда
$V \approx 0,5 \cdot N^2 / M =0,5\cdot 10^{2n }\cdot 10^{-m}$
Поскольку $\log_{10}(0,5)\approx -0,3$ (это широкоизвестная цифра например в виде "два раза это три децибела"), то $0,5\approx 10^{-0,3}$ и наконец получаем

$$V \approx 10^{2n-m-0,3}$$

Плюс-минус порядок...

Таким вот образом задачка из вида "ужос-ужос" превращается в устную

[Dmitriy40]

А интересный тест на истинную случайность получился, причём вступающий в противоречие со здравым смыслом: обнаружение повтора говорит за случайность, а не наоборот.

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

"Здравый смысл" это перенос бытового опыта в сферу вне его. Есть множество областей, в которых "здравый смысл" оказывается не просто нерабочим, а прямо обманывающим. И теория вероятностей одна из первейших в этом отношении.
Я бы посоветовал почитать Секеи, "Парадоксы в теории вероятностей и математической статистике". Крайне любопытное чтение.