2
$\begingroup$

This is a follow-up question to How to uniformly sample vertices from a large graph with given distance from a fixed vertex?.

Suppose I took a set $B$ of $n$ samples from a large but finite universe $U\supset B$. Each element $x\in U$ has a bias value $b(x)>0$ such that for any elements $x,y\in U$ we have $\frac{P[x\in B]}{P[y\in B]}=\frac{b(x)}{b(y)}$, i.e. $b(x)$ is proportional to $P[x\in B]$.

Knowing $b(x)$ for all $x\in B$, I would like to take a subsample $S\subset B$ of size $|S|=\frac{n}{c}$ for some $c>0$ such that $S$ is a uniform random sample of $U$. To achieve this, my idea was to take a weighted random sample with weights $w(x)=b(x)^{-1}$ from $B$, cancelling out the existing bias.

You may assume that $n$ is reasonably large (in my case $n\ge 1000000$) and that it can be taken as large as needed.

Does this method work? What value for $c$ can I choose to not run into artifacts from this method? If the method does not work, is there a different way to achieve the desired result?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.