泊松分布
周末,同事离去的都很早。我留在办公室,这周想做的事情基本完成,那就随便写点东西。
写写概率论中非常重要的泊松分布(poisson distribution)是我这周中间就有的想法。
具体的起因记的不太准确了,似乎是因为在一个接收新游戏 bug 反馈的 IM 群里跟同事聊天跑题。从游戏的 bug 扯到游戏的数值设定,然后说起概率,再跑题到大学中学到的数学知识;正好前几天睡觉前在翻《一生受用的公式》这本袖珍小册子,看到了泊松分布的公式以及关于它的有趣的插图;然后问起同事对这个东西的了解程度。
结果可想而知,当时没有人可以准确告诉我到底什么是泊松分布,它有什么用,当然更不用提它的公式是怎么推导出来的了。让我有点自鸣得意的是,自己大概还知道个所以然。不管怎么说,若不是当年本科的概率统计考试中的笔误,我就能拿个满分的。上大学时,考试前我很少复习,不感兴趣的课程也基本没去读书。不是说天才到可以以那种状态考试过关,只是那个时候我不太在意挂科而已 :)。相比较而言,没经过理解的东西让我去背公式应付考试这种事情,我是坚决不干的。
可惟独这本概率统计,我是相当喜欢,也就最认真的去学了。
自己明白不是真的明白,一旦想教给别人时就会露馅。当想把我曾经的理解和记忆写出来时,才发现自己写不太清楚。这几天没事翻了翻书,也 google 了一下,理清了点思路。今天记录下来,算是一个总结。
首先必须由二项分布引出:
如果做一件事情成功的概率是 p 的话,那么独立尝试做这件事情 n 次,成功次数的分布就符合二项分布。展开来说,在做的 n 次中,成功次数有可能是 0 次、1 次 …… n次。成功 i 次的概率是:
( n 中选出 i 项的组合数) * p ^ i * (1-p)^ (n-i)
以上公式很容易推导,用一点概率学最基本的知识就够了。因为每一特定事件成功的概率是 p ,不成功的概率是 1-p 。i 次成功的事件可以任意分布在总共的 n 次尝试中。把它们乘起来就是恰好成功 i 次的概率。
当我们把二项分布推而广之后,就可以得到波松分布。
可以这样考虑,在一个特定时间内,某件事情会在任意时刻随机发生(前提是,每次发生都是独立的,且跟时间无关)。当我们把这个时间段分成非常小的时间片构成时,可以认为,每个时间片内,该事件可能发生,也可能不发生。几乎可以不考虑发生多于一次的情况(因为时间片可被分的足够小)。
当时间片分的越小,该时间片内发生这个事件的概率 p 就会成正比的减少。即:特定时间段被分成的时间片数量 n 与每个时间片内事件发生的概率 p 的乘积 n*p 为一个常数。这个常数表示了该事件在指定时间段发生的频度。
回过头来再来看这段时间内,指定事件恰好发生 i 次的概率是多少?代入上面推导出来的公式得到:
n * (n-1)... (n-i+1) / i! * p^i * (1-p) ^ (n-i) => np(np-p)...(np-ip+p) / i! * ((1-p) ^ (-1/p))^(-np) / (1-p) ^i
当 n 趋向无穷大时,p 趋向 0 。而此时 (1-p)^(-1/p) 趋向 e 。注:推导过程可见文末。
上面这个公式可以划简为 lamda ^ i / i! * e ^ - lamda (lamda=n*p)
这个公式推导过程不复杂,耐心点一看就明白。而这个关于 i 的分布就是著名的泊松分布了。
为什么泊松分布很有价值,因为我们在推算某些特殊事件在一段时间内可能发生次数的时候经常会用到它。比如设计一个无聊的打怪练级的 MMORPG ,假如玩家到一个地图杀怪纯属独立随机事件,我们应该在这个地图按什么频率刷怪可以合适到让来的玩家不会找不到怪打。
玩家同时来到这个地图的数量就是满足泊松分布的,我们统计出一段时间来访玩家的平均数,就可以根据泊松分布公式推算出玩家峰值在什么数量上出现很大的概率。然后就可以进一步计算出合适的刷怪频率和密度了。
呵呵,想指责我这个想法过于天真的职业游戏策划请先别忙着骂。我承认我这个例子举的很不恰当。因为导致玩家去一个地区的因素很多,包括地图的怪的数量等等。而且玩家之间也有很强的联系。玩家到一个地图去并不是独立事件,最终的结果很可能偏离泊松分布很远。但请原谅我吧,今天太晚了,一下想不出什么跟游戏设计密切相关的例子。有机会我会补充个更好的。
不过请相信我,日常生活中有很多突发事件满足泊松分布的,不信请自己 google 之。
本着追根究底的原则,写一下前面提到的一个极限的推导。尽量用高中数学程度就可以理解的语言啦:
(1-p)^(-1/p) 当 p 趋向于 0 时,为什么它的值趋向 e ?
关于 e 可以看我写的另一篇文章 ,从那篇文章提到的知识,我们可知 ln x 的导数是 1/x ,由导数的定义可知
1/x = lim (( ln x' - ln x ) / ( x' -x )) 这里 x' 趋向 x
令 x' = x + 1/n ( n 趋向无穷大) 代到上式中, 并用对数计算法则化简得到
1/x = lim ( ln ((1+ 1/ (n*x)) ^ n)) 这里 n 趋向无穷大
再令 z = 1/x ,并再一次用对数运算法则化简可得
z = lim (ln (1+z/n)^ n ) 这里 n 趋向无穷大,两边取指数函数,可变化为 e^z = lim ((1+z/n)^n)
当 z = 1 时,我们可以得到特例: e = lim ( (1+1/n)^n ) ,n 趋向无穷大
回头再来看式子 (1-p)^(-1/p) ,令 n = 1/p ,因为 p 趋向于 0 ,所以 n= 1/p 趋向无穷大。前式可变形为:
(1+1/(n-1))^n ,当 n 趋向无穷大的时候,跟 (1+1/n) ^ n 有相同的极限 e 。
Comments
那个,推导过程中有漏洞……
通过二项分布的概率密度函数直接推导是错的,lz可以再仔细看一下。应该是通过分布函数推导的……
Posted by: 甲鱼 | (23) January 9, 2008 11:11 AM
谢谢你写的内容,但是我感觉你关于e的推导似乎有本末倒置的嫌疑,是先有的e,才会有lnx导数的推导的:)
Posted by: littlesongshu | (22) December 1, 2007 09:08 PM
国内的把软件工程和计算机科协合到一起了,so~~像波松分布这样在计算机科学里面用得很多的概率分布,simulation,到处能看到
Posted by: kelvin | (21) November 21, 2007 10:16 PM
lamda 在实际应用中该如何确定,不如你说的网游打怪的例子?另外,我在Matlab的帮助里看到泊松分布在lamda很大时近似于正态分布.
Posted by: kicool | (20) November 13, 2007 09:56 AM
Posted by: nothanks | September 26, 2007 09:01 AM
讨论一个问题, 在网页或文本中(没高级符号的插入功能的情况下), 如何才能较准确有效地书写公式.因为直接打字而不是研究麻烦的符号输入还是方便一点.
---------------------------
latex
Posted by: lbaby | (19) October 17, 2007 05:38 PM
对这些名人,不知道说什么是好.很敬仰他们!
Posted by: ymg | (18) October 15, 2007 06:22 PM
to 枫之羽
谢谢!
我已经看过你说的那本书的1,3,4章,类的对象在内存中的分布也知道,字节的对齐规则我也知道。但是我举的那2个例子好像不按规则来,不知道这么回事
Posted by: hns | (17) September 27, 2007 07:38 PM
回楼下兄弟的,类的字节对齐的问题可以去看Inside C++ Object Model ,里面有比较详细的阐述!
Posted by: 枫之羽 | (16) September 27, 2007 07:16 PM
像是泊松公布之类分布的,我读大学里是在工程数学里面学的,似乎概率论,线性代数之类这块更关切的似乎是应用工程科学吧, 因为确实很多领域有应用.
而和计算机关系最密切的是形式数学这一块吧, 形式理论大多数都很抽象,计算机程序处理的其实就是符号系统,理论中比较完美的编程环境应该是静态语义的,不用关心非常复杂的运行时情况.
而实际上编程高手,谁去理解这么多数学,形式数学的专家们,又有谁对操作系统的细节,如些多的编程语言环境和工具熟悉.
这本来就是一种隔阂,将来,我认为数学理论将会越来越多地渗透地工程领域, 就象编程之外的其它科学一样.
Posted by: xf | (15) September 26, 2007 04:11 PM
那就需要制定一套有别于传统符号的规则
Posted by: nothanks | (14) September 26, 2007 09:01 AM
讨论一个问题, 在网页或文本中(没高级符号的插入功能的情况下), 如何才能较准确有效地书写公式.因为直接打字而不是研究麻烦的符号输入还是方便一点.
Posted by: xf | (13) September 25, 2007 10:20 PM
“相比较而言,没经过理解的东西让我去背公式应付考试这种事情,我是坚决不干的。
可惟独这本概率统计,我是相当喜欢,也就最认真的去学了。
自己明白不是真的明白,一旦想教给别人时就会露馅。”
这几句话,深得我心。
Posted by: 尉迟方 | (12) September 25, 2007 04:13 PM
防沉迷系统不可取.
Posted by: oyang | (11) September 24, 2007 04:44 PM
话虽这么说,但是游戏应该尽量引导而不是仲裁他们
Posted by: nothanks | (10) September 24, 2007 09:40 AM
由游戏引出的问题不是游戏的事,是人的问题,看人对游戏的态度,并不是游戏说你沉迷你就沉迷,而人说我要沉迷,所以他就沉迷了.我觉得不关游戏的事,是人的问题啊!!
Posted by: 顶风作案 | (9) September 24, 2007 09:04 AM
呵呵,明白了,以后问问题再也不贴这么长的代码了:)。
Posted by: hns | (8) September 23, 2007 09:24 PM
不欢迎贴代码 ;) 也不解答具体代码问题。
这些问题可以问书本、问老师、问 google 、问同事,就是不要问我 :D
Posted by: Cloud | (7) September 23, 2007 09:18 PM
帮顶!并请教一些问题:)
关于类的字节对齐的一些疑问:
以下代码在VC6.0中测试:
(<>和#显示不出来。。。,第一次留言,不知道这么排版,可能看起来比较痛苦,sorry)
#include "iostream"
#include "vector"
using namespace std;
class A
{
public:
char c;
void Test();
};
void A::Test()
{
}
class B : public A
{
public:
char bc;
virtual void Test2();
int bi;
};
void B::Test2()
{
}
int main()
{
cout<<"sizeof(A)"<<sizeof(A)<<endl; //1
cout<<"sizeof(B)"<<sizeof(B)<<endl;//12
printf("the address of B::c is %d\n", &B::c);//0
printf("the address of B::bc is %d\n", &B::bc);//5,从5开始
printf("the address of B::bi is %d\n", &B::bi);//8
return 0;
}
//--------------------------------------------------
#include "iostream"
#include "vector"
using namespace std;
class A
{
public:
char c;
void Test();
};
void A::Test()
{
}
class B : public A
{
public:
char bc;
double bf;//加了一个double变量
virtual void Test2();
int bi;
};
void B::Test2()
{
}
int main()
{
cout<<"sizeof(A)"<<sizeof(A)<<endl; //1
cout<<"sizeof(B)"<<sizeof(B)<<endl;//32
printf("the address of B::c is %d\n", &B::c);//0
printf("the address of B::bc is %d\n", &B::bc);//9,加了一个double变量后这么就从9开始了?
printf("the address of B::bf is %d\n", &B::bf);//16
printf("the address of B::bi is %d\n", &B::bi);//24
return 0;
}
Posted by: hns | (6) September 23, 2007 07:59 PM
呵呵。楼下的问题问的好。我一直没机会表明我的态度:
最开始我对做网络游戏一点兴趣都没有,所以做了好几年引擎。
后来发现其实还有点意思,不过并没有意识到其社会问题。
现在,熟悉我的人都知道,我是把网络游戏带来的社会问题经常拿出来跟人讨论的。并且尽力让网络游戏向更健康的方向发展。
Posted by: Cloud | (5) September 23, 2007 12:58 AM
要是三年前的今天就看到你的Blog,也许我的数学不会这么烂了,我想问你一个问题,制作游戏的有没有想过玩游戏的是谁?
玩了这个游戏会有什么后果?
现在的游戏是从客户出发,也就是一种纯商业的模式。
Posted by: Anonymous | (4) September 22, 2007 11:14 PM
朝着自己的理想奋斗是幸福的。前几天还在看概率,看泊松分布。不同的是,我是为了改变,让工作不是为了生计,而是理想。
Posted by: 橙子 | (3) September 22, 2007 09:42 PM
记得初中化学还是生物什么的,有张图片就是钨原子还是什么病毒的泊松分布电子照片
Posted by: 11 | (2) September 22, 2007 05:12 PM
不错,不错
Posted by: noname | (1) September 22, 2007 03:38 PM