Skip to main content

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

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?