Duc M. Nguyen

Duc M. Nguyen

Master's student at GSAI, POSTECH. Research interests: NLP, RL, AI4Math, and Viz.

How Many Cycles Does a Random Permutation Have? (Part 1)

12 minute read

Published:

A few days ago, I was doom-scrolling on Instagram and came across a post that shared an interview problem of a quant firm: “Let $C_n$ denote the number of cycles in a random permutation of $[2n] = \{1,2,\ldots,2n\}$ whose lengths are greater than $n$. What is $\lim_{n \to \infty} \mathbb{E}[C_n]$?”. It caught my attention almost immediately, since permutation problems were among my favorites back when I did competitive programming. “This should be quite easy for me,” I said to myself, and started doing some calculations. Oh boy. It opened up a whole rabbit hole, leading me to a bunch of related questions, and a few interesting findings of my own, that ended up consuming most of my weekend.

The boredom of vibe coding

Well, this section is totally unrelated to the problem, but it is the background that led me to it.

The rise of vibe coding

Nowadays, the term vibe coding is everywhere. Wherever I go, I see people sharing their vibe-coded projects, bragging about how easy coding is. As a programmer, this made me feel somewhat irritated. I mean, coding was not easy (well, pre-LLM era). I still remember the days when I was implementing a skip list from scratch, and I had to spend hours debugging a single line of code. I remember implementing my first proper website and had to spend hours debugging and scrolling through StackOverflow. It was hard, but I loved it. There was something deeply satisfying about finally getting my own code to work, or solving a problem I had been stuck on for hours.

That’s why I was so annoyed when I saw people claiming coding was easy. I felt like they were trivializing the efforts and skills that went into programming. It made me feel like my own struggles and achievements were being diminished. It even made me question the value of my bachelor’s degree in computer science. I started to wonder if I had wasted my time learning to code, when it seemed like anyone could do it now. I felt like I was being left behind, and that my skills learnt during my studies were no longer relevant.

Vibe coding is not that bad?

I had that feeling for a while, until quite recently, when I had to do an implementation-heavy project for my research, which I was not particularly interested in. I realized that vibe coding is not necessarily a bad thing. I used Codex to generate the frontend code for my project, and it saved me a lot of time and effort. I was amazed at how quickly I was able to prototype my ideas, and I can focus on the research aspects of the project, rather than getting bogged down in the details of coding. This reminded me of my first participation in a research project during my undergradudate studies, where I had to implement a complicated UI and optimizing algorithms. I spent weeks trying to get the code to work, leaving me with little time to actually do any research. It was a frustrating experience, but finally getting it to work was satisfying nonetheless. Now with vibe coding, I was able to get the same results in a fraction of the time. It made me realize that vibe coding can be a useful tool for programmers, especially when it comes to prototyping, and doing repetitive or time-consuming tasks.

While it is true that modern LLMs can efficiently generate functional code, they are not perfect. They sometimes make small but critical mistakes, especially when you are solving a problem that no one has done before. I need to extract texts and formalize them into actionable knowledge base. The pipeline that Codex cooked up for me was not perfect at the first try. I had to spend time looking through the generated code, reading the outputs, and identify the bottlenecks, and iteratively improve the pipeline. It was a bit frustrating, but I realized that this is where my skills as a programmer came in handy. I was able to identify the issues and fix them, which made me feel like I was still relevant in the age of vibe coding. Nevertheless, Codex still saved me a lot of time and effort, where I just need to identify the issues and ask it to fix them, instead of writing the code from scratch. It was a good balance between human-AI collaboration, and I felt like I was able to leverage my skills as a programmer to get the best results.

Ok, nice story, but what does it have to do with the problem?

Well, I was vibe coding the UI for that project, and just seeing Codex generating the code is incredibly boring. I was just staring at the screen, looking at the “thoughts” and the “actions” of GPT. While vibe coding saves me time and lets me focus on other research tasks, there are still moments when I have nothing useful to do but wait: for it to fix a small bug, try a new approach, or finish running some code. These periods of waiting can be painfully boring. When I wrote everything myself, I was at least constantly engaged with the problem in front of me. I guess that is one thing vibe coding takes away from programming: it can make the process feel more passive and less engaging. Still, I appreciate the time it saves, since it lets me spend more of my energy on higher-level problem solving rather than on the mechanics of writing code.

And what do we do when we are bored? Just turn on our phone, and start doom-scrolling! For some reasons, my feeds were continuously filled with AI-generated posts that share quant interview problems (Mathemaniac has a great video on AI-generated math videos, I highly recommend). I usually just scroll past them, occasionally stopping to read ones that catch my attention. This time, the algorithm suggested me the permutation problem I mentioned at the beginning of this post. This reminds me of the time when I was doing competitive programming, where permutation-related problems were among my favorites. I was immediately intrigued, and I started doing some calculations. It was a fun exercise, and I ended up spending most of my weekend extending the problem and exploring related questions.

Back to the problem

Ok, enough backstory, let’s get back to the problem.

Let $C_n$ denote the number of cycles in a random permutation of $[2n] = \{1,2,\ldots,2n\}$, whose lengths are greater than $n$. What is $\lim_{n \to \infty} \mathbb{E}[C_n]$?

Before computing the limits, we need to make sense of what’s inside it. By definition of expectation: \begin{equation} \label{eqn:expectation-def} \mathbb{E}[C_n] = \sum_k{P[C_n = k]k}. \end{equation}

The first observation is that: “there can be at most 1 cycle that has length greater than $n$”. This is because if we have 2 or more, the number of nodes would exceed $2n$. Thus, equation \ref{eqn:expectation-def} becomes \begin{equation} \label{eqn:objective} \mathbb{E}[C_n] = P[C_n = 1], \end{equation} essentially, finding the probability that a random permutation of $[2n]$ has a cycle of length greater than $n$. A nice trick here is that we can decompose the “greater than $n$” into “of length $n+1, n+2, \ldots, 2n$”. Another observation is that: since we only care about cycles of length greater then $n$, it will be the longest cycle, and there can only be 1 of it. Let’s denote $l(\pi)$ be the longest cycle of a permutation $\pi$, then, equation \ref{eqn:objective} becomes \begin{equation} \label{eqn:sum-prob} \mathbb{E}[C_n] = \sum_{k=n+1}^{2n}{P[l(\pi) = k]}. \end{equation} To calculate $P[l(\pi) = k]$, let’s do some counting. First, we can select $k$ numbers from $[2n]$ to form the desired cycle, which has $\binom{2n}{k}$ choices. Among the chosen $k$ numbers, we can permute them in a cicle to obtain a new permutation, so it’s additional $(k-1)!$ choices (this is cyclic permutation). Then, we have the remaining $2n-k$ numbers, which we can permute however we want, which contributes $(2n-k)!$ choices. Hence, equation \ref{eqn:sum-prob} becomes \begin{align*} \mathbb{E}[C_n] &= \sum_{k=n+1}^{2n}{P[l(\pi) = k]} \\ &= \sum_{k=n+1}^{2n}{\frac{\binom{2n}{k}(k-1)!(2n-k)!}{2n!}} \\ &= \sum_{k=n+1}^{2n}{\frac{\frac{\cancel{2n!}}{k!\cancel{(2n-k)!}}(k-1)!\cancel{(2n-k)!}}{\cancel{2n!}}} \\ &= \sum_{k=n+1}^{2n}{\frac{(k-1)!}{k!}} \\ &= \sum_{k=n+1}^{2n}{\frac{1}{k}}. \end{align*}

Beautiful!

One caveat about this argument is that: at first glance, it seems that we can apply it to generalize for any cycle length $1, 2, \ldots, 2n$, not just those greater than $n$. This, unfortunately, is incorrect. The issue is that when the cycle length is less than $n$, it implies the possibility of having more than 1 cycle of that length, which we will “double-count” using the above argument. I will write about the generalization of this fact in a future blog.

Now the problem reduces to calculating

\[\lim_{n \to \infty}{\sum_{k=n+1}^{2n}{\frac{1}{k}}}.\]

This limit, if you have taken Calculus 1, you already know how to do it with Riemann sums. In this blog, I will introduce you another approach to calculate that limit, in which we will derive a nice property of Harmonic numbers.

We already know the harmonic numbers: $H_n = \sum_{k=1}^{n}{\frac1k}$. One of the first trick when I learnt competitive programming is that: the harmonic numbers grow in $O(\log{n})$! In fact, they behave very much like $\log{n}$. Heuristically, this is enough for us to guess the final answer:

\[\lim_{n \to \infty}{\sum_{k=n+1}^{2n}{\frac{1}{k}}} = \lim_{n \to \infty}{\left(H_{2n} - H_n\right)} \approx \lim_{n \to \infty}{\left(\log{2n} - \log{n}\right)} = \log{2}.\]

However, this is not rigourous as we cannot directly replace $H_n$ with $\log{n}$. To do that replacement, we need a stronger result about Harmonic number:

Lemma 1. There exists a constant $\gamma \geq 0$ such that $H_n = \log{n} + \gamma + O(\frac1n)$.

Proof of the lemma Consider the sequence $(a_n)_{n \in \mathbb{N}^+}$, where $a_n = H_n - \log{n}$. Note that $\frac1x$ decreases, we have: $$ \log{n} = \int_{1}^{n}{\frac1x}dx < \sum_{k=1}^{n}{\frac1k} = H_n. $$
You can convince yourself, or check the proof:
For each integer $k \in \\{1, 2, \ldots, n-1\\}$, consider an arbitrary number $x \in (k, k+1)$, we have $\frac1x < \frac1k$. Integrate both sides,$ \int_{k}^{k+1}{\frac1x}dx < \frac1k$. Summing everything up to $n$, we obtain $$ \sum_{k=1}^{n}{\int_{k}^{k+1}{\frac1x}dx} < \sum_{k=1}^{n}{\frac1k} $$ this is actually equivalent to $$ \int_{1}^{n}{\frac1x}dx < \sum_{k=1}^{n}{\frac1k} = H_n. $$
That gives us $a_n > 0$. Now, let's compare the consecutive terms of the sequence: \begin{align*} a_{n} - a_{n - 1} &= H_n - \log{n} - H_{n-1} + \log{\left(n-1\right)} \\ &= \frac1n + \log{\left(n-1\right)} - \log{n} \\ &= \frac1n - \int_{n-1}^{n}{\frac1x}dx. \end{align*} Note that $\int_{n-1}^{n}{\frac1x}dx > \frac1n \implies \frac1n - \int_{n-1}^{n}{\frac1x}dx < 0 \implies a_{n} - a_{n - 1} < 0$. Thus, $(a_n)_{n \in \mathbb{N}^{+}}$ decreases. By the Monotone convergence theorem, $(a_n)_{n \in \mathbb{N}^+}$ converges. By choosing $\gamma = \lim_{n \to \infty}{\left(H_n - \log{n}\right)}$, we almost finishes the proof, as now we already have $$ H_n = \log{n} + \gamma + O(1). $$ We just need to reduce the error terms down to $O\left(\frac1n\right)$. Let's decompose the error term into $a_n - \gamma = \sum_{k=n}^{\infty}{\left(a_{k} - a_{k+1}\right)}$. From above, \begin{align*} a_{k} - a_{k+1} &= \int_{k}^{k+1}{\frac1x}dx - \frac{1}{k+1} \end{align*} Using the facts we proved above that $\frac{1}{k+1} < \int_{k}^{k+1}{\frac1x}dx < \frac{1}{k}$, we can bound the difference by $$ 0 < a_{k} - a_{k+1} < \frac{1}{k} - \frac{1}{k+1} $$ Sum it to infinity: $$ 0 <a_n - \gamma < \sum_{k=n}^{\infty}{\left(\frac{1}{k} - \frac{1}{k+1}\right)} = \frac{1}{n}. $$ This implies $a_n - \gamma = O(\frac{1}{n})$.

Now the difference becomes \begin{align*} H_{2n} - H_n &= \log{2n} + \gamma + O\left(\frac{1}{2n}\right) - \log{n} - \gamma - O\left(\frac1n\right)\\ &= \log{2n} - \log{n} + O\left(\frac{1}{n}\right). \end{align*}

Since every $O(\frac1n)$ term tends to 0, we have:

\[\lim_{n \to \infty}{\sum_{k=n+1}^{2n}{\frac{1}{k}}} = \log{2}.\]

Therefore, the final answer to the question is $ \lim_{n \to \infty}{\mathbb{E}[C_n]} = \log{2}. $

The aftermath

At last, we have come to the final answer of this problem. The process of solving this problem itself didn’t took me the whole weekend (in fact, it’s just less than 1 hour, but I guess it’s still slow given that it’s an interview problem). What consumes my weekend is the extension of this problems and related questions. I usually just move on and do something else, however, as I said, I’m quite interested in permutations, so I dig deeper. Since we are dealing with cycles of a random permutation, it’s natural to ask: “On average, how many cycles are there in a random permutation?”, and “What are the probability of having cycle of length $k$?”. For the folks that have background in competitive programming, it’s also natural to extend this into a CP-style problem, which turns out to be a very interesting finding.

To be continue…