# On the Uniform Distribution of
Regular Expressions

Sabine Broda  António Machiavelo  Nelma Moreira  Rogério Reis
CMUP & DM-DCC, Faculdade de Ciências da Universidade do Porto,
Rua do Campo Alegre, 4169-007 Porto, Portugal
<EMAIL_ADDRESS>
###### Abstract

Although regular expressions do not correspond univocally to regular
languages, it is still worthwhile to study their properties and algorithms.
For the average case analysis one often relies on the uniform random
generation using a specific grammar for regular expressions, that can
represent regular languages with more or less redundancy. Generators that are
uniform on the set of expressions are not necessarily uniform on the set of
regular languages. Nevertheless, it is not straightforward that asymptotic
estimates obtained by considering the whole set of regular expressions are
different from those obtained using a more refined set that avoids some large
class of equivalent expressions. In this paper we study a set of expressions
that avoid a given absorbing pattern. It is shown that, although this set is
significantly smaller than the standard one, the asymptotic average estimates
for the size of the Glushkov automaton for these expressions does not differ
from the standard case.

##  1 Introduction

Average-case studies often rely on uniform random generation of inputs. In
general, those inputs correspond to trees, and generators are uniform on the
set of these trees, but not on the set that those inputs represent (such as
languages or boolean functions). Koechlin et al. [7, 8] studied expressions
that have subexpressions which are (semantically) absorbing for a given
operator, calling them _absorbing patterns_. For instance, $(a+b)^{\star}$ is
absorbing for the union of regular expressions over the alphabet $\\{a,b\\}$,
since $\alpha+(a+b)^{\star}$, or $(a+b)^{\star}+\alpha$, is equivalent to
$(a+b)^{\star}$ for any expression $\alpha$. After repeatedly applying the
induced simplification, in the example above replacing $\alpha+(a+b)^{\star}$
by $(a+b)^{\star}$, the resulting expression can be significantly smaller. For
uniformly random generated expressions of a given size, Koechlin et al. showed
that the expression resulting from this simplification has constant expected
size. That result led the authors to the conclusion that uniform random
generated regular expressions lack expressiveness, and in particular that
uniform distribution should not be used to study the average case complexity
in the context of regular languages. This conclusion is misleading in at least
two aspects. First, as pointed out above, one is considering regular
expressions and not regular languages themselves. For instance, if one wants
to estimate the size of automata obtained from regular expressions, one
disregards whether they represent the same language or not. What is implied by
the results of Koechlin et al. is that, if one uniformly random generates
regular expressions, one cannot expect to obtain, with a reasonable
probability, regular languages outside a constant set of languages. This means
that a core set of regular languages have so many regular expression
representatives that the remaining languages very scarcely appear. While
neither regular expressions ($\operatorname{RE}$) nor nondeterministic finite
automata (NFA) behave uniformly when representing regular languages, it is
known that deterministic automata (DFA) are a better choice, in the uniform
model, as they are asymptotically minimal [10]. In this sense, minimal DFAs
are a perfect model for regular languages. However, in practice, regular
expressions are usually preferred as a representation of regular languages,
and are used in a non-necessarily simplified form. Moreover, all of these
objects ($\operatorname{RE}$s, NFAs, and DFAs) are combinatorial objects per
se that can have their behaviour, as well as of the algorithms having them as
input, studied on average and asymptotically. One should not confuse regular
expressions by themselves with the languages that they represent. Second, the
results of Koechlin et al. do not imply that asymptotic estimates obtained by
considering the whole set of regular expressions are different from those
obtained by using a more refined set with less equivalent expressions. For
instance, some results obtained for expressions in strong star normal form
coincide with the ones for standard regular expressions [2]. In order to
further sustain the above claim, in this paper we consider the set
$\operatorname{\mathsf{R}}$ of regular expressions avoiding an absorbing
pattern which extends the pattern in the example above and was the one
considered by Koechlin et al. It is shown that, although the set
$\operatorname{\mathsf{R}}$ is significantly smaller than the set
$\operatorname{RE}$, the asymptotic estimates for the size of the Glushkov
automaton on these sets is the same. Given the complexity of the grammars
expressing the classes here studied, we had to deal with algebraic curves and
polynomials of degree depending on the size of the alphabet, $k$, which
brought up challenges that are new, as far as we know. Not only we had to use
the techniques developed in our previous work [3], but also some non-trivial
estimates using Stirling approximation, and some asymptotic equivalence
reductions in order to obtain the asymptotic estimates, and their limits with
$k$.

##  2 The analytic tools

Given some measure of the objects of a combinatorial class, $\mathcal{A}$, for
each $n\in\mathbb{N}_{0}$, let $a_{n}$ be the sum of the values of this
measure for all objects of size $n$. Now, let $A(z)=\sum_{n}a_{n}z^{n}$ be the
corresponding generating function (_cf_. [5]). We will use the notation
$[z^{n}]A(z)$ for $a_{n}$. The generating function $A(z)$ can be seen as a
complex analytic function. When this function has a unique dominant
singularity $\rho$, the study of the behaviour of $A(z)$ around it gives us
access to the asymptotic form of its coefficients. In particular, if $A(z)$ is
analytic in some indented disc neighbourhood of $\rho$, then one has the
following [5, Corol. VI.1, p. 392]:

######  Theorem 1.

The coefficients of the series expansion of the complex function $f(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$z\\!\to\\!\rho$}}}}$}\;\lambda\,\left(1-\frac{z}{\rho}\right)^{\nu},$
where $\nu\in\mathbb{C}\setminus\mathbb{N}_{0}$, $\lambda\in\mathbb{C}$, have
the asymptotic approximation
$[z^{n}]f(z)=\frac{\lambda}{{\rm\Gamma}(-\nu)}\,n^{-\nu-1}\rho^{-n}+o\left(n^{-\nu-1}\rho^{-n}\right)$.
Here ${\rm\Gamma}$ is, as usual, the Euler’s gamma function and the notation
$f(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$z\\!\to\\!z_{0}$}}}}$}\;g(z)$
means that $\lim\limits_{z\to z_{0}}\frac{f(z)}{g(z)}=1$.

###  2.1 Regular Expressions

Given an alphabet $\Sigma=\\{\sigma_{1},\ldots,\sigma_{k}\\}$, the set
$\operatorname{RE}$ of (standard) _regular expressions_ , $\beta$, over
$\Sigma$ contains $\emptyset$ and the expressions defined by the following
grammar:

$\displaystyle\beta$ $\displaystyle:=$
$\displaystyle\varepsilon\mid\sigma\in\Sigma\mid(\beta+\beta)\mid(\beta\cdot\beta)\mid(\beta^{\star}).$
(1)

The _language_ associated to $\beta$ is denoted by $\mathcal{L}(\beta)$ and
defined as usual (with $\varepsilon$ representing the empty word). Two
expressions $\beta_{1}$ and $\beta_{2}$ are _equivalent_ ,
$\beta_{1}=\beta_{2}$, if $\mathcal{L}(\beta_{1})=\mathcal{L}(\beta_{2})$. The
_(tree-)size_ $|\beta|$ of $\beta\in\operatorname{RE}$ is the number of
symbols in $\beta$ (disregarding parentheses). The _alphabetic size_
$|\beta|_{\Sigma}$ is the number of letters occurring in $\beta$. The
generating function of $\operatorname{RE}$ is
$B_{k}(z)=\sum_{\beta\in\operatorname{RE}}z^{|\beta|}=\sum_{n>0}b_{n}z^{n}$,
where $b_{n}$ is the number of expressions of size $n$,cf. [9, 1]. From
grammar (1) one gets $B_{k}(z)=(k+1)z+2zB_{k}(z)^{2}+zB_{k}(z)$. Considering
the quadratic equation this yields
$B_{k}(z)=\frac{1-z-\sqrt{1-2z-(7+8k)z^{2}}}{4z}.$ To use Theorem 1 one needs
to obtain the singularity, $\rho$, as well as the constants $\nu$ and
$\lambda$. Following Broda et al [1, 3], we have

$B_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$z\\!\to\\!\rho_{k}$}}}}$}\;-\frac{\sqrt{2-2\rho_{k}}}{4\rho_{k}}\left(1-\frac{z}{\rho_{k}}\right)^{\frac{1}{2}},$

where the singularity $\rho_{k}=\frac{1}{1+\sqrt{8+8k}}$ is the positive root
of $p_{k}(z)=1-2z-(7+8k)z^{2}$. Thus, applying Theorem 1 and noting that
$\Gamma(-\frac{1}{2})=\sqrt{\pi}$, the number of expressions of size $n$ is
asymptotically given by

$[z^{n}]B_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{\sqrt{2-2\rho_{k}}}{8\rho_{k}\sqrt{\pi}}\,n^{-\frac{3}{2}}\,\rho_{k}^{-n},$
(2)

where we use the notation
$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$ instead of
$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n\\!\to\\!\infty$}}}}$
.

##  3 Regular Expressions without $\Sigma^{\star}$ in Unions

We consider the set $\operatorname{\mathsf{R}}$ of all regular expressions
$\alpha$ such that $\Sigma^{\star}$ does not occur in an union. Here
$\Sigma^{\star}$ denotes any expression
$(\sigma_{i_{1}}+\cdots+\sigma_{i_{k}})^{\star}$ where
$\sigma_{i_{1}},\ldots,\sigma_{i_{k}}$ is a permutation of $\Sigma$. Note that
$\Sigma^{\star}$ represents an absorbing pattern in the sense of [7], i.e.
$(\alpha+\Sigma^{\star})=(\Sigma^{\star}+\alpha)=\Sigma^{\star}$, and that
$\operatorname{\mathsf{R}}$ still generates all regular languages over
$\Sigma$. We first consider $\Sigma=\\{a,b\\}$, for which we have the
following grammar $\mathcal{G}_{2}$ for $\operatorname{\mathsf{R}}$.

$\displaystyle\alpha$ $\displaystyle:=$ $\displaystyle\varepsilon\mid a\mid
b\mid(\alpha\cdot\alpha)\mid(\alpha^{\star})\mid(\alpha_{P}+\alpha_{P})$ (3)
$\displaystyle\alpha_{P}$ $\displaystyle:=$ $\displaystyle\varepsilon\mid
a\mid
b\mid(\alpha\cdot\alpha)\mid(\alpha_{\Sigma}^{\star})\mid(\alpha_{P}+\alpha_{P})$
$\displaystyle\alpha_{\Sigma}$ $\displaystyle:=$ $\displaystyle\varepsilon\mid
a\mid b\mid(\alpha\cdot\alpha)\mid(\alpha^{\star})\mid\gamma$
$\displaystyle\gamma$ $\displaystyle:=$
$\displaystyle(\alpha_{ab}+\alpha_{ab})\mid(\alpha_{ab}+a)\mid(\alpha_{ab}+b)\mid(a+\alpha_{ab})\mid(b+\alpha_{ab})\mid(a+a)\mid(b+b)$
$\displaystyle\alpha_{ab}$ $\displaystyle:=$
$\displaystyle\varepsilon\mid(\alpha\cdot\alpha)\mid(\alpha_{\Sigma}^{\star})\mid(\alpha_{P}+\alpha_{P}).$

The set of expressions generated by the nonterminals of $\mathcal{G}_{2}$,
are, respectively,

$\displaystyle[\\![\,\alpha\,]\\!]$ $\displaystyle=$
$\displaystyle\operatorname{\mathsf{R}},$
$\displaystyle[\\![\,\alpha_{P}\,]\\!]$ $\displaystyle=$
$\displaystyle\\{\,\alpha\in\operatorname{\mathsf{R}}\mid\alpha\not=(a+b)^{\star}\wedge\alpha\not=(b+a)^{\star}\,\\},$
$\displaystyle[\\![\,\alpha_{\Sigma}\,]\\!]$ $\displaystyle=$
$\displaystyle\\{\,\alpha\in\operatorname{\mathsf{R}}\mid\alpha\not=(a+b)\wedge\alpha\not=(b+a)\,\\},$
$\displaystyle[\\![\,\gamma\,]\\!]$ $\displaystyle=$
$\displaystyle\\{\,(\alpha_{1}+\alpha_{2})\in\operatorname{\mathsf{R}}\mid\\{\alpha_{1},\alpha_{2}\\}\not=\\{a,b\\}\,\\},$
$\displaystyle[\\![\,\alpha_{ab}\,]\\!]$ $\displaystyle=$
$\displaystyle\\{\,\alpha\in[\\![\,\alpha_{P}\,]\\!]\mid\alpha\not=a\wedge\alpha\not=b\,\\}.$

In particular, we obtain the correctness of $\mathcal{G}_{2}$.

######  Lemma 2.

An expression $\alpha\in\operatorname{RE}$ is generated by $\mathcal{G}_{2}$
if and only the absorbing pattern $(a+b)^{\star}$ or $(b+a)^{\star}$ does not
occur in a union.

Let $R_{2}(z)$ denote the generating function for the class
$\operatorname{\mathsf{R}}$ when $|\Sigma|=2$. It follows from
$\eqref{eq:reg}$ that $R_{2}(z)=3z+zR_{2}(z)^{2}+zR_{2}(z)+zR_{P}(z)^{2},$
where $R_{P}(z)$ is the generating function for the class of expressions
generated by $\alpha_{P}$. Comparing $[\\![\,\alpha\,]\\!]$ and
$[\\![\,\alpha_{P}\,]\\!]$, one observes that the only expressions not
generated by $\alpha_{P}$ are $(a+b)^{\star}$ and $(b+a)^{\star}$, which are
both of size $4$. Thus, $R_{P}(z)=R_{2}(z)-2z^{4}.$ In general, for an
arbitrary alphabet $\Sigma=\\{\sigma_{1},\ldots,\sigma_{k}\\}$, the
expressions $\alpha\in\operatorname{\mathsf{R}}$ satisfy the following grammar
$\mathcal{G}_{k}$

$\displaystyle\alpha$ $\displaystyle:=$
$\displaystyle\varepsilon\mid\sigma_{1}\mid\cdots\mid\sigma_{k}\mid(\alpha\cdot\alpha)\mid(\alpha^{\star})\mid(\alpha_{P}+\alpha_{P}),$
(4)

where
$[\\![\,\alpha_{P}\,]\\!]=\\{\,\alpha\in\operatorname{\mathsf{R}}\mid\alpha\not=(\sigma_{i_{1}}+\cdots+\sigma_{i_{k}})^{\star}\wedge\\{\sigma_{i_{1}},\ldots,\sigma_{i_{k}}\\}=\Sigma\,\\}.$
As before, we obtain the following two equations for the corresponding
generating functions, where $(k-1)!\binom{2k-2}{k-1}$ denotes the number of
expression $(\sigma_{i_{1}}+\cdots+\sigma_{i_{k}})^{\star}$ with
$\\{\sigma_{i_{1}},\ldots,\sigma_{i_{k}}\\}=\Sigma$, each of which has size
$2k$.

$\displaystyle R_{k}(z)$ $\displaystyle=$
$\displaystyle(k+1)z+zR_{k}(z)^{2}+zR_{k}(z)+zR_{P,k}(z)^{2},$ (5)
$\displaystyle R_{P,k}(z)$ $\displaystyle=$ $\displaystyle
R_{k}(z)-(k-1)!\binom{2k-2}{k-1}z^{2k}.$ (6)

In the next section, the asymptotic estimates of $[z^{n}]R_{k}(z)$ are
computed.

###  3.1 Asymptotic Estimates for the Number of Expressions in
$\operatorname{\mathsf{R}}$

The generating function $R_{k}=R_{k}(z)$ satisfies the following equation:

$2zR_{k}^{2}-r_{k}R_{k}+zs_{k}=0,$ (7)

where

$\displaystyle r_{k}=r_{k}(z)$ $\displaystyle=$ $\displaystyle
1-z+2z^{2k+1}C_{k},$ $\displaystyle s_{k}=s_{k}(z)$ $\displaystyle=$
$\displaystyle 1+k+z^{4k}C_{k}^{2},$ $\displaystyle C_{k}$ $\displaystyle=$
$\displaystyle\binom{2k-2}{k-1}(k-1)!=\frac{(2k-2)!}{(k-1)!}.$

The discriminant of equation (7) is
$\Delta_{k}=\Delta_{k}(z)=p_{k}(z)+4z^{2k+1}C_{k}h_{k}(z),$ where

$\displaystyle p_{k}=p_{k}(z)$ $\displaystyle=$ $\displaystyle
1-2z-(7+8k)z^{2},$ $\displaystyle h_{k}=h_{k}(z)$ $\displaystyle=$
$\displaystyle 1-z-C_{k}\,z^{2k+1}.$

Thus,

$R_{k}=R_{k}(z)=\frac{r_{k}-\sqrt{\Delta_{k}}}{4z},$ (8)

where the choice of the sign is determined by noticing that
$r_{k}(0)=\Delta_{k}(0)=1$. Let us now show that $R_{k}(z)$ has a unique
determinant singularity in the interval $]0,1[$, for all $k$. The ideia is to
use the fact that the polynomial $p_{k}(z)$ has only one positive zero, namely
$\rho_{k}$, use Rouché’s Theorem to show that, in the disk
$|z|<\frac{1}{\sqrt{8+8k}}$, the polynomial $\Delta_{k}(z)$ has exactly one
root in that disk, and finally show that that unique root is real. We recall
that Rouché’s Theorem states that, in particular, for polynomials $f(z)$ and
$g(z)$ such that $|f(z)-g(z)|<|f(z)|+|g(z)|$ holds for all $|z|=R$, in the
complex plane, then $f(z)$ and $g(z)$ have the same number of roots, taking
into account multiplicities, in the disk $|z|<R$ [11, Thm 3.3.4]. In order to
estimate $|\Delta_{k}(z)-p_{k}(z)|$, we start by noticing that from Stirling
approximation, $\sqrt{2\pi}\,n^{n+\frac{1}{2}}e^{-n}\leq n!\leq
n^{n+\frac{1}{2}}e^{1-n}$, valid for all $n\in\mathbb{N}$, one gets that, for
all $k\geq 2$,

$\frac{\sqrt{2\pi}\,(2k-2)^{2k-\frac{3}{2}}\,e^{2-2k}}{(k-1)^{k-\frac{1}{2}}\,e^{2-k}}\leq
C_{k}=\frac{(2k-2)!}{(k-1)!}\leq\frac{(2k-2)^{2k-\frac{3}{2}}\,e^{3-2k}}{\sqrt{2\pi}\,(k-1)^{k-\frac{1}{2}}\,e^{1-k}},$

i.e.,

$\frac{\sqrt{2\pi}\,2^{2k-\frac{3}{2}}(k-1)^{k-1}}{e^{k}}\leq
C_{k}\leq\frac{2^{2k-\frac{3}{2}}(k-1)^{k-1}}{\sqrt{2\pi}\,e^{k-2}}.$ (9)

Therefore, for $|z|=\frac{1}{\sqrt{8+8k}}$,

$\displaystyle|\Delta_{k}(z)-p_{k}(z)|$ $\displaystyle\leq$ $\displaystyle
4C_{k}\frac{1}{(8+8k)^{k+\frac{1}{2}}}\,|h_{k}(z)|$ $\displaystyle\leq$
$\displaystyle\frac{(k-1)^{k-1}}{\sqrt{2\pi}\,e^{k-2}\,2^{k+1}(k+1)^{k+\frac{1}{2}}}\left(1-\frac{1}{\sqrt{8+8k}}-\frac{C_{k}}{(8+8k)^{k+\frac{1}{2}}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1.48}{(2e)^{k}(k-1)\sqrt{k+1}}\left(1-\frac{1}{\sqrt{8+8k}}-\frac{C_{k}}{(8+8k)^{k+\frac{1}{2}}}\right).$

Noticing that, from (9), one has

$\frac{\sqrt{2\pi}\,(k-1)^{k-1}}{e^{k}2^{k+3}(k+1)^{k+\frac{1}{2}}}\leq\frac{C_{k}}{(8+8k)^{k+\frac{1}{2}}}\leq\frac{(k-1)^{k-1}}{\sqrt{2\pi}\,e^{k-2}2^{k+3}(k+1)^{k+\frac{1}{2}}}\,,$

one concludes that $\lim\limits_{k\to\infty}|\Delta_{k}(z)-p_{k}(z)|=0$.

Let us now find the minimum of $|p_{k}(z)|$ on the circunference
$|z|=\frac{1}{\sqrt{8+8k}}=R$. Put $z=Re^{i\theta}$. One has

$\displaystyle|p_{k}(z)|^{2}$ $\displaystyle=$
$\displaystyle|1-2Re^{i\theta}-(7+8k)R^{2}e^{2i\theta}|^{2}$ $\displaystyle=$
$\displaystyle(1-2R\cos\theta-(7+8k)R^{2}\cos
2\theta)^{2}+(1-2R\sin\theta-(7+8k)R^{2}\sin 2\theta)^{2}$ $\displaystyle=$
$\displaystyle
2+4R^{2}+(7+8k)^{2}R^{4}-4R(\cos\theta+\sin\theta)-2(7+8k)R^{2}(\cos
2\theta+\sin 2\theta)$ $\displaystyle+4R^{3}(7+8k)(\cos\theta\cos
2\theta+\sin\theta\sin 2\theta)$ $\displaystyle=$ $\displaystyle
2+\frac{1}{2+2k}+\left(\frac{7+8k}{8+8k}\right)^{2}-\frac{2(\cos\theta+\sin\theta)}{\sqrt{2+2k}}-\frac{(7+8k)(\cos
2\theta+\sin 2\theta)}{4+4k}$ $\displaystyle+\frac{(7+8k)(\cos\theta\cos
2\theta+\sin\theta\sin 2\theta)}{4(k+1)\sqrt{2+2k}}.$

It follows that $\lim\limits_{k\to\infty}|p_{k}(z)|^{2}=3-2(\cos 2\theta+\sin
2\theta)$. Since $\max\limits_{\theta}(\cos\theta+\sin\theta)=\sqrt{2}$, one
concludes that $\lim\limits_{k\to\infty}|p_{k}(z)|^{2}\geq 3-2\sqrt{2}>0$.
From all this, one concludes that $|\Delta_{k}(z)-p_{k}(z)|<|p_{k}(z)|$ for
large enough values of $k$, and so Rouché’s Theorem applies to show that the
polynomial $\Delta_{k}(z)$ has exactly one root in the open disk
$|z|<\frac{1}{\sqrt{8+8k}}$. 111It is actually true that
$|\Delta_{k}(z)-p_{k}(z)|<|p_{k}(z)|$ for all $|z|=\frac{1}{\sqrt{8+8k}}$ and
$k\geq 2$. Since $\Delta_{k}(0)=1$, in order to show that that root must be
real it suffices to show that one has
$\Delta_{k}\left(\frac{1}{\sqrt{8+8k}}\right)<0$. This can be shown as
follows. Since

$\displaystyle\Delta_{k}\left(\frac{1}{\sqrt{8+8k}}\right)$ $\displaystyle=$
$\displaystyle
2^{-6k-\frac{7}{2}}(k+1)^{-2k-1}\left(2^{3k+2}\left(4\sqrt{k+1}-\sqrt{2}\right)(k+1)^{k}C_{k}\right.$
$\displaystyle\left.-4\sqrt{2}\,C_{k}^{2}-64^{k}\left(8\sqrt{k+1}-\sqrt{2}\right)(k+1)^{2k}\right),$

we want to show that

$2^{3k}\left(\sqrt{8k+8}-1\right)(k+1)^{k}C_{k}<C_{k}^{2}+2^{6k-2}\left(2\sqrt{8k+8}-1\right)(k+1)^{2k}.$

Using (9), it is enough to show that

$\displaystyle\frac{2^{k}e^{k+2}\left(\sqrt{8k+8}-1\right)}{\sqrt{\pi}}<2^{2k}\left(2\sqrt{8k+8}-1\right)\frac{(k+1)^{k}}{(k-1)^{k-1}}e^{2k}+\pi\frac{(k-1)^{k-1}}{(k+1)^{k}},$

that follows from this trivially true inequality

$\displaystyle\frac{\sqrt{8k+8}-1}{\sqrt{\pi}}<2^{k}\left(2\sqrt{8k+8}-1\right)\frac{(k+1)^{k}}{(k-1)^{k-1}}e^{k-2}.$

The singularity of $R_{k}(z)$ is therefore given by the unique root of
$\Delta_{k}(z)$ in the interval $\left]0,\frac{1}{\sqrt{8k+8}}\right[$, which
will henceforth denote by $\eta_{k}$. It also follows from Rouché’s Theorem
that this root has multiplicity one. Now,
$\Delta_{k}(z)=\left(1-\frac{z}{\eta_{k}}\right)\psi_{k}(z)$, for some
$\psi_{k}(z)\in\mathbb{R}[z]$. Using L’Hôpital’s Rule, one has

$\psi_{k}(\eta_{k})=-\eta_{k}\Delta^{\prime}_{k}(\eta_{k}).$ (10)

Then, one has $R_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$z\\!\to\\!\eta_{k}$}}}}$}\;\frac{-r_{k}(\eta_{k})-\sqrt{\psi_{k}(\eta_{k})}\left(1-\frac{z}{\eta_{k}}\right)^{\frac{1}{2}}}{4\eta_{k}}.$
By Theorem 1, one gets the following asymptotic approximation for the number
of regular expressions

######  Theorem 3.

With the notations above, one has

$[z^{n}]R_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{\sqrt{\psi_{k}(\eta_{k})}}{8\eta_{k}\sqrt{\pi}}n^{-\frac{3}{2}}\eta_{k}^{-n}.$

Using (2), we have

######  Theorem 4.

The asymptotic ratio of the number of expressions in
$\operatorname{\mathsf{R}}$ and the number of expressions in
$\operatorname{RE}$ is given by,

$\frac{[z^{n}]R_{k}(z)}{[z^{n}]B_{k}(z)}\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{\frac{\sqrt{\psi_{k}(\eta_{k})}}{8\eta_{k}\sqrt{\pi}}n^{-\frac{3}{2}}\eta_{k}^{-n}}{\frac{\sqrt{2-2\rho_{k}}}{8\rho_{k}\sqrt{\pi}}\,n^{-\frac{3}{2}}\,\rho_{k}^{-n}}=\frac{\sqrt{\psi_{k}(\eta_{k})}}{\sqrt{2-2\rho_{k}}}\left(\frac{\rho_{k}}{\eta_{k}}\right)^{n+1}.$

Since, as seen before, $\eta_{k}>\rho_{k}$, for all $k$, this yields that, for
every $k$, this ratio tends to $0$ as $n\to\infty$. As such, considering
$\operatorname{\mathsf{R}}$ instead of $\operatorname{RE}$, actually avoids a
significant set of redundant expressions. Such an improvement, in the sense of
[7], might influence the results obtained by asymptotic studies. In the
following section we show that is not the case for the average asymptotic size
of the Glushkov automaton in terms of states and transitions [9, 1].

##  4 Asymptotic Average Size of the Glushkov Automaton

The Glushkov automaton [6] is constructed from an equivalent regular
expression $\beta$ using the set $\operatorname{{\mathsf{Pos}}}(\beta)$ of
positions of the letters in $\beta$, as the set of states (plus one initial
state). Let
$\operatorname{{\mathsf{Pos}}}(\beta)=\\{1,2,\ldots,|\beta|_{\Sigma}\\}$,
$\operatorname{{\mathsf{Pos}}}_{0}(\beta)=\operatorname{{\mathsf{Pos}}}(\beta)\cup\\{0\\}$
and $\overline{\beta}$ denote the expression obtained from $\beta$ by marking
each letter with its position in $\beta$. The construction is based on the
position sets $\operatorname{\mathsf{First}}(\beta)=\\{\,i\mid(\exists w)\
\sigma_{i}w\in\mathcal{L}(\overline{\beta})\,\\}$,
$\operatorname{\mathsf{Last}}(\beta)=\\{\,i\mid(\exists w)\
w\sigma_{i}\in\mathcal{L}(\overline{\beta})\,\\}$, and
$\operatorname{\mathsf{Follow}}(\beta)=\\{\,(i,j)\mid(\exists u,v)\
u\sigma_{i}\sigma_{j}v\in\mathcal{L}(\overline{\beta})\,\\}$. The _Glushkov
automaton_ for $\beta$ is
$\mathcal{A}_{\operatorname{POS}}(\beta)=\langle\operatorname{{\mathsf{Pos}}}_{0}(\beta),\Sigma,\delta_{\operatorname{POS}},0,F\rangle$
with the set of transitions
$\delta_{\operatorname{POS}}=\\{\,(0,\overline{\sigma_{j}},j)\mid
j\in\operatorname{\mathsf{First}}(\overline{\beta})\,\\}\cup\\{\,(i,\overline{\sigma_{j}},j)\mid\;(i,j)\in\operatorname{\mathsf{Follow}}(\overline{\beta})\,\\}$
and the set of final states
$F=\operatorname{\mathsf{Last}}(\overline{\beta})\cup\\{0\\}$ if
$\varepsilon\in\mathcal{L}(\beta)$, and
$F=\operatorname{\mathsf{Last}}(\overline{\beta})$, otherwise.

In the next subsection, we estimate the average number of letters in
$\alpha\in\operatorname{\mathsf{R}}$, i.e., the number of states of
$\mathcal{A}_{\operatorname{POS}}(\alpha)$. In the last subsection we consider
the number of transitions.

###  4.1 Estimates for the Number of Letters

The average number of letters in uniform random generated regular expressions
of a given size have been estimated for different kinds of expressions [9, 3].
For standard regular expressions that value is half the size of the
expressions as the size of the alphabet goes to $\infty$. In the following we
obtain the same value for expressions in $\operatorname{\mathsf{R}}$. To count
the number of letters in all expressions of a given size we use the bivariate
generating function $\mathcal{L}_{k}(u,z)=\sum_{n,i\geq 1}c_{n,i}u^{i}z^{n},$
where $c_{n,i}$ is the number of regular expressions of size $n$ with $i$
letters. Therefore, the total number of letters in all the regular expressions
of size $n$ is given by the coefficients of the sum of the two series

$L_{k}(z)=\frac{\partial\mathcal{L}_{k}(u,z)}{\partial
u}\bigg{|}_{u=1}=\sum_{n,i\geq 1}i\,c_{n,i}\,z^{n}.$

From grammar (4) the generating function $L_{k}(z)$ satisfies the following.

$\displaystyle L_{k}(z)$ $\displaystyle=$ $\displaystyle
kz+2zL_{k}(z)R_{k}(z)+zL_{k}(z)+2zP_{k}(z)R_{P}(z),$ (11) $\displaystyle
P_{k}(z)$ $\displaystyle=$ $\displaystyle L_{k}(z)-k!\binom{2k-2}{k-1}z^{2k}.$
(12)

Using equations (5),(6),(16),(12) and Buchberger’s algorithm [4] one obtains
the following equation, which is satisfied by the generating function
$L_{k}=L_{k}(z)$:

$\Delta_{k}L_{k}^{2}+\bar{r}_{k}L_{k}-\bar{s}_{k}=0,$ (13)

where

$\displaystyle\bar{r}_{k}$ $\displaystyle=$ $\displaystyle
kz^{2k}C_{k}\,\Delta_{k},$ $\displaystyle\bar{s}_{k}$ $\displaystyle=$
$\displaystyle
kz^{2}+k^{2}z^{2k+1}\,C_{k}\,\left((z-1)(1+2z^{4k+1}C_{k}^{2})+2C_{k}(2+k)+2z^{6k+1}C_{k}^{3}\right).$

The discriminant of equation (13) can be shown to be

$\bar{\Delta}_{k}(z)=z^{2}k^{2}\Delta_{k}(z)g_{k}(z)^{2},$ (14)

where

$g_{k}(z)=2-C_{k}z^{2k-1}\left(h_{k}(z)-C_{k}z^{2k-1}\right).$ (15)

Therefore,

$\displaystyle L_{k}(z)$ $\displaystyle=$
$\displaystyle\frac{kz^{2k}C_{k}\Delta_{k}(z)\pm\sqrt{\bar{\Delta}_{k}(z)}}{2\Delta_{k}(z)}=\frac{kz^{2k}C_{k}}{2}\pm\frac{kzg_{k}(z)}{2\sqrt{\Delta_{k}(z)}}.$

Using the fact that we know $L_{k}^{\prime}(0)=k$, one deduces that

$L_{k}(z)=\frac{kz^{2k}C_{k}}{2}+\frac{kzg_{k}(z)}{2\sqrt{\Delta_{k}(z)}}.$
(16)

Now, applying the procedure described in Broda et al. [3] one obtains:

######  Theorem 5.

With the same notations as above, where $\eta_{k}$ is as defined in page 3.1,

$[z^{n}]L_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{k\,\eta_{k}\,g_{k}(\eta_{k})}{2\sqrt{\pi}\sqrt{\psi_{k}(\eta_{k})}}n^{-\frac{1}{2}}\eta_{k}^{-n}.$

Therefore, from Theorems 3 and 5, one deduces:

######  Theorem 6.

The asymptotic ratio of letters in the expressions in
$\operatorname{\mathsf{R}}$ is given by

$\frac{[z^{n}]L_{k}(z)}{n[z^{n}]R_{k}(z)}\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{4k\,\eta_{k}^{2}\,g_{k}(\eta_{k})}{\psi_{k}(\eta_{k})}.$

Let us now see that

$\lim_{k\to\infty}k\,\eta^{2}_{k}=\frac{1}{8}.$ (17)

Since we know that $\Delta_{k}(0)=1$, and $\Delta_{k}(x)$ has exactly one real
root in the interval $\left[0,\frac{1}{\sqrt{8+8k}}\right]$, in order to show
that $\eta_{k}>\rho_{k}$ for all $k$, it is enough to show that:

$\Delta_{k}(\rho_{k})=p_{k}(\rho_{k})+4\rho_{k}^{2k+1}C_{k}h_{k}(\rho_{k})>0,\text{
i.e. }h_{k}(\rho_{k})>0.$

Now, $h_{k}(\rho_{k})>0\iff
1>\rho_{k}+C_{k}\rho_{k}^{2k+1}\iff\sqrt{8+8k}>\frac{C_{k}}{(1+\sqrt{8+8k})^{2k}}.$
From (9) it follows that

$\frac{C_{k}}{(1+\sqrt{8+8k})^{2k}}\leq\frac{2^{2k-\frac{3}{2}}(k-1)^{k-1}}{\sqrt{2\pi}\,e^{k-2}(1+\sqrt{8+8k})^{2k}}.$

It is therefore enough to show:

$\frac{2^{2k-\frac{3}{2}}(k-1)^{k-1}}{\sqrt{2\pi}\,e^{k-2}(1+\sqrt{8+8k})^{2k}}<\sqrt{8+8k},$

which is equivalent to

$2^{2k-\frac{3}{2}}(k-1)^{k-1}<\sqrt{2\pi}\,e^{k-2}(1+\sqrt{8+8k})^{2k}\sqrt{8+8k}.$

This is the same as

$\left(\frac{4}{e}\right)^{k}(k-1)^{k-1}<\frac{2^{\frac{3}{2}}\,\sqrt{2\pi}}{e^{2}}\,(1+\sqrt{8+8k})^{2k}\sqrt{8+8k},$

which follows from:

$\left(\frac{4}{e}\right)^{k}(k-1)^{k}<\frac{2^{\frac{3}{2}}\,\sqrt{2\pi}}{e^{2}}\,2^{2k+1}(2+2k)^{k+\frac{1}{2}}.$

That is obvious when rewritten as

$\left(\frac{4}{e}\right)^{k}(k-1)^{k}<\left(\frac{2^{\frac{3}{2}}\,\sqrt{2\pi}}{e^{2}}\,2\right)\,4^{k}(2+2k)^{k+\frac{1}{2}}.$

Thus, we conclude that

$\rho_{k}=\frac{1}{1+\sqrt{8+8k}}<\eta_{k}<\frac{1}{\sqrt{8+8k}}.$ (18)

From this it immediately follows that
$\lim\limits_{k\to\infty}k\,\eta^{2}_{k}=\frac{1}{8}$, and then
$\lim\limits_{k\to\infty}p_{k}(\eta_{k})=0$. Using the right hand inequality
in (9) together with (18), it is not hard to show the following result.

######  Lemma 7.

For all $t,s\in\mathbb{R}$, one has

$\lim_{k\to\infty}C_{k}k^{t}\eta_{k}^{2k+s}=0.$ (19)

From all this, and from (15) and (10), one easily gets
$\lim\limits_{k\to\infty}g_{k}(\eta_{k})=\lim\limits_{k\to\infty}\psi_{k}(\eta_{k})=2$,
and thus:

$\lim_{k\to\infty}\frac{4k\,\eta_{k}^{2}\,g_{k}(\eta_{k})}{\psi_{k}(\eta_{k})}=\frac{1}{2}.$
(20)

This means that the following result holds.

######  Theorem 8.

In regular expressions without $\Sigma^{\star}$ in unions, the asymptotic
ratio of letters goes to $\frac{1}{2}$ as $k$ goes to $\infty$.

###  4.2 Estimates for the Number of Transitions

The transitions of the Glushkov automaton are defined using the sets of
positions $\operatorname{\mathsf{First}}$, $\operatorname{\mathsf{Last}}$ and
$\operatorname{\mathsf{Follow}}$. These sets can be inductively define for
$\alpha\in\operatorname{\mathsf{R}}$, as it is usually done [1]. Let
$\alpha_{\varepsilon}\in\operatorname{\mathsf{R}}$ be the set of expressions
such that $\varepsilon\in\mathcal{L}(\alpha_{\varepsilon})$ and let
$\alpha_{\overline{\varepsilon}}$ represent the set of expressions such that
$\varepsilon\notin\mathcal{L}(\alpha_{\overline{\varepsilon}})$. We have that
those sets satisfy the following grammars:

$\displaystyle\alpha_{\varepsilon}$ $\displaystyle:=$
$\displaystyle\varepsilon\mid(\alpha_{\varepsilon}\cdot\alpha_{\varepsilon})\mid(\alpha^{\star})\mid(\alpha_{P,\varepsilon}+\alpha_{P})\mid(\alpha_{P,\overline{\varepsilon}}+\alpha_{P,\varepsilon})$
(21) $\displaystyle\alpha_{\overline{\varepsilon}}$ $\displaystyle:=$
$\displaystyle\sigma\in\Sigma\mid(\alpha_{\overline{\varepsilon}}\cdot\alpha)\mid(\alpha_{\varepsilon}\cdot\alpha_{\overline{\varepsilon}})\mid(\alpha_{P,\overline{\varepsilon}}+\alpha_{P,\overline{\varepsilon}}),$
(22)

where $\alpha_{P,\varepsilon}$ and $\alpha_{P,\overline{\varepsilon}}$
represent the expressions $\alpha_{P}$ such that
$\varepsilon\in\mathcal{L}(\alpha_{P,\varepsilon})$ and
$\varepsilon\notin\mathcal{L}(\alpha_{P,\overline{\varepsilon}})$,
respectively. Note that then $\alpha\in\in\operatorname{\mathsf{R}}$ could be
defined by: $\alpha:=\alpha_{\varepsilon}\mid\alpha_{\overline{\varepsilon}}$.
With this we have the following definitions.

$\displaystyle\begin{array}[]{lcl}\operatorname{\mathsf{First}}(\varepsilon)&=&\emptyset,\\\
\operatorname{\mathsf{First}}(\sigma_{i})&=&\\{i\\},\\\
\operatorname{\mathsf{First}}(\alpha^{\star})&=&\operatorname{\mathsf{First}}(\alpha),\end{array}$
$\displaystyle\begin{array}[]{lll}\operatorname{\mathsf{First}}(\alpha_{P}+\alpha_{P}^{\prime})&=&\operatorname{\mathsf{First}}(\alpha_{P})\cup\operatorname{\mathsf{First}}(\alpha_{P}^{\prime}),\\\
\operatorname{\mathsf{First}}(\alpha_{\varepsilon}\cdot\alpha)&=&\operatorname{\mathsf{First}}(\alpha_{\varepsilon})\cup\operatorname{\mathsf{First}}(\alpha),\\\
\operatorname{\mathsf{First}}(\alpha_{\overline{\varepsilon}}\cdot\alpha)&=&\operatorname{\mathsf{First}}(\alpha_{\overline{\varepsilon}}).\end{array}$

The definition of $\operatorname{\mathsf{Last}}$ is almost identical and
differs only for the case of concatenation, which is
$\operatorname{\mathsf{Last}}(\alpha\cdot\alpha_{\varepsilon})=\operatorname{\mathsf{Last}}(\alpha)\cup\operatorname{\mathsf{Last}}(\alpha_{\varepsilon})$
and
$\operatorname{\mathsf{Last}}(\alpha\cdot\alpha_{\overline{\varepsilon}})=\operatorname{\mathsf{Last}}(\alpha_{\overline{\varepsilon}})$.
Following Broda et al. [1] the set $\operatorname{\mathsf{Follow}}$ satisfies

$\displaystyle\operatorname{\mathsf{Follow}}(\varepsilon)$
$\displaystyle=\operatorname{\mathsf{Follow}}(\sigma_{i})=\emptyset,$
$\displaystyle\operatorname{\mathsf{Follow}}(\alpha_{P}+\alpha_{P}^{\prime})$
$\displaystyle=\operatorname{\mathsf{Follow}}(\alpha_{P})\cup\operatorname{\mathsf{Follow}}(\alpha_{P}^{\prime}),$
$\displaystyle\operatorname{\mathsf{Follow}}(\alpha\cdot\alpha^{\prime})$
$\displaystyle=\operatorname{\mathsf{Follow}}(\alpha)\cup\operatorname{\mathsf{Follow}}(\alpha^{\prime})\cup\operatorname{\mathsf{Last}}(\alpha)\times\operatorname{\mathsf{First}}(\alpha^{\prime}),$
$\displaystyle\operatorname{\mathsf{Follow}}(\alpha^{\star})$
$\displaystyle=\operatorname{\mathsf{E}^{\star}}(\alpha),\ \text{where}$
$\displaystyle\operatorname{\mathsf{E}^{\star}}(\varepsilon)$
$\displaystyle=\emptyset,\ \
\operatorname{\mathsf{E}^{\star}}(\sigma_{i})=\\{(i,i)\\},\ \
\operatorname{\mathsf{E}^{\star}}(\alpha^{\star})=\operatorname{\mathsf{E}^{\star}}(\alpha),$
$\displaystyle\operatorname{\mathsf{E}^{\star}}(\alpha_{P}+\alpha_{P}^{\prime})$
$\displaystyle=\operatorname{\mathsf{E}^{\star}}(\alpha_{P})\cup\operatorname{\mathsf{E}^{\star}}(\alpha_{P}^{\prime})\cup\operatorname{\mathsf{Cross}}(\alpha_{P},\alpha_{P}^{\prime}),$
$\displaystyle\operatorname{\mathsf{E}^{\star}}(\alpha_{\varepsilon}\cdot\alpha_{\varepsilon}^{\prime})$
$\displaystyle=\operatorname{\mathsf{E}^{\star}}(\alpha_{\varepsilon})\;\cup\;\operatorname{\mathsf{E}^{\star}}(\alpha_{\varepsilon}^{\prime})\;\cup\;\operatorname{\mathsf{Cross}}(\alpha_{\varepsilon},\alpha_{\varepsilon}^{\prime}),$
$\displaystyle\operatorname{\mathsf{E}^{\star}}(\alpha_{\varepsilon}\cdot\alpha_{\overline{\varepsilon}}^{\prime})$
$\displaystyle=\operatorname{\mathsf{Follow}}(\alpha_{\varepsilon})\;\cup\;\operatorname{\mathsf{Follow}}^{\star}(\alpha_{\overline{\varepsilon}}^{\prime})\;\cup\;\operatorname{\mathsf{Cross}}(\alpha_{\varepsilon},\alpha_{\overline{\varepsilon}}^{\prime}),$
$\displaystyle\operatorname{\mathsf{E}^{\star}}(\alpha_{\overline{\varepsilon}}\cdot\alpha_{\varepsilon}^{\prime})$
$\displaystyle=\operatorname{\mathsf{Follow}}^{\star}(\alpha_{\overline{\varepsilon}})\;\cup\;\operatorname{\mathsf{Follow}}(\alpha_{\varepsilon}^{\prime})\;\cup\;\operatorname{\mathsf{Cross}}(\alpha_{\overline{\varepsilon}},\alpha_{\varepsilon}^{\prime}),$
$\displaystyle\operatorname{\mathsf{E}^{\star}}(\alpha_{\overline{\varepsilon}}\cdot\alpha_{\overline{\varepsilon}}^{\prime})$
$\displaystyle=\operatorname{\mathsf{Follow}}(\alpha_{\overline{\varepsilon}})\;\cup\;\operatorname{\mathsf{Follow}}(\alpha_{\overline{\varepsilon}}^{\prime})\;\cup\;\operatorname{\mathsf{Cross}}(\alpha_{\overline{\varepsilon}},\alpha_{\overline{\varepsilon}}^{\prime}),$

with
$\operatorname{\mathsf{Cross}}(\alpha,\alpha^{\prime})=\operatorname{\mathsf{Last}}(\alpha)\times\operatorname{\mathsf{First}}(\alpha^{\prime})\cup\operatorname{\mathsf{Last}}(\alpha^{\prime})\times\operatorname{\mathsf{First}}(\alpha)$.

The generating functions for $\alpha_{\varepsilon}$ and
$\alpha_{\overline{\varepsilon}}$, respectively,
$R_{\varepsilon,k}(z)=R_{\varepsilon,k}$ and
$R_{\overline{\varepsilon},k}(z)=R_{\overline{\varepsilon},k}$, satisfy

$\displaystyle R_{\varepsilon,k}$ $\displaystyle=$ $\displaystyle
z+zR_{\varepsilon,k}^{2}+zR_{k}+2zR_{P,\varepsilon,k}R_{P,k}-zR_{P,\varepsilon,k}^{2},$
$\displaystyle R_{\overline{\varepsilon},k}$ $\displaystyle=$ $\displaystyle
R_{k}-R_{\varepsilon,k},$ $\displaystyle R_{P,\overline{\varepsilon},k}$
$\displaystyle=$ $\displaystyle R_{\overline{\varepsilon},k},$ $\displaystyle
R_{P,\varepsilon,k}$ $\displaystyle=$ $\displaystyle
R_{P,k}-R_{\overline{\varepsilon},k}=R_{\varepsilon,k}-C_{k}z^{2k}.$

From that we conclude that

$\displaystyle R_{\varepsilon,k}$ $\displaystyle=$ $\displaystyle
z+zR_{k}+zR_{P,k}^{2}-zR_{k}^{2}+2zR_{\varepsilon,k}R_{k}$ (24)

The function that counts the cardinality of
${\operatorname{\mathsf{First}}}(\alpha)$ is $\mathop{\textsf{f}}(\alpha)$ and
is defined as follows:

$\displaystyle\mathop{\textsf{f}}(\sigma_{i})$ $\displaystyle=1,$ (25)
$\displaystyle\mathop{\textsf{f}}(\alpha_{P}+\alpha_{P}^{\prime})$
$\displaystyle=\mathop{\textsf{f}}(\alpha_{P})+\mathop{\textsf{f}}(\alpha_{P}^{\prime}),$
$\displaystyle\mathop{\textsf{f}}(\alpha_{\varepsilon}\cdot\alpha^{\prime})$
$\displaystyle=\mathop{\textsf{f}}(\alpha_{\varepsilon})+\mathop{\textsf{f}}(\alpha^{\prime}),$
$\displaystyle\mathop{\textsf{f}}(\alpha_{\overline{\varepsilon}}\cdot\alpha^{\prime})$
$\displaystyle=\mathop{\textsf{f}}(\alpha_{\overline{\varepsilon}}),$
$\displaystyle\mathop{\textsf{f}}(\alpha^{\star})$
$\displaystyle=\mathop{\textsf{f}}(\alpha),$

Note that
$\mathop{\textsf{f}}((\sigma_{i_{1}}+\cdots+\sigma_{i_{k}})^{\star})=k$ for
any permutation $\sigma_{i_{1}},\ldots,\sigma_{i_{k}}$ of
$\Sigma=\\{\sigma_{1},\ldots,\sigma_{k}\\}$. The correspondent generating
function $F_{k}(z)=\sum_{\alpha}\mathop{\textsf{f}}(\alpha)z^{|\alpha|}=F_{k}$
satisfies the following equations

$\displaystyle F_{k}$ $\displaystyle=$ $\displaystyle
kz+zF_{k}+2zF_{P,k}R_{P,k}+zF_{k}R_{\varepsilon,k}+zF_{k}R_{k},$
$\displaystyle F_{P,k}$ $\displaystyle=$ $\displaystyle F_{k}-kC_{k}z^{2k},$
$\displaystyle R_{\varepsilon,k}$ $\displaystyle=$ $\displaystyle
z+zR_{k}+2zR_{\varepsilon,k}R_{k}+zC_{k}^{2}z^{4k}-2zR_{k}C_{k}z^{2k},$

Let $\mathop{\textsf{s}}(\alpha)$ be the function that counts the cardinality
of ${\operatorname{\mathsf{Last}}}(\alpha)$ and $S_{k}(z)$ the correspondent
generating function. By symmetry we have that $S_{k}(z)=F_{k}(z)$. The
functions counting the cardinalities of
$\operatorname{\mathsf{Follow}}(\alpha)$ and
$\operatorname{\mathsf{E}^{\star}}(\alpha)$ are $\mathop{\textsf{e}}(\alpha)$
and $\mathop{\textsf{e}}^{\star}(\alpha)$, respectively. Those functions are
defined as follows:

$\displaystyle\mathop{\textsf{e}}(\sigma)$
$\displaystyle=\mathop{\textsf{e}}(\varepsilon)=0,$ (26)
$\displaystyle\mathop{\textsf{e}}(\alpha_{P}+\alpha_{P}^{\prime})$
$\displaystyle=\mathop{\textsf{e}}(\alpha_{P})+\mathop{\textsf{e}}(\alpha_{P}^{\prime}),$
$\displaystyle\mathop{\textsf{e}}(\alpha\cdot\alpha^{\prime})$
$\displaystyle=\mathop{\textsf{e}}(\alpha)+\mathop{\textsf{e}}(\alpha^{\prime})+\mathop{\textsf{s}}(\alpha)\mathop{\textsf{f}}(\alpha^{\prime}),$
$\displaystyle\mathop{\textsf{e}}(\alpha^{\star})$
$\displaystyle={\mathop{\textsf{e}}}^{\star}(\alpha),$

where ${\mathop{\textsf{e}}}^{\star}(\alpha)$ is given by

$\displaystyle{\mathop{\textsf{e}}}^{\star}(\varepsilon)$
$\displaystyle=0,\text{\hphantom{mm}}{\mathop{\textsf{e}}}^{\star}(\sigma)=1,$
$\displaystyle{\mathop{\textsf{e}}}^{\star}(\alpha_{P}+\alpha_{P}^{\prime})$
$\displaystyle={\mathop{\textsf{e}}}^{\star}(\alpha_{P})+{\mathop{\textsf{e}}}^{\star}(\alpha_{P}^{\prime})+\mathop{\textsf{c}}(\alpha_{P},\alpha_{P}^{\prime}),$
$\displaystyle{\mathop{\textsf{e}}}^{\star}(\alpha_{\varepsilon}\cdot\alpha^{\prime}_{\varepsilon})$
$\displaystyle={\mathop{\textsf{e}}}^{\star}(\alpha_{\varepsilon})+{\mathop{\textsf{e}}}^{\star}(\alpha^{\prime}_{\varepsilon})+\mathop{\textsf{c}}(\alpha_{\varepsilon},\alpha^{\prime}_{\varepsilon}),$
$\displaystyle{\mathop{\textsf{e}}}^{\star}(\alpha_{\overline{\varepsilon}}\cdot\alpha^{\prime}_{\varepsilon})$
$\displaystyle={\mathop{\textsf{e}}}^{\star}(\alpha_{\overline{\varepsilon}})+\mathop{\textsf{e}}(\alpha^{\prime}_{\varepsilon})+\mathop{\textsf{c}}(\alpha_{\overline{\varepsilon}},\alpha^{\prime}_{\varepsilon}),$
$\displaystyle{\mathop{\textsf{e}}}^{\star}(\alpha_{{\varepsilon}}\cdot\alpha^{\prime}_{\overline{\varepsilon}})$
$\displaystyle=\mathop{\textsf{e}}(\alpha_{{\varepsilon}})+{\mathop{\textsf{e}}}^{\star}(\alpha^{\prime}_{\overline{\varepsilon}})+\mathop{\textsf{c}}(\alpha_{{\varepsilon}},\alpha^{\prime}_{\overline{\varepsilon}}),$
$\displaystyle{\mathop{\textsf{e}}}^{\star}(\alpha_{\overline{\varepsilon}}\cdot\alpha^{\prime}_{\overline{\varepsilon}})$
$\displaystyle=\mathop{\textsf{e}}(\alpha_{\overline{\varepsilon}})+\mathop{\textsf{e}}(\alpha^{\prime}_{\overline{\varepsilon}})+\mathop{\textsf{c}}(\alpha_{\overline{\varepsilon}},\alpha^{\prime}_{\overline{\varepsilon}}),$

with
$\mathop{\textsf{c}}(\alpha,\alpha^{\prime})=\mathop{\textsf{s}}(\alpha)\mathop{\textsf{f}}(\alpha^{\prime})+\mathop{\textsf{s}}(\alpha^{\prime})\mathop{\textsf{f}}(\alpha)$.
From the above the corresponding generating functions
$E_{k}(z)=\sum_{\alpha}\mathop{\textsf{e}}(\alpha)z^{|\alpha|}=E_{k}$ and
$E^{\star}_{k}(z)=\sum_{\alpha}\mathop{\textsf{e}}^{\star}(\alpha)z^{|\alpha|}=E_{k}^{\star}$,
respectively, satisfy the following equations.

$\displaystyle E_{k}$ $\displaystyle=$ $\displaystyle
2zE_{P,k}R_{P,k}+2zE_{k}R_{k}+zF_{k}^{2}+zE^{\star}_{k},$ $\displaystyle
E^{\star}_{k}$ $\displaystyle=$ $\displaystyle
kz+2zE_{P,k}^{\star}R_{P,k}+2zF_{P,k}^{2}+2zE^{\star}_{\varepsilon,k}R_{\varepsilon,k}+2zF_{\varepsilon,k}F_{\varepsilon,k}$
$\displaystyle+\
zE^{\star}_{\overline{\varepsilon},k}R_{\varepsilon,k}+zE_{\varepsilon,k}R_{\overline{\varepsilon},k}+2zF_{\varepsilon,k}F_{\overline{\varepsilon},k}+zE_{\varepsilon,k}R_{\overline{\varepsilon},k}$
$\displaystyle+\
zE^{\star}_{\overline{\varepsilon},k}R_{\varepsilon,k}+2zF_{\varepsilon,k}F_{\overline{\varepsilon},k}+2zE_{\overline{\varepsilon},k}R_{\overline{\varepsilon},k}+2zF_{\overline{\varepsilon},k}F_{\overline{\varepsilon},k}+zE^{\star}_{k}$
$\displaystyle=$ $\displaystyle
kz+2zE_{P,k}^{\star}R_{P,k}+2zE^{\star}_{k}R_{\varepsilon,k}+2zE_{k}(R_{k}-R_{\varepsilon,k})$
$\displaystyle+\ 2zF_{P,k}^{2}+2zF_{k}^{2}+zE^{\star}_{k},$ $\displaystyle
E_{P,k}$ $\displaystyle=$ $\displaystyle E_{k}-k^{2}C_{k}z^{2k},$
$\displaystyle E^{\star}_{P,k}$ $\displaystyle=$ $\displaystyle
E^{\star}_{k}-k^{2}C_{k}z^{2k}.$

The last two equations follow from the fact that
$\mathop{\textsf{e}}((\sigma_{i_{1}}+\cdots+\sigma_{i_{k}})^{\star})=\mathop{\textsf{e}}^{\star}((\sigma_{i_{1}}+\cdots+\sigma_{i_{k}})^{\star})=k^{2}$,
for any permutation $\sigma_{i_{1}},\ldots,\sigma_{i_{k}}$ of $\Sigma$. The
cost function
$\mathop{\textsf{t}}(\alpha)=\mathop{\textsf{f}}(\alpha)+\mathop{\textsf{e}}(\alpha)$
computes the number of transitions in the Glushkov automaton of $\alpha$. The
generating function associated to $\mathop{\textsf{t}}$ is given by
$T_{k}(z)=F_{k}(z)+E_{k}(z)$. Setting $w=T_{k}(z)$, one has

$c_{2}w^{2}+c_{1}w+c_{0}=0,$

where the $c_{i}=c_{i}(k,z)$. Therefore,

$w=\frac{-c_{1}\pm\sqrt{c_{1}^{2}-4c_{0}c_{2}}}{2c_{2}}.$

Now, one can see that $c_{1}=\Delta_{k}s_{k}$,
$c_{2}=\Delta_{k}a_{k}b_{k}^{2}$ and
$c_{1}^{2}-4c_{0}c_{2}=k^{2}\Delta_{k}q_{k}^{2},$ from which it follows that

$w=-\frac{s_{k}}{2a_{k}b_{k}^{2}}\pm\frac{kq_{k}}{2a_{k}b_{k}^{2}\sqrt{\Delta_{k}}}.$

With $\eta_{k}$ as defined in p.3.1, one can now deduce, as above, that

$T_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$z\to\eta_{k}$}}}}$}\;\frac{kq_{k}(\eta_{k})}{2a_{k}(\eta_{k})b_{k}(\eta_{k})^{2}\sqrt{\psi_{k}(\eta_{k})}}\left(1-\frac{z}{\eta_{k}}\right)^{\frac{1}{2}},$

and therefore

$[z^{n}]T_{k}(z)\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{kq_{k}(\eta_{k})}{2\sqrt{\pi}a_{k}(\eta_{k})b_{k}(\eta_{k})^{2}\sqrt{\psi_{k}(\eta_{k})}}\,\eta_{k}^{-n}n^{-\frac{1}{2}}.$

From all this, one gets:

$\frac{[z^{n}]T_{k}(z)}{[z^{n}]R_{k}(z)}\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$n$}}}}$}\;\frac{4k\eta_{k}q_{k}(\eta_{k})}{a_{k}(\eta_{k})b_{k}(\eta_{k})^{2}\psi_{k}(\eta_{k})}\,n.$

With the help of a symbolic and numeric computing system one can explicitly
find out the polynomials222These polynomials are quite large, e.g. $q_{k}$ has
$437$ monomials and degree $10+28k$. $a_{k}$, $b_{k}$, $q_{k}$, and then
reducing them modulo $\Delta_{k}$ (which has $\eta_{k}$ as a root), and then
using Lemma 7 and (17), one obtains:

$a_{k}(\eta_{k})\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$k$}}}}$}\;\frac{1}{2}k\eta_{k}\quad;\quad
b_{k}(\eta_{k})\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$k$}}}}$}\;\frac{1}{8}k\eta_{k}\quad;\quad
q_{k}(\eta_{k})\;\lower
6.0pt\hbox{$\stackrel{{\scriptstyle\mbox{\Large$\sim$}}}{{\mbox{\tiny{$k$}}}}$}\;\frac{1}{2048}k.$

This yields

$\lim_{k\to\infty}\frac{4k\eta_{k}q_{k}(\eta_{k})}{a_{k}(\eta_{k})b_{k}(\eta_{k})^{2}\psi_{k}(\eta_{k})}=1.$

We have thus obtained the following result.

######  Theorem 9.

For expressions of size $n$ over an alphabet of size $k$, the number of
transitions in the Glushkov automaton for regular expressions, without
$\Sigma^{\star}$ in unions, is asymptotically, with respect to $n$, given by
$\lambda_{k}n$, where $\lim\limits_{k\to\infty}\lambda_{k}=1$.

To grasp the progression of $\lambda_{k}$, observe that $\lambda_{2}=4.03$,
$\lambda_{5}=2.91$, $\lambda_{10}=2.30$, $\lambda_{10}=1.89$,
$\lambda_{50}=1.54$, $\lambda_{100}=1.38$, $\lambda_{10000}=1.03$. Theorems 8
and 9 show that the size of the Glushkov automaton, both in states and
transitions, is, on average and asymptotically, independent of whether we
consider all regular expressions or the restricted set
$\operatorname{\mathsf{R}}$ mentioned by Koechlin et al.

#### Acknowledgments

This work was partially supported by CMUP, through FCT – Fundação para a
Ciência e a Tecnologia, I.P., under the project with reference
UIDB/00144/2020.

## References

  * [1] Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average size of Glushkov and partial derivative automata. Int. J. Found. Comput. Sci. 23(5), 969–984 (2012)
  * [2] Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On average behaviour of regular expressions in strong star normal form. Int. J. Found. Comput. Sci. 30(6-7), 899–920 (2019)
  * [3] Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Analytic combinatorics and descriptional complexity of regular languages on average. ACM SIGACT News 51(1), 38–56 (March 2020)
  * [4] Buchberger, B.: Gröbner bases: A short introduction for systems theorists. In: Computer Aided Systems Theory - EUROCAST. pp. 1–19 (2001)
  * [5] Flajolet, P., R.Sedgewick: Analytic Combinatorics. CUP (2008)
  * [6] Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys 16(5), 1–53 (1961)
  * [7] Koechlin, F., Nicaud, C., Rotondo, P.: Uniform random expressions lack expressivity. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th MFCS 2019. LIPIcs, vol. 138, pp. 51:1–51:14 (2019)
  * [8] Koechlin, F., Nicaud, C., Rotondo, P.: On the degeneracy of random expressions specified by systems of combinatorial equations. In: Jonoska, N., Savchuk, D. (eds.) 24th DLT 2020. LNCS, vol. 12086, pp. 164–177. Springer (2020)
  * [9] Nicaud, C.: On the average size of Glushkov’s automata. In: Dediu, A., Ionescu, A.M., Vide, C.M. (eds.) 3rd LATA. LNCS, vol. 5457, pp. 626–637. Springer (2009)
  * [10] Nicaud, C.: Random deterministic automata. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 5–23. Springer (2014)
  * [11] Simon, B.: Basic Complex Analysis, vol. 2A. American Mathematical Society (2015)


# Concentration of quantum equilibration and an estimate of the recurrence
time

Jonathon Riddell<EMAIL_ADDRESS>Department of Physics &
Astronomy, McMaster University, 1280 Main St. W., Hamilton ON L8S 4M1, Canada.
Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada
Nathan J. Pagliaroli<EMAIL_ADDRESS>Department of Mathematics, Western
University, 1151 Richmond St, London ON N6A 3K7, Canada  Álvaro M. Alhambra
<EMAIL_ADDRESS>Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-
Straße 1, D-85748 Garching, Germany

###### Abstract

We show that the dynamics of generic quantum systems concentrate around their
equilibrium value when measuring at arbitrary times. This means that the
probability of finding such values away from that equilibrium is exponentially
suppressed, with a decay rate given by the effective dimension. Our result
allows us to place a lower bound on the recurrence time of quantum systems,
since recurrences corresponds to the rare events of finding a state away from
equilibrium. In many-body systems, this bound is doubly exponential in system
size. We also show corresponding results for free fermions, which display a
weaker concentration and earlier recurrences.

Closed quantum systems obey the Schrödinger equation, so that their dynamics
are both unitary and reversible. Most large systems, however, seem to quickly
evolve towards a steady state for long times, with only very small out-of-
equilibrium fluctuations around it. This process is usually called
_equilibration_ , and is associated with the emergence of statistical physics
Gogolin and Eisert (2016); Ueda (2020). The equilibrated or average
expectation value of an observable $A$ is

$\overline{\langle
A\rangle}=\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}\langle
A(t)\rangle,$ (1)

where $\langle A(t)\rangle=\bra{\Psi}e^{-iHt}Ae^{iHt}\ket{\Psi}$ for some
initial state $\Psi$ and Hamiltonian $H$.

If a system equilibrates, it is because the probability of finding $\langle
A(t)\rangle$ very close to $\langle\overline{\langle A\rangle}\rangle$ at any
given time is overwhelmingly large. We show that this is indeed the case: the
dynamics of quantum systems with a _generic_ spectrum concentrate highly
around the steady-state value $\langle\overline{\langle A\rangle}\rangle$.

More specifically, we show that when sampling times at random $t\in[0,\infty)$
the probability of finding the system away from equilibrium is exponentially
suppressed. The decay rate of that exponential is given by the _effective
dimension_ or _inverse participation ratio_. This is defined as
$\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1}$, where $\omega$
is the diagonal ensemble

$\omega=\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}e^{-iHt}\ket{\Psi}\bra{\Psi}e^{iHt},$
(2)

which is such that
$\operatorname{\textnormal{Tr}}\left[{A\omega}\right]=\overline{\langle
A\rangle}$. A similar result to what we here prove was argued to hold as a
consequence of the ETH in Srednicki (1999).

That this equilibration happens, leaving little or no memory from the initial
conditions, seems to conflict with the unitarity and reversibility of the
dynamics. This conflict can be seen by considering the Poincaré recurrence
theorem in quantum mechanics Bocchieri and Loinger (1957); Percival (1961);
Hogg and Huberman (1982); Duvenhage (2002); Wallace (2015), which states that
any closed quantum evolution eventually returns arbitrarily close to its
initial state.

The solution to this problem is that even if the initial state is eventually
recovered to an arbitrarily good approximation, this only happens at extremely
long times. These recurrences constitute large out-of-equilibrium
fluctuations, that can be understood as the rare events of finding a system
far from its equilibrated state.

Based on this idea, we show how a lower bound on the average spacing between
recurrences follows from our concentration results, as the inverse of the tail
bound. We find that recurrences occur at time intervals that are at least
exponential in the effective dimension. This gives a mathematically rigorous
scaling on the average recurrence time, that matches the scaling of previous
estimates Bhattacharyya and Mukherjee (1986) and exact calculations Venuti
(2015a). See Hogg and Huberman (1983); Peres (1982) for other related results.

We also show equivalent results for free fermion Hamiltonians with generic
single-particle modes. We find that under the assumption of extensivity in the
single particle eigenstates a similar concentration bound and recurrence time
result hold, but with a slower exponential scaling on the lattice size. This
shows the markedly different behaviour with respect to generic models. See
Table 1 for a summary.

| $\langle A(t)\rangle$ | $|\bra{\Psi}e^{-itH}\ket{\Psi}|^{2}$
---|---|---
Generic | $e^{\Omega\left(\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1/2}\right)}$ | $e^{\Omega\left(\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1}\right)}$
Free | $e^{\Omega\left(\sqrt{L}\right)}$ | $e^{\Omega\left(L\right)}$
Table 1: Lower bounds on the recurrence time for different dynamical
quantities. $\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1}$ is
the effective dimension of a system with generic spectrum and $L$ is the
number of sites in a fermionic lattice. In the free case, the observable and
initial state are restricted to specific forms. See below for the precise
statements.

Our results constitute a qualitative improvement over previous bounds on out-
of-equilibrium fluctuations Reimann (2008); Linden  _et al._ (2009); Reimann
and Kastner (2012) for systems with a generic spectrum. These only focused on
the variance induced by the probability measure
$\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}$, while we are able
to analyze arbitrarily high moments thereof. The improvement is exponential in
the same sense in which the Chernoff-Hoeffding bound is exponentially better
than Chebyshev’s inequality.

##  I Concentration bound

We consider functions of time $f(t)$ that track some physical property of
interest. In the cases here, $f(t)=\langle A(t)\rangle$ is the expectation
value of a time-evolved operator $A(t)$. This allows us to define the moments
of a probability distribution

$\displaystyle\overline{f}$
$\displaystyle\equiv\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}f(t),$
(3)
$\displaystyle\mu_{q}\equiv\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}\left(f(t)-\overline{f}\right)^{q}.$
(4)

These moments are bounded for arbitrary $q$ as $\mu_{q}\leq(2||A||)^{q}$. This
means that they uniquely determine a characteristic function with an infinite
radius of convergence

$\phi(\lambda)=\sum_{q}\frac{\mu_{q}\lambda}{q!}.$ (5)

This function defines a probability distribution, which we can write formally
as

$P(x)=\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}\delta(x-f(t)).$
(6)

Here $P(x)$ should be understood as the probability that, if we pick a random
time $t\in[0,\infty)$, the value of $f(t)$ is exactly $x$ (see also Venuti and
Zanardi (2010) and Venuti (2015b) for an overview of previous results). Note
that in order to compute $\int x^{q}P(x)dx$ the limit in $T$ is swapped with
the integral in $x$. For justification of this see Appendix A. An example of
$P(x)$ forming for $f(t)=\langle A(t)\rangle$ is given in Fig. 1. Fig. 1 shows
how averaging over a finite interval gives concentrated distributions around
equilibrium. The distribution becomes sharper as we increase the length of
time being averaged over.

Figure 1: Convergence of $P_{T}(x)$ to $P(x)$ where
$P_{T}(x)=\int_{0}^{T}\frac{\text{d}t}{T}\delta(x-\langle A(t)\rangle)$ and
$P(x)$ is recovered as $T\to\infty$. $\tilde{P}_{T}(x)$ represents the
approximation of $P_{T}(x)$ by binning samples and constructing a histogram.
1000 bins were used to create this histogram. Numerics were performed on a
spin 1/2 chain with 22 sites. The data is normalized such that
$\int_{-\infty}^{\infty}\tilde{P}_{T}(x)dx=1$. The Hamiltonian is a Heisenberg
type model with nearest and next nearest neighbour interactions. The
parameters in the Hamiltonian are chosen so that we have a non-integrable
model. Further details can be found in App. D.

Below we prove that the moments $\mu_{q}$ are bounded by

$\kappa_{q}\leq\left(qg\right)^{q},$ (7)

where $g$ is some small quantity, decreasing quickly as the size of the system
grows and such that $g\rightarrow 0$ in the thermodynamic limit. A bound of
this form implies that the distribution concentrates highly around the
average, as per the following elementary lemma.

######  Lemma 1.

Let $|\mu_{q}|\leq\left(qg\right)^{q}$ for $q$ even. Then,

$\displaystyle\mathrm{Pr}\left[\big{|}f(t)-\overline{f}\big{|}\geq\delta\right]\leq
2e\times\exp\left(-\frac{\delta}{eg}\right).$ (8)

###### Proof.

Let us set $\overline{f}=0$ for simplicity, and focus on the case
$x\geq\delta$. We have that

$\displaystyle\mathrm{Pr}\left[\langle A(t)\rangle\geq\delta\right]$
$\displaystyle=\int_{x\geq\delta}P(x)\text{d}x$ (9)
$\displaystyle\leq\frac{1}{\delta^{q}}\int_{x\geq\delta}x^{q}P(x)\text{d}x$
(10) $\displaystyle\leq\frac{\mu_{q}}{\delta^{q}}$ (11)
$\displaystyle\leq\left(\frac{qg}{\delta}\right)^{q}.$ (12)

A similar inequality holds for $x\leq-\delta$, so that
$\mathrm{Pr}\left[\big{|}f(t)\big{|}\geq\delta\right]\leq
2\left(\frac{qg}{\delta}\right)^{q}$. The bound is obtained by choosing
$q=\lfloor\frac{\delta}{eg}\rfloor$. ∎

We now simply need to find the corresponding $g$ for the concentration bound
to hold, which we do for various physical problems.

##  II Generic models

First we consider models governed by a Hamiltonian
$H=\sum_{m=1}^{D}E_{m}|E_{m}\rangle\langle E_{m}|$, which we assume to have a
discrete and _generic_ spectrum.

######  Definition 1.

Let $H$ be a Hamiltonian with spectrum
$H=\sum_{j}E_{j}\ket{E_{j}}\bra{E_{j}}$, and let
$\Lambda_{q},\Lambda^{\prime}_{q}$ be two arbitrary sets of $q$ energy levels
$\\{E_{j}\\}$. The spectrum of $H$ is generic if for all $q\in\mathbb{N}$ and
all $\Lambda_{q},\Lambda^{\prime}_{q}$, the equality

$\sum_{j\in\Lambda_{q}}E_{j}=\sum_{j\in\Lambda^{\prime}_{q}}E_{j}$ (13)

implies that $\Lambda_{q}=\Lambda^{\prime}_{q}$.

This condition is expected to hold in non-integrable and chaotic models, such
as those with Wigner-Dyson level statistics, and is otherwise expected to not
hold in integrable models. It has previously appeared in the literature under
various names Kaneko  _et al._ (2020); Mark  _et al._ (2022). It is an
extension of the well-known non-degenerate gaps condition, which is the $q=2$
case Gogolin and Eisert (2016); Short (2011), and also implies that the energy
spectrum is non-degenerate. A possible stronger condition, that implies Def.
1, is that of rational independence of the energy levels (see e.g. Goldstein
_et al._ (2006); Campos Venuti and Zanardi (2010)). Notably, the probability
of uniformly choosing a non-generic Hamiltonian is zero, as seen in the
following lemma.

######  Lemma 2.

For any positive integer $d\geq 2$, the set of $d\times d$ complex Hermitian
matrices that are not generic has Lebesgue measure zero.

The proof is a straightforward generalization of the $q=2$ case in Huang and
Harrow (2020) and can be found in Appendix B.

Consider $f(t)=\langle\psi|A(t)|\psi\rangle$ to be the pure state time
evolution of some observable $A$. The first concentration result is as
follows.

######  Theorem 1.

Let $H$ have a generic spectrum, with $\omega$ the diagonal ensemble, and
$||A||$ the largest singular value of $A$. The moments in Eq. 4 are such that

$\mu_{q}\leq\left(q||A||\sqrt{\mathrm{Tr}[\omega^{2}]}\right)^{q}.$ (14)

We thus have the bound

$\displaystyle\mathrm{Pr}$ $\displaystyle\left[\big{|}\langle
A(t)\rangle-\overline{\langle A\rangle}\big{|}\geq\delta\right]$ (15)
$\displaystyle\leq
2e\times\mathrm{exp}\left(-\frac{\delta}{e||A||\sqrt{\mathrm{Tr}[\omega^{2}]}}\right).$

This states that the probability of finding $\langle A(t)\rangle$ away from
$\overline{\langle A\rangle}$ even by a small amount is exponentially
suppressed in $\sqrt{\mathrm{Tr}[\omega^{2}]}$. It also rigorously proves one
of the main results from Srednicki (1999), where a similar concentration bound
was heuristically argued as a consequence of the ETH. Previous results Reimann
(2008); Short (2011) only yield the bound

$\mathrm{Pr}\left[\big{|}\langle A(t)\rangle-\overline{\langle
A\rangle}\big{|}\geq\delta\right]\leq\frac{||A||^{2}\mathrm{Tr}[\omega^{2}]}{\delta^{2}}.$
(16)

A particular observable of interest is the initial state itself,
$A=\ket{\Psi}\bra{\Psi}$. In this case, the quantity at hand is the fidelity
with the initial state

$F(t)=\bra{\Psi}e^{-itH}\ket{\Psi}\bra{\Psi}e^{itH}\ket{\Psi}.$ (17)

######  Theorem 2.

Let $H$ have a generic spectrum and let $A=\ket{\Psi}\bra{\Psi}$, then

$\mu_{q}\leq\left(q\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]\right)^{q}.$
(18)

Notably, assuming a generic spectrum, the average fidelity is
$\overline{F}=\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]$, so
that we have the concentration bound

$\displaystyle\mathrm{Pr}\left[\big{|}F(t)-\mathrm{Tr}[\omega^{2}]\big{|}\geq\delta\right]\leq
2e\times\mathrm{exp}\left(-\frac{\delta}{e\mathrm{Tr}[\omega^{2}]}\right).$
(19)

This improves on Eq. (15) by a factor of
$\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}$ when
substituted into $A=|\Psi\rangle\langle\Psi|$ and $||A||=1$. Eq. (18) appeared
previously in Campos Venuti and Zanardi (2010).

It is well known that
$\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]$ is exponentially
suppressed in system size for generic models for sufficiently well behaved
initial conditions. As an example, see figure 2, which shows a clear
exponential decay of $\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]$
with system size $L$.

Figure 2:  $\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]$ for a
variety of system sizes and states. Numerics were done with the same model as
Fig. 1 , which is non-integrable. The three states studied are
$|\psi\rangle\coloneqq|\uparrow\downarrow\uparrow\downarrow\dots..\rangle$,
$|\psi^{\prime}\rangle\coloneqq\frac{1}{\sqrt{2}}\left(|\uparrow\downarrow\uparrow\downarrow\dots..\rangle+|\downarrow\uparrow\downarrow\uparrow\dots..\rangle\right)$
and
$|\phi\rangle\coloneqq\frac{1}{\sqrt{L}}\sum_{r=0}^{L-1}\hat{T}^{r}|\uparrow\uparrow\dots\uparrow\downarrow\dots\downarrow\downarrow\rangle$
where $\hat{T}$ is the translation operator shifting lattice indices by one.
More details on the states and the model can be found in App. D.

##  III Free fermions

The second class that we consider are extended free fermionic models

$H=\sum_{m,n=1}^{L}M_{m,n}f_{m}^{\dagger}f_{n},$ (20)

where $f_{n}$ is a fermionic annihilation operator for the lattice site $n$.
The fermionic operators obey the standard canonical anti-commutation relations
$\\{f_{m},f_{n}\\}=\\{f_{m}^{\dagger},f_{n}^{\dagger}\\}=0,\enspace\\{f_{m}^{\dagger},f_{n}\\}=\delta_{m,n}$.
We assume $M$ is real symmetric, so it is diagonalized with a real orthogonal
matrix $O$ such that $M=ODO^{T}$. $D$ is a diagonal matrix with entries
$D_{k,k}=\epsilon_{k}$, which allows us to rewrite the Hamiltonian as

$H=\sum_{k=1}^{L}\epsilon_{k}d_{k}^{\dagger}d_{k},$ (21)

where $\epsilon_{k}$ are the single particle energy eigenmodes, and we have
new fermionic operators in eigenmode space defined in terms of the real space
fermionic operators: $d_{k}=\sum_{j=1}^{L}O_{j,k}f_{j}$. This class of models
notably does not obey Def. 1. However, we can instead give the following
definition.

######  Definition 2.

Let $H=\sum_{k=1}^{L}\epsilon_{k}d_{k}^{\dagger}d_{k}$ be a free Hamiltonian.
Let $\Lambda_{q},\Lambda^{\prime}_{q}$ be two arbitrary sets of $q$ eigenmodes
$\\{\epsilon_{j}\\}$. Then $H$ is an extended free fermionic model with a
generic spectrum if, for all $q\in\mathbb{N}$ and all
$\Lambda_{q},\Lambda^{\prime}_{q}$, the equality

$\sum_{j\in\Lambda_{q}}\epsilon_{j}=\sum_{j\in\Lambda^{\prime}_{q}}\epsilon_{j}$
(22)

implies that $\Lambda_{q}=\Lambda^{\prime}_{q}$ and the entries of $O$ are
such that

$O_{j,k}=\frac{c_{j,k}}{\sqrt{L}},$ (23)

with $c_{j,k}=\mathcal{O}(1)$.

Generic free extended models can be constructed relatively easily by imposing
translation invariance. Such models always have $O_{j,k}\propto 1/\sqrt{L}$.
One can then construct an eigenmode spectrum $\epsilon_{k}$ that is generic.
It would be interesting for future work to find local, or approximately local
examples of such a model.

The equivalent of Lemma 2 also holds here by applying it to the matrix $M$ and
the energy eigenmodes. This definition crucially excludes localized models,
which have entries of the form, $O_{m,k}\sim e^{-|k-m|/\xi}$, with $\xi$ the
localization length. The bound on the moments is as follows.

######  Theorem 3.

Let $H$ be an extended free fermionic Hamiltonian with generic spectrum and
let $A=f_{m}^{\dagger}f_{n}$. Then, for even $q$,

$\kappa_{q}\leq\left(qc^{2}\sqrt{\frac{\nu}{L}}\right)^{q},$ (24)

where $\nu=\frac{N}{L}$ is the filling factor of the fermions on the lattice
and $c=\sqrt{L}\max_{k_{j}}\\{O_{m,k_{j}},O_{n,k_{j}}\\}$.

The corresponding concentration bound is

$\displaystyle\mathrm{Pr}$ $\displaystyle\left[\big{|}\langle
f_{m}^{\dagger}f_{n}(t)\rangle-\overline{\langle
f_{m}^{\dagger}f_{n}\rangle}\big{|}\geq\delta\right]$ (25) $\displaystyle\leq
2e\times\mathrm{exp}\left(-\frac{\delta}{ec^{2}}\sqrt{\frac{L}{\nu}}\right).$

Theorem 3 can be contrasted with the bound found in Venuti and Zanardi (2013)
for the second moment. The authors consider a potentially extensive observable
and do not limit the analysis to extensive models, recovering
$\kappa_{2}\leq||a||^{2}\nu L$ for an observable
$A=\sum_{m,n}f^{\dagger}_{m}a_{m,n}f_{n}$.

The last quantity of interest is the single particle propagator

$\displaystyle\\{f_{m}^{\dagger}(t),f_{n}\\}=a_{m,n}(t).$ (26)

For example, if we initialize our state as
$|\Psi\rangle=f_{m}^{\dagger}|0\rangle$, then the fidelity is

$F(t)=|a_{m,m}(t)|^{2}.$ (27)

The more general $|a_{m,n}(t)|^{2}$ is also studied in the context of out of
time ordered correlators Riddell and Sørensen (2019, 2020); Xu and Swingle
(2020); Khemani  _et al._ (2018). Consider

$|a_{m,n}(t)|^{2}=\sum_{k,l}O_{m,k}O_{n,k}O_{m,l}O_{n,l}e^{i(\epsilon_{k}-\epsilon_{l})t}.$
(28)

The infinite time average of this quantity is taken as

$\omega_{m,n}=\sum_{k}O_{m,k}^{2}O_{n,k}^{2}.$ (29)

For extended models with non-degenerate frequencies this quantity decays to
zero since $\omega_{m,n}\sim\frac{1}{L}$ and $\kappa_{2}\leq\frac{c}{L^{2}}$,
where $c$ is weakly dependent on system size and is $\mathcal{O}(1)$ in the
thermodynamic limit Riddell and Sørensen (2020). We can bound the moments for
the single particle propagator as follows.

######  Theorem 4.

Let $H$ be a free fermionic Hamiltonian with a generic spectrum, and let the
dynamical function $f(t)=|a_{m,n}(t)|^{2}$ be the squared single particle
propagator. The moments are then bounded by

$\kappa_{q}\leq\left(\frac{qc^{4}}{L}\right)^{q},$ (30)

where $c=\sqrt{L}\max_{k_{j}}\\{O_{m,k_{j}},O_{n,k_{j}}\\}$.

Finally, the corresponding concentration bound is

$\displaystyle\mathrm{Pr}$
$\displaystyle\left[||a_{m,n}(t)|^{2}-\omega_{m,n}\big{|}\geq\delta\right]\leq
2e\times\mathrm{exp}\left(-\frac{\delta L}{ec^{4}}\right).$ (31)

##  IV Recurrence time

All the quantities analyzed above always come back arbitrarily close to their
initial values at $t=0$. For large systems, however, such recurrences only
happen at astronomically large timescales, inaccessible to both experiments
and numerical studies. We now put a lower bound on those timescales through a
suitably defined notion of _average recurrence time_ , both for observables
and also the whole state.

######  Definition 3.

A $(u,\Delta,A)$-recurrence occurs at a time interval
$\mathcal{C}_{\Delta}=[t_{\Delta},t_{\Delta}+\Delta]$ if, for all
$t\in\mathcal{C}_{\Delta}$,

$|\langle A(t)\rangle-\langle A(0)\rangle|\leq u||A||,$ (32)

where $\Delta>0$ and $u\in(0,2]$. Similarly, a $(u,\Delta)$-recurrence occurs
if, for all $t\in\mathcal{C}_{\Delta}$,

$1-F(t)\leq u.$ (33)

We identify a recurrence with an interval of time during which the system is
close to the initial value. Thus, the definition contains two free parameters:
$\Delta$ is the time duration of that recurrence, and $u$ quantifies how close
to the initial state that is. We expect that the larger $\Delta$ and the
smaller $u$ are, the more seldom a $(u,\Delta,A)$-recurrence will happen. In
fact, for some large enough $\Delta$, a $(u,\Delta,A)$-recurrence will likely
never happen.

Notice that it follows from the Fuchs-van de Graafs inequalities Fuchs and van
de Graaf (1998) that an $(u,\Delta)$-recurrence implies an
$(u,\Delta,A)$-recurrence for all $A$, and that conversely an
$(u,\Delta,A)$-recurrence for all $A$ implies an $(u,\Delta)$-recurrence.
However, individual observables may have additional earlier recurrences than
those of the fidelity.

Let us also define $t^{n}_{\Delta}(A)$ as the initial point of the time
interval corresponding to the $n$-th $(u,\Delta,A)$-recurrence, so that
$t^{n}_{\Delta}(A)<t^{n+1}_{\Delta}(A)$, and analogously, $t^{n}_{\Delta}$ for
the fidelity recurrences. This motivates the following definition, inspired by
that in Venuti (2015a).

######  Definition 4.

The average $(u,\Delta,A)$-recurrence time is

$T(u,\Delta,A)\equiv\lim_{n\rightarrow\infty}\frac{t_{\Delta}^{n}(A)}{n},$
(34)

with $T(u,\Delta)$ analogously defined.

$T(u,\Delta,A)$ can be understood as the inverse of the density of
recurrences. To see this, first note that $\langle A(t)\rangle$ is a
Besicovitch almost periodic function and we can therefore choose a well-
defined almost period $\tilde{P}$ in the sense of Besicovitch (1926).
Evaluating our sequence at integer multiples of the almost period gives
$\frac{t_{\Delta}^{n}(A)}{n}\rightarrow\frac{\tilde{P}}{n_{\tilde{P}}}$ where
$n_{\tilde{P}}$ is the number of $t_{\Delta}^{n}(A)$ inside an almost period.
Then it follows that $T(u,\Delta,A)=1/D(u,\Delta,A)$ where $D(u,\Delta,A)$ is
the density of $(u,\Delta,A)$ recurrences. These quantities can be easily
bounded with the concentration bounds above. First, for $T(u,\Delta,A)$.

######  Corollary 1.

Let $H$ have a generic spectrum, and let w.l.o.g. $\langle
A(0)\rangle-\overline{\langle A\rangle}=c_{A}||A||\geq 0$. Then, for $u\leq
c_{A}$,

$\frac{\Delta}{2e}\mathrm{exp}\left(\frac{c_{A}-u}{e\sqrt{\mathrm{Tr}[\omega^{2}]}}\right)\leq
T(u,\Delta,A).$ (35)

###### Proof.

From the definition of the distribution $P(x)$ in Eq. (6) and Eq. (15) we have
that

$\displaystyle\lim_{n\rightarrow\infty}$ $\displaystyle\frac{\Delta
n}{t_{\Delta}^{n}(A)+\Delta}\leq\mathrm{Pr}\left[|\langle A(t)\rangle-\langle
A(0)\rangle|\leq u||A||\right]$ $\displaystyle\leq\mathrm{Pr}\left[|\langle
A(t)\rangle-\overline{\langle A\rangle}|\geq(c_{A}-u)||A||\right]$
$\displaystyle\leq
2e\times\mathrm{exp}\left(\frac{u-c_{A}}{e\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}}\right).$
(36)

Notice that $\lim_{n\rightarrow\infty}\frac{\Delta
n}{t_{\Delta}^{n}(A)+\Delta}=\Delta/T(u,\Delta,A)$. Solving for
$T(u,\Delta,A)$ yields the result. ∎

The previous results are stated in terms of arbitrary recurrences, defined
with free parameters $\Delta,u$. We now explain for which choices of these we
expect the bounds to be more meaningful. With typical out-of-equilibrium
initial conditions, we have that $c_{A}=\mathcal{O}(1)$. In that case,
meaningful recurrences, comparable in magnitude to the initial condition, will
be such that $c_{A}-u=\mathcal{O}(1)$. We expect that in those cases, the
recurrences will have a duration comparable to that of the initial
equilibration time $T^{A}_{\text{eq}}$, which we can loosely define as the
time it takes for $\langle A(t)\rangle$ to initially settle around the steady
value $\overline{\langle A\rangle}$. These recurrences are then on average
spaced by a time which we roughly estimate to be

$T\gtrsim
T^{A}_{\text{eq}}e^{\Omega\left(\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1/2}\right)}.$
(37)

See Goldstein  _et al._ (2013); Malabarba  _et al._ (2014); García-Pintos  _et
al._ (2017); de Oliveira  _et al._ (2018); Wilming  _et al._ (2018) for
analytical bounds on $T^{A}_{\text{eq}}$. Note that for local Hamiltonians and
observables, $T^{A}_{\text{eq}}$ is believed to generally scale as a low-
degree polynomial in system size D’Alessio  _et al._ (2016).

A possible shortcoming of Eq. (35) is that the bound vanishes when
$\Delta\rightarrow 0$. That is, Corollary 1 is unable to estimate vanishingly
small recurrences. However, we expect that meaningful recurrences, getting
somewhat close to the expectation value of initial conditions, will typically
have a relaxation time comparable to that of the initial conditions, in which
case the estimate of Eq. (37) applies.

For the fidelity, the bound on the recurrence follows exactly the proof of
Corollary 1 but using Eq. (19) instead.

######  Corollary 2.

Let $H$ have a generic spectrum. Then,

$\frac{\Delta}{2e^{2}}\mathrm{exp}\left(\frac{1-u}{e\mathrm{Tr}[\omega^{2}]}\right)\leq
T(u,\Delta).$ (38)

Again, there are particular choices of the free parameters for which we expect
the bounds to be more meaningful. In many-body systems, the fidelity initially
decays as $F(t)=e^{-\sigma^{2}t^{2}/2}$ where
$\sigma^{2}=\bra{\Psi}H^{2}\ket{\Psi}-\bra{\Psi}H\ket{\Psi}^{2}$ is the energy
variance Torres-Herrera and Santos (2014); Torres-Herrera  _et al._ (2014);
Alhambra  _et al._ (2020a). Recurrences with $u=\mathcal{O}(1)$, in which the
time-evolved state reaches a meaningful fidelity with the initial one, likely
decay in a similar fashion, and as such we expect them to have a time duration
of $\Delta\sim\sigma^{-1}$, so that on average they are spaced by a time

$T\gtrsim\sigma^{-1}e^{\Omega\left(\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1}\right)}.$
(39)

This resembles the result in Venuti (2015a), which gives an exact calculation
of the average recurrence time based on some heuristic assumptions on the
wave-function, and finds a similar scaling of
$e^{\Omega\left(\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1}\right)}$,
with a slightly different prefactor. It also matches the scaling of other
previous estimates Bhattacharyya and Mukherjee (1986), so Eq. (38) should be
close to optimal.

Finally, we also have corresponding bounds for fermions.

######  Corollary 3.

Let $H$ be a free fermionic Hamiltonian with generic spectrum, and let
w.l.o.g. $\langle f_{m}^{\dagger}f_{n}(0)\rangle-\overline{\langle
f_{m}^{\dagger}f_{n}\rangle}=c_{f}\geq 0$. Then, for $u\leq c_{f}$,

$\frac{\Delta}{2e}\mathrm{exp}\left(\frac{c_{f}-u}{ec^{2}}\sqrt{\frac{L}{\nu}}\right)\leq
T(u,\Delta,f_{m}^{\dagger}f_{n}),$ (40)

as well as for the fidelity in Eq. (27).

######  Corollary 4.

Let $H$ be a free fermionic Hamiltonian with generic spectrum. Then,

$\frac{\Delta}{2e}\mathrm{exp}\left(\frac{(1-u)L}{ec^{4}}\right)\leq
T(u,\Delta).$ (41)

The analogue of Eq. (37) and Eq. (39) also holds following the same
considerations. These bounds however scale as
$e^{\Omega\left(\sqrt{L}\right)}$ and $e^{\Omega\left(L\right)}$ respectively,
which are exponential in the number of sites $L$. This is a fast scaling, but
still exponentially slower than that from Corollaries 1 and 2. Even shorter
recurrence times are also found in specific instances of Bose gases Kaminishi
_et al._ (2015); Solano-Carrillo (2015); Kaminishi and Mori (2019), which can
even be experimentally tested Rauer  _et al._ (2018) with cold atoms.

##  V Conclusion

We have shown how in systems with a generic spectrum as given in Definition 1
both observables and the fidelity with the initial state equilibrate around
their time-averaged values, with out-of-equilibrium fluctuations suppressed
exponentially in the effective dimension
$\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{-1}$. This number
scales exponentially under very general conditions on the state and the
Hamiltonian Wilming  _et al._ (2019); Rolandi and Wilming (2020); Huang and
Harrow (2020); Haferkamp  _et al._ (2021), so in these systems fluctuations
are most often doubly exponentially suppressed. Since partial or full
recurrences are far from equilibrium fluctuations, our bounds yield an
estimate of their occurrence, with a scaling that we believe is almost
optimal. Equivalent results with a slower scaling also hold for free fermions.

Previous works Linden  _et al._ (2010); Friesdorf  _et al._ (2015); Farrelly
_et al._ (2017); Wilming  _et al._ (2019); Huang and Harrow (2020); Haferkamp
_et al._ (2021) start with the bound on the second moment in Reimann (2008);
Linden  _et al._ (2009) to obtain results on equilibration, so the present
findings naturally strengthen them. Also, Theorem 2 in Alhambra  _et al._
(2020b) extends Reimann (2008); Linden  _et al._ (2009) to two-point
correlation functions, and the corresponding concentration bound is
straightforward.

Our bounds on the recurrence time apply to individual states. A given
Hamiltonian should also have other later state-independent recurrences. For
instance, the recent result for random circuits Oszmaniec  _et al._ (2022)
suggests that a recurrence in complexity of $e^{-itH}$ might still doubly
exponential, but with a larger exponent that Eq. (39).

###### Acknowledgements.

AMA acknowledges support from the Alexander von Humboldt foundation. J.R. and
N.J.P. acknowledges support from the Natural Sciences and Engineering Research
Council of Canada (NSERC).

## References

  * Gogolin and Eisert (2016) C. Gogolin and J. Eisert, Rep. Prog. Phys. 79, 056001 (2016).
  * Ueda (2020) M. Ueda, Nature Reviews Physics 2, 669 (2020).
  * Srednicki (1999) M. Srednicki, Journal of Physics A: Mathematical and General 32, 1163 (1999).
  * Bocchieri and Loinger (1957) P. Bocchieri and A. Loinger, Phys. Rev. 107, 337 (1957).
  * Percival (1961) I. C. Percival, Journal of Mathematical Physics 2, 235 (1961), https://doi.org/10.1063/1.1703705 .
  * Hogg and Huberman (1982) T. Hogg and B. A. Huberman, Phys. Rev. Lett. 48, 711 (1982).
  * Duvenhage (2002) R. Duvenhage, International Journal of Theoretical Physics 41, 45 (2002).
  * Wallace (2015) D. Wallace, Journal of Mathematical Physics 56, 022105 (2015), https://doi.org/10.1063/1.4907384 .
  * Bhattacharyya and Mukherjee (1986) K. Bhattacharyya and D. Mukherjee, The Journal of Chemical Physics 84, 3212 (1986), https://doi.org/10.1063/1.450251 .
  * Venuti (2015a) L. C. Venuti, “The recurrence time in quantum mechanics,”  (2015a).
  * Hogg and Huberman (1983) T. Hogg and B. A. Huberman, Phys. Rev. A 28, 22 (1983).
  * Peres (1982) A. Peres, Phys. Rev. Lett. 49, 1118 (1982).
  * Reimann (2008) P. Reimann, Phys. Rev. Lett. 101, 190403 (2008).
  * Linden  _et al._ (2009) N. Linden, S. Popescu, A. J. Short, and A. Winter, Phys. Rev. E 79, 061103 (2009).
  * Reimann and Kastner (2012) P. Reimann and M. Kastner, New Journal of Physics 14, 043020 (2012).
  * Venuti and Zanardi (2010) L. C. Venuti and P. Zanardi, Physical Review A 81 (2010), 10.1103/physreva.81.032113.
  * Venuti (2015b) L. C. Venuti, in  _Quantum Criticality in Condensed Matter_ (WORLD SCIENTIFIC, 2015).
  * Kaneko  _et al._ (2020) K. Kaneko, E. Iyoda, and T. Sagawa, Physical Review A 101 (2020), 10.1103/physreva.101.042126.
  * Mark  _et al._ (2022) D. K. Mark, J. Choi, A. L. Shaw, M. Endres, and S. Choi, “Benchmarking quantum simulators using quantum chaos,”  (2022).
  * Short (2011) A. J. Short, New. J. Phys. 13, 053009 (2011).
  * Goldstein  _et al._ (2006) S. Goldstein, J. L. Lebowitz, R. Tumulka, and N. Zanghì, Journal of Statistical Physics 125, 1193 (2006).
  * Campos Venuti and Zanardi (2010) L. Campos Venuti and P. Zanardi, Phys. Rev. A 81 (2010), 10.1103/physreva.81.022113.
  * Huang and Harrow (2020) Y. Huang and A. W. Harrow, “Instability of localization in translation-invariant systems,” (2020), arXiv:1907.13392 [cond-mat.dis-nn] .
  * Venuti and Zanardi (2013) L. C. Venuti and P. Zanardi, Phys. Rev. E 87, 012106 (2013).
  * Riddell and Sørensen (2019) J. Riddell and E. S. Sørensen, Phys. Rev. B 99, 054205 (2019).
  * Riddell and Sørensen (2020) J. Riddell and E. S. Sørensen, Phys. Rev. B 101, 024202 (2020).
  * Xu and Swingle (2020) S. Xu and B. Swingle, Nature Physics 16, 199 (2020).
  * Khemani  _et al._ (2018) V. Khemani, D. A. Huse, and A. Nahum, Phys. Rev. B 98, 144304 (2018).
  * Fuchs and van de Graaf (1998) C. A. Fuchs and J. van de Graaf, “Cryptographic distinguishability measures for quantum mechanical states,” (1998), arXiv:quant-ph/9712042 [quant-ph] .
  * Besicovitch (1926) A. Besicovitch, Proceedings of the London Mathematical Society 2, 495 (1926).
  * Goldstein  _et al._ (2013) S. Goldstein, T. Hara, and H. Tasaki, Phys. Rev. Lett. 111, 140401 (2013), arXiv:1307.0572 .
  * Malabarba  _et al._ (2014) A. S. L. Malabarba, L. P. García-Pintos, N. Linden, T. C. Farrelly, and A. J. Short, Phys. Rev. E 90, 012121 (2014).
  * García-Pintos  _et al._ (2017) L. P. García-Pintos, N. Linden, A. S. L. Malabarba, A. J. Short, and A. Winter, Phys. Rev. X 7, 031027 (2017).
  * de Oliveira  _et al._ (2018) T. R. de Oliveira, C. Charalambous, D. Jonathan, M. Lewenstein, and A. Riera, New. J. Phys. 20, 033032 (2018).
  * Wilming  _et al._ (2018) H. Wilming, T. R. de Oliveira, A. J. Short, and J. Eisert, in  _Thermodynamics in the Quantum Regime_ (Springer, 2018) pp. 435–455.
  * D’Alessio  _et al._ (2016) L. D’Alessio, Y. Kafri, A. Polkovnikov, and M. Rigol, Advances in Physics 65, 239 (2016).
  * Torres-Herrera and Santos (2014) E. J. Torres-Herrera and L. F. Santos, Physical Review A 89 (2014), 10.1103/physreva.89.043620.
  * Torres-Herrera  _et al._ (2014) E. J. Torres-Herrera, M. Vyas, and L. F. Santos, New Journal of Physics 16, 063010 (2014).
  * Alhambra  _et al._ (2020a) A. M. Alhambra, A. Anshu, and H. Wilming, Phys. Rev. B 101 (2020a), 10.1103/physrevb.101.205107.
  * Kaminishi  _et al._ (2015) E. Kaminishi, J. Sato, and T. Deguchi, Journal of the Physical Society of Japan 84, 064002 (2015), https://doi.org/10.7566/JPSJ.84.064002 .
  * Solano-Carrillo (2015) E. Solano-Carrillo, Phys. Rev. E 92, 042164 (2015).
  * Kaminishi and Mori (2019) E. Kaminishi and T. Mori, Phys. Rev. A 100, 013606 (2019).
  * Rauer  _et al._ (2018) B. Rauer, S. Erne, T. Schweigler, F. Cataldini, M. Tajik, and J. Schmiedmayer, Science 360, 307 (2018), https://www.science.org/doi/pdf/10.1126/science.aan7938 .
  * Wilming  _et al._ (2019) H. Wilming, M. Goihl, I. Roth, and J. Eisert, Phys. Rev. Lett. 123, 200604 (2019).
  * Rolandi and Wilming (2020) A. Rolandi and H. Wilming, “Extensive rényi entropies in matrix product states,” (2020), arXiv:2008.11764 [quant-ph] .
  * Haferkamp  _et al._ (2021) J. Haferkamp, C. Bertoni, I. Roth, and J. Eisert, PRX Quantum 2 (2021), 10.1103/prxquantum.2.040308.
  * Linden  _et al._ (2010) N. Linden, S. Popescu, A. J. Short, and A. Winter, New Journal of Physics 12, 055021 (2010).
  * Friesdorf  _et al._ (2015) M. Friesdorf, A. H. Werner, M. Goihl, J. Eisert, and W. Brown, New Journal of Physics 17, 113054 (2015).
  * Farrelly  _et al._ (2017) T. Farrelly, F. G. Brandão, and M. Cramer, Phys. Rev. Lett. 118, 140601 (2017).
  * Alhambra  _et al._ (2020b) Á. M. Alhambra, J. Riddell, and L. P. García-Pintos, Phys. Rev. Lett. 124, 110605 (2020b).
  * Oszmaniec  _et al._ (2022) M. Oszmaniec, M. Horodecki, and N. Hunter-Jones, “Saturation and recurrence of quantum complexity in random quantum circuits,”  (2022).

##  Appendix A Defining moments

The average value of $\langle A(t)\rangle$ in Eq. 1 motivates the formal
definition of the following probability distribution

$P(x)=\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}\delta(x-\langle
A(t)\rangle).$

Note that this integral is convergent since this distribution is well-defined
by the argument given between equations 4-6. We would like to compute the
moments as

$\mu_{q}\equiv\lim_{T\rightarrow\infty}\int_{0}^{T}\frac{\text{d}t}{T}\left(\langle
A(t)\rangle-\overline{\langle A\rangle}\right)^{q}.$

This requires swapping the integral over $x$ and limit in $T$ and can be
justified using the dominated convergence theorem. To use this famous result
we must prove that the absolute value of the integrand is bounded by an
integrable function. Consider

$\kappa_{q}=\int x^{q}\lim_{T\rightarrow\infty}P_{T}(x)dx.$

For book-keeping purposes let $g(t)=\left(\langle
A(t)\rangle-\overline{\langle A\rangle}\right)$. We may bound the integrand
inside the limit

$|x^{q}P_{T}(x)|=|\frac{x^{q}}{T}\int_{0}^{T}\text{d}t\delta(x-g(t))|\leq\frac{|x|^{q}}{T}\int_{0}^{T}\text{d}t\delta(x-g(t)).$

Integrating the absolute value of the right-hand side and applying Fubini’s
theorem we find

$\int\left|\frac{|x|^{q}}{T}\,\int_{0}^{T}\text{d}t\delta(x-g(t))\right|dx\leq\int\frac{|x|^{q}}{T}\,\left|\int_{0}^{T}\text{d}t\delta(x-g(t))\right|dx\leq\int\frac{|x|^{q}}{T}\,\int_{0}^{T}\text{d}t\delta(x-g(t))dx$
$\leq\frac{1}{T}\,\int_{0}^{T}\text{d}t|g(t)|^{q}.$

The function $g(t)$ is continuous and therefore bounded on the interval
$[0,T]$, so the integral is finite, therefore its positive and negative
components are as well, thus the $q$-th absolute moment is bounded. We may
therefore conclude that the absolute value of the integrand is bounded by an
integrable function, so by the dominated convergence theorem we may swap the
integral and limit.

Note that equivalently, one may define the moments for finite $T$ and then
take the limit.

##  Appendix B Generic spectra

######  Lemma 1.

The set of generic Hermitian matrices in $M_{d}(\mathbb{C})$ has full Lebesgue
measure.

###### Proof.

Note that this proof is similar to the proof that the set of non-
diagonalizable matrices has Lebesgue measure zero. Let $H$ be some Hermitian
$d\times d$ matrix. We start by defining the function

$F(H)=\prod_{\begin{subarray}{c}n_{1},m_{1},...,n_{q},m_{q}\\\
{n_{i}}\not={m_{i}}\end{subarray}}\left(\sum_{i=1}^{q}E_{n_{i}}-E_{m_{i}}\right).$

This function is zero precisely when the spectrum is not generic. Clearly
swapping eigenvalues does not change the function $F$, i.e. $F$ is a symmetric
polynomial of the eigenvalues. By the fundamental theorem of symmetric (real)
polynomials $F$ can be written uniquely as a polynomial in the elementary
symmetric polynomials in $E_{i}$’s, which are precisely trace powers of $H$.

Recall that $H$ can be expressed in some basis. For example some generalized
Pauli basis, or even the standard basis. This is conceptually equivalent to
saying that the vector space of all possible $H$ can be parameterized by the
coefficients of the basis elements in the expansion. Thus, we may expand $H$
in this basis and then take trace powers, showing us that $F$ is a real
polynomial in the space of these coefficients.

It is a well known fact from measure theory that the zero set of a
multivariate polynomial has Lebesgue measure zero. ∎

##  Appendix C Bounding the moments

###  C.1 Proof for generic models

######  Theorem 1.

Let $H$ have a generic spectrum, $\omega$ the diagonal ensemble, and $||A||$
the largest singular value of $A$. The moments in Eq. 4 in the main text are
such that

$\mu_{q}\leq\left(q||A||\sqrt{\mathrm{Tr}[\omega^{2}]}\right)^{q}.$ (42)

###### Proof.

First we prove the following inequality:

$|\operatorname{\textnormal{Tr}}\left[{(A\omega)^{q}}\right]|\leq\left(||A||\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}\right)^{q}.$
(43)

To realize this, consider the matrix $A\omega$, which is not Hermitian and
therefore may have complex eigenvalues and may potentially not be
diagonalizable. This, however, does not prevent us from finding a complete set
of eigenvalues such that their multiplicity summed is the dimension of
$A\omega$. The matrix is always similar to its Jordan form, and we can in
general always write

$\operatorname{\textnormal{Tr}}\left[{A\omega}\right]=\sum_{i}\lambda_{i},$
(44)

where $\lambda_{i}$ is the $i$-th (potentially complex) eigenvalue of
$A\omega$. More generally, we can always write

$\operatorname{\textnormal{Tr}}\left[{(A\omega)^{q}}\right]=\sum_{i}\lambda_{i}^{q}.$
(45)

From here we can bound the following:

$\displaystyle|\operatorname{\textnormal{Tr}}\left[{(A\omega)^{q}}\right]|$
$\displaystyle=|\sum_{i}\lambda_{i}^{q}|$ (46)
$\displaystyle\leq\sum_{i}|\lambda_{i}^{q}|$ (47)
$\displaystyle=||\lambda||^{q}_{q}$ (48)
$\displaystyle\leq||\lambda||_{2}^{q}=\left(\sum_{i}|\lambda_{i}|^{2}\right)^{q/2}$
(49)

where we used the triangle inequality in (47), and in (49) we use the property
$||x||_{p+a}\leq||x||_{p}$ for any vector $x$ and real numbers $p\geq 1$ and
$a\geq 0$. Note that, using the Shur decomposition, we may write
$A\omega=QUQ^{\dagger}$, where $Q$ is a unitary matrix, and $U$ is upper
triangular with the same spectrum on the diagonal as $A\omega$. Using this, we
have that

$\operatorname{\textnormal{Tr}}\left[{(A\omega)(A\omega)^{\dagger}}\right]=\operatorname{\textnormal{Tr}}\left[{QUQ^{\dagger}(QUQ^{\dagger})^{\dagger}}\right]=\operatorname{\textnormal{Tr}}\left[{UU^{\dagger}}\right]=\sum_{i}|\lambda_{i}|^{2}+\text{other
non-negative terms}.$

Thus,

$\displaystyle\sum_{i}|\lambda_{i}|^{2}\leq\operatorname{\textnormal{Tr}}\left[{A\omega\omega^{\dagger}A^{\dagger}}\right]\leq||AA^{\dagger}||\operatorname{\textnormal{Tr}}\left[{\omega\omega^{\dagger}}\right]\leq||A||^{2}\operatorname{\textnormal{Tr}}\left[{\omega\omega^{\dagger}}\right]=||A||^{2}\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right].$

This gives us our desired inequality.

Moving on, let us derive a general bound for the $q$-th moment of models
satisfying Definition 1. For simplicity, and w.l.o.g., let us assume that
$\overline{\langle A\rangle}=0$. Expanding the definition of the moments we
arrive at

$\mu_{q}=\lim_{\tau\to\infty}\frac{1}{\tau}\int_{0}^{\tau}dt\sum_{m_{1},n_{1},...,m_{q},n_{q}}\prod_{i=1}^{q}\left(A_{m_{i},n_{i}}\bar{c}_{m_{i}}c_{n_{i}}\right)e^{i(E_{m_{i}}-E_{n_{i}})t}.$
(50)

The assumption that the Hamiltonian is generic means that only certain terms
in the sum survive after averaging over all time: those for which the sets of
$\\{m_{i}\\}$ and $\\{n_{i}\\}$ coincide up to permutations, which we denote
with $\\{\sigma(i)\\}$. Due to the equilibrium expectation value being zero,
we can also eliminate all terms for which $i=\sigma(i)$ for $1\leq i\leq q$.
Thus, we want all permutations on $q$ elements except those that have a fixed
point. Such permutations are called derangements. The number of distinct
derangements is denoted by $!q=\lfloor\frac{q!}{e}+\frac{1}{2}\rfloor$. Let
$D_{q}$ denote the set of derangements on $\\{1,2,..,q\\}$. Eq. (50) becomes

$\displaystyle\mu_{q}=\sum_{m_{1},...,m_{q}}\prod_{i=1}^{q}|c_{m_{i}}|^{2}\sum_{\sigma\in
D_{q}}\prod_{i=1}^{q}A_{m_{i},\sigma(m_{i})}.$ (51)

Given a derangement $\sigma$, it can be decomposed as the product of cycles
$\sigma_{1},\sigma_{2},...,\sigma_{r}$ with lengths
$\ell_{1},\ell_{2},...,\ell_{r}$, respectively, such that
$\sum_{j=1}^{r}l_{j}=q$. In each term of the inner summation we can collect
terms of the same cycle. For example for $q=6$ and
$\sigma=\sigma_{1}\sigma_{2}=(m_{1},m_{2})(m_{3},m_{4},m_{5},m_{6})$ the term
can be written as

$(A_{m_{1},m_{2}}A_{m_{2},m_{1}})(A_{m_{3},m_{4}}A_{m_{4},m_{5}}A_{m_{5},m_{6}}A_{m_{6},m_{3}}).$

Summing over $m_{1},m_{2},m_{3},m_{4},m_{5},m_{6}$ we have that this term is
precisely

$\operatorname{\textnormal{Tr}}\left[{(A\omega)^{2}}\right]\operatorname{\textnormal{Tr}}\left[{(A\omega)^{4}}\right].$

In general, each cycle of a term will correspond to a product of trace powers
i.e. $\sigma=\sigma_{1},\sigma_{2},...,\sigma_{r}$ corresponds to

$\operatorname{\textnormal{Tr}}\left[{(A\omega)^{\ell_{1}}}\right]\operatorname{\textnormal{Tr}}\left[{(A\omega)^{\ell_{2}}}\right]...\operatorname{\textnormal{Tr}}\left[{(A\omega)^{\ell_{r}}}\right].$

We may apply Eq. (43) term-wise to get

$\operatorname{\textnormal{Tr}}\left[{(A\omega)^{\ell_{1}}}\right]\operatorname{\textnormal{Tr}}\left[{(A\omega)^{\ell_{2}}}\right]...\operatorname{\textnormal{Tr}}\left[{(A\omega)^{\ell_{r}}}\right]\leq\left(||A||\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}\right)^{\ell_{1}+\ell_{2}+...+\ell_{r}}=\left(||A||\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}\right)^{q}.$

In each moment’s inner summation there are precisely $!q$ terms of this form
because there are $!q$ derangements, thus

$\displaystyle\mu_{q}\leq$
$\displaystyle!q\left(||A||\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}\right)^{q}\leq\left(q||A||\sqrt{\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]}\right)^{q}.$
(52)

∎

The $q=2$ case can be found in Short (2011).

######  Theorem 2.

Let $H$ have a generic spectrum and let $A=\ket{\Psi}\bra{\Psi}$, then

$\mu_{q}\leq\left(q\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]\right)^{q}.$
(53)

###### Proof.

The moments defined for the fidelity are defined as

$\displaystyle\mu_{q}=\lim_{\tau\to\infty}\frac{1}{\tau}\int_{0}^{\tau}dt\prod_{i=1}^{q}\sum_{m_{i}\neq
n_{i}}|c_{m_{i}}|^{2}|c_{n_{i}}|^{2}e^{i(E_{m_{i}}-E_{n_{i}})t},$ (54)
$\displaystyle=\sum_{m_{1},\dots
m_{q}}\prod_{i=1}^{q}|c_{m_{i}}|^{2}\prod_{\sigma\in
D_{q}}|c_{\sigma(m_{i})}|^{2}.$ (55)

In the above expression we can note that there are $!q$ possible derangements
using genericity given in Definition 1. Each $m_{i}$ will have one pair given
to us from $\sigma(m_{i}$), implying each individual term in the sum is
$\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{q}$, so our final
expression is

$\mu_{q}=!q\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]^{q}\leq\left(q\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]\right)^{q}.$
(56)

∎

###  C.2 Generic free models

This class of models conserves total particle number, which we will denote as

$N=\sum_{j=1}^{L}\langle f_{j}^{\dagger}f_{j}\rangle=\sum_{k=1}^{L}\langle
d_{k}^{\dagger}d_{k}\rangle.$ (57)

######  Theorem 3.

Let $H$ be a extended free fermionic Hamiltonian with a generic spectrum and
let $A=f_{m}^{\dagger}f_{n}$. Then, the even moments are bounded above by

$\kappa_{q}\leq\left(qc^{2}\sqrt{\frac{\nu}{L}}\right)^{q},$ (58)

where $\nu=\frac{N}{L}$ is the filling factor of the fermions on the lattice
and $c=\sqrt{L}\max_{k_{j}}\\{O_{m,k_{j}},O_{n,k_{j}}\\}$.

###### Proof.

Consider

$\kappa_{2n}=\lim_{T\to\infty}\frac{1}{T}\int_{0}^{\infty}dt\prod_{j=1}^{n}\sum_{k_{j}\neq
l_{j}}O_{m,k_{j}}O_{n,l_{j}}\langle d_{k_{j}}^{\dagger}d_{l_{j}}\rangle
e^{i(\epsilon_{k_{j}}-\epsilon_{l_{j}})t}\sum_{p_{j}\neq
q_{j}}O_{m,p_{j}}O_{n,q_{j}}\langle d_{q_{j}}^{\dagger}d_{p_{j}}\rangle
e^{i(\epsilon_{q_{j}}-\epsilon_{p_{j}})t}.$ (59)

Let us define the tensor (note the $j$ dependence)

$B_{k_{j},l_{j}}=\begin{cases}O_{m,k_{j}}O_{n,l_{j}}\langle
d_{k_{j}}^{\dagger}d_{l_{j}}\rangle&j\text{ odd}\\\
O_{m,l_{j}}O_{n,k_{j}}\langle d_{k_{j}}^{\dagger}d_{l_{j}}\rangle&j\text{
even}\\\ 0&k_{j}=l_{j}\end{cases}.$ (60)

This allows us to rewrite our equation as

$\kappa_{2n}=\lim_{T\to\infty}\frac{1}{T}\int_{0}^{\infty}dt\prod_{j=1}^{2n}\sum_{k_{j},l_{j}}B_{k_{j},l_{j}}e^{i(\epsilon_{k_{j}}-\epsilon_{l_{j}})t}.$
(61)

This can likewise be rewritten as

$\kappa_{2n}=\lim_{T\to\infty}\frac{1}{T}\int_{0}^{\infty}dt\sum_{k_{1},l_{1},\dots
k_{2n},l_{2n}}\prod_{j=1}^{2n}B_{k_{j},l_{j}}e^{i(\epsilon_{k_{j}}-\epsilon_{l_{j}})t}.$
(62)

Assuming a generic single-particle spectrum, this means we have the following
surviving terms:

$\kappa_{2n}=\sum_{k_{1},\dots k_{2n}}\sum_{\sigma\in
S_{2n}}\prod_{j=1}^{2n}B_{k_{j},\sigma(k_{j})}$ (63)

where $S_{2n}$ denotes the symmetric group on ${1,2\dots 2n}$. We can then
enforce the fact that these terms are zero if $k_{j}=\sigma(k_{j})$ for $1\leq
j\leq 2n$. So denoting the derangements as $D_{2n}$ as earlier, we arrive at

$\kappa_{2n}=\sum_{k_{1},\dots k_{2n}}\sum_{\sigma\in
D_{2n}}\prod_{j=1}^{2n}B_{k_{j},\sigma(k_{j})}.$ (64)

Next, recognizing that each definition of $B$ contains two extensive terms
multiplied, let $c=\sqrt{L}\max_{k_{j}}\\{O_{m,k_{j}},O_{n,k_{j}}\\}$,

$\kappa_{2n}\leq\frac{c^{4n}}{L^{2n}}\sum_{k_{1},\dots k_{2n}}\sum_{\sigma\in
D_{2n}}\prod_{j=1}^{2n}\langle d_{k_{j}}^{\dagger}d_{\sigma(k_{j})}\rangle$
(65)

As in Theorem 1, each term will be a trace of powers of $\Lambda$, and there
can be at most $n$ products of traces of $\Lambda$. Since
$0\leq\Lambda\leq\mathbb{I}$, each trace of $\Lambda$ can further be bounded
by
$\operatorname{\textnormal{Tr}}\left[{\Lambda^{p}}\right]\leq\operatorname{\textnormal{Tr}}\left[{\Lambda}\right]=N=\nu
L$, which means we can bound $\kappa_{2n}$ by

$\kappa_{2n}\leq!(2n)\frac{c^{4n}\nu^{n}}{L^{2n-n}}\leq\left(\frac{4n^{2}c^{4}\nu}{L}\right)^{n},$
(66)

where $c$ is weakly dependent on system size and $0\leq\nu\leq 1$. Choosing
$q=2n$ and reorganizing gives the desired result. ∎

######  Theorem 4.

Let $H$ be a free fermionic Hamiltonian with a generic spectrum, and let our
dynamical function $f(t)=|a_{m,n}(t)|^{2}$ be the squared single particle
propagator, then we can bound the moments by

$\kappa_{q}\leq\left(\frac{qc^{4}}{L}\right)^{q},$ (67)

where $c=\sqrt{L}\max_{k_{j}}\\{O_{m,k_{j}},O_{n,k_{j}}\\}$.

###### Proof.

The $q$-th moment can be written as

$\mu_{q}=\lim_{T\to\infty}\frac{1}{T}\int_{0}^{\infty}dt\prod_{i=1}^{q}\sum_{k_{i}\neq
l_{i}}O_{m,k_{i}}O_{n,k_{i}}O_{m,l_{i}}O_{n,l_{i}}e^{i(\epsilon_{k_{i}}-\epsilon_{l_{i}})t},$
(68)

through the usual procedure and using the definition 2 in the main text we
recover

$\mu_{q}=\sum_{k_{1},\dots
k_{q}}\prod_{i=1}^{q}O_{m,k_{i}}O_{n,k_{i}}\prod_{\sigma\in
D_{q}}O_{m,\sigma(k_{i})}O_{n,\sigma(k_{i})},$ (69)

defining $c=\sqrt{L}\max_{k_{j}}\\{O_{m,k_{j}},O_{n,k_{j}}\\}$, we factor out
four of these, and sum up the indices, giving us

$\mu_{q}\leq\frac{!qc^{4q}}{L^{q}}\leq\left(\frac{qc^{4}}{L}\right)^{q}.$ (70)

∎

##  Appendix D Numerics

The numerics for the figures in the main body were carried out on the spin 1/2
Hamiltonian,

$\displaystyle{H}=$
$\displaystyle\sum_{j=1}^{L}J_{1}\left({S}_{j}^{+}S_{j+1}^{-}+\text{h.c}\right)+\gamma_{1}\,{S}_{j}^{Z}{S}_{j+1}^{Z}+J_{2}\left({S}_{j}^{+}{S}_{j+2}^{-}+\text{h.c}\right)+\gamma_{2}{S}_{j}^{Z}{S}_{j+2}^{Z},$

where $(J_{1},\gamma_{1},J_{2},\gamma_{2})\nobreak=\nobreak(-1,1,-0.2,0.5)$
giving us a non-integrable model. We perform exact diagonalization exploiting
total spin conservation and translation invariance. We choose pure initial
states that allow us to further exploit the $Z_{2}$ spin flip symmetry and the
spatial reflection symmetry. In Fig. 1 we see the approximated probability
distribution function $\tilde{P}_{T}(x)$ as a histogram. The observable is
$A=\sigma_{1}^{Z}$, the Pauli-z matrix on the first lattice site. The initial
state is a Néel type state:

$|\psi\rangle=|\uparrow\downarrow\dots\rangle.$ (71)

In Fig. 2 we calculate the purity of the diagonal ensemble
$\operatorname{\textnormal{Tr}}\left[{\omega^{2}}\right]$ for three states.
The states featured are

$\displaystyle|\psi\rangle$
$\displaystyle\coloneqq|\uparrow\downarrow\uparrow\downarrow\dots..\rangle,$
(72) $\displaystyle|\psi^{\prime}\rangle$
$\displaystyle\coloneqq\frac{1}{\sqrt{2}}\left(|\uparrow\downarrow\uparrow\downarrow\dots..\rangle+|\downarrow\uparrow\downarrow\uparrow\dots..\rangle\right),$
(73) $\displaystyle|\phi\rangle$
$\displaystyle\coloneqq\frac{1}{\sqrt{L}}\sum_{r=0}^{L-1}\hat{T}^{r}|\uparrow\uparrow\dots\uparrow\downarrow\dots\downarrow\downarrow\rangle.$
(74)