Вероятность про урну с нумерованными шарами

[Yadryara]

mihaild в сообщении #1661366 писал(а):

Но я всё еще не понимаю, что вы считаете.

А я не понимаю кому задан вопрос. Но отвечу.

mihaild в сообщении #1661366 писал(а):

Вы считаете, что у вас число шаров на интервале $[1, n]$ распределено (примерно) нормально

Разве ж оно может быть нормальным? Вот об этом разве можно забывать:

mihaild в сообщении #1661275 писал(а):

Если $I(n)$ - индикатор "$n$ является началом кортежа", то она переформулируется в $I(n) \sim \frac{1}{\log^{k} n}$ (где $\sim$ понимается в некотором очень странном смысле).

Наш белый шар — это кортеж из 19 простых чисел, стало быть и степень 19-я:

$I(n) \sim \frac{1}{\log^{19} n}$

[vicvolf]

mihaild в сообщении #1661366 писал(а):

Неравенство Чебышева для нормального распределения очень грубое - оно верно уже для распределений с плотностью, убывающей как $1/x^3$, а для
$1/\exp(x^2)$ оценка сильно лучше.

Разговор зашел о неравенстве Чебышева после моего ответа на сообщение:

Dmitriy40 в сообщении #1661291 писал(а):

Как раз с логарифмом там совсем беда, для начального отрезка мат.ожидание (результат гипотезы) улетает в космос, в триллионы штук для интервала 1...10 например. Это очевидно бред артефакт. Но мы придумали как с ним бороться: пользуемся свойством интеграла суммы и разбиваем интервал на два, начальный до скажем $10^{2\ldots20}$ и остальной докуда нам надо, и априори считаем что в первом интервале интеграл равен строго нулю, а не сколько выдаёт гипотеза. Мы же проверили первый интервал и убедились что количество там именно нулевое, так что имеем право. Но это безусловно хак. Зато работает.

При малом количестве кортежей, вообще не надо говорить о предельном распределении. Вам известны мат. ожидание и среднее квадратичное отклонение, поэтому для определения вероятности отклонения количества кортежей от мат. ожидания лучше использовать формулу Чебышева. Вероятность отклонения от мат. ожидания в $3\sigma$ в этом случае будет $0,89$, а $4\sigma$ - $0,94$.

[Dmitriy40]

mihaild в сообщении #1661366 писал(а):

Но я всё еще не понимаю, что вы считаете.

Да мы и сами не понимаем. И что считаем, и что хотим посчитать. Тема во многом об этом.
Вообще конечно хотим оценить время до нахождения первого белого шара (фактически его номер). Но из параметров задачи знаем только про нормальность распределения случайной величины (если честно не вполне уверен чего именно), её мат.ожидание и её же стандартное отклонение (оно же СКО?). Мат.ожидание из первой гипотезы Харди-Литтвуда, остальное видимо доказал vicvolf.

mihaild в сообщении #1661366 писал(а):

Вы считаете, что у вас число шаров на интервале $[1, n]$ распределено (примерно) нормально с параметрами $\mu_n, \sigma_n$ и хотите посчитать вероятность того, что будет хотя бы один шар? Она равна $\frac{1}{2} - \frac{1}{2}\operatorname{erf}\left(\frac{1 - \mu_n}{\sqrt 2 \sigma_n}\right)$ (и ничего про отрезки говорить не нужно).

Тут как понимаю проблема в том что $\mu_n$ (это же мат.ожидание?) зависит от $n$. А что такое $\sigma_n$ вообще не понял, величина стандартного отклонения что ли? Так она же и так на число домножается, зачем ей индекс $n$, или это уже домноженное значение (т.е. величина отклонения в одну сигму)? Тогда да, и оно тоже зависит от $n$.
Формула кстати ну очень похожа на ту что я объяснял выше словами, может даже идентична, только я её чуть по другому считал.

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

Разве ж оно может быть нормальным?

Конечно может. Если мы считаем количество шаров на интервале случайной величиной (пока не проверили интервал и не узнали точное значение). И её распределение нормально. А мат.ожидание её значения даёт ХЛ1. А метод вычисления величины 1 сигмы - vicvolf.
И да, степень логарифма 19, это понятно. И да, количество именно так и должно падать. На единицу интервала! Ну или на одно число (единичный интервал). Не на весь интервал. Это же просто вероятность конкретному числу быть нашим решением (как $1/\ln(n)$ вероятность числу быть простым). Да, она падает. Но мы же берём каждый раз всё больше и больше интервал и потому несмотря на падение вероятности для каждого числа (как логарифм в минус 19 степени) общая сумма для всех чисел интервала (т.е. фактически интеграл) растёт. Что и видим из ХЛ1, в котором именно оно и считается, просто с очень хитрой константой.

-- 13.11.2024, 16:36 --

vicvolf в сообщении #1661373 писал(а):

Вероятность отклонения от мат. ожидания в $3\sigma$ в этом случае будет $0,89$, а $4\sigma$ - $0,94$.

А формулу? $\operatorname{erf}$ в PARI есть, а как это считать?
И обоснования так и не понял. То у вас всё нормально распределено, то формула Чебышева, то малое количество кортежей, хотя мы его не знаем и как раз и пытаемся подсчитать. Путаница.

[mihaild]

Dmitriy40 в сообщении #1661375 писал(а):

Но из параметров задачи знаем только про нормальность распределения случайной величины

Вот я тоже не понимаю. Речь то о числе шаров, то об отдельных шарах. И еще вероятностное пространство меняется.

Результаты про нормальность, насколько я понимаю, имеют вид "если взять очень большой отрезок, и в нем взять случайный подотрезок, все еще большой, но гораздо меньше исходного, то распределение величины "количество хороших чисел на подотрезке" примерно нормальное". В этом результат?

Dmitriy40 в сообщении #1661375 писал(а):

Тут как понимаю проблема в том что $\mu_n$ (это же мат.ожидание?) зависит от $n$. А что такое $\sigma_n$ вообще не понял, величина стандартного отклонения что ли?

Да, стандартная параметризация нормального распределения.

[vicvolf]

Dmitriy40 в сообщении #1661375 писал(а):

$\operatorname{erf}$ в PARI есть, а как это считать?

vicvolf в сообщении #1661363 писал(а):

Пусть $X$ - случайная величина, $a$ - ее мат. ожидание, $\sigma$ - среднее квадратичное отклонение и $k>0$, тогда вероятность по формуле Чебышева - $P(|X-a| \leq k\sigma) \geq 1-1/k^2$.

Я уже писал формулу. Вероятность равна $1-1/k^2$

Цитата:

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

Когда количество кортежей на интервале очень большое, то можно говорить о близости распределения кортежей к предельному распределению. А когда количество кортежей на интервале мало, например Вы говорили - 14 кортежей, то нельзя говорить о близости к предельному распределению. В этом случае лучше говорить о неравенстве Чебышева, которое не зависит от вида распределения.
Я уже говорил, что количество кортежей на интервале является арифметической функцией, поэтому, на указанном в другой теме вероятностном пространстве, можно говорить о мат. ожидании, дисперсии, среднем квадратичном отклонении соответствующей случайной величины. Поэтому по неравенству Чебышева можно подсчитать вероятность попадания случайной величины количества кортежей - $X$ в интервал: $a-k\sigma \leq X \leq a+k\sigma$ по формуле $1-1/k^2$.

[Dmitriy40]

mihaild в сообщении #1661377 писал(а):

Вот я тоже не понимаю. Речь то о числе шаров, то об отдельных шарах. И еще вероятностное пространство меняется.

Про вероятностное пространство я ничего не знаю. Если оно идентично пространству/множеству возможных исходов - дело другое.
Давайте я попробую по аналогии пояснить.
Вот есть вероятность произвольно взятому натуральному числу $x$ быть простым, $p=1/\ln(x)$. Вроде бы пока никаких сложностей не возникает, хоть простые числа и не случайные и для любого натурального числа вероятность или 1 или 0, строго. Или возникает?
Если я всё правильно понял, то первая гипотеза Харди-Литтвуда (далее везде ХЛ1, надоело полностью именовать) утверждает что для некоего кортежа из чисел начиная с числа $x$ (т.е. последовательность чисел с заданными свойствами, не суть какими именно) данная вероятность равна $C/\ln^{19}(x)$ (и $C$ (смысл слова "равна" обсуждать не хотелось бы, ведь расчёты хорошо совпадают с практикой) и $19$ вычисляются известно как по конкретному кортежу в зависимости от его свойств). Т.е. ткнув в произвольное натуральное число $x$ мы с вот этой вероятностью обнаружим что оно нам подходит (является белым шаром, искомым кортежем). Пока всё тоже вроде корректно?
Если же хотим узнать сколько таких чисел на интервале длиной $n$ чисел, то берём интеграл от этой вероятности по интервалу (почему вместо дискретной суммы не вполне ясно, но такое часто в теории чисел, так что верю). Как и для простых чисел. И получаем то что выше называю мат.ожиданием количества подходящих чисел (белых шаров) на интервале $n$.
Точным значением вместо мат.ожидания оно никак быть не может, мы же складываем/интегрируем вероятности. И должны получить или вероятность оказаться на взятом интервале подходящих чисел, или их количеству (не точному, а в смысле мат.ожидания). Вычисления дают цифры больше 1, значит это точно не вероятность. Значит мат.ожидание количества.
Значит само количество на интервале является случайной величиной в каком-то смысле ... Наверное.
Где тут вероятностное пространство или пространство исходов неясно.
Однако вычисления показывают что число посчитанное по ХЛ1 хорошо совпадает с реальным количеством кортежей в интервале, для разных кортежей и интервалов. Не идеально, но хорошо. И чем больше интервал и количество кортежей, тем лучше совпадает. Выходит если где и ошибаюсь с терминами, то расчёт происходит всё равно более-менее верный. По крайней мере про количество кортежей на любом интервале по ХЛ1.

А теперь хотим оценить какой интервал надо взять чтобы обнаружить заданный кортеж. Но раз не знаем их точное количество ни на одном интервале (знаем только где их точно нет), то и о точном интервале речи не идёт. Тогда видимо речь может идти лишь о вероятности нахождения кортежа в интервале. И соответственно об интервале на котором эта вероятность выше заданного порога. Для этого можем посчитать его мат.ожидание по ХЛ1 для любого интервала, из него можем получить СКО (если верим vicvolf-у и о нормальности чего-то там и об вычислении СКО, проверить это мне/нам нереально), а вот как из этого получить интервал или вероятность нахождения в заданном интервале - непонятно, это и вопрос темы.
Разные пространства снова неясно где тут искать.
Хотя нет, и урна, и кубик, и вон та модель с кучей $C_a^b$ вроде как задают пространство исходов, его найти легче вероятностного (конечно если они разные).

vicvolf в сообщении #1661385 писал(а):

Поэтому по неравенству Чебышева можно подсчитать вероятность попадания случайной величины количества кортежей - $X$ в интервал: $a-k\sigma \leq X \leq a+k\sigma$ по формуле $1-1/k^2$.

Прекрасно, это уже 5-й вариант вычисления вероятности. Для $n=67\#: a=0.5, \sigma=0.7$ если я правильно понимаю Ваши обозначения, как подсчитать вероятность для интервала $1 \le X \le 10^{24}$ (т.е. что будет найден хотя бы один)? Такая вероятность пока ещё (несколько недель) точно больше нуля, так что вопрос правомерен.

-- 13.11.2024, 19:43 --

vicvolf в сообщении #1661385 писал(а):

А когда количество кортежей на интервале мало, например Вы говорили - 14 кортежей, то нельзя говорить о близости к предельному распределению.

Это тоже непонятно, что значит мало или велико, ведь для множества других кортежей и интервалов совпадение реального количества с количеством (мат.ожиданием количества) по ХЛ1 достаточно хорошее, хотя кортежей тоже мало в вашем смысле. Вы вообще отказывали ХЛ1 в применении пока количество кортежей не превысит сильно начального выброса в полтора миллиарда кортежей. Повторяется та же история что ли? Но нас не интересуют числа далеко за горизонтом и тем более на бесконечности, мы не теорему доказываем, а пытаемся оценить потребное время работы компов. Как можем.

-- 13.11.2024, 20:01 --

Dmitriy40 в сообщении #1661387 писал(а):

Для $n=67\#: a=0.5, \sigma=0.7$ если я правильно понимаю Ваши обозначения, как подсчитать вероятность для интервала $1 \le X \le 10^{24}$ (т.е. что будет найден хотя бы один)?

Впрочем дайте догадаюсь: раз интересует лишь одна граница, то посчитаем вероятность что $X \le 1$ (т.е. что она ближе к мат.ожиданию чем правая граница), вычтем её из 1 (получим вероятность что значение дальше границы в любую сторону) и поделим пополам чтобы взять только правый хвост. ОК, считаем: $1=a+k \sigma = 0.5 + 0.7 k$, тогда $k=0.7 \to P=(1-(1-1/k^2))/2=(1-(1-1/0.7^2))/2=1.02$. Вероятность больше $1$ (более точное значение $1.06$)?! А вероятность обоих хвостов больше $2$?! Вместо десятка процентов? Поясняйте плиз.

[vicvolf]

Dmitriy40 в сообщении #1661387 писал(а):

Для $n=67\#: a=0.5, \sigma=0.7$ если я правильно понимаю Ваши обозначения, как подсчитать вероятность для интервала $1 \le X \le 10^{24}$ Поясняйте плиз.

Я обозначил $X$ не интервал, а случайную величину количества кортежей. А неравенство Чебышева надо читать так - вероятность отклонения случайной величины $X$ от мат. ожидания $a$ на величину $k\sigma$ больше или равна $P=1-1/k^2$.
Например, в нашем случае для $k=2$, вероятность, что количество кортежей на интервале $n \leq 10^{24}$ будет от $0$ до $0,5+2 \cdot 0,7=1,9$, больше или равна $P=1-1/2^2=0,75$.

[Yadryara]

А теперь уже, видимо, Вы не поняли. Матожидание равно 0.51 штуки не на $0-10^{24}$, а на интервале $0-67\#$, при этом $67\#\approx 7.858\cdot 10^{24}$

Это раз. Нам нужна вероятность, что найдётся хотя бы один кортеж. Это два. Считаем:

$$0.511+0.684 \cdot 0.715\approx 1.000$$

Нас интересует правая часть, то есть та, где кортежей не меньше единицы. Но $k$, как видите получилось меньше единицы (0.684). Значит нельзя применять формулу Чебышёва?

[mihaild]

Dmitriy40 в сообщении #1661387 писал(а):

Вот есть вероятность произвольно взятому натуральному числу $x$ быть простым, $p=1/\ln(x)$. Вроде бы пока никаких сложностей не возникает, хоть простые числа и не случайные и для любого натурального числа вероятность или 1 или 0, строго. Или возникает?

Возникает. Потому что прежде чем говорить о вероятности, нужно сказать, какое у нас вообще множество исходов.
Можно сказать следующее: мы равномерно выбираем случайное число $x$ из отрезка $[1, N]$, $N$ большое. Тогда $P(x \in P | x \leq k) \approx \frac{1}{\ln k}$.
Поскольку логарифм растет медленно, то можно брать отрезок не $[1, N]$, а $[N, 2N]$ и получится примерно то же самое.

Dmitriy40 в сообщении #1661387 писал(а):

Если же хотим узнать сколько таких чисел на интервале длиной $n$ чисел, то берём интеграл от этой вероятности по интервалу (почему вместо дискретной суммы не вполне ясно, но такое часто в теории чисел, так что верю).

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

Dmitriy40 в сообщении #1661387 писал(а):

Точным значением вместо мат.ожидания оно никак быть не может, мы же складываем/интегрируем вероятности

Так эти вероятности как раз получены обратным процессом - из асимптотики количества хороших чисел на начальном интервале.

Dmitriy40 в сообщении #1661387 писал(а):

Значит само количество на интервале является случайной величиной в каком-то смысле

Нет. Потому что никакого распределения самих интервалов нет. А чтобы говорить об ожидании количества чисел на интервале, нужно, чтобы можно было говорить о вероятности получить интервал $[42, 666]$.

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

Значит нельзя применять формулу Чебышёва?

Можно, только её нужно правильно записать.

vicvolf в сообщении #1661363 писал(а):

$P(|X-a| \leq k\sigma) \geq 1-1/k^2$.

При $k < 1$ неравенство Чебышева говорит, что вероятность больше некоторого отрицательного числа. Что всё еще верно, хотя и не очень полезно.

[vicvolf]

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

Нас интересует правая часть, то есть та, где кортежей не меньше единицы.

Вам нужна другая формула Чебышева (см. здесь https://ru.wikipedia.org/wiki/%D0%9D%D0 ... 0%B2%D0%B0
Вас интересует правый хвост больше 1. Не забудьте разделить пополам (эта вероятность всегда меньше 0,5).

[Dmitriy40]

vicvolf в сообщении #1661412 писал(а):

Вам нужна другая формула Чебышева (см. здесь https://ru.wikipedia.org/wiki/%D0%9D%D0 ... 0%B2%D0%B0

Если Вы про $P(|X-\mu| \ge a) \le \sigma^2 / a^2$, то это ровно та же формула, дающая столь же бессмысленный ответ для $\mu=0.5112, \sigma=0.715, a=1-\mu, P=2.14$ (для двух хвостов, но и её половина $P/2>1$, а никакая вероятность не должна быть больше $1$). Так про какую другую формулу Вы?

[mihaild]

Dmitriy40 в сообщении #1661421 писал(а):

$P=2.14$

Там же неравенство, $P \leq 2.14$. С чем вряд ли кто-то будет спорить.

Но скорее всего имелся в виду вариант из теории меры. Если величина неотрицательна (а вроде у вас так), то $P(X \geq 1) \leq \mu$. Что собственно я выше писал

mihaild в сообщении #1661257 писал(а):

Уж точно среднее число шаров больше вероятности вытащить хотя бы один

[Dmitriy40]

mihaild в сообщении #1661411 писал(а):

Можно сказать следующее: мы равномерно выбираем случайное число $x$ из отрезка $[1, N]$, $N$ большое. Тогда $P(x \in P | x \leq k) \approx \frac{1}{\ln k}$.

Простите, а зачем упоминание отрезка $[1,N]$ если он в формуле не используется?

mihaild в сообщении #1661411 писал(а):

Так эти вероятности как раз получены обратным процессом - из асимптотики количества хороших чисел на начальном интервале.

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

mihaild в сообщении #1661411 писал(а):

Нет. Потому что никакого распределения самих интервалов нет. А чтобы говорить об ожидании количества чисел на интервале, нужно, чтобы можно было говорить о вероятности получить интервал $[42, 666]$.

Ну то есть гипотеза ХЛ1 снова выдаёт не мат.ожидание. Как так то?! Я понимаю что Вы сами себе не противоречите, но каждый раз смысл величины, которую только и можем мы посчитать, почему-то меняется. И непонятно имеем ли мы право считать то, что хорошо согласуется с опытом.

mihaild в сообщении #1661423 писал(а):

Там же неравенство, $P \leq 2.14$. С чем вряд ли кто-то будет спорить.

Ну да. Только какой в этом практический смысл?! Никакого.

mihaild в сообщении #1661423 писал(а):

Если величина неотрицательна (а вроде у вас так), то $P(X \geq 1) \leq \mu$.

Простите, это конечно интереснее, но практического смысла тоже ноль: снизу то она не ограничена (кроме нуля), может и одной стомиллионной быть - ну и как оценивать потребное время работы компов?

vicvolf
Эти два вопросам к Вам, зачем нам неравенство Чебышева, которое вообще ничего не даёт для ответа на нужный вопрос?!
А ещё, если возьмём $\mu=1$ и попытаемся оценить вероятность всей правой половины распределения $X \ge 1$, то получим деление на ноль ($a=0$). Великолепно! Понятно что вероятность можно считать бесконечной (больше любого числа), но как-то это ...

[mihaild]

Dmitriy40 в сообщении #1661427 писал(а):

ростите, а зачем упоминание отрезка $[1,N]$ если он в формуле не используется?

Он используется. В букве $P$.
(которой я удачно обозначил и вероятность, и множество простых чисел, дальше буду писать для вероятности $\mathcal P_N$)
Т.е. $\mathcal P_N(x \in P | x \leq k)$ это на самом деле $\frac{\mu_N(P)}{\mu_N([1, k])}$, где $\mu_N(X) = \frac{|X \cap \overline{1, N}|}{N}$. И выкинуть $N$ из $\mathcal P_N$ нельзя, никакого "естественного" распределения на натуральных чисел нет.
Прежде чем спрашивать, с какой вероятностью случайное натуральное число окажется простым, нужно ответить, с какой вероятностью случайное натуральное число окажется равным $42$.

Dmitriy40 в сообщении #1661427 писал(а):

Ну то есть гипотеза ХЛ1 снова выдаёт не мат.ожидание. Как так то?

Она выдает, в некотором смысле, последовательность мат. ожиданий. А именно, она говорит, что если на отрезке $[1, N]$ ввести равномерное распределение и случайную величину $f_N(x) = \frac{1}{\ln^{k+1}(x)}$, то доля хороших чисел на отрезке примерно равна мат. ожиданию этой величины. Это строго.
А дальше предыдущее утверждение творчески интерпретируется как "вероятность случайного числа оказаться хорошим", хотя это некорректно, потому что гипотеза - она не про вероятность, а про последовательность вероятностей, причем в разных пространствах.
Хотя вроде бы и берется она из таких же соображений - что для больших отрезков, события "$x + k_i$ простое" и события "$x \equiv t \pmod p$" (тут $x$ выбирается равномерно из отрезка, $k_i$ фиксированы, $p$ пробегает все простые числа) примерно независимы в совокупности, при условии что $t + k_i \neq 0 \pmod p$.

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

Dmitriy40 в сообщении #1661427 писал(а):

ну и как оценивать потребное время работы компов?

А что Вы хотите найти? Хороший кортеж?

[Dmitriy40]

mihaild в сообщении #1661436 писал(а):

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

Не принципиально, по контексту понятно.

mihaild в сообщении #1661436 писал(а):

Говорит гипотеза, в конечном итоге, сколько примерно хороших чисел мы найдем на больших интервалах.

Ну так это и нужно, сколько чисел на интервале (с оговорками). После этого применяем доказательства vicvolf-а что распределение чего-то там нормальное с параметрами мат.ожидание равно вот этому примерному количеству и СКО известно как вычисляемому. Т.е. считаем что распределение нормальное с известными параметрами $\mu(n), \sigma(n)$.
И ставим вопрос какое надо взять $n$ чтобы получить вероятность попадания количества $X$ в диапазон $[a,b]$ в заданных (и разумных) границах. Или какова эта вероятность для заданных $n,a,b$. При условии что $\mu(n), \sigma(n)$ мы можем посчитать для любого $n$. Само $n$ отсюда не вытаскивается скорее всего, но не страшно, численное решение нам в руки, всё равно $\mu(n), \sigma(n)$ тоже считаются численно.

mihaild в сообщении #1661436 писал(а):

А что Вы хотите найти? Хороший кортеж?

Нет, искомый кортеж мы и так надеюсь найдём, в этой теме вопрос как посчитать сколько нам на это потребуется времени и как сделать этот вопрос более осмысленным и тогда уже посчитать (с привлечением понятий вероятности, мат.ожидания, СКО, гипотезы ХЛ1, ещё чего-то).
Ну и попутный вопрос какая модель более адекватна процессу поиска кортежа, с урной и шарами, с кубиком (-ами), с расстановками, другая, да ещё и в разных вариантах каждая. Но это так, попутно. Я понимаю что "сначала модель потом вычисления по ней", потому и начал тему с урны, но на практике по совпадению вычислений по формуле с известными фактами можно понять какая модель более адекватна.