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?
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.