Characterization of Finite Group Invariant Distributions

Alexander Volfovsky, Edoardo M. AiroldiarXiv 2014 · arXiv

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:

  1. 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.
  2. 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)$.
  3. 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

Abstract

Invariance properties of probability distributions have long been an area of interest in statistics and probability. In particular, much has been written about the famous de Finetti's theorem for infinitely exchangeable sequences and the Aldous-Hoover representation for infinitely exchangeable arrays. The key to both of these results is the existence of an infinite sequence or an infinite array. When this assumption fails, so do the aforementioned representation theorems. In this article we demonstrate this failure for the Aldous-Hoover representation and then develop a characterization theorem for the space of distributions that are invariant under a general finite group G. In particular, the results of Diaconis (1977) for finitely exchangeable sequences are a special case of our general result. We find sharp bounds on the total variation distance between distributions of finitely and infinitely partially exchangeable sequences and finitely and infinitely exchangeable arrays. Additionally we provide an example of the applicability of the theory for groups other than the symmetric group.
BibTeX
@misc{volfovsky2014characterization,
  author = {Alexander Volfovsky and Edoardo M. Airoldi},
  title = {{Characterization of Finite Group Invariant Distributions}},
  year = {2014},
  eprint = {1407.6092},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.6092},
}

Loading related content...

Figure