生成函数

动机

我们经常遇到一些比较复杂的数据集，然后对它做运算，它会变得更加的复杂。一个例子是：我们假设第一个数据集是随机变量$X_1$给定值的概率，而第二个数据集是随机变量$X_2$给定的值的概率，利用这些信息，我们虽然可以通过蛮力计算$X_1+X_2$取某个值的概率，但我们仍然希望能避免这种繁琐的计算，接下来，我们将学习的研究这种问题的特殊情形，我们将给出一个例子，设两个服从泊松分布的随机变量。

$X_1$是服从参数为$5$的泊松分布，再设一个$X_2$是服从参数为$7$的泊松分布，即：

$ \begin{aligned} &\mathrm{Prob}(X_1 = m) = 5^me^{-5}/m!\\ &\mathrm{Prob}(X_2=n) = 7^ne^{-1}/n! \end{aligned} $

其中$m,n$取遍非负整数，先设$k$是非负整数，我们考察$X_1+X_2 =k$的情况。不妨设$X_1 = l$，由于$X_1$介于$0$和$k$中间，那么$X_2$可以被我们设为$k-l = X_2$，由于两个随机变量相互独立，那么一起发生的概率就是两个概率事件的乘积，因此我们有

$\begin{aligned} \mathrm{Prob}(X_1+X_2 = k) &= \sum^k_{l=0}\mathrm{Prob}(X_1 = l)\mathrm(Prob)(X_2 = k-l)\\ &=\sum^k_{l=0}\frac{5^le^{-5}}{l!}\frac{7^{k-l}e^{-7}}{(k-l)!} \end{aligned}$

这是个很难计算的东西，但我们可以使用一些小技巧

• 注意到因子$1/l!(k-1)!$，他和我们的二项式系数很像，因为${k\choose l} = \frac{k!}{l!(k-l)!}$，那么我们等一下将乘1，也就是$k!/k!$。这样子我们就可以把$1/k!$提到外面去。
• 式子中的$e^{-5}$和$e^{-7}$与$l$无关，因此也可以提出来，我们就有$e^{-12}$
• 那么我们可以简化得到$\frac{e^{-12}}{k!}\sum^k_{l=0}{k\choose l}5^l7^{k-l}$，后面可以还原成二项式，那么久是$(5+7)^k = 12^k$

综上所述，我们就有

$\mathrm{Prob}(X_1+X_2=k) = \frac{12^ke^{-12}}{k!}$

即我们得到了服从$12$为参数的泊松分布。有一个推广的定理，可以由归纳法得到：

---

服从泊松分布的随机变量之和：已知存在$n$个相互独立的随机变量，若其分别服从参数为$\lambda_1,\lambda_2,\cdots,\lambda_n$的泊松分布，那么它们的和服从参数为$\lambda_1+\lambda_2+\cdots+\lambda_n$的泊松分布。

这种计算非常复杂，因此我们在下面引入一些生成函数的理论，然后讲讲应用

---

定义

我们定义序列的生成函数，通常应用在不同事件的概率或者分布的矩。我们来看几个例子

---

定义：生成函数 已知序列$\{a_n\}^\infty_{n=0}$，它的生成函数我们定义为：

$G_a(s) = \sum^\infty_{n=0}a_ns^n$

其中$s$是使得函数收敛的任意数

---

我们都知道 斐波那契数列，它定义$F_0 =0$，$F_1 = 1$，它的一半公式是$F_n = F_{n-1}+F_{n-2}$，前几项是$0,1,1,2,3,5,8,13,\cdots$。但这个公式不好用，例如$F_{10} = 55$，但$F_{100}$是一个有21位的巨大数字，计算这个很枯燥，而$F_{2011}$和更是超过了400位了。而现在，我们试试生成函数，利用它来计算，我们给定

$G_F(s) = \sum^\infty_{n=0}F_ns^n$

我们单独给出$n=0,1$时候的项，当$n\geq 2$，利用递推关系$F_n = F_{n-1}+F_{n-1}$有：

$\begin{aligned} G_F(s)=&F_0+F_1s+\sum^\infty_{n=0}(F_{n-1}+F_{n-2})s^n\\ =&0 +s+\sum^\infty_{n=2}F_{n-1}s^n+\sum^\infty_{n=2}F_{n-2}s^n \end{aligned}$

我们现在提出一些方幂来对和式重新标记

$\begin{gathered} G_{F}(s) =s+s\sum_{n=2}^{\infty}F_{n-1}s^{n-1}+s^{2}\sum_{n=2}^{\infty}F_{n-2}s^{n-2} \\ =s+s\sum_{m=1}^{\infty}F_{m}s^{m}+s^{2}\sum_{m=0}^{\infty}F_{m}s^{m}. \end{gathered}$

由于$F_0=0$，因此我们可以把它变成从$m=0$开始技术，那么上面两个和式就是$G_F(s)$，那么就有

$G_F(s) = s+sG_F(s)+s^2G_F(s)$

利用二次公式即得

$G_F(s) = \frac{s}{1-s-s^2}$

为了处理这个式子，我们利用部分分式，那么有

$\frac{s}{1-s-s^2} = \frac{a}{1-As}+\frac{b}{1-Bs}$

简单的计算$A,B$，则有$A=\frac{1+\sqrt{5}}{2}$，而$B = \frac{1-\sqrt{5}}{2}$。而$a,b$的计算也颇为简单，有关系是$-(aB+bA) =1$得到$b = -a$，因此，带入可以得到$a = \frac{1}{\sqrt{5}}$，$b = -\frac{1}{\sqrt{5}}$，我们就得到

$G_F(s) = \frac{s}{1-s-s^2} = \frac{1}{\sqrt{5}}\frac{1}{1-As} - \frac{1}{\sqrt{5}}\frac{1}{1-Bs}$

利用几何级数展开就有

$G_F(s) = \frac{1}{\sqrt{5}}\sum^\infty_{n=0}A^ns^n - \frac{1}{\sqrt{5}}\sum^\infty_{n=0}B^ns^n$

最后得到

$\sum_{n=0}^{\infty}\left[{\frac{1}{\sqrt{5}}}\left({\frac{1+{\sqrt{5}}}{2}}\right)^{n}-{\frac{1}{\sqrt{5}}}\left({\frac{1-{\sqrt{5}}}{2}}\right)^{n}\right]s^{n}$

我们就得到了第$n$个斐波那契数列的公式。

---

比内公式： 设$\{F_n\}^\infty_{n=0}$是斐波那契级数，其中$F_0 =0,F_1 =1$，且$F_{n+2} = F_{n+1}+F_n$，于是

$F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$