知识库 · 文字讲解,AI 整理
集券问题
有 $n$ 种优惠券,每次等概率抽到一种,集齐全部平均要抽多少次?
已经有 $k$ 种时,下一次抽到新券的概率 $p_k=\frac{n-k}{n}$。等到下一张新券的次数服从几何分布,期望 $\frac1{p_k}=\frac n{n-k}$(几何级数 里算过)。由期望的线性性
LaTeX
$$E[T]=\sum_{k=0}^{n-1}\frac n{n-k}=n\sum_{j=1}^{n}\frac1j=nH_n=n\ln n+\gamma n+\frac12+O(n^{-1}).$$
$H_n$ 是 调和数。最后几张券最难等:收集最后一种平均就要 $n$ 次。
随机采样、哈希、随机算法的分析里常常出现这个 $n\ln n$。进一步可以算方差和高概率的界。
用到它的地方
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。