Размещение n шаров по n корзинам

[YuryS]

Задача: однородным случайным образом размещаем n шаров по n корзинам.
Найти вероятность того, что в заданной корзине (допустим, первой) вообще не окажется шаров.

1-й вариант решения: подсчитываем общее количество таких размещений, подсчитываем количество
размещений, при которых первая корзина оказалась пуста. Находим отношение второй величины к первой,
и получаем отношение (см. допустим, учебник Ширяева ) $(n-1)/(2n-1)$.

2-й вариант решения: при размещении одного шара по корзинам, вероятность того, что он попадет в заданную
корзину равна $1/n$, а вероятность того, что он не попадет в эту корзину равна $(n-1)/n$.
Соответственно, вероятность того, что ни один из $n$ размещаемых шаров не попадет в заданную корзину
равна $(n-1/n)^n$.

Какой из вариантов решения правильный, поскольку, в общем случае, очевидно, что они дают разные ответы
(допустим, при $n=3$, первый способ дает 0.4, а второй - 8/27=0.3)?
И какой из них неправильный и почему?

[mihaild]

YuryS в сообщении #1443034 писал(а):

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

Что тут понимается под размещением - общее число шаров в каждой корзине? Если да, то почему вы считаете, что все такие размещения равновероятны?

[YuryS]

Т.е., вы полагаете, что первый вариант неправилен ?
Так, например, для $n=3$, если один исход размещения есть 3-0-0, а другой исход есть 1-1-1
(имеется ввиду распределение шаров по корзинам), то эти исходы неравновероятны ? Почему?

[Sender]

YuryS в сообщении #1443074 писал(а):

Так, например, для $n=3$, если один исход размещения есть 3-0-0, а другой исход есть 1-1-1
(имеется ввиду распределение шаров по корзинам), то эти исходы неравновероятны ? Почему?

А вы пронумеруйте шары.

[mihaild]

Давайте две корзины возьмем и покрасим шары. Сначала кинем желтый шар - какие варианты можем получить? какие у них будут вероятности?
Потом докинем красный - какие варианты получим? какие у них будут вероятности?

После этого сотрем с шаров краску - опять же, какие варианты и с какими вероятностями можно получить?

[Connector]

Задача действительно допускает два варианта решения, и действительно можно подсчитать общее количество таких размещений, подсчитать количество
размещений, при которых первая корзина оказалась пуста, найти отношение второй величины к первой, и получить отношение. Только отношение у меня получилось другое.
Кстати, в стартовом посте опечатка: вероятность, рассчитанная вторым способом, равна $(1-1/n)^n$ .

[YuryS]

Да, спасибо, я понял свою грубую детскую ошибку.

Вероятность, рассчитанная вторым способом, действительно, равна $(1-1/n)^n$,
только она у меня была записана без использования дополнительных скобок, формально строго
нужно было записать $((n-1)/n)^n$.

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

А именно - как и прежде, размещаем однородным случайным образом $n$ шаров по $n$
корзинам.
В частности, мы рассчитали вероятность того, что в отдельной корзине вообще не будет шаров -
пусть эта вероятность равна $p$, что в отдельную корзину попадет в точности один шар -
пусть, для простоты, эту вероятность также примем равной $p$ (это допущение можно принять,
когда $n$ велико), соответственно, вероятность того, что в корзину попадет более одного шара
равна $1-2p$.

А теперь вопрос - пусть мы опять же однородным случайным образом выбрали
одну из $n$ корзин.
Каково среднее (ожидаемое) количество шаров, которое в нее попадет ?
А если мы выбрали таким же образом 2 корзины, то каково аналогичное значение ?
А если $k$ корзин ?

[mihaild]

YuryS в сообщении #1443248 писал(а):

это допущение можно принять,
когда $n$ велико

Нужно уточнять, в каком смысле "можно".

YuryS в сообщении #1443248 писал(а):

Каково среднее (ожидаемое) количество шаров, которое в нее попадет ?

А тут надо воспользоваться линейностью математического ожидания и тем, что число попавших в корзину шаров равно сумме индикаторов того, что $i$-й шар в неё попал.

[YuryS]

Цитата:

Нужно уточнять, в каком смысле "можно".

Если $n$ устремить к бесконечности, то окажется, что первая и вторая вероятности
(что вообще не попадет ни один шар, и что попадет в точности один шар) равны $1/e$.
Но здесь это не совсем существенно.

Цитата:

А тут надо воспользоваться линейностью математического ожидания и тем, что число попавших в корзину шаров равно сумме индикаторов того, что $i$-й шар в неё попал.

Что нужно воспользоваться линейностью МО это очевидно,
а вот вторую часть фразы - про индикаторы - я не понял.
Это как, конкретно, подсчитывается, в случаях с одной, двумя и $k$ корзинами?

[mihaild]

Пусть $x_i = 0$ если $i$-й шар не попал в первую корзину, и $x_i = 1$ если $i$-й шар попал в первую корзину. Как число шаров, попавших в $i$-ю корзину, выражается через $x_i$? Чему равно $\mathbb E x_i$?