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

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?

• For your real-life sampling what is the number of unique values and what is the largest sample size being considered? While I suspect that the two schemes are equivalent for all sample sizes and numbers of unique values, for small enough sample sizes one can show the equivalence explicitly.
– JimB
May 25, 2020 at 22:45
• The number of unique values is a million, and the sample size being consider is in thousands (5K for example). So an empirical verification is difficult. But your "proof" is a good starting point. I suspect that this should be a known result if true but haven't found a reference yet. May 30, 2020 at 0:45
• Good. Yes, I would agree this must have proved appropriately and probably many decades ago. I've written Mathematic code for both approaches and while I haven't got Mathematica to simplify symbolically to the same for both schemes, for all sorts of numerical examples they give the same results. (And that's probably my fault rather than Mathematica's.)
– JimB
May 30, 2020 at 0:55

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))$$.