匹配问题

以下的第一个匹配问题摘自[1]:

问题:假如你有一个装了n个无差别的球的罐子,每个球分别贴了1,2,3,…,n的标签。每次取出一个球直至所有球均取出,那么,至少有1个球的取出顺序与它的标签一致的概率是多少(例如,标签为2的球是第2个取出来的)?

解答 n个球有n!种排列顺序,假设在某一排列中第j个元素代表第j个取出的球。令Pj(j=1,2,…,n)代表某一给定的排列的第j个取出的球的标签为j,并且令Aj代表具有属性Pj的排列的集合。那么,至少有1个球的取出顺序与它的标签一致的排列的数量Ln
$$! \begin{array}{l} {{L}_{n}}=|{{A}_{1}}\cup {{[......]

阅读全文 »

Dice Roll

连续抛掷一枚标准的骰子(即出现6种点数的概率一样,均为1/6)直至点数和超过12。则点数和最有可能是多少?例如,如果点数依次为3、6、1、5,则点数和为15。

一种解法是穷举所有点数系列,看看哪个点数和最有可能。但有另一种更巧妙的方法。假如点数系列之和为14,则最后一次抛骰子的点数不可能是1,否则点数和为13(已经超过12)而终止。对于产生14的所有点数系列,如果最后一次的点数均减少1,则可以产生13(因得到14的最后一次不能是1,所以得到14的最后一次骰子点数只能是2、3、4、5、6,那么若最后一次骰子点数改为1,2,3,4,5,这些点数系列之和就会得到13),因此,出现点数和为[......]

阅读全文 »

转载:《狼来了》的概率论解读

伊索寓言《狼来了》可谓家喻户晓。那个说谎的孩子是怎样一步一步丧失村民的信任的呢?借助于贝叶斯公式我们可以给出故事的概率论解读。

记A为事件“这个小孩说谎”,B为事件“这个小孩被认为可信”;再不妨设可信的孩子说谎的可能性为0.1,不可信的孩子说谎的可能性为0.5,即


原来,村民们对这个小孩的印象是
$$! \begin{equation} \label{F2} P(B)=0.8,\quad P(\overline[......]

阅读全文 »

浦丰投针问题(Buffon’s Needle Problem)

浦丰投针问题(Buffon’s Needle Problem)是几何概率的经典问题之一,由George-Louis Leclerc和Comte de Buffon于1777年提出——平面上画有等距离为D(D>0)的无限多条平行线,向此平面投掷一根长度为L(L≤D)的针,则该针与任一平行线相交的概率Pcut为:


重复进行投掷的试验,记下试验总次数Nd和针与平行线相交的次数Nc,则利用以上公式可以近似求得圆周率π:
$$!\pi =\frac{2L}{{{P}_{cut}}D}\approx \frac{2L}{({{N}[......]

阅读全文 »

斯特林公式的概率证明

斯特林公式[1]是用来求n阶乘的近似值,公式如下:


该公式的一种概率证明方法如下[2]。令X1,X2,...,Xn是独立的泊松分布随机变量,均值都是1,令,则Sn的均值和方差都是n。
$$!\begin{array}{l} P\{{{S}_{n}}=n\}=P\{n-1[......]

阅读全文 »

单位区间[0 1]里随机分布n个点

在数轴上的区间[0 1]上有两个随机点A和B,它们的坐标服从[0 1]上的均匀分布,即X1~U(0,1),X2~U(0,1)。则此两点间距离的数学期望是多少?

两点间的距离X = |X1-X2| = max{X1,X2} - min{X1,X2}。令Y = max{X1,X2}, Z = min{X1,X2},两者的累积分布函数为:

F(Y) = P(Y≦y) = P(X1≦y & X2≦y) = P(X1≦y) × P(X2≦y) = y×y = y2

F(Z) = P(Z≦z) = 1-P(Z≧z) = 1-P(X1≧z & X2≧z) = 1 - P(X1≧z) × P(X[......]

阅读全文 »

收集与调和级数

Collecting Coupons: Coupons in cereal boxes are numbered 1 to 5, and a set of one of each is required for a prize. With one coupon per box, how many boxes on the average are required to make a complete set?

这是《Fifty Challenging Problems in Probability with Solutions》书中的第14个题目[1]。在第一个盒子中,我们得到其中一个数字[......]

阅读全文 »

生日问题(Birthday Problem)

生日问题[1-2]是指在随机选择的一群人当中有两人的生日相同的概率。如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%;对于60或者更多的人,这种概率要大于99%。计算与此相关的概率被称为生日问题,在这个问题之后的数学理论已被用于设计著名的密码攻击方法:生日攻击。

假设有n个人在同一房间内,不考虑特殊因素,例如闰年、双胞胎,并且假设一年365日出生概率是均匀分布的。首先计算每个人的生日日期都不同的概率为:
$$!\begin{equation} \overline{p(n,365)}=\frac{A_{365}^{n}}{{{365}^{n}}} \en[......]

阅读全文 »

最佳奖品问题、麦穗问题、相亲问题、炮灰模型、秘书问题—最优停止理论

在读Ross的《Introduction to Probability Models》时[1],有个例子的原理被广泛讨论——

(最佳奖品问题) 假设我们可以从一系列先后宣布的n个不同的奖项中选取一个,在一个奖项宣布后我们必须立刻决定是接受还是拒绝转而考虑随后的奖项。我们只能根据该奖项与前面已经宣布的奖项的比较决定是否接受它。就是说,例如,当第5个奖项宣布时,我们知道它与前面已经宣布的4个奖是如何比较的。假设拒绝了一个奖就失去了这次机会,我们的目标是使得到最佳奖的概率达到极大。假定奖项的所有n!个次序都是等可能的,我们该怎样做?

 选定一个k,0≦k≦n,同时考虑前k个都拒绝并接受[......]

阅读全文 »

连续抛掷一枚出现正面的概率为p的硬币

一、首次出现正面时抛掷次数的平均值E(N)。

令Y=1表示第一次掷硬币的结果是正面,Y=0表示第一次掷硬币的结果是反面,则:

E(N) = E(N|Y=0) × P(Y=0) + E(N|Y=1) × P(Y=1)
=[1 + E(N)] × (1-p) + 1×p
=1 + (1-p) × E(N)

所以:E(N) = 1/p

另一种方法是使用吸收马尔可夫链,以硬币处于正面的状态为吸收状态,易得标准形式的转移矩阵为:


则有:N = (I-B)-1 =[......]

阅读全文 »