1 Introduction
Let
$\alpha = x_1 x_2 \cdots $
be an infinite sequence over a finite alphabet
$\Sigma $
. A string
$w \in \Sigma ^*$
is said to occur in
$\alpha $
with limiting frequency f if
$\lim _{N \rightarrow \infty } ({\#_w(x_1 \cdots x_N)}/{N}) = f$
, where
$\#_w(x_1 \cdots x_N)$
is the number of times that w occurs as a contiguous subsequence in
$x_1 \cdots x_N$
. Here,
$\alpha $
is said to be normal if every finite string of length n over
$\Sigma $
occurs with limiting frequency
$\vert \Sigma \vert ^{-n}$
in
$\alpha $
[Reference Borel11]. By standard results, the fractional part of the base-b expansion of almost all real numbers is a normal sequence for
$b \geq 2$
, so for base
$10$
, almost all real numbers have the digit ‘0’ occurring 1-in-10 times in all sufficiently long finite prefixes of their digit expansion, have ‘11’ occurring 1-in-100 times, ‘110’ occurring 1-in-1000 times, and so on. Concrete examples of normal sequences include Champernowne’s sequence
$1234567891011\cdots $
[Reference Champernowne17], the Copeland–Erdös sequence
$235711131719\cdots $
consisting of concatenating the prime numbers [Reference Copeland and Erdös21], and for any polynomial f with positive integer coefficients the sequence
$f(1)f(2)f(3) \cdots $
[Reference Davenport and Erdös22].
A finite-state selector is a deterministic finite automaton (DFA) that selects those symbols
$x_m$
from
$\alpha $
such that
$x_1 \cdots x_{m-1}$
is accepted by the DFA. The sequence of selected symbols may thus be finite or infinite. Agafonov’s theorem states that a sequence
$\alpha $
is normal if and only if any DFA that selects an infinite sequence from
$\alpha $
, selects a normal sequence. Colloquially, Agafonov’s theorem can be stated as: ‘any constant-space algorithm must preserve normality’.
The purpose of this paper is twofold: (i) we study whether analogues of Agafonov’s theorem hold if the distribution of finite strings is different from equidistribution, that is, whether distributions where finite strings s are allowed to occur with frequency distinct from
$\vert \Sigma \vert ^{-\vert w \vert }$
; and (ii) we study extensions of Agafonov’s theorem to infinite alphabets (which in the traditional setup in Agafonov’s theorem is meaningless as there is no equidistributed probability distribution on a countably infinite set).
As an example, consider the (non-normal) sequence
$\alpha = 010101\cdots $
. Clearly, every finite bit string occurs in
$\alpha $
with some well-defined frequency (the simplest way to see this is that for each
$n> 0$
, there are exactly two distinct substrings of length n in
$\alpha $
: one starting with
$0$
and one starting with
$1$
), and the frequencies thus induce a probability distribution on
$\{0,1\}^n$
for each n. In particular,
$0$
and
$1$
each occur with limiting frequency
$1/2$
, but any DFA that selects symbols at even positions will select the sequence
$111\cdots $
, and thus the probability distribution on
$\{0,1\}$
is not preserved, showing that Agafonov’s theorem in general fails to hold.
The motivation for studying infinite alphabets is that the study of normality is closely tied to the study of symbolic dynamics and (information-theoretic) coding theory [Reference Blanchard8, Reference Blanchard, Dumont and Thomas9, Reference Lind and Marcus30, Reference Madritsch31], and that both areas have witnessed recent advances using infinite alphabets [Reference Bontemps, Boucheron and Gassiat10, Reference Boucheron, Garivier and Gassiat12, Reference Hosseini and Santhanam26, Reference Madritsch and Mance33, Reference Silva and Piantanida49]; in particular, the techniques of Madritsch and Mance [Reference Madritsch and Mance33] have allowed construction of Champernowne-like sequences for various distributions over infinite alphabets.
1.1 Contribution
The formal statement of the main theorem can be found in Theorem 3.1 below. In plain language, we prove the following.
Let
$\Sigma $
be a non-empty finite or countably infinite alphabet, and let
$\mu : \Sigma ^* \longrightarrow [0,1]$
be a probability map (that is, for all
$n \geq 0$
,
$1 = \sum _{w \in \Sigma ^n} \mu (w)$
) such that there exists at least one
$\alpha \in \Sigma ^\omega $
that is
$\mu $
-distributed. Then, the following are equivalent.
-
(1)
$\mu $
is induced by a positive Bernoulli probability distribution p on
$\Sigma $
, that is, for every
$a_1,\ldots ,a_n \in \Sigma $
,
$\mu (a_1 \cdots a_n) = \prod _{i=1}^n p(a)$
, and for every
$a \in \Sigma $
,
$p(a)> 0$
. -
(2) For every DFA A over
$\Sigma $
and every
$\mu $
-distributed sequence
$\alpha \in \Sigma ^\omega $
, if A selects an infinite sequence from
$\alpha $
, then the selected sequence is
$\mu $
-distributed.
The above result completely characterizes the probability maps preserved by selection by DFAs, both for finite and infinite alphabets, and Agafonov’s theorem follows immediately as a corollary. We briefly review the roadmap and techniques used for the proof of the main result in §1.3.
As the study of distributions associated to limiting frequencies of finite strings in (right-)infinite strings is cryptomorphic to the study of shift-invariant probability measures on the shift space
$(\Sigma ^\omega ,s)$
equipped with the
$\sigma $
-algebra induced by the basis of cylinder sets on
$\Sigma $
, we obtain a complete characterization of the shift-invariant probability measures
$\nu $
for which any finite-state selector preserves genericity for
$\nu $
, see §6.
1.2 Related work
Agafonov’s theorem [Reference Агафонов57] was one of the end results of multiple efforts grappling with the two notions of: (i) kollektiv—roughly,
$\alpha \in \{0,1\}^\omega $
is a kollektiv with respect to a set
$\mathcal {S}$
of selection strategies if the limiting frequency of
$1$
is unchanged after applying any strategy in
$\mathcal {S}$
to
$\alpha $
(we note that the exact definition of kollektiv differs subtly across different authors, compare e.g., [Reference Church18, Reference Postnikova40, Reference Von Mises54]; the original notion of kollektiv introduced by von Mises [Reference Von Mises54] had no constraints on the set
$\mathcal {S}$
, but this turned out to be essentially fruitless [Reference Copeland20, Reference Kamke28, Reference Reichenbach41, Reference Tornier50]); and (ii) admissible sequence and its relation to the notion of normal sequence [Reference Copeland19, Reference Reichenbach41, Reference Reichenbach42, Reference Постников59, Reference Постников and Пятещкий60]. Agafonov’s theorem itself had a virtually unknown precursor in a beautiful result by Postnikova [Reference Postnikova40] that showed, with the terminology of the present paper, that
$\alpha \in \{0,1\}^\omega $
is normal if and only if the distribution of 1s is preserved by selection strategies depending only on a finite word (see Definition 2.5 for the formal definition of Postnikova strategies).
Both Postnikova [Reference Postnikova40] and Agafonov [Reference Агафонов58] considered selection functions on sequences in
$\{0,1\}^\omega $
, where the limiting distribution of
$1$
was
$0 < p < 1$
(that is, considered a Bernoulli distribution on
$\{0,1\}$
), but considering Bernoulli distributions instead of the special case of equidistributions seems to have disappeared almost completely from all later work. One possible reason for this is that only the short version (without proofs or explanation of techniques) of Agafonov’s result [Reference Агафонов57] appeared in English as [Reference Agafonov1]; in contrast, the original longer paper in Russian [Reference Агафонов58] was published in a more obscure journal and was never translated. We have provided a (very) embellished account of the arguments in [Reference Агафонов58] on the preprint server arXiv (https://arxiv.org/abs/2007.03249), where we expand Agafonov’s terse use of existing results of the time in much more detail, including using more basic arguments with modern methods (e.g., using concentration bounds directly instead of appealing to the law of large numbers) and add further embellishments to Agafonov’s original arguments. Many of the results in the present paper exist due to insights obtained due to this embellishment, rather than the original proof itself.
For equidistribution, the earliest extension to arbitrary alphabets seems to be by Broglio and Liardet [Reference Broglio and Liardet13], and a number of authors have since re-proved Agafonov’s theorem in the special case of equidistribution using a variety of methods; for example, using predictors defined from finite automata (for
$\Sigma = \{0,1\}$
) [Reference O’Connor38], using compressibility arguments [Reference Becher, Carton and Heiber5, Reference Becher and Heiber6, Reference Shen, Klasing and Zeitoun46], and a combination of automata-theoretic and probabilistic methods similar to Agafonov’s original reasoning [Reference Carton14].
Agafonov’s theorem itself has been generalized to treat selectors that are not necessarily (induced by prefix selection by) finite automata [Reference Airey and Mance2, Reference Becher, Carton and Heiber5, Reference Carton and Vandehey15, Reference Vandehey53], and some generalizations consider selectors based on relaxed finiteness criteria of the syntactic monoid of a language selecting prefixes of infinite sequences [Reference Kamae and Weiss27, Reference Tornier50]; conversely, results by Merkle and Reimann show that adding just slight computational power to the selection strategies beyond finite automata—e.g., using a Pushdown automaton with unary stack alphabet instead of a DFA renders Agafonov’s theorem invalid [Reference Merkle and Reimann35]. (In fact, one of the strategies considered by Merkle and Riemann, which consists in computing the language
$\{ww^{\mathrm {R}}\mid w\in \Sigma ^*\}$
, where
$w^{\mathrm {R}}$
is the reverse of w, can be computed by an arguably less expressive model of computation, namely two-way automata with two heads [Reference Holzer, Kutrib and Malcher25].) Similarly, selection by finite automata has been extended, and analogues for Agafonov’s theorem been proved, in other settings than selection from elements of the set
$\Sigma ^\omega $
, e.g., for shifts of finite type [Reference Carton14]. All of these results only consider normality rather than more general classes of distributions on finite strings.
Conversely, construction of normal sequences (as opposed to selecting normal sequences from other normal ones) has been investigated thoroughly for more than a hundred years [Reference Champernowne17, Reference Mance34, Reference Nakai and Shiokawa36, Reference Pollack and Vandehey39, Reference Sierpinski48, Reference Vandehey51], including explicit construction of real numbers with normal expansion for any integer base
$b \geq 2$
[Reference Aistleitner, Becher, Scheerer and Slaman4, Reference Levin29, Reference Scheerer43] and real numbers with normal expansion in non-integer bases [Reference Madritsch, Scheerer and Tichy32, Reference Vandehey52]. Among this work, the result of most use to the present paper is the construction by Madritsch and Mance of generic sequences for any shift-invariant probability measure
$\mu $
[Reference Madritsch and Mance33]—these are essentially sequences that are
$\mu $
-distributed using the terminology of the present paper (see Definition 2.4).
In very recent work, Carton [Reference Carton14] proves that, for any Markov measure
$\mu $
on
$\Sigma ^\omega $
induced by a pair
$(P,\pi )$
of a stochastic
$\vert \Sigma \vert \times \vert \Sigma \vert $
matrix and a stationary distribution
$\pi $
for P, any sequence selected from a
$\mu $
-distributed sequence by a finite-state selector from a particular subset of
$\mu $
-compatible selectors will be
$\mu $
-distributed. Roughly, a finite-state selector is compatible if it can only read consecutive symbols of
$\Sigma $
with non-zero transition probability in P and every state has only incoming transitions of at most one symbol from
$\Sigma $
. In contrast, we consider the full set of finite-state selectors. Moreover, Carton’s results are restricted to the case of finite alphabets.
1.3 Overview of techniques and the proof of the main theorem
The main result has two directions: (i) proving that if
$\mu $
-distributedness is preserved by selection by any DFA, then
$\mu $
is necessarily induced by a Bernoulli distribution; and (ii) any
$\mu $
induced by a Bernoulli distribution is preserved across selection by any DFA.
For direction (i), we prove the more general result that if
$\mu $
is not induced by a Bernoulli distribution on
$\Sigma $
, selection by a particular Postnikova strategy (roughly, a Postnikova strategy selects an element of the sequence if and only if it follows a fixed finite word) will select a non-
$\mu $
-distributed infinite sequence from a—bespoke—
$\mu $
-distributed sequence. The Postnikova strategy contains prefixes in the form
$u\cdot w \in \Sigma ^*$
for a fixed w chosen such that
$w \cdot a \in \Sigma ^{\vert w \vert +1}$
is a minimal witness string such that
$\mu (w \cdot a) \neq \mu (w) \cdot \mu (a)$
. Using basic constructions, we can then prove that the Postnikova strategy can be implemented by a DFA that simulates a sliding fixed-width window.
For direction (ii), most of the modern methods of proving Agafonov’s theorem (e.g., [Reference Becher, Carton and Heiber5, Reference Becher and Heiber6, Reference Shen, Klasing and Zeitoun46]) are not immediately adaptable because they use methods that are particular to equidistributions on finite alphabets (e.g., lossless finite-state compressors [Reference Becher and Heiber6] or automatic Kolmogorov complexity [Reference Shen, Klasing and Zeitoun46])—and we consider both Bernoulli distributions and infinite alphabets. Instead, we work along the general lines of Agafonov’s original proof [Reference Агафонов57] that more heavily uses probabilistic reasoning.
The key insights in Agafonov’s original proof was: (i) that any strongly connected finite automaton (containing at least one accepting state) applied to a normal sequence must select (always, not just with probability
$1$
) more than a constant fraction of elements from any sufficiently long finite substring of its input; and (ii) that selecting more than a constant fraction of sufficiently long substrings entails that each element of
$ \Sigma $
must be selected with approximately equal probability, by the law of large numbers. In Agafonov’s original approach (for
$\Sigma = \{0,1\}$
), an appeal to the strong law of large numbers was used in conjunction with the product measure on the product topology on
$\{0,1\}^\omega $
, thus required reasoning about cylinder sets centered on sets A of finite strings; and to avoid ‘double-counting’ the probabilities, these sets had to be prefix-free. We avoid this difficulty by using concentration bounds to tally the occurrences of elements
$a \in \Sigma $
in block decompositions of finite prefixes of
$\alpha $
.
The proof that any DFA selects a
$\mu $
-distributed infinite sequence from a
$\mu $
-distributed infinite sequence then follows by observing that: (i) any run of a DFA on an infinite sequence eventually reaches a strongly connected component C of the DFA that is recurrent (that is, the run can never exit C); and (ii) that any such component induces an irreducible Markov chain, whence we can apply the ergodic theorem for Markov chains to conclude that accepting states are reached infinitely often and with appropriate frequency.
The extension to infinite alphabets is surprisingly straightforward in most proofs: essentially, instead of using combinatorial estimates for finite sets, we have to ensure that series taken over infinite alphabets converge properly, but almost all instances involve series that: (i) have non-negative elements; and (ii) are bounded above, whence the usual reasoning about absolutely convergent series can be employed. Similarly, the classic results for finite automata that we use need to be re-stated and re-proved in the case of infinite alphabets, but this in general turns out to be doable without too much leg-work (e.g., Lemma A.1). One caveat is that several important ancillary results have standard proofs that use combinatorial arguments on finite sets and we thus need to provide alternative proofs using different methods.
2 Preliminaries
Definition 2.1. We assume a non-empty, possibly (countably) infinite, alphabet
$\Sigma $
and denote by
$\unicode{x3bb} $
the empty string; the sets of finite and right-infinite sequences of elements of
$\Sigma $
are denoted by
$\Sigma ^*$
and
$\Sigma ^\omega $
, respectively. We denote by
$\Sigma ^+$
the set of finite non-empty words, that is,
$\Sigma ^+=\Sigma ^*\setminus \{\unicode{x3bb} \}$
. Elements of
$\Sigma ^*$
are ranged over by
${v}, {w},\ldots $
and elements of
$\Sigma ^\omega $
by
$\alpha , \beta , \ldots $
. If
$\alpha = a_1 a_2 \cdots \in \Sigma ^\omega $
and N is a positive integer, we denote by
$\alpha \vert _{\leq N}$
the finite string
$a_1 a_2 \cdots a_N$
.
Given
$v \in \Sigma ^*$
and
$u \in \Sigma ^* \cup \Sigma ^\omega $
, we write
$v\cdot u$
for the element of
$\Sigma ^* \cup \Sigma ^\omega $
obtained by concatenation. For words
$v \in \Sigma ^*$
and
$w \in \Sigma ^* \cup \Sigma ^\omega $
, v is said to be a prefix of w, written
$v \preceq w$
, if there exists
$u \in \Sigma ^* \cup \Sigma ^\omega $
such that
$w = v\cdot u$
. If
$v \preceq w$
and
$v \neq w$
, v is said to be a proper prefix of w, written
$v \prec w$
. For any
${w} \in \Sigma ^*$
, the cylinder set of
${w}$
, denoted
$[{{w}}]$
, is the subset of
$\Sigma ^\omega $
defined by
$[{{w}}] = \{\alpha \in \Sigma ^\omega : \alpha = w \cdot \beta , \beta \in \Sigma ^\omega \}$
, that is, the set of right-infinite sequences that have
${w}$
as prefix.
Definition 2.2. Let
$\Sigma $
be a non-empty, possibly (countably) infinite, alphabet. A probability map (over
$\Sigma $
) is a map
$\mu : \Sigma ^+ \longrightarrow [0,1]$
such that, for all positive integers n, the series
$$ \begin{align*} \sum_{a_1 \cdots a_n \in \Sigma^n} \mu(a_1 \cdots a_n) \end{align*} $$
is convergent with limit
$1$
. Note that convergence implies absolute convergence here.
A probability map
$\mu $
is said to be:
-
• induced by a Bernoulli distribution
$p : \Sigma \longrightarrow [0,1]$
if, for all positive integers n, and all
$a_1,\ldots ,a_n \in \Sigma $
,
$\mu (a_1 \cdots a_n) = \prod _{i=1}^n \mu (a_i) = \prod _{i=1}^n p(a_i)$
; -
• invariant if, for all
${w} \in \Sigma ^*$
, the series
$\sum _{a \in \Sigma } \mu ({w}\cdot a)$
and
$\sum _{a \in \Sigma } \mu (a \cdot {w})$
are convergent with limit
$\mu ({w})$
; -
• (when
$\Sigma $
is finite) equidistributed if, for any
${w} \in \Sigma ^{n}$
,
$\mu ({w}) = \vert \Sigma \vert ^{-n}$
.
Observe that an equidistributed
$\mu $
is also Bernoulli. For alphabets
$\vert \Sigma \vert> 1$
, any map
$p : \Sigma \longrightarrow [0,1]$
such that the series
$\sum _{a \in \Sigma } p(a)$
converges to
$1$
induces a probability map
$\mu _p$
by setting
$\mu _p(a_1 \cdots a_n) = \prod _{j=1}^n p(a_j)$
. For finite alphabets
$\Sigma $
, this map is equidistributed if and only if
$p(a) = \vert \Sigma \vert ^{-1}$
for every
$a \in \Sigma $
.
The expression ‘induced by a Bernoulli distribution’ is justified by the fact that Bernoulli probability maps correspond directly to the measure of cylinders in Bernoulli shifts [Reference Shields47]. (In the literature on normal numbers, the word Bernoulli is sometimes used slightly differently, for example, Schnorr and Stimm [Reference Schnorr and Stimm44] use the term ‘Bernoulli sequence’ for sequences that are equidistributed in our terminology. We also note that
$\mu $
-distributed sequences (defined later) with respect to Bernoulli distributions were first introduced by Postnikov and I. I. Piatetski-Shapiro under the name ‘Bernoulli normal sequences’ [Reference Постников and Пятещкий60].)
Proposition 2.1. A probability map
$\mu $
induced by a Bernoulli distribution is invariant.
Proof. For any
$w \in \Sigma ^*$
,
$\sum _{a\in \Sigma } \mu (a w) = \sum _{a \in \Sigma } \mu (a)\mu (w) = \sum _{a \in \Sigma } \mu (w)\mu (a) = \sum _{a \in \Sigma } \mu (wa)$
. And
$\sum _{a \in \Sigma } \mu (w)\mu (a) = \mu (w)\sum _{a \in \Sigma } \mu (a) = \mu (w)$
.
We shall need probability maps to act as ‘measures’ on (possibly infinite) sets of finite strings.
Definition 2.3. Let
$\Sigma $
be a non-empty alphabet, let
$W \subseteq \Sigma ^*$
, and let
$\mu $
be a probability map over
$\Sigma $
. If
$W = \emptyset $
, we define
$\mu (W) = 0$
. If
$\sum _{w \in W} \mu (w)$
converges, we define
$\mu (W) = \sum _{w \in W} \mu (w)$
.
Observe that as
$\mu (w) \geq 0$
for all
$w \in \Sigma ^*$
, if
$\sum _{w \in W} \mu (w)$
converges, it is absolutely convergent (hence, we do not need to specify an ordering of W).
We are interested in the probability maps whose values can be realized as the limiting frequencies of finite words in right-infinite sequences over
$\Sigma $
.
Definition 2.4. Let
${v} = v_1 \cdots v_N$
and
${w} = w_1 \cdots w_n$
be finite words over
$\Sigma $
. We denote by
$\#_{{w}}({v})$
the number of occurrences of
${w}$
in
${v}$
, that is, the quantity
$$ \begin{align*} \vert \{j\leq N+1-n : v_j v_{j+1} \cdots v_{j+n-1} = w_1 w_2 \cdots w_n \}\vert \end{align*} $$
Let
$\mu $
be a probability map over
$\Sigma $
and let
$\alpha $
be a right-infinite sequence over
$\Sigma $
. If the limit
$$ \begin{align*} \lim_{N \rightarrow \infty} \frac{\#_{{w}}(\alpha\vert_{\leq_N})}{N} \end{align*} $$
exists and is equal to some real number f, we say that
${w}$
occurs in
$\alpha $
with limiting frequency f. If every
${w} \in \Sigma ^+$
occurs in
$\alpha $
with limiting frequency
$\mu ({w})$
, we say that
$\alpha $
is
$\mu $
-distributed.
Proposition 2.2. Let
$\mu $
be a probability map over
$\Sigma $
. If there exists a
$\mu $
-distributed sequence, then
$\mu $
is invariant.
Proof. Let
$\mu $
be a probability map over
$\Sigma $
and
$\alpha =a_1 a_2\dots $
a
$\mu $
-distributed sequence. We consider
$w=w_1 w_2\dots w_k \in \Sigma ^k$
and note that for all
$N> 0$
,
$$ \begin{align*} \bigg\vert\kern-3pt \sum_{a \in \Sigma} \#_{aw}(\alpha\vert_{\leq N})- \#_{w}(\alpha\vert_{\leq N}) \bigg\vert \leq 1. \end{align*} $$
Indeed, every occurrence of w as
$a_i a_{i+1} \dots a_{i+k}$
such that
$i>1$
is also an occurrence of
$b\cdot w$
for a (unique)
$b\in \Sigma $
, so the expressions
$\#_{w}(\alpha \vert _{\leq N})$
and
$\sum _{a \in \Sigma } \#_{aw}(\alpha \vert _{\leq N})$
are equal if and only if
$a_1 a_{2} \dots a_{k}\neq w$
and their difference is equal to
$1$
otherwise.
Thus,
$$ \begin{align*} \bigg\vert \frac{\sum_{a \in \Sigma} \#_{aw}(\alpha\vert_{\leq N})}{N}- \frac{\#_{w}(\alpha\vert_{\leq N})}{N}\bigg\vert \leq \frac{1}{N}. \end{align*} $$
We therefore obtain that
$$ \begin{align*} \bigg\vert \frac{\sum_{a \in \Sigma} \#_{aw}(\alpha\vert_{\leq N})}{N} - \mu(w) \bigg\vert \leq \bigg\vert \frac{\sum_{a \in \Sigma} \#_{aw}(\alpha\vert_{\leq N})}{N} - \frac{\#_{w}(\alpha\vert_{\leq N})}{N} \bigg\vert + \bigg\vert \frac{\#_{w}(\alpha\vert_{\leq N})}{N} - \mu(w) \bigg\vert. \end{align*} $$
Since both expressions on the right converge to
$0$
, the left-hand side converges to zero, showing that
$\mu (w)=\lim _{n\rightarrow \infty } ({\sum _{a \in \Sigma } \#_{aw}(\alpha \vert _{\leq n})}/{n})=\sum _{a\in \Sigma } \lim _{n\rightarrow \infty }({\#_{aw}(\alpha \vert _{\leq n})}/{n})=\sum _{a\in \Sigma } \mu (aw)$
.
Similarly, for all
$N>0$
,
$$ \begin{align*} \bigg\vert \kern-3pt\sum_{a \in \Sigma} \#_{wa}(\alpha\vert_{\leq N})-\#_{w}(\alpha\vert_{\leq N})\bigg\vert \leq 1, \end{align*} $$
by a similar argument as the one used above, noting that the number of occurrences is different if and only if
$a_{N-k+1}a_{N-k+2}\cdots a_N= w$
. We then conclude that
$\mu (w)=\sum _{a\in \Sigma } \mu (wa)$
in the same way.
Observe that an infinite sequence
$\alpha $
is normal in the usual sense if and only if it is
$\mu $
-distributed for (the unique) equidistributed probability map
$\mu $
over
$\Sigma $
.
Example 2.3. An example of a probability map that is not Bernoulli, but such that there is at least one
$\mu $
-distributed right-infinite sequence, is the map
$\mu $
over
$\Sigma = \{0,1\}$
defined by
$\mu (w) = 1/2$
if w does not contain any of the strings
$00$
or
$11$
(note that for each positive integer n, there are exactly two such strings of length n, namely
$0101010\cdots $
and
$101010\cdots $
), and
$\mu (w) = 0$
otherwise. Observe that the right-infinite sequence
$010101 \cdots $
is
$\mu $
-distributed.
In contrast to all previous work on Agafonov’s theorem, we allow countably infinite alphabets
$\Sigma $
. Alphabets of larger cardinality do not in general have probability measures realizable by considering limiting frequencies of elements of
$\Sigma ^\omega $
—simply because most elements of
$\Sigma $
cannot occur at all in a single element of
$\Sigma ^\omega $
.
One reason why previous generalizations of Agafonov’s theorem have not considered infinite alphabets is that there can be no equidistribution on a countably infinite set. However, there are Bernoulli measures
$\mu $
on countably infinite alphabets
$\Sigma $
and
$\mu $
-distributed infinite sequences over
$\Sigma $
.
Example 2.4. An example of a countably infinite alphabet with a Bernoulli measure is
$\Sigma = \mathbb {N}$
and
$p(n) = 6/(\pi n)^2$
(note that we have
$\sum _{n \in \Sigma } p(n) = 1$
). In general, any convergent series
$\sum _{n=1}^\infty a_n$
, where every
$a_n$
is non-negative, induces a Bernoulli distribution on
$\mathbb {N}$
by setting
$p(n) = a_n/ \sum _{n=1}^\infty a_n$
. Each such Bernoulli distribution p induces an invariant probability map
$\mu _p$
, and by a result of Madritsch and Mance [Reference Madritsch and Mance33], there exists a
$\mu _p$
-distributed sequence.
Remark 2.5. As we consider possibly infinite alphabets, we often have to consider infinite series instead of finite sums in the proofs. In most cases, these series will have elements that are known to be non-negative and the sum of all partial sums will be bounded above, whence the series will be absolutely convergent and the order of summation can thus be changed freely. A trivial example of use is to consider some
$B \subseteq \Sigma $
and note that
$\sum _{a \in B} p(a) = 1 - \sum _{a \in \Sigma \setminus B} p(a)$
(as
$\sum _{a \in B} p(a) \leq 1$
,
$\sum _{a \in \Sigma \setminus B} p(a) \leq 1$
, and
$p(a) \geq 0$
the two series are absolutely convergent, and
$\sum _{a \in B} p(a) + \sum _{a \in \Sigma \setminus B} = \sum _{a \in \Sigma } p(a) = 1$
).
2.1 Strategies
Definition 2.5. Let
$\Sigma $
be an alphabet. A strategy S over
$\Sigma $
is a subset
$S\subseteq \Sigma ^{*}$
.
Given a strategy S and
$\alpha \in \Sigma ^\omega $
, we define the sequence selected by S, denoted
$S(\alpha )$
, as follows: if
$i_{1},i_{2},\dots ,i_{k},\dots $
is the (increasing) sequence of indices
$i_j$
such that
$\alpha \vert _ {< i_j} \in S$
, then
$S(\alpha )_{j}= \alpha _{i_{j}}$
. When
$w \in \Sigma ^*$
is a finite word, we define
$S(w)$
mutatis mutandis.
A strategy S is a Postnikova strategy if there is
$w \in \Sigma ^*$
such that
$S = \Sigma ^* w$
.
Thus,
$S(\alpha )$
is simply the subsequence of symbols from
$\alpha $
that are ‘picked out’ by applying S to prefixes of
$\alpha $
. Note also that if
${w} \in S$
, then in any word on the form
${w} \cdot b \cdot {v}$
, S must pick b. Thus, S cannot be made to, for instance, only pick out a single symbol from
$\Sigma $
—it must select ‘the next symbol’ after any
${w} \in S$
. This precludes, for example, constant-memory strategies from selecting only
$0$
s from a normal binary sequence.
Our primary object of study is the case where S is a regular language, described next.
2.2 Finite-state selectors and selection by DFAs
As we treat both finite and (countably) infinite alphabets, we must consider automata over possibly infinite alphabets. Every automaton has a finite number of states as usual, but as the alphabet is infinite and a deterministic automaton has transitions on all symbols from every state, the underlying graph of the automaton will be infinitely branching. To keep notation simple, we refer to a deterministic automaton with a finite number of states as a ‘DFA’ as usual, even if the underlying alphabet is infinite.
Definition 2.6. A finite-state selector over
$\Sigma $
is a DFA
$A = (Q,\delta ,q_s,Q_F)$
, where Q is a finite set of states,
$q_s$
is the unique start state,
$Q_F$
is the set of accepting states, and
$\delta : Q \times \Sigma \longrightarrow Q$
is the transition relation.
A DFA is strongly connected if its underlying directed graph (states are nodes, transitions are edges) is strongly connected.
Denote by
$L(A)$
the language accepted by the automaton. If
$\alpha = a_1 a_2 \cdots $
is a finite or right-infinite sequence over
$\Sigma $
, the subsequence selected by A is the (possibly empty) sequence of letters
$a_n$
such that the prefix
$a_1 \cdots a_{n-1} \in L(A)$
, that is, the automaton when started on the finite word
$a_1 \cdots a_{n-1}$
in state
$q_s$
ends in an accepting state after having read the entire word. The run of A on input
$\alpha $
is the sequence of states visited when A is applied to
$\alpha $
from the starting state. For
$(q,w) = (q,w_1 \cdots w_n) \in Q \times \Sigma ^*$
, we use the notation
$\delta ^*(q,w)$
to denote the state
$\delta (\cdots \delta (\delta (q,w_1),w_2) \cdots w_n)$
, that is, the state reached by starting from q and following the (unique) path induced by w.
Observe that a DFA may select an empty, finite, or infinite sequence when run on a right-infinite word.
Definition 2.7. Let A be a DFA. A strongly connected component C in (the underlying directed graph of) A is said to be recurrent if, for every state p in C and every
$a \in \Sigma $
,
$\delta (p,a)$
is a state in C (that is, once a run of A on some infinite word reaches a state in C, the run cannot leave C).
Definition 2.8. Let
$A = (Q,\Sigma ,\delta ,q_0,Q_F)$
be a connected DFA. For all
$q\in Q$
, we denote by
$A_{q}$
the automaton
$(Q,\Sigma ,\delta ,q,Q_F)$
, that is, where the state q is chosen as the initial state.
Definition 2.9. Let
$A = (Q,\Sigma ,\delta ,q_0,Q_F)$
be a connected DFA and let
$q\in Q$
. Let
$\alpha $
be a right-infinite sequence over
$\Sigma $
. We denote by
$A_{q}[{\alpha }]$
the subsequence
$\bar {\alpha }$
of
$\alpha $
picked out by
$A_{q}$
, that is,
$w_{i}\in \bar {{w}}$
if and only if
$\delta ^*(q,\alpha _{<i})$
is an accepting state.
Let us stress that
$A_{q}[{\alpha }]$
differs in general from
$S(\alpha )$
, where
$S\in \Sigma ^*$
is the strategy defined as the language accepted by A. Indeed, these are equal only when q is chosen to be the initial state of A.
We shall use the following fundamental result in automata theory (the result in [Reference Schnorr and Stimm44] is stated for finite alphabets, but the proof method carries through for infinite alphabets as well. We provide a proof in Appendix A).
Lemma 2.6. [Reference Schnorr and Stimm44, Lemma 2.6]
For every DFA
$A = (Q,\delta ,q_s,Q_F)$
over the (possibly infinite) alphabet
$\Sigma $
, there is a word
$w \in \Sigma ^*$
such that, for every
$q \in Q$
, there is a strongly connected recurrent component C (of the underlying directed graph of A) such that
$\delta ^*(q,w) \in C$
.
Corollary 2.7. Let
$\mu $
be a probability map induced by a positive Bernoulli distribution on
$\Sigma $
, let A be a DFA over
$\Sigma $
, and let
$\alpha \in \Sigma ^\omega $
be
$\mu $
-distributed. Then, the run of A on
$\alpha $
eventually reaches a strongly connected recurrent component of A.
Proof. Let w be the word obtained from Lemma 2.6. As
$\alpha $
is p-distributed, w appears in
$\alpha $
, so write
$\alpha = v w \alpha '$
, and let q be the state of A reached after
$\vert v \vert $
transitions in the run of A on
$\alpha $
. Then, after at most a further
$\vert w \vert $
transitions, the run reaches a state in a strongly connected component of (the underlying directed graph of) A.
Corollary 2.7 ensures that we can assume without loss of generality that the finite-state selectors we treat are strongly connected. Note that the corollary does not imply that the strongly connected recurrent component contains an accepting state (indeed, the automata may have an empty set of accepting states). Thus, some automata do not always select infinite sequences, and additional assumptions are needed if this is desirable (this is discussed in Remark 3.2 below). However, this is not an issue for our main result which states that the output of a selector applied to a normal sequence is again normal as long as it is infinite.
3 Main result
Theorem 3.1. Let
$\Sigma $
be a non-empty (finite or infinite) alphabet and
$\mu $
be a probability map such that there exists at least one
$\alpha \in \Sigma ^\omega $
that is
$\mu $
-distributed. Then, the following statements are equivalent:
-
(1)
$\mu $
is induced by a positive Bernoulli distribution p on
$\Sigma $
, that is, for every
$a_1 \cdots a_n \in \Sigma $
,
$\mu (a_1 \cdots a_n) = \prod _{i=1}^n p(a)$
and
$p(a)> 0$
for all
$a \in \Sigma $
; -
(2) (Postnikova property) for every finite word
$w\in \Sigma ^{\ast }$
and
$\mu $
-distributed sequence
${\alpha \in \Sigma ^\omega }$
, if the sequence selected from
$\alpha $
by the Postnikova strategy
$\mathcal {S}_w=\{ u\in \Sigma ^*\mid \text { there exists } v\textrm { such that }u=v w\}$
is infinite, then it is
$\mu $
-distributed; -
(3) (Agafonov property) for every DFA A over
$\Sigma $
and every
$\mu $
-distributed sequence
$\alpha \in \Sigma ^\omega $
, if the sequence selected from
$\alpha $
by A is infinite, then it is
$\mu $
-distributed.
Proof. For the implication (1)
$\Rightarrow $
(3), Theorem 2.7 yields that any run of a finite-state selector on a
$\mu $
-distributed sequence eventually reaches a strongly connected recurrent component; the restriction of any DFA to the state set of one of its recurrent component is also a DFA, and the result now follows by Theorem 5.9. The implication (3)
$\Rightarrow $
(2) is clear from the definitions since the considered strategies are computed by finite automata (Theorem 4.3). Lastly, Theorems 4.1 and 4.2 prove that (2)
$\Rightarrow $
(1).
Remark 3.2. Theorem 3.1 addresses the case where a DFA or Postnikova strategy selects an infinite sequence from a
$\mu $
-distributed sequence. If one wants to restrict attention to automata that always select an infinite subsequence from any
$\mu $
-distributed sequence, extra conditions sometimes occur in the literature, e.g., that every cycle in the (underlying graph of the) DFA contains an accepting state [Reference Becher and Heiber6] ensuring that an infinite subsequence is selected from any (not just
$\mu $
-distributed sequence). Another condition that ensures that an infinite subsequence is selected from any
$\mu $
-distributed sequence is to consider only DFAs such that every strongly connected recurrent component contains at least one accepting state. In this case, Corollary 2.7 ensures that any run on the automaton on a
$\mu $
-distributed sequence will reach a strongly recurrent component, and Lemma 5.4 below then ensures that the DFA accepts an infinite subsequence from
$\alpha $
.
4 Non-preservation of
$\mu $
-distributedness for non-Bernoulli measures
We first prove that if
$\mu $
is a probability map such that any DFA selects a
$\mu $
-distributed right-infinite sequence from any
$\mu $
-distributed right-infinite sequence, then
$\mu $
must be Bernoulli. This is an immediate consequence of a stronger property proved in Lemma 4.1 below.
The idea of the proof is that if
$\mu $
is not Bernoulli, there exists a word
$a_1 \cdots a_k$
such that
$\mu (a_1 \cdots a_{k-1}) = \prod _{j=1}^{k-1} \mu (a_j)$
, but
$\mu (a_1 \cdots a_{k-1} a_k) \neq \mu (a_1 \cdots a_{k-1}) \cdot \mu (a_k)$
. One can then construct a finite-state selector that acts like a ‘sliding window’ of size
$k-1$
, that is, remembers the last
$k-1$
letters scanned and accepts if these are
$a_1 \cdots a_k$
. This selector will select every letter following
$a_1 \cdots a_{k-1}$
; after a prefix of length N of a right-infinite sequence has been scanned, approximately
$N \cdot \mu (a_1 \cdots a_{k-1})$
have been selected and approximately
$N \cdot \mu (a_1 \cdots a_{k-1} a_k)$
of these will be the symbol
$a_k$
. However, then the limiting frequency of
$a_k$
in the sequence selected will be
$\mu (a_1 \cdots a_{k-1} a_k)/\mu (a_1 \cdots a_{k-1}) \neq \mu (a_k)$
and the result follows.
For completeness, we give a fully formal proof after the lemma, but the entirety of the reasoning is essentially as we just described.
Lemma 4.1. Let
$\mu : \Sigma ^* \longrightarrow [0,1]$
be a probability map. If
$\mu $
is not induced by a Bernoulli distribution on
$\Sigma $
, there exists a finite word
$w\in \Sigma ^*$
such that if
$\alpha \in \Sigma ^\omega $
is
$\mu $
-distributed, then the Postnikova strategy
$\mathcal {S}_w=\{ u\in \Sigma ^*\mid \text { there exists } v\textrm { such that } u=vw\}$
selects from
$\alpha $
an infinite sequence
$\beta \in \Sigma ^\omega $
that is not
$\mu $
-distributed.
Proof. If no element of
$\Sigma ^\omega $
is
$\mu $
-distributed, the lemma is vacuously true. Hence, assume that there is at least one
$\alpha \in \Sigma ^\omega $
that is
$\mu $
-distributed. If
$\vert \Sigma \vert = 1$
, then there is exactly one probability map on
$\Sigma ^*$
, namely the one that assigns probability
$1$
to the unique element of
$\Sigma ^k$
for every
$k \geq 0$
, and this probability map is clearly Bernoulli and the lemma is thus vacuously true. Hence, in the remainder of the proof, assume that
$\vert \Sigma \vert \geq 2$
.
Assume that
$\mu $
is not induced by a Bernoulli distribution on
$\Sigma $
. Then, there are k and a word
$a_1\cdots _{k-1} a_k \in \Sigma ^k$
such that
$\mu (a_1 \cdots a_{k-1} a_k) \neq \prod _{j=1}^k \mu (a_j)$
. Observe that
$k = 1$
is impossible and thus we must have
$k \geq 2$
. Assume without loss of generality that k is minimal among such k, and hence that
$\mu (a_1 \cdots a_{k-1}) = \prod _{j=1}^{k-1} \mu (a_j)$
, and note that this implies
$\mu (a_1 \cdots a_{k-1} a_k) \neq \mu (a_1 \cdots a_{k-1}) \cdot \mu (a_k)$
.
Assume for contradiction that
$\mu (a_1 \cdots a_{k-1}) = 0$
. Then,
$\mu (a_i) = 0$
for at least one
$a_i$
. We also must have
$\mu (a_1 \cdots a_{k-1} a_k) = 0$
because otherwise, the fact that there is at least one
$\mu $
-distributed right-infinite sequence entails that
$\mu (a_1 \cdots a_{k-1} a_k)> 0$
, which in turn implies that
$\mu (a_i) \geq \mu (a_1 \cdots a_{k-1} a_k)> 0$
for each i. However, this is a contradiction, because then we would have that
$\mu (a_1 \cdots a_{k-1} a_k) = 0 = \prod _{j=1}^k \mu (a_j)$
. Thus,
$\mu (a_1 \cdots a_{k-1})> 0$
.
As
$\mu (a_1 \cdots a_{k-1} a_k) \neq \mu (a_1 \cdots a_{k-1}) \cdot \mu (a_k)$
,
$\mu (a_1 \cdots a_{k-1})> 0$
, and we have
$\mu (a_1 \cdots a_{k-1} a_k) \leq \mu (a_1 \cdots a_{k-1})$
(because
$\mu $
is invariant by Proposition 2.2), there is a real number
$\gamma $
with
$0 < \gamma < 1$
such that:
$$ \begin{align*} \bigg\vert \frac{\mu(a_1 \cdots a_{k-1} a_k)}{ \mu(a_1 \cdots a_{k-1})} - \mu(a_k) \bigg\vert> \gamma. \end{align*} $$
We now consider the Postnikova strategy
$\mathcal {S}_w$
with
$w=a_1 \cdots a_{k-1}$
, that is, the strategy that selects exactly the symbols following the occurrences of
$a_1 \cdots a_{k-1}$
in
$\alpha $
.
Let
$\alpha \in \Sigma ^\omega $
be
$\mu $
-distributed. Then, for every
$\epsilon> 0$
, there is an
$N_\epsilon> 0$
such that for all
$n>N_\epsilon $
, we have
$$ \begin{align*} \bigg\vert\frac{\#_{a_1 \cdots a_{k-1}}(\alpha\vert_{\leq n})}{n}-\mu(a_1 \cdots a_{k-1})\bigg\vert\leq\epsilon \end{align*} $$
and
$$ \begin{align*} \bigg\vert\frac{\#_{a_1 \cdots a_{k-1}a_k}(\alpha\vert_{\leq n})}{n}-\mu(a_1 \cdots a_{k-1}a_k)\bigg\vert\leq\epsilon. \end{align*} $$
Hence,
$$ \begin{align} n \mu(a_1 \cdots a_{k-1}) - n\epsilon \leq \#_{a_1 \cdots a_{k-1}}(\alpha\vert_{\leq n}) \leq n \mu(a_1 \cdots a_{k-1}) + n\epsilon \end{align} $$
and
$$ \begin{align} n \mu(a_1 \cdots a_{k-1} a_k) - n\epsilon \leq \#_{a_1 \cdots a_{k-1} a_k}(\alpha\vert_{\leq n}) \leq n \mu(a_1 \cdots a_{k-1} a_k) + n\epsilon. \end{align} $$
As
$\mu (a_1 \cdots a_{k-1})> 0$
and
$\mathcal {S}_w$
selects the symbol after each occurrence of
$a_{1} \cdots a_{k-1}$
,
$\mathcal {S}_w$
selects an infinite sequence
$\beta $
from
$\alpha $
. Let
$\beta ^{(n)} \in \Sigma ^*$
be the finite sequence selected by
$\mathcal {S}_w$
from
$\alpha \vert _{\leq n}$
. Observe that we have
$\vert \beta ^{(n)} \vert = \#_{a_1 \cdots a_{k-1}}(\alpha \vert _{< n})$
and
$\#_{a_k}(\beta ^{(n)}) = \#_{a_1 \cdots a_{k-1}a_k}(\alpha \vert _{< n})$
. The fraction of occurrences
$\#_{a_k}(\beta ^{(n)})/\vert \beta ^{(n)} \vert $
of
$a_k$
in
$\beta ^{(n)}$
thus satisfies
$$ \begin{align*} \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} = \frac{ \#_{a_1 \cdots a_{k-1}a_k}(\alpha\vert_{< n})}{ \#_{a_1 \cdots a_{k-1}}(\alpha\vert_{< n})} = \frac{\#_{a_1 \cdots a_{k-1}a_k}(\alpha\vert_{< n})}{n} \cdot \frac{n}{ \#_{a_1 \cdots a_{k-1}}(\alpha\vert_{< n})} \end{align*} $$
and hence, by equations (4.1) and (4.2), for all
$n> N$
,
$$ \begin{align} \frac{\mu(a_1 \cdots a_{k-1} a_k) - \epsilon}{\mu(a_1 \cdots a_{k-1}) + \epsilon} \leq \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} \leq \frac{\mu(a_1 \cdots a_{k-1} a_k) + \epsilon}{\mu(a_1 \cdots a_{k-1}) - \epsilon}. \end{align} $$
Consider an arbitrary
$\delta $
with
$0 < \delta < \gamma /2$
. By equation (4.3), for all sufficiently small
$\epsilon $
, we have
$$ \begin{align*} \bigg\vert \frac{\mu(a_1 \cdots a_{k-1}a_k)}{\mu(a_1 \cdots a_{k-1})} - \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} \bigg\vert < \delta \end{align*} $$
and thus for all
$n> N_\epsilon $
,
$$ \begin{align*} \gamma &< \bigg\vert \frac{\mu(a_1 \cdots a_{k-1} a_k)}{\mu(a_1 \cdots a_{k-1})} - \mu(a_k) \bigg\vert\\ &\leq \bigg\vert \frac{\mu(a_1 \cdots a_{k-1} a_k)}{\mu(a_1 \cdots a_{k-1})} - \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} \bigg\vert + \bigg\vert \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} - \mu(a_k) \bigg\vert \\ & < \delta + \bigg\vert \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} - \mu(a_k) \bigg\vert < \frac{\gamma}{2} + \bigg\vert \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} - \mu(a_k) \bigg\vert \end{align*} $$
whence
$$ \begin{align*} \bigg\vert \frac{\#_{a_k}( \beta^{(n)})}{\vert \beta^{(n)} \vert} - \mu(a_k) \bigg\vert> \frac{\gamma}{2} \end{align*} $$
and as the sequence
$(\beta ^{(n)})_{n \in \mathbb {N}}$
consists of prefixes of the sequence
$\mathcal {S}_w[\alpha ]$
selected by
$\mathcal {S}_w$
from
$\alpha $
, and is eventually increasing, the frequency of occurrences of
$a_k$
differs infinitely often from
$\mu (a_k)$
by at least
$\gamma /2$
, so
$\mathcal {S}_w[\alpha ]$
cannot be
$\mu $
-distributed.
Lemma 4.1 shows that if a probability map is not induced by a Bernoulli distribution on
$\Sigma $
, some Postnikova strategy will select a non-
$\mu $
-distributed sequence from any
$\mu $
-distributed sequence. In the case where
$\mu $
is induced by a Bernoulli distribution, but not a positive Bernoulli distribution, we can show the weaker result that there will be a Postnikova strategy that selects a non-
$\mu $
-distributed sequence from some
$\mu $
-distributed sequences (and this is sufficient for our main theorem).
Lemma 4.2. Let
$\mu : \Sigma ^* \longrightarrow [0,1]$
be a probability map induced by a Bernoulli distribution on
$\Sigma $
that is not positive. Then, there exists a finite word
$w\in \Sigma ^*$
and
$\mu $
-distributed
$\alpha \in \Sigma ^\omega$
such that the Postnikova strategy
$\mathcal {S}_w=\{ u\in \Sigma ^*\mid \text { there exists } v\textrm { such that } u=vw\}$
selects from
$\alpha $
an infinite sequence
$\beta \in \Sigma ^\omega $
that is not
$\mu $
-distributed.
Proof. As
$\mu $
is not positive, pick
$b \in \Sigma $
such that
$\mu (b) = 0$
, and let
$\Gamma \subseteq \Sigma $
be a maximal subset such that the restriction of
$\mu $
to
$\Gamma $
is a positive Bernoulli distribution (observe that
$\Gamma $
is non-empty because
$\mu $
is a probability map and
$1 = \sum _{a \in \Sigma } \mu (a)$
thus implies
$\mu (a)> 0$
for some
$a \in \Sigma $
). By [Reference Madritsch and Mance33], there exists a
$\mu $
-distributed infinite sequence
$\beta \in \Gamma ^\omega $
; notice that
$\beta $
can be assumed without loss of generality to not contain any occurrences of b. Let
$\alpha \in \Sigma ^\omega $
be obtained by inserting the string
$bb$
at positions
$2,4,8,16,\ldots $
. Then,
$\alpha $
is
$\mu $
-distributed because: (i) every
$v \in \Gamma ^*$
occurs with the same limiting frequency as in
$\beta $
(the key observation here is that since the ‘bb’s are inserted at exponentially increasing positions, the frequency of occurrence of all other strings is decreased by a very small (and quickly decaying) factor); and (ii) every
$v \in \Sigma ^*$
that contains an element of
$\Sigma \setminus \Gamma $
occurs in
$\alpha $
with limiting frequency
$0$
. Set
$w = b$
; then the Postnikova strategy
$\mathcal {S}_w = \{u \in \Sigma ^* \vert \text { there exists } v \mathrm { such that } u = vw\}$
selects from
$\alpha $
a sequence
$\beta = \mathcal {S}_w[\alpha ]$
such that, for every
$n> 0$
,
$\#_{b}(\beta \vert _{\leq n}) \geq n/2 - 1$
. Thus, the limiting frequency of b in
$\beta $
is not
$0$
, and hence is not
$\mu (b)$
, proving that
$\beta $
is not
$\mu $
-distributed.
Lemma 4.3. Let
$w\in \Sigma ^*$
. The Postnikova strategy
$\{ u\in \Sigma ^*\mid \text { there exists } v\textrm { such that } u=vw\}$
is computable by a strongly connected DFA over
$\Sigma $
.
Proof. Note that the alphabet can possibly be infinite in the following proof. In the trivial case
$\vert \Sigma \vert = 1$
, the desideratum follows since there is only one infinite sequence
$\alpha $
and every Postnikova strategy extracts
$\alpha $
from
$\alpha $
. If
$\vert w \vert = 0$
, the single-state DFA that accepts all input and with transitions on all symbols to the state itself clearly computes the Postnikova strategy. Hence, we may assume in the remainder of the proof that
$\vert \Sigma \vert> 1$
and
$\vert w \vert> 0$
.
Write
$w = w_1,w_2,\dots ,w_m$
, where
$w_1,\ldots , w_m \in \Sigma $
. We construct a finite state selector
$M_w$
with exactly
$m+1$
states which will select a symbol from the input if and only if it is preceded by the word w. Let
$M_w=(\mathbf {m},\delta ,q_s,Q_F)$
be defined as follows:
-
•
$\mathbf {m}=\{0,1,\ldots ,m\}$
; state
$i \in \{0,\ldots ,m\}$
represents the case where the longest prefix of m read from the last i symbols has length i (observe that there may be several shorter prefixes present and that a prefix of w may contain a shorter prefix of w as a suffix); -
•
$q_s = 0$
; -
•
$Q_F = \{m\}$
; -
•
$\delta $
is defined by Observe that the above cases exhaust all possibilities and that
$$ \begin{align*} \delta(i,a) = \begin{cases} i+1 & \textrm{if } i < m \textrm{ and } a = w_{i+1},\\ j & \textrm{if } (i = m \textrm { or } a\neq w_{i+1}) \textrm{ and where } j \textrm{ is the longest prefix of } \\ & w \textrm{ such that } w_{i-j+1} \cdots w_i a = w_1 \cdots w_j. \\ \end{cases} \end{align*} $$
$\delta $
thus is well-defined. Note in particular that
$\delta (i,a)=0$
when there is no j such that
$w_{i-j+1}\cdots w_i a=w_1\cdots w_j$
.
As an example, consider the case where
$\Sigma = \{a,b\}$
, and
$w = aabaabb$
. If
$M_w$
is in state
$6$
(corresponding to the
$6$
most recently seen symbols being
$aabaab$
and
$M_w$
reads the symbol a, then the longest prefix of w most recently read is
$aaba$
, corresponding to the suffix
$aab$
of
$aabaab$
followed by a). Hence,
$M_w$
enters state
$4$
.
Observe that
$M_w$
implements the Postnikova strategy as
$M_w$
accepts if and only if the last sequence of m symbols read is w.
We now prove that the underlying directed graph of
$M_w$
is strongly connected. To prove the claim, observe first that by construction, there is a directed edge from every state
$i \in \{0,\ldots ,m-1\}$
to state
$i+1$
(namely the transition on symbol
$w_{i+1}$
corresponding to the first case in the definition of
$\delta $
). As
$\vert \Sigma \vert> 1$
, there is a symbol
$a \in \Sigma $
with
$a \neq w_1$
, and hence there is an edge from state
$0$
to itself on symbol a. We claim that, for any state
$i \in \{1,\ldots ,m\}$
, there is a path in (the underlying directed graph of)
$M_w$
to some state
$j < i$
; it then follows by induction that there is a path from i to
$0$
and, by the above remarks, there is a path from state
$0$
to any state in
$M_w$
, whence
$M_w$
is strongly connected.
To prove the claim, let
$i \in \{1,\ldots ,m\}$
. Split on cases as follows.
-
• If
$i = m$
, choose (as
$\vert \Sigma \vert> 1$
)
$a \in \Sigma $
such that
$a \neq w_m$
. Then, by construction, there is a transition from state m on symbol a to some state
$j < m$
because the final symbol of
$w = w_1 \cdots w_m$
is distinct from a, the longest prefix of w such that
$w_{i-j+2} \cdots w_i a = w_1 \cdots w_j$
must satisfy
$j < m$
. -
• If
$i < m$
, choose (as
$\vert \Sigma \vert $
)
$a \in \Sigma $
such that
$a \neq w_{i+1}$
and, hence,
$w_1 \cdots w_i a$
is not a prefix of w, whence the longest prefix
$w_1 \cdots w_j$
of w such that
$w_{i-j+2} \cdots w_{i} a = w_1 \cdots w_j$
must satisfy
$j \leq i$
. If
$j < i$
, the claim is proved. If
$j = i$
, we have
$w_1 \cdots w_i = w_2 \cdots w_i a$
and, hence,
$w_ 1 = w_2 = \cdots = w_{i-1} = w_i = a$
. However, then
$w_1 \cdots w_i w_{i+1} = a^i w_{i+1}$
with
$w_{i+1} \neq a$
.-
– If
$i+1 = m$
, there is a directed edge from state i to state m on symbol
$w_m$
, and as
$w= a^{m-1} w_{i+1}= a^{m-1} w_m$
with
$w_m \neq a$
, there is a directed edge from state m to state
$0$
on symbol
$w_m$
because
$w_m w_m$
does not occur as a substring of w and
$w_m \neq a = w_1$
, concluding the proof of the claim. -
– If
$i + 1 < m$
, let k be the greatest integer such that
$k \leq m$
and
$w_{i+1},w_{i+2},\ldots , w_k \neq a$
. Then, there is a directed edge from state
$i+k$
to state
$0$
on symbol
$w_{i+1}$
because
$w= a^i w_{i+1} \cdots w_{k} c$
for some (possibly empty) string c and, thus, no non-empty suffix of
$ a^i w_{i+1} \cdots w_{k} w_{i+1}$
can be a prefix of w. By construction, there is a directed path from state i to state
$k> i$
. Hence, there is a directed path from state i to state
$0$
, as desired.
-
5 Finite-state selectors preserve
$\mu $
-distributedness for Bernoulli measures
The sequence of auxiliary results of this section follows the general lines of Agafonov’s original proof in Russian for the case
$\Sigma = \{0,1\}$
[Reference Агафонов57], but with multiple proofs needing more careful analysis and adapted techniques.
5.1 Ancillary definitions and results
Definition 5.1. Let
$\Sigma $
be an alphabet,
$\alpha = x_1 x_2 \cdots x_n \cdots \in \Sigma ^\omega $
, and let n be a positive integer. The n-block decomposition of
$\alpha $
is the sequence
$(\alpha _{(n,r)})_{r \geq 1}$
, where
$\alpha _{(n,r)} = x_{(r-1)n+1} \cdots x_{rn} \in \Sigma ^n$
.
Thus,
$\alpha _{(n,1)}$
is the string of the first n symbols of
$\alpha $
,
$\alpha _{(n,2)}$
is the string of the next n symbols, and so forth.
Definition 5.2. Let
$\mu $
be a probability map over
$\Sigma $
and
$\alpha =x_{1}x_{2}\cdots x_{n} \cdots \in \Sigma ^\omega $
. We say that
$\alpha $
is
$\mu $
-block-distributed if, for each
$n \geq 1$
and every
${w} \in \Sigma ^n$
, the n-block decomposition
$(\alpha _{(n,r)})_{r\geq 1}$
of
$\alpha $
satisfies
$$ \begin{align*} \lim_{k \rightarrow \infty} \frac{\vert i \leq k : \alpha_{(n,i)} = {w} \vert}{k} = \mu({w}). \end{align*} $$
For finite alphabets and the special case of p being an equidistribution on
$\Sigma $
, it is straightforward to prove that the properties of being
$\mu _p$
-distributed and
$\mu _p$
-block-distributed are equivalent [Reference Cassels16, Reference Niven and Zuckerman37, Reference Постникова61]. For the present paper, we only use that
$\mu _p$
-distributedness implies
$\mu _p$
-block-distributedness. This result can be proved by tedious, but standard, counting arguments on sufficiently large finite prefixes of
$\alpha \vert _{\leq N}$
using the same reasoning as the original proof by Niven and Zuckerman for finite alphabets and normality [Reference Niven and Zuckerman37]. However, we are indebted to an anonymous referee for suggesting the—much more elegant and succinct—proof of Proposition 5.1 below.
Proposition 5.1. Let
$\mu _p$
be a probability map induced by a Bernoulli distribution p on the alphabet
$\Sigma $
. If
$\alpha \in \Sigma ^\omega $
is
$\mu _p$
-distributed, it is
$\mu _p$
-block distributed.
Proof. Let I be an arbitrary set of cylinder sets
$[{v}]$
with
$v \in \Sigma ^*$
and let m be a positive integer (the ‘block size’). For any non-negative integer n, let
$\#^0_I(n)$
be the number of occurrences of an element of I in the prefix of
$\alpha $
of length n at any position j with
$j = km+1$
for some non-negative integer k (that is, the element of I occurs in the beginning of a size-m block in the block decomposition of
$\alpha $
), and let
$\#_I(n)$
be the number of occurrences of an element of I in any position in the prefix of
$\alpha $
of length n.
Let
$W \subseteq \Sigma ^*$
be a set such that no element of W is a prefix of any other element. Hence, for arbitrary
$v,w \in W$
with
$v \neq w$
, the cylinder sets
$[{v}]$
and
$[{w}]$
are disjoint.
Then,
$$ \begin{align*} \limsup_{n \rightarrow \infty} \frac{\#^0_W(n)}{n/m} \leq \limsup_{n \rightarrow \infty} \frac{\#_W(n)}{n/m} \leq m \limsup_{n\rightarrow \infty} \frac{\#_W(n)}{n}. \end{align*} $$
However, as
$\alpha $
is
$\mu _p$
-distributed, for every
$w \in W$
, we have
$\lim _{n\rightarrow \infty } \#_w(n)/n = \mu _p(w)$
, and as
$\mu _p$
is a probability map and no element of W is a prefix of any another,
$\sum _{w \in W} \mu _p(w)$
exists by the dominated convergence theorem. By the bounded convergence theorem, we then have
$\lim _{n \rightarrow \infty } ({\#_W(n)}/{n}) = \sum _{w \in W} \mu _p(w)$
and, thus,
$$ \begin{align*} m \limsup_{n\rightarrow \infty} \frac{\#_W(n)}{n} = m \lim_{n \rightarrow \infty} \frac{\#_W(n)}{n} = m \sum_{w \in W} \mu_p(w), \end{align*} $$
whence in particular
$\limsup _{n \rightarrow \infty } ({\#^0_W(n)}/{n/m}) \leq m \sum _{w \in W} \mu _p(w)$
.
Any union of a countable set I of cylinder sets is also the union of a countable set
$W \subseteq I$
of cylinder sets
$[{v}]$
such that no string v is a prefix of any other string
$w \neq v$
with
$[{w}] \in I$
(simply winnow out all strings that are proper suffixes of elements already in I), and hence, by the above inequalities,
$$ \begin{align*} \limsup_{n\rightarrow \infty} \frac{\#^0_I(n)}{n/m} \leq \limsup_{n\rightarrow \infty} \frac{\#^0_W(n)}{n/m} \leq m \sum_{w \in W} \mu_p(w) \leq m \sum_{w \in I} \mu_p(w), \end{align*} $$
where
$\sum _{w \in W} \mu _p(w)$
always exists.
It then follows immediately by [Reference Airey and Mance3, Theorem 2] that for any cylinder set
$[w]$
with
$w \in \Sigma ^m$
, we have
$$ \begin{align*} \lim_{n\rightarrow \infty} \frac{\#_W^0 (n)}{n/m} = \sum_{w \in W} \mu_p(w) = \mu_p(w). \end{align*} $$
The number of occurrences of w as a size-m block in the first n symbols of the m-block decomposition of
$\alpha \vert _{\leq n}$
is exactly
$\#^0_{w} (n)$
, and the result follows.
We now prove that finite-state selectors can be composed appropriately; this will later be a key ingredient in reducing the problem of selecting finite strings
$w \in \Sigma ^*$
with frequency
$\mu _p(w)$
to the problem of selecting single symbols
$a \in \Sigma $
with frequency
$p(a)$
.
Proposition 5.2. (Finite-state selectors are compositional)
Let A and B be DFAs over the same alphabet. Then, there is a DFA C such that, for each sequence
${w}$
,
$C[{{w}}] = B[{A[{{w}}]}]$
. If A and B are both strongly connected, and A contains at least one accepting state, C can be chosen to be strongly connected.
Proof. Let
$A = (Q^A,\Sigma ,\delta ^A,q_0^A,Q_F^A)$
and
$B = (Q^B,\Sigma ,\delta ^B,q_0^B,Q_F^B)$
. Define
$Q^C = Q^A \times Q^B$
, and set
$q_0^C = (q_0^A,q_0^B)$
and
$Q_F^C = Q_F^A \times Q_F^B$
. For each
$q^B \in Q^B$
, define the set
$D_{q^B} = \{(q,q^B) : q \in Q^A \} \subseteq Q^C$
. Observe that
$Q^C = \bigcup _{q^B \in Q^B} D_{q^B}$
and that for
$q^B, r^B \in Q^B$
with
$q^B \neq r^B$
, we have
$D_{q^B} \cap D_{r^B} = \emptyset $
, and thus
$\{D_{q^B} : q^B \in Q^B\}$
is a partitioning of
$Q^C$
. Hence, the transition relation,
$\delta ^C$
, of C may be defined by defining it separately on each subset
$D_{q^B}$
:
$$ \begin{align*} \delta^C((q,q^B),a) = \begin{cases} (r,q^B) & \textrm{if } q \notin Q_F^A \textrm{ and } \delta^A(q,a) = r, \\ (r,r^B) & \textrm{if } q \in Q_F^A \textrm{ and } \delta^A(q,a) = r \textrm{ and } \delta^B(q^B,a) = r^B. \\ \end{cases} \end{align*} $$
Thus, when C processes its input, it freezes the current state
$q^B$
of B (the freezing is represented by staying within
$D_{q^B}$
) and simulates A until an accepting state of A is reached (that is, just before A would select the next symbol); on the next transition, C unfreezes the current state of B and moves to the next state
$r^B$
of B, and then freezes it and continues with a simulation of A.
Observe that a symbol is picked out by C if and only if the state is an element of
$Q_F^C = Q_F^A \times Q_F^B$
if and only if the symbol is the next symbol read after simulation of A reaches an accepting state of A when the current frozen state of B is an accepting state of B.
By construction, C is strongly connected if both A and B are: for any pair of states
$(q_1^A,q_1^B)$
and
$(q_2^A,q^2_B)$
in
$Q^C$
, strong connectivity of B implies that there is a directed path from
$q_1^B$
to
$q_2^B$
in B. Let
$q_1^B, q_{1,2}^B, q_{1,3}^B,\ldots ,q_{1,k}^B$
be the states along this path. Strong connectivity of A and the assumption that there is some
$q_1^F \in Q_F^A$
imply that there is a directed path from
$(q_1^A,q_1^B)$
to
$(q_1^F,q_1^B)$
in C, and by definition of
$\delta ^C$
, there is a transition in C from
$(q_1^F,q_1^B)$
to
$(q_1^B,q_{1,2}^B)$
. A straightforward induction on k now completes the proof.
The following shows that to prove that the property of being
$ \mu _p$
-distributed is preserved under finite-state selection, it suffices to prove that the limiting frequency of each
$a \in \Sigma $
exists and equals
$p(a)$
.
Lemma 5.3. Let
$\mu _p$
be a probability map induced by a Bernoulli distribution p on
$\Sigma $
, and let
$\alpha \in \Sigma ^\omega $
be
$\mu _p$
-distributed. The following are equivalent.
-
• For all strongly connected DFAs A, if
$A[\alpha ]$
is infinite, then
$A[\alpha ]$
is
$\mu _p$
-distributed. -
• For all strongly connected DFAs A and all
$a \in \Sigma $
, if
$A[\alpha ]$
is infinite, then the limiting frequency of a in
$A[\alpha ]$
exists and equals
$p(a)$
.
Proof. If, for all A such that
$A[\alpha ]$
is infinite,
$A[\alpha ]$
is
$\mu _p$
-distributed, then in particular the limiting frequency of a in
$A[\alpha ]$
exists and is equal to
$p(a)$
for all A.
Conversely, suppose that, for all strongly connected DFAs A and all
$a \in \Sigma $
, if
$A[\alpha ]$
is infinite, then the limiting frequency of a in
$A[\alpha ]$
exists and equals
$p(a)$
. If
$\vert \Sigma \vert = 1$
, it follows immediately that
$A[\alpha ]$
is
$\mu _p$
-distributed; hence, in the remainder of the proof, assume that
$\vert \Sigma \vert \geq 2$
.
Let A be a strongly connected DFA such that
$A[\alpha ]$
is infinite. If A has no accepting states, there is nothing to prove, so assume that A has at least one accepting state.
We will prove by induction on
$k \geq 0$
that the limiting frequency of every
$v_1 \cdots v_k v_{k+1} \in \Sigma ^{k+1}$
exists and equals
$\mu _p(v_1 \cdots v_k v_{k+1})$
.
-
•
$k = 0$
. This is the supposition. -
•
$k \geq 1$
. Suppose that the result has been proved for
$k-1$
. Let
$v = v_1 \cdots v_k \in \Sigma ^k$
; by the induction hypothesis, the limiting frequency of
$v_1 \cdots v_k$
in
$A[{w}]$
is
$\mu _p(v_1 \cdots v_k)$
. We claim that there is a strongly connected DFA B that, from any sequence
$\alpha $
, selects the symbol after each occurrence of
$v_1 \cdots v_k$
, and only those symbols, except for at most k symbols at the start of
$\alpha $
. We construct such a DFA as follows. Set
$B = (\{q_0,\ldots ,q_k\},\delta , q_0, \{q_k\}\}$
, with
$\delta $
to be defined below. For i with
$0\leq i\leq k$
, the state
$q_i$
represents a situation where the last i symbols read by
$M_w$
is a length-i prefix of v among the last k symbols read, and i is maximal (that is, there is no j with
$i < j \leq k$
such that the last j symbol read by B is also a prefix of v); observe that v can overlap with itself, e.g.,
$wv= 000$
, so when B has read the string
$100$
,
$i=2$
, but the rightmost
$0$
in
$100$
is also a prefix of v.We define
$\delta $
as follows, for any
$q_i$
and
$a \in \Sigma $
:
$\delta (q_i,a) = q_j$
, where j is the largest j with
$0 < j \leq k$
such that
$v_{k-j+1} \cdots v_i \cdot a$
is a prefix of v. Note in particular that if
$v_1 \cdots v_i a = v_1 \cdots v_i v_{i+1}$
, then
$\delta (q_i,a) = q_{i+1}$
. If no such j exists (that is, no prefix of v overlaps with the last k symbols read), we define
$\delta (q_i,a) = q_0$
. Observe in particular, that
$q_0$
has transitions to itself on all symbols a such that
$a \neq v_1$
.To see that
$M_w$
is strongly connected, we prove the stronger property that between any (not necessarily distinct) states
$q_i, q_j$
, there is a path containing the state
$q_k$
. Observe that the state
$q_i$
represents the situation where the prefix
$v_1 \cdots v_i$
has been read by B, and that there is a path
$(q_{i},v_{i+1}) \cdots (q_{k-1}, v_{k})$
to
$q_k$
. As
$\vert \Sigma \vert \geq 2$
, there is at least one symbol
$a \in \Sigma $
such that no suffix of
$v_1 \cdots v_k \cdot a$
is a non-empty prefix of v, and hence, there is at least one transition from
$q_k$
to
$q_0$
; this proves strong connectivity.By Theorem 5.2, there is a strongly connected DFA C such that
$C[{w}] = B[A[{w}]]$
for all
$w \in \Sigma ^*$
.For any
$a \in \Sigma $
and any sufficiently large positive integer N, we have
$$ \begin{align*} \frac{\#_{a}(C[{\alpha\vert_{\leq N}}])}{\vert C[{\alpha\vert_{\leq N}}] \vert} = \frac{\#_{a}(B[{A[{\alpha\vert_{\leq N}}]}])}{\vert B[{A[{\alpha\vert_{\leq N}}]}] \vert} = \frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])}. \end{align*} $$
By the induction hypothesis, for every
$\epsilon> 0$
, we have, for all sufficiently large N, that
$\vert {\#_{a}(C[{\alpha \vert _{\leq N}}])}/{\vert C[{\alpha \vert _{\leq N}}] \vert } - p(a) \vert < \epsilon $
, and hence, (5.1)
$$ \begin{align} \bigg\vert\frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])} - p(a) \bigg\vert < \epsilon. \end{align} $$
However, for all sufficiently large N, the induction hypothesis also furnishes that
(5.2)Nevertheless, as
$$ \begin{align} \bigg\vert \frac{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])}{\vert A[{\alpha\vert_{\leq N}}]\vert} - \mu_p(v_1 \cdots v_k)\bigg\vert < \epsilon. \end{align} $$
equations (5.1) and (5.2) thus yield
$$ \begin{align*} \frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\vert A[{\alpha\vert_{\leq N}}]\vert} = \frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])} \cdot \frac{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])}{\vert A[{\alpha\vert_{\leq N}}]\vert}, \end{align*} $$
Hence, for all
$$ \begin{align*} &\bigg\vert \frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\vert A[{{\alpha\vert_{\leq N}}}]\vert} - \mu_p(v_1 \cdots v_k a)\bigg\vert\\ &\quad= \bigg\vert \frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])} \cdot \frac{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])}{\vert A[{\alpha\vert_{\leq N}}]\vert} - \mu_p(v_1 \cdots v_k)p(a) \bigg\vert \\ &\quad< \epsilon^2 + \epsilon\bigg( \frac{\#_{v_1 \cdots v_k a}(A[{\alpha\vert_{\leq N}}])}{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])} + \frac{\#_{v_1 \cdots v_k }(A[{\alpha\vert_{\leq N}}])}{\vert A[{\alpha\vert_{\leq N}}]\vert}\bigg)\\ &\quad\leq \epsilon^2 + 2\epsilon. \end{align*} $$
$a \in \Sigma $
, the limiting frequency of
$v_1 \cdots v_k a$
in
$A[{\alpha }]$
exists and equals
$\mu _p(v_1 \cdots v_k a)$
, as desired.
5.2 Preservation of Bernoulli
$\mu _p$
-distributedness under finite-state selection
By Lemma 5.3, we may restrict our attention to proving that the frequency of single symbols from
$\Sigma $
are preserved under selection by DFAs. The strategy will be to consider an arbitrary strongly connected DFA A, split the set of finite words
$\Sigma ^*$
into multiple classes that depend on the selection behavior of A, and use a combination of concentration bounds and basic Markov chain theory applied to these classes to obtain upper and lower bounds on the frequency with which A selects each symbol from A.
Definition 5.3. Let
$A = (Q,\Sigma ,\delta ,q_0,Q_F)$
be a strongly connected DFA. For any probability distribution
$p : \Sigma \longrightarrow [0,1]$
, any
$b\in [0,1]$
,
$n\in \mathbb {N}$
, and any
$\epsilon>0$
, we define sets
$D^p_n(b,\epsilon )$
,
$E_n(b)$
, and
$G_n(b,\epsilon )$
as follows:
$$ \begin{align*} D_{n}^{p}(b,\epsilon,q) &= \bigg\{{w}\in\Sigma^{n}~:~ \vert A_{q}[{{w}}] \vert>bn \textrm{ and } \sup_{a \in \Sigma} \bigg\vert \frac{\#_{a}(A_{q}[{w}])}{\vert A_{q}[{w}]\vert}-p(a)\bigg\vert<\epsilon\bigg\}, \\ D_n^p(b,\epsilon) &= \bigcap_{q \in Q} D_n^p(b,\epsilon,q),\\ E_n(b,q) &= \{{w}\in\Sigma^{n} : \vert A_{q}[{w}] \vert\leq bn\}, \\ E_{n}(b) &= \bigcup_{q\in Q} E_{n}(b,q),\\ G_n(b,\epsilon,q) &= \bigg\{{w}\in\Sigma^{n} : \vert A_{q}[{w}]\vert>bn \textrm{ and } \sup_{a \in \Sigma} \bigg\vert\frac{\#_{a}(A_{q}[{w}])}{\vert A_{q}[{w}] \vert}-p(a) \bigg\vert \geq\epsilon\bigg\},\\ G_{n}(b,\epsilon) &=\bigcup_{q\in Q}G_{n}(b,\epsilon,q). \end{align*} $$
The definitions of the above sets are necessarily quite technical, but we will try to provide some rough intuitive explanations. The set
$D_n(b,\epsilon )$
consists of words
${w}$
of length n such that the automata A, given any state q as initial state, will pick out from
${w}$
a subsequence of length at least
$bn$
and in which is well-distributed up to
$\epsilon $
. The set
$E_n(b)$
denotes the set of words
${w}$
of length n such that there exists at least one state q for which A, with initial state q, will pick out from
${w}$
a word of length smaller that
$bn$
. Lastly, the set
$G_n(b,\epsilon )$
is the set of words
${w}$
of length n such that there exists at least one state q for which A, with initial state q, will pick out from
${w}$
a word of length at least
$bn$
, but in which the proportion of at least one symbol a will differ from
$p(a)$
by more than
$\epsilon $
.
Observe that, for all
$b,n,\epsilon $
,
$$ \begin{align*} \Sigma^n = E_n(b) \cup D_n^p(b,\epsilon) \cup G_n(b,\epsilon) \end{align*} $$
(and also note that
$E_n(b)$
and
$G_n(b,\epsilon )$
are not necessarily disjoint).
We will show in the following that as n grows, the measure of the set
$D_n(b,\epsilon )$
(for a well-chosen value b) goes to
$1$
. This is done by showing that the measure of the two other sets goes to
$0$
. We will then be able to use this result to prove that the sequence picked out from A will be well distributed. A key observation here is the intersection over all states in the definition of
$D_n(b,\epsilon )$
as it ensures that one can apply the result on any block in the block decomposition of the input sequence even if the state the automata A will have reached through the computation over preceding blocks is unknown.
Lemma 5.4. Let p be a positive Bernoulli distribution on
$\Sigma $
, let
$S=(Q,\Sigma ,\delta ,q_s,Q_F)$
be a strongly connected finite automaton with
$Q_F \neq \emptyset $
, and let n be a positive integer. Then, there exists a real number
$c>0 $
such that for all real numbers
$\epsilon>0$
, we have
$\lim _{n\rightarrow \infty } \mu _{p}( E_{n} (c-\epsilon ))=0$
.
Proof. Here, S induces a stochastic
$\vert Q \vert \times \vert Q \vert $
matrix
$\mathbf {P}$
by setting
$$ \begin{align*}\mathbf{P}_{ij} = \sum_{a \in \Sigma} p(a) \cdot 1_ {\delta(i,a)=j}. \end{align*} $$
Observe that if
$\Sigma $
is infinite, the fact that (i)
$p(a) \cdot 1_{\delta (i,a)=j} \geq 0$
, (ii)
$p(a) \cdot 1_{\delta (i,a)=j} \leq p(a)$
, and (iii)
$\sum _{a \in \Sigma } p(a) = 1$
entails that the series
$\sum _{a \in \Sigma } p(a) \cdot 1_{\delta (i,a)=j}$
is absolutely convergent.
Note also that
$\mathbf {P}_{ij} =0$
if and only if there are no transitions from i to j in Q on a symbol
$a \in \Sigma $
with
$p(a)> 0$
. As S is strongly connected, there exists a path from state i to state j for each
$i,j \in Q$
. Let v be the word along this path; as
$p(a)> 0$
for all
$a \in \Sigma $
, we have
$\mu _p(v)> 0$
, whence for each
$i,j$
, there is an integer
$n_{ij}$
such that
$\mathbf {P}^{n_{ij}}_{ij}> 0$
, that is,
$\mathbf {P}$
(and its associated Markov chain) is irreducible. As all states of a finite Markov chain with irreducible transition matrix are positive recurrent, standard results (see, e.g., [Reference Serfozo45, Theorem 54]) yield that there is a unique positive stationary distribution
$\pi : Q \longrightarrow [0,1]$
(such that, for all
$i \in Q$
, we have
$\pi (i)> 0$
and
$\pi (i) = \sum _{j \in Q} \pi (j)\mathbf {P}_{ij}$
). Furthermore, the expected return time
$M_i$
to state i satisfies
$M_i = 1/\pi (i)$
.
Let
$(X_n)_{n \geq 0} = (X_0,X_1,X_2,\ldots )$
be the Markov chain with transition matrix
$\mathbf {P}$
and some initial distribution
$\unicode{x3bb} $
on the states. Consider, for each
$i \in Q$
, the stochastic variable
$V_i$
, where
$$ \begin{align*} V_i(n) = \sum_{k=0}^{n-1} 1_{X_k = i}, \end{align*} $$
that is,
$V_i(n)$
is the number of times state i is visited in the first n elements of the Markov chain. As
$\mathbf {P}$
is irreducible, the ergodic theorem for Markov chains (see, e.g., [Reference Serfozo45, Theorem 75]) yields that, independently of
$\unicode{x3bb} $
, we have for arbitrary
$\epsilon> 0$
,
$$ \begin{align} \lim_{n\rightarrow\infty} \textrm{Pr}\bigg( \bigg\vert \frac{V_i(n)}{n} - \pi(i) \bigg\vert \geq \epsilon \bigg) = \lim_{n\rightarrow\infty} \textrm{Pr}\bigg( \bigg\vert \frac{V_i(n)}{n} - \frac{1}{M_i} \bigg\vert \geq \epsilon \bigg) = 0. \end{align} $$
Let n be a positive integer, let
$w = w_1 \cdots w_n \in \Sigma ^n$
, and let
$\mathbf {q}_{S_j}(w) = q^w_0 q^w_1 \cdots q^w_{n}$
be the sequence of states visited in the run of
$S_j$
on w (that is,
$q^w_0 = j$
). The probability of observing a state sequence
$q_0 \cdots q_n$
in the Markov chain is (when the initial distribution
$\unicode{x3bb} $
has
$\unicode{x3bb} (q_0) = \unicode{x3bb} (j) = 1$
)
$$ \begin{align*} \textrm{Pr}(q_0 \cdots q_n) &= \prod_{i=0}^{n-1} \sum_{a \in \Sigma} p(a) 1_{\delta(q_i,a) = q_{i+1}}\\ &= \sum_{a_1,\ldots,a_n \in \Sigma} p(a_1)1_{\delta(q_0,a_1) = q_1} \cdots p(a_n)1_{\delta(q_{n-1},a_{n}) = q_n}, \end{align*} $$
where we have used the fact that the Cauchy product of two absolutely convergent series is convergent.
As for all integers i with
$0 \leq i \leq n$
, we have
$\delta (q^w_{i-1},w_i) = q^w_i$
, we obtain
$$ \begin{align*} &\sum_{a_1,\ldots,a_n \in \Sigma} p(a_1)1_{\delta(q_0,a_1) = q_1} \cdots p(a_n)1_{\delta(q_{n-1},a_{n}) = q_n}\\ &\quad= \mu_p(\{a_1 \cdots a_n : \mathbf{q}_{S_j}(a_1 \cdots a_n) = q_0 \cdots q_n\}), \end{align*} $$
and hence,
$$ \begin{align} \textrm{Pr}(q_0 \cdots q_n) = \mu_p(\{w : \mathbf{q}_{S_j}(w) = q_0 \cdots q_n \}). \end{align} $$
Thus, as S is deterministic and every
$w_1 \cdots w_n \in \Sigma ^n$
occurs along exactly one path of states in S, we have
$$ \begin{align} \textrm{Pr}\bigg( \bigg\vert \frac{V_i(n)}{n} - \pi(i)\bigg\vert \geq \epsilon\bigg) &= \sum_{q_0 q_1 \cdots q_n \in Q^n} \textrm{Pr}( q_0 \cdots q_{n}) 1_{\vert V_i(n)/n - \pi(i) \vert \geq \epsilon} \nonumber \\ &= \sum_{q_0 q_1 \cdots q_n \in Q^n} \mu_p(\{w_1 \cdots w_n : \mathbf{q}_{S_j}(w_1 \cdots w_n) = q_0 \cdots q_n\}) \nonumber \\ &= \mu_p\bigg( w : \bigg\vert \frac{V_i(n)}{n} - \pi(i)\bigg\vert \geq \epsilon \bigg). \end{align} $$
Hence, by equations (5.3) and (5.5), we have
$$ \begin{align} \lim_{n\rightarrow \infty} \mu_p\bigg( w : \bigg\vert \frac{V_i(n)}{n} - \pi(i)\bigg\vert \geq \epsilon \bigg) = 0. \end{align} $$
If
$\mathbf {q}_{S_j}(w) = q_0 \cdots q_{n}$
and
$q_k \in Q_F$
for some k with
$0 \leq k \leq n-1$
, then
$S_j$
selects
$w_{k+1}$
. Set
$c = \min _{q_i \in Q_F} \pi (i)$
(c is well defined as
$Q_F \neq \emptyset $
), and let
$i \in Q_F$
be such that
$\pi (i) = c$
. Then, for all
$j \in Q$
,
$$ \begin{align*} &\mu_p(E_n(c-\epsilon,j))\\ &\quad= \mu_p\bigg( \{w \in \Sigma^n : \vert S_j[w] \vert \leq (c - \epsilon) n \}\bigg) \leq \mu_p\bigg( \{w \in \Sigma^n : V_i(n) \leq (c - \epsilon) n \}\bigg) \\ &\quad= \mu_p\bigg( \bigg\{w \in \Sigma^n : \frac{V_i(n)}{n} - c \leq - \epsilon \bigg\}\bigg) \leq \mu_p\bigg( \bigg\{w \in \Sigma^n : \bigg\vert \frac{V_i(n)}{n} - c \bigg\vert \geq \epsilon \bigg\}\bigg). \end{align*} $$
Hence, by equation (5.6), we have
$\lim _{n\rightarrow \infty } \mu _p(E_n(c-\epsilon ,j)) = 0$
, and as
$j \in Q$
was arbitrary, we obtain
$$ \begin{align*} \lim_{n\rightarrow\infty} \mu_p(E_n(c-\epsilon)) &= \lim_{n\rightarrow\infty} \mu_p(\bigcup_{j \in Q} E_n(c-\epsilon,j) \leq \lim_{n \rightarrow \infty} \sum_{j \in Q} \mu_p(E_n(c - \epsilon,j)) \\ &= \sum_{j \in Q} \lim_{n\rightarrow\infty} \mu_p(E_n(c - \epsilon,j)) = 0, \end{align*} $$
as desired.
Lemma 5.5. Let S be a strategy,
$a \in \Sigma $
,
$b, \epsilon $
be real numbers with
$0 < b \leq 1$
and
$\epsilon> 0$
, and
$p : \Sigma \longrightarrow [0,1]$
be a positive Bernoulli distribution. Define, for all positive integers n,
$$ \begin{align*} H_{n}(b,\epsilon) &=\bigg\{{w}\in\Sigma^{n} : \vert S({w})\vert>bn \textrm{ and } \bigg\vert p(a) - \frac{\#_{a}(S({w}))}{\vert S({w}) \vert} \bigg\vert \geq \epsilon\bigg\} \\ &= \bigcup_{bn < \ell \leq n} \bigg\{{w} \in \Sigma^n : S({w}) \in \Sigma^\ell \textrm{ and } \bigg\vert p(a) - \frac{\#_{a}(S({w}))}{\ell} \bigg\vert \geq \epsilon \bigg\}. \end{align*} $$
Then,
$$ \begin{align*} \lim_{n\rightarrow\infty}\mu_{p}(H_{n}(b,\epsilon))=0. \end{align*} $$
Proof. Define
$$ \begin{align*} F_n(b,\epsilon) = \bigcup_{bn < \ell \leq n} \bigg\{ {y} \in \Sigma^{\ell} : \bigg\vert p(a) - \frac{\#_{a}({y})}{\ell} \bigg\vert \geq \epsilon \bigg\}. \end{align*} $$
Observe that
$H_n(b,\epsilon ) = \{{w} \in \Sigma ^n : S({w}) \in F_n(b,\epsilon ) \}$
. By definition of
$\mu _p$
, if
${v} = v_1 \cdots v_n\in \Sigma ^n$
, then the set
$T_v = \{w \in \Sigma ^* : \text { there exists } u_0,\ldots ,u_n \in \Sigma ^*. w = u_0 v_1 u_1 \cdots v_n u_n\}$
satisfies
$\mu _p(T_w) \leq \mu _p(v)$
, and hence in particular if S is any strategy, then
$\mu _p(\{{w} : S(w) = v\}) \leq \mu _p(v)$
. Thus,
$\mu _p(H_n(b,\epsilon )) \leq \mu _p (F_n(b,\epsilon ))$
for all n, and it thus suffices to prove that
$\lim _{n\rightarrow \infty } \mu _p(F_n(b,\epsilon )) = 0$
.
Consider the stochastic variable
$X_a$
that is
$1$
when a is picked from
$\Sigma $
with probability
$p(a)$
, and
$0$
otherwise. Then, the mean of
$X_a$
is
$p(a)$
and the variance of
$X_a$
is
$p(a) (1-p(a))$
. Now consider performing
$\ell \geq 1$
independent Bernoulli trials drawn according to
$X_a$
. Define
$q : \{0,1\}^+ \longrightarrow [0,1]$
inductively by
$q(1) = p(a)$
,
$q(0) = 1-p(a)$
, and
$q(1c) = q(c)p(a)$
and
$q(0c) = q(c)(1-p(a))$
for
$c \in \{0,1\}^+$
, and observe that q induces a probability distribution
$\bar {q}$
on
$\Sigma ^\ell $
by setting
$\bar {q}(w) = q(w)$
. Now, for any
${v} \in \{0,1\}^\ell $
,
$\bar {q}({v})$
is the probability of obtaining
${v}$
by performing
$\ell $
independent Bernoulli trials as above.
Define the stochastic variable
$X^{\ell }_a = X_a + X_a + \cdots + X_a$
(
$\ell $
times). Then,
$X^\ell $
counts the number of occurrences of a by performing the
$\ell $
repeated Bernoulli trials.
By the Chernoff bound,
$X^{\ell }_a$
satisfies
$$ \begin{align} \textrm{Pr}\bigg(\bigg\vert p(a) - \frac{X^{\ell}_a}{\ell} \bigg\vert \geq \epsilon \bigg) \leq 2 e^{-{\ell \epsilon^2}/{3p(a)}}. \end{align} $$
Define the map
$g : \Sigma \longrightarrow \{0,1\}$
by
$g(a) = 1$
and
$g(b) = 0$
for all
$b \in \Sigma \setminus \{a\}$
. Clearly, g extends homomorphically to a map
$\tilde {g} : \Sigma ^\ell \longrightarrow \{0,1\}^\ell $
by setting
$\tilde {g}(c_1 c_2 \cdots c_\ell ) = g(c_1)g(c_2) \cdots g(c_\ell )$
.
Claim. For any
${u} \in \{0,1\}^\ell $
,
$$ \begin{align} \bar{q}({u}) = \mu_p(\{{y} \in \Sigma^\ell : \tilde{g}({y}) = {u}\}). \end{align} $$
Proof of claim
By induction on
$\ell $
:
-
• if
$\ell = 1$
, then if
${u} = 0$
, we have
$\{{y} \in \Sigma ^\ell : \tilde {g}({y}) = {u}\} = \Sigma \setminus \{a\}$
and thus, Similarly, if
$$ \begin{align*} \bar{q}({u}) = \bar{q}(0) = q(0) = 1 - p(a) = \sum_{b \in \Sigma \setminus \{a\}} p(b) = \mu_p(\Sigma \setminus \{a\}). \end{align*} $$
${u} = 1$
, we have
$\{{y} \in \Sigma ^\ell : \tilde {g}({y}) = {u}\} = \{a\}$
and thus,
$\bar {q}({u}) = \bar {q}(1) = q(1) = p(a) = \mu _p(\{a\})$
, as desired;
-
• if
$\ell> 1$
, write
${u} = b_1 \cdots b_{\ell - 1} b_\ell $
; by the induction hypothesis, If
$$ \begin{align*} \bar{q}(b_1 \cdots b_{\ell - 1}) = \mu_p(\{{y} \in \Sigma^\ell : \tilde{g}({y}') = b_1 \cdots b_{\ell - 1}\}) = \sum_{\substack{{y}' \in \Sigma^{\ell - 1} \\ \tilde{g}({y}') = b_1 \cdots b_{\ell-1}}} \mu_p({y}'). \end{align*} $$
$b_\ell = 0$
, then where (
$$ \begin{align*} \bar{q}(b_1 \cdots b_{\ell - 1} b_\ell) &= \bar{q}(b_1 \cdots b_{\ell - 1})q(0)\\ & = \bar{q}(b_1 \cdots b_{\ell - 1})(1-p(a))\\ &= \sum_{\substack{{y}' \in \Sigma^{\ell - 1} \\ \tilde{g}({y}') = b_1 \cdots b_{\ell-1}}} \mu_p({y}') (1 - p(a)) \\ &= \sum_{\substack{{y}' \in \Sigma^{\ell - 1} \\ \tilde{g}({y}') = b_1 \cdots b_{\ell-1}}} \bigg(\mu_p({y}') \sum_{c \in \Sigma\setminus\{a\}} p(c) \bigg) \\ & = \sum_{\substack{{y}' \in \Sigma^{\ell - 1} \\ \tilde{g}({y}') = b_1 \cdots b_{\ell-1}}} \sum_{c \in \Sigma\setminus\{a\}} \mu_p({y}')p(c) \\ &\stackrel{(\dagger)}{=} \sum_{\substack{{y}' \in \Sigma^{\ell - 1} \\ \tilde{g}({y}') = b_1 \cdots b_{\ell-1}\\ c \in \Sigma \setminus \{a\}}} \mu_p({y}'c)\\ & = \sum_{\substack{{y} \in \Sigma^{\ell} \\ \tilde{g}({y}) = b_1 \cdots b_{\ell-1} b_\ell}} \mu_p({y})\\ &= \mu_p(\{{y} \in \Sigma^\ell : \tilde{g}({y}) = b_1 \cdots b_{\ell - 1} b_\ell\}), \end{align*} $$
$\dagger $
) follows as both series on the left- and right-hand sides of the equality are absolutely convergent. The proof for the case
$b_\ell = 1$
is symmetric, mutatis mutandis.
Observe that, for any
${y} \in \Sigma ^\ell $
, we have
$$ \begin{align} \vert p(a) - \#_{1}({\tilde{g}({y})})/\ell \vert \geq \epsilon \quad \text{if and only if} \quad \vert p(a) - \#_{a}({y})/\ell \vert \geq \epsilon. \end{align} $$
Hence, by equation (5.8), for any event
$\mathcal {U} \subseteq \{0,1\}^\ell $
, we have
$$ \begin{align} \textrm{Pr}(\mathcal{U}) &= \sum_{{u} \in \mathcal{U}} \bar{q}({u})= \sum_{{u} \in \mathcal{U}} \mu_p(\{{y} \in \Sigma^\ell : \tilde{g}({y}) = {u}\})) \nonumber\\ &= \mu_p( \{ {y} \in \Sigma^\ell : \tilde{g}({y}) \in \mathcal{U} \}). \end{align} $$
The event
$\vert p(a) - X^{\ell }_a/\ell \vert \geq \epsilon $
is shorthand for the set
$$ \begin{align*} \bigg\{ {u} \in \{0,1\}^\ell : \bigg\vert p(a) - \frac{\sum_{j=1}^\ell u_j}{\ell} \bigg\vert \geq \epsilon\bigg\} &= \bigg\{ {u} \in \{0,1\}^\ell : \bigg\vert p(a) - \frac{\#_{1}({u})}{\ell} \bigg\vert \geq \epsilon\bigg\}. \end{align*} $$
We thus obtain
$$ \begin{align} \textrm{Pr}\bigg( \bigg\vert p(a) - \frac{X^{\ell}_a}{\ell} \bigg\vert \geq \epsilon \bigg) &= \textrm{Pr}\bigg( \bigg\{ {u} \in \{0,1\}^\ell : \bigg\vert p(a) - \frac{\#_{1}({u})}{\ell} \bigg\vert \geq \epsilon\bigg\} \bigg) \nonumber\\ &= \mu_p \bigg( \bigg\{ {y} \in \Sigma^\ell : \bigg\vert p(a) - \frac{\#_{1}({\tilde{g}({y})})}{\ell} \bigg\vert \geq \epsilon \bigg\} \bigg) &\textrm{by equation}\ (5.10) \nonumber \\ &= \mu_p\bigg( \bigg\{ {y} \in \Sigma^\ell : \bigg\vert p(a) - \frac{\#_{a}({y})}{\ell} \bigg\vert \geq \epsilon \bigg\} \bigg) &\textrm{by equation}\ (5.9). \end{align} $$
Observe that
$$ \begin{align*} \mu_p\bigg(F_n(b,\epsilon) \bigg) &= \mu_p \bigg(\bigcup_{bn < \ell \leq n} \bigg\{ {y} \in \Sigma^{\ell} \cap F_n(b,\epsilon) : \bigg\vert p(a) - \frac{\#_{a}({y})}{\ell} \bigg\vert \geq \epsilon \bigg\} \bigg) \nonumber \\ &= \sum_{bn < \ell \leq n} \mu_p\bigg( \bigg\{ {y} \in \Sigma^{\ell} \cap F_n(b,\epsilon) : \bigg\vert p(a) - \frac{\#_{a}({y})}{\ell} \bigg\vert \geq \epsilon \bigg\} \bigg) \\ &\leq \sum_{bn < \ell \leq n}\mu_p\bigg( \bigg\{ {y} \in \Sigma^\ell : \bigg\vert p(a) - \frac{\#_{a}({y})}{\ell} \bigg\vert \geq \epsilon \bigg\} \bigg) \\ &= \sum_{bn < \ell \leq n} \textrm{Pr}\bigg( \bigg\vert p(a) - \frac{X^{\ell}_a}{\ell} \bigg\vert \geq \epsilon \bigg)\qquad\qquad \textrm{by equation}\ (5.11)\\ &\leq \sum_{bn < \ell \leq n} 2 e^{-{\ell \epsilon^2}/{3p(a)}}\qquad\qquad\qquad\qquad\hspace{5pt} \textrm{by equation}\ (5.7) \\ &\leq (1-b)n 2 e^{-{bn \epsilon^2}/{3p(a)}}. \end{align*} $$
Thus,
$\lim _{n\rightarrow \infty } \mu _p(F_n(b,\epsilon )) = 0$
, as desired.
Corollary 5.6. Let
$b,\epsilon $
be real numbers with
$0 < b \leq 1$
and
$\epsilon> 0$
. Then,
$$ \begin{align*} \lim_{n\rightarrow\infty}\mu_{p}(G_{n}(b,\epsilon))=0. \end{align*} $$
Proof. By Lemma 5.5 with S the strategy defined by the automaton
$A_q$
, we obtain that
$$ \begin{align*} \lim_{n\rightarrow\infty} \mu_p(G_n(b,\epsilon,q)) = 0 \end{align*} $$
and as
$G_n(b,\epsilon ) = \bigcup _{q\in Q}G_{n}(b,\epsilon ,q)$
, we have
$$ \begin{align*} \mu_p(G_n(b,\epsilon)) \leq \sum_{q\in Q}\mu_p(G_n(b,\epsilon,q)). \end{align*} $$
As Q is finite, we hence obtain
$\lim _{n \rightarrow \infty } \mu _p(G_n(b,\epsilon )) = 0$
.
Lemma 5.7. There is a real number b with
$0 < b \leq 1$
such that for all
$\epsilon> 0$
,
$$ \begin{align*} \lim_{n\rightarrow\infty} \mu_{p}(D_{n}^{p}(b,\epsilon)) = 1. \end{align*} $$
Proof. Observe that, for all b with
$0 < b \leq 1$
,
$$ \begin{align*} &\Sigma^n \setminus D_{n}^{p}(b,\epsilon))\\ &\quad= \{{w} \in \Sigma^n : \text{there exists } q \in Q. \vert A_q[{w}] \vert \leq bn\} \\ &\quad\cup \bigg\{ {w} \in \Sigma^n : \text{there exists } q \in Q. \vert A_q[{w}] \vert> bn \land \sup_{a \in \Sigma} \bigg\vert \frac{\#_{a}(A_q[{w}])}{\vert A_q[{w}] \vert} - p(a) \bigg\vert \geq \epsilon \bigg\} \\ &\quad= \bigg( \bigcup_{q \in Q} E_n(b,q) \bigg) \cup \bigg(\bigcup_{q \in Q} G_n(b,\epsilon,q) \bigg) \end{align*} $$
and thus,
$$ \begin{align*} \mu_p(\Sigma^n \setminus D_n^{p}(b,\epsilon)) &\leq \mu_p\bigg( \bigcup_{q \in Q} E_n(b,q) \bigg) + \mu_p\bigg( \bigcup_{q \in Q} G_n(b,\epsilon,q) \bigg)\\ &= \mu_p(G_n(b,\epsilon)) + \mu_p(E_n(b)). \end{align*} $$
By Theorem 5.4, choose a real number
$c> 0$
such that
$\lim _{n\rightarrow \infty } \mu _{p}(E_{n}(c-\epsilon ))=0$
, and set
$b = c - \epsilon $
.
By Theorem 5.6, we obtain that
$\lim _{n\rightarrow \infty } G_n(b,\epsilon ) = 0$
, and thus
$\lim _{n\rightarrow \infty }\mu _p(\Sigma ^n \setminus D_n^{p}(b,\epsilon )) = 0$
. The result now follows by
$\mu _p(D_n^{p}(b,\epsilon )) = 1 - \mu _p(\Sigma ^n \setminus D_n^{p}(b,\epsilon ))$
.
Lemma 5.8. Let
$p : \Sigma \longrightarrow [0,1]$
be a probability distribution, let
$\alpha \in \Sigma ^\omega $
be
$\mu _p$
-block-distributed, and A a strongly connected DFA over
$\Sigma $
. Then, for all
$a \in \Sigma $
, the limiting frequency of a in the sequence
$\beta = A[\alpha ]$
exists and equals
$p(a)$
.
Proof. For each
$n,r$
, let
$\beta _{(n,r)}$
be the sequence of symbols picked out from the block
$\alpha _{(n,r)}$
when A is applied to
$\alpha $
; note that each
$\beta _{(n,r)}$
has length between
$0$
and n.
For each positive integer m, define
$$ \begin{align*} L_m =\sum_{i=1}^{m}\vert \beta_{(n,i)} \kern-2pt\vert \end{align*} $$
and for each
$a \in \Sigma $
, define
$\rho _a^m$
by
$$ \begin{align*} \rho_a^m =\frac{\sum_{i=1}^{m} \#_{a}(\beta_{(n,i)})}{L_m}. \end{align*} $$
To prove the lemma, it suffices to show that, for any real number
$\epsilon> 0$
, then for all sufficiently large m, we have
$\mathopen {|}\rho _a^m-p(a)\mathclose {|}<\epsilon $
.
Define
$$ \begin{align*} I_m=\bigg\{i\leq m : \beta_{(n,i)}\not\in D_{n}^{p}\bigg(b,\frac{\epsilon}{2}\bigg)\bigg\}, \end{align*} $$
where
$b < 1$
is a constant to be fixed later in the proof.
Define
$$ \begin{align*} \ell_m =\sum_{i\in I_m}\vert \beta_{(n,i)} \kern-2pt\vert \end{align*} $$
Now, define
$\theta _a^m$
by
$$ \begin{align*} \theta_a^m = \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m} \#_{a}(\beta_{(n,i)})}{\sum_{i \in \{1,\ldots,m\} \setminus I_m} \vert \beta_{(n,i)}\kern-2pt\vert} = \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m} \#_{a}(\beta_{(n,i)})}{L_m - \ell_m}. \end{align*} $$
That is,
$\theta _a^m$
is the frequency of occurrences of a when the blocks
$\beta _{(n,i)]}$
picked out from blocks
$\alpha _{(i,r)} \in D_{n}^{p}(b,{\epsilon }/{2})$
with
$i \leq m$
are all concatenated. Observe that, by definition of
$D^p_n$
, we have
$\mathopen {|}\theta ^m_a-p(a)\mathclose {|}<{\epsilon }/{2}$
.
We have
$$ \begin{align} \rho_a^m - \theta_a^m &= \frac{\sum_{i=1}^{m} \#_{a}(\beta_{(n,i)})}{L_m} - \frac{\sum_{i\in \{1,\ldots,m\} \setminus I_m} \#_{a}(\beta_{(n,i)})}{L_m - \ell_m} \nonumber\\ &= \bigg(\frac{\sum_{i\in I_m} \#_{a}(\beta_{(n,i)})}{L_m} + \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m} \#_{a}(\beta_{(n,i)})}{L_m}\bigg) - \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m}\#_{a}(\beta_{(n,i)})}{L_m-\ell_m} \nonumber \\ &= \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m} \#_{a}(\beta_{(n,i)})}{L_m} - \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m}\#_{a}(\beta_{(n,i)})}{L_m-\ell_m} + \frac{\sum_{i\in I_m} \#_{a}(\beta_{(n,i)})}{L_m} \nonumber\\ &\leq \frac{\sum_{i\in I_m} \#_{a}(\beta_{(n,i)})}{L_m} \leq \frac{\sum_{i\in I_m} \vert \beta_{(n,i)}\kern-2pt\vert}{L_m} = \frac{\ell_m}{L_m}, \end{align} $$
where the penultimate inequalities in the last line above follows because
$L_m \geq L_m - \ell _m$
implies
${\sum _{i \in \{1,\ldots ,m\} \setminus I} \#_{a}(\beta _{(n,i)})}/{L} - {\sum _{i \in \{1,\ldots ,m\} \setminus I}\#_{a}(\beta _{[n,i]})}/{L-\ell } \leq 0$
, and the final inequality follows because
$\sum _{i\in I_m} \#_{a}(\beta _{(n,i)})\leq \sum _{i\in I}\vert \beta _{(n,i)} \kern -2pt\vert = \ell _m$
.
By basic algebra, we have
$$ \begin{align*} \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m} \#_{a}(\beta_{(n,i)})}{L_m} - \frac{\sum_{i \in \{1,\ldots,m\} \setminus I_m}\#_{a}(\beta_{(n,i)})}{L_m-\ell_m} = \frac{-\ell_m \sum_{i\in\{1,\ldots,m\} \setminus I}\#_{a}(\beta_{(n,i)})}{L_m(L_m-\ell_m)} \end{align*} $$
and as
$$ \begin{align*} \sum_{i\in\{1,\ldots,m\} \setminus I_m}\#_{a}(\beta_{(n,i)}) \leq \sum_{i\in\{1,\ldots,m\} \setminus I_m} \vert \beta_{(n,i)} \kern-2pt\vert = L_m-\ell_m, \end{align*} $$
we conclude that
$$ \begin{align*} \frac{-\ell_m \sum_{i\in\{1,\ldots,m\} \setminus I_m}\#_{a}(\beta_{(n,i)})}{L_m(L_m-\ell_m)} \geq -\frac{\ell_m}{L_m} \end{align*} $$
and thus by the first line of equation (5.12) and the fact that
$\ell _m \leq L_m$
, we have
$$ \begin{align*} \rho_a^m - \theta_a^m - \frac{\sum_{i\in I_m} \#_{a}(\beta_{(n,i)})}{L_m} \geq - \frac{\ell_m}{L_m}, \end{align*} $$
whence
$-\ell _m/L_m \leq \rho ^m_a - \theta ^m_a$
, which combined with equation (5.12) yields
$\vert \rho ^m_a - \theta ^m_a \vert \leq \ell _m/L_m$
.
By Theorem 5.7, pick a b such that for all
$\epsilon> 0$
, we have
$\lim _{n\rightarrow \infty } \mu _{p}(D_{n}^{p}(b,\epsilon )) = 1$
. Choose
$\delta>0$
with
$\delta <{b\epsilon }/{8}$
, and pick
$n\in \mathbb {N}$
such that
$\mu _{p}(D_{n}^{p}(b,\epsilon ))>1-\delta $
. Now, pick
$\gamma <{b\epsilon }/{8}$
. Because
$\alpha $
is
$\mu _p$
-block-distributed, there exists
$M \in \mathbb {N}$
such that for all
$k \geq M$
and all
${B}\subseteq \Sigma ^{n}$
, the prefix
$\alpha \vert _{\leq kn}$
satisfies
$$ \begin{align*} \bigg\vert \frac{\vert \{ i \leq k : \alpha_{(n,i)} \in {B}\} \vert}{k} - \mu_p({B}) \bigg\vert < \gamma. \end{align*} $$
In the particular case
${B} = D^p_n(b,\epsilon /2)$
, we thus have
$$ \begin{align*} \bigg\vert \frac{\vert \{ i \leq k : \alpha_{(n,i)} \in D_n^p(b,{\epsilon}/{2})\} \vert}{k} - \mu_p( D^p_n(b,{\epsilon}/{2}) ) \bigg\vert < \gamma \end{align*} $$
and thus,
$$ \begin{align*} &1 - \delta - \frac{\vert \{ i \leq k : \alpha_{(n,i)} \in D_n^p(b, {\epsilon}/{2})\} \vert}{k}\\ &\quad\leq \mu_p( D^p_n( b,{\epsilon}/{2} ) ) - \frac{\vert \{ i \leq k : \alpha_{(n,i)} \in D_n^p(b,{\epsilon}/{2})\} \vert}{k} < \gamma, \end{align*} $$
whence we conclude
$$ \begin{align} \bigg\vert \bigg\{ i \leq k : \alpha_{(n,i)} \in D_n^p\bigg( b,\frac{\epsilon}{2}\bigg)\bigg\} \bigg\vert> k(1-\delta - \gamma). \end{align} $$
By definition of
$D_{n}^{p}(b, {\epsilon}/{2})$
, as remarked above, every
$\alpha _{(n,i)} \in D_{n}^{p}(b, {\epsilon}/{2})$
satisfies
$\vert A_{\delta ^*(q_0,\alpha _{\leq ni})}[{\alpha _{(n,i)}}] \vert> bn$
, whichever state
$\delta ^*(q_0,\alpha _{\leq ni})$
is reached at the beginning of the block. We will in the following simply write
$\vert A[{\alpha _{(n,i)}}]\vert $
to simplify notation. We thus have
$$ \begin{align} L_m = \sum_{i=1}^m \vert \beta_{(n,i)} \vert = \sum_{i=1}^m \vert A[{\alpha_{(n,i)}}] \vert \geq \bigg\vert \bigg\{ i \leq m : \alpha_{(n,i)} \in D_n^p\bigg( b,\frac{\epsilon}{2}\bigg)\bigg\} \bigg\vert bn> m(1 - \delta - \gamma)bn. \end{align} $$
Furthermore, by the definition of
$I_m$
and equation (5.13),
$$ \begin{align*} \vert I_m \vert &= \bigg\vert \bigg\{i\leq m : \alpha_{(n,i)}\not\in D_{n}^{p}\bigg(b,\frac{\epsilon}{2}\bigg)\bigg\}\bigg\vert = m - \bigg\vert \bigg\{ i \leq m : \alpha_{(n,i)} \in D_n^p\bigg( b,\frac{\epsilon}{2}\bigg)\bigg\} \bigg\vert\\ &< m - m(1-\delta-\gamma) = m(\delta+\gamma). \end{align*} $$
However, then,
$$ \begin{align} \ell_m = \sum_{i \in I_m} \vert \beta_{(i,n)} \vert \leq \vert I_m \vert n < mn(\delta + \gamma) \end{align} $$
and thus by equations (5.14) and (5.15),
$$ \begin{align*} \frac{\ell_m}{L_m} < \frac{mn(\delta + \gamma)}{m(1 - \delta -\gamma)bn} = \frac{\delta + \gamma}{b(1 - \delta - \gamma)} < \frac{{b\epsilon}/{8} + {b\epsilon}/{8}}{b( 1- {b\epsilon}/{8} - {b\epsilon}/{8})} < \frac{{\epsilon}/{4}}{1 - {1}/{4}} < \frac{\epsilon}{2}, \end{align*} $$
where we have used that
$b\epsilon < 1$
in the penultimate inequality.
We now finally have
$$ \begin{align*} \vert \rho^m_a -p(a) \vert \leq \vert\rho^m_a - \theta^m_a \vert + \vert \theta^m_a -p(a) \vert < \frac{\ell_m}{L_m} + \frac{\epsilon}{2} < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon \end{align*} $$
concluding the proof.
Lemma 5.9. Let
$\Sigma $
be an alphabet, p a positive Bernoulli distribution on
$\Sigma $
, let
$\alpha \in \Sigma ^\omega $
be
$\mu _p$
-distributed, and let A be a strongly connected DFA over
$\Sigma $
. Then,
$A[\alpha ]$
is
$\mu _p$
-distributed.
Proof. By Lemma 5.3, it suffices to show for every
$a \in \Sigma $
and every strongly connected A that the limiting frequency of a in
$A[\alpha ]$
exists and equals
$p(a)$
. As
$\alpha $
is
$\mu _p$
-distributed, it follows from Proposition 5.1 that it is
$\mu _p$
-block-distributed, and the result then immediately follows by Lemma 5.8.
6 An application in symbolic dynamics: characterizing measures where genericity is preserved by DFAs
We now show an application of the main result to the area of symbolic dynamical systems. The following section recalls basic facts about symbolic dynamical systems, including establishing the correspondence between probability maps on
$\Sigma ^*$
and probability measures on full shifts.
6.1 Shift spaces and genericity
We briefly introduce basic notions; full accounts can be found in standard textbooks, e.g., [Reference Lind and Marcus30].
Definition 6.1. Let
$\Sigma $
be a non-empty alphabet. The (one-sided) shift
$s : \Sigma ^\omega \longrightarrow \Sigma ^\omega $
is the map defined by
$s(a_1 a_2 a_3 \cdots ) = a_2 a_3 \cdots $
. A shift space is a pair
$(X,s)$
, where
$X \subseteq \Sigma ^\omega $
is a closed (in the product topology on
$\Sigma ^\omega $
when
$\Sigma $
is endowed with the discrete topology) subset such that
$s(X) = X$
(for one-sided shifts, some authors require only
$s(X) \subseteq X$
; we shall not do so here) and s is the restriction of the shift to X.
As usual, we consider the
$\sigma $
-algebra
$\mathcal {C}$
on
$\Sigma ^\omega $
having the set of cylinders
$\{[{{w}}] : {w} \in \Sigma ^*\}$
as basis. All measures
$\mu $
in the remainder of the paper are understood to be measures on
$(\Sigma ^\omega , \mathcal {C})$
.
The standard example of probability measures on shift spaces is the set of Bernoulli measures [Reference Shields47].
Definition 6.2. A probability measure on the shift space
$(\Sigma ^\omega ,s)$
is a probability measure on
$\Sigma ^\omega $
with the
$\sigma $
-algebra generated by the cylinder sets
$\{[{{v}}] : {v} \in \Sigma ^*\}$
. A probability measure
$\bar {\mu }$
on the full shift is a Bernoulli measure if there is a probability distribution
$p : \Sigma \longrightarrow [0,1]$
such that the measure of each cylinder satisfies
$\bar {\mu }([{{a_1 \cdots a_n}}]) = \prod _{i=1}^n p(a_i)$
. In this case, we say that
$\bar {\mu }$
is induced by p.
Definition 6.3. Let
$(X,s)$
be a shift space. A probability measure
$\bar {\mu }$
on X is said to be shift invariant if
$\bar {\mu }(s^{-1}(A)) = \bar {\mu }(A)$
for all
$A \subseteq X$
. A finite word
${w} \in \Sigma ^k$
is said to be admissible for
$\mu $
if
$\bar {\mu }([{{w}}])> 0$
.
A right-infinite sequence
$\alpha \in \Sigma ^\omega $
is said to be generic for
$\bar {\mu }$
if, for all words
${w}$
admissible for
$\bar {\mu }$
, we have
$$ \begin{align*} \lim_{n\rightarrow \infty} \frac{\#_{{w}}(\alpha\vert_{\leq n})}{n} = \bar{\mu}([{{w}}]). \end{align*} $$
That is,
${w}$
occurs in
$\alpha $
with limiting frequency
$\bar {\mu }([{{w}}])$
.
The study of probability measures on the full shift is cryptomorphic to the study of invariant probability maps; this folklore result is contained in the following two propositions (proofs can be found in Appendix A).
Proposition 6.1. Every invariant probability map
$\mu : \Sigma ^* \longrightarrow [0,1]$
induces a shift-invariant probability measure
$\bar {\mu } : \Sigma ^\omega \longrightarrow [0,1]$
by setting
$\bar {\mu }([{{w}}]) = \mu ({w})$
. Conversely, every probability measure
$\nu :\Sigma ^\omega \longrightarrow [0,1]$
induces a probability map
$\underline {\nu } : \Sigma ^* \longrightarrow [0,1]$
by defining
$\underline {\nu }({w}) = \nu ([{{w}}])$
; if
$\nu $
is shift-invariant, then
$\underline {\nu }$
is invariant. Furthermore,
$\mu = \underline {(\bar {\mu })}$
and
$\nu = \overline {(\underline {\nu })}$
.
Proposition 6.2. Let
$\mu : \Sigma ^* \longrightarrow [0,1]$
be a probability map. The following are equivalent:
-
(1) there exists a
$\mu $
-distributed
$\alpha \in \Sigma ^\omega $
; -
(2)
$\mu $
is invariant; -
(3) there exists a shift-invariant probability measure
$\nu $
on
$\Sigma ^\omega $
such that
$\bar {\mu } = \nu $
.
Conversely, let
$\nu $
be a probability measure on
$\Sigma $
. The following are equivalent:
-
(1) there exists
$\alpha \in \Sigma ^\omega $
that is generic for
$\nu $
; -
(2)
$\nu $
is shift-invariant; -
(3) there exists an invariant probability map
$\mu : \Sigma ^* \longrightarrow [0,1]$
such that
$\underline {\nu } = \mu $
.
It follows that the shift-invariant probability measures
$\nu $
on the full shift such that genericity is preserved by finite-state selection are exactly the Bernoulli measures.
Theorem 6.3. Let
$\Sigma $
be a non-empty alphabet and let
$\nu $
be a shift-invariant measure on the full shift
$(\Sigma ^\omega ,s)$
. Then, every finite-state selector preserves genericity if and only if
$\nu $
is a Bernoulli measure such that all words in
$\Sigma ^*$
are admissible.
7 Future work
The most obvious extension of our main results is to attempt to relax the requirement that selection is done by a DFA by using methods similar to those of Kamae and Weiss [Reference Kamae and Weiss27], and Kamae and Wang [Reference Wang and Kamae56], where reasoning using a combination of density arguments and relaxed finiteness conditions on the syntactic monoid of the strategy (using our terminology) have been used for normal sequences over binary alphabets. We conjecture that some of these techniques can be adapted to positive Bernoulli distributions on arbitrary finite alphabets. Notably, Auslander and Dowker proved some 45 years ago a general result on dynamical systems on compact metric spaces equipped with invariant Borel probability measures that, as a special case, identifies a very broad class of transformations (essentially selectors in the vernacular of the present paper) that preserve
$\mu $
-distributed sequences if
$\mu $
is induced by a Bernouilli distribution on
$\Sigma $
, generalizing the work of Wall [Reference Wall55], Furstenberg [Reference Furstenberg23], and others on preservation of normality by various, more restrictive, classes of selectors. Also of interest would be to ascertain whether the ‘if’ in Auslander and Dowker’s work (or, less ambitiously, for more restricted classes of selectors) can be extended to ‘if and only if’.
A different possible thrust is to consider generalizations of Agafonov’s theorem on domains different from infinite sequence over alphabets. However, some results in the—sparse—literature on selection from normal sequence-like objects in other contexts are negative; for example, normality is not preserved by arithmetic progressions (so, probably not by finite-state selectors in any reasonable sense) for continued fraction expansions [Reference Heersink and Vandehey24]. However, very recent work by Bergelson et al has succesfully adapted the classical techniques of Kamae and Weiss [Reference Kamae and Weiss27] to show that certain Følner sequences preserve (the appropriate analog of) normality in cancellative amenable semigroups [Reference Bergelson, Downarowicz and Vandehey7].
Acknowledgement
T. Seiller was partially supported by the ANR ANR-22-CE48-0003-01 project DySCo.
A Appendix. Auxiliary proofs and definitions
A.1 Automata and selectors
The following is a proof of the extension of [Reference Schnorr and Stimm44, Lemma 2.6]. The proof follows the original in most details.
Definition A.1. Let
$G = (V,E)$
be a directed multigraph, and denote by
$\sim \subseteq V \times V$
the equivalence relation such that
$v \sim w$
if and only if there is a directed path from v to w and a directed path from w to v. For every
$v \in V$
, denote by
$[v]_\sim $
the equivalence class containing v. Define the partial order
$<$
on
$V/\!\sim $
by
$\mathcal {V} < \mathcal {W}$
if and only if there are
$v \in \mathcal {V}$
and
$w \in \mathcal {W}$
such that there is a directed path from w to v.
If G has a finite number of nodes,
$<$
is clearly well founded. As
$<$
is clearly also transitive, every
$\mathcal {W} \in V/\!\sim $
satisfies
$\mathcal {W} \geq \mathcal {V}$
for some
$<$
-minimal
$\mathcal {V} \in V/\!\sim $
.
Also observe that every
$<$
-minimal
$\mathcal {V}$
is a recurrent strongly connected component, because (i) it is strongly connected by definition, and (ii)
$<$
-minimality implies that no directed path from any node in
$\mathcal {V}$
can reach a node in a strongly connected component distinct from
$\mathcal {V}$
.
Lemma A.1. Let
$S = (Q,\delta ,q_s,Q_F)$
be a finite automaton over a (possibly infinite) alphabet
$\Sigma $
. Then, there is a word
$w \in \Sigma ^*$
such that, for all states
$q \in Q$
,
$\delta ^*(q,w)$
is a state in a
$<$
-minimal element of
$Q/\!\sim $
.
Proof. Write
$Q = \{q_1,\ldots ,q_m\}$
. We prove by induction on
$i \leq m$
that there is a word
$w_i \in \Sigma ^*$
such that for all
$j \leq i$
,
$\delta ^*(q_j,w_i)$
is a state in a
$<$
-minimal element of
$Q/\!\sim $
.
-
i = 1. Let
$\mathcal {V}$
be a
$<$
-minimal element of
$Q/\!\sim $
such that
$[q_1]_\sim> \mathcal {V}$
. Choose
$q \in Q$
such that
$[q]_\sim = \mathcal {V}$
. Then, there is a directed path from
$q_1$
to q. Let
$w_1$
be the word along that path and observe that
$\delta ^*(q_1,w_1) = q$
. -
i > 1. Let
$\mathcal {V}$
be a
$<$
-minimal element of
$Q/\!\sim $
such that
$\delta ^*(q_{i+1},w_i) \in \mathcal {V}$
, and let
$q \in \mathcal {V}$
, whence there is a directed path from
$\delta ^*(q_{i+1},w_i)$
to q. Let
$w' \in \Sigma ^*$
be the word along that path, whence
$\delta ^*(\delta ^*(q_{i+1},w_i),w') = q$
. Define
$w_{i+1} = w_i \cdot w'$
and observe that
$\delta ^*(q_{i+1},w_{i+1}) = q$
.For
$j \leq i$
, we claim that
$\delta ^*(q_{j},w_{i+1})$
is a state in a
$<$
-minimal element of
$Q/\!\sim $
. For, by the induction hypothesis,
$\delta (q_j,w_i)$
is in a
$<$
-minimal element
$\mathcal {V}_j$
of
$Q/\!\sim $
, and as
$<$
-minimal elements are recurrent strongly connected components, no directed path from
$\delta (q_j,w_i)$
can end in a state outside
$\mathcal {V}_j$
.
Proof of Lemma 2.6
Any
$<$
-minimal element of
$Q/\!\sim $
is recurrent. By Lemma A.1, there is a word w such that from any state
$q \in Q$
,
$\delta ^*(q,w)$
is a state in a recurrent strongly connected component of the automaton. As
$p(a)> 0$
for all
$a \in \Sigma $
,
$\mu _p(w)> 0$
, and as
$\alpha $
is p-distributed, w thus occurs (infinitely often) in
$\alpha $
. After the first occurrence of w, the run of A on
$\alpha $
has entered a strongly recurrent connected component.
A.2 Symbolic dynamical systems
Proof of Proposition 6.1
The two identities
$\mu = \underline {\bar {\mu }}$
and
$\nu = \bar {\underline {\nu }}$
follow directly from the definitions. If
$\mu $
is invariant, then for every cylinder
$[{{w}}]$
, we have
$\bar {\mu }([{{w}}]) = \mu ({w}) = \sum _{a \in \Sigma }\mu ({w} \cdot a) = \sum _{a \in \Sigma }\bar {\mu }([{{w} \cdot a}])$
; from this, and the observation that
$1 = \mu (\unicode{x3bb} ) = \bar {\mu }([{\unicode{x3bb} }]) = \bar {\mu }(\Sigma ^\omega )$
,
$\bar {\mu }$
is a probability measure on
$\Sigma $
with the sigma algebra generated by the cylinder sets. In addition, as
$\mu $
is invariant, we have for any cylinder
$[{{w}}]$
that
$$ \begin{align*} \bar{\mu}(S^{-1}([{w}])) = \bar{\mu}\bigg( \bigcup_{a \in \Sigma} [{a \cdot {w}}] \bigg) = \sum_{a \in \Sigma}\bar{\mu}([{a \cdot {w}}]) = \sum_{a \in \Sigma} \mu(a \cdot {w}) = \mu({w}) = \bar{\mu}([{{w}}]), \end{align*} $$
whence
$\bar {\mu }$
is shift-invariant.
Conversely, if
$\nu $
is a shift-invariant probability measure on
$\Sigma ^\omega $
, we have for any
${w}$
that
$$ \begin{align*} \underline{\nu}({w}) = \nu([{{w}}]) = \nu\bigg( \bigcup_{a \in \Sigma} [{{w} \cdot a}] \bigg) = \sum_{a \in \Sigma} \nu([{{w} \cdot a}]) = \sum_{a \in \Sigma} \underline{\nu}({w} \cdot a) \end{align*} $$
and
$$ \begin{align*} \underline{\nu}({w}) = \nu([{{w}}]) = \nu(S^{-1}([{{w}}])) = \nu\bigg( \bigcup_{a \in \Sigma}[{a \cdot {w}}] \bigg) = \sum_{a \in \Sigma} \nu([{a \cdot {w}}]) = \sum_{a \in \Sigma} \underline{\nu}(a \cdot {w}), \end{align*} $$
showing that
$\underline {\nu }$
is invariant.
Proof of Proposition 6.2
For the first part, we prove (1)
$\Rightarrow $
(2)
$\Rightarrow $
(3)
$\Rightarrow $
(1).
Assume that
$\alpha \in \Sigma ^\omega $
is
$\mu $
-distributed. Observe that every occurrence of a word of the form
$a \cdot {w}$
in
$\alpha $
contains an occurrence of
${w}$
, and hence,
$\#_{{w}}(\alpha \vert _{\leq _n}) \geq \sum _{a \in \Sigma } \#_{a \cdot {w}}(\alpha \vert _{\leq _n})$
. Conversely, for every occurrence of
${w}$
starting at some position
$i \geq 2$
in
$\alpha $
, there is exactly one
$a \in \Sigma $
such that the word
$a \cdot {w}$
occurs at position
$i-1$
, whence
$\#_{{w}}(\alpha \vert _{\leq _n}) \leq 1 + \sum _{a \in \Sigma } \#_{a \cdot {w}}(\alpha \vert _{\leq _n})$
.
Let
$\preceq _\alpha $
be any total ordering on
$\Sigma $
. List the elements of
$\Sigma $
as
$a_1 \preceq _\alpha a_2 \preceq _\alpha a_3 \cdots $
. For any positive integer m and any
$\epsilon> 0$
, choose, by
$\mu $
-distribution of
$\alpha $
, n large enough that
$\vert \#_{{w}}(\alpha \vert _{\leq _n})/n - \mu ({w}) \vert < \epsilon /2$
and
$\vert \#_{a_i \cdot {w}}(\alpha \vert _{\leq _n})/n - \mu ({a_i \cdot w}) \vert < \epsilon /(2m)$
for all
$i \in \{1,\ldots ,m\}$
. Then,
$$ \begin{align*} \mu({w}) + \frac{\epsilon}{2} &\geq \frac{\#_{{w}}(\alpha\vert_{\leq_n})}{n} \geq \sum_{a \in \Sigma} \frac{\#_{a \cdot {w}}(\alpha\vert_{\leq_n})}{n} \geq \sum_{i=1}^m \frac{\#_{a_i \cdot {w}}(\alpha\vert_{\leq_n})}{n} \\ &\geq \sum_{i=1}^m\bigg(\mu(a_i \cdot {w}) - \frac{\epsilon}{2m}\bigg) \end{align*} $$
and hence
$\mu (w) + \epsilon \geq \sum _{i=1}^m \mu (a_i \cdot {w})$
. As this inequality holds for all positive m, and all
$\mu (a_i \cdot w)$
are positive, we have by the monotone convergence theorem that the limit
$\sum _{i=1}^\infty \mu (a_i \cdot (w))$
exists, and thus that
$\mu (w) + \epsilon \geq \sum _{i=1}^\infty \mu (a_i \cdot {w})$
. Conversely, for m, n, and
$\epsilon $
as above, we have
$$ \begin{align*} \mu({w}) - \frac{\epsilon}{2} &\leq \frac{\#_{{w}}(\alpha\vert_{\leq_n})}{n} \leq \frac{1 + \sum_{a \in \Sigma} \#_{a \cdot {w}}(\alpha\vert_{\leq_n})}{n} \\ &\leq \frac{1}{n} + \sum_{i=1}^m \bigg(\mu(a_i \cdot {w}) + \frac{\epsilon}{2m}\bigg) \end{align*} $$
and thus
$\mu ({w}) - \epsilon \leq 1/n + \sum _{i=1}^m \mu (a_i \cdot {w})$
. As n can be taken arbitrarily large, we have
$\mu ({w}) - \epsilon \leq \sum _{i=1}^m \mu (a_i \cdot {w})$
, and we obtain by the same reasoning as above that
$\mu ({w}) - \epsilon \leq \sum _{i=1}^\infty \mu (a_i \cdot {w})$
. Thus,
$\vert \mu ({w}) - \sum _{i=1}^\infty \mu (a_i \cdot {w}) \vert < \epsilon $
, and as
$\epsilon $
was arbitrary, we conclude that
$\mu ({w}) = \sum _{i=1}^\infty \mu (a_i \cdot {w})$
. As all
$\mu (a_i \cdot {w})$
are non-negative, the series
$\sum _{i=1}^\infty \mu (a_i \cdot {w})$
is absolutely convergent whence the ordering of the terms does not affect convergence, and we obtain
$\mu ({w}) = \sum _{a \in \Sigma } \mu (a \cdot {w})$
. By reasoning identical to the preceding, we obtain mutatis mutandis that
$\mu ({w}) = \sum _{a \in \Sigma } \mu ({w} \cdot a)$
, whence
$\mu $
is invariant, as desired.
If
$\mu $
is invariant, then by Proposition 6.1,
$\bar {\mu }$
is a shift-invariant probability measure on
$\Sigma ^\omega $
. If
$\nu $
is a shift-invariant probability measure on
$\Sigma ^\omega $
such that
$\bar {\mu } = \nu $
, then by [Reference Madritsch and Mance33, Main Theorem 2.1], there exists
$\alpha \in \Sigma ^\omega $
generic for
$\bar {\mu }$
, and thus for any admissible
${w} \in \Sigma ^*$
,
$\lim _{n\rightarrow \infty } ({\#_{{w}}(\alpha \vert _{\leq n})}/{n}) = \nu ({w}) = \bar {\mu }([{{w}}]) = \mu ({w})$
. Observe that any inadmissible word
$w = a_1 \cdots a_n$
has
$\prod _{i=1}^n \mu (a_i) = \mu (w) = 0$
, whence
$\mu (a_i) = 0$
for some i, and hence
$\lim _{n\rightarrow \infty } ({\#_{{w}}(\alpha \vert _{\leq n})}/{n}) \leq \lim _{n \rightarrow \infty } ({\#_{a_i}(\alpha \vert _{\leq n})}/{n}) = 0$
. Hence,
$\alpha $
is
$\mu $
-distributed.
For the second part, we prove (1)
$\Rightarrow $
(3)
$\Rightarrow $
(2)
$\Rightarrow $
(1). Assume that
$\alpha $
is generic for
$\nu $
. By construction,
$\underline {\nu }$
is a probability map such that
$\alpha $
is
$\underline {\nu }$
-distributed, and by the first part of the proposition,
$\underline {\nu }$
is invariant, as desired. If
$\underline {\nu }$
is an invariant probability map, then as any measurable A can be written as a disjoint union of cylinder sets, and as we for any cylinder
$[{{w}}]$
have
$S^{-1}([{w}]) = \bigcup _{a \in \Sigma } [{a \cdot {w}}]$
, we obtain
$$ \begin{align*} \nu(S^{-1}([{w}])) = \underline{\nu}\bigg(\bigcup_{a \in \Sigma} [{a \cdot {w}}]\bigg) = \sum_{a \in \Sigma} \underline{\nu}(a \cdot {w}) = \underline{\nu}({w}) = \nu([{w}]), \end{align*} $$
showing that
$\nu $
is shift-invariant. Finally, if
$\nu $
is shift-invariant, it follows from [Reference Madritsch and Mance33, Main Theorem 2.1] that there exists
$\alpha \in \Sigma ^\omega $
generic for
$\nu $
, as desired.
