1
$\begingroup$

Let $p$ be a distribution over $N$ objects, pick an object $k$ from $N$, and define $p^*(x)$ to be 0 if $x = k$ and $p(x) / (1 - p(k))$ otherwise.

Suppose I want to sample $n$ items from $p^*$ without replacement (that is, every time I draw an element, I set it aside and renormalise the probabilities of the remaining items), but I can only draw samples WOR from $p$. Is the following a valid sampling WOR scheme for $p^*$:

  1. Draw $n+1$ items from $p$ WOR.
  2. If any of the $n+1$ items are equal to $k$, remove it from the sample.
  3. Otherwise take the first $n$ items.
$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, it should be. My intuition is as follows.

Consider drawing $N$ items from $p$ WOR. This is a random ordering of your items. Picking the $n$ first items from this list is equivalent to drawing $n$ items from $p$.

Now consider the effect of your steps 2 and 3 of this interpretation. 2 and 3 together is equivalent to removing items $k$ from your list of $N$ randomly ordered items and picking the remaining $n$ first items is equivalent to drawing $n$ items from the set of size $N-N_k$ where $N_k$ items $k$ have been removed in accordance with $p^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.