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?


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.