Monday Math 125

Consider two bins, each with N items, with N a large number. Let us randomly select one of the two bins, with equal probability (such as by flipping a fair coin), and remove an item from the selected bin. We repeat this procedure of removing items from the bins by random selection until one bin is empty. What, then, is the expected value n of the number of items remaining in the non-empty bin?

Let us denote by (a,b) the situation where a items have been removed from bin 1, and b have been removed from bin 2. Thus, we want to find the probability of (N,b). To find this, we note that to achieve this situation, we must first have (N-1,b), and then have bin 1 chosen for the next removal.
To find the probability of reaching (N-1,b), we note that we have done a total of N-1+b selections, each with probability 1/2; and that the number of different ways that the N-1+b selections can lead to N-1 from bin 1 and b from bin 2 is given by the binomial coefficient , so our probability is
, and so the next selection will choose bin 1 with probability 1/2, giving us
Now, our situation of one bin empty is (N,b) or (b,N), which has the same probability due to symmetry, thus requiring us to multiply by a factor of two; our expected value is thus

For large N, we can approximate our binomial coefficient with a Gaussian; from this previous post, we found

(where for convienience, we have renamed one of the variables).
To express our above binomial coefficient in this form, we first note that
and so
Next, we choose to define . Then, rewriting the above sum in terms of ξ instead of b (consequently reversing the order of summation):
Now, letting , so that , we can rewrite the binomial coefficient as
, so with
, we have the form for our Gaussian approximation; we see
and so
Note that our exponential factor means that only ξ terms of up to order will contribute, so for a large N, adding ξ to N will have negligible effect, and we can make the approximations , , and , so that we have
where this last change is due to the fact that the ξ=0 term for the sum is zero and so may be added freely. For large N, we can approximate the sum as an integral, and as the Gaussian is negligible for ξ>N, we may take the upper limit of the integral as infinity, instead of N, so we have
where we used the u-substitution .


Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: