三消游戏自动消除ｎ个障碍的概率

KeyTo9_Fans

有一个宽度为$1$，高度为$+\infty$的容器。

一开始容器的顶部有$3$个空位，其余全是障碍物（云层），如下图所示：



如果容器顶部有空位，那么这些空位会被小动物填补。

小动物只有$2$种。

每个空位被填补的小动物是随机且独立的，

被青蛙填补的概率是$p$，

被狐狸填补的概率是$(1-p)$。

下图是其中一种可能的填补：



当所有空位都被填满后，如果有连续$3$个或$3$个以上相同的小动物排在一起，这些小动物会被消除。

如果紧贴云层的小动物被消除，那么这块云层也会被一起消除，如下图所示：



小动物和云层被消除后都会变成空位，空位上方的小动物（如果有的话）会依次落下来。

当所有小动物都落稳后，容器顶部的空位会被新的小动物（按照$p$和$(1-p)$的概率随机、独立地）填补。

下图是其中一种可能的填补：



填补后如果还有连续$3$个或$3$个以上相同的小动物排在一起，这些小动物会被消除。



上述过程不断反复，直到没有连续$3$个或$3$个以上相同的小动物排在一起为止，如下图所示：



我们把上述过程消除掉的云层总数记为$n$。

问题$1$：

当$p=0.5$时，给定非负整数$k$，求$n=k$的概率$P(n=k)$是多少。（如果没有通式，求出$P(n=0)$、$P(n=1)$、……、$P(n=20)$即可）

问题$2$：

当$p=0.5$，$k->\infty$时，$\frac{P(n=k+1)}{P(n=k)}$是否有极限？如果有，该极限是多少？

问题$3$：

当$p$取何值时，我们有$\sum_{k=0}^\infty P(n=k)<1$？

mathe

这个问题状态很复杂，感觉很难求解，不知道是否可以有近似解法。

Lwins_G

动态规划可以求解，想法是在一开始就确定某个动物是怎么被消除的。（状态维数很大，可能要4维或者5维）