Draw Balls from an Urn Without Replacement with Probability Drawing Proportional to Size of Ball.

Question

Sighs - Another ball and urn question? I don't think so - I feel that this one has a nice twist to it :)

Problem Statement

You are given $N$ balls in an urn. The volume of the $i$-th ball is $V_i$.

You pick the $N$ balls one at a time from the urn without replacement such that the probability of drawing the $i$-th ball from the urn is proportional to the ratio of volume of the $i$-th ball to the total remaining volume of balls in the urn.

What is the probability that ball $i$ is sampled before ball $j$?

The Bigger Picture

The actual problem that I am trying to solve is to find the expect number of times I will draw a ball from the urn before I draw the $i$-th ball from the urn. Using linearity of expectation I was able to reduce this quantity to $$1 + \sum_{j\not=i} Pr(idx_j < idx_i)$$ where $idx_i$ is the the turn in which the $i$-th ball was drawn and $Pr(idx_j < idx_i)$ is the main quantity that I want to know from the question.

I conjecture that $Pr(idx_j < idx_i) = \frac{V_j}{V_i + V_j}$ and this seems to be working for a couple of small examples that I checked manually. I could try and prove this using induction but I don't find it very satisfying to prove statements like this using induction after guessing the final form - you usually tend to miss out on the underlying structure that enforces such formulae.

Any hints on how to estimate this quantity? Thanks!

Answer 1

Fix $i$ and $j$, and consider any drawing where both balls $B_i$ and $B_j$ are still in the urn. Let $W$ be the total weight of all other balls still in the urn. The probability that we draw $B_i$, resp. $B_j$, is given by $$P(i)={V_i\over V_i+V_j+W},\quad P(j)={V_j\over V_i+V_j+W}\ ,$$ and since these events are exclusive the probability that we draw one of them is $$P(i\vee j)={V_i+V_j\over V_i+V_j+W}\ .$$ It follows that the conditional probability of drawing $B_i$, given that one of $B_i$ or $B_j$ is drawn, comes to $$P(i\>|\> i\vee j)={V_i\over V_i+V_j}\ ,$$and this is valid for all drawings until one of $B_i$ or $B_j$ is drawn, whereby the game ends.

Answer 2

Yeah, I think your conjecture is right, but I cannot seem to find a way to do it without induction. Thanks to induction, the only case we care about is when $V_i$ or $V_j$ is picked first. Then, for all such cases, the probability that $V_i$ comes before $V_j$ is indeed given by your formula $\frac{V_i}{V_i + V_j}$.

Also, in your other formula, I suspect you are counting the draw of the $i$th ball as one draw too? The problem seems to be formulated as "expected number of draws before the $i$th one" in which case that +1 shouldn't be there I think (not that it matters too much)