Interval fragmentations with choice: Equidistribution and the evolution of tagged fragments

Pascal Maillard, Elliot PaquetteThe Annals of Applied Probability 2022 · DOI · arXiv

Abstract

We consider a Markovian evolution on point processes, the $\Psi$-process, on the unit interval in which points are added according to a rule that depends only on the spacings of the existing point configuration. Having chosen a spacing, a new point is added uniformly within it. Building on previous work of the authors and of Junge, we show that the empirical distribution of points in such a process is always equidistributed under mild assumptions on the rule, generalizing work of Junge. A major portion of this article is devoted to the study of a particular growth-fragmentation process, or cell process, which is a type of piecewise-deterministic Markov process (PDMP). This process represents a linearized version of a size-biased sampling from the $\Psi$-process. We show that this PDMP is ergodic and develop the semigroup theory of it, to show that it describes a linearized version of the $\Psi$-process. This PDMP has appeared in other contexts, and in some sense we develop its theory under minimal assumptions.

Introduction: The Power of Choice in Point Processes

When points are placed randomly and independently on a line segment, they eventually fill the space. However, in many computational and physical systems, points are not placed purely at random. Instead, a "rule" or "choice" is applied to favor certain regions—typically the largest existing gaps. A classic example is the max-$k$ process: pick $k$ existing intervals at random and place a new point in the largest of the $k$. Intuitively, this "power of choice" should lead to a more uniform distribution of points than pure randomness.

While this intuition is strong, providing a rigorous mathematical proof that such processes always lead to "equidistribution" (where the empirical distribution of points converges to the Lebesgue measure) has proven remarkably difficult. Previous breakthroughs, most notably by Junge (2015), established equidistribution but required restrictive technical conditions: the selection rules had to be twice-differentiable ($C^2$) and satisfy specific inequalities that excluded common algorithms like the max-3 process. This paper bridges that gap, proving equidistribution under minimal $C^1$ assumptions and providing a unified framework for understanding these processes.

The Linearization Strategy: The Cell Process

The primary challenge in analyzing the $\Psi$-process is that it is a many-body problem; the probability of splitting one interval depends on the lengths of all other intervals in the system. To overcome this, the authors employ a linearization procedure. Instead of tracking the entire configuration of points, they focus on the evolution of a single "tagged fragment"—a representative interval as it grows and splits over time.

This evolution is modeled as a Piecewise-Deterministic Markov Process (PDMP), referred to here as the "cell process." In this model:

  1. Growth: Due to time-rescaling, the interval appears to grow exponentially.
  2. Fragmentation: At random times (determined by the selection rule $\Psi$), a new point is placed inside the interval, causing it to "jump" to a smaller size.

By analyzing this single-cell process, the authors can describe the global behavior of the entire point system. This transforms a complex, interacting system into a linear evolution equation similar to those used in biology to model cell division.

Theoretical Framework: Semigroups and Ergodicity

To prove that the system stabilizes into a uniform distribution, the authors develop a robust semigroup theory for the operator governing the cell process. A key innovation here is the use of $L^1$ spaces relative to a stationary measure. While previous research often relied on bounded continuous functions, the $L^1$ approach allows the authors to handle "rougher" selection rules—specifically those that are only once-differentiable ($C^1$).

The authors prove the system is ergodic, meaning that regardless of the initial placement of points, the system will eventually "forget" its starting state and converge to a unique equilibrium. They achieve this through a probabilistic coupling argument, demonstrating that the process "regenerates" whenever an interval hits a specific size, eventually forcing the entire configuration into a state of equidistribution.

Key Insights

  • Equidistribution vs. Interval Lengths: A subtle but vital insight is the distinction between the distribution of points and the distribution of interval lengths. The paper shows that points can become perfectly uniform across the unit interval even if the lengths of the gaps between them follow a "heavy-tailed" distribution (where a few large gaps and many tiny gaps coexist).
  • Population-Conservative Systems: Most mathematical literature on fragmentation focuses on "mass-conservative" systems. This work demonstrates that "population-conservative" models—where we follow the lineage of a single descendant—are the natural way to analyze interval fragmentation with choice.
  • Solving the Max-$k$ Problem: By relaxing the smoothness requirements from $C^2$ to $C^1$, the authors provide the first formal proof of equidistribution for the max-$k$ and min-$k$ processes for all $k \ge 1$, finally capturing cases like max-3 that were previously mathematically unreachable.

Conclusion and Future Directions

This research provides a definitive proof that a wide class of choice-based fragmentation rules naturally results in uniform point distributions. By establishing ergodicity for the associated PDMP under minimal assumptions, the authors have created a framework that is both mathematically rigorous and applicable to the algorithms used in computer science.

However, questions remain. While the paper proves that convergence occurs, it does not establish the rate of convergence—how many points must be added before the distribution is sufficiently uniform. Additionally, the current methods are optimized for one-dimensional intervals; extending the "power of choice" logic to higher dimensions, such as the partitioning of Voronoi cells in 2D or 3D, remains a significant open challenge in the field.

Summary updated

Abstract

We consider a Markovian evolution on point processes, the Ψ-process, on the unit interval in which points are added according to a rule that depends only on the spacings of the existing point configuration. Having chosen a spacing, a new point is added uniformly within it. Building on previous work of the authors and of Junge, we show that the empirical distribution of points in such a process is always equidistributed under mild assumptions on the rule, generalizing work of Junge. A major portion of this article is devoted to the study of a particular growth-fragmentation process, or cell process, which is a type of piecewise-deterministic Markov process (PDMP). This process represents a linearized version of a size-biased sampling from the Ψ-process. We show that this PDMP is ergodic and develop the semigroup theory of it, to show that it describes a linearized version of the Ψ-process. This PDMP has appeared in other contexts, and in some sense we develop its theory under minimal assumptions.
BibTeX
@article{maillard2022interval,
  author = {Pascal Maillard and Elliot Paquette},
  title = {{Interval fragmentations with choice: Equidistribution and the evolution of tagged fragments}},
  journal = {The Annals of Applied Probability},
  year = {2022},
  doi = {10.1214/21-aap1766},
}
Figure