Probability to choose specific item in a "weighted sampling without replacement" experiment
I'm pulling this from Pavlos S. Efraimidis, Paul G. Spirakis, Weighted random sampling with a reservoir, Information Processing Letters, Volume 97, Issue 5, 16 March 2006, Pages 181-185, ISSN 0020-0190, 10.1016/j.ipl.2005.11.003.
There, the authors begin by describing a basic weighted random sampling algorithm with the following definition:
Input: A population $V$ of $n$ weighted items
Output: A set $S$ with a WRS of size m
- Repeat Steps 2 and 3 for $k=1,2,\ldots,m$
- The probability of $v_i$ to be selected is:$$p_i(k) = \frac{w_i} {\sum_{S_j \in V - S} {w_j}}$$
- Randomly select an item $v_k \in V - S$ and insert it into $S$
The authors go on to explain how they arrive at the probability, but I'll summarize. Starting with the first item, the probability that $w_n$ is selected is its own weight divided by the sum of all weights. $$\frac{w_n}{w_1 + w_2+w_3+\ldots+w_n}$$ Easy enough. Now, the probability that each subsequent item will be chosen is its own weight divided by the sum of the remaining weights. If we do this calculation for each weight $w_i$ in order with $i=[1,n]$, we arrive at the authors' final summary equation for any permutation $\Pi$:
$$ P(\Pi) = \prod_{i=1}^{n} {\frac{w_i} {w_1 + w_2 +\ldots+w_i}} $$
Which is to say, the probability that an item is chosen can be defined as indexes of an array $w$ that contains all weights, like so: $$\frac{w(i)}{w([1,i])}$$
This isn't particularly difficult work, but I didn't want to create the proof myself, hence the quoting of Efraimidis & Spirakis.