Timeline for Random Permutation with fixed cycle length.
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 15, 2012 at 7:08 | comment | added | Brendan McKay | @gmath: Sorry, I meant for odd cycles. It shouldn't be too hard since the generating function is simple. I think $\sum Q_{n,N} x^n y^N/n! = ((1+x)/(1-x))^{y/2}$ where $Q_{n,N}$ is the number of permutations with $N$ odd cycles. | |
| May 15, 2012 at 6:33 | comment | added | gmath | @Brendan: Yes those are exactly what is known as stirling numbers of the first kind but I couldn't find anything for odd length cycles. Finding the asymptotics for odd length cycle is possible from whats known but its very very complicated (at least via the method I thought). I am trying to see of there is a softer argument. | |
| May 15, 2012 at 4:21 | comment | added | Brendan McKay | Do you know the asymptotic size of $S_{n,N}$? I'm pretty sure that will provide a good estimate for what you ask. | |
| May 15, 2012 at 1:16 | history | edited | gmath |
edited tags
|
|
| May 15, 2012 at 1:01 | comment | added | gmath | @Douglas: I was thinking in the same lines but couldnt find a proof. Could you be more specific? How are the measures same? thanks. | |
| May 15, 2012 at 1:00 | comment | added | gmath | @Aaron: I want to show after fixing the proportionality constant that for large enough $n$ the probability that the largest cycle is greater than $C$ goes to zero uniformly in $n$. | |
| May 15, 2012 at 0:56 | comment | added | gmath | @John Jiang: Here is the result with no restriction on cycle lengths: degruyter.com/view/j/dma.2003.13.issue-5/156939203322694781/… For the even lengths here is an argument: Note we want probability of an event depending only on the cycle type. I consider a map from $S_{n/2,N}$ to "$S_{n,N}$ with even cycle lengths" which sends a cycle type (k_1,...k_N) to (2k_1, ... 2k_n). The map is measure preserving (one can check) if we consider uniform measure on the range. Hence the result follows from the results about uniform measure on $S_{n,N}$. | |
| May 15, 2012 at 0:55 | comment | added | gmath | @Brendan: Yes you are right. $S_{n,N}$ is the set of permutations of a set of $n$ elements with $N$ cycles. Sorry for being sloppy. | |
| May 14, 2012 at 14:49 | comment | added | Douglas Zare | Although I don't see all of the details, the result for odd cycles should follow from the result for even cycles by combining pairs of cycles of odd length into cycles of even length. | |
| May 14, 2012 at 6:10 | comment | added | Aaron Meyerowitz | Do you mean that fixing the constant of proportionality between $n$ and $N$ and letting $n$ grow, there is a size $C$ so that with probability approaching $1$ the longest cycle is shorter than $C$ (or $C \log{n}$ or something like that?) Be more specific please. | |
| May 14, 2012 at 5:25 | comment | added | John Jiang | @gmath: It would also be nice to have the references of the two results you mentioned. | |
| May 14, 2012 at 3:05 | comment | added | Brendan McKay | Please edit your question to clarify it. Is $S$ a "set of $n$ elements" as you say, or a set of permutations of $n$ elements? And should "with $N$ many cycles" be "with $N$ cycles"? | |
| May 14, 2012 at 2:59 | history | asked | gmath | CC BY-SA 3.0 |