# A Measure-Theoretic Characterization of Tight Language Models

Li Du${}^{\text{{\tipaencoding 6}}}$ Lucas Torroba
Hennigen${}^{\text{{\tipaencoding@}}}$ Tiago Pimentel${}^{\text{{\tipaencoding
D}}}$
Clara Meister${}^{\text{{\tipaencoding Q}}}$ Jason
Eisner${}^{\text{{\tipaencoding 6}}}$ Ryan Cotterell${}^{\text{{\tipaencoding
Q}}}$
${}^{\text{{\tipaencoding 6}}}$Johns Hopkins University
${}^{\text{{\tipaencoding@}}}$MIT
${}^{\text{{\tipaencoding D}}}$University of Cambridge
${}^{\text{{\tipaencoding Q}}}$ETH Zürich
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Language modeling, a central task in natural language processing, involves
estimating a probability distribution over strings. In most cases, the
estimated distribution sums to 1 over all finite strings. However, in some
pathological cases, probability mass can “leak” onto the set of infinite
sequences. In order to characterize the notion of leakage more precisely, this
paper offers a measure-theoretic treatment of language modeling. We prove that
many popular language model families are in fact tight, meaning that they will
not leak in this sense. We also generalize characterizations of tightness
proposed in previous works.

##  1 Introduction

Language modeling is a core task in natural language processing. As
canonically defined, language modeling involves estimating a distribution over
the set of strings over a given alphabet. If the alphabet is the set of words
in a language,111Or perhaps alphabetic symbols or subwords; see, e.g., Bostrom
and Durrett (2020). then a language model can be thought of as a distribution
over the language’s sentences. Since Shannon (1948), language modeling has
been used to estimate statistical properties of language and has become
essential for computational linguistics research Hale (2001); Meister et al.
(2021). Further, it is also central to a wide range of natural language
processing applications, whether as a source model in a noisy channel
architecture Weaver (1955); Jelinek (1976), as a way of learning better
representations of language (Peters et al., 2018), or, more recently, for
prompted generation (Brown et al., 2020), where the distribution defined by a
language model is employed in tasks like question-answering (Petroni et al.,
2019), style transfer (Reif et al., 2022), and even sequence tagging Liu et
al. (2022).

More formally, a language model is typically defined to be a distribution over
the _countably_ infinite set $\Sigma^{*}$ of all (finite) strings Booth and
Thompson (1973).222Recall that
$\Sigma^{*}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\bigcup_{n}\Sigma^{n}$
where for $n\geq 0$, $\Sigma^{n}$ is the set of strings of length $n$. The ∗
is the Kleene closure operator. However, it has been shown that some classes
of autoregressive language models have parameter settings in which the
generative process terminates with probability $<1$. Welleck et al. (2020)
discuss this issue for recurrent neural network language models. Models whose
generative process may fail to terminate are called non-tight (Chi, 1999, who
discussed non-tight PCFGs). If an autoregressive language model is non-tight,
it may generate infinite sequences and MCMC algorithms over such models will
not mix to the correct distribution.

It is here that a subtlety arises: the set of infinite sequences is
_uncountably_ infinite. Properly treating a distribution over this sample
space requires a modicum of measure theory.333Indeed, our treatment resolves
an imprecision present in the literature. For instance, Welleck et al. (2020)
discusses the probability of infinite sequences despite using the canonical
definition of a language model as a distribution over $\Sigma^{*}$. To clarify
the situation, we review the measure-theoretic treatment of distributions over
infinite sequences. We then make use of a termination symbol eos to define a
random variable whose value can be a string, i.e., an element of $\Sigma^{*}$,
or an infinite sequence. In a tight language model, this random variable has
probability 1 of being a string and hence finite.

Beyond offering a measure-theoretic formalization, our paper also demonstrates
how tightness relates to the Borel–Cantelli lemmata, simplifying a recent
result by Meister et al. (2022). To conclude our paper, we analyze several
language modeling architectures and give conditions on their tightness. We
demonstrate that $n$-gram language models—and more generally, language models
defined by stochastic finite-state automata—can be non-tight, and we give a
simple necessary and sufficient condition for tightness in terms of the
inverse of the automaton’s transition matrix. This builds on a known result
due to Lehmann (1977). We also discuss when neural language models become non-
tight. We prove that Transformer-based language models Vaswani et al. (2017);
Brown et al. (2020) are always tight and that recurrent neural language models
are always tight when they employ a bounded activation function. However, we
also exhibit a recurrent neural network (RNN) language model with a ReLU
activation (Nair and Hinton, 2010) that is non-tight in a simpler construction
than the one offered by Chen et al. (2018). As a byproduct, we also generalize
and strengthen the results given by Welleck et al. (2020), who give a
sufficient condition for tightness of recurrent neural language models in
terms of the norm of the hidden state.

##  2 Motivating Examples

$\bar{p}(\texttt{a}\mid\textsc{bos})$ 1 $\bar{p}(\texttt{a}\mid\texttt{a})$
0.7 $\bar{p}(\texttt{b}\mid\texttt{a})$ 0.2
$\bar{p}(\textsc{eos}\mid\texttt{a})$ 0.1 $\bar{p}(\texttt{b}\mid\texttt{b})$
1 $\bar{p}(\textsc{eos}\mid\textsc{eos})$ 1

abeosbos$\texttt{a}/1$$\texttt{a}/0.7$$\texttt{b}/1$$\textsc{eos}/1$$\texttt{b}/0.2$$\textsc{eos}/0.1$

(a) Non-tight $2$-gram model.

$\bar{p}(\texttt{a}\mid\textsc{bos})$ 1 $\bar{p}(\texttt{a}\mid\texttt{a})$
0.7 $\bar{p}(\texttt{b}\mid\texttt{a})$ 0.2
$\bar{p}(\textsc{eos}\mid\texttt{a})$ 0.1 $\bar{p}(\texttt{b}\mid\texttt{b})$
0.9 $\bar{p}(\textsc{eos}\mid\texttt{b})$ 0.1
$\bar{p}(\textsc{eos}\mid\textsc{eos})$ 1

abeosbos$\texttt{a}/1$$\texttt{a}/0.7$$\texttt{b}/0.9$$\textsc{eos}/0.1$$\textsc{eos}/1$$\texttt{b}/0.2$$\textsc{eos}/0.1$

(b) Tight $2$-gram model.

Figure 1: Tight and non-tight bigram models, expressed as Mealy machines (see
§ 5.1). Transitions with conditional probability of 0 are omitted. The
termination probability at a state is represented by an eos arc from that
state.

Let $\Sigma$ be an alphabet, i.e., a finite set of symbols, and let
$\textsc{eos}\notin\Sigma$ be a distinguished end-of-sequence symbol. Let
$\overline{\Sigma}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\Sigma\cup\\{\textsc{eos}\\}$.
A string of length $n\geq 0$ is a finite sequence $\bm{x}=x_{1}x_{2}\ldots
x_{n}$ where each $x_{t}\in\Sigma$. By convention, we say that
$x_{n+1}=\textsc{eos}$, although $x_{n+1}$ is not an element of the sequence
$\bm{x}$. For any integer $1\leq t\leq n+1$, we write $\bm{x}_{<t}$ for the
prefix $x_{1}x_{2}\cdots x_{t-1}$.

We now begin to distinguish between “language models” and “sequence models.”
As is traditional in the NLP literature, we henceforth define a language model
to be a probability distribution over the countable set $\Sigma^{*}$ of all
strings (see Def. 3.4). It is popular to specify such a distribution in terms
of its conditional probabilities $\bar{p}(x_{t}\mid\bm{x}_{<t})$.

######  Definition 2.1.

An autoregressive sequence model (ASM) is a conditional probability
distribution $\bar{p}(x_{t}\mid\bm{x}_{<t})$ where $x_{t}\in\overline{\Sigma}$
and $\bm{x}_{<t}\in\overline{\Sigma}^{*}$.

If $\bar{p}$ is an ASM, then we define a non-negative function $p$ over
$\Sigma^{*}$ by
$p(\bm{x})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\prod_{t=1}^{n+1}\bar{p}(x_{t}\mid\bm{x}_{<t})=\bar{p}(\textsc{eos}\mid\bm{x})\prod_{t=1}^{n}\bar{p}(x_{t}\mid\bm{x}_{<t})$,
where $n$ denotes the length of $\bm{x}$.

But is $p$ a language model? Not always, since as we will see below, it is
possible for
$p(\Sigma^{*})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sum_{\bm{x}\in\Sigma^{*}}p(\bm{x})<1$.
Of course this “bad” case never happens if the ASM’s conditional probabilities
are derived from a known LM, in which case $p$ simply recovers that LM.444That
is, suppose the ASM’s conditional probabilities match the conditional
probabilities of some known language model $p_{0}$: that is,
$p_{0}(X_{t}=x_{t}\mid X_{1}\ldots
X_{t-1}=\bm{x}_{<t})=\bar{p}(x_{t}\mid\bm{x}_{<t})$ whenever the former
conditional probability is well-defined under the language model $p_{0}$,
i.e., whenever $x_{t}\in\overline{\Sigma}$ and $\bm{x}_{<t}\in\Sigma^{*}$ with
$p_{0}(X_{1}\ldots X_{t-1}=\bm{x}_{<t})>0$. Then by the chain rule of
probability, $p(\bm{x})=p_{0}(\bm{x})$ for each $\bm{x}\in\Sigma^{*}$. Thus
$p=p_{0}$, so $p$ is a language model. In this case clearly
$p(\Sigma^{\ast})=1$. It follows that if $p(\Sigma^{\ast})<1$, then the ASM’s
conditional probabilities do _not_ match the conditional probabilities of any
language model $p_{0}$.

We now exhibit such a “bad” ASM. Although the conditional probability
distributions $\bar{p}(\cdot\mid\bm{x}_{<t})$ each sum to 1 over
$\overline{\Sigma}$, they fail to combine into a model $p$ that sums to 1 over
$\Sigma^{*}$ (i.e., a language model).

######  Example 2.2 (non-tight bigram model).

Consider the bigram model defined in Fig. 1(a) over the alphabet
$\Sigma=\\{\texttt{a},\texttt{b}\\}$. Under this model, any finite string that
contains the symbol b will have probability 0, since
$\bar{p}(\textsc{eos}\mid\texttt{b})=\bar{p}(\texttt{a}\mid\texttt{b})=0$.
This implies
$p(\Sigma^{\ast})=\sum_{n=0}^{\infty}p(\texttt{a}^{n})=\sum_{n=0}^{\infty}(0.7)^{n}\cdot
0.1=\frac{0.1}{1-0.7}=\frac{1}{3}<1$. ∎

######  Example 2.3 (tight bigram model).

In contrast, in Fig. 1(b), obtained from Ex. 2.2 by changing the arcs from the
b state, $p(\Sigma^{*})=1$. See App. B for details of this calculation. ∎

Ex. 2.2 above confirms that the autoregressive formulation does not
necessarily yield $p$ that is a valid distribution over $\Sigma^{*}$.

But if $p$ is not a language model, what is it? It is intuitive to suspect
that, in a model with $p(\Sigma^{*})<1$, the remainder of the probability mass
“leaks” to infinite sequences, i.e., the generative process may continue
forever with probability $>0$. We will make this intuition formal in § 3. By
analogy with Chi and Geman (1998) and Cohen and Johnson (2013), we refer to
such models as non-tight.555In Chi and Geman (1998) and Cohen and Johnson
(2013), a PCFG is non-tight if its generative process may not terminate, and
consequently the total probability of all finite trees is less than 1.

The non-tightness of Ex. 2.2 is related to the fact that the probability of
eos is $0$ at some states, in contrast to Ex. 2.3. However, requiring
$\bar{p}(\textsc{eos}\mid\bm{x}_{<t})>0$ for all prefixes $\bm{x}_{<t}$ is
neither necessary nor sufficient to ensure tightness. It is not _necessary_
because one can, for example, construct an ASM in which
$\bar{p}(\textsc{eos}\mid\bm{x}_{<t})=0.1$ when $t$ is even but $=0$
otherwise. Such a model generates only odd-length strings but is tight. It is
not _sufficient_ because of the following example, in which
$\bar{p}(\textsc{eos}\mid\bm{x}_{<t})$ is always positive but decays so
rapidly toward $0$ that the generative process might continue forever.

######  Example 2.4 (non-tight RNN).

Consider an RNN over a small alphabet
$\overline{\Sigma}=\\{\texttt{a},\textsc{eos}\\}$ with the following hidden
state recurrence:

$\displaystyle h_{0}$ $\displaystyle=0,$ $\displaystyle h_{t}$
$\displaystyle=\text{ReLU}(h_{t-1}+1).$ (1)

In this case, the hidden state admits a closed-form expression
$h_{t}=t\in\mathbb{R}$. Setting the (1-dimensional) embedding of the alphabet
to be $v_{\texttt{a}}=1$ and $v_{\textsc{eos}}=0$, we arrive at

$\displaystyle\bar{p}(\textsc{eos}$
$\displaystyle\mid\bm{x}_{<t})=\mathrm{softmax}(v_{\texttt{a}}h_{t},v_{\textsc{eos}}h_{t})_{\textsc{eos}}$
$\displaystyle=\textstyle\frac{e^{0\cdot t}}{e^{1\cdot t}+e^{0\cdot
t}}=\frac{1}{e^{t}+1}>0.$ (2)

The eos probability is always strictly positive, but Thm. 4.7 shows that this
sequence model is non-tight. Numerically, $p(\Sigma^{*})\approx 0.702<1$. ∎

On the other hand, an ASM may be tight after all if the probability of eos
decays more slowly—even when it still approaches $0$.

######  Example 2.5 (tight RNN).

Consider again an RNN over the alphabet
$\overline{\Sigma}=\\{\texttt{a},\textsc{eos}\\}$ with the following
recurrence using $\mathrm{softplus}$ activation:666We use $\mathrm{softplus}$
instead of ReLU to simplify arithmetics.

$\displaystyle h_{1}$ $\displaystyle=0,$ $\displaystyle h_{t}$
$\displaystyle=\log(\exp(h_{t-1})+1).$ (3)

Starting from $h_{1}=0=\log 1$, a simple induction argument shows that

$\displaystyle h_{t}=\log(\exp\log(t-1)+1)=\log t.$ (4)

Again, setting $v_{\texttt{a}}=1$ and $v_{\textsc{eos}}=0$, we arrive at

$\displaystyle\bar{p}(\textsc{eos}\mid\bm{x}_{<t})$
$\displaystyle=\mathrm{softmax}(v_{\texttt{a}}h_{t},v_{\textsc{eos}}h_{t})_{\textsc{eos}}$
(5) $\displaystyle=\textstyle\frac{e^{0\cdot\log t}}{e^{1\cdot\log
t}+e^{0\cdot\log t}}=\frac{1}{t+1}>0.$

This decays slowly to 0:
$\lim_{t\to\infty}\bar{p}(\textsc{eos}\mid\bm{x}_{<t})=0$, but since
$\sum_{t=1}^{\infty}\bar{p}(\textsc{eos}\mid\bm{x}_{<t})=\infty$, Prop. 4.3
below implies that this ASM is tight. ∎

Finally, we illustrate the peril of not treating distributions over
uncountable sets carefully.

######  Example 2.6 (infinite coin toss).

Consider the infinite independent fair coin toss model, where we aim to place
a distribution over $\\{\texttt{H},\texttt{T}\\}^{\infty}$, the uncountable
set of infinite sequences of $\\{\texttt{H},\texttt{T}\\}$. Intuitively, such
a distribution corresponds to an ASM in which for all $\bm{x}_{<t}$,
$\bar{p}(\texttt{H}\mid\bm{x}_{<t})=\bar{p}(\texttt{T}\mid\bm{x}_{<t})=\frac{1}{2}$
and $\bar{p}(\textsc{eos}\mid\bm{x}_{<t})=0$. Clearly, each individual
infinite sequence over $\\{\texttt{H},\texttt{T}\\}$ should be assigned
probability $(\frac{1}{2})^{\infty}=0$. Without a formal foundation, one may
arrive at the following paradox:

$\displaystyle 1$
$\displaystyle=p\left(\\{\texttt{H},\texttt{T}\\}^{\infty}\right)=\textstyle
p\left(\bigcup_{\bm{\omega}\in\\{\texttt{H},\texttt{T}\\}^{\infty}}\\{\bm{\omega}\\}\right)$
(6)
$\displaystyle=\sum_{\bm{\omega}\in\\{\texttt{H},\texttt{T}\\}^{\infty}}p(\\{\bm{\omega}\\})=\sum_{\bm{\omega}\in\\{\texttt{H},\texttt{T}\\}^{\infty}}0\stackrel{{\scriptstyle?}}{{=}}0.$
∎

Together, these examples suggest that one must take care to characterize
tightness. And, to the authors’ surprise, it does not appear as if such a
careful characterization yet exists in the NLP literature.

##  3 The Language Model Measure

In this section, we rigorously characterize the kind of distribution induced
by an ASM. As mentioned earlier, an ASM can lose probability mass to the set
of infinite sequences, $\Sigma^{\infty}$. However, $\Sigma^{\infty}$, unlike
$\Sigma^{*}$, is uncountable, and it is due to this fact that we need to work
explicitly with the measure-theoretic formulation of probability.

###  3.1 Measure-Theoretic Background

The goal of measure-theoretic probability is to assign probability to subsets
of an outcome space $\Omega$. For instance, in Ex. 2.6,
$\Omega=\\{\texttt{H},\texttt{T}\\}^{\infty}$. However, in the course of the
study of measure theory, it has become clear that for many common $\Omega$, it
is impossible to assign probabilities in a way that satisfies a set of
reasonable desiderata.777Measure theory texts commonly discuss such desiderata
and the dilemmas that comes with them. See, e.g., Chapter 7 in Tao (2016),
Chapter 3 in Royden (1988) or Chapter 3 in Billingsley (1995). We also give an
example in Thm. 3.5. Consequently, the standard approach to probability theory
resorts to only assigning probability to certain “nice” subsets of $\Omega$,
which are referred to as events or measurable subsets, as in the theory of
integration or functional analysis. The set of measurable subsets is commonly
denoted as $\mathcal{F}$ (Def. 3.1), and a probability measure
$\mathbb{P}:\mathcal{F}\to[0,1]$ is the function that assigns a probability to
each measurable subset. As it turns out, the following simple and reasonable
requirements imposed on $\mathcal{F}$ and $\mathbb{P}$ are enough to
rigorously discuss probability Kolmogorov (1933).

######  Definition 3.1.

Let $\mathcal{P}(\Omega)$ be the powerset of $\Omega$. Then
$\mathcal{F}\subseteq\mathcal{P}(\Omega)$ is called a $\bm{\sigma}$-algebra
(or $\sigma$-field) over $\Omega$ if the following conditions hold:

  1. 1)

$\Omega\in\mathcal{F}$,

  2. 2)

if $E\in\mathcal{F}$, then its complement $E^{\mathsf{c}}\in\mathcal{F}$,

  3. 3)

if $E_{1},E_{2},\dots$ is a finite or infinite sequence of sets in
$\mathcal{F}$, then $\bigcup_{n}E_{n}\in\mathcal{F}$.

If $\mathcal{F}$ is a $\sigma$-algebra over $\Omega$, we call the tuple
$(\Omega,\mathcal{F})$ a measurable space.

A measurable space guarantees that operations on countably many sets are
always valid, and hence permits the following definition.

######  Definition 3.2.

A probability measure $\mathbb{P}$ over a measurable space
$(\Omega,\mathcal{F})$ is a function $\mathbb{P}:\mathcal{F}\to[0,1]$ such
that

  1. 1)

$\mathbb{P}(\Omega)=1$,

  2. 2)

if $E_{1},E_{2},\dots$ is a finite or infinite sequence of disjoint sets in
$\mathcal{F}$, then $\mathbb{P}(\bigcup_{n}E_{n})=\sum_{n}\mathbb{P}(E_{n})$.

In this case we call $(\Omega,\mathcal{F},\mathbb{P})$ a probability space.
Note that it assigns measure only to the sets in $\mathcal{F}$; other sets are
said to be non-measurable.

###  3.2 Sequence Models

As we saw in § 2, sampling successive symbols from a non-tight ASM has
probability $>0$ of continuing forever. Hence, we hope to regard the ASM as
defining a probability space over $\Omega=\Sigma^{*}\cup\Sigma^{\infty}$,
where $\Sigma^{\infty}$ denotes the set of infinite strings888We will use the
phrase “infinite string” in this paper when it is natural to do so, e.g., in
the context of $\Sigma^{*}\cup\Sigma^{\infty}$. However, this is nonstandard
terminology: in computer science, _string_ generally refers to a finite
object. over $\Sigma$. Note that this set $\Omega$ is uncountable whenever
$|\Sigma|\geq 2$. We will first need to turn it into a measurable space by
defining an appropriate $\sigma$-algebra.

This type of distribution is more general than a language model, which takes
$\Omega$ to be the set $\Sigma^{*}$ of finite strings. To distinguish the two,
we refer to a distribution over $\Sigma^{*}\cup\Sigma^{\infty}$ as a sequence
model.

######  Definition 3.3.

A sequence model is a probability measure $P$ over the set
$\Sigma^{*}\cup\Sigma^{\infty}$.

Intuitively (we will make this precise later), the event
$\Sigma^{\infty}\subset\Sigma^{*}\cup\Sigma^{\infty}$ in Def. 3.3 represents
non-termination of the generating process, i.e., it attempts to generate an
infinitely long sequence. If this never happens, we have a language model.

######  Definition 3.4.

A language model is a probability measure $P$ over just $\Sigma^{*}$.
Equivalently, it is a sequence model $P$ such that $P(\Sigma^{\infty})=0$.

Our goal in the rest of this section is to rigorously construct a sequence
model $P$ that encodes the conditional probabilities of a given ASM. Since the
ASM specifies conditional distributions over the augmented alphabet
$\overline{\Sigma}$, we first use it to construct a probability measure
$\mathbb{P}$ over a measurable space
$(\overline{\Sigma}^{\infty},\sigma(\overline{\mathcal{C}}))$. We then derive
our sequence model $P$ from $\mathbb{P}$ as the probability measure of a
random variable $X$ in a measurable space
$(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$. The $\sigma$-algebras
$\sigma(\overline{\mathcal{C}})$ and $\sigma(\mathcal{C})$ will be built
below.

###  3.3 Pre-Measure

As mentioned in § 3.1, it is often impossible to measure the probability of
every single subset of $\Omega$. For example, in the infinite coin toss model
in Ex. 2.6, we might begin by reasonably assigning probability 0 to each
individual sequence $\bm{\omega}\in\\{\texttt{H},\texttt{T}\\}^{\infty}$.
Unfortunately, it is then impossible to assign probability to _every_ subset
of $\\{\texttt{H},\texttt{T}\\}^{\infty}$; we must restrict our measurable
space to a strict subset of $\mathcal{P}(\Omega)$, where $\mathcal{P}()$ is
the powerset operator.

######  Theorem 3.5.

Assuming the Axiom of Choice and the Continuum Hypothesis, there exists no
probability measure $\mathbb{P}$ over
$(\\{\texttt{H},\texttt{T}\\}^{\infty},\mathcal{P}(\\{\texttt{H},\texttt{T}\\}^{\infty}))$
such that $\mathbb{P}(\\{\bm{\omega}\\})=0$ for each
$\bm{\omega}\in\\{\texttt{H},\texttt{T}\\}^{\infty}$.

###### Proof.

This is a direct consequence of Ulam (1930). See § C.1.1 for a discussion.∎

We will address this with well-known methods. A versatile theorem of
Carathéodory provides a natural way to construct a probability space for
sequences, in which prefix probabilities are well-defined. We first review two
needed definitions.

######  Definition 3.6.

$\mathcal{A}\subseteq\mathcal{P}(\Omega)$ is called an algebra (or field) over
$\Omega$ if

  1. 1)

$\Omega\in\mathcal{A}$,

  2. 2)

if $E\in\mathcal{A}$, then $E^{\mathsf{c}}\in\mathcal{A}$,

  3. 3)

if $E_{1},E_{2}\in\mathcal{A}$, then $E_{1}\cup E_{2}\in\mathcal{A}$.

######  Definition 3.7.

Let $\mathcal{A}$ be an algebra over some set $\Omega$. A probability pre-
measure over $(\Omega,\mathcal{A})$ is a function
$\mathbb{P}_{0}:\mathcal{A}\to[0,1]$ such that

  1. 1)

$\mathbb{P}_{0}(\Omega)=1$,

  2. 2)

if $E_{1},E_{2},\dots$ is a (countable) sequence of disjoint sets in
$\mathcal{A}$ _whose (countable) union is also in_ $\mathcal{A}$, then
$\mathbb{P}_{0}(\cup_{n=1}^{\infty}E_{n})=\sum_{n=1}^{\infty}\mathbb{P}_{0}(E_{n})$.

Note that the only difference between a $\sigma$-algebra (Def. 3.1) and an
algebra is that condition 3 is weakened from countable to finite, and the only
difference between a probability measure (Def. 3.2) and a pre-measure is that
the latter is defined with respect to an algebra instead of a
$\sigma$-algebra.

The idea behind Carathéodory’s Extension Theorem is that there is often a
simple construction of an algebra $\mathcal{A}$ over $\Omega$ such that there
is a natural way to define a probability pre-measure. One can then extend this
probability pre-measure to a probability measure that is both minimal and
unique in a precise sense. For example, the standard Lebesgue measure over the
the real line can be constructed in this way. For our case of infinite
sequences, we will first construct an algebra over
$\Omega=\overline{\Sigma}^{\infty}$ for some alphabet $\Sigma$. Then, assuming
we are given an ASM $\bar{p}$ over $\overline{\Sigma}$, we can associate the
algebra with a pre-measure that is consistent with $\bar{p}$. We will make use
of the following definition to construct the algebra:

######  Definition 3.8.

Given any set $H\subseteq\overline{\Sigma}^{k}$, define its cylinder set (of
rank $k$) to be

$\overline{C}(H)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\left\\{\bm{x}\bm{\omega}~{}:~{}\bm{x}\in
H,\bm{\omega}\in\overline{\Sigma}^{\infty}\right\\}$ (7)

In essence, a cylinder set of rank $k$ is the set of infinite strings that
share their $k$-prefix with some string $\bm{x}\in
H\subseteq\overline{\Sigma}^{k}$. For a length-$k$ string $\bm{x}=x_{1}\dotsm
x_{k}$, the rank-$k$ cylinder set
$\overline{C}(\bm{x})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\overline{C}(\\{\bm{x}\\})$
is the set of all infinite strings prefixed by $\bm{x}$.999This type of
cylinder set, i.e., one that is generated by a singleton, is also called a
thin cylinder. We denote the collection of all rank-$k$ cylinder sets by
$\overline{\mathcal{C}}_{k}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\left\\{\overline{C}(H)~{}:~{}H\in\mathcal{P}(\overline{\Sigma}^{k})\right\\}$
and define
$\overline{\mathcal{C}}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\bigcup_{k=1}^{\infty}\overline{\mathcal{C}}_{k}$
to be the collection of all cylinder sets over $\Omega$.101010Observe that
$\overline{\mathcal{C}}_{1}\subset\overline{\mathcal{C}}_{2}\subset\overline{\mathcal{C}}_{3}\subset\dotsm$.

######  Lemma 3.9.

$\overline{\mathcal{C}}\subset\mathcal{P}(\Omega)$ is an algebra over
$\Omega=\overline{\Sigma}^{\infty}$.

###### Proof.

See § C.1.2. ∎

We are now ready to define the pre-measure $\mathbb{P}_{0}$ for the cylinder
algebra $\overline{\mathcal{C}}$. Given an ASM $\bar{p}$ and any set
$\overline{C}(H)\in\overline{\mathcal{C}}$, let

$\displaystyle\textstyle\mathbb{P}_{0}(\overline{C}(H))\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sum_{\bm{x}\in
H}\bar{p}(\bm{x})$ (8)

where, denoting the length of $\bm{x}$ by $k$,

$\displaystyle\textstyle\bar{p}(\bm{x})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\prod_{t=1}^{k}\bar{p}(x_{t}\mid\bm{x}_{<t}).$
(9)

We confirm in Prop. C.2 that $\mathbb{P}_{0}$ is well-defined even though the
cylinder set $\overline{C}(H)$ may also arise as $\overline{C}(H^{\prime})$
where $H^{\prime}\neq H$.111111For example, in the infinite coin toss model,
$\overline{C}(\texttt{H})=\overline{C}(\\{\texttt{HH},\texttt{HT}\\})$.

######  Lemma 3.10.

$\mathbb{P}_{0}$ is a pre-measure over $\overline{\mathcal{C}}$.

###### Proof.

See § C.1.2. ∎

###  3.4 Extension of Pre-Measure

We have now gathered all the ingredients needed to state Carathéodory’s
theorem.

######  Theorem 3.11 (Carathéodory’s Extension Theorem).

Given an algebra $\mathcal{A}$ over some set $\Omega$ and a probability pre-
measure $\mathbb{P}_{0}:\mathcal{A}\to[0,1]$, there exists a probability space
$(\Omega,\mathcal{F},\mathbb{P})$ such that $\mathcal{A}\subset\mathcal{F}$
and $\mathbb{P}|_{\mathcal{A}}=\mathbb{P}_{0}$. Furthermore, the
$\sigma$-algebra $\mathcal{F}$ depends only on $\mathcal{A}$ and is minimal
and unique—thus we may denote it by $\sigma(\mathcal{A})$—and the probability
measure $\mathbb{P}$ is unique.

###### Proof Sketch.

See § C.2.1. ∎

Applying Carathéodory’s extension theorem to our cylinder algebra
$\overline{\mathcal{C}}$ and pre-measure $\mathbb{P}_{0}$, we see that there
exists a probability space
$(\overline{\Sigma}^{\infty},\sigma(\overline{\mathcal{C}}),\mathbb{P})$ over
$\overline{\Sigma}^{\infty}$ that agrees with the ASM $\bar{p}$’s
probabilities. It is a fair question to ask what kinds of sets are non-
measurable under this construction; we discuss this in § C.2.2.

###  3.5 A String-Valued Random Variable

Having constructed the probability space
$(\overline{\Sigma}^{\infty},\sigma(\overline{\mathcal{C}}),\mathbb{P})$, we
now demonstrate how to use it to induce a probability space over
$\Sigma^{*}\cup\Sigma^{\infty}$ as required by Def. 3.3. We will achieve this
through the use of a random variable.

######  Definition 3.12 (random variable).

A mapping $X:\Omega\to S$ between two measurable spaces $(\Omega,\mathcal{F})$
and $(A,\mathcal{G})$ is an $(A,\mathcal{G})$-valued random variable, or a
measurable mapping, if, for all $B\in\mathcal{G}$,

$X^{-1}(B)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\\{\omega\in\Omega:X(\omega)\in
B\\}\in\mathcal{F}.$ (10)

To construct a random variable that takes values in
$\Sigma^{*}\cup\Sigma^{\infty}$, Def. 3.12 requires us to first construct a
$\sigma$-algebra over $\Sigma^{*}\cup\Sigma^{\infty}$. We will do so in a
similar fashion as we constructed
$(\overline{\Sigma}^{\infty},\overline{\mathcal{C}})$. Given
$H\subseteq\Sigma^{k}$, define a rank-$k$ cylinder set in
$\Sigma^{*}\cup\Sigma^{\infty}$ to be

$\displaystyle
C(H)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\\{\bm{x}\bm{\omega}~{}:~{}\bm{x}\in
H,\bm{\omega}\in\Sigma^{*}\cup\Sigma^{\infty}\\}.$ (11)

Let $\mathcal{C}_{k}$ be the set of all rank-$k$ cylinder sets. Define
$\mathcal{C}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\cup_{k=1}^{\infty}\mathcal{C}_{k}$.
Then, $\sigma\left(\mathcal{C}\right)$ is a $\sigma$-algebra by the same
reasoning as in Lemma 3.9 and Thm. 3.11. We can now define the random variable
$X$ by121212In this definition, the position $k\leq\infty$ of the first eos—a
stopping time—is itself a random variable.

$\displaystyle\\!\\!X(\bm{\omega})=\begin{cases}\bm{\omega}_{<k}&\textbf{if
}\omega_{k}\text{ is the first {eos} in }\bm{\omega}\\\
\bm{\omega}&\textbf{otherwise}\text{ (}\textbf{if
}\textsc{eos}\notin\bm{\omega}\text{)}\end{cases}$ (12)

where $\bm{\omega}\in\overline{\Sigma}^{\infty}$. We claim that $X$ is well-
defined:

######  Proposition 3.13.

The function
$X:(\overline{\Sigma}^{\infty},\sigma(\overline{\mathcal{C}}))\to(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$
defined in Eq. 12 is a measurable mapping.

###### Proof.

See § C.3. ∎

Any measurable function induces a probability measure on the output space,
called the pushforward measure (cf. §2.4 in Tao, 2011), given by

$\displaystyle P(X\in
E)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathbb{P}(X^{-1}(E)).$
(13)

One can check that $P$, defined using $\mathbb{P}$, is indeed a probability
measure on $(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$ and hence
$(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}),P)$ is a probability
space. We have therefore shown that, given any ASM, we can construct an
associated sequence model as defined in Def. 3.3.

Under the formulation of a probability space together with a random variable,
useful probability quantities arise naturally and intuitively. In particular,
when $\bm{x}\in\Sigma^{*}$ is a finite string, we have

$P(X=\bm{x})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}P(X\in\\{\bm{x}\\})=p(\bm{x})$
(14)

with the definition of $p$ from § 2. Additionally, as we will show in the next
section, the probability of the set of infinite strings
$P(X\in\Sigma^{\infty})$ is the probability of generating an infinite
string.131313An important detail left out in this discussion is that both the
singleton set $\\{\bm{x}\\}$ and $\Sigma^{\infty}$ need to be measurable in
$(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$ for the above to make
sense. This is addressed by Prop. C.7 and Prop. C.8.

##### Deriving eos

As an aside, the preceding section allows us to motivate the eos token in ASM
as a construct that emerges naturally. Specifically, for any
$\bm{x}\in\Sigma^{\ast}$, rearranging Eq. 14:

$\displaystyle\bar{p}(\textsc{eos}\mid\bm{x})$
$\displaystyle=\textstyle\frac{P(X=\bm{x})}{\bar{p}(\bm{x})}=\textstyle\frac{P(X=\bm{x})}{P(X\in
C({\bm{x}}))}$ (15a) $\displaystyle=P(X=\bm{x}\mid X\in C({\bm{x}}))$ (15b)

where we have used
$\bar{p}(\bm{x})=\mathbb{P}(\overline{C}(\bm{x}))=\mathbb{P}(X^{-1}(C(\bm{x})))=P(X\in
C(\bm{x}))$. This means that the eos probability in an ASM emerges as the
conditional probability that, given that we must generate a string with a
prefix $\bm{x}\in\Sigma^{\ast}$, the string is exactly $\bm{x}$.

##  4 Characterizing Tightness

Beyond the measure-theoretic formalization, a goal of this paper is to provide
an exact characterization of tightness in ASMs. The results presented in this
section generalize Lemma 3.2 in Welleck et al. (2020). First, we consider the
event

$\displaystyle
A_{k}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\\{\bm{\omega}\in\overline{\Sigma}^{\infty}:\omega_{k}=\textsc{eos}\\}$
(16)

in the probability space
$(\overline{\Sigma}^{\infty},\sigma(\overline{\mathcal{C}}),\mathbb{P})$.
Intuitively, $A_{k}$ is the event that an eos symbol appears at position $k$
in the string. Note that under this definition the $A_{k}$ are not disjoint.
For example, the string
$\bm{\omega}=\texttt{ab}\,\textsc{eos}\,\texttt{c}\,\textsc{eos}\,\texttt{dd}\dotsm$
lives in the intersection of $A_{3}$ and $A_{5}$ since eos appears at both
position 3 and position 5. Using Eq. 16, we can express the event consisting
of all finite strings as $\bigcup_{k=1}^{\infty}A_{k}$. It follows that we can
express the event of an infinite string as
$\left(\bigcup_{k=1}^{\infty}A_{k}\right)^{\mathsf{c}}=\bigcap_{k=1}^{\infty}A_{k}^{\mathsf{c}}$.
Thus, using the random variable $X$, we can express the probability of
generating an infinite string as

$\displaystyle P(X\in\Sigma^{\infty})$
$\displaystyle=\mathbb{P}(X^{-1}(\Sigma^{\infty}))$ (17a)
$\displaystyle=\textstyle\mathbb{P}\left(\bigcap_{k=1}^{\infty}A^{\mathsf{c}}_{k}\right).$
(17b)

Hence, we can now formalize the notion of tightness, which we have introduced
in § 2 and Def. 3.4.

######  Definition 4.1.

A sequence model $P$ is said to be tight if $P(X\in\Sigma^{\infty})=0$, in
which case it is also a language model (cf. Prop. C.9). Otherwise, we say that
it is non-tight.

Note that the definition of $A_{k}$ only uses a string’s $k$-prefix, and hence
is a cylinder set of rank $k$. Recalling that the cylinder sets are measurable
and so are the sets countably generated by them, we see that both the event
consisting of all finite strings and the event consisting of all infinite
strings are measurable. Thus,
$\mathbb{P}\left(\cup_{k=1}^{\infty}A_{k}\right)$ and
$\mathbb{P}\left(\cap_{k=1}^{\infty}A_{k}^{\mathsf{c}}\right)$ are well
defined.

###  4.1 A Lower Bound Result

We have characterized tightness in terms of the probability of a specific
event $\mathbb{P}\left(\cap_{k=1}^{\infty}A_{k}^{\mathsf{c}}\right)$, a
quantity we now seek to determine.

######  Lemma 4.2.

If
$\sum_{n=2}^{\infty}\mathbb{P}\left(A_{n}\mid\cap_{m=1}^{n-1}A_{m}^{\mathsf{c}}\right)=\infty$,
then $\mathbb{P}\left(\cap_{m=1}^{\infty}A_{m}^{\mathsf{c}}\right)=0$.

###### Proof.

See App. D. ∎

Using Lemma 4.2, we can derive the following useful sufficient condition for a
sequence model derived from an ASM to be tight. It applies when the
probability of eos does not decay too rapidly with the length of the prefix.

######  Proposition 4.3.

If $\bar{p}(\textsc{eos}\mid\bm{x})\geq f(t)$ for all $t\geq
1,\bm{x}\in\Sigma^{t-1}$, and $\sum_{t=1}^{\infty}f(t)=\infty$, then
$\mathbb{P}(\cap_{k=1}^{\infty}A_{k}^{\mathsf{c}})=0$. In other words, $P$ is
tight.

###### Proof.

See § D.2. ∎

This test implies tightness for all of the tight examples in § 2, but not for
the non-tight ones. Note that the lower-bounding function $f$ depends only on
the length of the prefix, not its content. $f$ does not have to be
monotonic—in the case of the even/odd example from § 2, it is not.

###  4.2 The Borel–Cantelli Lemmata

It turns out that Prop. 4.3 admits a converse statement in which we can prove
a similar property of $\bar{p}$ by assuming that the model is tight. To prove
this result, we will use a fundamental inequality from probability theory—the
Borel–Cantelli lemmata. The Borel–Cantelli lemmata are useful for our purposes
because they relate the probability measure of sets of the form
$\bigcap_{n=0}^{\infty}A_{n}$ or $\bigcup_{n=0}^{\infty}A_{n}$ to a series
$\sum_{n=0}^{\infty}p_{n}$. We will only state the lemmata here without
supplying their proofs;141414See §2.3 in Durrett (2019) or §4 in Billingsley
(1995) instead. however, we point out that Lemma 4.2 can be viewed as a
parallel statement to the Borel–Cantelli lemmata and one can prove the lemmata
using a very similar proof (cf. proof of Thm 2.3.7 in Durrett, 2019).

Concretely, given a sequence of events $\\{A_{n}\\}_{n=1}^{\infty}$ in some
probability space, the Borel–Cantelli lemmata are statements about the event

$\textstyle\\{A_{n}\text{
i.o.}\\}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\bigcap_{m=1}^{\infty}\bigcup_{n=m}^{\infty}A_{n}$
(18)

where i.o. stands for “infinitely often.” Intuitively, $\\{A_{n}\text{
i.o.}\\}$ is the set of outcomes that appear in infinitely many sets in the
collection $\\{A_{n}\\}_{n=1}^{\infty}$ (hence the name). We will not use
Borel–Cantelli directly, but they offer a probabilistic proof of a key result
(Cor. 4.6) which will in turn lead to the desired statement about tightness.
We formally state the first and second Borel–Cantelli lemmata below.

######  Lemma 4.4 (Borel–Cantelli I).

If
$\sum_{n=1}^{\infty}\mathbb{P}(A_{n})<\infty$, then $\mathbb{P}(A_{n}\text{
i.o.})=0$.

######  Lemma 4.5 (Borel–Cantelli II).

If
$\sum_{n=1}^{\infty}\mathbb{P}(A_{n})=\infty$, then $\mathbb{P}(A_{n}\text{
i.o.})=1$, provided that $\\{A_{n}\\}$ is a sequence of independent events.

Using the Borel–Cantelli lemmata, we can prove the following useful fact.

######  Corollary 4.6.

Given a sequence $\\{p_{n}\\}$ where $p_{n}\in[0,1)$. Then,

$\textstyle\prod_{n=1}^{\infty}(1-p_{n})=0\Longleftrightarrow\sum_{n=1}^{\infty}p_{n}=\infty.$
(19)

###### Proof.

See § D.3. ∎

We now turn to proving a more general version of Prop. 4.3, which would imply
its converse. First, we define the following quantity

$\displaystyle\widetilde{p}_{\textsc{eos}}(t)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathbb{P}(A_{t}\mid
A_{1}^{\mathsf{c}}\cap\dotsm\cap A_{t-1}^{\mathsf{c}})$ (20)

which can be viewed as the eos probability at step $t$, given that eos was not
generated at any earlier step. In Eq. 48a in § D.2, we show that, when
$\widetilde{p}_{\textsc{eos}}(t)$ is defined, it has the same value as

$\displaystyle\widetilde{p}_{\textsc{eos}}(t)=\frac{\sum_{\bm{\omega}\in\Sigma^{t-1}}\bar{p}(\bm{\omega})\bar{p}(\textsc{eos}\mid\bm{\omega})}{\sum_{\bm{\omega}\in\Sigma^{t-1}}\bar{p}(\bm{\omega})\phantom{\bar{p}(\textsc{eos}\mid\bm{\omega})}}.$
(21)

We can now completely characterize the tightness of an ASM with the following
theorem.

######  Theorem 4.7 (Proposition 2.4 in Meister et al., 2022).

An ASM is tight if and only if $\widetilde{p}_{\textsc{eos}}(t)=1$ for some
$t$ or $\sum_{t=1}^{\infty}\widetilde{p}_{\textsc{eos}}(t)=\infty$.

###### Proof.

See § D.4. The proof uses Cor. 4.6, which accounts for the form of the
condition. ∎

We remark that Thm. 4.7 is a generalization of Prop. 4.3 since if
$\widetilde{p}_{\textsc{eos}}(t)$ is lower-bounded by $f(t)$ whose series
diverges, its own series would also diverge. However, since
$\widetilde{p}_{\textsc{eos}}(t)$ involves the computation of a partition
function in its denominator, it can be intractable to calculate (Lin et al.,
2021). Hence, Prop. 4.3 will be our main tool for determining tightness.

Finally, we note that Thm. 4.7 generalizes claims in previous work. For
example, Welleck et al. (2020) require $f(t)=c>0$ for some constant $c$ to
determine tightness. Hence, their bound is not helpful in determining the
tightness in either Ex. 2.4 or Ex. 2.5, because the eos probability can be
arbitrarily small in both cases. Applying Prop. 4.3, we see that (1) the ASM
in Ex. 2.4 is non-tight, because the series
$\sum_{t=1}^{\infty}\frac{1}{e^{t}+1}$ is convergent, and (2) the ASM in Ex.
2.5 is tight, since the series $\sum_{t=1}^{\infty}\frac{1}{t+1}$ is
divergent.

##  5 Analysis of Common Language Models

We now put into practice the foundations built up in the previous sections and
discuss the tightness of several classes of ASMs.

###  5.1 Stochastic Finite-State Language Models

Language modeling based on $n$-grams has been historically influential in NLP
(Jurafsky and Martin, 2009, Ch. 4). However, as Fig. 1 illustrates, $n$-gram
language models are specific cases of the more general stochastic finite-state
language models (Vidal et al., 2005). Tightness is more naturally
characterized in this more general setting, as it turns out. We begin with a
linear-algebraic definition of stochastic finite-state language models—or,
more precisely, sequence models, since in this paper we do not consider the
non-tight ones to be language models.

######  Definition 5.1.

A $Q$-state stochastic finite-state sequence model (SFSSM) is a quadruple
$\big{(}\Sigma,\bm{s},\\{{\mathbf{P}}^{(a)}\\}_{a\in\Sigma},\bm{t}\big{)}$,
where $\Sigma$ is an alphabet of symbols,
${\mathbf{P}}^{(a)}\in\mathbb{R}^{Q\times Q}_{\geq 0}$ is a symbol-specific
transition matrix for $a\in\Sigma$,151515For simplicity, we have disallowed
$\varepsilon$-transitions. $\bm{s}\in\mathbb{R}^{Q}_{\geq 0}$ is a vector of
initial state probabilities, and $\bm{t}\in\mathbb{R}^{Q}_{\geq 0}$ is a
vector of termination probabilities, i.e., probabilities of generating eos in
each state.161616We use $Q$ to denote the number of states as $Q$ is the
traditional notation for the set of states in a finite-state automaton. We
further require that $\sum_{q=1}^{Q}s_{q}=1$ and that
$t_{q}+\sum_{q^{\prime}=1}^{Q}{\mathbf{P}}_{qq^{\prime}}=1$ for all $1\leq
q\leq Q$, where
${\mathbf{P}}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sum_{a\in\Sigma}{\mathbf{P}}^{(a)}$
is the transition sum matrix.

Given an SFSSM
$\Big{(}\Sigma,\bm{s},\\{{\mathbf{P}}^{(a)}\\}_{a\in\Sigma},\bm{t}\Big{)}$,
the probability of a string $\bm{x}\in\Sigma^{*}$ is defined by

$\bar{p}(x_{1}\cdots
x_{n})=\textstyle\bm{s}^{\top}\left(\prod_{t=1}^{n}{\mathbf{P}}^{(x_{t})}\right)\bm{t}.$
(22)

######  Definition 5.2.

A state $q$ of an SFSSM ($1\leq q\leq Q$) is accessible if there is a
positive-probability path to $q$ from some state $r$ with $s_{r}>0$; it is co-
accessible if there is a positive-probability path from $q$ to some state $r$
with $t_{r}>0$. It is useful if it is both accessible and co-accessible, i.e.,
$q$ appears on some positive-probability accepting path.

Def. 5.2 allows a simple characterization of tight SFSSMs, namely Thm. 5.3,
and a straightforward proof of Cor. 5.4.171717Cor. 5.4 is a special case of
Chi and Geman (1998), who showed that MLE estimates of PCFGs are tight.

######  Theorem 5.3.

An SFSSM is tight iff all accessible states are also co-accessible.

###### Proof.

See § E.1.1. ∎

######  Corollary 5.4.

Maximum likelihood estimates of $n$-gram models based on some corpus are
tight.

###### Proof.

See § E.1.1. ∎

In fact, we can express the termination probability of an SFSSM in simple
linear algebra terms.

######  Definition 5.5.

Trimming an SFSSM means removing its non-useful (useless) states to obtain a
substochastic finite-state sequence model.181818We use the term
_substochastic_ rather than _stochastic_ here because the trimmed model
satisfies
$t^{\prime}_{q}+\sum_{q^{\prime}=1}^{Q^{\prime}}{\mathbf{P}}^{\prime}_{qq^{\prime}}\leq
1$, but might no longer achieve equality as required by Def. 5.1. This does
not affect the string probabilities 22. Removing the non-useful states means
removing their rows and columns from ${\mathbf{P}}$ as well as their rows from
$\bm{s}$ and $\bm{t}$, yielding possibly smaller
${\mathbf{P}}^{\prime},\bm{s}^{\prime}$ and $\bm{t}^{\prime}$.

######  Theorem 5.6.

Let ${\mathbf{P}}^{\prime}$ be the transition sum matrix of a trimmed
substochastic FSSM. Then ${\mathbf{I}}-{\mathbf{P}}^{\prime}$ is invertible
and
$P(X\in\Sigma^{*})=\bm{s}^{\prime\top}({\mathbf{I}}-{\mathbf{P}}^{\prime})^{-1}\bm{t}^{\prime}\leq
1$.

###### Proof.

See § E.1.2. ∎

The well-known matrix inversion formula used above finds the total weight of
all accepting paths in any weighted graph Tarjan (1981).191919This is assuming
the total weight is finite (which we guarantee by substochasticity) and the
matrix is invertible (which we guarantee by trimming) The formula can be seen
as a special case of Lehmann’s (1977) algebraic path algorithm.

###  5.2 Transformer Language Models

We now prove that all Transformer language models are tight. Key to our proof
of the tightness of various neural architectures, including the Transformer,
is the following basic fact in topology.

######  Theorem 5.7.

Let $X$ be a compact topological space and $Y$ be any topological space. If
$f:X\to Y$ is continuous, then $f(X)\subseteq Y$ is also compact.

###### Proof.

See § E.2. ∎

To address the variable-length nature of modern deep NLP models, we will
mathematically abstract them as a function on vector tuples,202020Here
$\left(\mathbb{R}^{d}\right)^{+}$ is the set of nonempty tuples of vectors in
$\mathbb{R}^{d}$. This is formally the disjoint union (coproduct)
$\coprod_{t\in\mathbb{Z}_{>0}}\mathbb{R}^{t\times d}$.
$f:\left(\mathbb{R}^{d}\right)^{+}\to\left(\mathbb{R}^{d}\right)^{+}$, that is
length-preserving in the sense that $f\left(\mathbb{R}^{t\times
d}\right)\subseteq\left(\mathbb{R}^{t\times d}\right)$ for all $t>0$.
Intuitively, this definition is saying that $f$ is a function that maps a
nonempty vector tuple $\\{\bm{v}_{i}\\}_{i=1}^{t}$ to another vector tuple
$\\{\bm{h}_{i}\\}_{i=1}^{t}$ of the same length,

$\displaystyle
f(\bm{v}_{1},\dots,\bm{v}_{t})=(\bm{h}_{1},\dots,\bm{h}_{t})\in\mathbb{R}^{t\times
d},$ (23)

where $\bm{v}_{i}\in\mathbb{R}^{d}$ is commonly the embedding of the input
symbol $x_{i}$. In particular, we can take the function
$f:\left(\mathbb{R}^{d}\right)^{+}\to\left(\mathbb{R}^{d}\right)^{+}$ to be
the function defined by a stack of Transformer layers. This setup will help us
state the following.

######  Lemma 5.8.

Let $f:\left(\mathbb{R}^{d}\right)^{+}\to\left(\mathbb{R}^{d}\right)^{+}$ be
the function defined by a finite number of Transformer layers (e.g., $n$
layers) with any continuous activation function. Given a compact set
$K\subset\mathbb{R}^{d}$. Then, there exists a compact set
$K^{\prime}\subset\mathbb{R}^{d}$ such that for every $t\in\mathbb{Z}_{>0}$,

$f\big{(}K^{t}\big{)}\subseteq\left(K^{\prime}\right)^{t}.$ (24)

###### Proof.

See § E.2. ∎

Recall that a Transformer language model—or more precisely, a Transformer
ASM—defines the conditional probabilities using the softmax transformation

$\displaystyle\bar{p}(x_{t+1}\mid\bm{x}_{\leq
t})=\frac{\exp(\bm{u}_{x_{t+1}}^{\top}\bm{h}_{t})}{\sum_{y\in\overline{\Sigma}}\exp(\bm{u}_{y}^{\top}\bm{h}_{t})}$
(25)

where $\bm{u}_{x}\in\mathbb{R}^{d}$ is the output symbol embedding of
$x\in\overline{\Sigma}$ and $\bm{h}_{t}$ is defined from the input embeddings
of $\bm{x}_{\leq t}$ via Eq. 23. Using Lemma 5.8, together with the finiteness
of the vocabulary $\Sigma$ and the continuity of the softmax transformation
25, readily yields our main result on Transformers.

######  Theorem 5.9.

The autoregressive sequence model defined by any (fixed-depth) Transformer is
tight.

###### Proof.

See § E.2. ∎

###  5.3 Recurrent Neural Language Models

Recall that the hidden state of an RNN is typically defined by the recurrence

$\displaystyle\bm{h}_{t}=\sigma\left(\bm{W}\bm{v}_{t}+\bm{U}\bm{h}_{t-1}+\bm{b}\right)$
(26)

where $\bm{v}_{t}\in\mathbb{R}^{d}$ is the embedding of the input symbol
$x_{t}$, as above, and $\sigma(\cdot)$ is some activation function Elman
(1990). The conditional probabilities are usually defined in the same way as
Eq. 25. Using Thm. 5.7 and the same strategy of proof as in Thm. 5.9, one can
also easily prove the tightness of any RNN ASM with bounded activations (e.g.,
$\tanh$ or $\mathrm{sigmoid}$). However, as we saw in Ex. 2.4, an unbounded
activation function (e.g., ReLU) can indeed lead to non-tightness by making
the probability of eos decay too fast. The condition derived in Thm. 4.7
precisely determines how fast such decay can be without losing the tightness
of the language model. Below, we generalize this result as well as Lemma 3.2
of Welleck et al. (2020), and show that if the norm of the activations
eventually grows sub-logarithmically, the RNN is still tight.

######  Proposition 5.10.

Given an RNN ASM over $\overline{\Sigma}$. Again let the output symbol vector
be $\bm{u}_{x}\in\mathbb{R}^{d}$ for $x\in\overline{\Sigma}$, and set
$k\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sup_{x\in\Sigma}\|\bm{u}_{x}-\bm{u}_{\textsc{eos}}\|_{2}$.
Additionally, for each $t>0$, let $\|\widehat{\bm{h}}_{t}\|_{2}$ be the
maximum attainable hidden state norm for any context $\bm{x}\in\Sigma^{t}$.
Such a sequence model is tight if $k\|\widehat{\bm{h}}_{t}\|_{2}\leq\log t$
for all sufficiently large $t$.

###### Proof.

See § E.3. ∎

This result is weaker than Thm. 5.9 because in an RNN, unlike a Transformer,
the depth of the computation graph grows with the sequence length.

##  6 Conclusion

This paper presents a measure-theoretic treatment of language modeling and its
tightness. Practical implications of our results include determining when
sampling from an autoregressive sequence model is guaranteed to terminate and
whether MCMC algorithms over such models will mix to the correct distribution.

To this end, we first defined various components of language modeling in
measure-theoretic terminology. This in turn allows us to understand the
portion of probability mass allocated to infinite-length strings. Importantly,
this presentation formalizes a definition of sequence modeling under which the
probability of producing an infinite-length sequence is non-zero; while
today’s models are often capable of producing such strings, previously there
was no rigorous treatment of this case.

Indeed, such a definition is useful when considering a number of neural
architectures (e.g., a simple RNN as in Elman, 1990) and language generation
systems (e.g., the distribution induced by nucleus sampling; Holtzman et al.,
2020). In particular, we showed that perhaps the most commonly-used NLP
architecture, the Transformer language model, is indeed a language model—a
tight distribution over finite strings—a property that had been called into
question by previous work.

## Limitations

Our discussion in this paper leaves out the consideration of computability of
measures over languages. Specifically, we note that there exist works on
computable measure theory developed in the context of theoretical computer
science (de Leeuw et al., 1956) and probabilistic programming languages (Roy,
2011). Additional machinery needs to be developed in order for a proper
treatment and we leave this for future work.

Another notable limitation is that we exclusively focused on the
autoregressive production of language. Importantly, our formalism might not be
compatible with other models of language production such as those induced by a
PCFG.

Finally, our proofs of Theorems 5.9 and 5.10 exploit the strictly positive
property of the softmax function. Importantly, they do not apply to models
with sparse distributions Martins and Astudillo (2016); Peters et al. (2019);
Martins (2021).

## Ethics

There are no ethical implications of this paper to the best knowledge of the
authors.

## Acknowledgments

We thank Holden Lee for helpful discussion and suggestions, Anej Svete for
help with the graphics and Chu-Cheng Lin and Xinyan Velocity Yu for helpful
comments. LD is partially supported by the Johns Hopkins Mathematical
Institute for Data Science (MINDS) Fellowship. Finally, we thank the students
of the LLM course at ETH Zürich (263-5354-00L) for carefully reading this
paper as part of their lecture notes, and in particular, Valentin Bieri for
making a valuable remark.

## References

  * Axler (2020) Sheldon Axler. 2020.  _Measure, Integration & Real Analysis_.  Springer International Publishing.
  * Billingsley (1995) Patrick Billingsley. 1995.  _Probability and Measure_, 3${}^{\text{rd}}$ edition.  Wiley.
  * Blackwell and Diaconis (1996) David Blackwell and Persi Diaconis. 1996.  A non-measurable tail set.  _Statistics, probability and game theory: Papers in honor of David Blackwell_ , 30:1–5.
  * Booth and Thompson (1973) Taylor L. Booth and Richard A. Thompson. 1973.  Applying probability measures to abstract languages.  _IEEE Transactions on Computers_ , C-22(5):442–450.
  * Bostrom and Durrett (2020) Kaj Bostrom and Greg Durrett. 2020.  Byte pair encoding is suboptimal for language model pretraining.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4617–4624, Online. Association for Computational Linguistics.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901.
  * Chen et al. (2018) Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. 2018\.  Recurrent neural networks as weighted language recognizers.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2261–2271, New Orleans, Louisiana. Association for Computational Linguistics.
  * Chi (1999) Zhiyi Chi. 1999.  Statistical properties of probabilistic context-free grammars.  _Computational Linguistics_ , 25(1):131–160.
  * Chi and Geman (1998) Zhiyi Chi and Stuart Geman. 1998.  Estimation of probabilistic context-free grammars.  _Computational Linguistics_ , 24(2):299–305.
  * Cohen and Johnson (2013) Shay B. Cohen and Mark Johnson. 2013.  The effect of non-tightness on Bayesian estimation of PCFGs.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1033–1041, Sofia, Bulgaria. Association for Computational Linguistics.
  * de Leeuw et al. (1956) K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro. 1956.  _COMPUTABILITY BY PROBABILISTIC MACHINES_, Annals of Mathematics. Studies, no. 34, pages 183–212. Princeton University Press.
  * Durrett (2019) Rick Durrett. 2019.  _Probability: Theory and Examples_, 5${}^{\text{th}}$ edition.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
  * Elman (1990) Jeffrey L. Elman. 1990.  Finding structure in time.  _Cognitive Science_ , 14(2):179–211.
  * Folland (1999) Gerald B. Folland. 1999.  _Real Analysis: Modern Techniques and Their Applications_, 2${}^{\text{nd}}$ edition.  Wiley.
  * Grinstead and Snell (1997) Charles M. Grinstead and J. Laurie Snell. 1997.  _Introduction to Probability_, 2${}^{\text{nd}}$ revised edition.  American Mathematical Society.
  * Hale (2001) John Hale. 2001.  A probabilistic Earley parser as a psycholinguistic model.  In _Second Meeting of the North American Chapter of the Association for Computational Linguistics_.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_.
  * Horn and Johnson (2012) Roger A. Horn and Charles R. Johnson. 2012.  _Matrix Analysis_, 2${}^{\text{nd}}$ edition.  Cambridge University Press.
  * Jelinek (1976) Frederick Jelinek. 1976.  Continuous speech recognition by statistical methods.  _Proceedings of the IEEE_ , 64(4):532–556.
  * Jurafsky and Martin (2009) Dan Jurafsky and James Martin. 2009.  _Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition_, 2${}^{\text{nd}}$ edition.  Pearson Prentice Hall.
  * Kolmogorov (1933) A. N. Kolmogorov. 1933.  _Grundbegriffe der Wahrscheinlichkeitsrechnung_.  Springer.
  * Lehmann (1977) Daniel J. Lehmann. 1977.  Algebraic structures for transitive closure.  _Theoretical Computer Science_ , 4(1):59–76.
  * Lin (2022) Chu-Cheng Lin. 2022.  _On Expressiveness, Inference, and Parameter Estimation of Discrete Sequence Models_.  Ph.D. thesis, Johns Hopkins University.
  * Lin et al. (2021) Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R. Gormley, and Jason Eisner. 2021.  Limitations of autoregressive models and their alternatives.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5147–5173, Online. Association for Computational Linguistics.
  * Lin and McCarthy (2022) Chu-Cheng Lin and Arya D. McCarthy. 2022.  On the uncomputability of partition functions in energy-based sequence models.  In _International Conference on Learning Representations_.
  * Liu et al. (2022) Tianyu Liu, Yuchen Jiang, Nicholas Monath, Ryan Cotterell, and Mrinmaya Sachan. 2022\.  Autoregressive structure prediction with language models.  In _Findings of the Association for Computational Linguistics: EMNL 2022_ , Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Martins and Astudillo (2016) Andre Martins and Ramon Astudillo. 2016.  From softmax to sparsemax: A sparse model of attention and multi-label classification.  In _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 1614–1623, New York, New York, USA. PMLR.
  * Martins (2021) André F. T. Martins. 2021.  Reconciling the discrete-continuous divide: Towards a mathematical theory of sparse communication.  _CoRR_ , abs/2104.00755.
  * Meister et al. (2021) Clara Meister, Tiago Pimentel, Patrick Haller, Lena Jäger, Ryan Cotterell, and Roger Levy. 2021.  Revisiting the uniform information density hypothesis.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 963–980, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Meister et al. (2022) Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2022.  Locally typical sampling.  _Transactions of the Association for Computational Linguistics_.
  * Munkres (2000) James R. Munkres. 2000.  _Topology_, 2${}^{\text{nd}}$ edition.  Prentice Hall, Inc.
  * Nair and Hinton (2010) Vinod Nair and Geoffrey E. Hinton. 2010.  Rectified linear units improve restricted Boltzmann machines.  In _Proceedings of the 27th International Conference on International Conference on Machine Learning_ , pages 807–814, Madison, WI, USA.
  * Nederhof and Satta (2006) Mark-Jan Nederhof and Giorgio Satta. 2006.  Estimation of consistent probabilistic context-free grammars.  In _Proceedings of the Human Language Technology Conference of the NAACL, Main Conference_ , pages 343–350, New York City, USA. Association for Computational Linguistics.
  * Oxtoby (1980) John C. Oxtoby. 1980.  _Measure and Category: A Survey of the Analogies between Topological and Measure Spaces_.  Springer New York.
  * Peters et al. (2019) Ben Peters, Vlad Niculae, and André F. T. Martins. 2019.  Sparse sequence-to-sequence models.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1504–1519, Florence, Italy. Association for Computational Linguistics.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2227–2237, New Orleans, Louisiana. Association for Computational Linguistics.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. 2019.  Language models as knowledge bases? In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2463–2473, Hong Kong, China. Association for Computational Linguistics.
  * Reif et al. (2022) Emily Reif, Daphne Ippolito, Ann Yuan, Andy Coenen, Chris Callison-Burch, and Jason Wei. 2022.  A recipe for arbitrary text style transfer with large language models.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 837–848, Dublin, Ireland. Association for Computational Linguistics.
  * Roy (2011) Daniel M. Roy. 2011.  _Computability, Inference and Modeling in Probabilistic Programming_.  Ph.D. thesis, Massachusetts Institute of Technology, USA.  AAI0823858.
  * Royden (1988) Halsey L. Royden. 1988.  _Real Analysis_, 3${}^{\text{rd}}$ edition.  Prentice-Hall.
  * Shannon (1948) Claude E. Shannon. 1948.  A mathematical theory of communication.  _Bell System Technical Journal_ , 27:623–656.
  * Tao (2011) Terence Tao. 2011.  _An Introduction to Measure Theory_.  American Mathematical Society.
  * Tao (2016) Terence Tao. 2016.  _Analysis II: Third Edition_.  Texts and Readings in Mathematics. Springer Singapore.
  * Tarjan (1981) Robert E. Tarjan. 1981.  Fast algorithms for solving path problems.  _Journal of the Association for Computing Machinery_ , 28(3):594–614.
  * Ulam (1930) Stanisław Ulam. 1930.  Zur masstheorie in der allgemeinen mengenlehre.  _Fundamenta Mathematicae_ , 16(1):140–150.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30.
  * Vidal et al. (2005) E. Vidal, F. Thollard, C. de la Higuera, F. Casacuberta, and R.C. Carrasco. 2005\.  Probabilistic finite-state machines - part i.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 27(7):1013–1025.
  * Weaver (1955) Warren Weaver. 1955.  Translation.  In William N. Locke and A. Donald Boothe, editors, _Machine Translation of Languages_ , pages 15–23. MIT Press.  Reprinted from a memorandum written by Weaver in 1949.
  * Welleck et al. (2020) Sean Welleck, Ilia Kulikov, Jaedeok Kim, Richard Yuanzhe Pang, and Kyunghyun Cho. 2020.  Consistency of a recurrent language model with respect to incomplete decoding.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5553–5568, Online. Association for Computational Linguistics.

##  Appendix A Related Work

The issue of tightness has been studied extensively in the context of
probabilistic context-free grammars (PCFG; Chi and Geman, 1998; Chi, 1999;
Cohen and Johnson, 2013), although Chi (1999) refers to non-tight models as
improper. Specifically, Chi (1999) gave algorithms for determining the
tightness of a PCFG by formalizing a PCFG as a branching process. Chi (1999)
further proved that any maximum-likelihood estimator yields a tight PCFG.
Several previous works study the ability of language models to place
probability mass on infinite-length strings Booth and Thompson (1973);
Nederhof and Satta (2006); Chen et al. (2018); Welleck et al. (2020), where
they refer to the non-tight language models as inconsistent. In some cases,
this behavior can be attributed to the discrepancy between the language model
itself and the distribution induced by a (possibly stochastic) decoding
algorithm: the decoder may have a lower probability of generating the eos
token. For example, on the tight bigram model of Ex. 2.3, a greedy decoder
will always generate a and never eos. Yet in other examples, it is the model
itself that leaks probability mass to infinite-length strings, i.e., it may be
non-tight, which is the problem we focus on in this work, providing a
characterization of tightness. Notably, the conditions we propose are more
general than those of Welleck et al. (2020).

Several other works consider the limitations of common neural network
architectures for modeling distributions over finite sequences (strings),
albeit focusing specifically on other attributes, such as their computational
complexity for problems like equivalence or undecidability Chen et al. (2018);
Lin et al. (2021); Lin and McCarthy (2022); Lin (2022). In contrast, this work
provides a formal treatment of language models by enlarging the sample space
to $\Sigma^{*}\cup\Sigma^{\infty}$, although to ensure tightness,
$\Sigma^{\infty}$ must receive probability 0. Such definitions are not
uncommon in probability theory. For example, while the Wiener process (i.e.,
the standard Brownian motion) is a distribution over _all_ functions, the
definition ensures that the set of discontinuous functions is assigned
probability 0 (Durrett, 2019, Ch. 7).

Meister et al. (2022) similarly address the notion of a language model as a
distribution over infinite sequences by casting such models as stochastic
processes. They use this framing in order to motivate decoding, without
providing comprehensive measure-theoretic foundations of such distributions.

##  Appendix B Details for Motivating Ex. 2.3

Here, we lay out the steps to calculate $\mathbb{P}(\Sigma^{*})$ from Fig.
1(b):

$\displaystyle\mathbb{P}(\Sigma^{*})$
$\displaystyle=\sum_{n=0}^{\infty}\left(\mathbb{P}(\texttt{a}^{n+1})+\sum_{m=0}^{\infty}\mathbb{P}(\texttt{a}^{n+1}\texttt{b}^{m+1})\right)$
(27a) $\displaystyle=\sum_{n=0}^{\infty}\left(1\cdot(0.7)^{n}\cdot
0.1+\sum_{m=0}^{\infty}1\cdot(0.7)^{n}\cdot 0.2\cdot(0.9)^{m}\cdot 0.1\right)$
(27b)
$\displaystyle=\sum_{n=0}^{\infty}\;(0.7)^{n}\cdot\left(0.1+0.2\cdot\left(\sum_{m=0}^{\infty}(0.9)^{m}\right)\cdot
0.1\right)$ (27c)
$\displaystyle=\sum_{n=0}^{\infty}\;(0.7)^{n}\cdot\left(0.1+0.2\cdot\frac{1}{1-0.9}\cdot
0.1\right)$ (27d) $\displaystyle=\sum_{n=0}^{\infty}\;(0.7)^{n}\cdot
0.3=\frac{0.3}{1-0.7}=1$ (27e)

##  Appendix C Measure Theory Details

###  C.1 Proofs and Details in § 3.3

####  C.1.1 Details of Thm. 3.5

See 3.5

This theorem is an impossibility of measure theorem. Generally speaking, the
existence of a non-measurable set implies some form of impossibility of
measure. The most famous example of non-measurable sets are Vitali sets, which
exist given the Axiom of Choice. Vitali’s 1905 construction is typically
described in introductory texts on measure theory Royden (1988); Billingsley
(1995); Axler (2020). The existence of Vitali sets shows that it is impossible
to define a probability measure that satisfies translational invariance on the
measurable space $\big{(}[0,1),\mathcal{P}([0,1))\big{)}$. Thus, to achieve
translational invariance, Lebesgue measure uses a $\sigma$-algebra smaller
than $\mathcal{P}([0,1))$, in which the Vitali sets are among the non-
measurable sets. However, the translational invariance desideratum is not
relevant to our space of discrete sequences. A theorem by Ulam (1930) reveals
a deeper reason that some sets must be non-measurable. We shall state the
theorem below as given in Oxtoby (1980) and omit its proof. We refer
interested readers to Chapter 5 in Oxtoby (1980), which contains an accessible
proof and an excellent discussion of the theorem including its generalizations
and historical context.

######  Theorem C.1 (Ulam, 1930).

Assuming the Axiom of Choice, a finite measure $\mu$ defined for all subsets
of a set $X$ of cardinality $\aleph_{1}$ vanishes identically [that is, equals
zero for all subsets] if it is equal to zero for every one-element subset.

In the statement above, $\aleph_{1}$ denotes the cardinality of the first
uncountable ordinal. We can see that Thm. 3.5 is a straightforward consequence
of Thm. C.1.

###### Proof of Thm. 3.5.

Recall that
$\mathrm{card}(\\{\texttt{H},\texttt{T}\\}^{\infty})=2^{\aleph_{0}}$. Assuming
the Continuum Hypothesis, $2^{\aleph_{0}}=\aleph_{1}$, and hence by Thm. C.1,
such a measure is uniformly 0, and hence cannot be a probability measure. ∎

####  C.1.2 Other Proofs in § 3.3

See 3.9

###### Proof.

First, $\Omega\in\overline{\mathcal{C}}$ since it is a cylinder set of rank 0
or indeed of any rank $k$:
$\Omega=\overline{C}(\overline{\Sigma}^{k})\in\overline{\mathcal{C}}_{k}\subset\overline{\mathcal{C}}$.
Second, $\overline{\mathcal{C}}$ is closed under complements: given a cylinder
set of rank $k$, that is, $\overline{C}(H)$ where
$H\subseteq\overline{\Sigma}^{k}$, its complement
$\big{(}\overline{C}(H)\big{)}^{\mathsf{c}}=\overline{C}\left(\overline{\Sigma}^{k}\setminus
H\right)$ is also a cylinder set of rank $k$. Finally,
$\overline{\mathcal{C}}$ is closed under union: the union of cylinder sets of
ranks $k_{1}\leq k_{2}$ is a cylinder set of rank $k_{2}$, since both can be
regarded as cylinder sets of rank $k_{2}$. Hence, $\overline{\mathcal{C}}$ is
an algebra over $\Omega$. ∎

######  Proposition C.2.

$\mathbb{P}_{0}$ as defined in Eq. 8 is a well-defined function.

###### Proof.

Suppose a cylinder set arises in two ways,
$\overline{C}(H_{1})=\overline{C}(H_{2})$, where
$H_{1}\subseteq\overline{\Sigma}^{k_{1}}$ and
$H_{2}\subseteq\overline{\Sigma}^{k_{2}}$. We must show $\sum_{\bm{x}\in
H_{1}}\bar{p}(\bm{x})=\sum_{\bm{x^{\prime}}\in
H_{2}}\bar{p}(\bm{x^{\prime}})$. Without loss of generality, assume that
$k_{1}\leq k_{2}$. The definition of $\overline{C}(H_{2})$ (Def. 3.8) implies
that $H_{2}$ consists of all length-$k_{2}$ prefixes of strings in
$\overline{C}(H_{2})$. But $\overline{C}(H_{2})=\overline{C}(H_{1})$, so the
definition of $\overline{C}(H_{1})$ (Def. 3.8) implies that its length-$k_{2}$
prefixes are exactly the strings of the form $\bm{x}\bm{y}$ where $\bm{x}\in
H_{1},\bm{y}\in\overline{\Sigma}^{k_{2}-k_{1}}$. Hence we can write $H_{2}$ in
terms of $H_{1}$ as $H_{2}=\\{\bm{x}\bm{y}:\bm{x}\in
H_{1},\bm{y}\in\overline{\Sigma}^{k_{2}-k_{1}}\\}$. Thus

$\displaystyle\sum_{\bm{x^{\prime}}\in H_{2}}\bar{p}(\bm{x^{\prime}})$
$\displaystyle=\sum_{\bm{x}\in
H_{1}}\sum_{\bm{y}\in\overline{\Sigma}^{k_{2}-k_{1}}}\bar{p}(\bm{x}\bm{y})=\sum_{\bm{x}\in
H_{1}}\bar{p}(\bm{x})$ (28)

where the last equality is true because $\bar{p}$ is defined by the locally
normalized product 9. ∎

See 3.10 For the proof of Lemma 3.10, we will mostly follow the proof of Thm
2.3 in Billingsley (1995), with the exception of invoking the Tychonoff
theorem directly. This proof depends on the following lemma, which is Example
2.10 in Billingsley (1995). We repeat the statement and proof here for the
reader’s convenience.

######  Lemma C.3.

Let $\mathbb{P}_{0}$ be a finitely additive probability pre-measure over
$\overline{\mathcal{C}}$ such that, given a decreasing sequence of sets
$A_{1}\supset A_{2}\supset\dotsm$ in $\overline{\mathcal{C}}$ where
$\bigcap_{n=1}^{\infty}A_{n}=\emptyset$,
$\lim_{n\to\infty}\mathbb{P}_{0}(A_{n})=0$. Then, $\mathbb{P}_{0}$ is also
countably additive over $\overline{\mathcal{C}}$.

###### Proof.

Let $\\{A_{n}\\}$ be a sequence of disjoint sets in $\overline{\mathcal{C}}$
such that $A=\bigcup_{n}A_{n}\in\overline{\mathcal{C}}$. Then, defining
$B_{n}=\bigcup_{m>n}A_{m}$, we see that $B_{1}\supset B_{2}\supset\dotsm$ and
$\bigcap_{n}B_{n}=\emptyset$. Notice that

$A=A_{1}\cup B_{1}=A_{1}\cup A_{2}\cup B_{2}=\dotsm=A_{1}\cup\dotsm\cup
A_{n}\cup B_{n}$ (29)

for any $n$ and hence by finite additivity of $\mathbb{P}_{0}$

$\mathbb{P}_{0}(A)=\mathbb{P}_{0}(A_{1})+\dotsm+\mathbb{P}_{0}(A_{n})+\mathbb{P}_{0}(B_{n})$
(30)

or equivalently

$\mathbb{P}_{0}(A_{1})+\dotsm+\mathbb{P}_{0}(A_{n})=\mathbb{P}_{0}(A)-\mathbb{P}_{0}(B_{n}).$
(31)

Since, $B_{n}\downarrow\emptyset$ implies that
$\mathbb{P}_{0}(B_{n})\downarrow 0$ by assumption, taking the limits on both
sides of Eq. 31 yields

$\sum_{n}\mathbb{P}_{0}(A_{n})=\lim_{n\to\infty}\sum_{i\leq
n}\mathbb{P}_{0}(A_{i})=\mathbb{P}_{0}(A)-\lim_{n\to\infty}\mathbb{P}_{0}(B_{n})=\mathbb{P}_{0}(A)$
(32)

which shows countable additivity. ∎

We also recall the Tychonoff theorem.212121See §37 in Munkres (2000) for a
detailed and well-written treatise.

######  Theorem C.4 (Tychonoff).

Let $\\{X_{\alpha}\\}_{\alpha\in J}$ be an indexed family of compact
topologies. Then, their product topology $\prod_{\alpha\in J}X_{\alpha}$ is
also compact.

We can now give the proof for Lemma 3.10.

###### Proof of Lemma 3.10.

We first show that $\mathbb{P}_{0}$ is finitely additive over
$\overline{\mathcal{C}}$. Let $C(H_{1})$ and $C(H_{2})$ be two disjoint
cylinder sets. By Prop. C.2, we can assume they are of the same rank without
loss of generality. Then,

$\displaystyle C(H_{1})\cup C(H_{2})$ $\displaystyle=\bigcup_{\bm{x}\in
H_{1}}\\{\bm{x}\bm{\omega}:\bm{\omega}\in\overline{\Sigma}^{\infty}\\}\cup\bigcup_{\bm{x}\in
H_{2}}\\{\bm{x}\bm{\omega}:\bm{\omega}\in\overline{\Sigma}^{\infty}\\}$ (33a)
$\displaystyle=\bigcup_{\bm{x}\in H_{1}\cup
H_{2}}\\{\bm{x}\bm{\omega}:\bm{\omega}\in\overline{\Sigma}^{\infty}\\}\qquad\text{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}($H_{1}$
and $H_{2}$ equal rank and disjoint)}}$ (33b) $\displaystyle=C(H_{1}\cup
H_{2})$ (33c)

which leads to

$\displaystyle\mathbb{P}_{0}(C(H_{1})\cup C(H_{2}))$
$\displaystyle=\mathbb{P}_{0}(C(H_{1}\cup H_{2}))=\sum_{\bm{x}\in H_{1}\cup
H_{2}}\bar{p}(\bm{x})=\mathbb{P}_{0}(C(H_{1}))+\mathbb{P}_{0}(C(H_{2})).$
(34a)

Hence, $\mathbb{P}_{0}$ is finitely additive.

Now, equip $\overline{\Sigma}$ with the discrete topology. Since
$\overline{\Sigma}$ is finite, it is compact under the discrete topology and
so is $\overline{\Sigma}^{\infty}$ by Thm. C.4. Then, by properties of the
product topology over discrete finite spaces, all cylinder sets in
$\overline{\Sigma}^{\infty}$ are compact. To apply Lemma C.3, let
$C_{1}\supset C_{2}\supset\dotsm$ be a decreasing sequence of cylinder sets
with empty intersection. Suppose to the contrary that
$\mathbb{P}_{0}\left(\bigcap_{n}C_{n}\right)>0$. This would imply that all
$C_{n}$ are nonempty (any of these being empty would result in a measure 0).
However, by Cantor’s intersection theorem222222Cantor’s intersection theorem
states that a decreasing sequence of nonempty compact sets have a nonempty
intersection. A version of this result in introductory real analysis is the
Nested Interval Theorem., $\bigcap_{n}C_{n}$ is nonempty, contradicting the
assumption. Hence, $\mathbb{P}_{0}\left(\bigcap_{n}C_{n}\right)=0$, and by
Lemma C.3, $\mathbb{P}_{0}$ is countably additive. ∎

###  C.2 Details in § 3.4

####  C.2.1 Carathéodory’s Extension Theorem

See 3.11

###### Proof Sketch.

First, construct an outer measure by approximation with countable coverings.
Then, show that the collection of sets that is measurable with respect to this
outer measure is a $\sigma$-algebra $\mathcal{F}$ that contains $\mathcal{A}$.
Finally, restricting the outer measure to this $\sigma$-algebra, one is then
left with a probability space. To show minimality, one can show that
$\mathcal{F}$ is contained in any $\sigma$-algebra that contains
$\mathcal{A}$. Uniqueness is given by applying Dynkin’s $\pi$-$\lambda$
theorem (Theorem 3.2 in Billingsley, 1995).

Great care must be taken in each step involved in the outline above. To
address these is well beyond the scope of this paper and we refer reader to
the many excellent texts with a proof of this theorem, such as Chapter 12 in
Royden (1988) and Chapter 11 in Billingsley (1995). ∎

####  C.2.2 The Space of Non-measurable Sets

Non-measurable sets are, in general, difficult to find. Even when we can
exhibit such sets, they tend to be very abstract and counter-intuitive.
Vitali’s and Bernstein’s sets are two prominent examples for the Lebesgue
measure. Blackwell and Diaconis (1996) offers a construction of a non-
measurable set in the cylinder $\sigma$-algebra.232323The following assumes
basic familiarity with the theory of ordinal numbers. Readers without such
background may skip to the last paragraph for conclusion.

As another approach to understand this better, we can consider how our
collection $\sigma(\overline{\mathcal{C}})$ of all measurable sets, i.e., our
$\sigma$-algebra, is constructed from our algebra $\overline{\mathcal{C}}$ of
cylinder sets (as opposed to simply knowing from Carathéodory’s Extension
Theorem that it exists). Concretely, as in §1.6 in Folland (1999), we can
intuitively consider the following process to build from the collection of
cylinder sets $\overline{\mathcal{C}}$, which is a countable collection, all
the way up to its generated $\sigma$-algebra, whose cardinality is unknown
just yet:

  * •

Let $\overline{\mathcal{C}}_{0}=\overline{\mathcal{C}}$,

  * •

Let $\overline{\mathcal{C}}_{1}$ be the set that includes all countable unions
of sets in $\overline{\mathcal{C}}_{0}$ or the complements of such,

  * •

Repeat this process to build $\overline{\mathcal{C}}_{n}$ for every
$n\in\mathbb{N}$.

One might then take the union
$\bigcup_{n\in\mathbb{N}}\overline{\mathcal{C}}_{n}$ of this increasing
sequence of collections of sets, and ask if it is the same as
$\sigma(\overline{\mathcal{C}})$. In general, the answer is no (as one might
expect if one is familiar with the Borel Hierarchy). However, we can obtain
$\sigma(\overline{\mathcal{C}})$ if we perform this construction for every
countable ordinal $\alpha$. Abbreviating the operation in the second step
above as $\delta$, i.e.,
$\overline{\mathcal{C}}_{1}=\delta(\overline{\mathcal{C}}_{0})$, and letting
$\omega_{1}$ be the collection of all countable ordinals,242424$\omega_{1}$
is, in fact, the same as the first uncountable ordinal. Its existence (and
hence the existence of the collection of all countable ordinals) can be
guaranteed by exhibiting a well-ordered uncountable set using the Axiom of
Choice. we can define

$\displaystyle\overline{\mathcal{C}}_{\alpha}=\begin{cases}\delta(\overline{\mathcal{C}}_{\beta})&\text{if
}\alpha=\beta+1\text{ for some }\beta\in\omega_{1},\\\
\bigcup_{\beta\in\omega_{1}:\beta<\alpha}\overline{\mathcal{C}}_{\beta}&\text{otherwise}.\end{cases}$
(35)

This will give us the desired set as follows:

######  Proposition C.5 (Proposition 1.23, Folland, 1999).

$\sigma(\overline{\mathcal{C}})=\bigcup_{\alpha\in\omega_{1}}\overline{\mathcal{C}}_{\alpha}$.

Next, we recall the following basic fact from cardinality theory.

######  Proposition C.6 (Proposition 0.14, Folland, 1999).

If $\mathrm{card}(A)\leq 2^{\aleph_{0}}$ and $\mathrm{card}(X_{\alpha})\leq
2^{\aleph_{0}}$ for all $\alpha\in A$, then
$\mathrm{card}\left(\bigcup_{\alpha\in A}X_{\alpha}\right)\leq
2^{\aleph_{0}}$.

Noting that $\mathrm{card}(\omega_{1})\leq 2^{\aleph_{0}}$ and
$\mathrm{card}(\overline{\mathcal{C}})={\aleph_{0}}$, we can conclude that
$\mathrm{card}(\sigma(\overline{\mathcal{C}}))\leq 2^{\aleph_{0}}$ from Prop.
C.5 and Prop. C.6. In other words, the cardinality of
$\sigma(\overline{\mathcal{C}})$ is at most that of the continuum, and since
$\mathrm{card}\big{(}\mathcal{P}(\overline{\Sigma}^{\infty})\big{)}=2^{2^{\aleph_{0}}}(=\beth_{2})$,
$\sigma(\overline{\mathcal{C}})$ is, in terms of cardinality, an almost
negligible subset of $\mathcal{P}(\overline{\Sigma}^{\infty})$! That is, most
subsets in $\overline{\Sigma}^{\infty}$ are non-measurable—though explicit
examples have rarely been constructed Blackwell and Diaconis (1996). § C.3
below establishes that common subsets of $\overline{\Sigma}^{\infty}$ that we
work with are measurable.

###  C.3 Proofs in § 3.5

See 3.13

###### Proof.

To show that $X$ is measurable, it suffices to show the measurability of
preimages of a generating set252525A set $G$ is said to be a generating set of
a $\sigma$-algebra $\mathcal{F}$ if $\mathcal{F}$ is the smallest
$\sigma$-algebra that contains $G$. of the $\sigma$-algebra
$\sigma(\mathcal{C})$ on $\Sigma^{*}\cup\Sigma^{\infty}$. Such a generating
set is formed by the thin cylinders
$C(\bm{x})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}C(\\{\bm{x}\\})$
for $\bm{x}\in\Sigma^{*}$. (Recall that cylinders in
$\Sigma^{*}\cup\Sigma^{\infty}$ are defined by Eq. 11.) Given
$\bm{x}\in\Sigma^{*}$:

$\displaystyle X^{-1}(C(\bm{x}))=$ $\displaystyle
X^{-1}(\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{*}\cup\Sigma^{\infty}\\})$
(36a) $\displaystyle=$ $\displaystyle
X^{-1}(\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{*}\\})\cup
X^{-1}(\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{\infty}\\})$ (36b)
$\displaystyle=$
$\displaystyle\left(\bigcup_{\bm{\omega}\in\Sigma^{*}}\overline{C}(\bm{x}\bm{\omega}\,\textsc{eos})\right)\cup\left(\overline{C}(\bm{x})\cap\bigcap_{k=1}^{\infty}A^{\mathsf{c}}_{k}\right)$
(36c)

Note that the set $A_{k}$ above, defined by Eq. 16, is a cylinder of
$\overline{\Sigma}^{\infty}$, representing the event of terminating by step
$k$. Then, from the derivation above, we can see that $X^{-1}(C(\bm{x}))$ is
formed by countable operations over measurable sets (cylinders) of
$\overline{\Sigma}^{\infty}$, and is hence measurable. So $X$ is a measurable
function. ∎

######  Proposition C.7.

In measure space $(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$,
$\\{\bm{x}\\}$ is measurable for all $\bm{x}\in\Sigma^{*}$.

###### Proof.

We will show that
$\\{\bm{x}\\}=C(\bm{x})\setminus\bigcup_{a\in\Sigma}C(\bm{x}a)$ and hence is
measurable. By definition in Eq. 11, for any $\bm{x}\in\Sigma^{*}$,

$\displaystyle C(\bm{x})$
$\displaystyle=\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{*}\cup\Sigma^{\infty}\\}$
(37a)
$\displaystyle=\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{*}\\}\cup\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{\infty}\\}$
(37b)

where

$\displaystyle\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{*}\\}=\\{\bm{x}\\}\cup\bigcup_{a\in\Sigma}\\{\bm{x}a\bm{\omega}:\bm{\omega}\in\Sigma^{*}\\}$
(38a)

and

$\displaystyle\\{\bm{x}\bm{\omega}:\bm{\omega}\in\Sigma^{\infty}\\}=\bigcup_{a\in\Sigma}\\{\bm{x}a\bm{\omega}:\bm{\omega}\in\Sigma^{\infty}\\}.$
(39)

So

$\displaystyle C(\bm{x})$
$\displaystyle=\\{\bm{x}\\}\cup\bigcup_{a\in\Sigma}\bigg{(}\\{\bm{x}a\bm{\omega}:\bm{\omega}\in\Sigma^{*}\\}\cup\\{\bm{x}a\bm{\omega}:\bm{\omega}\in\Sigma^{\infty}\\}\bigg{)}$
(40a) $\displaystyle=\\{\bm{x}\\}\cup\bigcup_{a\in\Sigma}C(\bm{x}a)$ (40b)

where the union is disjoint. This implies
$\\{\bm{x}\\}=C(\bm{x})\setminus\bigcup_{a\in\Sigma}C(\bm{x}a)$ as desired. ∎

######  Proposition C.8.

In the measure space $(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$,
$\Sigma^{\infty}$ is measurable.

###### Proof.

First, $\Sigma^{*}\cup\Sigma^{\infty}$ is the entire outcome space, which is
measurable by the definition of $\sigma$-algebra. Notice that

$\displaystyle\Sigma^{\infty}=(\Sigma^{*}\cup\Sigma^{\infty})\setminus\bigcup_{\bm{x}\in\Sigma^{*}}\\{\bm{x}\\}.$
(41)

Since each $\\{\bm{x}\\}$ in the above is measurable by Prop. C.7 and
$\Sigma^{*}$ is a countable set, $\Sigma^{\infty}$ is then measurable. ∎

The measurability of $\Sigma^{\infty}$ in
$(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}))$ (Prop. C.8) was assumed
by our definition of tightness (Def. 4.1). As we have also established that
each $\\{\bm{x}\\}$ is measurable (Prop. C.7), we can give an alternative
characterization.

######  Proposition C.9.

A sequence model $(\Sigma^{*}\cup\Sigma^{\infty},\sigma(\mathcal{C}),P)$ is
tight if and only if $\sum_{\bm{x}\in\Sigma^{*}}P(\\{\bm{x}\\})=1$.

###### Proof.

We defined a sequence model to be tight if and only if $P(\Sigma^{\infty})=0$
(Def. 4.1). By Propositions C.7 and C.8, we can write

$\displaystyle 1=P(\Sigma^{*}\cup\Sigma^{\infty})$
$\displaystyle=P(\Sigma^{\infty})+P(\Sigma^{*})$ (finite additivity) (42a)
$\displaystyle=P(\Sigma^{\infty})+\sum_{\bm{x}\in\Sigma^{*}}P(\\{\bm{x}\\}).$
(countable additivity) (42b)

Hence, a sequence model is tight if and only if
$\sum_{\bm{x}\in\Sigma^{*}}P(\\{\bm{x}\\})=1$. ∎

##  Appendix D Proofs on Characterizing Tightness (§ 4)

###  D.1 Proof of Lemma 4.2

The result below is stated without proof as Exercise 4.3.5 in Durrett (2019).

See 4.2

###### Proof.

First, recall an elementary inequality that for $x>0$,

$\displaystyle x-1\geq\log x\quad\Leftrightarrow\quad 1-x\leq\log\frac{1}{x}.$
(43)

Note that $\mathbb{P}(\cap_{m=1}^{n}A_{m}^{\mathsf{c}})>0$ for any $n$, for
otherwise the conditional probabilities would be undefined. Let
$p_{n}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathbb{P}(\cap_{m=1}^{n}A_{m}^{\mathsf{c}})$.
Then we have that $p_{n}>0$ for all $n$, and

$\displaystyle\infty$
$\displaystyle=\sum_{n=2}^{\infty}\mathbb{P}(A_{n}\mid\cap_{m=1}^{n-1}A_{m}^{\mathsf{c}})$
(44a)
$\displaystyle=\sum_{n=2}^{\infty}1-\mathbb{P}(A_{n}^{\mathsf{c}}\mid\cap_{m=1}^{n-1}A_{m}^{\mathsf{c}})$
(44b)
$\displaystyle=\lim_{N\to\infty}\sum_{n=2}^{N}1-\mathbb{P}(A_{n}^{\mathsf{c}}\mid\cap_{m=1}^{n-1}A_{m}^{\mathsf{c}})$
(44c) $\displaystyle\leq\lim_{N\to\infty}\sum_{n=2}^{N}\log
1/\mathbb{P}(A_{n}^{\mathsf{c}}\mid\cap_{m=1}^{n-1}A_{m}^{\mathsf{c}})$ (by
Eq. 43) (44d)
$\displaystyle=\lim_{N\to\infty}\sum_{n=2}^{N}\log\frac{\mathbb{P}(\cap_{m=1}^{n-1}A_{m}^{\mathsf{c}})}{\mathbb{P}(\cap_{m=1}^{n}A_{m}^{\mathsf{c}})}$
(44e) $\displaystyle=\lim_{N\to\infty}\sum_{n=2}^{N}\log\frac{p_{n-1}}{p_{n}}$
(44f) $\displaystyle=\lim_{N\to\infty}\sum_{n=2}^{N}(\log p_{n-1}-\log p_{n})$
(44g) $\displaystyle=\lim_{N\to\infty}(\log p_{1}-\log p_{N})$ (44h)
$\displaystyle=\log p_{1}-\lim_{N\to\infty}\log p_{N}$ (44i)

which implies that

$\displaystyle\lim_{N\to\infty}\log p_{N}=-\infty$ (45a)
$\displaystyle\Leftrightarrow\quad$ $\displaystyle\lim_{N\to\infty}p_{N}=0$
(45b) $\displaystyle\Leftrightarrow\quad$
$\displaystyle\lim_{N\to\infty}\mathbb{P}(\cap_{m=1}^{N}A_{m}^{\mathsf{c}})=0$
(45c) $\displaystyle\Leftrightarrow\quad$
$\displaystyle\mathbb{P}(\cap_{m=1}^{\infty}A_{m}^{\mathsf{c}})=0.$ (by
continuity of measure) (45d)

∎

###  D.2 Proof of Prop. 4.3

See 4.3

###### Proof.

In the proof, we rename the index $t$ to $n$ to match the usual presentation
of the Borel-Cantelli lemmata. We are given that
$\bar{p}(\textsc{eos}\mid\bm{x})\geq f(n)$ for all $\bm{x}\in\Sigma^{n-1}$. To
apply Lemma 4.2, we observe that

$\displaystyle A_{n}\cap(A_{1}^{\mathsf{c}}\cap\dotsm\cap
A_{n-1}^{\mathsf{c}})=$
$\displaystyle\\{\bm{\omega}\in\overline{\Sigma}^{\infty}:\omega_{n}=\textsc{eos}\\}~{}\cap\left(\bigcap_{i=1}^{n-1}\\{\bm{\omega}\in\overline{\Sigma}^{\infty}:\omega_{i}\not=\textsc{eos}\\}\right)$
(46a) $\displaystyle=$
$\displaystyle\\{\bm{\omega}\in\overline{\Sigma}^{\infty}:\bm{\omega}=\textsc{eos},\forall~{}i<n,\bm{\omega}\not=\textsc{eos}\\}$
(46b) $\displaystyle=$
$\displaystyle\\{\bm{\omega}\in\overline{\Sigma}^{\infty}:\text{$\bm{\omega}$'s
first {eos} is at position $n$}\\}$ (46c)

and similarly

$A_{1}^{\mathsf{c}}\cap\dotsm\cap
A_{n-1}^{\mathsf{c}}=\\{\bm{\omega}\in\overline{\Sigma}^{\infty}:\text{there
is no {eos} in $\bm{\omega}$'s first $n-1$ positions}\\}$ (47)

Setting
$G\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\\{\bm{\omega}\,\textsc{eos}:\bm{\omega}\in\Sigma^{n-1}\\}\subset\overline{\Sigma}^{n}$,
we get

$\displaystyle\mathbb{P}(A_{n}\mid A_{1}^{\mathsf{c}}\cap\dotsm\cap
A_{n-1}^{\mathsf{c}})$
$\displaystyle=\frac{\mathbb{P}(A_{n}\cap(A_{1}^{\mathsf{c}}\cap\dotsm\cap
A_{n-1}^{\mathsf{c}}))}{\mathbb{P}(A_{1}^{\mathsf{c}}\cap\dotsm\cap
A_{n-1}^{\mathsf{c}})}$ (48a)
$\displaystyle=\frac{\mathbb{P}(\overline{C}(G))}{\mathbb{P}(\overline{C}(\Sigma^{n-1}))}$
(definition of $G$) (48b)
$\displaystyle=\frac{\sum_{\bm{\omega}\in\Sigma^{n-1}}\bar{p}(\textsc{eos}\mid\bm{\omega})\bar{p}(\bm{\omega})}{\sum_{\bm{\omega}\in\Sigma^{n-1}}\bar{p}(\bm{\omega})}$
(by Eq. 8) (48c)
$\displaystyle\geq\frac{\sum_{\bm{\omega}\in\Sigma^{n-1}}f(n)\bar{p}(\bm{\omega})}{\sum_{\bm{\omega}\in\Sigma^{n-1}}\bar{p}(\bm{\omega})}$
(definition of $f(n)$) (48d)
$\displaystyle=f(n)\frac{\sum_{\bm{\omega}\in\Sigma^{n-1}}\bar{p}(\bm{\omega})}{\sum_{\bm{\omega}\in\Sigma^{n-1}}\bar{p}(\bm{\omega})}$
(48e) $\displaystyle=f(n).$ (48f)

Since $\sum_{n=1}^{\infty}f(n)=\infty$ and hence
$\sum_{n=2}^{\infty}f(n)=\infty$, the above inequality shows that the
condition of Lemma 4.2 holds. Hence by Lemma 4.2, the event of a string never
terminating, i.e., $\cap_{k=1}^{\infty}A_{k}^{\mathsf{c}}$, has probability
measure $\mathbb{P}(\cap_{k=1}^{\infty}A_{k}^{\mathsf{c}})=0$.

In summary, if the eos probability of a language model is lower-bounded at
ever steps by the terms of a divergent series, then the event that this
language model terminates has probability 1. ∎

###  D.3 Proof of Cor. 4.6

To show Cor. 4.6, we first show the following simple consequence of
Borel–Cantelli.

######  Corollary D.1.

If $\mathbb{P}(A_{n}\text{ i.o.})=1$, then
$\sum_{n=1}^{\infty}\mathbb{P}(A_{n})=\infty$.

###### Proof.

Suppose to the contrary that $\sum_{n=1}^{\infty}\mathbb{P}(A_{n})<\infty$,
then, by Borel–Cantelli I (Lemma 4.4), $\mathbb{P}(A_{n}\text{ i.o.})=0$,
which contradicts the assumption. Hence,
$\sum_{n=1}^{\infty}\mathbb{P}(A_{n})=\infty$.

∎

Cor. 4.6 below is also stated without proof as Exercise 4.3.4 in Durrett
(2019). See 4.6

###### Proof.

We can use a product measure to construct a sequence of independent events
$\\{A_{n}\\}_{n=1}^{\infty}$ such that $\mathbb{P}(A_{n})=p_{n}$. (The product
measure ensures independence.) Then, by definition in Eq. 18,

$\displaystyle\\{A_{n}\text{
i.o.}\\}^{\textsf{c}}=\bigcup_{m=1}^{\infty}\bigcap_{n\geq
m}A_{n}^{\textsf{c}}$ (49)

So,

$\displaystyle 1-\mathbb{P}(A_{n}\text{ i.o.})$
$\displaystyle=\mathbb{P}\left(\bigcup_{m}\bigcap_{n\geq
m}A_{n}^{\textsf{c}}\right)$ (50a)
$\displaystyle=\lim_{m\to\infty}\mathbb{P}\left(\bigcap_{n\geq
m}A_{n}^{\textsf{c}}\right)$ (50b)
$\displaystyle=\lim_{m\to\infty}\prod_{n\geq m}\mathbb{P}(A_{n}^{\textsf{c}})$
($A_{n}$ are independent by construction) (50c)
$\displaystyle=\lim_{m\to\infty}\prod_{n\geq m}(1-p_{n})$ (50d)

#####  $(\Rightarrow)$:

Assume $\prod_{n=1}^{\infty}(1-p_{n})=0$. Then, for any $m$,

$0=\prod_{n\geq 1}(1-p_{n})=\underbrace{\left(\prod_{1\leq
n<m}(1-p_{n})\right)}_{>0}\left(\prod_{n\geq m}(1-p_{n})\right)$ (51)

So it must the case that, for any $m$, $\prod_{n\geq m}(1-p_{n})=0$.
Therefore,

$1-\mathbb{P}(A_{n}\text{ i.o.})=\lim_{m\rightarrow\infty}\prod_{n\geq
m}(1-p_{n})=0$ (52)

which implies $\mathbb{P}(A_{n}\text{ i.o.})=1$. Cor. D.1 implies that
$\sum_{n=1}^{\infty}p_{n}=\infty$.

#####  $(\Leftarrow)$:

Assume $\sum_{n=1}^{\infty}p_{n}=\infty$. Then by Borel–Cantelli II (Lemma
4.5), $\mathbb{P}(A_{n}\text{ i.o.})=1$ which implies

$0=1-\mathbb{P}(A_{n}\text{ i.o.})=\lim_{m\rightarrow\infty}\prod_{n\geq
m}(1-p_{n})$ (53)

Observe that $\Big{\\{}\prod_{n\geq m}(1-p_{n})\Big{\\}}_{m}$ is a non-
decreasing sequence in $m$; to see this, note that as $m$ grows larger we
multiply strictly fewer values $(1-p_{n})\in(0,1]$. However, since we know the
sequence is non-negative and tends to $0$, it follows that for _any_ $m$, we
have

$\displaystyle\prod_{n\geq m}(1-p_{n})=0.$ (54)

It follows that, for any $m$, we have

$\prod_{n=1}^{\infty}(1-p_{n})=\prod_{n<m}(1-p_{n})\underbrace{\prod_{n\geq
m}(1-p_{n})}_{=0}=\prod_{n<m}(1-p_{n})\cdot 0=0.$ (55)

∎

###  D.4 Proof of Thm. 4.7

See 4.7

###### Proof.

Recall the definition of $\widetilde{p}_{\textsc{eos}}$, as previously defined
in Eq. 20, is

$\displaystyle\widetilde{p}_{\textsc{eos}}(t)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathbb{P}(A_{t}\mid
A_{1}^{\mathsf{c}}\cap\dotsm\cap A_{t-1}^{\mathsf{c}}).$ (56)

##### Case 1.

Suppose that $\widetilde{p}_{\textsc{eos}}(t)<1$ for all $t$. Consider the
termination probability again:

$\displaystyle\mathbb{P}\left(\bigcap_{t=1}^{\infty}A_{t}^{\mathsf{c}}\right)$
$\displaystyle=\lim_{T\to\infty}\mathbb{P}\left(\bigcap_{t=1}^{T}A_{t}^{\mathsf{c}}\right)$
(57a)
$\displaystyle=\lim_{T\to\infty}\prod_{t=1}^{T}\mathbb{P}(A_{t}^{\mathsf{c}}\mid
A_{1}^{\mathsf{c}}\cap\dotsm\cap A_{t-1}^{\mathsf{c}})$ (57b)
$\displaystyle=\lim_{T\to\infty}\prod_{t=1}^{T}(1-\widetilde{p}_{\textsc{eos}}(t))$
(57c) $\displaystyle=\prod_{t=1}^{\infty}(1-\widetilde{p}_{\textsc{eos}}(t)).$
(57d)

In the above, we have assumed that
$\mathbb{P}(A_{1}^{\mathsf{c}}\cap\dotsm\cap A_{t}^{\mathsf{c}})>0$ for all
$t$, which is true by assumption that $\widetilde{p}_{\textsc{eos}}(t)<1.$.
Hence, by Cor. 4.6, Eq. 57d is $0$ if and only if
$\sum_{t}\widetilde{p}_{\textsc{eos}}(t)=\infty$.

##### Case 2.

If $\widetilde{p}_{\textsc{eos}}(t)=1$ is true for some $t=t_{0}$, then
$\mathbb{P}(A_{1}^{\mathsf{c}}\cap\dotsm\cap A_{t_{0}}^{\mathsf{c}})=0$ and
hence $\mathbb{P}\left(\bigcap_{t=1}^{\infty}A_{t}^{\mathsf{c}}\right)=0$ and
such a language model is guaranteed to terminate at $t_{0}$. ∎

##  Appendix E Proofs for Analyses of Common Language Models (§ 5)

###  E.1 Proofs for FSSMs (§ 5.1)

####  E.1.1 Proofs for Stochastic FSSMs

See 5.3

###### Proof.

We refer to a state $q$ as initial if $s_{q}>0$ and as final if $t_{q}>0$.
(These are sometimes called source and sink states.) We prove each direction
of the theorem in turn:

##### ($\Rightarrow$):

Assume the SFSSM is tight. Let $q$ be an accessible state. Since the SFSSM has
at least one positive-probability path from an initial state, there is a
positive probability of reaching $q$ during generation. If there were no
positive-probability path from $q$ to a final state, then the SFSSM would
never terminate on the occasions when it reached $q$, contradicting the
assumption of tightness. Hence $q$ must be co-accessible.

##### ($\Leftarrow$):

Assume that all accessible states are co-accessible. We construct a Markov
chain whose states are the SFSSM’s accessible states
$Q_{A}\subseteq\\{1,\ldots,Q\\}$ together with an eos state. In this Markov
chain, the initial probability of $q$ is given by $s_{q}$ when $q\in Q_{A}$
and by $0$ when $q=\textsc{eos}$; the transition probability from $q$ to
$q^{\prime}$ is given by ${\mathbf{P}}_{qq^{\prime}}$ when $q,q^{\prime}\in
Q_{A}$, by $t_{q}$ when $q\in Q_{A}$ and $q^{\prime}=\textsc{eos}$, by $1$
when $q=q^{\prime}=\textsc{eos}$, and by $0$ otherwise. The probability that
the Markov chain is in state $q\in Q_{A}$ after $t$ steps equals the
probability that the SFSSM is in state $q$ after $t$ steps (note that the
SFSSM never reaches any state $q\notin Q_{A}$). The probability that it is in
state eos after $t$ steps equals the probability that the SFSSM has terminated
after $\leq t$ steps.

Clearly eos is an absorbing state of the Markov chain, meaning that once the
Markov chain reaches this state, it never leaves. A fundamental result on
finite-state Markov chains (Grinstead and Snell, 1997, Theorem 11.3) is that
if every state can reach an absorbing state, then with probability 1, the
chain reaches an absorbing state (“is absorbed”) in finite time. Every state
can in fact reach eos, by coaccessibility of $Q_{A}$. This further implies
that eos is the _only_ absorbing state (as an absorbing state cannot reach any
other state). So by the result cited above, the Markov chain reaches eos with
probability 1 in finite time. Consequently, the SFSSM terminates after
finitely many steps with probability 1; that is, the SFSSM is tight. ∎

See 5.4

###### Proof.

The SFSSM for an $n$-gram model has states that correspond to $(n-1)$-grams
and transitions that correspond to characters (unigrams), as illustrated by
Fig. 1. When the SFSSM’s probabilities are estimated with MLE, the accessible
states are $(n-1)$-grams that have appeared in some string in the corpus. Such
states must also be co-accessible so that they can generate the rest of that
string. Hence, by Thm. 5.3, this SFSSM is tight. ∎

####  E.1.2 Proofs for Substochastic FSSMs

To prove Thm. 5.6, we will make use of the following useful lemma.

######  Lemma E.1.

Let ${\mathbf{P}}^{\prime}$ be the transition sum matrix of a trimmed
substochastic FSSM. Then $\rho({\mathbf{P}}^{\prime})<1$ where $\rho(\cdot)$
denotes the spectral radius.

###### Proof.

To begin with, we wish to apply the following result, which connects the row
sums of a matrix to its spectral radius. Below, $M_{n}$ denotes the set of
$n\times n$ matrices, and
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\infty}=\max_{1\leq
i\leq n}\sum_{j=1}^{n}|A_{ij}|$ denotes the operator $\infty$-norm.

######  Proposition E.2 (§6.2.P8, Horn and Johnson, 2012).

For any $A\in M_{n}$,
$\rho(A)\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\infty}$.
Additionally, if $A$ is irreducible and not all absolute row sums of $A$ are
equal, then
$\rho(A)<{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\infty}$.

However, the transition sum matrix ${\mathbf{P}}$ of a substochastic FSSM may
be reducible, whereas the irreducibility condition in Prop. E.2 cannot be
dropped. Hence, we need to “decompose” ${\mathbf{P}}^{\prime}$ in a way that
recovers irreducibility. We use the _Frobenius normal form_ (also known as
_irreducible normal form_) to achieve this.

######  Proposition E.3 (§8.3.P8, Horn and Johnson, 2012).

Let $A\in M_{n}$ be non-negative. Then, either $A$ is irreducible or there
exists a permutation matrix $\Pi$ such that

$\displaystyle\Pi^{\top}A\Pi=\begin{bmatrix}A_{1}&&\ast\\\ &\ddots&\\\
\mathbf{0}&&A_{k}\end{bmatrix}$ (58)

is block upper triangular, and each diagonal block is irreducible (possibly a
$1\times 1$ zero matrix). This is called a Frobenius normal form (or
irreducible normal form) of $A$. Additionally,
$\lambda(A)=\lambda(A_{1})\cup\dotsm\cup\lambda(A_{k})$ where $\lambda(\cdot)$
denotes the set of eigenvalues of a matrix.

Notice that the permutation in the Frobenius normal form merely renumbers the
states of the trimmed FSSM. We may check that as a result, the termination
probability given in Thm. 5.6 is unchanged:262626The equalities here use the
fact that the inverse of a permutation matrix $\Pi$ is its transpose:
$\Pi\,\Pi^{\top}=I$.

$\displaystyle(\Pi^{\top}\bm{s}^{\prime})^{\top}(\Pi^{\top}{\mathbf{P}}^{\prime}\Pi)^{k}(\Pi^{\top}\bm{t}^{\prime})=(\bm{s}^{\prime\top}\Pi)(\Pi^{\top}{\mathbf{P}}^{\prime
k}\Pi)(\Pi^{\top}\bm{t}^{\prime})=\bm{s}^{\prime\top}{\mathbf{P}}^{\prime
k}\bm{t}^{\prime}$ (59)

Hence, with an appropriate renumbering, we may assume without loss of
generality that ${\mathbf{P}}$ is already given in Frobenius normal form

$\displaystyle{\mathbf{P}}^{\prime}=\begin{bmatrix}{\mathbf{P}}^{\prime}_{1}&&\ast\\\
&\ddots&\\\ \mathbf{0}&&{\mathbf{P}}^{\prime}_{k}\end{bmatrix}$ (60)

where each ${\mathbf{P}}^{\prime}_{i}$ is irreducible.

Since the transition sum matrix ${\mathbf{P}}^{\prime}$ of a trimmed
substochastic FSSM is a substochastic matrix, each ${\mathbf{P}}^{\prime}_{i}$
is also substochastic. In fact, each ${\mathbf{P}}^{\prime}_{i}$ is _strictly_
substochastic, meaning that there is at least one row that sums to less than
1. To see this, suppose to the contrary that there is a stochastic
${\mathbf{P}}^{\prime}_{i}$. Since the FSSM is trimmed, every state is both
accessible and co-accessible. Being accessible implies that there is a
positive probability of reaching every state in ${\mathbf{P}}^{\prime}_{i}$.
However, the stochasticity of ${\mathbf{P}}^{\prime}_{i}$ forces the
corresponding $\bm{t}^{\prime}$ entries to be 0. Hence, none of these states
can transition to eos, meaning that they’re not co-accessible, contradicting
the assumption. Hence, every ${\mathbf{P}}^{\prime}_{i}$ is strictly
substochastic. Then, either all row sums of ${\mathbf{P}}^{\prime}_{i}$ are
less than 1 (in which case
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|{\mathbf{P}}^{\prime}_{i}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\infty}<1$)
or some row sums are 1 and some are less than 1 (in which case
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|{\mathbf{P}}^{\prime}_{i}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\infty}=1$
and ${\mathbf{P}}^{\prime}$ has unequal absolute row sums). In either case,
Prop. E.2 implies that $\rho({\mathbf{P}}^{\prime}_{i})<1$, for all $1\leq
i\leq k$.

Finally, the last sentence of Prop. E.3 entails that
$\rho({\mathbf{P}}^{\prime})=\max\\{\rho({\mathbf{P}}^{\prime}_{1}),\dots,\rho({\mathbf{P}}^{\prime}_{k})\\}$.
Since each $\rho({\mathbf{P}}^{\prime}_{i})<1$, we have
$\rho({\mathbf{P}}^{\prime})<1$. ∎

See 5.6

###### Proof.

By Lemma E.1, $\rho({\mathbf{P}}^{\prime})<1$, in which case
${\mathbf{I}}-{\mathbf{P}}^{\prime}$ is invertible and the Neumann series
$\sum_{k=0}^{\infty}{\mathbf{P}}^{\prime
k}={\mathbf{I}}+{\mathbf{P}}^{\prime}+{\mathbf{P}}^{\prime 2}+\dotsm$
converges to $({\mathbf{I}}-{\mathbf{P}}^{\prime})^{-1}$ (Horn and Johnson,
2012, §5.6). Thus

$\displaystyle P(\Sigma^{\ast})$
$\displaystyle=\sum_{k=0}^{\infty}P(\Sigma^{k})=\sum_{k=0}^{\infty}\bm{s}^{\prime\top}{\mathbf{P}}^{\prime
k}\bm{t}^{\prime}=\bm{s}^{\prime\top}\left(\sum_{k=0}^{\infty}{\mathbf{P}}^{\prime
k}\right)\bm{t}^{\prime}=\bm{s}^{\prime\top}({\mathbf{I}}-{\mathbf{P}}^{\prime})^{-1}\bm{t}^{\prime}.$
(61)

∎

###  E.2 Proofs for Transformer Result (§ 5.2)

Again, the following theorem is well-known: See 5.7

###### Proof.

Let $\\{U_{\alpha}\\}_{\alpha\in\mathcal{A}}$ be any open cover of $f(X)$. By
continuity, $f^{-1}(U_{\alpha})\subset X$ is open for any
$\alpha\in\mathcal{A}$, and hence
$\\{f^{-1}(U_{\alpha})\\}_{\alpha\in\mathcal{A}}$ is also an open cover of
$X$. By the compactness of $X$, there is a finite sub-cover
$\\{f^{-1}(U_{\alpha_{i}})\\}_{i=1}^{n}$, in which case
$\\{U_{\alpha_{i}}\\}_{i=1}^{n}$ forms a finite sub-cover for $f(X)$. ∎

See 5.8

##### Note.

We make use of the following notations in the proof below:
$\triangle_{t-1}=\\{\bm{y}\in\mathbb{R}^{t}:\bm{y}\geq
0,\bm{1}^{\top}\bm{y}=1\\}$ denotes the $(t-1)$-dimensional simplex;
$B_{r}(\bm{z})=\\{\bm{v}\in\mathbb{R}^{n}:\text{dist}(\bm{z},\bm{v})<r\\}$
denotes the open ball centered at $\bm{z}$ with radius $r$; $\overline{A}$
denotes the closure of set $A$.

###### Proof.

Let $K_{0}=K$. In an autoregressive transformer, each of the $n$ layers
consists of two blocks: a self-attention block and a feedforward block. We
will use induction on the $2n$ blocks to build up compact sets
$K_{1},K_{2},\ldots,K_{2n}$ that contain the output vectors of these
respective blocks, and then take $K^{\prime}=K_{2n}$.

The self-attention block is a function on
$(\mathbb{R}^{d})^{+}\to(\mathbb{R}^{d})^{+}$. So, let $t\in\mathbb{Z}_{>0}$
be arbitrary and consider any sequence of input vectors
$(\bm{v}_{1},\dots,\bm{v}_{t})$ such that for all $i$, $\bm{v}_{i}\in K_{0}$.
Denote the output vectors of the attention block with
$(\bm{v}_{1}^{\prime},\dots,\bm{v}_{t}^{\prime})$. By definition of attention,
each output vector
$\bm{v}_{j}^{\prime}=\sum_{i=1}^{t}\alpha^{(j)}_{i}\bm{v}_{i}$ where
$\bm{\alpha}^{(j)}\in\triangle_{t-1}$ are the attention weight vectors
obtained through the softmax function. Compact sets in $\mathbb{R}^{d}$ are
bounded (by the Heine–Borel theorem), and hence there exists $M>0$ such that
$K_{0}\subseteq\overline{B_{M}(0)}$. Noting that the norm function $\|\cdot\|$
on $\mathbb{R}^{d}$ is convex, we have the following

$\displaystyle\|\bm{v}_{j}^{\prime}\|$
$\displaystyle=\left\|\sum_{i=1}^{t}\alpha^{(j)}_{i}\bm{v}_{i}\right\|$ (62a)
$\displaystyle\leq\sum_{i=1}^{t}\alpha^{(j)}_{i}\|\bm{v}_{j}\|$ ($\ast$)
$\displaystyle\leq\sum_{i=1}^{t}\alpha^{(j)}_{i}M=M$ (62b)

where ($\ast$ ‣ 62) results from Jensen’s inequality. Eq. 62b shows that each
of the output vectors $\bm{v}_{j}^{\prime}$ lies in $\overline{B_{M}(0)}$
which is compact. Hence, setting $K_{1}=\overline{B_{M}(0)}$, we have shown
that, for any $t\in\mathbb{Z}_{>0}$, the attention block maps $K_{0}^{t}$ into
$K_{1}^{t}$.

Note that we _cannot_ use Thm. 5.7 here because the attention block defines a
different function on $\mathbb{R}^{t\times d}\to\mathbb{R}^{t\times d}$ for
each $t$, and Thm. 5.7 only implies that there exists a separate _length-
dependent_ output compact set $K_{t}\subset\mathbb{R}^{t\times d}$ for each
$t$, which is different from this lemma’s statement.

The feedforward function is a continuous function on
$\mathbb{R}^{d}\to\mathbb{R}^{d}$, and therefore, by Thm. 5.7, maps its input
compact set $K_{1}$ to an output compact set, which we call $K_{2}$.

Finally, residual connections and layer norms are also continuous functions
acting on each of the input vectors, and hence by the same reasoning would
also preserve compactness.

Now we can use induction and show that there exist compact sets
$K_{3},K_{4},\dots,K_{2n-1},K_{2n}$ where $K_{2n}$ contains the output set of
the final layer. Set $K^{\prime}=K_{2n}$ and we have proven the statement. ∎

See 5.9

###### Proof.

Given the Transformer, there exists a fixed compact set $K$ that will contain
all inputs $\bm{v}_{i}\in\mathbb{R}^{d}$ to the first layer. This is true
because each $\bm{v}_{i}$ is the sum of a word embedding, which falls in a
finite set since $\overline{\Sigma}$ is finite, and a position embedding,
which lies in the compact set $[-1,1]^{d}$. Hence, by Lemma 5.8, there exists
a fixed compact set $K^{\prime}$ that contains all output embedding vectors
(regardless of how long the sequence is).

The final output probability is given by a multiplication with the word
embedding matrix followed by the softmax function as in Eq. 25. This process
amounts to composing two continuous functions. In particular, we can extract
the eos probability as a continuous $\mathbb{R}$-valued function
$g_{\textsc{eos}}:K^{\prime}\to(0,1)$ (neither 0 or 1 is in the range of the
softmax function). By continuity of $g_{\textsc{eos}}$ and Thm. 5.7,
$K^{\prime\prime}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}g_{\textsc{eos}}(K^{\prime})\subseteq(0,1)$
is compact. Since $K^{\prime\prime}$ is compact, and hence closed, $\inf
K^{\prime\prime}\in K^{\prime\prime}$. Thus $\inf K^{\prime\prime}\in(0,1)$
and in particular $\inf K^{\prime\prime}>0$. Therefore, taking $\epsilon=\inf
K^{\prime\prime}$, we have shown that the eos probability of a Transformer is
bounded below by some $\epsilon>0$ (regardless of the length of the sequence).

Hence, by Prop. 4.3, any Transformer ASM is tight and thus defines a language
model. ∎

###  E.3 Proofs for RNN Result (§ 5.3)

See 5.10

###### Proof.

Let $X_{t}(\bm{\omega})$ be the random variable that is equal to the $t$th
token in an outcome $\bm{\omega}\in\Omega$. Also let $\bm{h}_{\bm{x}}$ be the
hidden representation of the RNN after processing some finite list of tokens
$\bm{x}\in\Sigma^{\ast}$. Further, let $\bm{u}_{x}\in\mathbb{R}^{d}$ be the
output embedding of $x\in\overline{\Sigma}$, Then for any $t\in\mathbb{N}$ and
any $\bm{x}\in\Sigma^{t}$, we have:

$\displaystyle\mathbb{P}(X_{t+1}=\textsc{eos}\mid X_{\leq t}=\bm{x})$
$\displaystyle=\frac{\exp\bm{u}_{\textsc{eos}}^{\top}\bm{h}_{\bm{x}}}{\sum_{y\in\overline{\Sigma}}\exp\bm{u}_{y}^{\top}\bm{h}_{\bm{x}}}$
(63a)
$\displaystyle=\frac{1}{{\sum_{y\in\overline{\Sigma}}\exp\bm{u}_{y}^{\top}\bm{h}_{\bm{x}}}\,/\,{\exp\bm{u}_{\textsc{eos}}^{\top}\bm{h}_{\bm{x}}}}$
(63b)
$\displaystyle=\frac{1}{1+\sum_{y\in\Sigma}\exp(\bm{u}_{y}-\bm{u}_{\textsc{eos}})^{\top}\bm{h}_{\bm{x}}}$
(63c)
$\displaystyle\geq\frac{1}{1+\sum_{y\in\Sigma}\exp\left(\|\bm{u}_{y}-\bm{u}_{\textsc{eos}}\|_{2}\|\bm{h}_{\bm{x}}\|_{2}\right)}$
(Cauchy–Schwarz) (63d)
$\displaystyle\geq\frac{1}{1+\sum_{y\in\Sigma}\exp(k\|\bm{h}_{\bm{x}}\|_{2})}$
(63e) $\displaystyle=\frac{1}{1+|\Sigma|\exp(k\,\|\bm{h}_{\bm{x}}\|_{2})}$
(63f)

Now define
$\|\widehat{\bm{h}}_{t}\|_{2}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sup_{\bm{x}\in\Sigma^{t}}\|\bm{h}_{\bm{x}}\|_{2}$.
We then have that $\forall t\in\mathbb{N}$ and $\forall\bm{x}\in\Sigma^{t}$:

$\displaystyle\mathbb{P}(X_{t+1}=\textsc{eos}\mid X_{\leq
t}=\bm{x})\geq\frac{1}{1+|\Sigma|\exp(k\|\widehat{\bm{h}}_{t}\|_{2})}$ (64)

Now, by Prop. 4.3, we have that if
$\sum_{t=0}^{\infty}\frac{1}{1+|\Sigma|\exp(k\,\|\widehat{\bm{h}}_{t}\|_{2})}$
diverges, then the language model is tight. We will show that this condition
holds if $\exists N\in\mathbb{N}$ such that $\forall t\geq N$,
$k\|\widehat{\bm{h}}_{t}\|_{2}\leq\log t$.

First, note that
$\lim_{t\to\infty}\frac{1}{t}\frac{1+|\Sigma|t}{1}=\lim_{t\to\infty}\frac{1}{t}+|\Sigma|=|\Sigma|\in(0,\infty)$.
Hence, by the limit comparison test, since $\sum_{t=1}^{\infty}\frac{1}{t}$
diverges, this means $\sum_{t=1}^{\infty}\frac{1}{1+|\Sigma|t}$ must also
diverge.

Now, suppose there exists $N$ such that that
$k\,\|\widehat{\bm{h}}_{t}\|_{2}\leq\log t$ for all $t\geq N$. This implies
that for $t\geq N$ we have
$\frac{1}{1+|\Sigma|\exp(k\|\widehat{\bm{h}}_{t}\|_{2})}\geq\frac{1}{1+|\Sigma|t}$,
which combined with the above and the comparison test, implies that
$\sum_{t=N}^{\infty}\frac{1}{1+|\Sigma|\exp(k\|\widehat{\bm{h}}_{t}\|_{2})}$
diverges. This in turn means that
$\sum_{t=0}^{\infty}\frac{1}{1+|\Sigma|\exp(k\|\widehat{\bm{h}}_{t}\|_{2})}$
diverges.

Hence, if $k\,\|\widehat{\bm{h}}_{t}\|_{2}\leq\log t$ for all sufficiently
large $t$ (that is, for all $t\geq N$), then the RNN ASM is tight and thus
defines a language model.

∎