# Probability that a cycle of a permutation ends at $k$th step

Given a permutation of $1,\ldots,n$ we can decompose it into cycles (e.g., the permutation $(3,2,1,4)$ has cycles $1\to 3\to 1, 2\to 2, 4\to 4$). Let's use the convention that the first cycle starts with $1$.

Let $X_k=1$ if a cycle ends at the $k$th step and $0$ otherwise (so that in the above example, $X_1=0,X_2=X_3=X_4=1).$ I want to show $$P(X_k=1)=\frac{1}{n-k+1}$$

I am having difficulty since I don't know how many different ways one of the cycles can end at the $k$th step. If $k=2,$ we have either a cycle (a) $1\to a\to 1$ or (b) two cycles $1\to 1,a\to a$. So the probability that $P(X_2=1)$ should be the sum that we are in one of these disjoint cases. The probability of (a) is $\frac{(n-1)(n-2)!}{n!}=\frac{1}{n}$ since there are $n-1$ choices for $a$ and $(n-2)!$ ways to permute the remaining $n-2$ elements other than $1,a$; and the probability of (b) is $\frac{(n-1)(n-2)!}{n!}=\frac{1}{n}$ since there are $(n-1)(n-2)!$ permutations fixing $1,a\not=1$.

This cannot be correct since the sum is $2/n$ while the formula says it's $\frac{1}{n-2+1}=\frac{1}{n-1}$. How can this be proved (for any $k$)?

Attached is the original source of the problem, #12 of Feller'Probability.

• In your example, I don't understand what you mean by $X_4 = 1$. $1\to 2 \to 3 \to 1 \to 2$, yes? – Chas Brown Oct 13 '16 at 9:30
• I don't understand your example. In the permutation $\{3,2,1,4\}$ isn't $2$ fixed? – lulu Oct 13 '16 at 11:14
• Nor do I understand the desired formula for $P(X_2=1)$. As you say, there are two ways a cycle might end in $2$. Either $2$ is fixed (probability $\frac 1n$) or $2\to 1$ (also probability $\frac 1n$). So I see the answer as $\frac 2n$. Am I misreading (or miscalculating)? – lulu Oct 13 '16 at 11:32
• A useful page: en.wikipedia.org/wiki/Random_permutation_statistics – Jack D'Aurizio Oct 13 '16 at 11:56
• @Chas Brown. By $X_4=1$ I mean that one of the cycles ends at the 4th step. Namely the last cycle which sends 4 to 4 is the 4th step in the cycle decomposition. I edited the question. By $1 \to 2 \to 1$, I mean that one is sent to the original position that 2 was in and that 2 is sent to the position that 1 was originally in (so 1 and 2 are swapped). – cap Oct 13 '16 at 15:36

Define a bijection $\Phi:\Omega_n\to\Omega_n$ on the set $\Omega_n$ of permutations. For a permutation $x= x_1 x_2\dots x_n$, move from right to left inserting a right bracket after every $x_k$ where $x_k=\inf\{x_k,x_{k+1},\dots, x_n\}$. Fill in left brackets where necessary. This is the cycle structure of a new permuation $\Phi(x).$
For example, if $x = 361975284$ then we get the cycle structure $(361)(9752)(84)$ which gives $\Phi(x)=396821547$. We adopt the convention that the smallest element in each cycle is written last, and that the cycles are ordered by smallest element.
Since $\Phi$ is a bijection, if $Y$ is uniformly distributed on $\Omega_n$ then so is $X=\Phi^{-1}(Y)$. The chance that a randomly selected permutation $Y$ will have a cycle completed at the $k$th step is the chance that $X_k=\inf\{X_k,X_{k+1},\dots, X_n\}$, that is, ${1\over n-k+1}$.
• Start at the end of $361975284$ and put a right bracket whenever the value is a "record low". We first meet the number $4$. Is this a record low? Yes, so we insert a right bracket, giving $361975284)$. We move one step to the left and meet $8$. Is this a record low? No, so no bracket. We move one step to the left and meet $2$. Is this a record low? Yes, so insert a right bracket, giving $3619752)84)$. We move one step to the left and meet $5$. Is this a record low? No, so no bracket. We move one step to the left and meet $7$. Is this a record low? No, so no bracket. – user940 Oct 19 '16 at 12:40
• We move one step to the left and meet $9$. Is this a record low? No, so no bracket. We move one step to the left and meet $1$. Is this a record low? Yes, so insert a right bracket, giving $361)9752)84)$. Since $1$ is the smallest value over all we will not meet any more record lows: the final result is $361)9752)84).$ Fill in with left brackets where necessary to arrive at the result $(361)(9752)(84).$ This is a cycle decompostion. – user940 Oct 19 '16 at 12:43