Найти мат. ожидание дискретного распределения.

[Rubik]

Задача такая: есть игральная кость с $n$ гранями, на каждой число от $1$ до $n$. Выпадение каждой грани равновероятно. Кость бросают несколько раз до тех пор, пока сумма очков, выпавших за все разы на кости не станет больше или равна $n$. Найти мат. ожидание количества бросков.

Пусть вероятность того, что игра закончится за $k$ ходов ($1 \le k \le n$), равна $P_k$. Тогда мат. ожидание числа бросков: $M[k] = \sum\limits_{k=1}^nP_kk$.

Вероятность закончить за $1$ ход: $P_1 = \frac1n$.

Рассмотрим вероятность закончить за $k$ ходов, $k\ge1$. Пусть за $k-1$ ход было набрано $l-1$ очков, $k\le l\le n$. Возможностей набрать $l-1$ очков за $k-1$ ход - количество разбиений числа $l-1$ с $k-1$ слагаемыми, что равно $C_{l-2}^{k-2}$. Чтобы завершить за последний ход, необходимо набрать хотя бы $n-(l-1)$ очков, что можно сделать $l$ способами. Значит, всего возможностей завершить игру за $k$ бросков при условии, что после $k-1$ бросков сумма равнялась $l-1$ равно $C_{l-2}^{k-2}l$. Всего возможностей завершить за $k$ ходов: $\sum\limits_{l=k}^nC_{l-2}^{k-2}l$. Всего по результатам $k$ бросков возможно $n^k$ исходов, значит вероятность закончить за $k$ ходов: $P_k=\sum\limits_{l=k}^n\frac{C_{l-2}^{k-2}l}{n^k}$.

Значит, мат. ожидание $M[k] = \sum\limits_{k=1}^nP_kk = \frac1n + \sum\limits_{k=2}^n\sum\limits_{l=k}^n\frac{C_{l-2}^{k-2}lk}{n^k}$.

Путём нехитрых, но очень громоздких алгебраических преобразований (у меня заняли 5 страниц А4), я получил результат: $M[k] = \left(1+\frac1n\right)^{n-1}$.

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

[ShMaxG]

Обозначим $\nu$ -- количество бросков, а $\xi_1, \ \xi_2, ...$ -- независимые случайные величины, принимающие значения $[1,2,...,n]$ с равной вероятностью $1/n$. В таком случае

$$\[{\bf{E}}\nu = \sum\limits_{k = 1}^n {k{\bf{P}}\left( {\nu = k} \right)} = 1 + \sum\limits_{k = 2}^n {{\bf{P}}\left( {\nu \ge k} \right)} = 1 + \sum\limits_{k = 2}^n {{\bf{P}}\left( {{\xi _1} + {\xi _2} + ... + {\xi _{k-1}} \le {n-1}} \right)}. \]$$

Далее заметим, что

$$\[{\bf{P}}\left( {{\xi _1} + {\xi _2} + ... + {\xi _k} = j} \right) = \frac{{C_{j - 1}^{k - 1}}}{{{n^k}}}.\]$$

Действительно, вычисление этой вероятности можно производить по классическому определению вероятности, так как эта подзадача равносильна задаче выбора $j-k$ элементов из $k$ с возвращением и без учета порядка: $\[C_{k + \left( {j - k} \right) - 1}^{j - k} = C_{j - 1}^{k - 1},\]$ подробнее см. http://nsu.ru/mmf/tvims/chernova/tv/lec ... TION000212.

$$\[\begin{gathered} 1 + \sum\limits_{k = 2}^n {{\mathbf{P}}\left( {{\xi _1} + {\xi _2} + ... + {\xi _{k - 1}} \leqslant n - 1} \right)} = \\ = 1 + \sum\limits_{k = 1}^{n - 1} {{\mathbf{P}}\left( {{\xi _1} = k} \right)} + \sum\limits_{k = 1}^{n - 1} {{\mathbf{P}}\left( {{\xi _1} + {\xi _2} = k} \right)} + ... + \sum\limits_{k = 1}^{n - 1} {{\mathbf{P}}\left( {{\xi _1} + {\xi _2} + ... + {\xi _{n - 1}} = k} \right)} = \\ = 1 + \frac{1}{n}C_{n - 1}^1 + \frac{1}{{{n^2}}}\sum\limits_{k = 1}^{n - 1} {C_{k - 1}^1} + ... + \frac{1}{{{n^{n - 1}}}}\sum\limits_{k = 1}^{n - 1} {C_{k - 1}^{n - 2}} = \\ = 1 + \frac{1}{n}C_{n - 1}^1 + \frac{1}{{{n^2}}}C_{n - 1}^2 + ... + \frac{1}{{{n^{n - 1}}}}C_{n - 1}^{n - 1} = \boxed{{{\left( {1 + \frac{1}{n}} \right)}^{n - 1}}} \\ \end{gathered} \]$$

Ответ выделен в рамочку. Здесь я пользовался формулой $\[\sum\limits_{m = 0}^n {C_m^k} = C_{n + 1}^{k + 1}\]$, доказательство очень простое на основе главного тождества биномиальных коэффициентов.