Задача про шары и урны (из книги Кормена)

[Interloper]

Добрый день. Помогите разобраться с задачей 5.4-2 из книги "Алгоритмы. Построение и анализ" (Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн - 2005 год).
Условие задачи:

Цитата:

Предположим, что b урн наполняются шарами. Каждое опускание шара происходит независимо от других, и шар с равной вероятностью может оказаться в любой урне. Чему равно математическое ожидание количества шаров, которое необходимо опустить для того, чтобы хотя бы в одной урне оказалось два шара?

Я рассуждал так. Пусть X - случайная величина, равная количеству опущенных шаров, обеспечивающих первое появление двух шаров в какой-либо урне. Тогда $E[x]=\sum_{i=2}^{n+1}i\cdot{p_i}$, где $p_i=P(X=i)$.
Посмотрим на $p_i$.
$p_2=\frac1b$, поскольку для того, чтобы 2 опускания шара обеспечили 2 шара в одной урне, второй шар должен попасть туда же, куда и первый, поэтому вероятность этого события равна $\frac1b$.
$p_3=\frac{b-1}b\cdot\frac2b$, поскольку второй шар должен не попасть в ту же урну, что и первый (вероятность этого события равна $\frac{b-1}b$), а третий шар должен попасть в урну с первыи или вторым шаром (вероятность этого события равна $\frac2b$).
Рассуждая аналогично, получим: $p_i=\frac{(i-1)\cdot(b-1)!}{(b-i+1)!\cdot b^{i-1}}$
Свернуть сумму таких $p_i$, получив хотя бы приближенную формулу, мне не удалось.
Тогда я попытался использовать аппроксимацию $1+x\approx e^x$:
$p_i=(1-\frac1b)(1-\frac2b)\ldots(1-\frac{i-2}b)\cdot\frac{i-1}b \approx e^{-\frac1b}\cdot e^{-\frac2b} \cdot\ldots\cdot e^{-\frac{i-2}b}\cdot\frac{i-1}b=e^{\frac{(i-1)(i-2)}{2b}}\cdot\frac{i-1}b$
Просуммировать $p_i$ и в таком виде мне не представляется возможным.
Подскажите, как действовать, чтобы получить формулу (пусть и приближенную) для искомого математического ожидания, в которой не будет содержаться суммирование, т.е. формула будет иметь простой вид.

[ewert]

$b$ урн -- слишком мало, возьмём лучше $n$. Тогда матожидание равно $\sum\limits_{k=0}^n\dfrac{n!\cdot k(k+1)}{n^{k+1}(n-k)!}$. Поскольку при этом $\sum\limits_{k=0}^n\dfrac{n!\cdot k}{n^{k+1}(n-k)!}=1$, это матожидание сворачивается в довольно простую сумму: $\sum\limits_{k=0}^n\dfrac{n!}{n^k(n-k)!}=\dfrac{n!}{n^n}\sum\limits_{k=0}^n\dfrac{n^k}{k!}$, но дальше уже никак. Однако $k=n-\frac12$ -- это как раз примерно точка максимума общего члена последней суммы, поэтому сумма асимптотически равна половине суммы всего ряда, т.е. $\frac12e^n$ (там метод Лапласа и пр.). Тогда по Стирлингу получится, что матожидание ведёт себя как $\sqrt{\dfrac{\pi n}2}$; но сходимость медленная, конечно.

[Interloper]

ewert в сообщении #764183 писал(а):

$b$ урн -- слишком мало, возьмём лучше $n$. Тогда матожидание равно $\sum\limits_{k=0}^n\dfrac{n!\cdot k(k+1)}{n^{k+1}(n-k)!}$. Поскольку при этом $\sum\limits_{k=0}^n\dfrac{n!\cdot k}{n^{k+1}(n-k)!}=1$, это матожидание сворачивается в довольно простую сумму: $\sum\limits_{k=0}^n\dfrac{n!}{n^k(n-k)!}=\dfrac{n!}{n^n}\sum\limits_{k=0}^n\dfrac{n^k}{k!}$, но дальше уже никак. Однако $k=n-\frac12$ -- это как раз примерно точка максимума общего члена последней суммы, поэтому сумма асимптотически равна половине суммы всего ряда, т.е. $\frac12e^n$ (там метод Лапласа и пр.). Тогда по Стирлингу получится, что матожидание ведёт себя как $\sqrt{\dfrac{\pi n}2}$; но сходимость медленная, конечно.

А можно подробнее про "метод Лапласа и пр."? И из чего следует, что $k=n-\frac12$ -- это как раз примерно точка максимума общего члена последней суммы, поэтому сумма асимптотически равна половине суммы всего ряда?

[Deggial]

Interloper в сообщении #764201 писал(а):

А можно подробнее про "метод Лапласа и пр."? И из чего следует, что $k=n-\frac12$ -- это как раз примерно точка максимума общего члена последней суммы, поэтому сумма асимптотически равна половине суммы всего ряда?

Вот в этой теме есть более развернутое пояснение и ссылки на литературу.

[ewert]

Interloper в сообщении #764201 писал(а):

И из чего следует, что $k=n-\frac12$ -- это как раз примерно точка максимума общего члена последней суммы,

Это тривиально.

Interloper в сообщении #764201 писал(а):

поэтому сумма асимптотически равна половине суммы всего ряда?

А тут с моей стороны, конечно, некоторое жульничество; но я просто пытался изложить получение результата максимально надёжным способом, пусть и легкомысленным. Речь о том, что эта сумма асимптотически равна соответствующему интегралу (это легко). В котором подынтегральная функция, очевидно, аналитична по $k$. И при этом вне любой сколь угодно малой, но фиксированной (в относительном масштабе) окрестности точки максимума значения функции много меньше значения в центре (что очевидно хотя бы из того же Стирлинга). Поэтому как левая половина интеграла, так и правая определяются в первом приближении (с точностью до постоянных множителей) лишь второй производной подынтегральной функции в точке максимума; это, в принципе, и есть идеология метода Лапласа. Т.е. асимптотически обе половинки одинаковы.

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

[Interloper]

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

[ewert]

Interloper в сообщении #764941 писал(а):

мне кажется, что решение может быть значительно проще.

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

[Interloper]

Цитата:

Это тривиально.

А можно дать внятный ответ? Если бы это было для меня тривиально, я бы не спрашивал.

[ewert]

Interloper в сообщении #764201 писал(а):

из чего следует, что $k=n-\frac12$ -- это как раз примерно точка максимума общего члена последней суммы

$\dfrac{n^{k}}{k!}<\dfrac{n^{k+1}}{(k+1)!}\ \Leftrightarrow\ k+1<n$

[--mS--]

Ну проще, так проще, но никуда эта сумма не свернётся.

Для целочисленной случайной величины с неотрицательными значениями

$$\mathsf EX=\sum_{k=0}^{\infty} \mathsf P(X>k).$$

Для $X$ - числа разложенных шаров - эта сумма до $n$, поскольку $\mathsf P(X>n+1)=0$, а слагаемое $\mathsf P(X>k)=\dfrac{n!}{(n-k)! n^k}$ равно вероятности того, что $k$ шаров разложатся по одному. Ну и

$$\mathsf EX=\sum_{k=0}^{n} \mathsf P(X>k) = \sum_{k=0}^{n}\frac{n!}{(n-k)! n^k} = \frac{n!}{n^n} \sum_{k=0}^n \frac{n^k}{k!}.$$

[Interloper]

Не совсем понимаю как это равенство получается...

--mS-- в сообщении #765105 писал(а):

$\sum_{k=0}^{n}\frac{n!}{(n-k)! n^k} = \frac{n!}{n^n} \sum_{k=0}^n \frac{n^k}{k!}.$$

[ewert]

Тупой заменой ка на эн минус ка.

[Interloper]

Понял. А асимптотическую оценку как дальше получить?

[ewert]

Interloper в сообщении #765127 писал(а):

А асимптотическую оценку как дальше получить?

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