全触分布

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

初始问题

假设有两台服务器，各自有独立的缓存需要预热（即初始化缓存），而预热时只能通过相同的访问地址，访问负载均衡器之后，由负载均衡器等概率随机选择一台预热，问至少需要几次地址访问，才能保证两台服务器中的缓存都被预热过的概率超过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

全触分布的分布律

全触分布的累积分布函数

全触分布

初始问题

问题拓展到\(m\)

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

验证分布律的正确性

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

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