Probability of the $r$th number being smaller than all numbers before it in a uniform permutation of $n$ numbers

Question

Suppose we have an ordered list of $n$ numbers 1 to n, in a random permutation drawn uniformly from all possible permutations.

Let $r$ be one of the $n$ positions in the list. What is the probability all the numbers that come before it $(i.e. 1\ldots r-1$ inclusive) are all less than the number in position $r$?

I'm told this is $\frac{1}{r}$ but I'm not sure why. I tried computing the probability by a counting argument. I count a total of $n!$ permutations. I count that the number of ways that all the numbers that come before it are:

If the value at $r$ equals $r$, then there are $\frac{(r-1)!}{(r-1)!}$ possibilities for entries before $r$, and $(n-r)!$ possibilities for entries after $r$, so $\frac{(r-1)!}{(r-1)!}(n-r)!$ ways.

If the value at $r$ equals $r+1$, then there are $\frac{(r)!}{(r-1)!}$ possibilities for entries before $r$, and $(n-r)!$ possibilities for entries after $r$, so $\frac{r!}{(r-1)!}(n-r)!$ ways.

We continue on in this fashion until $r = n$.

So the probability is $\frac{\frac{(r-1)!}{(r-1)!}(n-r)! + \ldots + \frac{(n-1)!}{(r-1)!}(n-r)!}{n!}$, but this does not seem to simplify to $\frac{1}{r}$.

Where is the mistake?

Answer 1

Let $\mathbf{X} = (X_1,...,X_n)$ denote the random vector you are talking about. Since the elements of this vector are distinct numbers, the event you are describing is equivalent to the event $\max \{ X_1,...,X_r \} = X_r$. Since the random vector is uniform over all permutations, the elements are exchangeable, so we have:

$$\mathbb{P}(\max \{ X_1,...,X_r \} = X_r) = \frac{1}{r}.$$

You can compute this the long way using the permutation argument you are describing if you want to, but your combinatorial algebra for this is wrong. (For starters you need to choose a different variable to describe the value of the $r$th number, so as not to conflate it with the position $r$.) Given the value $X_r = x$ there are $(n-1)_{r-1}$ ways that the previous numbers can be arranged and $(x-1)_{r-1}$ of these satisfy the event requirement (using notation for the falling factorials). Thus, for any $1 \leqslant x \leqslant n$ we have:

$$\mathbb{P}(\max \{ X_1,...,X_r \} = x | X_r = x) = \frac{(x-1)_{r-1}}{(n-1)_{r-1}}.$$

Hence, using the law of total probability we get:

$$\begin{align} \mathbb{P}(\max \{ X_1,...,X_r \} = X_r) &= \sum_{x=1}^n \mathbb{P}(\max \{ X_1,...,X_r \} = X_r | X_r = x) \cdot \mathbb{P}(X_r = x) \\[6pt] &= \sum_{x=r}^n \mathbb{P}(\max \{ X_1,...,X_r \} = x | X_r = x) \cdot \mathbb{P}(X_r = x) \\[6pt] &= \sum_{x=r}^n \frac{(x-1)_{r-1}}{(n-1)_{r-1}} \cdot \frac{1}{n} \\[6pt] &= \frac{1}{(n)_{r}} \sum_{x=r}^n (x-1)_{r-1} \\[6pt] &= \frac{1}{(n)_{r}} \sum_{x=0}^{n-r} (x+r-1)_{r-1} \\[6pt] &= \frac{1}{(n)_{r}} \Bigg[ \frac{(n)_{r}}{r} - \frac{(r-1)_{r}}{r} \Bigg] \\[6pt] &= \frac{1}{r}. \\[6pt] \end{align}$$

(In the penultimate step I have used a summation formula for the falling factorials given here.)

Answer 2

For $1 \le i \le r $, let $p_i$ be the probability that of the first $r$ numbers in the permutation, the largest is in position $i$. By symmetry the $p_i$ are equal so each is equal to $\frac{1}{r}$.

An example of that symmetry: let $A$ be the set of permutations where the first number is the largest among the first 5 numbers, and $B$ be the set of permutations where the second number is the largest among the first 5 numbers. Then swapping the first two numbers of a permutation defines a bijection between $A$ and $B$, showing that the two sets are of equal size.