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

[Dmitriy40]

Приветствую математиков.
I need help, что называется.
Задача не учебная, чисто практическая, оценить сколько времени ещё считать одну из задач (месяцы или годы).

Итак, есть урна с белыми и чёрными шарами, ну как обычно. Общее количество шаров $M=10^{27}$ штук (все цифры буду произвольно округлять). Сколько из них белых неизвестно, пусть $W=11$шт. Все шары пронумерованы натуральными числами в случайном порядке независимо от их цвета.
Процесс выемки шаров выглядит так:
1. Не глядя вынимаем из урны случайный шар. Какое здесь должно быть распределение вероятностей по шарам я не знаю, для начала можно принять равновероятно любой из.
2. Проверяем что его номер больше$n=10^{25}$, тогда возвращаем шар в урну и возвращаемся к п.1.
3. Если вынули белый шар, то останавливаемся.
4. Иначе, шар чёрный, повторяем процесс с п.1 суммарно $n=10^{25}$ раз (да, число то же, в этом специальный смысл).
5. В результате окажутся вынуты $n$ чёрных шаров с номерами не больше $n$, или меньше если попадётся белый с номером не больше $n$.
Вопрос: какова вероятность что в результате будет вынут белый шар? И как она зависит от параметров задачи.

Если бы шары были не нумерованы и п.2 отсутствовал, то это стандартная задача из теорвера. А что делать здесь? Ведь количество шаров в урне уменьшается, соответственно растёт вероятность наткнуться на шар со слишком большим номером. С другой стороны, они не учитываются и тогда выходит ни на что не влияют?
Если бы ещё и белые шары тоже возвращали в урну и лишь по итогу вспоминали вынимали ли хоть один белый шар, то вероятность была бы $P=1-e^{-n/M}$, это более менее понятно (хотя вывести и не готов). С остановом по обнаружению белого шара задача тоже в общем стандартная и можно найти решение (или самому вывести). Но что делать с нумерованными шарами и п.2 не знаю. Подскажите?

И более важный вопрос: имеет ли вообще практический смысл полученная вероятность раз мы проводим такой опыт с урной лишь один раз? Формально нет, это понятно, а вот практически? Понятно что вынув все белый найдём, а вот насколько вероятно нахождение белого если вынуть $n=M/W$ шаров с номерами не более $n$?

PS. Только пожалуйста, не надо заставлять учить весь теорвер и иже с ним, задача не научиться решать такие примеры, а решить конкретно этот и понять как решение зависит от параметров. И сколько месяцев ещё платить за электричество для расчётов.

[waxtep]

Если я правильно понял условие, "счетчик вынутий" не увеличивается при вытаскивании шара с номером больше $n$. Но тогда Вы никогда не вытащите белый шар, если все номера белых шаров больше $n$. И гарантированно, с вероятностью единица, вытащите, если есть хотя бы один белый с малым номером, потому что переберете все $n$ шаров с малыми номерами. Что-то видимо все таки не так понял; особенно смущает шаг 4. И Вам точно нужна вероятность, или скорее среднее количество попыток до появления белого шара?

-- 11.11.2024, 21:20 --

Попробую переформулировать задачу, как ее понял:
а. Шары в непрозрачной обертке, на которой написан номер
б. Вытаскиваем - если номер на обертке больше $n$ - бросаем обратно
в. Иначе - разворачиваем; если шар белый - остановка, успех
г. Если черный - откладываем в сторонку, продолжаем; всего дается не более $n$ попыток вскрыть упаковку
д. Найти среднее количество вскрытий упаковки (или вытаскиваний?) до успеха.

Похоже или по-другому?

[mihaild]

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

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

Разными, от $1$ до $M$ или как-то иначе?

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

С другой стороны, они не учитываются и тогда выходит ни на что не влияют?

Да, можно сразу, не глядя, выкинуть из урны все шары с номерами, большими $n$.

[Dmitriy40]

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

mihaild
От $1$ до $M$.
Если можно не глядя выкинуть все шары с номерами больше $n$, то как тогда определить сколько в урне останется белых шаров $W$? Просто как $W_n=W\frac{n}{M}$? Что оно меньше 1 не смущает.
Или важно при этом распределение $W$ по $M$ и тогда как его учесть? Может ведь оказаться что все белые шары имеют номер больше $n$ и будут выкинуты. Интегралом от $1$ до $n$ вместо простой дроби?
Засада в том что это распределение, $W$ по $M$, нам в принципе неизвестно (иначе было бы выгоднее проверять не шары с номерами $1\ldots n$, а по другому, где больше белых шаров). Хотя можно построить плотность мат.ожидания $W_M$ по $M$ (или точнее зависимость мат.ожидания $W_M(1\ldots M)$), будет ли это тем же самым? Но тут гарантированно $W_M(n)<1$, но ведь это не гарантирует что таких белых шаров нет, мат.ожидание же ... Не понимаю.
На самом деле $W=11$ это тоже лишь мат.ожидание количества (с огромной дисперсией), точное значение нам пока неизвестно. И неизвестно какие номера у белых шаров. Важно ли это уточнение?

[mihaild]

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

то как тогда определить сколько в урне останется белых шаров $W$? Просто как $W_n=W\frac{n}{M}$?

Это будет случайной величиной. Вероятность того, что в урне останется хоть один белый шар, если они распределены равномерно и $W \ll n$, то попадания шаров почти независимо, и вероятность получить хотя бы один шар равна $1 - \left(1 - \frac{n}{M}\right)^W$.

[Yadryara]

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

вероятность получить хотя бы один шар равна $1 - \left(1 - \frac{n}{M}\right)^W$.

Получить = вытащить?
Один шар = один белый шар?
Это за $n$ вытаскиваний?
То есть, даже если белый шар вытащили, продолжаем вытаскивать, пока все $n$ шаров не вытащим и урна не опустеет?

[mihaild]

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

То есть, даже если белый шар вытащили, продолжаем вытаскивать, пока все $n$ шаров не вытащим и урна не опустеет?

А это неважно. Исходная задача эквивалентна "с какой вероятностью среди шаров с номерами, не превосходящими $n$, есть хоть один белый".

[Yadryara]

Попробую ещё уточнить. Допустим в урне $M$ шаров. Вероятность вытащить белый шар за одну попытку равна $\frac{W}{M}$. Но у нас в урне не $M$, а $n$ шаров. Значит вероятность вытащить белый шар ровно за одну попытку меньше в $\frac{M}{n}$ раз и равна

$$\frac{W}{M}\cdot\frac{n}{M}=\frac{Wn}{M^2}$$

Вероятность вытащить хотя бы один белый шар за две попытки

$$\frac{Wn}{M^2}+(1-\frac{Wn}{M^2})\cdot\frac{W(n-1)}{(M-1)^2}$$

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

Тут ещё вопрос: а уменьшается ли количество $M$ с каждым новым вытаскиванием? Я пока посчитал в предположении, что уменьшается.

[Yadryara]

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

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

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

Итак, у нас $W=11$, $\frac{n}{M}=\frac1{71}$.

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

вероятность получить хотя бы один шар равна $1 - \left(1 - \frac{n}{M}\right)^W$.

Подставляем:

$$1 - \left(1 - \frac{1}{71}\right)^{11}\approx 0.1455$$

Самая крошечная величина. (Ранее у нас были $0.25$, $0.32$ и $0.40$ )

Теперь считаем вероятность вытащить ровно один белый шар:

$$\frac{1^1 \cdot 70^{10}}{71^{11}}\binom{11}{1}\approx 0.1344$$

Ровно два белых шара:

$$\frac{1^2 \cdot 70^{9}}{71^{11}}\binom{11}{2}\approx 0.0096$$

Ровно три белых шара:

$$\frac{1^3 \cdot 70^{8}}{71^{11}}\binom{11}{3}\approx 0.0004$$

Остальные вероятности пренебрежимо малы. Теперь считаем матожидание:

$$1\cdot0.1344 + 2\cdot0.0096 + 3\cdot0.0004 + ... \approx 0.155$$

Но мы знаем, что матожидание в исходной задаче в теме «Симметричные кортежи из последовательных простых чисел» гораздо больше и равно примерно $0.51$. Похоже, что эта модель не подходит.

[Dmitriy40]

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

Это будет случайной величиной. Вероятность того, что в урне останется хоть один белый шар, если они распределены равномерно и $W \ll n$, то попадания шаров почти независимо, и вероятность получить хотя бы один шар равна $1 - \left(1 - \frac{n}{M}\right)^W$.

Тут понятно, только есть сомнения что условия $W \ll n$ достаточно, ведь мат.ожидание не равномерно по $M$, например реальные числа таковы: $W(71\#)/W(67\#)=11/0.5=22$ вместо $71$, это большая разница. $67\#$ это праймориал, примерно $7.858\cdot10^{24}$.
Мат.ожидания для любых величин получаются по первой гипотезе Харди-Литтвуда, её оттестировали для других случаев и она вполне хорошо работает. Не слишком точно, максимум две значащие цифры, но хорошо.

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

Исходная задача эквивалентна "с какой вероятностью среди шаров с номерами, не превосходящими $n$, есть хоть один белый".

Вообще говоря да. Только надо прикрутить сюда и мат.ожидание $W(n)$, которое мы умеем вычислять.

Но вопрос почему разными способами вычисления дают сильно разные результаты, от 15% по Вашей формуле выше, до 40%.
40% получаются если сделать $n$ независимых проверок (независимых по моему в том смысле что проверенные шары возвращаем в урну, но уверен не на 100%, ну или бросаем кубик с $n$ гранями $n$ раз и проверяем число с выпавшей грани), тогда вероятность обнаружить белый шар будет $P=1-1/e^{W(n)}=1-1/e^{0.5}=40\%$ (у нас $n=67\#, M=71\#$). Формулу привёл EUgeneUS (с нашей доработкой для произвольных $n$ и $W(n)$) и она тоже в общем похожа на правду.
А если по ней же посчитать вероятность $P=1-1/e^{n/Q}$, где $Q=2.6n$ это объём на котором мат.ожидание достигает $1$, то получим $P=1-1/e^{1/2.6}=32\%$. Для ровно того же объёма проверок $n$.
Если же оценить вероятность по нормальному распределению (а vicvolf вроде как доказал нормальность распределения), то из мат.ожидания и стандартного отклонения $W(67\#)=0.5 \pm 0.7 \sigma$ превышение $W(67\#)>1$ требует $\sigma>0.7$ (снова всё округляю) причём только в одну сторону, в плюс, а хвост правее 0.7 сигм это 24%.

Непонятно почему эти 3 или уже 4 оценки (40%, 32%, 24%, 15%) настолько не совпадают.
Это вероятности кардинально разных событий что ли?
Или каждый раз неверно какое-то использованное предположение (типа равномерного распределения белых шаров по номерам)?

PS. Модераторам: прошу не считать сообщения Yadryara захватом темы, мы с ним вместе пытаемся разобраться, вопрос общий.

[Yadryara]

Если взять $\frac{n}{M}=\frac1{52}$, то матожидание получится побольше — $0.212$. И в этом случае не всё множество $n$ целиком помещается в $M$ , ибо в $n$ есть балласт немаленького размера. Надо ли это учитывать...

К тому же мы ведь ищем именно отрезок натурального ряда в 253 числа подряд, а не отдельное число...

В общем, тему лучше бы озаглавить "Помогите подобрать мат. модель". Это гораздо ближе к сути дела.

[Dmitriy40]

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

К тому же мы ведь ищем именно отрезок натурального ряда в 253 числа подряд, а не отдельное число...

Нет, мы ищем именно начальное число, с которого начинается последовательность чисел с нужными нам свойствами. И можем проверять все натуральные числа подряд, хоть это и неразумно.

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

В общем, тему лучше бы озаглавить "Помогите подобрать мат. модель". Это гораздо ближе к сути дела.

Ну урна с уменьшающимся количеством шаров вполне подходит (по физическим соображениям). Главное правильно вероятность подсчитать.
Как подходит и "с какой вероятностью среди шаров с номерами, не превосходящими $n$, есть хоть один белый" с добавлением в параметры мат.ожидания $W(n)$ количества белых шаров с номером не больше $n$ (с заданным распределением этого мат.ожидания, мы его считать умеем).
Обе эти модели вполне адекватны. Вопрос что за вероятности мы считаем и какую надо считать. И как считать правильно.

[Yadryara]

Понятно, почему матожидание так занижено. Последняя формула совершенно не учитывает, что простых чисел внизу гораздо больше и не учитывает конкретный паттерн. Всё это учитывается при подсчёте по HL1. Никакой лучшей модели тут, видимо, не придумать.

[mihaild]

А что такое $W(n)$? Число белых шаров с номерами до $n$, вероятность $n$-го шара быть белым, еще что-то?

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

Непонятно почему эти 3 или уже 4 оценки (40%, 32%, 24%, 15%) настолько не совпадают.
Это вероятности кардинально разных событий что ли?

Потому что а почему бы они должны совпадать? Уж точно среднее число шаров больше вероятности вытащить хотя бы один.

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

А если по ней же посчитать вероятность $P=1-1/e^{n/Q}$, где $Q=2.6n$ это объём на котором мат.ожидание достигает $1$

ЯННП. Если мы бросаем $n$-гранный кубик $n$ раз, то мат. ожидание числа выпадений единицы - $1$. Что такое $2.6$?

[Dmitriy40]

О, для меня кажется что-то начинает проясняться.
Ситуация 1.
Если $W(n)$ это точное количество белых шаров на интервале $n$, то проверив все $n$ чисел мы гарантированно или найдём их все, или не найдём (если $W(n)=0$). Никакого понятия вероятности не нужно.
Ситуация 2.
Если $W(M)$ это точное количество шаров на интервале $M$, то проверив лишь $n<M$ любых чисел из $M$ мы найдём белый шар с вероятностью $P=1-(1-n/M)^W$.
Ситуация 3.
Если $W(n)$ это вероятность (не мат.ожидание! и не точное количество!) быть хотя бы одному белому шару на интервале $n$, то проверив все $n$ чисел мы найдём белый шар (не меньше одного) с вероятностью $W(n)$.
Ситуация 4.
Если на интервале $n$ есть ровно один белый шар, но проверяем мы не тотально весь интервал, а $n$ раз выбираем случайное число в этом интервале и проверяем его, не удаляя его из интервала (т.е. можем потом ещё не раз на него же наткнуться при выборе), то вероятность обнаружить белый шар будет $P=1-1/e$ (её обосновать не могу, поверю EUgeneUS, ведь похоже на правду, численное моделирование к ней и сходится). И она меньше $1$ потому что при случайном выборе чисел мы можем и будем повторно попадать на уже проверенные числа, а значит некоторые числа останутся непроверенными.
Ситуация 5.
Развивая предыдущую, проверяем случайные числа не $n$ раз, а $k$ раз, вероятность будет $P=1-e^{-k/n}$.

К сожалению это всё не наша ситуация, мы не знаем ни точного количества белых шаров, ни их вероятностей и не проверяем случайные числа. Посчитать мы можем только мат.ожидание количества белых шаров на интервале. Потому ...
Ситуация 6.
Если $W(n)$ это мат.ожидание (с известным распределением) количества белых шаров на интервале $n$, то оценивать вероятность обнаружения любого из них при проверке всего интервала надо именно по распределению, беря ту область под кривой, где мат.ожидание больше $1$, т.е. когда всё правее (с большим количеством) нас устраивает. Для нормального распределения (а что оно таково вроде как доказал vicvolf) нужно больше +0.7 сигм или те самые 24%. Тут я несколько путаюсь с терминами, где мат.ожидание, распределение чего нормально, что за кривая (чего именно), но интуитивно всё сходится.
И это как раз наш случай, насколько понимаю.

mihaild
Прошу прокомментировать эти ситуации, правильно ли я их все понимаю.

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

ЯННП. Если мы бросаем $n$-гранный кубик $n$ раз, то мат. ожидание числа выпадений единицы - $1$. Что такое $2.6$?

Первая гипотеза Харди-Литтвуда выдаёт нам мат.ожидание количества белых шаров на интервале $n$. И оказывается что для $n=67\#$ оно не равно $1$, а равно $0.5$. Фактически получается что на $n$-гранном кубике лишь $0.5$ граней покрашены в белый цвет и кинув данный кубик $n$ раз мы получим лишь $0.5$ раз белую грань. Или тут тоже надо прикручивать вероятность и её распределение и $0.5$ это мат.ожидание? Похоже да, нужно.
Тогда встаёт вопрос а сколько $n$ граней кубика нужно чтобы кинув его ровно $n$ раз получить белую грань (ровно? или не менее?) один раз, т.е. при каком $n$ мат.ожидание количества белых граней становится равным $1$ - и получается что нужно в $2.6$ раза больше граней чем $67\#$, не в $2$. Вот в этом смысле $2.6$.
Не знаю пояснил или запутал (и себя тоже), факт в том что мат.ожидание количества белых шаров растёт медленнее роста интервала, $W(67\#)=0.5, W(71\#)=11$, не $35$. И $W(n)=1$ для $n=2.6\cdot67\#$.