3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Mark Meckes
    Commented Sep 22, 2010 at 17:47
  • $\begingroup$ This is correct $\endgroup$
    – GuillaumeThomas
    Commented Sep 23, 2010 at 8:16

1 Answer 1

Reset to default
2
$\begingroup$

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}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ (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. $\endgroup$
    – Bill Thurston
    Commented Sep 22, 2010 at 19:33
  • $\begingroup$ $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? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Sep 22, 2010 at 20:41
  • $\begingroup$ 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 $\endgroup$
    – Bill Thurston
    Commented Sep 23, 2010 at 1:14
  • $\begingroup$ 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. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Sep 23, 2010 at 6:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .