Abstract
Permutations of correlated sequences of random variables appear naturally in a variety of applications such as graph matching and asynchronous communications. In this paper, the asymptotic statistical behavior of such permuted sequences is studied. It is assumed that a collection of random vectors is produced based on an arbitrary joint distribution, and the vectors undergo a permutation operation. The joint typicality of the resulting permuted vectors with respect to the original distribution is investigated. As an initial step, permutations of pairs of correlated random vectors are considered. It is shown that the probability of joint typicality of the permuted vectors depends only on the number and length of the disjoint cycles of the permutation. Consequently, it suffices to study typicality for a class of permutations called 'standard permutations', for which, upper-bounds on the probability of joint typicality are derived. The notion of standard permutations is extended to a class of permutation vectors called 'Bell permutation vectors'. By investigating Bell permutation vectors, upper-bounds on the probability of joint typicality of permutations of arbitrary collections of random sequences are derived.
Introduction
In classical information theory, data sequences are typically assumed to be synchronous. For two sequences $X$ and $Y$, it is generally understood that the $i$-th element of $X$ is paired with the $i$-th element of $Y$. However, modern data science problems—such as graph matching (identifying identical users across different social networks) or database de-anonymization—often involve scenarios where this alignment is lost. In these cases, we observe $X$ and a permuted version of $Y$, denoted as $\pi(Y)$. The fundamental challenge lies in determining the original permutation $\pi$ and understanding the statistical limits of this recovery.
This paper investigates the concept of joint typicality in the context of these permutations. Joint typicality measures the probability that a pair of sequences appears to have been drawn from a specific joint distribution. If a shuffled sequence $\pi(Y)$ remains jointly typical with $X$ under an incorrect permutation, it becomes impossible to reliably recover the true alignment. This research provides the theoretical foundation to quantify these error probabilities.
Theoretical Framework
Cycle Decomposition and Standard Permutations
The authors simplify the complex analysis of permutations by leveraging cycle decomposition. Any permutation can be broken down into a set of disjoint cycles. A key contribution of this work is the proof that the probability of joint typicality depends exclusively on the number and lengths of these cycles, rather than the specific elements being moved.
To make the mathematical derivation more tractable, the authors define standard permutations. These are representative permutations that share the same cycle structure as any given permutation. By showing that analyzing a standard permutation is sufficient to characterize its entire class, the authors provide a streamlined method for calculating typicality bounds.
Bell Permutation Vectors
When the problem expands beyond two sequences (e.g., matching three or more datasets), the relationships between indices become significantly more complex. The authors address this by introducing Bell permutation vectors. Utilizing Bell numbers—which count the ways to partition a set—this framework categorizes how different indices across multiple sequences are linked by permutations. This allows for the extension of joint typicality bounds to arbitrary collections of random sequences.
Key Insights and Results
The Significance of Fixed Points
The research highlights that the probability of a permuted sequence remaining typical is primarily determined by its fixed points (elements that remain in their original positions). If a permutation has many fixed points, it is highly likely to remain typical. Conversely, for "derangements" (permutations with no fixed points), the probability of joint typicality drops exponentially.
Information-Theoretic Bounds
The authors utilize Kullback-Leibler (KL) divergence and Mutual Information to establish exponential upper bounds on the probability of "accidental" typicality. Key results include:
- Theorem 1 (General Bound): Establishes an upper bound for the probability of joint typicality for any permutation with $m$ fixed points. The probability decays as $2^{-n \cdot D}$, where $D$ is a KL divergence term related to the fraction of fixed points.
- Theorem 2 (Multi-sequence Extension): Successfully extends these bounds to collections of $k$ sequences using the Bell permutation vector framework.
- Tightness for Derangements: For permutations with no fixed points, the probability is bounded by $2^{-\frac{n}{2}(I(X;Y)-\delta)}$, where $I(X;Y)$ is the mutual information. This directly links the probability of error to fundamental information-theoretic measures of correlation.
Conclusion and Future Work
This paper provides a rigorous mathematical foundation for understanding how permutations affect the statistical properties of correlated sequences. By refining the exponents in typicality bounds, the authors offer a more accurate picture of the limits of alignment recovery.
While the results are significant, the study assumes that sequences are Independent and Identically Distributed (i.i.d.), which may not capture the internal dependencies found in real-world data like social network structures. Furthermore, while the paper establishes the information-theoretic limits of what is possible, it does not propose specific algorithms for matching. Future research may focus on applying these bounds to evaluate the performance of specific graph-matching heuristics and extending the model to non-i.i.d. data sources.
Summary updated