%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{81}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

%\usepackage{lipsum}

%\usepackage{amsaddr}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{graphicx}
\usepackage{dsfont}
\usepackage{relsize}
\usepackage{enumitem}

\usepackage{tikz}
\usetikzlibrary{math,calc}

%\usepackage[colorlinks=true,
%linkcolor=webgreen,
%filecolor=webbrown,
%citecolor=webgreen,
%urlcolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{inconsolata}
\usepackage{bbm}
\usepackage{mathtools}

%\usepackage{shuffle}
%\usepackage[OT2,T1]{fontenc}
%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
%\DeclareSymbolFont{cyrletters}{OT2}{wncyss}{m}{n}
%\DeclareMathSymbol{\sha}{\mathalpha}{cyrletters}{"58}
% Based on https://tex.stackexchange.com/questions/124738/i-just-want-to-write-sha-without-ruining-everything/124746#124746 replacing wncy and wncyr10 with wncyss
\DeclareFontFamily{U}{wncyss}{}
\DeclareFontShape{U}{wncyss}{m}{n}{<->wncyss10}{}
\DeclareSymbolFont{mcy}{U}{wncyss}{m}{n}
\DeclareMathSymbol{\sha}{\mathalpha}{mcy}{"58}

\newtheorem{thm}{Theorem} 
\newtheorem*{thm*}{Theorem}
\newtheorem{prop}{Proposition}[section]
\newtheorem{pr}[prop]{Proposition}
\newtheorem{lem}[prop]{Lemma}
\newtheorem{lm}[prop]{Lemma}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{corollary}[prop]{Corollary}
\newtheorem{clm}[prop]{Claim}
\newtheorem{alsotheorem}[prop]{Theorem}
\newtheorem{st}{Step}
\newtheorem{ass}{Assumption}
\newtheorem{obs}[prop]{Observation}
\newtheorem*{obs*}{Observation}
\newtheorem{open}{Open problem}
\newtheorem{conj}{Conjecture}
\newtheorem{ex}{Example}
\theoremstyle{definition}
\newtheorem{definition}[prop]{Definition}
\newtheorem{nn}[prop]{Notation}
\newtheorem{cv}[prop]{Convention}
\newtheorem{rem}[prop]{Remark}
\theoremstyle{remark}
\newtheorem{rmk}[prop]{Remark}
\newtheorem*{rmk*}{Remark}
\newtheorem*{ex*}{Example}
\newtheorem{defn}[prop]{Definition}

\newcommand{\p}{\partial}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb C}
\newcommand{\Q}{Q}
\newcommand{\q}{q}
\newcommand{\EEE}{R}
\newcommand{\N}{\mathbb N}
\newcommand{\iii}{{\mathbf i}}
\newcommand{\jjj}{{\mathbf j}}
\newcommand{\A}{M}
\newcommand{\BS}{S}
\newcommand{\B}{B}
\newcommand{\del}{\partial}
%\newcommand{\sh}{\shuffle}
%\newcommand{\shh}{\shuffle^*}
\newcommand{\sh}{\sha}
\newcommand{\shh}{\sha^*}
\newcommand{\grad}{\nabla}
\newcommand{\ee}{\mathbf{e}}
\newcommand{\uu}{\mathbf{u}}
\newcommand{\mergeset}{\mathcal{M}}
\newcommand{\mergecnt}{\mu}

\newcommand{\TA}{{\text{\bfseries\ttfamily a}}}
\newcommand{\TB}{{\text{\bfseries\ttfamily b}}}
\newcommand{\TC}{{\text{\bfseries\ttfamily c}}}
\newcommand{\TD}{{\text{\bfseries\ttfamily d}}}
\newcommand{\TE}{{\text{\bfseries\ttfamily e}}}
\newcommand{\TI}{{\text{\bfseries\ttfamily i}}}
\newcommand{\TJ}{{\text{\bfseries\ttfamily j}}}
\newcommand{\TS}{{\text{\bfseries\ttfamily s}}}
\newcommand{\TT}{{\text{\bfseries\ttfamily t}}}
\newcommand{\TX}{{\text{\bfseries\ttfamily x}}}
\newcommand{\TY}{{\text{\bfseries\ttfamily y}}}
\newcommand{\TZ}{{\text{\bfseries\ttfamily z}}}
\newcommand{\To}{{\text{\bfseries\ttfamily 0}}}
\newcommand{\Ti}{{\text{\bfseries\ttfamily 1}}}
\newcommand{\Tii}{{\text{\bfseries\ttfamily 2}}}
\newcommand{\Tiii}{{\text{\bfseries\ttfamily 3}}}
\newcommand{\Tiiii}{{\text{\bfseries\ttfamily 4}}}
\newcommand{\THH}{{\text{\bfseries\ttfamily H}}}
\newcommand{\TTT}{{\text{\bfseries\ttfamily T}}}
\newcommand{\TEE}{{\text{\bfseries\ttfamily E}}}
\newcommand{\TNN}{{\text{\bfseries\ttfamily N}}}
\newcommand{\TWW}{{\text{\bfseries\ttfamily W}}}
\newcommand{\TSS}{{\text{\bfseries\ttfamily S}}}
\newcommand{\strip}{\mathcal{X}}
\newcommand{\E}{\mathbb E}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Akr}{M}

\newcommand{\Mp}{\mathcal{M}}
\newcommand{\Np}{\mathcal{N}}
\newcommand{\shp}{\mathcal{L}}
\newcommand{\RTR}{\mathcal{R}}
\newcommand{\proj}{\mathcal{P}}
\DeclareMathOperator{\Ima}{Im}
\newcommand{\npt}{\texorpdfstring{\spacefactor 1007}{}}
\newcommand{\Exp}{\operatorname{\mathbb{E}}}
\newcommand{\PR}{\operatorname{\mathbb{P}}}
\newcommand{\Var}{\operatorname{V}}
\newcommand{\Cov}{\operatorname{Cov}} 
\newcommand{\word}{\operatorname{word}} 
\newcommand{\kpa}{\boldsymbol{\kappa}}
\newcommand{\lmda}{\boldsymbol{\lambda}}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\SPAN}{span}









%% define your title in the usual way
\title{Spectral Analysis of Word Statistics}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
Chaim Even-Zohar\thanks{
\href{mailto:chaim@ucdavis.edu}{chaim@ucdavis.edu} 
C.~E.~was supported by the Lloyd’s Register Foundation / Alan Turing Institute programme on Data-Centric Engineering.
}\addressmark{1}, 
Tsviqa Lakrec\thanks{
\href{mailto:tsviqa@gmail.com}{tsviqa@gmail.com}
T.~L.~was supported by the ISF grant 891/15 and ERC 2020 grant HomDyn 833423.
}\addressmark{2}, \and
Ran J. Tessler\thanks{
\href{mailto:ran.tessler@weizmann.ac.il}{ran.tessler@weizmann.ac.il}
R.~T.~(incumbent of the Lillian and George Lyttle Career Development Chair) was supported by the ISF grant No. 335/19 and by a research grant from the Center for New Scientists of Weizmann Institute.
}\addressmark{3}
}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}The Alan Turing Institute, London, United Kingdom \\ \addressmark{2}Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Israel \\
\addressmark{3}Department of Mathematics, Weizmann Institute of Science, Rehovot, Israel
}

%% put the date of submission here
\received{December 1, 2020}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\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.

\begin{rmk*}
This is an extended abstract. A~preprint of the full paper is available online at \texttt{https://arxiv.org/pdf/2012.00742} .
\end{rmk*}
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
%\keywords{math, maths, mathematics}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{81Even-Zohar.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Word Statistics}

Sequences over a finite alphabet are ubiquitous in pure and applied mathematics, and lie at the core of many probabilistic models. They may represent steps of a random walk, words of group generators, discrete-valued time series, DNA segments, or output of pseudorandom generators, to mention a few examples. In the analysis of such sequences, one often considers various numerical \emph{statistics}, in order to capture their main features, extract meaningful information, apply further processing, or take informed decisions. It is hence important to examine general families of such statistics, and thoroughly understand their expected behavior.

\smallskip
\emph{Subword counts} give rise to a broad family of word statistics, which this work investigates. Given a finite alphabet $\Sigma = \{\TA,\TB,\TC,\dots\}$, a pattern $u \in \Sigma^k$, and a longer text $w \in \Sigma^n$, we consider $\#u(w)$, the number of occurrences of~$u$ as a subsequence of~$w$. The copies of~$u$ that we count do not have to appear consecutively in the text, nor to be disjoint. For example \mbox{$\#\texttt{fee}(\texttt{referee}) = 3$}. Many well-studied word statistics are special cases of these counts, or finite linear combinations of them.

\smallskip
\emph{Randomized models} provide a natural setting to investigate words and their statistics. They help us analyze these fundamental objects via typical instances, and guide us in developing relevant tools for applications. Here are two basic models for a random word~$w \in \Sigma^n$, that appear naturally in various contexts and applications. 
\begin{itemize}[leftmargin=15pt]
\setlength{\itemsep}{0.25em}
\item 
\textbf{One-Sample: $\mathcal{W}(n,\mathbf{p})$} where $\mathbf{p}=(p_\TA, p_\TB, \dots) \in (0,1)^{|\Sigma|}$ and $\sum_{\TX} p_\TX = 1$ \\[0.125em] 
The letters of~$w$ are independent, and every letter $w_i=\TX$ with probability~$p_\TX$. 
\item
\textbf{Multi-Sample: $\mathcal{W}'(\mathbf{n})$} where $\mathbf{n}=(n_\TA, n_\TB,\dots) \in \mathbb{N}^{|\Sigma|}$ and $\sum_\TX n_\TX = n$ \\[0.125em]
Every word~$w$ with exactly $n_\TX=\#\TX(w)$ for every~$\TX$, is equally likely.
\end{itemize}
The word models $\mathcal{W}$ and $\mathcal{W}'$ parallel the two best-studied random graph models on $n$ labeled vertices. For graphs, $\mathcal{G}(n,p)$ selects every edge with probability~$p$ independently, and $\mathcal{G}'(n,m)$ selects exactly $m$ edges uniformly from all possible ways~\cite{janson2011random}. While the two kinds of models share many asymptotic properties, they differ in some important aspects, especially regarding subgraph counts, and in our models -- subword counts.

\begin{rmk*}
This is an extended abstract. A~preprint of the full paper is available online at~\cite{full}, and includes all the details of the constructions, the proofs, and more applications.
\end{rmk*}

\section{Spaces of Subword Counts}

We start with a general presentation of our approach to subword statistics. Some new results and special cases will be mentioned, but full formal statements are deferred to the subsequent~\S\ref{results}. 

Let $k \in \mathbb{N}$, and consider the random variables $\#u$, for all $k$-letter words $u \in \Sigma^k$. For the sake of this general discussion, the distribution of the underlying $w \in \Sigma^n$ may be either $\mathcal{W}(n,\mathbf{p})$ or~$\mathcal{W}'(\mathbf{n})$. In the latter model, we let $n_\TX = p_\TX n$ and the same general statements apply up to minor changes. 

How is the subword count $\#u$ distributed as the text size $n$ grows? By summation over all $\tbinom{n}{k}$ potential occurrences, one can see that the expected value and variance are
$$ \Exp\left[\#u\right] \;=\; \frac{p_{u_1}\!\cdots p_{u_k}}{k!}\, n^k \pm O(n^{k-1})\,, \;\;\;\;\;\;\;\; \Var\left[\#u\right] \;=\; O\left(n^{2k-1}\right) $$

It follows that the vector of \emph{subword frequencies}, $\#u/\tbinom{n}{k}$ for $u \in \Sigma^k$, satisfies a law of large numbers: 
$$ \mathbf{X}_k \;:=\; \left\{\tfrac{\displaystyle \#u}{\tbinom{n}{k}}\right\}_{u \in \Sigma^k} \;\;\;\xrightarrow[\text{\;in probability\;}]{n \to \infty} \;\;\; \Exp\left[\mathbf{X}_k\right] \;=\; \mathbf{p}^{\otimes k} $$

It is then natural to study interactions between different subword counts. In general, there is a nonzero correlation between $\#u$ and $\#v$, even in the limit as $n \to \infty$. These correlations are encoded in the following $|\Sigma|^k$-dimensional central limit theorem, as we will see later on.
$$ \sqrt{n}\left(\mathbf{X}_k - \Exp\left[\mathbf{X}_k\right]\right) \;\;\;\xrightarrow[\text{\;in distribution\;}]{n \to \infty} \;\;\; \mathcal{N}\left(\mathbf{0},\, \lim_{n \to \infty} n  \Cov\left[\mathbf{X}_k\right] \right) $$

However, the multivariate Gaussian limit reveals only a small part of the asymptotic picture. It turns out that the rank of the limiting covariance matrix is much lower than~$|\Sigma|^k$, so that the limit law is supported on a low-dimensional subspace. In terms of linear combinations of the form $\sum_u f_u\, \#u$ with $f_u \in \mathbb{R}$, many of those are significantly more concentrated than their individual constituents, and should be scaled differently. 

Let $\mathbb{R}\Sigma^k$ denote the space of formal linear combinations of $k$-letter words over~$\Sigma$. Every $f = \sum_u f_u u \in \mathbb{R}\Sigma^k$ defines a scalar random variable $\#f$ by linearity. One desirable goal is to find the typical order of magnitude of all~$\#f$. The first step in our approach is \emph{grading} the space of all subword combinations. This grading provides an orthogonal decomposition $\mathbb{R}\Sigma^k = \bigoplus_{r} V_r$ such that $\Exp[(\#f/n^k)^2] = \Theta(1/n^r)$ for every nonzero $f \in V_r$.

The next goal is to analyze the random variables within each component, that is, $n^{r/2} \mathbf{X}_k$ projected onto~$V_r$. The spaces of word statistics in our models come with natural inner product structures. The most fundamental and most practical objective is a basis of statistics that diagonalizes the covariance matrix of this multivariate distribution, in the spirit of principal component analysis, PCA. Thus, the second step is a \emph{spectral} decomposition of each component~$V_r$. 

Having a full explicit decomposition of this form, one can readily obtain the precise leading term of the variance $\Var[\#f]$ for any feature $f$ which is a scalar projection of~$\mathbf{X}_k$. It lets one identify and compare the various ``modes'' of the joint distribution, which reveals much of its structure. 

Our main contribution is the implementation of this plan. We provide gradings of word statistics by scale, and diagonalizations by second moments, as stated below in~\S\ref{results}. These are demonstrated on diverse examples in~\S\ref{examples}. Several previously-studied word statistics naturally arise as special cases, including some of order smaller than $1/\sqrt{n}$. Also new families of word statistics constructed this way seem to be meaningful and useful. 

The analysis of multivariate statistical features of ordered or sequential data is a direct practical application of our work. Linear decompositions of data on combinatorial structures have been studied since the seminal monograph by Diaconis \cite[\S8]{diaconis1988group}, that introduced the use of algebraic tools such as representations of the symmetric group. However, the crucial issue of choosing bases for components has mostly been left arbitrary, depending on matters of convenience, or ad~hoc interpretations. Our proposed approach, which turns to the second moment structure of typical data distributions, aims to provide a systematic treatment that seems very natural from a practical perspective. In fact, the random word models we use make it particularly well-suited for extracting features in the high noise regime.

\section{Main Results}
\label{results}

We now present the scaling decompositions and the spectral decompositions of the subword statistics of random words. The one-sample model $\mathcal{W}(n,\mathbf{p})$, where letters are independent, is treated in Theorems \ref{main1}~and~\ref{main2}. Theorems \ref{main3}~and~\ref{main4} concern the more involved setting of the multisample model $\mathcal{W}'(\mathbf{n})$, with randomly ordered letters. 

All the components can be obtained by straightforward elementary computations, using Gaussian elimination and combinatorial manipulations on words. These constructions are very briefly sketched in the next section, while detailed accounts are available in the full version at~\cite{full}. 

\medskip

Let $w$ be a random word in the model $\mathcal{W}(n, \mathbf{p})$. Recall that $\Sigma = \{\TA,\TB,\cdots\}$ is a finite alphabet, so that $d := |\Sigma| \geq 2$, and the characters of $w$ are independent and distributed with $\mathbf{p} = (p_\TA, p_\TB, \cdots) \in \mathbb{R}^d$. We count subwords $u \in \Sigma^k$ occurring in $w \in \Sigma^n$, and study the normalized statistic,
$$ \bar\#u(w) \;:=\; \frac{\#u(w)}{\tbinom{n}{k}} \;\in\; [0,1]$$
Moreover, we study all linear combinations of the random variables $\bar\#u$ for $u \in \Sigma^k$. Every formal sum $f = \sum_u f_u u$ in the $d^k$-dimensional space $W_k := \mathbb{R}\Sigma^k$ defines such statistics $\#f$ and $\bar\#f$ by linearity. 

Working with a single length $k \in \mathbb{N}$ is not a real restriction. Indeed, in \S2.4 of~\cite{full} we define compatible linear embeddings $W_k \hookrightarrow W_{k+1}$. Therefore, every $W_k$ contains all $W_{j}$ for $j < k$. The space of all subword statistics is thus denoted $W := \bigcup_{k\in\mathbb{N}}\, W_k$. 

In order to establish the scaling of $\#f$ for every $f \in W$, we study the structure of every~$W_k$. In \S2.1 of~\cite{full} we define a grading on the spaces $W_k$, which will yield a well-defined grading on $W$. Every space $W_k$ decomposes into $k+1$ subspaces, denoted
\begin{align*}
& W_k \;=\; W_{k0} \,\oplus\, W_{k1} \,\oplus\, \dots \,\oplus\, W_{kk} \\ 
& \dim W_{kr} \;=\; \tbinom{k}{r}(d-1)^r 
\end{align*}
This primary decomposition depends on the probability vector $\mathbf{p}$. The following theorem asserts that it determines the order of magnitude in $n$ of any statistic in $W_k$, and different components are uncorrelated. 

\begin{thm}
[Grading under $\mathcal{W}(n,\mathbf{p})$]
\label{thm:main_grading_variance}
\label{main1}
$ $ \\[0.25em]
Let $k \in \mathbb{N}$ and $r \in \{0,1,\dots,k\}$. For every nonzero statistic $f \in W_{kr}$ there exists $C_{f,\mathbf{p}} > 0$ such that
$$ n^r \, \Exp_{\,\mathcal{W} (n,\mathbf{p})}\left[\left(\bar\#f\right)^2\right] \; \xrightarrow[\;n \to \infty\;]{}\; C_{f,\mathbf{p}}. $$
Moreover, for every $r' \neq r$ and $f' \in W_{kr'}$, \;$\Exp_{\,\mathcal{W}(n,\mathbf{p})}\left[\,\bar\#f\;\bar\#f'\,\right] \, = \, 0$.
\end{thm}

\begin{rmk*}
This decomposition also has the property that $W_{k0}, \dots, W_{kk}$ are pairwise orthogonal. Here we work with the inner product on $W_k$, naturally induced from the measure $\mathcal{W}(k,\mathbf{p})$, and denoted~$\langle f,f'\rangle_{\mathbf{p}}$.
\end{rmk*}

We further refine each component $W_{kr}$ into $k-r+1$ orthogonal subspaces. For every $k \geq r \geq 1$, the following decomposition is given in \S2.3 of~\cite{full}. 
\begin{align*}
& W_{kr} \;=\; W_{kr0} \,\oplus\, W_{kr1} \,\oplus\, \dots \,\oplus\, W_{kr(k-r)} \\ 
& \dim W_{krm} \;=\; \tbinom{r+m-1}{m}(d-1)^r
\end{align*}
This secondary decomposition yields a full asymptotic diagonalization of the covariance of~$W_k$, as follows.

\begin{thm}[Spectrum under $\mathcal{W}(n,\mathbf{p})$] $ $ \\[0.25em]
\label{main2}
Let $k \in \mathbb{N}$, $r \in \{1,\dots,k\}$, and $m,m' \in \{0,\dots,k-r\}$. For every $f \in W_{krm}$ and $f' \in W_{krm'}$ 
$$ \Exp_{\,\mathcal{W}(n,\mathbf{p})}\left[\left(n^{r/2}\,\bar\#f\right)\left(n^{r/2}\,\bar\#f'\right)\right] \;\; \xrightarrow[\;n \to \infty\;]{}\;\; \frac{(k!)^2 \, \left\langle f,f' \right\rangle_{\mathbf{p}}}{(k+m)!(k-r-m)!} $$
In particular, if $m'\neq m$ then this limit is 
$\left\langle f,f' \right\rangle_{\mathbf{p}} = 0$.
\end{thm}

In \S2.6 of the full version~\cite{full} we present a concise and practical description of the spaces~$W_{krm}$, which provides insight into their structure. We establish an explicit isomorphism between $W_{krm}$ and $U_{krm} \otimes (\mathbb{R}^{d-1})^{\otimes r}$, where $U_{krm}$ are spaces of \emph{multivariate orthogonal polynomials on the discrete simplex}.

\begin{rmk*}
As we discuss in \S2.12 of~\cite{full}, if $f \in W_{kr}$ then $\bar\#f$ is a so-called \emph{U-statistic of rank~$r$}. This fact provides additional information on the distribution of these random variables. \end{rmk*}

\medskip

We now turn to the other model $\mathcal{W}'(\mathbf{n})$ where the random word $w$ has a prescribed \emph{composition} $\mathbf{n} =  (n_\TA,n_\TB,n_\TC,\dots)$, meaning $\#\TX(w)=n_\TX$ for every letter $\TX \in \Sigma$. Denote the set of such words by $\tbinom{\mathsmaller{\Sigma}}{\mathbf{n}}$, and denote their length by $n = |\mathbf{n}| := {\sum}_\TX n_\TX$. The number of words in the set $\tbinom{\mathsmaller{\Sigma}}{\mathbf{n}}$ is the multinomial coefficient $\tbinom{n}{\mathbf{n}} = n!/(n_\TA!n_\TB!\cdots)$, and each one is equally likely in~$\mathcal{W}'(\mathbf{n})$.

As before, we count the occurrences of subwords $u \in \Sigma^k$ and analyze the random variables $\#u$, or $\#f$ for linear combinations $f = \sum_u f_u u$. However, in this model it is sufficient to consider words~$u \in \tbinom{\mathsmaller{\Sigma}}{\kpa}$, fixing the composition $\kpa = (k_\TA,k_\TB,\dots)$ of~$u$. Indeed, in \S2.7 of~\cite{full} we show how subwords of different compositions reduce to this case. We therefore work in the linear space of formal sums of words of composition~$\kpa$, denoted
$W_{\kpa} = W_{(k_\TA ,k_\TB,\dots)} := \mathbb{R}\tbinom{\Sigma}{\kpa}$. Note that $\dim W_{\kpa} = \tbinom{k}{\kpa}$ where $k = |\kpa|$. For $u\in \tbinom{\mathsmaller{\Sigma}}{\kpa}$, a natural choice of normalization is 
$$ \tilde\# u \;:=\; \frac{\#u}{\prod_{\TX  \in \Sigma} \tbinom{n_\TX}{k_\TX}} \;\in\; [0,1]$$
extended to $\tilde\#f$ for linear combinations $f = \sum_uf_uu \in W_{\kpa}$. Without loss of generality we assume $k_\TA \geq k_\TB \geq \dots > 0$ unless stated otherwise.

Our primary decomposition of $W_{\kpa}$ is based on representations of the symmetric group~$S_k$. The space $W_{\kpa}$ admits an action of $S_k$ by reordering all $k$-letter words in its basis. The implied decomposition of $W_{\kpa}$ as a direct sum of simple $S_k$ representations is well-studied. In~\S2.8-2.9 of~\cite{full}, we briefly review this decomposition and use it to describe the following $k-k_\TA+1$ components of word statistics.
$$ W_{\kpa} \;=\; W_{\kpa0} \oplus W_{\kpa1} \oplus \dots \oplus W_{\kpa(k-k_\TA)} $$
The next theorem asserts that the word statistics in~$W_{\kpa r}$ have order of magnitude~$n^{-r/2}$, and that different components $W_{\kpa r}$ and $W_{\kpa r'}$ are asymptotically uncorrelated. By writing $\mathbf{n}/n \to \mathbf{p}$ we denote the assumption that the parameters $\mathbf{n} = (n_\TA,n_\TB,\dots)$ grow such that $n_{\TX}/n \to p_{\TX}>0$ as $n = |\mathbf{n}| \to \infty$, for every~$\TX$.

\begin{thm}
[Grading under $\mathcal{W}'(n_\TA, n_\TB, n_\TC, \dots)$]
$ $ 
\label{main3}\label{thm:main3}
\\[0.25em]
Let $f \in W_{\kpa r}$ be a nonzero statistic of composition $\kpa = (k_\TA,k_\TB,\dots)$ where $r \in \left\{0,\dots,|\kpa|-k_\TA\right\}$, and suppose that $\mathbf{n}/n \to \mathbf{p}$. Then, there exists $C'_{f,\mathbf{p}} > 0$ such that
$$ n^r \, \Exp_{\,\mathcal{W}' (\mathbf{n})}\left[\left(\tilde\#f\right)^2\right] \; \xrightarrow[\;n\to \infty\;]{}\; C'_{f,\mathbf{p}}\;. $$
Moreover, for every $r' \neq r$ and $f' \in W_{\kpa r'}$
$$ \Exp_{\,\mathcal{W}'(\mathbf{n})}\left[\left(n^{r/2}\,\tilde\#f\right)\left(n^{r'/2}\,\tilde\#f'\right)\right] \;\xrightarrow[\;n\to \infty\;]{}  \; 0 \;.$$
\end{thm}

\begin{rmk*}
The components $W_{\kpa 0},W_{\kpa 1},W_{\kpa 2},\dots$ are pairwise orthogonal with respect to the standard inner product of $W_{\kpa}$, denoted $\langle-,-\rangle$. 
\end{rmk*}

\begin{rmk*}
Similar to the first random model, the random variables $\tilde \# f$ are \emph{generalized U-statistics of rank $r$}. See~\S2.13 in the full version~\cite{full}.
\end{rmk*}

\medskip

The next result elaborates on the two-sample random model $\mathcal{W}'(n_\TA,n_\TB)$. Here $w$ is a uniformly random word of length $n = n_\TA+n_\TB$ with $\#\TA(w)=n_\TA$ and $\#\TB(w)=n_\TB$, and we count all subwords of composition $\kpa=(k_\TA,k_\TB)$ with $k_\TA \geq k_\TB \geq 1$, where $k = |\kpa| = k_\TA + k_\TB$. The primary decomposition of $W_{\kpa}$ already gives the components $W_{\kpa r}$ for $r \in \{0,\dots,k_\TB\}$.

The full decomposition of $W_{\kpa}$ is defined in \S2.11 in~\cite{full}, where we refine every $W_{\kpa r}$ into $(k-2r+1)r$ orthogonal subspaces as follows:
\begin{align*}
&W_{\kpa r} \;=\; \bigoplus_{i=0}^{k-2r} \; \bigoplus_{j=0}^{r-1} \; W_{\kpa rij} \;\;\;\;\;\;\;\;\;\; r \in \{1,\dots,k_\TB\} \\[0.5em]
&\dim W_{\kpa rij} \;=\; \frac{(k-2r-i+j+1)\,(k-i-j-2)!}{(k-i-r)!\,(r-j-1)!} \end{align*}
We do not consider the case $r=0$, because $W_{\kpa 0}$ is simply the 1-dimensional space of constant statistics.

This decomposition yields the following full asymptotic diagonalization of the covariance matrix. In writing $f \in W_{\kpa rij}$ it is implied that $r,i,j$ are any numbers in the applicable ranges $r \in \{1,\dots,k_\TB\}$, $i \in \{0,\dots,k-2r\}$, and $j\in\{0,\dots,r-1\}$, where as usual $k=k_\TA+k_\TB$ and $n=n_\TA+n_\TB$.

\begin{samepage}
\begin{thm}[Spectrum under $\mathcal{W}'(n_\TA,n_\TB)$] $ $ \label{main4 nisayon}
\label{main4}
\label{thm:main4}
\nopagebreak
\\[0.25em]
Let $\kpa=(k_\TA,k_\TB)$. For every two word statistics $f \in W_{\kpa rij}$ and $f' \in W_{\kpa r'i'j'}$
$$ \Exp_{\,w\in\mathcal{W}(n_\TA,n_\TB)}\left[ \left(\left(\tfrac{n_\TA n_\TB}{n}\right)^{r/2} \tilde\#f \right)\;\left( \left(\tfrac{n_\TA n_\TB}{n}\right)^{r'/2} \tilde\#f'\right) \right] \;\;\; \xrightarrow[\;\;n_\TA,n_\TB \;\to\; \infty\;\;]{} \;\;\; \Lambda_{\kpa rij} \left\langle f,f' \right\rangle $$
where 
$$ \Lambda_{\kpa rij} \;:=\; \frac{(k_\TA!)^2\,(k_\TB!)^2\,(k-2r)!\,(k-2r+1)!}{(k_\TA-r)!\,(k_\TB-r)!\,i!\,(2k-r-i-j)!\,(k-2r+1+j)!} \vspace{0.5em} $$
In particular, if $(r',i',j') \neq (r,i,j)$ then this limit is $\left\langle f,f' \right\rangle = 0$.
\end{thm}
\end{samepage}

\begin{rmk*}
This spectral decomposition of $W_{\kpa r}$ does not depend on $p_\TA$ and $p_\TB$, if these are respectively the limits of $n_\TA/n$ and $n_\TB/n$ as in Theorem~\ref{main3}. This remarkable property is not true in general, in the case of three samples or more.

In fact, the limit in this theorem is taken with respect to any $n_\TA$ and $n_\TB$ such that $\min(n_\TA,n_\TB) \to \infty$. This is a relaxation of the assumption of Theorem~\ref{main3} that $n_\TX/n$ converges to a positive constant $p_\TX$ for every~$\TX \in \Sigma$. For this reason, the formulation of Theorem~\ref{main4} restates the case~$r \neq r'$.
\end{rmk*}

\section{Decompositions}
\label{decompo}

The purpose of this short section is to give some general idea what goes into the decompositions of Theorems~\ref{main1}-\ref{main4}. Again, all the details are available in the full version~\cite{full}.

In Theorem~\ref{main1}, the primary components $W_{kr}$, giving the scaling of the statistics in $W_k$, rely on an orthogonal decomposition $\mathbb{R}\Sigma = \mathbb{R}\Ti \oplus (\Ti^{\perp})$ depending on~$\mathbf{p}$, and the structure it induces on $W_k \cong (\mathbb{R}\Sigma)^{\otimes k}$. In Theorem~\ref{main3}, the primary decomposition of $W_{\kpa}$ uses the structure induced by the $S_k$ action, where the different components $W_{\kpa r}$ correspond to submodules of the different Young diagram ``widths''.

The secondary decompositions that diagonalize the covariances are defined in terms of a set of linear operators in the words algebra, that has been studied and developed in a recent line of work~\cite{reiner2014spectra, dieker2018spectral}. The operators $\del$, $\sh$, $\shp$, and $\Theta$ respectively perform deletion, insertion, lifting, and replacement, of letters in formal sums of words. The decompositions of Theorems~\ref{main2} and~\ref{main4} can be expressed as
\begin{align*}
& W_{krm} \;=\; \sh_\Ti^{k-r-m}\ker \left( \del_\Ti{\big |}_{\displaystyle W_{(r+m)r}} \right) \\
& W_{\kpa rij} \;=\; \Theta_{\TA\TB}^{k_b-r}\;\shp_\TB^j \;\, \sh_\TA^i \,\ker\left(\del_\TA {\big |}_{\displaystyle W_{(k_\TA+k_\TB-r-i,r-j),r-j}} \right) 
\end{align*}

The relation of operators in the words algebra to terms of a certain order in the covariance of subword statistics is not immediate, and the translation requires considerable combinatorial effort. The resulting expressions for the leading terms are often quite intricate, and our analysis combines the existing knowledge on the words algebra and representations with some new techniques and ideas.

\section{Examples}
\label{examples}

We list a variety of examples for subword statistics, as special cases of our treatment. We examine how they are scaled and classified by the scheme of Theorems~\ref{main1}-\ref{main4}. All the computations of the decompositions and second moments are straightforward from the definitions and can be done automatically. 

We keep the discussion brief as our main purpose is not to study these particular examples, but demonstrate how various statistics from diverse contexts unify under one framework. Nevertheless, in several cases our perspective sheds a new light on them, or points to potential generalizations. The full version at~\cite{full} discusses additional examples from the combinatorial literature, such as the \emph{discrete L\'evy area} of a random walk on the grid, and the problem of \emph{intransitive dice}.

\smallskip
\begin{ex}
Warm Up: Coin Flips
\end{ex}
\noindent
A sequence of $n$ tosses of a fair coin gives a word in $\{\THH,\TTT\}^n$, distributed by $\mathcal{W}(n,(\tfrac12,\tfrac12))$. The decomposition for $k=1$ gives $W_{10} =  \SPAN\{\THH+\TTT\}$ and $W_{11} =  \SPAN\{\THH-\TTT\}$. As Theorem~\ref{main1} claims, the former yields $\bar\#(\THH+\TTT) \equiv 1$ of constant order. The latter, of order $1/\sqrt{n}$, is the ``observed bias'' of the coin under the fairness hypothesis. 

Computing for $k=2$: $W_{20}\; = \SPAN\{\THH\THH+\THH\TTT+\TTT\THH+\TTT\TTT\}$, $W_{210} = \SPAN\{\THH\THH-\TTT\TTT\}$, $W_{211} = \SPAN\{\THH\TTT-\TTT\THH\}$, $W_{220} = \SPAN\{\THH\THH+\TTT\TTT-\THH\TTT-\TTT\THH\}$.

The first two come from $W_{10}$ and $W_{11}$ via the embedding $W_1 \hookrightarrow W_2$. The new statistic $\bar\#(\THH\TTT-\TTT\THH)$ may be interpreted as the tendency of tails to occur after heads. It also scales as $1/\sqrt{n}$, but Theorem~\ref{main2} implies that its variance is $\tfrac13$ of that of $\bar\#(\THH\THH-\TTT\TTT)$, and these two statistics are uncorrelated. By \S2.13 in~\cite{full}, their joined distribution is asymptotically binormal. The fourth statistic scales as~$1/n$ and leads to the next example.

\smallskip
\begin{ex}
Pearson's $\chi^2$ Test Statistic
\end{ex}
\noindent
The following holds up to a \emph{constant} correction of smaller order in~$n$:
$$ \bar\#(\THH\THH+\TTT\TTT-\THH\TTT-\TTT\THH)\;=\; 2\bar\#(\THH\THH+\TTT\TTT)-1 \;\approx\; \frac{ (\bar\#\THH - 0.5)^2}{0.5} + \frac{(\bar\#\TTT - 0.5)^2}{0.5} $$ 
This is the classical Pearson's $\chi^2$ test statistic for fitting the frequencies of $\THH$ and $\TTT$ to the distribution $(0.5,0.5)$~\cite{pearson1900criterion}. This fact extends to any finite-dimensional distribution vector~$\mathbf{p}$. The combination $\sum_{\TX}\bar\# \TX\TX/p_{\TX} - 1$, which is essentially Pearson's $\chi^2$ statistic, always lies in~$W_{220}$. 

\smallskip
\begin{ex}
Functions on the Boolean Hypercube
\end{ex}
\noindent
Consider a binary stream $w \in \{\To,\Ti\}^n$, distributed with $\mathcal{W}(n,(p,q))$. The subword statistics of $w$ correspond to $\mathbb{R}\{\To,\Ti\}^k$, or equivalently Boolean functions $f:\{\To,\Ti\}^k \to \mathbb{R}$, so they take the form $\sum_u f(u)\,\bar\#u$. 
The primary decomposition of $\mathbb{R}\{\To,\Ti\}^k$ follows the so-called ``slices'' of the Fourier basis of Boolean functions. Namely, we expand all the ``monomials'' with $k-r$ times $(\To+\Ti)$ and $r$ times $(q\,\To-p\,\Ti)$ to obtain $\tbinom{\mathsmaller{k}}{r}$ combinations that span $W_{kr}$. For example, the expansion of $(q\,\To-p\,\Ti)^k$ from $W_{kk}$ gives the most concentrated statistic, with variance~$\sim k!/n^k$ by Theorems~\ref{main1}-\ref{main2}. For $p=q=\tfrac12$, it is the bias of the parities of $k$-bit subwords of~$w$.
The diagonalization in each slice introduces a finer decomposition into orthogonal subspaces, corresponding to the above-mentioned special orthogonal polynomials.
For example, in order $1/\sqrt{n}$ we obtain the basis $\{P_i(1)f_1 + \dots + P_i(k)f_k\}_{0 \leq i < k}$, where $f_1,\dots,f_k$ are so-called ``dictatorship'' functions, and $P_i(x)$ are the orthogonal polynomials of the uniform measure on~$\{1,\dots,k\}$. As $n$ grows, these $k$ statistics tend to independent Gaussian distributions.

\smallskip

\begin{ex}
Two-Sample Statistical Tests
\label{statistical}
\end{ex}
\noindent
Consider two real-valued samples $X_1,\dots,X_n$ and $Y_1,\dots,Y_m$ drawn independently from unknown continuous distributions, denoted by the random variables $X$ and~$Y$. The relative order of the observations induces a word $w$ over $\{\TX,\TY\}$ of length~$n+m$. For example, if $X_2 < Y_3 < Y_1 < X_1 < Y_2$ then $w=\TX\TY\TY\TX\TY$. If the two distributions coincide, $X \sim Y$, then $w$~is exactly as in the random model~$\mathcal{W}'(n,m)$. This is the null hypothesis of several nonparametric tests for comparing two distributions. 

Persson~\cite{persson1979new} represents several two-sample test statistics in terms of subword counts in~$w$. We review these statistics below.

\textbf{Mann--Whitney U \cite{mann1947test}.} 
This test statistic, $U = \#\TY\TX$ estimates how much $P(Y<X)$ deviates from $1/2$ for randomly selected $X$ and~$Y$. The equivalent combination $u = (\TY\TX - \TX\TY)/2$ lies in the component $W_{\kpa 1}$ where $\kpa=(1,1)$. The null distribution of~$\tilde\#u$ is asymptotically normal with variance ${\tfrac{1}{12}}(\tfrac{1}{m} + \tfrac{1}{n})$, reproduced by Theorems~\ref{main3}-\ref{main4}.

\textbf{Cram\'er--von Mises criterion~\cite{lehmann1951consistency}.}
The above $U$ might fail to detect $X \not\sim Y$ when the probability of $X<Y$ happens to be exactly~$1/2$. However, given four independent replications $X$, $X'$, $Y$, and $Y'$, the probability that $\max(X,X')<\min(Y,Y')$ or $\max(Y,Y')<\min(X,X')$ is $1/3$ if and only if $X \sim Y$. Otherwise, it is greater than $1/3$ by an $L^2$ difference between the distribution functions $F_X$ and~$F_Y$. This difference can be estimated by $2\,\tilde\#t$ for the following centralized combination in $W_{(2,2)}$:
$$ t \;=\; \tfrac13(\TX\TX\TY\TY + \TY\TY\TX\TX) - \tfrac16(\TX\TY\TY\TX + \TY\TX\TX\TY + \TX\TY\TX\TY + \TY\TX\TY\TX) $$
Theorems~\ref{main3}-\ref{main4} give $t \in W_{(2,2)201}$ and $\Var[\tilde\#t] \;\sim\; \tfrac{1}{45}(\tfrac{1}{m} + \tfrac{1}{n})^2$ in agreement with~\cite{anderson1962distribution}.

\textbf{Watson's $U^2$ \cite{watson1962goodness}.}
Now suppose that $\{X_i\}$ and $\{Y_i\}$ are samples on the circle~$S^1$. In this case, the previous test for $X \sim Y$ depends on an arbitrary choice of a starting point. Another notion of difference by Watson can be estimated by $\tilde\#s$, for the following \emph{rotation invariant} combination.
$$ s \;=\; \tfrac{1}{12}(\TX\TX\TY\TY + \TY\TY\TX\TX + \TX\TY\TY\TX + \TY\TX\TX\TY) - \tfrac16(\TX\TY\TX\TY + \TY\TX\TY\TX) $$
This is not a principal direction of the covariance, but $s = v + \tfrac14 t$ for $v \in W_{(2,2)200}$ and so $W_{(2,2)2} = \SPAN\{s,t\}$. By Theorem~\ref{main4}, $\Var[\tilde\#v] \sim \tfrac{1}{720}(\tfrac{1}{m} + \tfrac{1}{n})^2$, so $\Var[\tilde\#s] \sim \tfrac{1}{360}(\tfrac{1}{m} + \tfrac{1}{n})^2$.

\begin{rmk*}
A~surprising connection between Watson's test statistic and the size distribution of $(s,t)$-core partitions has been discovered in~\cite{ekhad2015explicit}, and further unfolded in~\cite{even2020sizes} based on this perspective of subword counts.
\end{rmk*}

We mention the possibility of similarly analyzing Cram\'er--von Mises type tests for the classical $K$-sample problem~\cite{kiefer1959k, puri1965some}. It is also possible to study such functionals with higher $L_p$~norms of $(F_X-F_Y)$ as word statistics. This may be interesting because the infinity norm gives another popular two-sample test by Kolmogorov--Smirnov.

\smallskip
\begin{ex}
Path Signature and Machine Learning
\end{ex}
\noindent 
Finally, we describe a potential application to machine learning, which will be investigated in future work. In many application areas the data takes the form of a long random-like text over a finite alphabet. This may either be a stream of symbols, that comes with a natural ordering or ``time'' parameter, or a mixture of $d$ samples of real-valued data points, as in Example~\ref{statistical}. Suppose that one wishes to classify, model, estimate a parameter, or learn a function of such sequences, say by applying a neural network. Then, the input sequence first has to be summarized as a vector of \emph{characteristic features}, of reasonable length. 

The \emph{signature method} is a generic way of extracting feature sets for sequential data. The basic idea is to embed the data as a path $[0,1] \to \mathbb{R}^d$, and then to use features from its \emph{signature}, which is the graded sequence of its iterated integrals. The coordinates of the signature are definite integrals of the path $(x_t,y_t,\dots)_{0\leq t \leq 1}$ such as $\int_{t}dx_t$, $\int_{t}dy_t$, $\int_{t<s}dx_tdx_s$, $\int_{t<s}dx_tdy_s$, and so on. This method has achieved success in several recent machine learning applications to financial data, clinical symptoms, handwriting recognition, and more \cite[for overviews]{levin2013learning, chevyrev2016primer}. The notion of path signature originates in the fundamental theory of rough paths \cite{chen1958integration, lyons1998differential}.

Though the signature method has mostly been applied to vector-valued time series and spatial data, also a text over $d$ symbols naturally embeds as a path in $\mathbb{R}^d$. Every appearance of a letter $\TX$ contributes a unit step along the axis that corresponds to~$\TX$. The signature of the resulting path is essentially the set of subword statistics in the given text, where the $k$th level corresponds to subwords of $k$ letters.

Now, our results on the diagonalization of the space of subword statistics provide a suitable choice of basis for feature selection in the signature. Such a basis may be crucial for addressing several important challenges, such as how and where to truncate the coordinates of the signature, how to adjust input parameters in specific applications, how to interpret the contribution of the various characteristic features, etc. 

One prediction we would like to make is that our suggested basis of attributes will actually be most beneficial for \emph{highly noisy} data, since our decomposition diagonalizes the joint distribution under randomness. Then, it seems particularly preferable to use a basis of uncorrelated features that distinguishes between statistics that scale differently with the data length.

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
