И начать хочу с той же задачи, с которой начинает Кнут. Бросим две обычные (честные!) игральные кости. Результат может быть от 2 до 12 очков — но (как известно любому игроку в настольные игры!) шанс выкинуть 7 очков (1/6) гораздо больше, чем выкинуть 2 или 12 очков (1/36). Так вот, вопрос:
А нельзя ли сделать такие две кости, чтобы суммарное число очков принимало все значения от 2 до 12 равновероятно?
Вопрос не такой очевидный — ведь если кинуть монетку, равновероятно падающую сторонами «0» и «1», и независимо от неё «трёхгранную» кость, равновероятно дающую «1», «3», и «5» — то суммарный результат будет равновероятно принимать все значения от 1 до 6 — то есть как раз быть обычной игральной костью.
И это тот сюжет, когда можно достаточно естественно если не придумать, то рассказать характеристические функции для случайных величин.
Пусть у нас есть случайная величина — результат бросания кости — которая принимает неотрицательные целые значения. Её распределение — это то, с какой вероятностью p_n принимается какое значение n. То есть последовательность чисел. А в стандартный — и очень мощный — приём в комбинаторике это превратить последовательность чисел p_n в производящую функцию
F(x) = \sum_n p_n x^n.
В скобках — в этом канале производящие функции уже несколько раз появлялись: вот тут в связи с числами Каталана, вот тут в связи с решёткой Е_8, вот тут в связи с разбиением числа в сумму слагаемых и пентагональной теоремой Эйлера и (чуть ниже) тройным произведением Якоби / предсказанием позитрона Дираком. Первая ссылка, которая мне тут приходит в голову — это отличные «Лекции о производящих функциях» Сергея Константиновича Ландо, насколько я понимаю, потом легшие в основу первой части его же книги «Введение в дискретную математику» (электронная версия / МЦНМО). Но я дальше буду писать так, как будто о производящих функциях мы ничего не знаем.
Так вот — пусть у нас есть две случайные величины: первая принимает значение n с вероятностью p_n, вторая — с вероятностью q_n. Соберём из этих последовательностей производящие функции:
F(x) = \sum_n p_n x^n.
G(x) = \sum_m q_m x^m.
Тогда, если эти случайные величины независимы, вероятность того, что первая приняла значение n, а вторая m, равно p_n q_m; в этом случае сумма принимает значение m+n, и соответствующий вклад в производящую функцию, которую мы сопоставим сумме величин, равен
p_n q_m x^{n+m} = (p_n x^n)* (q_m x^m).
То есть это произведение соответствующих мономов. Значит, производящая функция для распределения суммы независимых случайных величин — это просто произведение производящих функция для распределений слагаемых, F(x)*G(x) !