算法-一个概率相关的算法问题

Question

现在有4个方格，方格编号依次是0,1,2,3。一个人站在0号方格，他的目的是到达3号方格。他一次只能移动一格，具体规则是这样的：
1.如果他在0号方格，那么他下次移动到方格1的概率是1.
2.如果他在1号方格，那么他下次移动的时候，有1/3的概率到达2号方格，1/3的概率留在1号方格，1/3的概率倒退到0号方格.
3.如果他在2号方格，那么他下次移动的时候，有1/9的概率到达3号方格，4/9的概率留在2号方格，4/9的概率倒退到1号方格.
那么在上述规则下，如果这个人最终要到达3号方格，他平均需要移动多少次？
其实这个问题还有一个更加普遍的描述。如果他在n号方格，那么他下次移动的时候，有(1/3)^n的概率到达(n+1)号方格，(1/2)[1-(1/3)^n]的概率留在n号方格，(1/2)[1-(1/3)^n]的概率倒退到(n-1)号方格。问：他到达m号方格，平均需要移动多少次？

Answer 1

先Mark一下，其实所求的平均次数就是要求的期望。
我总是感觉这种情况符合 X^2分布、t分布、F分布中的某一种。

Answer 2

以4个格子为例：

我们记从第i个格子到第i+1个格子的平均步数为 E（i）

所以E（0） = 1

E(1) = 1/3 × 1 + 1/3 × (1 + E(1)) + 1/3 × (1 + E(0) + E(1))
=> E(1) = 4

E(2) = 1/9 × 1 + 4/9 × (1 + E(2)) + 4/9 × (1 + E(1) + E(2))
=> E(2) = 25

所以总的步数是 E（从0到1再到2再到3的步数）= E（0） + E（1） + E（2） = 30 (和的期望的等于期望的和）

类似可以推出N个格子的情况是一个E(i)和E(i+1)的递推式，迭代N次能求出最终结果。

Answer 3

是个有限状态（扩展情况下不有限，不过可以看做有限）马尔科夫过程
转移概率矩阵可以写作：
0 1/3 0 0
1 1/3 4/9 0
0 1/3 4/9 0
0 0 1/9 1

记这个矩阵为P，则第k次转移后的概率分布可以写作P^k * (1 0 0 0)T
知道概率分布自然就可以求出期望值了
注意求出的概率分布向量中的最后一个元素，是P(X<=k)的值
E(X) = ∑k * P(X=k) = ∑k * (P(X<=k) - P(X<=k-1)) = lim(∑k * P(X<=k) - ∑(k +1)P(X<=k) + (k+1)P(X<=k)) = lim((k+1)P(X<=k) - ∑P(X<=k))
=lim((k+1)P(X<=k)-k + ∑(1-P(X<=k))) = 1 + ∑(1-P(X<=k))，求和从1开始。

至于矩阵的乘幂可以用化对角阵或准对角阵的方法，或者低阶的直接计算。