论文标题
关于随机变量序列排列的联合典型性
On the Joint Typicality of Permutations of Sequences of Random Variables
论文作者
论文摘要
随机变量的相关序列的排列自然出现在各种应用中，例如图形匹配和异步通信。在本文中，研究了此类序列的渐近统计行为。假定基于任意关节分布产生随机向量的集合，并且向量进行置换操作。研究了相对于原始分布的产生置换载体的联合典型性。作为第一步，考虑了相关随机向量对的排列。结果表明，置换载体的关节典型性的概率仅取决于排列的分离周期的数量和长度。因此，研究称为“标准排列”的一类排列的典型性足够，为此，对关节典型性的可能性上限。标准排列的概念扩展到称为“ Bell置换矢量”的一类排列向量。通过研究Bell置换矢量，得出了关于随机序列的任意集合置换置换典型性的上限。
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.
