Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi

I have a problem which i find hard to modelize.

Suppose i have an urn with $N$ marbles. Among these marbles, one is white and all the other ones are black. I draw $P$ marbles without replacement. If the probability of drawing one marble is uniform, then the hypergeometric distribution tells me that the probability $P_W$ of having the white marble among the $P$ marbles is:

$P_W=\frac{\binom{1}{1} \binom{N-1}{P-1}}{\binom{N}{P}}=\frac{P}{N}$

That was the easy case.

Now suppose we have different weights for each marble. One marble $i$ is assigned a weight $w_i$, and the probability of drawing the marble $i$ with one and only one draw is $p_i=\frac{w_i}{\sum_i w_i}$

Now let's go back to ou $P$ draws. What is the probability $P_W$ according to $P$,$N$,$w_i$.

All the ideas are welcome even with limit cases such as $P << N$

Thanks

share|improve this question
    
On the second and later draws, do you mean that the probability of drawing marble $i$ (if it has not already been drawn) is $w_i/(\sum_j w_j)$, with the sum over only those marbles not already drawn? –  Mark Meckes Sep 22 '10 at 17:47
    
This is correct –  GuillaumeThomas Sep 23 '10 at 8:16

1 Answer 1

up vote 2 down vote accepted

This probability is always bounded from below by the probability with replacement, which is $1-(1-w)^k$ where $w$ is the probability to pick the white marble in a single draw, and $k$ is the number of draws (changed from $P$ in your question which is rather unorthodox choice).

The probability of drawing the white marble at the $i$-th stage is bounded from above by $w/(1-\sum_{j=0}^i w_j)$, where $w_0,\ldots$ are ordered by descending weight, and sum to 1. So the probability of drawing the white marble can be bounded from above by $$1-\prod_{i=0}^k(1-\frac{w}{1-\sum_{j=0}^i w_j})$$

In particular, we get the same asymptotic bound when $w_0 << k^{-2}$.

share|improve this answer
    
(Re-entered after TeX error) Just a remark: the probability of drawing the white marble on the kth draw depends on the average weight of black marbles that are left (it's $w/(w + B_k)$, where $B_k$ is the mean weight of black marbles weight after $k$ draws of black marbles without replacement.) Since $B_k$ is a symmetric function of the weights of black marbles, the sequence of $B_k$ depends precisely on the first $k$ moments of the distribution of weights of black marbles, and probably has a nice formula that someone can supply. –  Bill Thurston Sep 22 '10 at 19:33
    
$B_k$ as you define it is a random variable. Its distribution is a symmetric function of the weights, but why does this mean it depends only on the first $k$ moments? –  Ori Gurel-Gurevich Sep 22 '10 at 20:41
    
The mean weight after $n$ disjoint picks is a symmetric polynomial of degree $n+1$ in the weights: it's the sum of all products of distinct weights times the their total, times a constant (the total weight of all black marbles). There vector space ofof symmetric degree $ \le n$ polynomials has dimension $n$, so since moments are linearly independent polynomials, they form a basis. There's a dimension shift if normalize sum of weights = 1, to coincide with probabilistic moments. Cf. en.wikipedia.org/wiki/Elementary_symmetric_polynomial –  Bill Thurston Sep 23 '10 at 1:14
    
Perhaps I completely misunderstood your comment. The way I see it is this: Denote the total weight of the remaining black marbles after $k$ draws by $X_k$. This is a random variable. The probability to now draw the white marble is $w/(w+X_k)$. Do you claim that the expected value of $X_k$ is a symmetric polynomial of the weights? I don't think that's true (except for $k=1$) since already the second draw involves division by $w+X_1$, so it seems like you get a some rational symmetric function. –  Ori Gurel-Gurevich Sep 23 '10 at 6:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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