# How to calculate inclusion probability under sampling without replacement

I am quite new to sampling method.

The task is sampling without replacement with unequal probabilities, but I have problem in calculating inclusion probability.

I want to sample $n$ units from the population of size $N$ through the following procedure in the figure. After the procedure, I need to calculate the inclusion probability in order to get the Horvits-Tompson estimator, an unbiased estimator of the Population Total.

But I don't know how to calculate inclusion probability, because I need to traverse $n!\binom{N-1}{n-1}$ n-tuples (e.g. add the probability of $50!\binom{999}{49}$ n-tuples), it's huge and not realistic!!!

My ultimate goal is to have an unbiased estimator of the Population Total, based on $p_i(k)$ constructed by myself.

How can I do this?

The inclusion probability is also written as the following $p(u_i)$:

$p(i) = \sum_{(i_1, i_2, ..., i_n)\in S(i)}{p(i_1, i_2, ..., i_n)}$ where $S(i)$ is consisting of n-tuples where unit $i$ and other $(n-1)$ different units . There are $n!\binom{N-1}{n-1}$ elements in $S(i)$!

The formula is from paper: SAMPLING WITH VARYING PROBABILITIES WITHOUT REPLACEMENT: ROTATING AND NON-ROTATING SAMPLES.

• Hmm. There's not "one ultimate method" because as you note in your original question, the straightforward approach is computational intractably in all but the most trivial cases. Some methods work well in some cases but not in others, e.g. some form of rejection sampling can work well if you only want to draw 2 or 3 units from a large $n$ but becomes intractable if you want to draw a large fraction of $n$. Maybe this is a better introduction: sciencedirect.com/science/article/pii/… Commented Jan 13 at 13:40