1
$\begingroup$

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. enter image description here

$\endgroup$
  • $\begingroup$ In your example, I don't understand what you mean by $X_4 = 1$. $1\to 2 \to 3 \to 1 \to 2$, yes? $\endgroup$ – Chas Brown Oct 13 '16 at 9:30
  • $\begingroup$ I don't understand your example. In the permutation $\{3,2,1,4\}$ isn't $2$ fixed? $\endgroup$ – lulu Oct 13 '16 at 11:14
  • $\begingroup$ 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)? $\endgroup$ – lulu Oct 13 '16 at 11:32
  • $\begingroup$ A useful page: en.wikipedia.org/wiki/Random_permutation_statistics $\endgroup$ – Jack D'Aurizio Oct 13 '16 at 11:56
  • $\begingroup$ @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). $\endgroup$ – cap Oct 13 '16 at 15:36
3
+50
$\begingroup$

Here is one way of understanding this result.

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

$\endgroup$
  • $\begingroup$ I don't quite understand your example. Where are the brackets in your example? How did you decompose into those cycles? $\endgroup$ – cap Oct 19 '16 at 6:26
  • $\begingroup$ 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. $\endgroup$ – user940 Oct 19 '16 at 12:40
  • $\begingroup$ 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. $\endgroup$ – user940 Oct 19 '16 at 12:43

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.