Comparing Maxima of Two Halves of a Random Permutation

Probability · Medium · Free problem

A random permutation of $\{1, 2, \ldots, 12\}$ is revealed one element at a time from left to right. Define two groups: the first half (positions 1--6) and the second half (positions 7--12). Let $A$ be the event that the maximum among the first 6 revealed values is strictly larger than the maximum among the last 6 values.

  1. Compute $P(A)$.
  1. Conditional on the overall maximum (the value 12) landing in the first half, compute $P(A \mid 12 \text{ is in the first 6 positions})$.
  1. Generalize your results to a random permutation of $\{1, 2, \ldots, 2n\}$ split into two halves of size $n$.

Hints

  1. All 12 values are distinct, so the two half-maxima can never be equal. What does that tell you about the number of cases?
  2. Think about which half the overall maximum element (12) lands in. By symmetry of the uniform permutation, what is the probability it falls in the first half?
  3. The event $A$ occurs if and only if the largest element is in the first half. Once you see this, parts (a), (b), and (c) all follow immediately.

Worked Solution

How to Think About It: Before doing any counting, think about what determines the event $A$. The only thing that matters is which half gets the overall maximum element. Since the permutation is uniform, every element is equally likely to land in any position. The values are all distinct, so the two half-maxima can never tie. This means the problem collapses to a single coin flip: which half gets the biggest number?

Quick Estimate: By symmetry, the maximum element 12 is equally likely to be in the first half or the second half. If 12 is in the first half, then $\max(\text{first 6}) = 12 > \max(\text{last 6})$, so $A$ occurs. If 12 is in the second half, then $\max(\text{last 6}) = 12 > \max(\text{first 6})$, so $A$ does not occur. So $P(A)$ should be exactly

/2$. Parts (b) and (c) should follow immediately from the same reasoning.

Approach: Use a symmetry argument for part (a), direct reasoning for part (b), and then note that nothing in the argument depends on $n = 6$.

Formal Solution:

Part (a): In a uniformly random permutation of $\{1, 2, \ldots, 12\}$, all 12 values are distinct. Define $M_1 = \max(\text{first 6})$ and $M_2 = \max(\text{last 6})$. Since all values are distinct, exactly one of $M_1 > M_2$ or $M_1 < M_2$ holds (no ties are possible).

Consider the bijection that swaps positions $i \leftrightarrow i + 6$ for $i = 1, \ldots, 6$. This maps each permutation to another permutation with equal probability, and it exchanges the first and second halves. Under this map, $M_1 > M_2$ becomes $M_2 > M_1$ and vice versa. Therefore:

$P(M_1 > M_2) = P(M_2 > M_1)$

Since these are the only two possibilities:

$P(A) = P(M_1 > M_2) = \frac{1}{2}$

Alternative argument: The event $A$ occurs if and only if the overall maximum, 12, lands in the first half. Since each of the 12 positions is equally likely to receive the value 12, the probability that 12 is in positions 1--6 is $6/12 = 1/2$.

Part (b): If 12 is in the first half, then $M_1 \geq 12$, so $M_1 = 12$. The second half contains only values from $\{1, \ldots, 11\}$, so $M_2 \leq 11 < 12 = M_1$. Therefore:

$P(A \mid 12 \text{ in first 6}) = 1$

This is immediate: once you know the largest element is in the first half, the first half's maximum is guaranteed to be larger.

Part (c): For a random permutation of $\{1, 2, \ldots, 2n\}$ split into a first half of size $n$ and a second half of size $n$, the identical symmetry argument gives:

$P(A) = \frac{1}{2}$

for all $n \geq 1$. The value

n$ lands in the first half with probability $n/(2n) = 1/2$, and whenever it does, $A$ occurs; whenever it does not, $A$ fails.

Similarly:

$P(A \mid 2n \text{ in first } n \text{ positions}) = 1$

$P(A \mid 2n \text{ in last } n \text{ positions}) = 0$

This is a special case of the law of total probability check: $P(A) = 1 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2} = \frac{1}{2}$.

Answer: (a) $P(A) = \dfrac{1}{2}$. (b) $P(A \mid 12 \text{ in first 6}) = 1$. (c) For n$ elements, $P(A) = \dfrac{1}{2}$ and $P(A \mid 2n \text{ in first half}) = 1$ for all $n \geq 1$.

Intuition

The key insight is that comparing the maxima of two groups drawn from distinct values reduces entirely to asking one question: which group got the overall maximum? Everything else is irrelevant. It does not matter how the remaining 11 elements are distributed, or what the second-largest value is, or how the elements within each half are ordered. The maximum dominates everything.

This is a pattern that comes up constantly in order-statistics problems on interviews: before you start counting arrangements or summing over cases, ask yourself whether there is a single element (usually the max or min) whose placement determines the entire event. If so, the problem collapses from a complicated combinatorial question to a trivial one. Many candidates lose time trying to compute $\binom{12}{6}$ ratios when the answer is just

/2$ by symmetry. The ability to spot these shortcuts quickly is exactly what interviewers are testing.

Open the full interactive solver →