Найти изящное красивое решение по вероятности

[Skipper]

Задача такая.

Есть 9 изначально пустых корзин, куда падают равновероятно, шары. В каждую корзину может попасть много, любое количество шаров.
Каждый шар падает равновероятно в одну из 9-ти корзин, т.е. относительно каждой корзины можно утверждать что при следующем выпадении шара - он туда попадёт с вероятностью 1/9.
Три вопроса- 1) если бросить 30 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?
2) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?
3) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина, с менее чем 10-ю шарами?

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

[Skipper]

Цитата:

2) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?
3) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина, с менее чем 10-ю шарами?

Сравнивая эти два вопроса, можно заметить следующее. Допустим, мы нашли ответ на 3-й вопрос, т.е. знаем эту вероятность. Рассмотрим теперь только подмножество вариантов выпадений шаров таких, что одна из корзин (именно её и рассматриваем в разных вариантах)- имеет именно менее чем 10 шаров. Для сравнения вероятностей при ответе на 2-у и 3-й вопрос, остальные корзины можно вообще больше не рассматривать. Значит, если в "минимальной" корзине 9 шаров ровно, обозначим варианты как,
$1111111110000000..0$
$1111111101000000..0$
$1111111100100000..0$
... (и т.д.)

длина этой последовательности нулей-единиц, равна $150$, где 0 означает непопадание шара в эту корзину на N-й попытке, а 1 - означает попадание шара в эту корзину.

если 8 или менее шаров, то строится аналогичным способом,

если 1 шар, то множество будет таким, уже только будет содержать 150 вариантов,
$1000000000000000..0$
$0100000000000000..0$
$0010000000000000..0$
... (и т.д.)
$0000000000000000..1$

и если 0 шаров, то обозначение будет,
$0000000000000000..0$

Значит подмножество вариантов, в котором ни разу шар не попал в корзину, будет из 1 элемента, обозначенного всеми нулями, а вариантов в которых, в корзине 9 или менее шаров, будет равно

$C_{150}^9$ + $C_{150}^8$ + $C_{150}^7$ + $C_{150}^6$ + $C_{150}^5$ + $C_{150}^4$ + $C_{150}^3$ + $C_{150}^2$ + $C_{150}^1$ + 1 = 82947113349100 + 5257211409450 + 294109729200 + 14297000725 + 591600030 + 20260275 + 551300 + 11175 + 150 + 1 =

88513344451531

значит сравнивая два вопроса,

Цитата:

2) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?
3) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина, с менее чем 10-ю шарами?

Вероятность как ответ для 3-го вопроса будет примерно в 88 триллионов раз больше, чем во 2-м вопросе?
Правильно я тут понял?

[Skipper]

Найдём теперь ответ на 1-й вопрос,

Цитата:

1) если бросить 30 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?

Сначала посчитаем вероятность, что именно конкретно в 1-й корзине после бросания 30-ти шаров не окажется ни одного шара. Тут простое пересечение событий, потому можно просто перемножить вероятности, получим (это тривиально просто)

$ (1 - \frac{1}{9})^{30} =(\frac{8}{9})^{30} = 0,029202...$
(что примерно равно $2.9$ %)

Ну а то, что при этом в 2-й корзине - шары точно будут, вероятность равна (т.к. считаем для пересечения событий, то шары в первую корзину заведомо не попали)

$ 1 - (1 - \frac{1}{8})^{30} =1 - (\frac{7}{8})^{30} = 0,9817...$

Найдём аналогичные последовательности значений, что шары будут и в 3-й корзине, в 4-й и т.д. Значит вероятность общего события, того что
"в 1-й корзине шаров не будет И (во 2-й корзине шары будут) И (в 3-й корзине шары будут) ... и т.д. И (в 9-й корзине шары будут)" , так как это пересечение событий, эта вероятность равна-

$(0,029202 \cdot 0,9817 \cdot 0,990 \cdot 0,995 \cdot 0,998 \cdot 0,999 \cdot 0,999 \cdot 0,999 \cdot 1 ) = 0,02809..$

(что примерно равно $2.8$ %)

Как видим, эти множители для высчитывания вероятности

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

почти не повлияли, т.е. без этого "И" была вероятность $2.9$ % а стала $2.8$ %.

Но зачем эти множители нужны были? Затем что теперь у нас множество вариантов для события - "только в 1-й корзине нет шаров", не пересекается с множеством вариантов для событий "только в 2-й корзине нет шаров", "только в 3-й.." и т.д.,
а значит чтобы посчитать вероятность события, "в какой то одной из корзин, неважно какой - нет шаров", мы можем просто сложить вероятности, так как это объединение непересекающихся подмножеств, и получим,

"если бросить 30 шаров, то с какой вероятностью останется ИМЕННО одна корзина пустой, неважно какая, т.е. куда-то не угодит ни один шар?"

будет равна $2.8$ % , сложенное с собой 9 раз, т.е. 25,2$ %.

Значит, чтобы ответить на 1-й вопрос вопрос задачи,

Цитата:

1) если бросить 30 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?

эта вероятность будет совсем немногим больше чем 25,2$ %, потому что мы нашли что
ИМЕННО одна корзина пустая - 25,2$ %, ну а дополнительные возможности, что также даже две или более корзин окажутся пустыми при 30-ти бросаниях шара, совсем уж быстро стремится к нулю, и существенно на эти
25,2$ % не влияет.

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

[мат-ламер]

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

1) если бросить 30 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?

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

эта вероятность будет совсем немногим больше чем 25,2$ %

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

[zykov]

мат-ламер
Для 30 шаров где-то так.
Можно приближенно оценить как $9\cdot \left(\frac{8}{9}\right)^{30} \approx 0.263$.

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

[мат-ламер]

zykov в сообщении #1596841 писал(а):

Для 30 шаров где-то так.

Извиняюсь, попутал условие. Мне показалось, что там три корзины.

-- Ср июн 07, 2023 18:50:52 --

zykov в сообщении #1596841 писал(а):

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

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

-- Ср июн 07, 2023 18:54:01 --

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

потому и хочу спросить, если ли тут какое то красивое изящное решение, может даже готовая формула (для такого класса задач) ?

Для первых двух вопросов, если скомбинировать предельную теорему Пуассона и формулу включений-исключений, то можно попробовать получить некую простую приближённую формулу с экспонентой. Но не уверен.

[Skipper]

zykov в сообщении #1596841 писал(а):

мат-ламер
Для 30 шаров где-то так.
Можно приближенно оценить как $9\cdot \left(\frac{8}{9}\right)^{30} \approx 0.263$.

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

Так даже не приближённо а точно вот так и можно оценить, не надо никаких поправок -
$9\cdot \left(\frac{8}{9}\right)^{30}$

Почему?
Занумеруем каждую корзину цифрой от 0, до 8, так как у нас всего 9 корзин, и любой исход из 30-ти шаров будем представлять как число в 9-ричной системе счисления, например,

$08421237367...2$

длиной в $30$ цифр, где цифра от 0 до 8 в каждом порядковом номере, указывает корзину куда упал шар, а длина 30, потому что всего 30 шаров бросали.
Тогда вариантов этого числа, очевидно $9^N$ , где $N$ число шаров, и в нашем случае их $30$.

Это количество всех исходов. Если ни один шар не попал в какую то корзину, то какая то цифра будет просто отсутствовать в этом ряду, и не важно какая, например отсутствует $8$.

$03421237367...2$

количество таких исходов, представляется как бы уже числом в 8-ричной системе счисления, где цифра от 0 до 7 в каждом порядковом номере, указывает корзину куда упал шар.
Тогда вариантов этого числа, очевидно $8^N$ , где $N$ число шаров, и в нашем случае их $30$.
Но не обязательно только варианты с отсутствием шаров в корзине $8$. Они могут отсутствовать и в корзине 7, и в корзине 6, и т.д, в 9-ти вариантах корзин.
Поэтому всего количество исходов где хотя бы одна корзина остаётся пустой,
$9 \cdot 8^N$ , И их часть от всех равна -

$\frac{9 \cdot 8^N}{9^N}$ что при $N$ равным $30$, и равняется тому что вы написали-
$9\cdot \left(\frac{8}{9}\right)^{30}$

Вот так, получается красивая формула, и не надо считать никаких "малых поправок".

Значит ответы на два первых вопроса такие -

Цитата:

1) если бросить 30 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?

вероятность $9\cdot \left(\frac{8}{9}\right)^{30} \approx 0.263$

Цитата:

2) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина пустой, т.е. туда не угодит ни один шар?

вероятность $9\cdot \left(\frac{8}{9}\right)^{150} \approx 0.000000191$

вот так - просто умножать на 9 надо, правильно?

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

Цитата:

3) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина, с менее чем 10-ю шарами?

не может быть такого, что эта вероятность больше в 88 триллионов раз больше, чем во 2-м вопросе, т.е. чем $0.000000191$.

Что я там запорол, пока не понял, как и то, какую формулу вывести вот для решения этого, 3-го вопроса,

[mihaild]

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

Поэтому всего количество исходов где хотя бы одна корзина остаётся пустой, $9 \cdot 8^N$ ,

Вы несколько раз посчитали варианты, в которых пустой остается более одной корзины. При $30 = 1$ Ваши выкладки дают вероятность того, что для одного шара хотя бы одна корзина останется пустой с вероятностью $8$ (а не $1$ как должно быть).

[Skipper]

НУ хотя бы при $N$ достаточно большом ($30$ уже достаточно большое, а тем более $150$), часть исходов где хотя бы одна корзина остаётся пустой, (а значит и вероятность этого) - асимптотически стремится, и можно сказать, округлённо равна -

$9\cdot \left(\frac{8}{9}\right)^{N}$

так?
Мне тут нужна как можно более простая формула, достаточно точная (абсолютная точность пока не требуется), которую можно применить, чтобы также вывести достаточно простую формулу, для вопроса

Цитата:

3) если бросить 150 шаров, то с какой вероятностью останется хотя бы одна корзина, с менее чем 10-ю шарами?

Эти вероятности интересно, как будут изменяться, 1) и при случае с фиксированными 10 шарами которых может не оказаться хотя бы в одной корзине. но при разных количествах бросания шаров,
и 2) наоборот, при фиксированном числе бросания в 150 раз, но рассмотреть вероятности, когда менее 9-ти шаров может не быть, менее 8-ми, менее 7-ми, и т.д.
Чтобы увидеть график и всё это понять, мне и нужна как можно более простая формула,

[Geen]

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

Считать и раскладывать по формулам, вести комбинаторные подсчёты я могу

Мда... а по тому, что Вы пишете, возникает ощущение, что Вы не можете решить эту задачу...

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

Мне тут нужна как можно более простая формула, достаточно точная

Вы получите точную формулу в общем виде - и тогда увидите что как себя ведёт и где что можно упрощать (для "практических применений").

[Combat Zone]

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

Вероятность как ответ для 3-го вопроса будет примерно в 88 триллионов раз больше, чем во 2-м вопросе?
Правильно я тут понял?

Даже не подумает.
Первая задача действительно решается формулой включения-исключения, точный ответ на нее в общем случае $1- P\{m_0=0\}=1-\dfrac{9!}{9^{30}}S(30,9)$, где $S$ - число Стирлинга второго рода. Примерно она совпадет с той, что вы посчитали, погрешность довольно мала.
Конечно, можно и вторую так же пытаться решать, но например, у моего компьтера не хватает к тому способностей. Потому используются или асимптотика чисел Стирлинга (достаточно точная), или предельные теоремы для таких вероятностей. Их в той отрасли теории вероятностей много, можете посмотреть, например, Колчин, Севастьянов, Чистяков "Случайные размещения" и статьи, на которые они ссылаются. Есть и более поздние на ту же тему. Материал действительно востребован на практике, потому одно время активно разрабатывался.
Третья задача - о распределении первой порядковой статистики набора случайных величин $X_1,\ldots,X_N$, где $X_k$ - кол-во шаров в k-й корзине.
Тем самым, нужно найти $P\{X_{(1)}\ge 10\}$. Для этого опять же используются предельные теоремы, и у меня такое впечатление, что скорее всего те из них, где сходимость будет к распределению Гумбеля.

Но это надо проверять.

[Alex Krylov]

IMHO, для начала надо сказать, что тут речь идет о таких комбинаторных объектах как, как k-композиция (англ. k-composition) и слабая k-композиция (англ. weak k-composition):

Цитата:

Совокупность чисел $(x_1,...,x_k)\in\mathbb{N}^k: x_1+...+x_k=n$ называется k-композицией числа $n$

Совокупность чисел $(x_1,...,x_k)\in\mathbb{N}_0^k: x_1+...+x_k=n$ называется слабой k-композицией числа $n$.

Цитата:

Для $n,k\in\mathbb{N}_0$ справедливы следующие утверждения:

1) Число слабых $k$-копозиций числа $n$ равно $\binom{n+k-1}{n}$
2) Число $k$-копозиций числа $n$ равно $\binom{n-1}{k-1}$

[Combat Zone]

Alex Krylov в сообщении #1597074 писал(а):

1) Число слабых $k$-копозиций числа $n$ равно $\binom{n+k-1}{n}$
2) Число $k$-копозиций числа $n$ равно $\binom{n-1}{k-1}$

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

[Skipper]

Combat Zone в сообщении #1596959 писал(а):

Первая задача действительно решается формулой включения-исключения, точный ответ на нее в общем случае $1- P\{m_0=0\}=1-\dfrac{9!}{9^{30}}S(30,9)$, где $S$ - число Стирлинга второго рода

Ну по этому пункту понятно, и достаточно просто. Может я позже, более подробно формулы распишу, с асимптотиками чисел Стирлинга.

Но вот 3-я задача, пока непонятно как решать.. ("о распределении первой порядковой статистики набора случайных величин"). Что тут наиболее простое можно придумать?
Я пытаюсь упростить для случая, с требованием не $10$ шаров, как допустимый минимум в корзинах рассматривать, а поначалу, $2$ шаров. А всего бросаем допустим, $80$ шаров.
Пусть, это 4-я задача, как упрощение 3-й.

Напрашивается вариант - разбить множество ячеек на $18$, найти $S(80,18)$ - где $S$ - число Стирлинга второго рода. Это будет число разбиений $80$-элементного множества, на $18$ блоков.
Потом как то подсчитать $X$ количество вариантов, со "склейками" этих блоков, произвольным образом, но с условием, каждые $2$ блока попарно склеиваются.
Тогда получим в каждом "склеенном" новом блоке - минимум $2$ шара, всего таких блоков равно будет $9$.
Тогда $S(80,18) / X$ будет равно числу число разбиений $80$-элементного множества, на $9$ блоков, но уже в каждом из которых может быть не менее $2$ шаров.
Умножив на $9!$ получим то же самое с учетом перестановок, это итоговое число разделив на $9^{30}$ (что равно вообще числу вообще всех вариантов), получили бы вероятность события-

Цитата:

4) если бросить 80 шаров, то с какой вероятностью не будет ни одной корзины, с менее чем $2$-мя шарами?

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

Может подскажете, самую простую литературу для решения такой задачи?

[zykov]

Skipper
Так всё же, нужно найти вероятность точно или приближенной оценки достаточно?