5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Suppose you have $r$ unique numbers. Then the maximum of those numbers is unique, i.e. there is $1$ maximum and $r$ options. Therefore picking a number uniformly at random, you have a $1/r$ chance of picking the maximum. The probability of any of the numbers ending up in any given spot (including the $r$-th spot) is the same, i.e. uniform, so picking the last ($r$-th) slot is the same as picking a number uniformly at. $\endgroup$
    – Oxonon
    Dec 17 '20 at 7:54
  • $\begingroup$ Hi jh1001, this is a well written question, welcome to Stats SE! $\endgroup$
    – Fato39
    Dec 17 '20 at 10:17
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for this answer. I'm still confused as to why my answer was wrong. Is it not true for example, that if the value at $r$ equals $r+1$, then there are a total of $\frac{r!}{(r-1)!}(n-r)!$ ways for this to happen while satisfying the condition that the value at $r$ is smaller than all values preceding it? $\endgroup$
    – jh1001
    Dec 18 '20 at 10:52
  • $\begingroup$ If $n = 10, r=3$, and suppose the numbers were from 1 to 10, and the value at slot 3 was 4. Then you have to fill the first two slots, and you have to pick 2 values from 1, 2, or 3, which is, using the permutation function, 3 permute 2, which is $\frac{r!}{(r-1)!}$. Then you have free choice over the last 7 slots, and you have 7 numbers to choose from, namely 4, 5, ..., 10 so it would be $7!$. This is the formula I wrote above. If I do this for all values of $r$, wouldn't it be the total ways that the desired condition can be satisfied? $\endgroup$
    – jh1001
    Dec 18 '20 at 10:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.