|
On Two Trays |
|
|
|
I’m one step ahead of the shoe shine, |
|
Two steps away from the county line, |
|
Just tryin’ to keep my customers satisfied… |
|
Paul Simon |
|
|
|
Suppose there are two trays, each containing 4 marbles. We randomly select one of the trays (with equal probabilities), and remove a marble from the selected tray. We repeat this process until we select a tray that has no marbles. At this point, what is the probability that the other tray has exactly 2 marbles? |
|
|
|
This can be treated as a Markov model, with the state of the system corresponding to the numbers of marbles in the two trays, beginning in the state [4,4]. The probabilities for the remaining states can be computed recursively as shown below. |
|
|
|
|
|
|
|
Beginning from the initial state [4,4] in the upper left position of this array, each of the states [4,3] and [3,4] has probability 1/2. In general, the probability of each state (except for the boundary states along the bottom row and right-hand column) equals half the probability of the state above it, plus half the probability of the state to its left. Thus the probabilities satisfy the recurrence |
|
|
|
|
|
|
|
Consequently, the numerators are just the binomial coefficients, and the denominators are consecutive powers of 2. The column and row marked “0” represent the states in which one or both of the trays are empty, but this isn’t the end of the process, because the problem statement stipulates that the process doesn’t end until we have selected an empty tray. For example, in the state [3,0] we have an empty tray, but we haven’t selected an empty tray yet. We have only probability 1/2 of selecting that empty tray on the next step. The row and column marked “–1” signify the states when an empty tray has been selected. Thus from the state [0,3], which has probability 5/32, the probability of selecting the empty tray on the next step is 1/2, so the probability of state [–1,3] is 5/64. There is no contribution from the state [4,–1] because that is a terminating state. Therefore, for the terminating row and column we have P[–1,k] = P[0,k]/2 and P[k,–1] = P[k,0]/2. Note that the sum of the probabilities in this row and column is 1, as required, since every trial must end in one of these conditions. |
|
|
|
From these considerations it follows that, beginning with N marbles on each of two trays, the probability when we select an empty tray of having k marbles on the other tray is P[k,–1] + P[–1,k], which equals |
|
|
|
|
|
|
|
Thus the answer to the original question is |
|
|
|
|
|
|
|
Likewise if we begin with 10 marbles on each tray, the probability when we select an empty tray of having exactly 5 marbles on the remaining tray is |
|
|
|
|
|
|
|
This problem is often confused with the closely related problem of determining the probability of k marbles in the remaining tray when we remove the last marble from one of the trays. For that problem the relevant array (for N = 4) is as shown below |
|
|
|
|
|
|
|
From this we can see that, for this version of the problem, the general answer is |
|
|
|
|
|
|
|
and for the particular case N = 4, k = 2 we have |
|
|
|
|
|
|
|
Likewise with N = 10 and k = 5 the result is |
|
|
|
|
|
|
|
Thus the answers to these two seemingly similar questions (often mistaken for each other) are significantly different. The ratio of the two probabilities is (2N–k)/(2N). |
|
|
