Let us have $k$ elements of weights $w_1,\ldots,w_k$ where the sum of the weights $w_1+w_2+\ldots+w_k=k$, where $w_i\geq 0$ for all $i$. We sample elements using weighted sampling (probabilities proportional to their weights) without replacement. Let $i$ be an element of relatively large weight, say $1000$. We want to understand the number of samples (in expectation or high probability) we need to draw to sample the element $i$.
We know the probability of sampling this element in the first iteration is $1000/k$. So, we should sample this element within expected $k/1000$ steps. However, since we are doing weighted sampling without replacement, we believe the expected number of steps should be much much smaller.
Any suggestions or ideas are welcome.