Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: mathematics

Topic: permutations with a single 2-cycle

John Baez (Dec 08 2024 at 23:50):

A correspondent writes:

Subject: Random Permutations (Secret Santa)

My office Secret Santa this year contained a 2-cycle, which I thought must occur with low probability given the large number of people involved.

I enjoyed reading your series on random permutations and was wondering if you know the answer to the following:

What is the probability that a random permutation in $S_n$ contains exactly one 2-cycle?

I reread my series and figured it out. Does anyone want to try?

John Baez (Dec 08 2024 at 23:56):

I think the best way to try this is to just guess at first. What do you intuitively think happens to the probability as $n \to +\infty$ ? Does it approach $1$ , $0$ , something else...?

John Baez (Dec 08 2024 at 23:56):

@Sridhar Ramesh is not allowed to do this puzzle until other people have tried it. :wink:

Riley Shahar (Dec 09 2024 at 01:58):

John Baez said:

A correspondent writes:

Subject: Random Permutations (Secret Santa)

My office Secret Santa this year contained a 2-cycle, which I thought must occur with low probability given the large number of people involved.

I enjoyed reading your series on random permutations and was wondering if you know the answer to the following:

What is the probability that a random permutation in $S_n$ contains exactly one 2-cycle?

I reread my series and figured it out. Does anyone want to try?

Fun puzzle, thank you for sharing! I solved this generatingfunctionologically, which was nice because I really enjoy generating functions but don't have a lot of opportunity to play with them. I'm happy to share that solution if you/anyone is interested, but I sort of assume you had a more creative solution in mind? (Although I haven't read your series, so I don't know what techniques you're using.)

Anyway, here is an answer, which agrees with the right answer at least for $n \leq 5$ :

If you confirm you had something else in mind, I will probably spend some time looking for it. I guess regardless it would be fun to see if I can find a direct combinatorial justification for this... feels very strongly like

which makes sense.

John Baez (Dec 09 2024 at 02:02):

Is your answer really a probability between $0$ and $1$ ? It seems to approach $+\infty$ as $n \to +\infty$ . Am I confused?

Riley Shahar (Dec 09 2024 at 02:02):

John Baez said:

Is your answer really a probability between $0$ and $1$ ? It seems to approach $+\infty$ as $n \to +\infty$ . Am I confused?

Oh, it needs to be divided by $n!$ then. I was counting the number of such permutations.

Riley Shahar (Dec 09 2024 at 02:02):

Sorry, totally read the question wrong

Riley Shahar (Dec 09 2024 at 02:03):

(funnily enough, I just multiplied by $n!$ at the end to get this answer... so I really ended up solving the question you actually asked.)

John Baez (Dec 09 2024 at 02:06):

Neat. Okay, then I think we may I agree. I used a method that only gave me the limit of your (corrected) answer as $n \to +\infty$ , since my correspondent mentioned "the large number of people involved." And this limit was

Riley Shahar (Dec 09 2024 at 02:08):

John Baez said:

Neat. Okay, then I think we may I agree. I used a method that only gave me the limit of your (corrected) answer as $n \to +\infty$ , since my correspondent mentioned "the large number of people involved." And this limit was

Cool! I don't really know what tools exist to extract limiting behavior from generating functions... let me try to figure it out. (You could also just take the limit of my closed form, but it's probably more fun/reproducible to do it from the generating function.)

John Baez (Dec 09 2024 at 02:10):

Well, I think it's pretty easy to take your formula, and then take the $n \to \infty$ limit of that, and see why it (almost) matches the answer in my spoiler.

Riley Shahar (Dec 09 2024 at 02:12):

John Baez said:

Well, I think it's pretty easy to take your formula, and then take the $n \to \infty$ limit of that, and see why it (almost) matches the answer in my spoiler.

Yeah but I know how to take limits already, it's more fun for me to see how to do it from the generating function. Because I imagine there are times when it's hard to extract a closed form from a generating function, but easier to compute the limit. That's certainly the case with lots of other statistics of sequences

John Baez (Dec 09 2024 at 02:12):

Okay. There's bunch of amazing stuff about the $n \to \infty$ limits of this and related problems, which I learned about while studying this material. I explain it starting here.

John Baez (Dec 09 2024 at 02:13):

One example of how cool this stuff is. The following two are equal:

The probability that N raindrops land on your head in a minute, if on average one lands on your head every k minutes.
The probability that a random permutation of a huge finite set has N cycles of length k.

John Baez (Dec 09 2024 at 02:14):

Here 'huge' means I'm taking the $n \to \infty$ limit we're discussing now, and I'm assuming the raindrops are described by a Poisson process (the simplest sort of random behavior one could expect here).

Riley Shahar (Dec 09 2024 at 02:16):

John Baez said:

One example of how cool this stuff is. The following two are equal:

The probability that N raindrops land on your head in a minute, if on average one lands on your head every k minutes.

The probability that a random permutation of a huge finite set has N cycles of length k.

wow, this is very cool

John Baez (Dec 09 2024 at 02:17):

By the way, my explanations were not as simple as they could probably become. I was just learning stuff and making stuff up as I went. I should polish this stuff some more.

Riley Shahar (Dec 09 2024 at 02:50):

Ok, there are definitely techniques for computing limits directly from the generating function. Applying them, I get the limit

which is also what I get just from computing the limit of the closed form above, but I'm glad I did it the long way.

Actually, it turns out Wilf introduces these techniques in the context of answering questions of the form "what is the probability a permutation has X?" And there is an extremely general theorem in Wilf (4.7.3) which answers all questions of the form "given some sequences $c_i$ and $k_i$ , with the $k_i$ ascending so that $\sum_i 1/{k_i}$ converges, what is the probability that a random permutation has $c_i$ $k_i$ -cycles for each $i$ ?" I.e., as long as you care about a sufficiently sparse set of cycle lengths there is a closed form for the probability. Maybe this theorem is in your posts, but regardless it's very fun-looking stuff.

John Baez (Dec 09 2024 at 02:56):

For anyone who wants the answer on a silver platter, here is a less cryptic spoiler that gives it all away:

According to @Riley Shahar the probability that a randomly chosen permutation of an $n$ -element set has exactly one 2-cycle is

$\displaystyle{ \frac{1}{2} \sum_{i = 0}^{\lfloor n/2 \rfloor - 1} \frac{(-1)^i}{i!2^i} }$

Taking the limit as $n \to \infty$ we get

$\displaystyle{ \frac{1}{2} \sum_{i = 0}^\infty \frac{(-1)^i}{i!2^i} = \frac{1}{2} e^{-1/2} \approx 0.30326532985\dots }$

which agrees with my own calculations: in the $n \to \infty$ limit, the probability that a randomly chosen permutation of an $n$ -element set has exactly $k$ $N$ -cycles is

$\displaystyle{ \frac{e^{-1/N}}{N^k k!} }$

John Baez (Dec 09 2024 at 03:04):

Riley Shahar said:

Actually, it turns out Wilf introduces these techniques in the context of answering questions of the form "what is the probability a permutation has X?" And there is an extremely general theorem in Wilf (4.7.3) which answers all questions of the form "given some sequences $c_i$ and $k_i$ , with the $k_i$ ascending so that $\sum_i 1/{k_i}$ converges, what is the probability that a random permutation has $c_i$ $k_i$ -cycles for each $i$ ?" I.e., as long as you care about a sufficiently sparse set of cycle lengths there is a closed form for the probability. Maybe this theorem is in your posts, but regardless it's very fun-looking stuff.

It's funny that I hadn't seen that in Wilf - thanks! It feels related to the Cycle Length Lemma that I discussed in Part 11 of my series. It may secretly be the same thing. The Cycle Length Lemma is a recipe for calculating the expected value of a product of falling powers of the numbers of cycles of length $k$ for some chosen set of numbers $k$ , assuming $n$ is big enough (but it can be finite).

John Baez (Dec 09 2024 at 03:05):

I gave a "categorified" proof of this already known lemma, expressing it as an equivalence of groupoids.

Riley Shahar (Dec 09 2024 at 03:07):

Cool! Definitely adding this series to my list of hopefully-not-too-difficult math things to read :)

John Baez (Dec 09 2024 at 03:47):

It would not be difficult if I'd explained it well... not sure I managed that.