Limit theorems for fixed point biased permutations avoiding a pattern of length three

This paper establishes limit theorems for the number of fixed points in random pattern-avoiding permutations under a biased distribution, revealing a phase transition where the limiting behavior shifts from negative binomial to Rayleigh to normal depending on the bias parameter.

The Gist

Imagine you have a deck of $n$ cards, numbered 1 to $n$. A permutation is just a way of shuffling these cards so they are in a new order.

In this paper, the authors are studying a very specific question: How many cards end up in their "original" spot? (For example, if the card numbered 5 is still in the 5th position after the shuffle). In math-speak, these are called fixed points.

Usually, if you shuffle a deck completely randomly, the number of cards that stay in place follows a very predictable pattern (like a Poisson distribution). But this paper asks: What happens if we don't shuffle randomly?

The Two Rules of the Game

The authors introduce two "twists" to the standard shuffling game:

1. The "Bias" (The Magnet): Imagine you have a magnet that attracts cards to their original spots.

   • If the magnet is weak (parameter $q < 1$), it actually repels cards from their spots. You get fewer fixed points than usual.
   • If the magnet is strong (parameter $q > 1$), it pulls cards into their spots. You get way more fixed points than usual.
   • The authors are studying how the number of fixed points behaves when you turn this magnet up or down.

2. The "Forbidden Pattern" (The Rulebook): Imagine you are playing a card game where you are not allowed to create a specific "forbidden sequence."

   • For example, you might be forbidden from having a "High-Low-Medium" sequence (like a 3, then a 1, then a 2).
   • The paper looks at what happens when you shuffle cards while obeying this rule, and also using the magnet.

The Big Discovery: The "Phase Transition"

The most exciting part of the paper is what happens when you combine the Forbidden Pattern with the Magnet.

The authors found that for certain types of forbidden patterns, the behavior of the cards changes dramatically depending on how strong the magnet is. They call this a Phase Transition. It's like water:

• Ice (Subcritical): When the magnet is weak ($q < 3$), the number of fixed points behaves like a standard "counting" distribution (Negative Binomial). It's stable and predictable.
• Water (Critical): When the magnet hits a specific sweet spot ($q = 3$), the behavior changes completely. The number of fixed points starts to grow with the square root of the deck size, following a "Rayleigh" distribution (think of the shape of a bell curve that's been squashed on one side).
• Steam (Supercritical): When the magnet is very strong ($q > 3$), the number of fixed points explodes. It grows linearly with the size of the deck, and the fluctuations around that average look like a perfect Bell Curve (Normal distribution).

The Analogy:
Imagine a crowd of people trying to stand in a specific line (the pattern rule).

• Weak Magnet: People are scattered. A few happen to stand in their "right" spot by accident.
• Strong Magnet: Everyone is desperately trying to stand in their "right" spot. The crowd organizes itself into a massive, orderly block.
• The Tipping Point ($q=3$): There is a specific moment where the crowd suddenly snaps from being scattered to being highly organized. The math describing this "snap" changes from one type of curve to another.

Why Should We Care?

You might wonder, "Who cares about shuffling cards with rules?"

1. Sorting Algorithms: In computer science, sorting data is a huge job. Some sorting algorithms work incredibly fast only if the data avoids certain patterns. Understanding how "ordered" (how many fixed points) this data is helps engineers design better, faster software.
2. Predicting Chaos: This research helps us understand how small changes in a system (turning up the magnet) can lead to sudden, massive shifts in the outcome (the phase transition). This is useful in physics, economics, and network theory.

Summary in a Nutshell

The authors took a classic math problem (shuffling cards), added a "preference" for order (the bias), and added a "rule" about what patterns are allowed (pattern avoidance).

They discovered that for some rules, the system behaves normally. But for others, there is a magic number (3). Below 3, the system is calm. Above 3, the system goes wild and organizes itself into a perfect bell curve. Right at 3, it does something entirely unique.

It's a beautiful example of how simple rules (shuffling, avoiding a pattern, and a little bias) can create complex, surprising, and mathematically elegant behaviors.

Technical Summary

Here is a detailed technical summary of the paper "Limit theorems for fixed point biased permutations avoiding a pattern of length three" by Aksheytha Chelikavada and Hugo Panzo.

1. Problem Statement

The paper addresses the limiting distribution of the number of fixed points ($fp$) in random permutations under two simultaneous generalizations of the classical "problem of coincidences":

1. Non-uniform Bias: Instead of the uniform distribution, permutations are drawn from a one-parameter family of Gibbsian biased distributions where the probability of a permutation $\sigma$ is proportional to $q^{fp(\sigma)}$. Here, $q > 0$ is a bias parameter.
   • If $q > 1$, permutations with many fixed points are favored (more "ordered").
   • If $0 < q < 1$, permutations with few fixed points are favored (more "disordered").
2. Pattern Avoidance: The permutations are constrained to avoid a specific pattern $\tau$ of length 3.

The authors investigate how the interplay between the bias parameter $q$ and the pattern avoidance constraint $\tau$ affects the asymptotic behavior of the number of fixed points as $n \to \infty$.

2. Methodology

The authors employ a combination of probabilistic techniques and tools from analytic combinatorics, specifically singularity analysis of generating functions.

• Generating Functions:
  • For the unbiased case ($q=1$), they utilize known limit theorems for pattern-avoiding permutations.
  • For the biased case, they rely on a bivariate generating function $G(z, q)$ derived by S. Elizalde, which counts $\tau$-avoiding permutations marked by length ($z$) and number of fixed points ($q$).
  • The normalization constant $Z_n(q, \tau)$ is identified as the coefficient $[z^n]G(z, q)$.
• Singularity Analysis:
  • The asymptotic behavior of $Z_n(q, \tau)$ is determined by analyzing the dominant singularities of $G(z, q)$ in the complex plane.
  • The paper identifies a critical phenomenon where the nature of the dominant singularity changes based on the value of $q$. Specifically, for certain patterns, the singularity shifts from a branch point at $z=1/4$ to a pole at $z = \frac{q-2}{(q-1)^2}$ as $q$ increases.
• Limit Theorems:
  • Subcritical/Critical Phases: Proofs involve calculating limits of probability generating functions (PGFs) or using the "moment pumping" method to match moments of the limiting distribution (e.g., Rayleigh).
  • Supercritical Phase: The authors apply Theorem IX.9 from Flajolet and Sedgewick's Analytic Combinatorics, which provides conditions for the convergence of random variables defined by coefficients of bivariate generating functions to a Gaussian distribution.

3. Key Contributions and Results

The results are categorized by the specific pattern $\tau$ being avoided.

A. Unconstrained Permutations (Generalization of Montmort's Theorem)

• Theorem 1: For random permutations distributed according to $P_n^q$ (no pattern avoidance), the number of fixed points converges in distribution to a Poisson($q$) random variable. This generalizes the classical result where $q=1$ yields Poisson(1).

B. Pattern $\tau = 123$

• Theorem 2: For permutations avoiding the pattern 123, the number of fixed points converges to the sum of two independent Bernoulli random variables with parameter $p = \frac{q}{3+q}$.
  • Limit: $A + B$, where $A, B \sim \text{Bernoulli}(\frac{q}{3+q})$.

C. Patterns $\tau \in \{132, 321, 213\}$: Phase Transitions

This is the most significant contribution. The authors discover a phase transition at $q=3$ where the limiting distribution changes qualitatively.

1. Subcritical Phase ($0 < q < 3$):

   • Theorem 3: The number of fixed points converges to a Negative Binomial distribution without scaling.
   • Limit: $\text{NegativeBinomial}(2, 1 - \frac{q}{3})$.

2. Critical Phase ($q = 3$):

   • Theorem 4: After scaling by $1/\sqrt{n}$, the number of fixed points converges to a Rayleigh distribution.
   • Limit: $\frac{fp(\Pi)}{\sqrt{n}} \xrightarrow{d} \text{Rayleigh}(\frac{3}{\sqrt{2}})$.

3. Supercritical Phase ($q > 3$):

   • Theorem 5: After appropriate centering and scaling, the number of fixed points converges to a Standard Normal distribution.
   • The mean scales linearly with $n$, and the variance scales linearly with $n$.
   • Limit: $\frac{fp(\Pi) - \mu_n}{\sigma_n} \xrightarrow{d} \mathcal{N}(0, 1)$, where $\mu_n \sim \Theta(n)$ and $\sigma_n \sim \Theta(\sqrt{n})$.

D. Normalization Constants (Lemma 1)

The paper derives the asymptotic growth of the normalization constant $Z_n(q, \tau)$ for $\tau \in \{132, 321, 213\}$, which exhibits the same phase transition:

• $q < 3$: Growth is dominated by $4^n n^{-3/2}$.
• $q = 3$: Growth is dominated by $4^n n^{-1/2}$.
• $q > 3$: Growth is exponential with a base dependent on $q$, specifically $\left(\frac{(q-1)^2}{q-2}\right)^n$.

4. Significance and Implications

• Phase Transitions in Combinatorial Probability: The paper provides a concrete example of a phase transition in the context of pattern-avoiding permutations. The shift from Negative Binomial (discrete, heavy-tailed) to Rayleigh (continuous, scaling $\sqrt{n}$) to Normal (scaling $n$) depending solely on the bias parameter $q$ is a novel finding.
• Connection to Sorting Algorithms: The fixed-point bias is analogous to "presortedness," a concept relevant to sorting algorithms. The patterns studied (e.g., 231 avoidance relates to stack-sortable permutations) are fundamental in the study of sorting efficiency.
• Methodological Advancement: The work demonstrates the power of singularity analysis in handling non-uniform distributions on combinatorial structures. It successfully bridges the gap between biased measures (Gibbs distributions) and pattern avoidance, a combination not previously explored in depth for limit theorems.
• Open Problems: The authors identify that the case $\tau \in \{231, 312\}$ remains open. They hypothesize a similar phase transition exists but note that current generating function techniques (continued fractions) are insufficient for singularity analysis in the biased case. They also suggest future work on the limiting "permuton" (the continuous limit shape of the permutation) for these biased models.

In summary, this paper rigorously establishes that introducing a bias toward fixed points in pattern-avoiding permutations creates a rich landscape of limiting behaviors, characterized by a sharp phase transition at $q=3$ for specific pattern classes.