Производящие функции: алгебра для вероятностей

Задача на технику: случайная величина принимает значения $0,1,2,3$ с вероятностями $\frac{1}{8},\frac{3}{8},\frac{3}{8},\frac{1}{8}$. Найдите дисперсию. Можно честно: суммировать $k^2{p}_k$, вычитать квадрат среднего. А можно записать четыре коэффициента в один многочлен и два раза его продифференцировать — ответ выйдет сам. Производящая функция — это упаковка для распределения: все вероятности в одном объекте, а операции над распределениями (сумма величин, поиск моментов) превращаются в школьную алгебру многочленов.

Определение: распределение как многочлен#

Пусть дискретная случайная величина (о них подробно рассказано в уроке про дискретные случайные величины) принимает неотрицательные целые значения $k=0,1,2,\dots$ с вероятностями $p_k$. Производящая функция — это степенной ряд, в котором $p_k$ сидит при степени $s^k$:

Соответствие взаимно однозначное: зная $G(s)$, вытащить $p_k$ можно вторым способом — коэффициентом при $s^k$; зная распределение, собрать $G$ можно за минуту. Два обязательных свойства: при $s=1$ ряд суммируется в единицу — $G(1)=\sum p_k=1$, это встроенная проверка нормировки; при $s=0$ получаем $p_0$ — вероятность нулевого значения. Обратная связь с комбинаторикой прямая: производящая функция последовательности — тот же аппарат, что в биноме Ньютона, только коэффициенты теперь вероятности.

Живой пример. Один бросок монеты с вероятностью орла $p$: число орлов даёт $G(s)=q+ps$, где $q=1-p$ — коэффициент $q$ при $s^0$ (ноль орлов), $p$ при $s^1$ (один орёл). Два независимых броска? Распределение суммы — и тут случается главное чудо метода: производящая функция суммы независимых величин равна произведению их производящих функций:

Для двух бросков: $(q+ps{)}^2=q^2+2qps+p^2{s}^2$ — коэффициенты мгновенно дают вероятности нуля, одного и двух орлов. Никаких таблиц, никакой свёртки сумм по индексам: раскрыли скобки — прочли распределение. Причина проста: при перемножении многочленов степень $s^k$ собирается всеми способами разбить $k$ между сомножителями, ровно как события складываются в сумму величин.

Моменты через производные#

Дифференцируем определение: $G^{\prime }(s)=\sum k{p}_k{s}^{k-1}$ — коэффициент $k$ вылезает из степени по правилу дифференцирования. Подставим $s=1$ и узнаем в левой части знакомую сумму:

Вторая производная даёт $G^{\prime \prime }(1)=\sum k(k-1)p_k=E[X(X-1)]$ — «факториальный момент», из которого дисперсия собирается одной строкой:

Схема работы всегда одна: получили распределение — записали $G(s)$ — продифференцировали дважды — выписали моменты. Никаких сумм с $k^2$, которые в непрерывных аналогах превращаются в кошмар интегрирования. Полная таблица моментных формул живёт в статье про производящую функцию моментов, а базовые определения ожидания и разброса — в уроке про матожидание и дисперсию.

Биномиальное распределение: два дифференцирования#

Число успехов в $n$ испытаниях схемы Бернулли — сумма $n$ независимых индикаторов, у каждого из которых $G(s)=q+ps$. Значит, у суммы $G(s)=(q+ps{)}^n$ — и дальше чистая механика:

Вся классическая таблица моментов биномиального закона — три строки алгебры. Сравните с прямым подсчётом $\sum k^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k{q}^{n-k}$, ради которого в учебниках выписывают комбинаторные тождества: производящая функция делает ту же работу автоматически.

Пуассон: экспонента вместо многочлена#

У распределения Пуассона с параметром $\lambda$ вероятности $p_k=\frac{{\lambda }^k}{k!}{e}^{-\lambda }$. Соберём ряд: $\sum \frac{{\lambda }^k}{k!}{s}^k{e}^{-\lambda }=e^{\lambda s}{e}^{-\lambda }=e^{\lambda (s-1)}$ — производящая функция оказалась экспонентой, и дифференцировать её легче лёгкого:

Заодно бесплатный бонус: производящая функция объясняет пуассоновское приближение биномиального закона. При $n\to \infty$, $p\to 0$, $np\to \lambda$ производящая функция $(q+ps{)}^n=(1+\frac{\lambda (s-1)}{n}{)}^n$ стремится к $e^{\lambda (s-1)}$ — точь-в-точь пуассоновская. Биномиальный закон переходит в пуассоновский прямо на уровне производящих функций, без единого предельного перехода в вероятностях.

Где метод незаменим#

Три сценария, в которых без производящих функций пришлось бы мучиться. Первый — суммы независимых величин: ветвящиеся процессы (потомство частиц), случайное блуждание по капиталу, очереди; там свёртки громоздки, а произведения функций элементарны. Второй — доказательства принадлежности: предельные теоремы удобнее всего проверять именно на уровне производящих функций — так, у биномиального и пуассоновского мы это видели выше, а формулировки предельных переходов для центральной предельной теоремы в родственном аппарате характеристических функций устроены так же. Третий — моменты без мучений: любую формулу вида «среднее плюс-минус разброс» метод выдаёт дифференцированием.

Ошибки в вычислениях#

• Продифференцировали $(q+ps{)}^n$ по $p$ вместо $s$: переменная дифференцирования — аргумент $s$, параметры трогать не нужно.
• Забыли подставить $s=1$: производная сама по себе — функция, момент появляется только в точке единица.
• Потерян нулевой коэффициент: $p_0$ участвует в $G(1)=1$ и в проверках; распределение без $p_0$ — неполное.
• Проверка нормировки пропущена: $G(1)=1$ за одну секунду ловит опечатки в коэффициентах — например, дроби, не сходящиеся в единицу.

Разбор классической задачи на сумму: игрока бросают две независимые кости, на каждой может выпасть от нуля до двух очков с равными шансами. Производящая функция одной кости $G(s)=\frac{1+s+s^2}{3}$, суммы — квадрат: $G_{X+Y}(s)=\frac{(1+s+s^2{)}^2}{9}$. Раскрываем числитель: $1+2s+3s^2+2s^3+s^4$. Коэффициенты читаются напрямую: вероятность суммы 2 равна $\frac{3}{9}=\frac{1}{3}$, суммы 0 и 4 — по $\frac{1}{9}$, крайние суммы редки, середина часта. Девять исходов посчитаны без единой таблицы комбинаций — весь ответ сидит в четырёх коэффициентах многочлена.

Считаем моменты на пальцах: для биномиального $B(n,p)$ производящая функция $G(s)=(1-p+ps{)}^n$. Первая производная в единице: $G^{\prime }(1)=np(1-p+p{)}^{n-1}=np$ — математическое ожидание прочитано без единого суммирования. Вторая производная $G^{\prime \prime }(s)=n(n-1)p^2(1-p+ps{)}^{n-2}$ даёт $G^{\prime \prime }(1)=n(n-1)p^2$, и дисперсия собирается по формуле $\mathrm{Var}X=G^{\prime \prime }(1)+G^{\prime }(1)-(G^{\prime }(1){)}^2=np(1-p)$. Три строки вместо страницы с комбинаторными суммами — за это производящие функции и любят.

Цикл о случайных процессах замкнут: от цепей Маркова через пуассоновский поток к алгебре распределений. Определения метода — в статьях про производящую функцию и дисперсию, сводка формул — в шпаргалке по комбинаторике; а если захочется потрогать распределения руками, вернитесь к дискретным случайным величинам.