Abstract
Invariance properties of probability distributions are fundamental to statistical inference and probability theory. While classical results such as de Finetti’s theorem and the Aldous-Hoover representation provide elegant characterizations for infinitely exchangeable sequences and arrays, these representations often fail when the assumption of infinity is removed. This paper addresses this gap by developing a unified characterization theorem for distributions invariant under any general finite group $G$. By leveraging group-theoretic structures, the authors provide sharp bounds on the total variation distance between finite and infinite representations and offer a framework for symmetries beyond the standard symmetric group.
Introduction
In many statistical models, we assume that the order of data points does not affect their joint probability distribution—a property known as exchangeability. For infinite sequences, de Finetti’s theorem allows us to treat such data as a mixture of independent and identically distributed (i.i.d.) variables. Similarly, the Aldous-Hoover representation provides a framework for infinitely exchangeable arrays.
However, real-world data is rarely infinite. Whether analyzing a social network of 50 countries, a classroom of 30 students, or a fixed $8 \times 8$ optical grid, the "infinite" assumption is a mathematical convenience that may not hold. When this assumption fails, the standard representation theorems break down, leading to potential inaccuracies in modeling. This research characterizes the space of distributions invariant under finite groups, providing a rigorous foundation for finite-sample statistics.
The Failure of Infinite Representations
The core challenge lies in the fact that certain finite distributions cannot be embedded into infinite ones. The authors demonstrate this through a concrete example of a $2 \times 2$ matrix. In this case, a valid finite exchangeable distribution exists that simply cannot be described by the Aldous-Hoover representation—the "gold standard" for infinite arrays. This discrepancy necessitates a new approach that does not rely on the existence of an infinite sequence or array.
A Unified Framework via Group Theory
To address these limitations, the authors utilize group theory to generalize the concept of invariance. The research focuses on several key methodological pillars:
Orbit Characterization
The authors prove that any distribution invariant under a finite group $G$ can be represented as a convex combination of "extreme points." Geometrically, the space of symmetric distributions can be viewed as a convex set (often described as a "tent"), where the corners are defined by the orbits of the group action. An orbit is the set of all possible states reachable from one another through group operations (e.g., all possible permutations of a sequence).
Projection and Extendibility
A significant contribution of this work is the development of a projection criterion. This method determines whether a distribution defined on a small set (such as a small network) can be extended to a larger set while maintaining its symmetry. The authors frame this as a linear programming problem, providing a computational path to verify the validity of symmetry assumptions in finite contexts.
Key Results and Sharp Bounds
The paper provides formal mathematical grounding through several key theorems:
- Theorem 1 (Characterization): This theorem formally defines the space of $G$-invariant measures as a convex set, establishing the theoretical basis for the rest of the work.
- Theorems 4 & 6 (Sharp Bounds): One of the most practical outcomes is the derivation of sharp bounds on the Total Variation (TV) distance. For a jointly exchangeable $m \times m$ array that is $r$-extendible, the distance to an infinite distribution is bounded by $2\beta(m, r)$.
- Convergence Rates: The authors show that the rate of convergence for these bounds is approximately $O(m^2/q + n^2/r)$. This result is crucial for practitioners, as it provides a mathematical justification for when it is "safe" to use infinite approximations for finite matrices.
Beyond the Symmetric Group
While most existing literature focuses on the symmetric group (simple shuffling), this paper extends the theory to more complex symmetries. For example, the authors apply their framework to the Dihedral Group, which describes the rotations and reflections of a square. This is particularly relevant in fields like geometric optics or physical imaging, where data is indexed by physical symmetries rather than just arbitrary ordering.
Computational Challenges
The authors acknowledge that while the theory is robust, implementation faces computational hurdles. Finding orbits for complex structures like large networks is computationally equivalent to the Graph Isomorphism Problem. This connection explains why modeling symmetries in large-scale relational data remains a significant challenge in computer science and statistics.
Conclusion
By characterizing finite group invariant distributions, this research bridges the gap between idealized infinite models and the constraints of real-world data. The introduction of sharp TV bounds and the move beyond the symmetric group provide statisticians with a more flexible and rigorous toolkit for modeling symmetric data. Future work involving signed measures and hypothesis testing frameworks promises to further refine our understanding of how symmetry shapes the foundations of probability.
Summary updated