Suppose I have an urn containing N different colours of balls and each different colour can appear a different number of times (if there are 10 red balls there need not also be 10 blue balls). If we know the exact contents of the urn before drawing we can form a discrete probability distribution which tells us the probability of drawing each colour of ball. What I am wondering is how the distribution changes after drawing k balls without replacement from the urn on average. I understand that as we draw from the urn we can update the distribution with the knowledge of what has been taken out, but what I want to know is what we would expect the shape of the distribution to be after we have removed k balls. Does the distribution change on average or does it remain the same? If it does not remain the same can we write down some formula for the what we expect the new distribution to look like on average after making k draws?
-
1$\begingroup$ i might be wrong - but this feels like that one knows the prior distribution, but has no informatoin about the likelihood (besides that k balls are removed). in that case - i would assume that the posterior is equal to the prior. To be fair - there is likelihood information that the number of balls has decreased, and that (for one ball removed) the distribution is hence e.g. bimodal between 50% possiblity of 9 red and 10 black and 50% possilbiity of 10 red and 9 black. i mgiht be wrong here though $\endgroup$– WouterJul 9, 2015 at 22:25
-
$\begingroup$ My intuition is that it is like the latter case which you described. I cannot find anyone speaking about this sort of process though. $\endgroup$– mjnicholJul 9, 2015 at 22:27
4 Answers
"Direct calculation": Let there be $n$ balls of $m$ colours in the urn. Let us focus on the probability of drawing one particular colour, say white, on the second draw. Let the number of white balls be $n_w$. Let $X_i$ be the colour of the ball obtained at the $i$-th draw.
\begin{eqnarray} P(X_2=W)&=&P(X_2=W|X_1=W)P(X_1=W)+P(X_2=W|X_1=\overline{W})P(X_1=\overline{W})\\ &=&\frac{n_w-1}{n-1}\frac{n_w}{n}+\frac{n_w}{n-1}\frac{n-n_w}{n}\\ &=&\frac{n_w(n-n_w+n_w-1)}{n(n-1)}\\ &=&\frac{n_w}{n}\\ &=&P(X_1=W) \end{eqnarray}
Of course this same argument applies to any colour on the second draw. We can apply the same kind of argument recursively when considering later draws.
[One could of course perform an even more direct calculation. Consider the first $k$ draws as consisting of $i$ white balls and $k-i$ non-white balls (with probability given by the hypergeometric distribution), and perform the corresponding calculation to the simple one above but for the draw at step $k+1$; one gets a similar simplification and cancellation, but it's not especially enlightening to carry out.]
A shorter argument: consider labelling the balls randomly with the numbers $1,2,...,n$, and then drawing them out in labelled order. The question now becomes "Is the probability that a given label, $k$, is placed on a white ball the same as the probability the label $1$ gets placed on a white ball?"
Now we see the answer must be "yes" by symmetry of the labels. Similarly, by symmetry of the ball-colours, it doesn't matter that we said "white", so the argument that label $k$ and label $1$ have the same probability applies to any colour. Hence the distribution at the $k$-th draw is the same as for the first draw, as long as we have no additional information from the earlier draws (i.e. as long as the earlier drawn balls are not seen).
-
$\begingroup$ Closely related to your 2nd way, is another short argument: imagine the set of all possible sequences in which the balls can be removed (e.g. blue first, then white, then white, ... might be one such sequence). If for each sequence in this set we swap the $1^{st}$ and $k^{th}$ elements, we simply permute the set. So for every sequence with a white (or whatever) ball in position $k$, there is exactly one corresponding sequence with a white ball in position $1$. Hence the probability of a white ball in position $k$ or position $1$ must be the same. I think this is essentially Neil's argument. $\endgroup$ Jul 10, 2015 at 0:52
-
$\begingroup$ @Silverfish Yes, looking at it, my second argument is essentially the same sort of argument as Neil's permutation argument. $\endgroup$– Glen_bJul 10, 2015 at 1:02
-
$\begingroup$ Thanks for the explanation. It was exactly what I needed to see! $\endgroup$– mjnicholJul 16, 2015 at 22:51
The only reason it is not perfectly obvious that the distribution remains unchanged (provided at least one ball remains) is that there is too much information. Let's strip out the distracting material.
Ignore, for a moment, the color of each ball. Focus on one ball. Assume $k$ balls are about to be randomly removed (and not observed), and then a $k+1$st ball will be drawn and observed. It makes no difference what order the selection occurs in, so you might as well observe the very first ball drawn (and then remove another $k$ balls if you insist). The distribution obviously has not changed, because it will not be affected by removing the other $k$ balls.
This argument--although perfectly valid--could make some people feel uneasy. The following analysis might be accepted as more rigorous, because it does not ask us to ignore the selection order.
Keep focusing on your ball. It will have some probability $p_k$ of being selected as the $k+1$st ball. Although $p_k$ is easy to compute, we don't need to know its value: all that matters is that it must be the same value for each ball (because all balls are equivalent) and that it be nonzero. But if it were zero, no ball would have any probability of being selected: so as long as at least one ball remains, $p_{k}\ne 0$.
Pay attention to the colors again. By definition, the chance that a particular color $C$ will be chosen (after $k$ balls are randomly removed) is the sum of the chances of all the original $C$-colored balls divided by the sum of chances of all original balls. When there originally are $k_C$ balls of color $C$ and $n$ balls total, that value is
$${\Pr}_k(C) = \frac{k_c p_k}{n p_k} = \frac{k_c}{n}.$$
When $k\lt n$ it does not depend on $k$, QED.
-
$\begingroup$ Thank you for the comment. It helped me understand the underlying processes more! $\endgroup$– mjnicholJul 16, 2015 at 22:52
Let the distribution of drawing a single ball — after having already drawn $k$ balls without replacement — have categorical distribution $E(D_k)$ given the distribution over such categorical distributions $D_k$.
I guess you are asking whether $E(D_k)$ is constant.
I think it is. Suppose that you eventually draw all of the balls. All permutations of the balls are equally likely. The probability of drawing initially is $E(D_0)$. You could rearrange your choices to an equally likely permutation whereby your first chosen ball was chosen last, and your second chosen was chosen first. That ball has expectation $E(D_1)$, which must be equal to $E(D_0)$ due to symmetry. By induction the $E(D_i)$ are all equal.
-
$\begingroup$ You mean that I am asking whether $E(D_k)$ is constant for every k, right? $\endgroup$– mjnicholJul 9, 2015 at 23:03
-
The "expected distribution" do not change. One could use a martingale argument! I Will add such to the answer later (I am travelling now).
The distribution, conditional on the earlier draws (for the later draws) do change only when you actually observes the draws. If you draw the ball from the urn with a tightly closed hand, and then throws it away without observing its color (I have used such theater effectively as class demonstration), the distribution do not change. This fact has an explication: Probability is about information, Probability is an information concept.
So probabilities do change only when you get new information (conditional probabilities, that is). Drawing the ball and throwing it away without observing it does not give you any new information, so nothing new to condition upon. So when you condition on the actual information set, that has not changed, so the conditional distribution cannot change.
EDIT
I will not now give much more details to this answer, only add one reference: Hosam M. Mahmoud:"Pólya Urn Models" (Chapman & Hall), which treats urn models like the one in this question, and also much more generalized urn schemes, also by using martingale methods for obtaining limit results. But the martingale methods are not needed for the question in this post.
-
$\begingroup$ The distribution (for the later draws) does not change even when you actually observe the draws. Why should observing anything change anything? $\endgroup$– Neil GJul 10, 2015 at 17:22
-
1$\begingroup$ @Neil I think kjetil is referring to the distribution conditional on the observed draws. $\endgroup$ Jul 10, 2015 at 20:01
-
$\begingroup$ @Silverfish: Ah I see. You're right, my apologies. $\endgroup$– Neil GJul 11, 2015 at 0:37
-
$\begingroup$ I Will edit to make clearer when at home in some two weeks. For now vacation in Venezia... $\endgroup$ Jul 11, 2015 at 14:31