The Agafonov and Schnorr-Stimm Theorems for Probabilistic Automata

Suppose that $X\in A^{\omega }$ is $\mu$-normal and consider a $\mu$-gambler $𝒢=(Q,A,q_I,\delta ,\gamma )$.

We can assume that the $\mu$-gambler only has one state on which it places a non-trivial bet. Indeed, define for every $q\in Q$ the $\mu$-gambler ${𝒢}^{[q]}=(Q,A,q_I,\delta ,{\gamma }^{[q]})$ where ${\gamma }^{[q]}(q,a)=\gamma (q,a)$ for all $a$ and ${\gamma }^{[q]}(q^{\prime },a)=1$ for $q^{\prime }\ne q$. That is, ${𝒢}^{[q]}$ is the gambler $𝒢$ where all states but state $q$ are neutralized (no bet is placed while on them). By the multiplicative nature of the function $\mathrm{Capital}$, we have for all $n$:

Thus if we can show that all quantities $\mathrm{Capital}({𝒢}^{[q]},X[0,n])$ are bounded, we are done. Let us assume that there is a state $r$ that is the unique state on which $𝒢$ bets. If instead of $𝒢$ we consider the selector $𝒮=(Q,A,q_I,\delta ,\{r\})$ with only $r$ as the selecting state, we know by Agafonov’s theorem for Bernoulli measures (Theorem 6) that the subsequence $Y$ of $X$ selected by $𝒮$ is $\mu$-normal, hence in particular $\mu$-balanced. But this subsequence is precisely the values of $X$ on which $𝒢$ bets!

We can further assume that $Y$ is infinite, otherwise it means that the run of $𝒢$ on $X$ passes by $r$ finitely often, hence $𝒢$ certainly cannot win as other states are not betting states. Now, suppose that at the $n$-th step of the run on $X$ the state $r$ has been visited $k=k(n)$ times. We have

But since $Y$ is $\mu$-normal we have, for every $a$, $\mathrm{NbOcc}(a,Y[0,k])=\mu (a)k+o(k)$. Thus,

or equivalently

(here we assume that all values $\gamma (r,a)$ involved in the product are positive for if not then the capital falls to $0$ and we are done). Since we have ${\sum }_{a\in A}\mu (a)=1$ ($\mu$ being a distribution), we can use the strict concavity of the function $\log$ on $(0,+\mathrm{\infty })$ to apply Jensen’s inequality and get

with strict inequality when not all $\gamma (q,a)$ are equal (which is the case where $𝒢$ makes non-trivial bets). But by the fairness condition, we have ${\sum }_{a\in A}\mu (a)\gamma (r,a)=1$ hence we see that $\log \mathrm{Capital}(𝒢,X[0,n])$ is either $0$ or ultimately negative which either way means that $𝒢$ does not win.

Assume that $X$ is not $\mu$-normal. This means that there is some word $w$ such that $\mathrm{Freq}(w,X[0,n])$ does not converge to $\mu (w)$. Let us assume that $w$ is such a word of minimal length and write $w=ux$ with $u\in A^{\ast }$ and $x\in A$.

Consider the sequence of vectors $f_n$ defined by

or equivalently,

All of these vectors belong to the set $\mathrm{\Gamma }=\{f:A\to [0,1]:{\sum }_{a\in A}f(a)=1\}$. This is a compact set, hence the sequence $f_n$ must have cluster points. By definition of $u$ and $x$, we know that $f_n$ does not converge to $\mu$ because $f_n(x)$ does not converge to $\mu (x)$: Indeed, in the definition of $f_n(x)$, the denominator converges to $\mathrm{Freq}(u,X)$ which by minimality of $w$ is defined and equal to $\mu (u)$, while the numerator is equal to $\mathrm{Freq}(w,X[0,n])$ which by definition of $w$ does not converge to $\mu (w)=\mu (u)\mu (x)$.

Therefore, the sequence $(f_n)$ must have at least one cluster point $\nu$ different from $\mu$. Fix such a cluster point $\nu$.

We now build our gambler $𝒢=(Q,A,q_I,\delta ,\gamma )$. The idea is that the gambler will record the last $|u|$ bits it read and will only place bets when these exactly form the word $u$. Let us thus take $Q=\{q_v:v\in A^{\ast },|v|\le |u|\}$ initial state $q_I=q_{ϵ}$ and define $\delta$ by

Now, define $\gamma (q_v,a)=1$ whenever $v\ne u$ and $\gamma (q_u,a)=\nu (a)/\mu (a)$ for all $a\in A$. Observe that this is a valid $\mu$-gambler as the fairness condition is satisfied: ${\sum }_{a\in A}\nu (a)/\mu (a)\cdot \mu (a)={\sum }_a\nu (a)=1$.

Suppose that after reading $n$ letters of $X$ the state $q_u$ has been visited $k=k(n)$ times. First, observe that $k(n)$ tends to $+\mathrm{\infty }$. Indeed, the state $q_u$ is visited whenever $u$ is seen as a subword of $X$. But we assumed that $u$ appears in $X$ with frequency $\mu (u)$, by minimality of $w$.

Second, unfolding the definition of $f_n$, we have,

This gives

Since $\nu$ is a cluster point of the sequence $f_n$, for any fixed $\epsilon >0$ there are infinitely many $n$ (or $k$) such that

But the term ${\sum }_{a\in A}\nu (a)\log \left(\frac{\nu (a)}{\mu (a)}\right)$ is the relative entropy from $\mu$ to $\nu$ (also known as Kullback-Liebler divergence, see for example [5]) which we denote by ${\mathrm{D}}_{KL}(\nu ||\mu )$. This quantity is non-negative in general and is positive when $\nu \ne \mu$, which is the case here. We have thus established that for any fixed $\epsilon$, there are arbitrarily large $n$ and $k$ such that

Taking any , this shows that

$◀$

Let us note that this last proof actually gives us a finer analysis of normality, in terms of the rate of failure or success of the gambler. This was already observed by Schnorr and Stimm in their seminal paper, where they proved the following.

As a byproduct of our proof of Theorem 7, we have the same dichotomy for positive Bernoulli measures (i.e., Bernoulli measures such that $\mu (a)>0$ for every letter):

Our proof of Theorem 7 almost establishes this, but we do need an additional technical lemma and the block-wise characterization of $\mu$-normality. Let $\mathrm{BFreq}(u,w)$ denote the block frequency of the word $u$ in $w$, defined as the proportion of non-overlapping blocks in $w$ that are equal to $u$. More precisely when $n=|w|$ and $k=|u|$,

For $w\in A^{\ast }$, let ${\mathrm{BFreq}}^{-}(w,X)$, ${\mathrm{BFreq}}^{+}(w,X)$ and $\mathrm{BFreq}(w,X)$ denote the lower, upper and limit block frequency of $w$ in $X$ defined similarly as ${\mathrm{Freq}}^{-}(w,X)$, ${\mathrm{Freq}}^{+}(w,X)$ and $\mathrm{Freq}(w,X)$. A sequence $X$ is $\mu$-block normal if for all words $w\in A^{\ast }$, $\mathrm{BFreq}(w,X)=\mu (w)$. The following was shown by Seiller and Simonsen.

We note that the converse implication also holds.

The above lemmas completes the proof of the following equivalence theorem between $\mu$-normality and $\mu$-block normality.

The proof of Lemma 11 uses a counting trick from the proof of Theorem 3.1 from [8] which in turn is based on the proof of the main theorem in [7].

As in the proof of Theorem 3.1 from [8], for any finite length string $w=a_1{a}_2{a}_3\mathrm{\dots }{a}_k\in A^k$ and large enough $n$,

where $f_p(n)$ are defined as follows:

In the above definition, $S_j$ is the set of strings of the form, $u{a}_1{a}_2\mathrm{\dots }{a}_{k}v$ where $u$ is some string of length $2^{p-2}k-j$ and $v$ is some string of length $2^{p-2}k-k+j$.

Equation 1 shows that the frequency of $w$ in $X[0,n]$ can be written as a sum of different block frequencies. The quantity $f_1(n)$ counts the number of occurrences of $w$ inside disjoint $k$-length blocks in $X[0,n]$, $f_2(n)$ counts the number of occurrences crossing the boundaries of these $k$-blocks, $f_3(n)$ counts those crossing boundaries of $2k$-blocks, and so on. In general, $f_p(n)$ counts the number of occurrences straddling boundaries of disjoint $2^{p-1}k$-length blocks. Each $f_p(n)$ may miss at most $(k-1)$ occurrences of $w$, which are accounted for by the error term.

Since $X$ is $\mu$-block normal,

Now, when $p\le 1+\lfloor {\log }_2(\frac{n}{k})\rfloor$,

Since ${⟨{\sum }_{i=1}^m{f}_i(n)⟩}_{m\in \mathbb{N}}$ is uniformly convergent, we have

Therefore from (1),

Hence, $X$ is $\mu$-normal. $◀$

We require the following technical lemma in the proof of Theorem 9.

On running an automaton upon a normal sequence, starting from any state, a strongly connected component must be reached in finitely many steps. Similar to [10], let us consider the Markov chain corresponding to the $|Q|\times |Q|$ stochastic matrix $𝐏$ where,

The proof follows using the Ergodic Theorem for Markov chains and the same steps in the proof of Lemma 4.5 from [9] by replacing the uniform measure with the positive Bernoulli measure induced by $\mu$. We note that this line of proof uses $\mu$-block normality, which is equivalent to $\mu$-normality (Theorem 12). $◀$

In part $(i)\Rightarrow (ii)$ of our proof of Theorem 7, we showed that on a given state $r$, either $r$ is not a betting state ($\gamma$ is the constant $1$ on this state) or it is and then the gambler loses money exponentially fast in the number of times this state is visited, the exponent being ${\alpha }_r={\sum }_{a\in A}\mu (a)\cdot \log \gamma (r,a)$ which we proved to be negative. By Lemma 13, betting states are either visited finitely often or with positive asymptotic density. If they are all visited finitely often, the capital stabilizes after the last bet is made. Otherwise, if betting states $r$ are visited with frequency ${\pi }_r$ and at least one ${\pi }_r$ is positive, then the gambler loses at an exponential rate, where the exponent is ${\sum }_r{\pi }_r{\alpha }_r$.

In part $(ii)\Rightarrow (i)$, under the assumption of non-$\mu$-normality of $X$, we built a gambler $𝒢$ satisfying the following: for any fixed $\epsilon$, there are arbitrarily large $n$ and $k$ such that $\log \mathrm{Capital}(𝒢,X[0,n])\ge k({\mathrm{D}}_{KL}(\nu ||\mu )-\epsilon )$. Here, $k$ is the number of visits to a state $q_u$. In the proof of Theorem 7 part $(ii)$, this state $q_u$ is visited with frequency $\mu (u)$ for large enough $n$. Hence the gambler has an “infinitely often” exponential rate of success with exponent $\mu (u)D_{KL}(\nu ||\mu )$. $◀$

While it is a bit easier to prove this lemma for block-normality, we prefer a more direct proof which does not rely on the equivalence between normality and block-normality.

Let $w=u\otimes v$ be a non-empty word over ${(A\times B)}^{\ast }$. Let $N$ be a large integer. We split $X\otimes Y$ into blocks of length $N$ :

with $|X_i|=|Y_i|=N$, for all $i\ge 1$. Introduce the random variables ${(B_i)}_{i\ge 1}$ which count the number of occurrences of $u\otimes v$ in each block:

For every integer $n\in \mathbb{N}$, within $(X\otimes Y)[0,n]$ there are $\lfloor n/N\rfloor$ complete blocks. Some occurrences of $u\otimes v$ in $(X\otimes Y)[0,n]$ do occur inside a block $X_i\otimes Y_i$ while some other do not because they overlap two contiguous blocks. There can be at most $|w|$ such overlapping occurrences between two given blocks. That observation leads to two ways to count the number of occurrences of $u\otimes v$: the exact way $C_n$ and the $N$-block way $C_{n,N}^{\prime }$, two random variables satisfying:

Let us focus on $C_{n,N}^{\prime }$ first. The variables $B_i$ can be grouped into ${|A|}^N$ different buckets, with respect to the corresponding value of $X_i$. For every $x\in A^N$, set $I_n(x)=\{1\le i\le \lfloor n/N\rfloor \mid X_i=x\}$, which is non-empty for $n$ large enough, since $X$ is normal. The random variables $(X_i\otimes Y_i)$ are mutually independent, and so are the random variables ${(B_i)}_{i\ge 1}$. Moreover, for a fixed $x\in A^N$, the random variables ${(B_i)}_{i\in I_{\mathrm{\infty }}(x)}$ are distributed identically, denote by ${\xi }_N(x)$ the corresponding probability distribution on $0\mathrm{\dots }N-|w|+1$. Then $𝔼\left[{\xi }_N(x)\right]$ measures the expected number of occurrences of $u\otimes v$ in a sequence where the left part is fixed, equal to $x$, and the right part is independently generated according to $\nu$. Thus

According to the Law of Large Numbers, $\frac{1}{|I_n(x)|}{\sum }_{i\in I_n(x)}{B}_i{\to }_n\mathrm{NbOcc}(u,x)\cdot \nu (v)$. Since $X$ is normal, every word $x\in A^N$ occurs with frequency $\mu (x)$ in $X_1,X_2,\mathrm{\dots }$ thus, almost-surely,

Since $X$ is normal, the right part in (3) converges to $\mu (u)\cdot \nu (v)$ when $N$ grows large. Using (2), we get the desired result:

$◀$

Suppose $Z\in {(A\times B)}^{\omega }$ is $\mu \otimes \nu$-normal. We only need to show that ${\pi }_0(Z)$ is $\mu$-normal, the proof of the $\nu$-normality of ${\pi }_1(Z)$ is the same by symmetry. Let $w\in A^n$. We have

which, by $\mu \otimes \nu$-normality of $Z$, implies

The same holds for ${\mathrm{Freq}}^{-}(w,{\pi }_0(Z))$, hence we have proven that $\mathrm{Freq}(w,{\pi }_0(Z))=\mu (w)$, which is what we wanted. $◀$

We are now ready to prove Agafonov’s theorem for PFAs.

Since deterministic selectors (for which we already have Agafonov’s theorem) are a subset of the probabilistic ones, all that is left to prove is $(i)\Rightarrow (iii)$.

Let $𝒮=(Q,A,q_I,\delta ,S)$ be a probabilistic selector. Recall that each transition $\delta (q,a)$ (where $q\in Q$ and $a\in A$) is some probability distribution over $Q$. Consider the set $𝒯$ of all functions $Q\times A\to Q$. We can put a distribution $\tau$ over $𝒯$ such that if $t$ is chosen according to $\tau$, for every $(q,a)$, the marginal distribution of $t(q,a)$ is $\delta (q,a)$. An easy way to do this is to take $\tau ={⨂}_{(q,a)\in Q\times A}\delta (q,a)$.

This construction means that, for a fixed sequence $X\in A^{\omega }$, an equivalent way to simulate the probabilistic run of $𝒮$ on $X$ is, every time we are in a state $q$ and read a letter $a$, to pick $t$ at random according to $\tau$ and move to state $t(q,a)$. But $𝒯$ is a finite set and $\tau$ a Bernoulli measure over it. This Bernoulli measure might not be positive. If it is not, we simply remove from $𝒯$ all functions whose $\tau$-probability is $0$. Reformulating slightly, yet another equivalent way to simulate the run of $𝒮$ over $X$ is to do the following:

1. 1.

   First choose $T\in {𝒯}^{\omega }$ at random with respect to the Bernoulli measure $\tau$.

2. 2.

   Then run on the sequence $X\otimes T$ the deterministic selector $\widehat{𝒮}$ whose set of states is $Q$ and transition $\widehat{\delta }$ is defined by $\widehat{\delta }(q,(a,t))=t(q,a)$.

Now, the two following random variables have the same distribution:

• $\mathrm{■}$

  The subsequence $Y$ of $X$ selected by $𝒮$.

• $\mathrm{■}$

  The sequence ${\pi }_0(\widehat{Y})$, where $\widehat{Y}$ is the subsequence of $X\otimes T$ selected by $\widehat{𝒮}$ when $T$ is chosen randomly according to $\tau$.

Since $X$ is $\mu$-normal, by Lemma 14, $X\otimes T$ is $\mu \otimes \tau$-normal $\tau$-almost surely. Thus, by Agafonov’s theorem for deterministic selectors and Bernoulli measures (Theorem 6), almost surely, the subsequence $\widehat{Y}$ selected by $\widehat{𝒮}$ is $\mu \otimes \tau$-normal. Finally, by Lemma 15, this implies that almost surely, the subsequence ${\pi }_0(\widehat{Y})$ of $X$ is $\mu$-normal. This concludes the proof. $◀$