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 .

### Like this:

Like Loading...

*Related*

Tags: Math, Monday Math, Probability

This entry was posted on June 28, 2010 at 12:08 am and is filed under Math/Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply