6
$\begingroup$

An urn contains N-1 red and 1 green ball. Each ball has an associated weight. If each ball is drawn (without replacement) with a probability proportional to how much its weight contributes to the urn, what is the expected number of attempts required to get the green ball?

Example: 2 red balls of weight 0.3 and 0.4, and green ball of weight 0.3.

In first attempt, Pr(red1)=0.3, Pr(red2)=0.4, Pr(green)=0.3.

Say, the red ball with weight 0.3 is chosen in the first attempt.
Then, in the next attempt, Pr(red2)=0.4/(0.4+0.3) and Pr(green)=0.3/(0.4+0.3). It becomes relatively difficult to keep track of the probabilities if there are more red balls.

Improve this question
$\endgroup$
2
  • $\begingroup$ Is this homework? If so please tag as such $\endgroup$
    – nico
    Commented Feb 2, 2013 at 15:41
  • 1
    $\begingroup$ It is not homework. Its a variation on the Wallenius' noncentral hypergeometric distribution, but I have not found a solution for it. $\endgroup$
    – user20388
    Commented Feb 2, 2013 at 15:57

1 Answer 1

Reset to default
5
$\begingroup$

The same model is used by poker players to estimate the probability of finishing in each place in a tournament given the stack sizes. It is called the Independent Chip Model or ICM. You can download my program ICM Explorer which can calculate the finishing probabilities for up to $10$ balls/players.

Although there doesn't seem to be a simple expression for the probability of finishing in the $k$th place, it's actually quite easy to answer your question. The expected number of red balls you draw before the green ball is the sum of the probabilities that you draw each red ball before the green ball. That's the same as a "last longer" bet in a poker tournament. According to this model, you can ignore all of the other players: consider the first time that you draw the green ball or the $i$th red ball. The conditional probability that you draw the red ball of weight $r_i$ before the green ball of weight $g$ is $r_i/(r_i+g)$, so the expected number of red balls you draw before the green ball is

$$\sum_i \frac{r_i}{r_i+g}$$

and the expected number of attempts necessary to find the green ball is $1$ more than this.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks Douglas. Can you explain why "the expected number of red balls you draw before the green ball is the sum of the probabilities that you draw each red ball before the green ball?" $\endgroup$
    – user20388
    Commented Feb 2, 2013 at 19:28
  • 1
    $\begingroup$ The count of red balls is a sum of indicator random variables which are $1$ if the $i$th red ball is drawn before the green ball, and $0$ otherwise. The expected value of a random variable which is $0$ or $1$ is the probability that the variable is $1$. $\endgroup$
    – Douglas Zare
    Commented Feb 2, 2013 at 19:31
  • $\begingroup$ Got that! I am also trying to mathematically show that the probability of drawing a certain red ball before the green one is independent of what other red balls having already been chosen. But, since probabilities are assigned based on the weight of remaining balls, I do not see how these are independent events. Any clarifications would help. $\endgroup$
    – user20388
    Commented Feb 2, 2013 at 23:57
  • 1
    $\begingroup$ Imagine the $i$th red ball and the green ball are stuck together to make a yellow ball whose weight is the sum of the weights of the pieces. When you draw the yellow ball, you break it into the red and green ball. You choose the red ball with probability $\frac{r_i}{r_i + g}$, and the green ball with the complement. Put the unchosen piece back into the urn. This procedure gives the same probability of each sequence of balls as the original without joining the $i$th red and the green ball, so the probability of choosing the $i$th red before the green is the same in the original. $\endgroup$
    – Douglas Zare
    Commented Feb 3, 2013 at 1:24
  • $\begingroup$ Great! Thanks for the head-to-toe explanation. $\endgroup$
    – user20388
    Commented Feb 3, 2013 at 14:59

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.