3
$\begingroup$

I have $n$ balls in an urn labeled from $1$ to $n$ and each of them has weight equal to its label. A ball has probability of being picked proportional to its weight, i.e. if the total weight of the balls in the urn is $w$ the probability of ball $i$ being picked is $\frac{i}{w}$.

My question now is, if I pick balls from the urn without replacement what is the probability that I pick ball $k$ before any ball in the set $\{k+1,\ldots, n\}$?

My only observation that might seem relevant at this time is that the ratio of the probability of picking ball $k$ to the probability of picking balls with weight greater than $k$ is constant at each step, i.e. it is $\frac{k}{\binom{n+1}{2}-\binom{k}{2}}$.

Edit: A spoiler for the answer can be found in the comment section. After seeing the solution I'm still wondering how that can come off as the intuitive answer. Is it possible to see the solution with intuition alone?

$\endgroup$
  • $\begingroup$ Suppose you added or removed other balls (not labeled in $k, k+1, \ldots, n$) from the urn in such a way that the probability ratio of your two events stays constant. Would this matter? If not, then you might just as well consider the simplest such example where there are no other balls... $\endgroup$ – whuber Oct 17 '11 at 15:55
  • 1
    $\begingroup$ I see, so you're saying the probability is $\frac{k}{\binom{n+1}{2}-\binom{k}{2}}$? I guess I will have to prove it by induction by first looking at the urn with only the balls in $\{k\ldots n\}$ and then proceed by adding balls. Thank you very much! $\endgroup$ – Haffi112 Oct 17 '11 at 18:03
  • $\begingroup$ One more question though if you have the time, is there any way to see this so it feels intuitive? $\endgroup$ – Haffi112 Oct 17 '11 at 18:27
  • $\begingroup$ That's a great followup. Why don't you edit your question to include it and see what responses you get? $\endgroup$ – whuber Oct 17 '11 at 19:02
1
$\begingroup$

Following up on the very astute observation by Haffi112 and the comment by @whuber, consider a standard problem of mutually exclusive events $A$ and $B$ that can occur on a trial of a simple experiment. Mutually independent trials of the simple experiment are conducted until one of the two events occurs. What is the probability that event $A$ occurs before event $B$? The standard analysis says that because of independence, we can ignore all previous trials and look only at the trial on which we know that one of $A$ and $B$ occurred, that is, $A \cup B$ occurred. The conditional probability that $A$ occurred on this trial is exactly the probability of "$A ~\text{before}~ B$" that we seek. $$P\{A ~\text{occurs before}~ B\} = P(A \mid (A\cup B)) = \frac{P(A \cap (A \cup B))}{P(A \cup B)} = \frac{P(A)}{P(A) + P(B)}$$

What if the trials of the simple experiment are not independent? The probabilities of $A$ and $B$ occurring on the $i$-th trial given that neither $A$ nor $B$ has occurred on the first, second, $\ldots$, $(i-1)$-th trials do depend on what happened on the previous trials, but denoting these probabilities by $P_i(A)$ and $P_i(B)$ respectively, we have, as before, that the conditional probability that the $i$-th trial concludes the compound experiment via occurrence of $A$ is $P_i(A)/(P_i(A) + P_i(B))$. Note that we are conditioning on what happened on the previous trials.

In the problem being analyzed, $$P_i(A) = \frac{k}{D}, ~ P_i(B) = \frac{(k + 1) + (k+2) + \cdots + n}{D} = \frac{\binom{n+1}{2} - \binom{k+1}{2}}{D} $$ where $D$ is the "weight" of the balls left in the urn after the $i-1$ trials. The exact value of $D$ depends on which of the balls numbered $1, 2, \ldots, (k-1)$ was drawn on the previous $i-1$ trials, but the ratio $P_i(A)/P_i(B)$ is the same regardless of what happened on the previous trials (as Haffi112 observed), and thus the probability that the compound experiment concludes on the $i$-th trial of the simple experiment is the same no matter which of the balls numbered $1, 2, \ldots, (k-1)$ was drawn on the previous $i-1$ trials.

The compound experiment must conclude no later than the $k$-th trial of the simple experiment. The law of total probability says that $$ P\{A ~\text{occurs before}~ B\} = \sum_{i=1}^{k} \frac{P_i(A)}{P_i(A) + P_i(B)}\times P\{\text{experiment concludes on}~i\text{-th trial}\}, $$ but since $$ \frac{P_i(A)}{P_i(A) + P_i(B)} = \frac{k}{\binom{n+1}{2} - \binom{k+1}{2}} ~ \text{for}~ i = 1, 2, \ldots k, $$ we have that $$ P\{A ~\text{occurs before}~ B\} = \frac{k}{\binom{n+1}{2} - \binom{k+1}{2}} $$ Note that the result is slightly different from the one conjectured by Haffi112.

$\endgroup$
  • $\begingroup$ Thank you for spending your time one this followup! It is definitely helpful and opened my eyes towards the problem from another perspective. $\endgroup$ – Haffi112 Oct 23 '11 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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