跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
intrepidsword
»
zhongzihao
»
random_string
2020-2021:teams:intrepidsword:zhongzihao:random_string
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
===== 随机串包含给定串的期望长度 ===== 设有一串 $S$,从一个空串开始,每次等概率随机往后面加一个字符,包含 $S$ 时停止,求串长度的期望。 设 $F(x)$ 表示恰在长度为 $x$ 停止的概率生成函数,$G(x)$ 表示长度为 $x$ 仍未停止的生成函数。那么有 $$ \begin{aligned} 1+xG(x)&=F(x)+G(x)\\ G(x)\cdot\frac{x^{n}}{|\Sigma|^{n}}&=F(x)\sum_{i=1}^{|S|}[1..i\text{ is border}]\frac{x^{n-i}}{|\Sigma|^{n-i}} \end{aligned} $$ 所求为 $F'(1)$。对式 $1$ 求导得 $G(x)+xG'(x)=F'(x)+G'(x)$,即 $F'(1)=G(1)$。式 $2$ 中令 $x=1$ 即可得到结论。
2020-2021/teams/intrepidsword/zhongzihao/random_string.txt
· 最后更改: 2021/01/24 15:13 由
toxel
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部