人类脑瘫行为观察 #2
tiger2005
·
·
个人记录
这次实际上是被骗了。
书接上回，昨天开学典礼结束，小 M 跟我说了一个问题：
题意：现在进行着一场抛硬币游戏。在一开始你有一枚硬币，在每轮中，你需要抛出手中所有的硬币，如果有 p\ (p > 0) 枚硬币正面朝上，则你将会获得 2p 枚硬币并继续下一轮；否则，如果没有硬币正面朝上，那么游戏结束。设游戏在 X 轮后结束，给定 n \in \mathbb{Z^+}，求 P(X \geq n) 的表达式。
我不到十分钟就甩出了一个生成函数，小 M 说这个东西应该是可以算的，于是昨天下午我就稍微写了一下思路。
设 p_{i,j} 表示在 i 轮过后，手上还有 j 枚硬币的概率，并且在此处假设手上没有硬币时将会经历后面的每一轮，那么有递推式：
\left\{
\begin{array}{lll}
a_{0,1}=1 \\
a_{i,j} = \sum_{k=\frac j 2}^{+\infty}a_{i-1,k}2^{-k}\binom{k}{\frac j 2} & & (i \in \mathbb{Z}^+, j \in 2 \mathbb{N}) \\
a_{i,j} = 0 & & (i \in \mathbb{Z}^+, j \in 2 \mathbb{N} + 1)
\end{array}
\right.
设 f_i(x) = \sum_{j=0}^{+\infty} a_{i,j}x^j，g(x)=\dfrac{x^2+1} 2，可以知道 f_0(x) = x，所求为 1 - f_{n}(0)，并且对于 \forall u \in 2\mathbb{Z}，有
[x^u]f_{i+1} = \sum_{k=0}^{+_\infty}([x^k]f_{i}(x))\dfrac{\binom{k}{\frac u 2}}{2^k}
故
\begin{aligned}
f_{i+1}(x) &= \sum_{u \in 2\mathbb{Z}}x^u\sum_{k=0}^{+_\infty}([x^k]f_{i}(x))\dfrac{\binom{k}{\frac u 2}}{2^k} \\
&= \sum_{k=0}^{+\infty}\dfrac{[x^k]f_i(x)}{2^k}\sum_{u=0}^{k}\binom{k}{u}x^{2u} \\
&= \sum_{k=0}^{+\infty}[x^k]f_i(x)g^k(x) \\
&= (f_i \circ g)(x)
\end{aligned}
我们可以知道：f_{n}(x) 等价于连续将 n 个函数 g(x) 进行复合的结果，可以推出：
f_{i+1}(x) = (g \circ f_i)(x)
于是根据定义，我们有等式
\begin{aligned}
T_n &= 1 - f_{n}(0) \\
&= 1 - g(f_{n-1}(0)) \\
&= 1 - g(1 - T_{n-1}) \\
&= -\dfrac{T_{n-1}^2} 2 + T_{n-1}
\end{aligned}
其中 T_{0} = 1。
然后我列出了 \{T_{n}\} 的前几项：\dfrac{1}{1}, \dfrac{1}{2}, \dfrac{3}{8}, \dfrac{39}{128},...，除了分母固定式 2^{2^n-1} 并且分子似乎有倍数关系之外就什么都算不出来了。
最后，我上了 OEIS，查了一下数组 1,1,3,39，终于找到了答案（A076628）：这个数列没有通项式！
白忙活半个上午，哈哈。