2020-2021:teams:intrepidsword:zhongzihao:random_string
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:intrepidsword:zhongzihao:random_string [2021/01/24 15:07] toxel 创建 |
2020-2021:teams:intrepidsword:zhongzihao:random_string [2021/01/24 15:13] (当前版本) toxel |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ===== 随机串包含给定串的期望长度 ===== | ===== 随机串包含给定串的期望长度 ===== | ||
| + | 设有一串 $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.1611472052.txt.gz · 最后更改: 2021/01/24 15:07 由 toxel
