Séminaire Lotharingien de Combinatoire, 85B.81 (2021), 12 pp.

Chaim Even-Zohar, Tsviqa Lakrec and Ran J. Tessler

Spectral Analysis of Word Statistics

Abstract. Given a random text over a finite alphabet, we study the frequencies at which fixed-length words occur as subsequences. As the data size grows, the joint distribution of word counts exhibits a rich asymptotic structure. We investigate all linear combinations of subword statistics, and fully characterize their different orders of magnitude using diverse algebraic tools.

Moreover, we establish the spectral decomposition of the space of word statistics of each order. We provide explicit formulas for the eigenvectors and eigenvalues of the covariance matrix of the multivariate distribution of these statistics. Our techniques include and elaborate on a set of algebraic word operators, recently studied and employed by Dieker and Saliola (2018).

Subword counts find applications in Combinatorics, Statistics, and Computer Science. We revisit special cases from the combinatorial literature, such as intransitive dice, random core partitions, and questions on random walk. Our structural approach describes in a unified framework several classical statistical tests. We propose further potential applications to data analysis and machine learning.

This is an extended abstract. A preprint of the full paper is available online at the arXiv version.

Received: December 1, 2020. Accepted: March 1, 2021. Final version: April 29, 2021.

The following versions are available: