重码估计方法

问题

设有 $n$ 个待编码对象，构成的集合为 $S$。

$$S=\{s_1,\cdots,s_n\}$$

现对其编码，允许使用的编码空间为集合 $C=\{c_1,\cdots,c_k\}$， 大小为 $k$，估计重码的数量。

独立随机编码近似

假设每个对象的编码是随机且独立的，则在编码每个对象时，某码 $c$ 可能被使用的概率是 $1/k$。在对集合 $S$ 中的每个字编码时，相当于重复执行 $n$ 次概率为 $1/k$ 的试验，最终 $c$ 被使用的次数 $X$ 满足 $B(n,1/k)$ 的二项分布，即

$$\mathbb P(X=x)=\binom{n}{x}\left(\frac1k\right)^{x}\left(1-\frac1k\right)^{n-x}$$

若 $X=0$ 或 $X=1$，则 $c$ 上不发生重码。若 $X\ge 2$，则 $c$ 上发生重码，需要选重的数量为 $X-1$. 因此，在这个编码上产生的选重数为 $Y=\max (X-1,0)$

$$\begin{aligned} \mathbb E(Y)&=\sum_{x=0}^{+\infty}\mathbb P(X=x)\max(X-1,0)\\ &=\sum_{x=1}^{+\infty}\mathbb P(X=x)(X-1)\\ &=\mathbb P(X=0)+\sum_{x=0}^{+\infty}\mathbb P(X=x)(X-1)\\ &=\mathbb P(X=0)+\mathbb E(X-1)\\ &=\mathbb P(X=0)+n/k-1 \end{aligned}$$

这意味着我们只需要计算 $\mathbb P(X=0)$ 即可。根据二项式展开：

$$\mathbb P(X=0)=\left(1-\frac1k\right)^n=1-\frac nk+\frac{n(n-1)}{2k^2}-\frac{n(n-1)(n-2)}{6k^3}+\cdots$$

注意到，前两项恰和 $n/k-1$ 抵消，因此在 $1\ll n\ll k$ 的情况下我们只需要取第三项即可，若要更精确，可取第四项。

$$\mathbb E(Y)\approx \frac{n(n-1)}{2k^2}-\frac{n(n-1)(n-2)}{6k^3}\approx\frac{n^2}{2k^2}\left(1-\frac{n}{3k}\right)$$

而发生重码的总数是全部编码上产生的选重数之和，因此需要乘以 $k$，即 $n^2/2k$。

另外，如果统计的标准不是选重数，而是涉及的重码总数，则可以表示为 $Z=X\times \mathbb I(X\ge 2)$ 的期望，

$$\mathbb E(Z)=\sum_{x=2}^{+\infty}\mathbb P(X=x)X=\mathbb E(X)-\mathbb P(X=1)$$ $$\mathbb P(X=1)=\frac nk\left(1-\frac1k\right)^{n-1}=\frac nk\left(1-\frac {n-1}k+\cdots\right)$$

因此

$$\mathbb E(Z)\approx\frac{n^2}{k^2}$$