可视化分钱的概率模拟算法

2017.12.18

介绍

之前在一篇文章上看到一个问题，说：“一个房间里有100个人，没人有100块钱，每分钟每人随机给另外的人一块钱，那么过一段时间后，这100个人的财富分布是什么情况？”。如果按照个人的常规直觉，无论过多久，他们的财富应该相差不会太多。可经过计算机模拟，他们的财富会出现两级分差，有钱的很有钱，没钱的很没钱。然后作者将他映射到现实社会中的财富分配，得出有钱人会越有钱，没钱的越没钱的道理。其实在我看来从这个模拟实验的结果来看，并不能得出这样的结论。本篇文章我来进行这项实验的可视化模拟。

HTML5的canvas

我会使用HTML5的canvas画布，来做可视化的工具。当然使用别的工具当然也是可以的，实现的方法是一样的。

对于canvas的用法，本篇文章不做详细的介绍，如果想要了解canvas的使用方法，参考这里

首先设置画布：

<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Demo</title>
	<style>
		canvas#test {
			border: 1px solid #999;
			margin: 30px auto;
			display: block;
		}
	</style>
	<script>
		window.onload = function() {
			var canvas = document.getElementById('test');
			var ctx = canvas.getContext('2d');

		}
</head>
<body>
	<canvas id="test" width="500" height="500"></canvas>
</body>
</html>

在画布上画出 100 个人的初始金钱数状况：

var canvas = document.getElementById('test');
var ctx = canvas.getContext('2d');
var beginX = 0;
var arr = new Array(100);
for (var a=0; a<100; a++) {
	arr[a] = 100;
}
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.fillStyle = '#157ac1c9';

for (var i=0; i<100; i++) {
	beginX = (canvas.width/100)*i;
	ctx.fillRect(beginX, canvas.height-arr[i], canvas.width/arr.length, arr[i]);
}

如图，x轴表示100个人，y轴表示每个人的金钱数100。

算法实现

每个人的初始财富都是 100 元，如果要让他们每轮每个人随机给另一个人一元，那么就相当于数组arr中的每一项，在每次循环后减去 1，然后每一次循环都有一个人增加 1。逻辑理好了，实现起来也很简单：

for (var i=0; i<arr.length; i++) {    
	if (arr[i] > 0) {
		arr[i] -= 1;
		n = parseInt(Math.random()*100);
		arr[n] += 1;
	}
}

if (arr[i] > 0) {}保证没钱的人不能失去一元钱。n = parseInt(Math.random()*100)这一句是JavaScript随机取 0-100 前闭后开区间的随机整数，这就表达出问题中的随机一人获得一元的语句。

通过循环，问题的模拟算法已经写好了，接下来就是画布中展示了。canvas的动画实现的原理就是显示图片，然后清空画布，在更新画布。

// 画图函数
function draw(array) {
	// 清空画布
	ctx.clearRect(0,0, canvas.width, canvas.height);
	for (var k=0; k<arr.length; k++) {
		beginX = (canvas.width/arr.length)*k;
		ctx.fillRect(beginX, canvas.height-arr[k], canvas.width/arr.length, arr[k]);
	}
}
// 算法实现
function algoImitate() {
	// 调用画图函数
	draw();
	for (var i=0; i<arr.length; i++) {    
		if (arr[i] > 0) {
			arr[i] -= 1;
			n = parseInt(Math.random()*100);
			arr[n] += 1;
		}
	}
	// 定时刷新画布
	setTimeout(algoImitate, 200);
}

algoImitate();

运行函数就可以看到画布上模拟出来的动画了。

但是运行的动画实在太慢了，需要等很长时间才能看到结果，为了加快速度，可以更改刷新画布的时间。但是如果不更改刷新时间，只是更改算法，该如何加快了。其实这就是如何加快模拟算法的问题，其实很简单，只需要在算法循环的外层在加一层循环就好了：

// 算法实现
function algoImitate() {
	// 调用画图函数
	draw();
	for (var b=0; b<50; b++) {
		for (var i=0; i<arr.length; i++) {    
			if (arr[i] > 0) {
				arr[i] -= 1;
				n = parseInt(Math.random()*100);
				arr[n] += 1;
			}
		}
	}
	// 定时刷新画布
	setTimeout(algoImitate, 200);
}

这里的b<50中的 50 可以自由定义，这样在加一层循环，实际上就相当于之前模拟的 50 倍速度。现在再运行函数，显然动画更新的更快了。

但是如图，我们还是不能清晰的看出财富的大致分布。为了更清晰，需要在每次刷新循环的时候给我们的数组排个序。我们整理一下代码，如下：

window.onload = function() {
	var canvas = document.getElementById('test');
	var ctx = canvas.getContext('2d');
	var beginX = 0;
	var arr = new Array(100);
	for (var a=0; a<100; a++) {
		arr[a] = 100;
	}
	ctx.clearRect(0, 0, canvas.width, canvas.height);
	ctx.fillStyle = '#157ac1c9';

	function draw() {
		ctx.clearRect(0,0, canvas.width, canvas.height);
		for (var k=0; k<arr.length; k++) {
			beginX = (canvas.width/arr.length)*k;
			ctx.fillRect(beginX, canvas.height-arr[k], canvas.width/arr.length, arr[k]);
		}
	}
	function algoImitate() {
		draw();
		// 排序
		arr.sort(function(a,b){return a>b ? 1 : -1});
		for (var b=0; b<50; b++) {
			for (var i=0; i<arr.length; i++) {    
				if (arr[i] > 0) {
					arr[i] -= 1;
					n = parseInt(Math.random()*100);
					arr[n] += 1;
				}
			}
		}
		setTimeout(algoImitate, 200);
	}

	algoImitate();
}

注意，JavaScript整数数组排序，如果使用Array.sort()直接排序的话，那么结果就是[1,11,12,...,20,21,...,30,...]。

动画运行一段时间就可以看出大致结果了。

不难发现财富的分布大致是呈一个幂指数的分布，有钱的和没钱的差距会很大。但是这是经过我们排序后的分布，也就是说有钱人和没钱的人不一定一直是一个人。如果按照看过的那篇文章说的“残酷的现实”结论，有钱的会更有钱，没钱的会更没钱的说法，显然是不对的。至少从这个模拟是看不出的。

算法 JS

乾之三爻