Warning: session_start(): open(/tmp/sess_d342e8c25c62e735f94c36e0a50a632f, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 随机串包含给定串的期望长度 =====
设有一串 $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$ 即可得到结论。