不放回的WRS问题算法正确性证明

未分类

---

算法：

对权值数列$\{a_i\},1 \le i \le n$每个数，取$b_i=random(0,1)^{\frac{1}{a_i}},random(0,1)$表示从$(0,1)$随机一个实数，然后对$\{b_i\}$排序，按$b_i$从大到小取样。

证明：

不放回取样算法的正确性基于对所有的二元组$a_i$和$a_j$，$1 \le i < j \le n$，取$i$的概率是$\frac{a_i}{a_i+a_j}$。

那么按照上面给出的算法，对二元组$(i,j)$，取$i$的概率是

$$p(i|(i,j))=\int _{0} ^{1} \int_{0} ^{1} (x_2^{\frac{1}{a_j}} < x_1^{\frac{1}{a_i}}) dx_1dx_2 = \int _{0} ^{1} x_1^{\frac{a_j}{a_i}} dx_1 = \frac{1}{1+\frac{a_j}{a_i}} x_1^{1+\frac{a_j}{a_i}} \left. \right|_0^1 = \frac{a_i}{a_i+a_j}$$