用$f(m,a,b,i,j)$表示起点在$(a,b)$的跳蚤且m步落在$(i,j)$的概率。显然有初值：
$$f(0,a,b,i,j)=\begin{cases}1 & (a,b)=(i,j), \\ 0 & (a,b)\neq(i,j).\end{cases}$$
用$g(i,j)$表示$(i,j)$的邻居组成的点集，则有递推式
$$f(m,a,b,i,j)=\sum_{(i',j')\in g(i,j)}\frac{f(m-1,a,b,i',j')}{|g(i',j')|}.$$
因此经过50步，某一点$(i,j)$上没有跳蚤的概率是
$$p(i,j)=\sum_{a,b\in\mathbb Z_{30}}\left(1-f(50,a,b,i,j)\right).$$
没有跳蚤的方格的期望数目是
$$\sum_{i,j\in\mathbb Z_{30}}p(i,j)=330.721154.$$
注：以下代码为Python 3，因代码中使用了除法的新特性。为防止假死，代码中打印了运行状态信息。
g=lambda x,y:[(u,v) for u,v in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)] if u>=0 and u<30 and v>=0 and v<30]
r=[[1]*30 for i in range(30)]
for a in range(30):
for b in range(30):
f=[[[0 for j in range(30)] for i in range(30)]for m in range(51)]
f[0][a][b]=1
for m in range(1,51):
for i in range(30):
for j in range(30):
f[m][i][j]=sum(f[m-1][u][v]/len(g(u,v)) for u,v in g(i,j))
for i in range(30):
for j in range(30):
r[i][j]*=(1-f[50][i][j])
print(a,b,"done")
print("%.6f" %(float(sum(sum(c) for c in r))))
|
