3
$\begingroup$

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?$

$\endgroup$
  • $\begingroup$ 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‌​. $\endgroup$ – user96124 Sep 22 '13 at 16:22
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – user96124 Sep 22 '13 at 4:39
  • $\begingroup$ $\ldots$inserting $1$ in one of $n$ positions. The probability that the insertion point is immediately in front of $2$ is $1/n.$ $\endgroup$ – user96124 Sep 22 '13 at 4:41
  • 1
    $\begingroup$ I have tried only to give the simplest way to see how $1/n$ arises. $\endgroup$ – Benjamin Dickman Sep 25 '13 at 4:23
  • $\begingroup$ 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. $\endgroup$ – user96124 Sep 25 '13 at 12:30
0
$\begingroup$

$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}.$$

$\endgroup$
0
$\begingroup$

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

$\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.