2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Вероятность про урну с нумерованными шарами
Сообщение11.11.2024, 18:16 
Заслуженный участник


20/08/14
11709
Россия, Москва
Приветствую математиков.
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. Только пожалуйста, не надо заставлять учить весь теорвер и иже с ним, задача не научиться решать такие примеры, а решить конкретно этот и понять как решение зависит от параметров. И сколько месяцев ещё платить за электричество для расчётов. :-)

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение11.11.2024, 21:02 
Аватара пользователя


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

-- 11.11.2024, 21:20 --

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

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

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение11.11.2024, 21:31 
Заслуженный участник
Аватара пользователя


16/07/14
9110
Цюрих
Dmitriy40 в сообщении #1661197 писал(а):
Все шары пронумерованы натуральными числами в случайном порядке независимо от их цвета
Разными, от $1$ до $M$ или как-то иначе?
Dmitriy40 в сообщении #1661197 писал(а):
С другой стороны, они не учитываются и тогда выходит ни на что не влияют?
Да, можно сразу, не глядя, выкинуть из урны все шары с номерами, большими $n$.

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 01:00 
Заслуженный участник


20/08/14
11709
Россия, Москва
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$ это тоже лишь мат.ожидание количества (с огромной дисперсией), точное значение нам пока неизвестно. И неизвестно какие номера у белых шаров. Важно ли это уточнение?

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 02:17 
Заслуженный участник
Аватара пользователя


16/07/14
9110
Цюрих
Dmitriy40 в сообщении #1661221 писал(а):
то как тогда определить сколько в урне останется белых шаров $W$? Просто как $W_n=W\frac{n}{M}$?
Это будет случайной величиной. Вероятность того, что в урне останется хоть один белый шар, если они распределены равномерно и $W \ll n$, то попадания шаров почти независимо, и вероятность получить хотя бы один шар равна $1 - \left(1 - \frac{n}{M}\right)^W$.

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 02:41 
Аватара пользователя


29/04/13
8066
Богородский
mihaild в сообщении #1661226 писал(а):
вероятность получить хотя бы один шар равна $1 - \left(1 - \frac{n}{M}\right)^W$.

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

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 03:01 
Заслуженный участник
Аватара пользователя


16/07/14
9110
Цюрих
Yadryara в сообщении #1661227 писал(а):
То есть, даже если белый шар вытащили, продолжаем вытаскивать, пока все $n$ шаров не вытащим и урна не опустеет?
А это неважно. Исходная задача эквивалентна "с какой вероятностью среди шаров с номерами, не превосходящими $n$, есть хоть один белый".

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 03:33 
Аватара пользователя


29/04/13
8066
Богородский
Попробую ещё уточнить. Допустим в урне $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$ с каждым новым вытаскиванием? Я пока посчитал в предположении, что уменьшается.

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 05:56 
Аватара пользователя


29/04/13
8066
Богородский
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$. Похоже, что эта модель не подходит.

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 07:08 
Заслуженный участник


20/08/14
11709
Россия, Москва
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 захватом темы, мы с ним вместе пытаемся разобраться, вопрос общий.

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 07:41 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 08:06 
Заслуженный участник


20/08/14
11709
Россия, Москва
Yadryara в сообщении #1661233 писал(а):
К тому же мы ведь ищем именно отрезок натурального ряда в 253 числа подряд, а не отдельное число...
Нет, мы ищем именно начальное число, с которого начинается последовательность чисел с нужными нам свойствами. И можем проверять все натуральные числа подряд, хоть это и неразумно.
Yadryara в сообщении #1661233 писал(а):
В общем, тему лучше бы озаглавить "Помогите подобрать мат. модель". Это гораздо ближе к сути дела.
Ну урна с уменьшающимся количеством шаров вполне подходит (по физическим соображениям). Главное правильно вероятность подсчитать.
Как подходит и "с какой вероятностью среди шаров с номерами, не превосходящими $n$, есть хоть один белый" с добавлением в параметры мат.ожидания $W(n)$ количества белых шаров с номером не больше $n$ (с заданным распределением этого мат.ожидания, мы его считать умеем).
Обе эти модели вполне адекватны. Вопрос что за вероятности мы считаем и какую надо считать. И как считать правильно.

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 09:52 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 12:24 
Заслуженный участник
Аватара пользователя


16/07/14
9110
Цюрих
А что такое $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$?

 Профиль  
                  
 
 Re: Вероятность про урну с нумерованными шарами
Сообщение12.11.2024, 13:35 
Заслуженный участник


20/08/14
11709
Россия, Москва
О, для меня кажется что-то начинает проясняться.
Ситуация 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\#$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group