一个点在x 轴行走，起始点在原点，每次走 1 格，每次的方向随机或正或负，概率均为1/2。行走 n 步后，预期该点相对原点的绝对距离是多少呢？

显然，这个点平均前进的距离为 0， 但是绝对距离却不显然。这个问题和气体中原子的运动，即布朗运动有关。下面来具体算下。

方法1: 假设行走 n 步后的距离为$D_n$，我们使用距离的平方 $D_n^2$ 来度量行走 n 步后的距离平方。现在来研究行走 n 步后和 n+1 步后距离平方的关系

\begin{align} D_{n+1}^2 &= \frac{1}{2}(\sqrt{D_n^2} + 1)^2 +\frac{1}{2}(\sqrt{D_n^2} - 1)^2 \\ &= D_n^2 + 1 \end{align}

由于 $D_1^2 = 1$, 所以可得

\[D_n^2 = n\]

方法2: 实际上我们由独立随机变量之和的方差，等于各变量的方差之和：

\[Var(X_1+\dots + X_n) = Var(X_1)+ \dots + Var(X_n) \tag{1}\]

可快速推出 $D_n^2=nVar=n$。这是因为每一步相对上一步的距离的方差为1。这个例子加深了我们对公式(1)的理解。

也就是说n步后平均偏离原点的绝对距离 $d_n = \sqrt{D_n^2} = \sqrt{n}  \quad (d_n > 0)$。 这个结果不知道有没有令你感到吃惊呢？我写了个程序模拟, 参考下面的代码。测试1000次随机行走，每次随机行走 1百万步，平均偏离原点的绝对距离。通过上面的分析，我们预期理论上平均偏离原点的绝对距离大概是 $\sqrt{1000000}=1000$ 。我运行了该程序 5 次，结果如下：

第1次运行结果: 772. 

第2次运行结果: 771. 

第3次运行结果: 767. 

第4次运行结果: 820. 

第5次运行结果: 768. 

从实验结果来看，和我们的理论值1000，相差不算太大。我采用的是 java.util.Random.nextInt(bound) 方法产生0和1的随机数。该程序稍加改造，替换掉随机数的生成方法，可以用于测试生成的随机数是否足够随机。

package com.math345.math;

import java.util.Random;

/**
 * @author yinfeng
 *
 */
public class RandomWalk {
	
	private static final Random random = new Random();
	
	
	/**
	 * 一次随机行走.
	 * @param step 该次行走总共的步数
	 * @param footprint 是否打印脚印, true 会打印行走过程中部分时刻的距离
	 * @return 最终偏离原点的距离
	 */
	public static int walk(int step, boolean footprint) {
		int distance = 0;
		for(int i = 0; i < step; i++) {
			if (random.nextInt(2) == 1) {
				distance += 1;
			}else {
				distance -=1;
			}
			
			if(footprint && i % 1000 == 999) {
				System.out.print(distance + ", ");
				
				if(i % 10000 == 9999) {
					System.out.println("");
				}
			}			
		}
		
		return distance;
	}


	public static void main(String[] args) {
	        // 测试1000次随机行走，每次随机行走 1百万步，平均偏离原点的绝对距离
		int sum = 0;
		int distance;
		int size = 1000;
		
		for(int i = 0; i < size; i++) {
			distance = walk(1000000, false);
			sum += Math.abs(distance);
			
			System.out.print(distance + ", ");			
			if(i % 10 == 9) {
				System.out.println("");
			}
		}
		
		System.out.println("The average distance:" + sum/size);
	}

}