Задача о математическом ожидании количества случайных слагаемых
Недавно Майкл Пенн разбирал интересную задачу, которую я cформулирую так:
Сколько в среднем нужно взять случайных натуральных чисел, равномерно распределенных на отрезке от 1 до $$n$$, чтобы их сумма превысила $$n$$?
Конструкция в его решении выглядит достаточно искусственной и требует непростых рассуждений. Я предлагаю решить задачу «в лоб», без применения хитрых конструкций. Оказывается, это можно сделать, немного повозившись с преобразованием сумм.
Решение
Ясно, что одного числа $$a_1\in[1,n]$$ недостаточно, чтобы сумма $$a_1$$ превысила $$n$$. Два числа уже могут в сумме $$a_1+a_2$$ дать число, большее $$n$$. Если это произошло, испытание завершается. В противоположном случае нужно выбрать еще одно число и т. д.
Обозначим через $$P_n(k)$$ вероятность неуспеха — вероятность того, что сумма случайно выбранных $$k$$ чисел окажется не больше $$n$$:
$$P_n(k)=P\left(\sum\limits_{i=1}^{k}a_i\leq n\right).$$(1)
Cхему одного испытания можно представить в виде дерева, где добавление нового числа при неуспехе каждый раз порождает развилку:
$$ \tikzstyle{level 1}=[level distance=5cm] \tikzstyle{level 2}=[level distance=6cm] \tikzstyle{bag}=[fill=red!20] \tikzstyle{end}=[fill=green!20] \begin{tikzpicture}[grow=right, sloped,sibling distance = 15mm] \node[bag, label=above:{$P_n(1)=1$}] {$a_1\leq n$} child[edge from parent/.style={draw, -latex, line width=0.8mm, black!30}] { node[end] {$a_1+a_2>n$} edge from parent node[below,black] {$P_n(1)-P_n(2)$} } child[edge from parent/.style={draw, -latex, line width=3mm, black!30}] { node[bag] {$a_1+a_2\leq n$} child[edge from parent/.style={draw, -latex, line width=1.2mm, black!30}] { node[end] {$a_1+a_2+a_3>n$} edge from parent node[below,black] {$P_n(2)-P_n(3)$} } child[edge from parent/.style={draw, -latex, line width=1.8mm, black!30}] { node[bag, label=right:{...}] {$a_1+a_2+a_3\leq n$} edge from parent node[above,black] {$P_n(3)$} } edge from parent node[above,black] {$P_n(2)$} }; \end{tikzpicture} $$
Из нее мы видим, что вероятность того, что в одном испытании будет взято ровно $$k$$ чисел, равна $$P_n(k-1)-P_n(k)$$. Действительно, событие, противоположное (1), состоит в том, что сумма произвольного не превосходящего $$k$$ количества случайно взятых чисел будет больше $$n$$. Его вероятность есть $$1-P_n(k)$$. Аналогично, вероятность того, что сумма произвольного не превосходящего $$k-1$$ количества случайно взятых чисел будет больше $$n$$ есть $$1-P_n(k-1)$$. Разность этих величин как раз и дает $$P_n(k-1)-P_n(k)$$.
Тогда искомое среднее $$N$$ можно выразить как
$$\begin{align*}N&=2\left[P_n(1)-P_n(2)\right]+3\left[P_n(2)-P_n(3)\right]+\ldots+(n+1)\left[P_n(n)-P_n(n+1)\right]=\\ &=2+P_n(2)+P_n(3)+P_n(4)+\ldots+P_n(n).\end{align*}$$(2)
В этой сумме мы раскрыли скобки и сгруппировали промежуточные слагаемые. Ясно, что дерево вероятностей конечно, и последняя ненулевая вероятность $$P_n(n)=1/n^n$$ в нем соответствует случаю $$a_1=a_2=\ldots=a_n=1$$. Поэтому сумма в (2) заканчивается на нулевом слагаемом $$-(n+1)P_n(n+1)=0$$, тем самым кроме сгруппированных промежуточных слагаемых никаких слагаемых в конце в ней нет.
Начнем с вычисления $$P_n(2)$$. Пространство элементарных событий для двух натуральных чисел от 1 до $$n$$ можно представить матрицей $$n\times n$$, в которой неудачные исходы $$a_1+a_2\leq n$$ расположены под главной диагональю:
$$ \tikzstyle{bad}=[fill=red!10!white, minimum width=0.98cm, minimum height=0.98cm] \tikzstyle{good}=[fill=green!10!white, minimum width=0.98cm, minimum height=0.98cm] \begin{tikzpicture}[scale=1] \draw[step=1] (0,0) grid (5,5); \node[bad] at (0.5,0.5) {2}; \node[bad] at (1.5,0.5) {3}; \node[bad] at (0.5,1.5) {3}; \node[good] at (4.5,4.5) {$2n$}; \foreach \x in {0,...,4} { \node[good] at (0.5+\x, 4.5-\x) {$n$+1}; } \foreach \x in {0,...,3} { \node[good] at (1.5+\x, 4.5-\x) {$n$+2}; } \foreach \x in {0,...,2} { \node[good] at (2.5+\x, 4.5-\x) {}; } \foreach \x in {0,...,1} { \node[good] at (3.5+\x, 4.5-\x) {}; } \foreach \x in {0,...,3} { \node[bad] at (0.5+\x, 3.5-\x) {$n$}; } \foreach \x in {0,...,2} { \node[bad] at (0.5+\x, 2.5-\x) {}; } \draw[->] (0,-0.5) -- ++(5,0) node[pos=0.5,below] {$a_1$}; \draw[->] (-0.5,0) -- ++(0,5) node[pos=0.5,left] {$a_2$}; \end{tikzpicture} $$
Искомая вероятность $$P_n(2)$$ равна отношению количества красных квадратиков к общему количеству квадратиков. Вычисляя, получаем, что она связана с треугольными числами $$T_n=n(n+1)/2$$:
$$P_n(2)={1\over n^2}\sum\limits_{a_1+a_2\leq n}1={1\over n^2}\sum\limits_{a_1=1}^{n-1}n-a_1={1\over n^2}\cdot{(n-1)n\over 2}={T_{n-1}\over n^2}={C_n^2\over n^2}.$$
Перейдем к $$P_n(3)$$. Пространство элементарных событий для трех чисел можно представить себе как часть куба $$n\times n\times n$$, нарезанного на единичные кубики. Нас интересуют неудачные исходы $$a_1+a_2+a_3\leq n$$, которые соответствуют такой пирамидке:
$$ \usetikzlibrary {perspective} \colorlet{cube color}{blue!50!cyan} \begin{tikzpicture}[3d view={110}{25},scale=0.8, line join=round, line cap=round,every path/.style={cube color,thick}] \def\k{1.2} \def\n{2} \draw[black,thin,->] (0,0) -- ++(0,4.4) node[pos=0.9,above] {$a_1$}; \draw[black,thin,->] (0,0) -- ++(4.5,0) node[pos=0.9,left] {$a_2$}; \draw[black,thin,->] (0,0,0) -- ++(0,0,4.2) node[pos=0.9,left] {$a_3$}; \foreach \z in {0,...,\n} { \pgfmathsetmacro{\ymax}{\n-\z} \foreach \y in {0,...,\ymax} { \pgfmathsetmacro{\xmax}{\ymax-\y} \foreach \x in {0,...,\xmax} { \draw[fill=cube color!30] (\k*\x, \k*\y, \k*\z+1) -- ++(1, 0, 0) -- ++(0, 1, 0) -- ++(-1, 0, 0) -- cycle; \draw[fill=cube color!50] (1+\k*\x, \k*\y, \k*\z) -- ++(0, 0, 1) -- ++(0, 1, 0) -- ++(0, 0, -1) -- cycle; \draw[fill=cube color!70] (\k*\x, \k*\y+1, \k*\z) -- ++(1, 0, 0) -- ++(0, 0, 1) -- ++(-1, 0, 0) -- cycle; } } } \end{tikzpicture}$$
Здесь мы можем предположить, что вероятность $$P_n(3)$$ выражается через тетраэдральные числа $$\inlineTe_n=\sum_{k=1}^nT_n$$. Формально этот результат получается при вычислении суммы на множестве $$a_1+a_2+a_3\leq n$$ по слоям: сначала по слою $$a_1+a_2+a_3=n$$, потом по слою $$a_1+a_2+a_3=n-1$$ и т. д:
$$ \usetikzlibrary {perspective} \colorlet{cube color}{blue!50!cyan} \begin{tikzpicture}[3d view={110}{25},scale=0.8, line join=round, line cap=round,every path/.style={cube color,thick}] \def\k{1.2} \def\n{2} \foreach \z in {0,...,\n} { \pgfmathsetmacro{\ymax}{\n-\z} \foreach \y in {0,...,\ymax} { \pgfmathsetmacro{\xmax}{\ymax-\y} \foreach \x in {0,...,\xmax} { \pgfmathtruncatemacro{\layer}{\x + \y + \z} \ifnum \layer=2 \colorlet{cube color}{blue!50!cyan} \fi \ifnum \layer=1 \colorlet{cube color}{olive} \fi \ifnum \layer=0 \colorlet{cube color}{orange} \fi \draw[fill=cube color!30] (\k*\x, \k*\y, \k*\z+1) -- ++(1, 0, 0) -- ++(0, 1, 0) -- ++(-1, 0, 0) -- cycle; \draw[fill=cube color!50] (1+\k*\x, \k*\y, \k*\z) -- ++(0, 0, 1) -- ++(0, 1, 0) -- ++(0, 0, -1) -- cycle; \draw[fill=cube color!70] (\k*\x, \k*\y+1, \k*\z) -- ++(1, 0, 0) -- ++(0, 0, 1) -- ++(-1, 0, 0) -- cycle; \pgfmathsetmacro{\s}{5.5+5*(\n-\layer)} \pgfmathsetmacro{\p}{-1-2.5*(\n-\layer)} \pgfmathsetmacro{\t}{0.45} \draw[fill=cube color!30] (\k*\x+\p, \k*\y+\s, \k*\z+1+\t) -- ++(1, 0, 0) -- ++(0, 1, 0) -- ++(-1, 0, 0) -- cycle; \draw[fill=cube color!50] (1+\k*\x+\p, \k*\y+\s, \k*\z+\t) -- ++(0, 0, 1) -- ++(0, 1, 0) -- ++(0, 0, -1) -- cycle; \draw[fill=cube color!70] (\k*\x+\p, \k*\y+1+\s, \k*\z+\t) -- ++(1, 0, 0) -- ++(0, 0, 1) -- ++(-1, 0, 0) -- cycle; } } } \node[black] at (0,4,1.25) {$=$}; \node[black] at (0,10,2.25) {$+$}; \node[black] at (0,15.5,3.15) {$+$}; \end{tikzpicture}$$
$$\begin{align*} P_n(3)&={1\over n^3}\sum\limits_{a_1+a_2+a_3\leq n}1={1\over n^3}\left(\sum\limits_{a_1+a_2+a_3=n}1+\sum\limits_{a_1+a_2+a_3=n-1}1+\ldots\right)=\\ &={1\over n^3}\left(\sum\limits_{a_1+a_2\leq n-1}1+\sum\limits_{a_1+a_2\leq n-2}1+\ldots\right). \end{align*}$$
Каждая из сумм в скобках уже вычислена на предыдущем этапе. Действительно, количество элементов в слоях задается треугольными числами. Подставляем:
$$P_n(3)={1\over n^3}(T_{n-2}+T_{n-3}+\ldots)={Te_{n-2}\over n^3}={C_n^3\over n^3}.$$
Идея с послойным вычислением суммы без
$$P_n(k)={C_n^k\over n^k}.$$(3)
Подставим в (2):
$$N=2+{C_n^2\over n^2}+{C_n^3\over n^3}+{C_n^4\over n^4}+\ldots+{C_n^n\over n^n}.$$
А это есть не что иное, как разложение $$(1+1/n)^n$$ через бином Ньютона. Ответ:
$$N=\left(1+{1\over n}\right)^n.$$
Обсуждение
В пределе неограниченно больших $$n$$ ожидаемое количество слагаемых стремится к $$e$$. Да и сама задача в этом пределе переходит в известную задачу о математическом ожидании количества случайных величин, равномерно распределенных на интервале от 0 до 1, таких чтобы их сумма превзошла 1. О том, что это математическое ожидание равно $$e$$, я узнал из книги Мартина Гарднера «Математические досуги»:
Идея рассуждений в непрерывном случае аналогична нашему решению, а детали вычислений оказываются проще. Суммы заменяются на интегралы от многочленов, которые без проблем вычисляются и дают меру симплекса, построенного на единичных отрезках на осях координат: $$P(k)=1/k!$$. Сумма в (2) становится бесконечной и превращается в известный ряд для числа $$e=1+1/1!+1/2!+\ldots$$
В дискретном случае приходится заниматься конечными суммами, которые сводятся к треугольным числам и их обобщениям. Надо сказать, что для решения никакие их свойства не использовались. Явный вид $$P_n(k)$$ можно было получить для нескольких начальных $$k$$ и затем по индукции доказать общий вид (3). Либо можно воспользоваться свойствами чисел, стоящих на местах с номером $$k$$ в треугольнике Паскаля:
$$ \makeatletter \newcommand\binomialcoefficient[2]{ % Store values \c@pgf@counta=#1% n \c@pgf@countb=#2% k % % Take advantage of symmetry if k > n - k \c@pgf@countc=\c@pgf@counta% \advance\c@pgf@countc by-\c@pgf@countb% \ifnum\c@pgf@countb>\c@pgf@countc% \c@pgf@countb=\c@pgf@countc% \fi% % % Recursively compute the coefficients \c@pgf@countc=1% will hold the result \c@pgf@countd=0% counter \pgfmathloop% c -> c*(n-i)/(i+1) for i=0,...,k-1 \ifnum\c@pgf@countd<\c@pgf@countb% \multiply\c@pgf@countc by\c@pgf@counta% \advance\c@pgf@counta by-1% \advance\c@pgf@countd by1% \divide\c@pgf@countc by\c@pgf@countd% \repeatpgfmathloop% \the\c@pgf@countc% } \makeatother \begin{tikzpicture}[scale=0.8] \node[red, right] at (0.9,-0.5) {Натуральные числа}; \node[orange, right] at (1.4,-1.5) {Треугольные числа}; \node[olive, right] at (1.9,-2.5) {Тетраэдральные числа}; \node[right] at (2.4,-3.5) {...}; \foreach \n in {0,...,7} { \foreach \k in {0,...,\n} { \ifnum \k=0 \node[black] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=1 \node[red,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=2 \node[orange,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=3 \node[olive,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=4 \node[green!70!black,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=5 \node[blue,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=6 \node[magenta,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi \ifnum \k=7 \node[purple,node font=\bf] (\n\k) at (\k-\n/2,-\n) {\binomialcoefficient{\n}{\k}}; \fi } } \end{tikzpicture}$$
Оставьте свой комментарий