# Maximum after m tries is the same as maximum after m+1 tries, without replacement

This is a question in a quant interview. Given a bag of $$n$$ marbles each of distinct weights, perform the following process. Pick two marbles at random, keep the heavier one and return the lighter one. Then, repeat the following process. Pick one marble at random from the rest, and compare it to the marble at hand. Keep the heavier one and return the lighter one to the bag. What is the probability that the marble you have in your hand after $$m$$ turns will remain in your hand after $$m+1$$ turns (one more turn)?

My thinking: It seems conditioning on the mth marble seems the way to go, since it is not true that all marbles have equal probability of being that maximum weight marble after m turns. Let $$W_{k}$$ be the marble in your hand after $$k$$ marbles have been drawn. So we have

$$\mathbb{P} \left[W_{m} = W_{m+1}\right] = \sum_{i=2}^{n}\mathbb{P}[W_{m+1} = W_{m} \mid W_m = i] \mathbb{P}[W_m=i]$$ These individual probabilities are easy to calculate. The conditional probability is just $$\frac{i-1}{n-1}$$, while $$\mathbb{P}[W_m = i] = \mathbb{P}[W_m \leq i] - \mathbb{P}[W_m \leq i-1] = \frac{i}{n} \cdot \left(\frac{i-1}{n-1}\right)^{m-1} - \frac{i-1}{n} \cdot \left(\frac{i-2}{n-1}\right)^{m-1}$$ as we condition on each turn and then we are only allowed to choose among $$i-1$$ of the remaining marbles each time to ensure the maximum weight is at most $$i$$.

This gives the answer as the sum $$\sum_{i=2}^{n} \frac{i-1}{n-1} \left(\frac{i}{n} \left(\frac{i-1}{n-1}\right)^{m-1} - \frac{i-1}{n} \left(\frac{i-2}{n-1}\right)^{m-1}\right)$$ However, I don't really see any way to simplify this sum. If I didn't have the $$\frac{i-1}{n-1}$$ term in front, this would be a telescoping series, but with that term I don't see how to break it up cleanly.

Is my approach right? If so, can you please help me simplify this sum. Otherwise, am I missing some simple symmetry or something that would make this problem much easier?

• The question states distinct weights, they don't mention anything about the weights being $1,...,n$ right? Commented Feb 14 at 22:00
• @LevieB Since only relative weights matter, you may as well assume them to be $1,\ldots, n$, but I haven't really assumed that these are the weights above. Commented Feb 14 at 22:01
• You do seem to implicitly use it in your sum as you sum from 2 to $n$. Therefore assuming you cannot condition on the lightest one. Commented Feb 14 at 22:07
• Ah yeah, I use it when I say $W_{m} = i$, but you can take this as short for $W_m = w_i$, where $w_i$ is the ith smallest. Commented Feb 14 at 22:18

Consider the sequence of $$m+2$$ extracted marbles (due to the nature of the first turn where you extract $$2$$ marbles, this only counts as $$m+1$$ turns). The maximum value is (uniquely) attained at the $$k$$th marble in the sequence. The $$m+1$$th kept marble ($$m$$th turn) will be different from the $$m+2$$th kept marble ($$m+1$$th turn) if and only if the maximum is attained at the last ($$m+2$$th) marble of the sequence, ie. $$k = m+2$$. The probability of maintaining the same marble is aproximately $$1-\frac{1}{m+2}$$.

Edit: the above formula is only a heuristic approximation which holds as $$n \rightarrow \infty$$. However, we can use the outlined method to compute the exact formula.

Let us count the valid sequences of $$m+2$$ marbles where the maximum is equal to $$k$$ and occurs at the last marble. We get:

$$\frac{k-1}{n}\left( \frac{k-2}{n-1} \right)^m \frac{1}{n-1}$$

This is by counting the valid possibilities for the first marble, middle $$m$$ marbles, and last marble.

By summing over possible $$k$$ we get the probability that the maximum marble is the last. Its complement is the desired probability. This gives:

$$p = 1 - \left(\frac{1}{n-1}\right)\left(\sum_{k=1}^{n}\frac{k-1}{n}\left(\frac{k-2}{n-1}\right)^m\right)$$

This explicit sum works for any $$n$$ and $$m$$. As $$n$$ goes to infinity, we can approximate it as:

$$p \approx 1 - \left(\frac{1}{n-1}\right)\left(\sum_{k=1}^{n}\left(\frac{k-2}{n-1}\right)^{m+1}\right) \approx \\ \approx 1 - \int_{0}^{1}{x^{m+1}\,dx} = 1 - \frac{1}{m+2}$$

recovering our initial guess.

• How do you compute this last probability, that $k=m+2$? Commented Feb 14 at 23:34
• @LevieB I've added an edit that explains this answer, which should show up once it is approved by community members Commented Feb 14 at 23:50
• It was more of a heuristic guess. Unfortunately, it turns out to be wrong, as it fails for $n = 2$ Commented Feb 14 at 23:55
• No, it is right. I have simulated it as well. Take a look at my suggested edit for the explanation math.stackexchange.com/review/suggested-edits/2077963 Commented Feb 14 at 23:57
• I've edited my answer to include its derivation. Commented Feb 15 at 0:53

Your calculation of $$\Pr[W_{m+1} = W_m \mid W_m = i]$$ is correct, but $$\Pr[W_m = i]$$ is not. To see why, note that after the first draw ($$m = 1$$), your formula would have $$\Pr[W_1 = i] = \frac{1}{n}$$ which is discrete uniform on the ranks of the marbles' weights. But this cannot be true: the first marble can never be the lightest, because two marbles were initially drawn and the heavier of the two is taken. Neither can the first marble be in general equally likely to be any of the $$n-1$$ marbles $$\{2, 3, \ldots, n\}$$. Of the $$\binom{n}{2}$$ pairs of distinct marbles on the first draw, the number of outcomes with $$W_1 = i$$ is $$i-1$$, thus $$\Pr[W_1 = i] = \frac{i-1}{\binom{n}{2}}, \quad i \in \{2, 3, \ldots, n\}.$$

In light of this, you may want to revise your work before proceeding further.

• Apologies for being unclear, but the first draw is just one marble. That is why in the first draw any of them can be the maximum when you have only picked the first marble. Your answer $\frac{i-1}{n}$ is actually what my formula gives for $m = 2$, correctly. And, the answer for $m = 1$ being uniform is correct as well, with my interpretation. Commented Feb 14 at 22:16
• @I_cosine_this You specifically stated in your question that you start by picking two marbles at random, keep the heavier one, and return the lighter one. This would suggest $W_1 > 1$. You should either reword your question or change how you define $W_k$. Commented Feb 14 at 22:18
• Wouldn't it be $P[𝑊_1=𝑖]=(i-1)/{n \choose 2}$? Commented Feb 14 at 22:21
• @heropup Yes, and that happens on turn 2 i.e when you pick the second marble. Whether you call this turn 2 or turn 1 really just changes the notation by 1, so i dont think its quite important Commented Feb 14 at 22:21
• Ok, I have changed W_k to marbles drawn, as I feel it makes the notation a bit simpler. @LevieB yes, it should be $\binom{n}{2}$ in the denominator. Commented Feb 14 at 22:29