# Direct proof that Pr[2 immediately follows 1] in a random permutation is 1/n

The probability that $1$ is a fixed point of a random permutation of $\{1,2,\ldots,n\}$ (with uniform distribution) is $1/n.$ This is easy to prove since there are $(n-1)!$ permutations that have $1$ as a fixed point and $(n-1)!\,/\,n!=1/n.$ A more direct proof is simply to observe that the image of $1$ under a random permutation is equally likely to be any of the $n$ elements of $\{1,2,\ldots,n\}.$

The probability that $2$ immediately follows $1$ in a random permutation is also $1/n,$ and there is a proof similar to the first proof above in that it involves the computation $(n-1)!\,/\,n!=1/n.$ In a permutation $\pi_1\pi_2\ldots\pi_n$ such that $\pi_i\pi_{i+1}=12$ there are $n-1$ possible values of $i$ and there are $(n-2)!$ ways to permute $\{3,4,\ldots,n\}$ among the remaining $n-2$ positions. Hence there are $(n-1)!$ permutations in which $2$ immediately follows $1.$ Perhaps simpler is to observe that there are $(n-1)!$ permutations of $\{12,3,4,\ldots,n\},$ where $12$ is regarded as a single object.

My question: is there a direct way of seeing this, similar to the direct way of seeing that the probability that $1$ is a fixed point is $1/n?$

• That the probability of 1 immediately preceding 2 equals that of 1 being a fixed point is a special case of a more general phenomenon. See the question asked here and here‌​. – user96124 Sep 22 '13 at 16:22

You need to ensure the last element in the $n$-element permutation is not $1$, since that would mean it has no immediate successor. The chance of this occurring is $(n-1)/n$.

In a scenario for which $1$ appears among the first $n-1$ entries, there are still $n-1$ elements left that could follow it, viz., $2, \ldots, n$. The probability in a given scenario that $2$ is the immediate successor, then, is $1/(n-1)$.

Then the probability in question is $\frac{n-1}{n} \cdot \frac{1}{n-1} = \frac{1}{n}$ as desired. QED

• This proof certainly avoids taking the quotient of two humongous numbers, which I think is aesthetically desirable. It seems that you and Dilip Sarwate had a very similar idea. I think one can perhaps avoid separate treatment of $1$ last versus $1$ among the first $n-1$ entries as follows. The permutations of $\{1,2,\ldots,n\}$ correspond in an obvious way to the permutations of $\{1,2,\ldots,n+1\}$ with $n+1$ fixed. Now consider the permutations of $\{2,3,\ldots,n+1\}$ with $n+1$ fixed. From such a permutation, a permutation of $\{1,2,\ldots,n+1\}$ with $n+1$ fixed is formed by$\ldots$ – user96124 Sep 22 '13 at 4:39
• $\ldots$inserting $1$ in one of $n$ positions. The probability that the insertion point is immediately in front of $2$ is $1/n.$ – user96124 Sep 22 '13 at 4:41
• I have tried only to give the simplest way to see how $1/n$ arises. – Benjamin Dickman Sep 25 '13 at 4:23
• I realize I should have been clearer about what I meant by "direct". In the proof that Pr$[1$ is a fixed point$]=1/n,$ there are $n$ images of $1,$ all of them equally likely. I'm looking for proofs of Pr$[1$ immediately precedes $2]=1/n$ that are similar in this regard: there are $n$ things that can happen, all of them equally likely. – user96124 Sep 25 '13 at 12:30

$1$ is equally likely to be in any of the $n$ positions in the permutation. If it is in the first $n-1$ positions (total probability $\frac{n-1}{n}$), then it is equally likely to be followed by any of the other $n-1$ symbols, and so the probability that it is followed by $2$ is $\frac{n-1}{n}\times \frac{1}{n-1} = \frac{1}{n}$. If $1$ is in the $n$-th position, it cannot be followed by anything. So, $$P\{1~\text{is followed by}~2\} = \frac{1}{n}.$$

An improved version of the observation in the comments to Benjamin Dickman's answer:

There is a $1$-to-$n$ map from the set of permutations of $\{2,3,\ldots,n\}$ to the set of permutations of $\{1,2,\ldots,n\}$ obtained by inserting $1$ in any of $n$ possible positions. Taking $n=4,$ we have, for example, $$243\mapsto\{1243,2143,2413,2431\}.$$ The probability that the insertion point is immediately in front of $2$ is $1/n.$