Probability of drawing one element before another in weighted sampling without replacement

Question

Setup:

The setup is weighted sampling without replacement. By which I mean:

• You have a set of $n$ items, indexed by integers 1 through $n$, and the items have associated weights $\{w_1,\ldots,w_n\}$ (nonnegative real numbers), with total weight $w_\text{total} = \sum_{i=1}^nw_i$.
• You sample without replacement from the set, according to the weights.
  • that is, the probability that the first item drawn is $i$ is $\frac{w_i}{w_\text{total}}$, then the probability that the second item is $k$ given the first item is $i$ is $\frac{w_k}{w_\text{total}-w_i}$, etc.

Question:

For fixed $n$ and fixed $i$ and $j$ in $\{1,\ldots, n\}$, what is an expression for the probability that item $i$ is drawn before item $j$?

I have a solution which I'll post below, but I wonder if there are nicer ways of explaining it.

Answer 1

The answer is $\mathbb{P}(i\text{ is drawn before }j) = \frac{w_i}{w_i + w_j}$.

This can be seen as a consequence of the fact that the probability that $i$ comes before $j$ is not affected by the weights other than $w_i$ and $w_j$. The desired probability doesn't change when conditioning on the outcome of any draw that isn't $i$ or $j$.

Imagine in the original setup you're drawing balls according to their weights from an urn. But now, suppose before starting you put items $i$ and $j$ together in a bag (let's call it $i\!\!j$; it has weight $w_i+w_j$). Now, there are $n-1$ objects in the urn, where we've replaced items $i$ and $j$ with the bag containing them, so the set of objects in the urn is $(\{1,\ldots,n\}\setminus\{i,j\})\cup\{ i\!\!j \}$. Then you draw items without replacement as usual, but if you get the bag, you then take an additional step: draw either $i$ or $j$ from the bag, according to their weights: so the conditional probability of $i$ given you drew the bag is $\mathbb{P}(i\mid i\!\!j) = w_i/(w_i+w_j)$, and likewise the conditional probability of $w_j$ is the complement. Whatever item was left in the bag, put in the original urn, and continue as usual. This leads to the same probabilities for sequences of items drawn as the original scheme.

Now it should be clear that for any permutation $\sigma$ from the set $S_{n-1}$ of all permutations of the $n-1$ objects in the urn, $\mathbb{P}(i \text{ before } j\mid \sigma)$ is simply $\mathbb{P}(i \mid i\!\!j)$, the probability of drawing $i$ from the bag $i\!\!j = w_i/(w_i+w_j)$ (which doesn't depend on $\sigma$). So, to be explicit:

$$ \begin{aligned} \mathbb{P}(i \text{ before } j) &= \sum_{\sigma} \mathbb{P}(i\text{ before }j \mid \sigma)\mathbb{P}(\sigma)\\ %&= \sum_{\sigma} \mathbb{P}(i\text{ before }j)\mathbb{P}(\sigma)\\ &= \sum_{\sigma} \mathbb{P}(i \mid i\!\!j)\mathbb{P}(\sigma)\\ %= \mathbb{P}(i \mid i\!\!j)\sum_{\sigma} \mathbb{P}(\sigma) &= \mathbb{P}(i \mid i\!\!j) = \frac{w_i}{w_i+w_j} \end{aligned} $$