• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

生成函数学习笔记(三)——概率生成函数初探

开发技术 开发技术 2周前 (04-06) 3次浏览

前言

一个挺早就知晓其存在的诡异科技,只不过当时遇到它的题目是用其他的做法搞过去的。

这次好好研读了一下杨懋龙神仙的论文《浅谈生成函数在掷骰子问题上的应用》,还是有不少收获的。(尽管看了一半就看不下去了

基本定义

假设存在一个离散随机变量(X)满足(P(X=i)=a_i),那么它的概率生成函数就应该是:

[F(x)=sum_{i=0}^{+infty}P(X=i)x^i
]

定义看起来很简单,更重要的是它的几个性质。

重要性质

性质一

(X)作为一个离散随机变量,显然它生成所有数的概率总和应当是(1),也就是说:

[F(1)=sum_{i=0}^{+infty}P(X=i)=1
]

性质二

我们对于(F(x))求导,得到:

[F'(x)=sum_{i=0}^{+infty}iP(X=i)x^{i-1}
]

然后再代入(x=1),得到:

[F'(1)=sum_{i=0}^{+infty}iP(X=i)
]

发现这玩意恰好是(X)的期望值!

也就是说:

[E(X)=F'(1)
]

性质三

我们继续对这个式子求导,可以发现:

[E(X^{underline{k}})=F^{(k)}(1)
]

性质四

对于方差有这样一个公式:

[Var(X)=E((X-E(X)))^2)=E(X^2-2XE(X)+E(X)^2)=E(X^2)-E(X)^2
]

考虑(E(X^2)),它可以这样表示:

[E(X^2)=E(X(X-1))+E(X)=E(X^{underline{2}})+E(X)=F”(1)+F'(1)
]

所以把这个式子代回原式,得到:

[Var(x)=F”(1)+F'(1)-(F'(1))^2
]

例题

讲完这些性质概率生成函数也就告一段落了,接下来就是例题。

这里就先列出一道吧:【洛谷4548】[CTSC2006] 歌唱王国(概率生成函数)。


程序员灯塔
转载请注明原文链接:生成函数学习笔记(三)——概率生成函数初探
喜欢 (0)