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

[itsmeagain]

Если правильно понял условие, то:
Всего может быть $C_{10^{27}}^{11}$ расположений белых шаров по $10^{27}$ номерам. Сколько из них существует расположений белых шаров в которых до номера $10^{25}$ есть хотя бы один белый шар?
Ответ:
$C_{10^{25}}^1\cdot C_{10^{27}-10^{25}}^{10}+C_{10^{25}}^2\cdot C_{10^{27}-10^{25}}^{9}+C_{10^{25}}^3\cdot C_{10^{27}-10^{25}}^{8}+...+C_{10^{25}}^{11}\cdot C_{10^{27}-10^{25}}^{0}$
Делим его на $C_{10^{27}}^{11}$, получаем искомую вероятность.

[Dmitriy40]

itsmeagain
Да, для случая точно известного количества шаров Вы всё поняли правильно. И это ещё одна модель задачи.
Спасибо, интересный вариант подсчёта вероятности (и главное понятный).
Сейчас попробую подсчитать ...

[mihaild]

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

Если $W(M)$ это точное количество шаров на интервале $M$, то проверив лишь $n<M$ любых чисел из $M$ мы найдём белый шар с вероятностью $P=1-(1-n/M)^W$.

При условии, что шары распределены равномерно по интервалу, и $W \ll \min(n, M - n)$. Ибо например если $W(M) + n > M$, то вероятность единичная (по принципу Дирихле), а формула дает меньше единицы.

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

то вероятность обнаружить белый шар будет $P=1-1/e$

Вероятность будет, очевидно, $1 - \left(1 - \frac{1}{n}\right)^n \approx 1 - \frac{1}{e}$ (практически определение $e$).

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

Развивая предыдущую, проверяем случайные числа не $n$ раз, а $k$ раз, вероятность будет $P=1-e^{-k/n}$.

При больших $k$ это становится неточным, но на практике сойдет.

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

Если $W(n)$ это мат.ожидание (с известным распределением)

У мат. ожидания не бывает распределения (ну кроме как когда рассматривается с.в., параметризованная другой, но это не тот случай).

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

$W(n)$ это мат.ожидание (с известным распределением) количества белых шаров на интервале $n$

То вероятность того, что $n$-й шар белый - $W(n) - W(n - 1)$. Распределение, правда, чисто из мат. ожидания не восстанавливается.

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

Спасибо, интересный вариант подсчёта вероятности (и главное понятный).

И из него как раз получается моё $1 - \left(1 - \frac{n}{M}\right)^W$.
Вероятность, что ни одного белого шара нет, аналогично $\frac{C_{M - n}^W}{C_M^W} = \frac{(M - n)! (M - W)! W!}{W! (M - n - W)! M!} = \frac{\prod_{i=0}^W (M - n - i)}{\prod_{i=0}^W (M - i)} \approx \frac{(M - n)^W}{M^W} = \left(1 - \frac{n}{M}\right)^W$.

[Dmitriy40]

mihaild
Спасибо! Всё лучше и лучше складываются в голове разрозненные куски.
Даже считать через комбинаторику не пришлось, пока отвлёкся на дела и вспоминал определение $C^a_b$, Вы уже привели вывод.

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

У мат. ожидания не бывает распределения

Ну значит я снова путаю термины. Как правильно называть тогда величины (включая и пропущенные) из фраз типа "для нормального распределения вероятность получить величину, отклоняющуюся от мат.ожидания не более чем на 2 сигмы, составляет 95.45%"?

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

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

$W(n)$ это мат.ожидание (с известным распределением) количества белых шаров на интервале $n$

То вероятность того, что $n$-й шар белый - $W(n) - W(n - 1)$.

А вот тут совсем не понял. Разность $W(n)-W(n-1)$ эффективно нулевая (с любой разумной точностью) для любых $n$.
Или может первая гипотеза Харди-Литтвуда выдаёт не мат.ожидание (без распределения) количества штук на интервале? Или я что-то путаю по пути от неё к нам?

[mihaild]

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

Как правильно называть тогда величины (включая и пропущенные) из фраз типа "для нормального распределения вероятность получить величину, отклоняющуюся от мат.ожидания не более чем на 2 сигмы, составляет 95.45%"?

Так и говорить, только обычно говорят "вероятность получить значение".
Или, другими словами, "вероятность того, что нормально распределенная случайная величина отклоняется от мат. ожидания больше чем на 2 сигмы, вот такая".
И среднее, и вероятность какого-то отклонения от него - характеристики случайной величины целиком. А говорить можно о распределении случайной величины, а не каких-то ее характеристик.

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

А вот тут совсем не понял. Разность $W(n)-W(n-1)$ эффективно нулевая (с любой разумной точностью) для любых $n$.

Значит и вероятность что конкретный шар будет белым мала.

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

Или может первая гипотеза Харди-Литтвуда выдаёт не мат.ожидание (без распределения) количества штук на интервале?

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

[Dmitriy40]

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

Значит и вероятность что конкретный шар будет белым мала.

Но мы же говорим о вероятности не для одного (конкретного) шара, а для $n$ штук, выходит эта разность ни о чём? Точнее о другом, типа её надо просуммировать/проинтегрировать по всем $1 \ldots n$. И придём обратно к тем же формулам выше.

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

Она и говорит, что доля чисел, являющихся начальными элементами кортежей,

Это можно называть мат.ожиданием количества таких чисел? Вроде можно.

Чуть резюмирую в надеюсь более правильной формулировке.
Количество белых шаров (чисел) на интервале является случайной величиной (с.в.) с нормальным распределением (в этом верим vicvolf-у) с вычислимыми мат.ожиданием и дисперсией (стандартным отклонением). А вероятность после проверки интервала получить значение этой с.в. в некотором диапазоне относительно её мат.ожидания (последнее выдаёт первая гипотеза Харди-Литтвуда) считается по распределению (например с привлечением стандартного отклонения или дисперсии).
Всё так с употреблением терминов? Что величина случайная, что её распределение нормальное, как оно считается - дело другое, считаем известным.

[mihaild]

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

Но мы же говорим о вероятности не для одного (конкретного) шара, а для $n$ штук, выходит эта разность ни о чём? Точнее о другом, типа её надо просуммировать/проинтегрировать по всем $1 \ldots n$. И придём обратно к тем же формулам выше

Безусловно. Это было простое замечание, основанное на том, что мат. ожидание числа белых шаров в диапазоне $(a, b]$ равно $M(b) - M(a)$, а для одного шара вероятность его оказаться белым равна мат. ожиданию числа белых шаров среди него.

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

Это можно называть мат.ожиданием количества таких чисел? Вроде можно.

Очень аккуратно, тут недалеко была про это тема vicvolf. И надо сообразить, но вроде бы только потому что там в знаменателе логарифм, если бы был, например, корень - так что слагаемые быстро меняются, и в ожидание существенный вклад вносит начальный отрезок - то было бы совсем непонятно, что там с вероятностной интерпретацией.

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

Всё так с употреблением терминов? Что величина случайная, что её распределение нормальное, как оно считается - дело другое, считаем известным.

Понятно, что число шаров нормально распределено быть не может, но для почти всех практических задач можно считать, что просто $p_n = \phi_{\mu,\sigma}(n)$ (и там вылезающие за границу хвосты обрезать и перенормировать, поправка будет маленькой).

[Dmitriy40]

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

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

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

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

Понятно, что число шаров нормально распределено быть не может,

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

mihaild
В общем ещё раз спасибо!
Понял не всё, но главное: по какой формуле считать вероятность - через гипотезу ХЛ и сигмы для нормального распределения. И надеюсь это не из-за желания оказаться правым.

[wrest]

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

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

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

[Dmitriy40]

wrest
Так нас и не интересует всё что дальше 3 сигм, у нас все вещественные числа в параметрах имеют худшую точность (большую погрешность), куда уж нам хвосты за десятки сигм резать.

[Yadryara]

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

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

А сколько это будет для нашего случая? Напомню, что матожидание у нас $0.51$ кортежа и нам нужно знать вероятность, что найдётся хотя бы один.