趣味问题-模式串在随机串中出现的次数

发表于 更新于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 4 分钟

问题是这样的，讨论 10000 和 00000 这两个串在随机串 中哪个出现的次数期望更多？

考虑重叠，不考虑重叠都分析一下

允许重叠的情况

这个分析起来比较简单，考虑任意一个长度为 5 的模式串 p

设随机变量 表示 是不是 p（i = 0,...,10000-5)

中出现次数的期望（可以重叠） 从上面的分析可以看出，无论模式串 p 的内容是什么，在允许重叠的情况下在 s 中出现次数的期望都是相等的。都等于

可以用上面这个结论去分析原来的问题， 10000 不会重叠，而 00000 会重叠，因此在不允许重叠的情况下，00000 出现次数的期望会比允许重叠的情况小

不允许重叠的情况

直接算期望

E(n)，E'(n) 表示长度为 n 的串中出现模式串次数的期望

  • 对于模式串 10000，有

可以这么理解，

= 前 n-1 个字符中 10000 出现次数的期望（）+ 包含第 n 个字符的 10000 串出现次数的期望（也就是说长度为 n 的串最后五个字符是 10000，概率为 ）

  • 对于模式串 00000 ，有

    第个字符使整个串中的数量增多

    什么情况下第 n 个字符能使整个串中 00000 的数量增多1？答案是 全零后缀的长度模 5 余 4（再加一个 0 就能多凑出来一个 00000），又分为两种情况：一种是 以 结尾，另一种是整个 串全 0，并且长度为 第个字符使整个串中的数量增加全零后缀的长度有后缀

例如

于是

因此可以用归纳法证明

有了上述式子，甚至可以把 的表达式写出来

验证结论

我们用长度为 20 的串来验证上面的结论

1
2
3
4
5
cases = StringJoin /@ Tuples[{"0", "1"}, 20];

Function[str,Total[StringCount[#, str, Overlaps -> False] & /@ cases]] /@ {"10000", "00000"} / (cases // Length)

Function[str,Total[StringCount[#, str, Overlaps -> True] & /@ cases]] /@ {"10000", "00000"} / (cases // Length)
image-20230930143832402

和用 递推式求出来的相符