模拟一唯随机游动

今天,无意中看到了这个blog里面的一篇有意思的文章.对里面的那个随机游动问题产生了一点兴趣:
原文中说: 1维和2维的随机游动是常返的，也就是说会无穷多次回到起点（但回来的平均时间期望是无穷的），而3维以上的随机游动是非常返的。因此对于2维的某个坐标，此物体会无穷多次经过，但是不会无穷多次经过原点。对一个完全没有方向感的人，在平面上不会迷路，但在宇宙中是会迷路的。
而且,还有个题目,说 一个物体从原点出发，每一秒以概率1/2向左走，1/2向右走，第一次回到原点的期望时间 比 一只猴子，每秒种随便按键盘上的一个键，第一次打出”Beijing Welcomes You”的期望时间 还要久,因为前者的期望是无穷大.
就有点奇怪了,顺手写了个程序验证一下,图方便,用了python,代码如下:

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
import random
# Nmax 是样本数
Nmax=10000
# A这个字典用于存放每个结果的次数
A={}
for N in range(0,Nmax):
	r=0
	i=0
	while True:
		#为了使结果不都是偶数,也为了少一半循环,每次循环都random两遍.
		if random.random()<0.5:
			r=r-1
		else:
			r=r+1
		if random.random()<0.5:
			r=r-1
		else:
			r=r+1
		i=i+1
		if r==0: #如果r==0,就说明回到原点了,记下结果,结束这个样本
			if i in A:
				A[i]=A[i]+1
			else:
				A[i]=1
			break
#所有样本都算完以后,对结果进行排序输出,并计算平均值
k=A.keys()
k.sort()
T=0
for i in range(0,len(k)):
	print "%d\t = %d"%(k[i],A[k[i]])
	T=T+k[i]*A[k[i]]
print "avg=",T/Nmax

这个代码会输出Nmax个样本里面,一维随机游走问题的各个秒数次数.
在Nmax样本数为10000的时候,如果运气好的话,可以在3秒内跑完,但是如果运气不好的话,就难说了,我最多的一次跑了45分钟,最大的一个样本,用了1679075437个循环,才跳回来…嘿嘿.看来那个无穷的期望是真的…
这个试验也告诉我们,即使在没有作弊的情况下,赌博输掉的人想要回本,也许要等到下辈子的下辈子的下辈子…..

最后修改时间: 2008年11月07日 20:35