全触分布

最近想到一个问题,发现了一个有趣的分布,姑且叫其全触分布。可能这个分布已经有了名字,不过翻了一遍概率论的书,似乎没有看到有谈过这个分布。

初始问题

假设有两台服务器,各自有独立的缓存需要预热(即初始化缓存),而预热时只能通过相同的访问地址,访问负载均衡器之后,由负载均衡器等概率随机选择一台预热,问至少需要几次地址访问,才能保证两台服务器中的缓存都被预热过的概率超过99%

这个问题等价于一个投硬币的问题,问至少多少次伯努利试验后,才能保证正反面都出现过的概率超过99%

令随机事件\(X\)表示,第\(n\)次伯努利试验时,才使得正反面都出现过。显然,当\(n<2\)时,事件不会发生;当\(n=2\)时,一定是一次正面一次反面;当\(n>2\)时,一定是前\(n-1\)次都是某一面,剩下的第\(n\)次是另外一面。 据此知道,随机事件\(X=n\)的概率为

$$P(X=n)=\frac{1}{2^{n-1}}$$

其中\(n \ge 2\),而当\(n < 2\)时,\(P(X=n)=0\)

验证所求分布律的正确性

$$P(X\ge 2)=\frac{1}{2}+\frac{1}{2^2}+…+\frac{1}{2^{n-1}}+…=1$$

分布应该如此。返回原始问题,得知在问,使得不等式\(P(X\le n)\ge0.99\)成立的最小的\(n\)为几。

由于

$$P(X\le n)=P(X=2)+P(X=3)+…+P(X=n)$$

$$=1-\frac{1}{2^{n-1}}$$

求得

$$n\ge 2\log_2{10}+1 \thickapprox7.6$$

所以,最小的\(n\)8,即至少8次伯努利试验后才能保证正反面都出现过的概率超过99%

问题拓展到\(m\)

进一步,假设原始问题中不止两台机器,而是\(m\)台,伯努利试验中也不是投掷硬币,而是从\(m\)个小球中随机选,问至少多少次试验后,才能保证每台机器或者每个小球都出现过的概率超过99%

类似地,令随机事件\(X\)表示,第\(n\)次试验时,才使得每个小球都出现过。显然,当\(n<m\)时,事件不会发生;当\(n=m\)时,一定是每个小球都只出现了一次;当\(n>m\)时,一定是前\(n-1\)次出现了\(m-1\)个小球,第\(n\)次恰好出现的是剩下的那个小球。

\(n\)次试验的概率空间容易计算,是\(m^n\),因为每次都有\(m\)种选择,一共要选\(n\)次。对于出现随机事件\(X\)的次数,可以假设为\(F(n,m)\)次,即\(F(n,m)\)表示第\(n\)次试验时,才使得\(m\)个小球每个小球都出现过,也即

$$P(X=n|m)=\frac{F(n,m)}{m^n}$$

因为\(P(X=n|m)\)表示第\(n\)次试验时,才使得每个小球都出现过,或每个机器都被触碰过,因而称作全触分布。

最终求解的目标是\(P(X\le n | m)\ge0.99\),而

$$P(X\le n | m)=\sum_{i=m}^{n}{P(X=i|m)}=\sum_{i=m}^{n}{\frac{F(i,m)}{m^i}}$$

所以,关键在于如何求解\(F(n,m)\)。前面分析到,当\(n>m\)时,一定是前\(n-1\)次出现了\(m-1\)个小球,第\(n\)次恰好出现的是剩下的那个小球。如果用\(G(n,m)\)表示\(n\)次试验中,\(m\)个小球都出现过的次数,那么

$$F(n,m)=m \cdot G(n-1,m-1)$$

\(G(n,m)\)不同于\(F(n,m)\)的地方在于,\(G(n,m)\)没有限制直到第\(n\)次试验,才满足\(m\)个小球都出现过,据此,有\(G(n,m)\ge F(n,m)\)

求解\(G(n,m)\),可以将集合划分为两个相似的缩小集合。这个划分可以根据,\(m\)个小球中的某一个是否只出现在了第\(n\)次试验中。如果某一个小球只出现在第\(n\)次试验中,那么前\(n-1\)次,就只有\(m-1\)个小球出现,即共有\(m\cdot G(n-1, m-1)\)种;如果同样的小球,不止出现在第\(n\)次试验中,那么前\(n-1\)次,仍旧有\(m\)个小球出现,共有\(m\cdot G(n-1, m)\)种。综合可得

$$G(n,m)=m\cdot G(n-1,m-1) + m\cdot G(n-1,m)$$

由以上两个等式可以知道,\(G(n,m)\)具体比\(F(n,m)\)多了多少,多了\(m\cdot G(n-1, m)\),即

$$G(n,m)-F(n,m)= m\cdot G(n-1,m)$$

在求解\(G(n,m)\)的解析形式前,根据定义能够得出以下两个恒等式,即

当\(n<m\)时,\(G(n,m)\equiv 0\)

当\(n=m\)时,\(G(n,m)\equiv 1\)

当求得解析解后,验证概率分布律时,将会再次通过代数的方式证明两个恒等式。 这是函数\(G(n,m)\)非常有趣的两个特性。

求\(G(n,m)\)的解析解

直接通过\(G(n,m)\)的递推形式,求解析形式比较困难,可以尝试用数学归纳法,先从较小的\(m\)开始。

当\(m=1\)时,\(G(n,1) \equiv 1\)

当\(m=2\)时,\(G(n,2) = 2G(n-1,2)+2\),解析解为\(G(n,2)=2^n-2\)

当\(m=3\)时,\(G(n,3) = 3G(n-1,3)+3 \times (2^{n-1}-2)\),解析解为\(G(n,3)=3^n-3\times 2^n+3\)

当\(m=4\)时,\(G(n,4) = 4G(n-1,4)+4 \times (3^{n-1}-3\times 2^{n-1}+3)\),解析解为\(G(n,4)=4^n-4\times 3^n + 6 \times 2^n -4\)

如果在求解到\(m = 4\)时,还没注意到组合系数的话,那大概需要补补组合数学基础了。

有了组合系数的观察,一般地,\(G(n,m) = \sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(m-k)^n\)

将\(m = 1, 2, 3,4\)分别依次带入方程,得出同直接由递推式求得一致的结果。

接下来验证,解析解能使递推式始终成立。由解析解方程,可知

$$G(n-1,m-1) = \sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
(m-1-k)^{n-1}$$

$$G(n-1,m) = \sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(m-k)^{n-1}$$

令第一式的\(t=k+1\),则

\(G(n-1,m-1) = \sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
(m-1-k)^{n-1}\)
\(= \sum
_{t=1}
^{m}
{
(-1)^{t-1}
{m-1 \choose t-1}
(m-t)^{n-1}
}\)

于是

\(G(n-1,m-1) + G(n-1,m)\)

\(= \sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(m-k)^{n-1}
+
\sum
_{t=1}
^{m}
{
(-1)^{t-1}
{m-1 \choose t-1}
(m-t)^{n-1}
}
\)

\(
=
m^{n-1}
+
\sum
_{k=1}
^{m}
{
(m-k)^{n-1}
\lgroup
(-1)^k
{m \choose k}
+
(-1)^{k-1}
{m-1 \choose k-1}
\rgroup
}
\)

\(
=m^{n-1}
+
\sum
_{k=1}
^{m}
{
(-1)^k
(m – k) ^ {n-1}
\lgroup
{m \choose k}

{m-1 \choose k-1}
\rgroup
}
\)

\(
=m^{n-1}
+
\sum
_{k=1}
^{m}
{
(-1)^k
(m – k) ^ {n-1}
{m-1 \choose k}
}
\)

\(
=m^{n}
\cdot
\frac{1}{m}
+
\sum
_{k=1}
^{m}
{
(-1)^k
(m – k) ^ {n}
{m-1 \choose k}
\frac{m}{m-k}
\cdot
\frac{1}{m}
}
\)

\(
=
\frac{1}{m}
\cdot
\lgroup
m^{n}
+
\sum
_{k=1}
^{m}
{
(-1)^k
(m – k) ^ {n}
{m \choose k}
}
\rgroup
\)

\(
=
\frac{1}{m}
\cdot
\sum
_{k=0}
^{m}
{
(-1)^k
{m \choose k}
(m – k) ^ {n}
}
\)

所以

\(G(n,m)=m\cdot G(n-1,m-1) + m\cdot G(n-1,m)\)成立。

验证分布律的正确性

由\(G(n,m) = \sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(m-k)^n\)
和\(F(n,m)=m \cdot G(n-1,m-1)\),得知

$$F(n,m) =
m
\cdot
\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
(m-1-k)^{n-1}$$

又\(P(X=n|m)=\frac{F(n,m)}{m^n}\)

所以

$$P(X=n|m)=
\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
\frac
{(m-1-k)^{n-1}}
{m^{n-1}}$$

正确的分布律应满足\(P(X \ge m|m)
\equiv
1\)
,即须证明

$$\sum
_{n=m}
^{\infty}
{P(X=n|m)}
\equiv
1$$

即证明

$$\sum
_{n=m}
^{\infty}
{
\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
\frac
{(m-1-k)^{n-1}}
{m^{n-1}}
}
\equiv
1$$

即证明

$$\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
\sum
_{n=m}
^{\infty}
{
(
1-
\frac
{1+k}
{m}
)^{n-1}
}
\equiv
1$$

即证明

$$\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
\frac
{m}
{1+k}
(
1-
\frac
{1+k}
{m}
)^{m-1}
\equiv
1$$

即证明

$$\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose 1+k}
(
1-
\frac
{1+k}
{m}
)^{m-1}
\equiv
1$$

即证明

$$\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose 1+k}
(
m-1-k
)^{m-1}
\equiv
m^{m-1}$$

也即证明

$$\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(
m-k
)^{m-1}
\equiv
0$$

观察恒等式左边,发现似曾相识,回看\(G(n,m)\)的解释式

$$G(n,m) = \sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(m-k)^n$$

发现

$$\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(
m-k
)^{m-1}
= G(m-1, m)$$

根据前面的恒等关系

当\(n<m\)时,\(G(n,m)\equiv 0\),得证。

等式\(\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(
m-k
)^{m-1}
\equiv
0\)
的常规证明

直接证明\(G(m-1,m)\equiv 0\),可能没有思路,可以先从\(G(0,m)\equiv 0\)和\(G(1,m)\equiv 0\)开始。

A.?证明\(G(0,m)
=
\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
\equiv
0\)

这个恒等式,直接用二项式展开,即可证得。根据二项式定理,知道

$$(x-1)^m
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
x^{m-k}$$

令\(x=1\),即得到

$$0
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k$$

得证\(G(0,m)\equiv 0\)。

B. 证明\(G(1,m)
=
\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(m-k)
\equiv
0\)

类似于A步的证明,对二项式等式

$$(x-1)^m
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
x^{m-k}$$

两边同时求\(x\)的导数,得

$$m\cdot
(x-1)^{m-1}
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
(m-k)
x^{m-k-1}$$

令\(x=1\),即得到

$$0
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
(m-k)$$

得证\(G(1,m)\equiv 0\)。

C. 证明\(\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(
m-k
)^{m-1}
\equiv
0\)

类似于B步骤的证明,对二项式等式

$$(x-1)^m
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
x^{m-k}$$

两边同时求\(x\)的\(n\)阶导函数(其中\(1 \le n \le m-1\)),得

$$\frac{m!}{(m-n)!}
\cdot
(x-1)
=
\sum
_{k=0}
^{m-n}
{m \choose k}
(-1)^k
\cdot
x^{m-k-n}
\cdot
\prod
_{i=0}
^{n-1}
(m-k-i)$$

令\(x=1\),即得到

$$0
=
\sum
_{k=0}
^{m-n}
{m \choose k}
(-1)^k
\cdot
\prod
_{i=0}
^{n-1}
(m-k-i)$$

因为当\(m-n+1\le k \le m\)时,有

$$\prod
_{i=0}
^{n-1}
(m-k-i)=0$$

所以

\(0
=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
\prod
_{i=0}
^{n-1}
(m-k-i)\)

\(=
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
\sum
_{i=1}
^{n}
a_i
\cdot
(m-k)^i\)

\(=
\sum
_{i=1}
^{n}
a_i
\cdot
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
(m-k)^i\)

因为对于所有的\(1 \le n \le m-1\),都有

$$\sum
_{i=1}
^{n}
a_i
\cdot
\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
(m-k)^i
=0$$

因而,不论常数\(a_i\)是多少,都有

$$\sum
_{k=0}
^{m}
{m \choose k}
(-1)^k
\cdot
(m-k)^n
=0$$

成立。

得证,当\(1 \le n \le m-1\)时,

$$G(n,m)\equiv 0$$

\(\sum
_{k=0}
^{m}
(-1)^k
{m \choose k}
(
m-k
)^{m-1}
\equiv
0\)显然是\(n=m-1\)时的情况。

类似地,也能证得\(G(m,m)\equiv 1\)。

求解\(P(X\le n | m)\ge0.99\)

回到最初的目标,

\(P(X\le n | m)
=
\sum
_{i=m}
^{n}
{P(X=i|m)}\)

\(=
\sum
_{i=m}
^{n}
\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
(1- \frac{1+k}{m})^{i-1}
\)

\(
=
\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
\sum
_{i=m}
^{n}
(1- \frac{1+k}{m})^{i-1}
\)

\(=
\sum
_{k=0}
^{m-1}
(-1)^k
{m-1 \choose k}
\frac
{m}
{1+k}
[
(1- \frac{1+k}{m})^{m-1}

(1- \frac{1+k}{m})^{n}
]
\)

\(=
\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose k+1}
(1- \frac{1+k}{m})^{m-1}

\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose k+1}
(1- \frac{1+k}{m})^{n}
\)

\(
=
1

\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose k+1}
(1- \frac{1+k}{m})^{n}
\)

若求\(P(X\le n | m)\ge0.99\)

即求

$$1

\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose k+1}
(1- \frac{1+k}{m})^{n}
\ge
0.99$$

即求

$$\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose k+1}
(1- \frac{1+k}{m})^{n}
\le
0.01$$

即求

$$0.01 \times m^n

\sum
_{k=0}
^{m-1}
(-1)^k
{m \choose k+1}
(m – 1 – k)^{n}
\ge
0$$

即求

$$0.01 \times m^n

\sum
_{k=1}
^{m}
(-1)^{k-1}
{m \choose k}
(m – k)^{n}
\ge
0$$

有此不等式,可知不同\(m\)时,满足不等式的\(n\)的最小取值,下表列举了前10项

m    1   2   3   4   5   6   7   8   9  10
n    1   8  15  21  28  36  43  51  58  66

全触分布的分布律

touch-all-dist

全触分布的累积分布函数

touch-all-cum

发布人

jeremy1990

现居北京,就职于亚马逊中国,软件工程师。

《全触分布》下有2条回复

  1. 从描述上来看“全触”应该属于典型的Coupon collector’s problem。“全触”这个问题还可以拓展成为缓存中每一项的命中概率是不相等的(因为计算机数据的访问有时间和空间局部性,或是人类行为对与数据访问符合zipf分布)。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注