1
$\begingroup$

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.

enter image description here

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

enter image description here

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.

enter image description here

Question

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


$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – JimB
    May 25, 2020 at 22:45
  • $\begingroup$ 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. $\endgroup$
    – elexhobby
    May 30, 2020 at 0:45
  • $\begingroup$ 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.) $\endgroup$
    – JimB
    May 30, 2020 at 0:55

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.