二项式系数比值的下界
首先,我们先把这个比值展开成更直观的连乘形式,这对推导下界很有帮助:
$$A(k,n,m)=\frac{\binom{k-m}{n-m}}{\binom{k}{n}} = \prod_{t=0}^{m-1} \frac{n-t}{k-t}$$
这个式子的概率意义是:从 $k$ 个元素中不放回抽取 $n$ 个,恰好包含指定 $m$ 个元素的概率,这也和你提到的抽样问题对应上了。
针对你想要更紧、更简洁的下界需求,我整理了几个实用的选项,按紧致性和易用性排序:
1. 最直观且紧致性优异的下界
观察函数 $f(t)=\frac{n-t}{k-t}$,对 $t$ 求导可以发现它是单调递减的(因为分子分母都随 $t$ 减小,但分母减小的速度更快)。也就是说,当 $t$ 从0到 $m-1$ 递增时,每一项 $\frac{n-t}{k-t}$ 的值是逐渐变小的,最小的项就是 $t=m-1$ 时的 $\frac{n-m+1}{k-m+1}$。
既然所有项都大于等于这个最小值,那么它们的乘积自然大于等于最小值的 $m$ 次方:
$$A(k,n,m) \geq \left( \frac{n-m+1}{k-m+1} \right)^m$$
这个下界计算简单、形式直观,紧致性比你原来的指数下界好很多。比如取 $k=10,n=5,m=2$,实际 $A$ 约为0.222,这个下界约为0.197,而你原下界约为0.082,差距非常明显。
2. 适合理论分析的调和数形式下界
如果需要更偏向理论推导的形式,我们可以对连乘取对数,结合对数函数的经典下界 $\ln(1-x) \geq -\frac{x}{1-x}$($0<x<1$)来推导:
$$\ln A = \sum_{t=0}^{m-1} \ln\left(1 - \frac{k-n}{k-t}\right) \geq -(k-n) \sum_{t=0}^{m-1} \frac{1}{n-t}$$
这里的求和项 $\sum_{t=0}^{m-1} \frac{1}{n-t}$ 其实就是第 $n$ 个调和数减去第 $n-m$ 个调和数,即 $H_n - H_{n-m}$(调和数定义:$H_n = 1+\frac{1}{2}+\dots+\frac{1}{n}$)。代入后得到:
$$A(k,n,m) \geq \exp\left( -(k-n)(H_n - H_{n-m}) \right)$$
这个下界的紧致性略逊于第一个,但调和数有成熟的渐近展开公式,适合在大样本场景下做近似分析。
3. 大n场景的渐近近似下界
当 $n$ 足够大时,调和数可以用欧拉常数做渐近近似:$H_n \approx \ln n + \gamma + \frac{1}{2n}$(其中 $\gamma \approx 0.5772$ 是欧拉-Mascheroni常数)。把这个近似代入调和数形式的下界,整理后可以得到:
$$A(k,n,m) \geq \left( \frac{n-m}{n} \right)^{k-n} \cdot \exp\left( \frac{(k-n)m}{2n(n-m)} \right)$$
这个下界在大样本下紧致性进一步提升,同时保持了较好的简洁性,非常适合抽样问题的渐近分析。
这几个下界都比你原来的结果更紧,你可以根据具体场景选择最适合的形式。
备注:内容来源于stack exchange,提问作者MMH




