三消游戏自动消除ｎ个障碍的概率
有一个宽度为$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$？ 这个问题状态很复杂，感觉很难求解，不知道是否可以有近似解法。 动态规划可以求解，想法是在一开始就确定某个动物是怎么被消除的。（状态维数很大，可能要4维或者5维）
页:
[1]