How can I prove that two algorithms for weighted sampling without replacement are equivalent?

Question

I have a table with N rows and n unique elements. Let j denote the row index and i denote the element. In the table below $N=9, n=3$. Let $w_i$ denote the count of element i. For example, $w_1=4, w_2=3, w_3=2$, in the table below. $\sum_{i=1}^n w_i = N$.

I want to do a weighted sampling of $m$ elements without replacement from this table, where the weight of element $i$ is $w_i$. I have two schemes and want to know if they're equivalent i.e., if they have the same probability of sampling any tuple of $m$ unique elements.

Assume $m=2$ for the discussion. Here are the two algorithms.

Scheme1

Generate a uniform random number $U_j \in [0,1]$ for each row. Sort the rows in decreasing order by $U_j$, and pick the top $m$ unique elements. So I keep scrolling the table till I find $m$ unique elements. The figure below shows the table after sorting, and in this case I would pick $m=2$ elements $i=1,3$.

Scheme 2

The other scheme, which is typically used to perform weighted sampling without replacement (see Algorithm A in https://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf), is to roll up the j index, so we have a table containing the $n$ elements exactly once (group by operation on the above table). We then generate random numbers $U_i^{1/w_i}$, sort by these values, and pick the top 2 elements. In the table below, the elements $i=2,3$ would be selected.

Question

Are these two sampling schemes equivalent? How can I prove / verify this?

---

Answer 1

If you just want to feel more comfortable about the equivalence, then performing simulations using both schemes would be good.

Here I'll do a brute force but limited proof.

For the first scheme consider just obtaining the proportion of equally likely arrangements that a 1 is followed by a 2. That can happen in with several different arrangements: {1,2}, {1,1,2}, {1,1,1,2}, {1,1,1,1,2}, etc. If we use the frequency counts ($w_1$, $w_2$, and $w_3$), then that probability is

$$\frac{w_1}{n} \left(\frac{w_2}{n-1}+\sum _{j=1}^{w_1-1} \frac{w_2 \left(\prod _{i=1}^j \frac{w_1-i}{n-i}\right)}{n-j-1}\right)$$

That simplifies to $\frac{w_1 w_2}{(w_2+w_3) (w_1+w_2+w_3)}$.

For the second scheme note that a uniform random variable $U$ raised to the $1/w$ power has a $\text{Beta}(w,1)$ distribution. As we have independent random variables $Z_i=U_i^{1/w_i}$ for $i=1,2,3$, we can integrate over the product of the pdf's such that $Z_1>Z_2>Z_3$.

$$\int _0^1\int _0^{z_1}\int _0^{z_2}\frac{z_1^{w_1-1} z_2^{w_2-1} z_3^{w_3-1}}{B(w_1,1) B(w_2,1) B(w_3,1)}dz_3 dz_2 dz_1$$

$$=w_1 w_2 w_3 \int _0^1\int _0^{z_1}\int _0^{z_2} z_1^{w_1-1} z_2^{w_2-1} z_3^{w_3-1}dz_3 dz_2 dz_1$$

$$=\frac{w_1 w_2}{(w_2+w_3) (w_1+w_2+w_3)}$$

where $B(a,b)=\frac{\Gamma (a) \Gamma (b)}{\Gamma (a+b)}$.

So we end up with the same result.

I'm sure this "proof" can be made much more solid and one can see if $n=\sum_i^k w_i$, then the probability of obtaining an $i$ followed by a $j$ (with $i\neq j$) is $w_i w_j/(n(n-w_i))$.