定义
我们定义一个形式幂级数 (A(x)) 称之为离散随机变量 (X) 的概率生成函数，当且仅当满足
[A(x)=sum_{i geq 0}Pr[X=i]x^i
]
性质
[egin{aligned}
A(1)=sum_{i geq 0}Pr[X=i]=1\A'(1)=sum_{igeq 0} iPr[X=i] = mathbb{E}[X]\A^{(n)}(1)=mathbb{E}[X^{underline n}]\
end{aligned}
]
一个离散随机变量 (X) 的方差 (DX) 定义为
[DX=mathbb{E}[(X-mathbb{E}[X])^2]
]
根据期望的线性性，我们可以展开：
[egin{aligned}DX&=mathbb{E}[(X-mathbb{E}[X])^2]\&=mathbb{E}[X^2-2Xmathbb{E}[X]+mathbb{E}[X]^2]\&=mathbb{E}[X^2]-mathbb{E}[2Xmathbb{E}[X]]+mathbb{E}[mathbb{E}[X]^2]\&= mathbb{E}[X^2]-2mathbb{E}[X]^2+mathbb{E}[X]^2\&= mathbb{E}[X^2]-mathbb{E}[X]^2\&= mathbb{E}[X^2]-(A'(1))^2end{aligned}
]
注意到
[x^k=sum_{i=0}^k left{^k_i
ight}x^{underline i}
]
所以
[egin{aligned}DX&= E[x^{underline 1}+x^{underline 2}]-(A'(1))^2\&= A'(1)+A''(1)-(A'(1))^2end{aligned}
]
对于某个概率生成函数 思考方向是 只要能求出它的封闭形式 对封闭形式求导 把 (1) 代入封闭形式 就能得到一个关于期望的不错的式子。
常见的概率模型
二项分布
二项分布（Binomial distribution）是n个独立的是/非试验中成功的次数的离散概率分布，其中每次试验的成功概率为(p)。
分布列 (inom N n p^nq^{N-n},n=0,1,2,ldots,N) 生成函数是 ((1-p+px)^N)
负二项分布
负二项分布是统计学上一种描述在一系列独立同分布的伯努利试验中，失败次数到达指定次数时成功次数的离散概率分布。
分布列 $inom{alpha +n-1}{n} p^{alpha} q^n,n = 0,1,2,ldots $ ，生成函数 ((frac{p}{1-qx})^{alpha})
剩下的我也看不懂。
例题
「清华集训2016」如何优雅地求和
给定一个 (m) 次多项式 (f(x)) 的 (m+1) 个点值，和两个常数 (n,x) 要你求出
[sum_{k=0}^n f(k)inom n k x^k (1-x)^{n-k}
]
(n leq 10^9,m leq 2 imes 10^4)
首先发现这个东西十分像二项分布的式子。所以这个题实际上是求：
设一个事件的成功概率为 (x) 做 (0,1,2,ldots,n) 次成功次数为 (X)， (mathbb{E}[F(X)]) 的期望。
首先发现(f) 是一个多项式 所以可以用期望的线性性拆开。现在我们主要考虑如何求出 (mathbb{E}[X^n])
考虑二项分布的生成函数 (A(x)=(1-p+px)^n)
[A'(x)=pn(1-p+px)^{n-1}
]
不难发现
[egin{aligned}
A^{(k)}(x)=p^kn^{underline k}(1-p+px)^{n-k}\A^{(k)}(1)=mathbb{E}[X^{underline k}]=p^kn^{underline k}
end{aligned}
]
所以 假设这个 (f) 对应的下降幂多项式是 (g) 的话 那么答案就是
[sum_{i=0}^m g_ip^in^{underline i}
]
于是我们需要搞一个普通幂转下降幂的东西。可以这样：
[egin{aligned}f(x)&=sum_{k}g_kx^{underline k}\&=sum_{k}g_kinom{x}{k}k!\g(x)x!&=sum_{k}(-1)^{x-k}inom{x}{k} f_kend{aligned}
]
多点求值 + FFT 一遍就可以。（二项式反演是要把所有和组合数无关的东西拿过去的）
「CTSC2012」歌唱王国
他们说 遇到用概率生成函数的题要分开考虑加单个和加一块的贡献 反正就是多列几个式子解出来
这个题我们设 (F(x)) 表示到第 (i) 个恰好停止的概率生成函数，(G(x)) 表示到第(i)个不停止的概率生成函数。
根据概率生成函数的性质 答案就是求 (F'(1))
(F(x),G(x)) 的系数我们用 (f_i,g_i) 来表示，可以列出以下式子：
[egin{aligned}
g_{i-1} = g_i+f_i\g_{i}(frac{1}{n})^m = sum_{j=1}^m a_jf_{i+j}(frac{1}{n})^{m-j}
end{aligned}
]
(a_i) 表示 (i) 前缀是否为 border。
首先加一个字符 之后可能结束也可能不结束。
然后直接加入整个 有可能在中间停止 枚举在哪里停止 停止的位置一定是一个 border。
写成生成函数的形式就是
[egin{aligned}
xG(x)+1=G(x)+F(x) (1) \
G(x)(frac{1}{n}x)^m = sum_{i=1}^m a_iF(x)(frac{1}{n}x)^{m-i} (2) \
end{aligned}
]
((1)) 求导，得
[egin{aligned}
G(x)+xG'(x)=G'(x)+F'(x)\
F'(x)=(x-1)G'(x)+G(x) (3)
end{aligned}
]
代入 (x=1)
[egin{aligned}
F'(1)&=G(1)\
G(1)(frac{1}{n})^m &=sum_{i=1}^m a_iF(1)(frac{1}{n})^{m-i} (4)
end{aligned}
]
根据 (F(1)=1) 可以得到
[F'(1)=G(1)=sum_{i=1}^m a_in^i
]
搞个 kmp 就行了。
加强：如何求方差
方差也就是 (F'(1)+F''(1)-(F'(1))^2)
现在问题是如何求 (F''(1))
[egin{aligned}
G'(x)+G''(x)+xG'(x)=G''(x)+F''(x)\F''(x)=xG'(x)+G'(x)\F''(1)=2G'(1)
end{aligned}
]
也就是要求(G'(1))
尝试把 ((2)) 求导
[egin{aligned}
G(x) &= sum_{i=1}^m a_iF(x)n^ix^{-i}\
G'(x)&=sum_{i=1}^m a_in^i(F(x)'x^{-i}-iF(x)x^{-i-1})\
G'(1)&=sum_{i=1}^m a_in^i(F(1)'-iF(1))
end{aligned}
]
就好啦！