# 全触分布

## 初始问题

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

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

$$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$$

## 问题拓展到$$m$$

$$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\le n | m)=\sum_{i=m}^{n}{P(X=i|m)}=\sum_{i=m}^{n}{\frac{F(i,m)}{m^i}}$$

$$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\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)$$的解析解

$$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}$$

$$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)$$成立。

## 验证分布律的正确性

$$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)= \sum _{k=0} ^{m-1} (-1)^k {m-1 \choose k} \frac {(m-1-k)^{n-1}} {m^{n-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) = \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)$$

## 等式$$\sum _{k=0} ^{m} (-1)^k {m \choose k} ( m-k )^{m-1} \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}$$

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

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

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

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

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

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

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

$$\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)$$

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

$$\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$$

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

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

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

$$\sum _{k=0} ^{m} (-1)^k {m \choose k} ( m-k )^{m-1} \equiv 0$$显然是$$n=m-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}$$

$$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    1   2   3   4   5   6   7   8   9  10
n    1   8  15  21  28  36  43  51  58  66