Infinite Excess Entropy Processes with Countable-State Generators

Abstract

We present two examples of finite-alphabet, infinite excess entropy processes generated by stationary hidden Markov models (HMMs) with countable state sets. The first, simpler example is not ergodic, but the second is. These are the first explicit constructions of processes of this type. 02.50.-r 89.70.+c 05.45.Tp 02.50.Ey

1. Introduction

For a stationary process (X_t) the excess entropy E is the mutual information between the infinite past X⃖ = . . . X₋₂X₋₁ and the infinite future X⃗ = X₀X₁ . . .. It has a long history and is widely employed as a measure of correlation and complexity in a variety of fields, from ergodic theory and dynamical systems to neuroscience and linguistics [1–6]. For a review the reader is referred to [7].

An important question in classifying a given process is whether the excess entropy is finite or infinite. In the former case the process is said to be finitary, and in the latter infinitary.

Over a finite alphabet, most of the commonly studied, simple process types are always finitary, including all independent identically distributed (IID) processes, finite-order Markov processes, and processes with finite-state hidden Markov model (HMM) presentations. However, there are also well known examples of finite-alphabet, infinitary processes. For instance, the symbolic dynamics at the onset of chaos in the logistic map and similar dynamical systems [7] and the stationary representation of the binary Fibonacci sequence [8] are both infinitary.

These latter processes, though, only admit stationary HMM presentations with uncountable state sets. Indeed, one can show that any process generated by a stationary, countable-state HMM either has positive entropy rate or consists entirely of periodic sequences, which these do not. Versions of the Santa Fe Process introduced in [6] are finite-alphabet, infinitary processes with positive entropy rate. However, they were not constructed directly as hidden Markov processes, and it seems unlikely that they should have any stationary, countable-state presentations either.

Here, we present two examples of stationary, countable-state HMMs that do generate finite-alphabet, infinitary processes. To the best of our knowledge, these are the first explicit constructions of this type in the literature. Although, subsequent to our release of the earlier version of the present work [9], two additional examples were given in [10].

Our first example is nonergodic, and the information conveyed from the past to the future essentially consists of the ergodic component along a given realization. This example is straightforward to construct and, though previously unpublished, others are likely aware of it or similar constructions. The second, ergodic example, though, is more involved, and both its structure and properties are novel.

To put these contributions in perspective, we note that any stationary, finite-alphabet process may be trivially presented by a stationary hidden Markov model with an uncountable state set, in which each infinite history ⃖ corresponds to a single state. Thus, it is clear that stationary HMMs with uncountable state sets can generate finite-alphabet, infinitary processes. In contrast, for any finite-state HMM E is always finite—bounded by the logarithm of the number of states. The case of countable-state HMMs lies in-between the finite-state and uncountable-state cases, and it was previously not demonstrated whether it is possible to have countable-state, stationary HMMs that generate infinitary, finite-alphabet processes and, in particular, ergodic ones.

2. Background

2.1. Excess Entropy

We denote by H [X] the Shannon entropy in a random variable X, by H [X|Y ] the conditional entropy in X given Y, and by I [X; Y ] the mutual information between random variables X and Y. For definitions of these information theoretic quantities, as well as the definitions of stationarity and ergodicity for a stochastic process (X_t), the reader is referred to [11].

Definition 1

For a stationary, finite-alphabet process (X_t)_t∈ℤ the excess entropy E is the mutual information between the infinite past X⃖ = . . . X₋₂X₋₁ and the infinite future X⃗ = X₀X₁ . . . :

$$\mathbf{E}=I[\overleftarrow{X};\overrightarrow{X}]=\underset{t\to \infty }{\text{lim}}\hspace{0.17em}I[{\overleftarrow{X}}^t;{\overrightarrow{X}}^t],$$

(1)

where X⃖^t = X_−t . . . X₋₁ and X⃗^t = X₀ . . . X_t−1 are the length-t past and future, respectively.

As noted in [7,12] this quantity, E, may also be expressed alternatively as:

$$\mathbf{E}=\underset{t\to \infty }{\text{lim}}\left(H[{\overrightarrow{X}}^t]-h·t\right),$$

(2)

where h is the process entropy rate:

$$h=\underset{t\to \infty }{\text{lim}}\frac{H[{\overrightarrow{X}}^t]}{t}=\underset{t\to \infty }{\text{lim}}\hspace{0.17em}H[X_t\mid {\overrightarrow{X}}^t].$$

(3)

That is, the excess entropy E is the asymptotic amount of entropy (information) in length-t blocks of random variables beyond that explained by the entropy rate. The excess entropy derives its name from this latter formulation. It is also this formulation that we use to establish that the process of Section 3.1 is infinitary.

Expanding the block entropy H [X⃗^t] in Equation (2) with the chain rule and recombining terms gives another important formulation [7]:

$$\mathbf{E}=\sum _{t=1}^{\infty }(h(t)-h),$$

(4)

where h(t) is the length-t entropy-rate approximation:

$$h(t)=H[X_{t-1}\mid {\overrightarrow{X}}^{t-1}],$$

(5)

the conditional entropy in the t-th symbol given the previous t – 1 symbols. This final formulation will be used to establish that the process of Section 3.2 is infinitary.

2.2. Hidden Markov Models

There are two primary types of hidden Markov models: edge-emitting (or Mealy) and state-emitting (or Moore). We work with the former edge-emitting type, but the two are equivalent in that any model of one type with a finite output alphabet may be converted to a model of the other type without changing the cardinality of the state set by more than a constant factor—the alphabet size. Thus, for our purposes, Mealy HMMs are sufficiently general. We also consider only stationary HMMs with finite output alphabets and countable state sets.

Definition 2

A stationary, edge-emitting, countable-state, finite-alphabet hidden Markov model (hereafter referred to simply as a countable-state HMM) is a 4-tuple ( , , {T^(x)}, π) where:

(1)

is a countable set of states.

(2)

is a finite alphabet of output symbols.

(3)

T_(x), x ∈ , are symbol labeled transition matrices whose sum T = ∑_x∈ T^(x) is stochastic.$T_{\sigma {\sigma }^{\prime }}^{(x)}$ is the probability that state σ transitions to state σ′ on symbol x.

(4)

π is a stationary distribution for the underlying Markov chain over states with transition matrix T. That is, π satisfies π = πT.

Remarks

(1)

“Countable” in Property 1 means either finite or countably infinite. If the state set is finite, we also refer to the HMM as finite-state.

(2)

We do not assume, in general, that the underlying Markov chain over states with transition matrix T is irreducible. Thus, even in the case that is finite, the stationary distribution π is not necessarily uniquely defined by the matrix T and is, therefore, specified separately.

Visually, a hidden Markov model may be depicted as a directed graph with labeled edges. The vertices are the states σ ∈ and, for all σ, σ′ ∈ with $T_{\sigma {\sigma }^{\prime }}^{(x)}>0$ , there is a directed edge from state σ to state σ′ labeled p|x for the symbol x and transition probability $p=T_{\sigma {\sigma }^{\prime }}^{(x)}$. These probabilities are normalized so that the sum of probabilities on all outgoing edges from each state is 1. An example is given in Figure 1.

The operation of a HMM may be thought of as a weighted random walk on the associated graph. From the current state σ the next state σ′ is determined by following an outgoing edge from σ chosen according to the edge probabilities (or weights). During the transition, the HMM also outputs the symbol x labeling this edge.

We denote the state at time t by S_t and the t-th symbol by X_t, so that symbol X_t is generated upon the transition from state S_t to state S_t+1. The state sequence (S_t) is simply a Markov chain with transition matrix T. However, we are interested not simply in this sequence of states, but also in the associated sequence of output symbols (X_t) that are generated by reading the labels off the edges as they are followed. The interpretation is that an observer of the HMM may directly observe this sequence of output symbols, but not the hidden internal states. Alternatively, one may consider the Markov chain over edges (E_t), of which the observed symbol sequence (X_t) is simply a projection.

In either case, the process (X_t) generated by the HMM ( , , {T^(x)}, π) is defined as the output sequence of edge symbols, which results from running the Markov chain over states according to the stationary law with marginals ℙ(S₀) = ℙ(S_t) = π. It is easy to verify that this process is itself stationary, with word probabilities given by:

$$\mathbb{P}(w)={\Vert \pi T^{(w)}\Vert }_1,$$

(6)

where for a given word w = w₁...w_n ∈ ^*, T^(w) is the word transition matrix T^(w) = T^(w₁) · · · T^(w_n).

Remark

Even for a nonstationary HMM ( , , {T^(x)}, ρ), where the state distribution ρ is not stationary, one may always define a one-sided process (X_t)_t≥0 with marginals given by:

$$\mathbb{P}({\overrightarrow{X}}^{\mid w\mid }=w)={\Vert \rho T^{(w)}\Vert }_1.$$

(7)

Furthermore, though the state sequence (S_t)_t≥0 will not be a stationary process if ρ is not a stationary distribution for T, the output sequence (X_t)_t≥0 may still be stationary. In fact, as shown in [12] (Example 2.9), any one-sided process over a finite alphabet , stationary or not, may be represented by a countable-state, nonstationary HMM in which the states correspond to finite-length words in ^*, of which there are only countably many. By stationarity, a one-sided stationary process generated by such a nonstationary HMM can be uniquely extended to a two-sided stationary process. So, in a sense, any two-sided stationary process (X_t)_t∈ℤ can be said to be generated by a nonstationary, countable-state HMM. Though, this is a slightly unnatural interpretation of process generation in that the two-sided process (X_t)_t∈ℤ is not directly that obtained by reading symbols off the edges of the HMM as it runs along transitioning between states in bi-infinite time. In either case, the space of stationary, finite-alphabet processes generated by nonstationary, countable-state HMMs is too large: it includes all stationary, finite-alphabet processes. Due to this, we restrict to the case of stationary HMMs where both the state sequence (S_t) and output sequence (X_t) are stationary processes, and henceforth use the term HMM implicitly to mean stationary HMM. Clearly, if one allows finite-alphabet processes generated by nonstationary, countable-state HMMs there are infinitary examples.

We consider now an important property known as unifilarity. This property is useful in that many quantities are analytically computable only for unifilar HMMs. In particular, for unifilar HMMs the entropy rate h is often directly computable, unlike in the nonunifilar case. Both of the examples constructed in Section 3 are unifilar, as is the Even Process HMM of Figure 1.

Definition 3

A HMM ( , , {T^(x)}, π) is unifilar if for each σ ∈ and x ∈ there is at most one outgoing edge from state σ labeled with symbol x in the associated graph G.

It is well known that for any finite-state, unifilar HMM the entropy rate in the output process (X_t) is simply the conditional entropy in the next symbol given the current state:

$$h=H[X_0\mid S_0]=\sum _{\sigma \in \mathcal{S}}{\pi }_{\sigma }{h}_{\sigma },$$

(8)

where π_σ is the stationary probability of state σ and h_σ = H [X₀|S₀ = σ] is the conditional entropy in the next symbol given that the current state is σ.

We are unaware, though, of any proof that this is generally true for countable-state HMMs. If the entropy in the stationary distribution H [π] is finite, then a proof along the lines given in [13] carries through to the countable-state case and Equation (8) still holds. However, countable-state HMMs may sometimes have H [π] = ∞. Furthermore, it can be shown [12] that the excess entropy E is always bounded above by H [π]. So, for the infinitary process of Section 3.2 we need slightly more than unifilarity to establish the value of h. To this end, we consider a property known as exactness [14].

Definition 4

A HMM is said to be exact if for a.e. infinite future ⃗ = x₀x₁... generated by the HMM an observer synchronizes to the internal state after a finite time. That is, for a.e. ⃗ there exists t ∈ ℕ such that H [S_t|X⃗^t = ⃗⃗ ^t] = 0, where ⃗^t = x₀x₁...x_t−1 denotes the the first t symbols of a given ⃗.

In the appendix we prove the following proposition.

Proposition 1

For any countable-state, exact, unifilar HMM the entropy rate is given by the standard formula of Equation (8).

The HMM constructed in Section 3.2 is both exact and unifilar, so Proposition 1 applies. Using this explicit formula for h, we will show that $\mathbf{E}={\sum }_{t=1}^{\infty }(h(t)-h)$ is infinite.

3. Constructions

We now present the two constructions of (stationary) countable-state HMMs that generate infinitary processes. In the first example the output process is not ergodic, but in the second it is.

3.1. Heavy-Tailed Periodic Mixture: An infinitary nonergodic process with a countable-state presentation

Figure 2 depicts a countable-state HMM M, for a nonergodic infinitary process ℘. The machine M consists of a countable collection of disjoint strongly connected subcomponents M_i, i ≥ 2. For each i, the component M_i generates the periodic process ℘_i consisting of i – 1 1s followed by a 0. The weighting (μ₂, μ₃, ..., ) over components is taken as a heavy-tailed distribution with infinite entropy. For this reason, we refer to the process M generates as the Heavy-Tailed Periodic Mixture (HPM) process.

Intuitively, the information transmitted from the past to the future for the HPM Process is the ergodic component i along with the phase of the period-i process ℘_i in this component. This is more information than simply the ergodic component i, which is itself an infinite amount of information: H [(μ₂, μ₃, ..., )] = ∞. Hence, E should be infinite. This intuition can be made precise using the ergodic decomposition theorem of Debowski [15], but we present a more direct proof here.

Proposition 2

The HPM Process has infinite excess entropy.

Proof

For the HPM Process ℘ we will show that (i) lim_t→∞ H [X⃗^t] = ∞and (ii) h = 0. The conclusion then follows immediately from Equation (2). To this end, we define sets:

$$\begin{array}{l}{W}_{i,t}=\{w:\mid w\mid =t\hspace{0.17em}\text{and\hspace{0.17em}}w\hspace{0.17em}\text{is\hspace{0.17em}in\hspace{0.17em}the\hspace{0.17em}support\hspace{0.17em}of\hspace{0.17em}process}\hspace{0.17em}{\mathcal{P}}_i\},\\ U_t=\underset{2\le i\le t/2}{\cup }{W}_{i,t},\hspace{0.17em}\text{and}\\ V_t=\underset{i>t/2}{\cup }{W}_{i,t}.\end{array}$$

Note that any word w ∈ W_i,t with i ≤ t/2 contains at least two 0s. Therefore:

(1)

No two distinct states σ_ij and σ_ij′ with i ≤ t/2 generate the same length t word.

(2)

The sets W_i,t, i ≤ t/2, are disjoint from both each other and V_t.

It follows that each word w ∈ W_i,t, with i ≤ t/2, can only be generated from a single state σ_ij of the HMM and has probability:

$$\begin{array}{l}\mathbb{P}(w)=\mathbb{P}({\overrightarrow{X}}^t=w)\\ =\mathbb{P}(S_0={\sigma }_{ij})·\mathbb{P}({\overrightarrow{X}}^t=w\mid S_0={\sigma }_{ij})\\ ={\pi }_{ij}·1\\ =C/(i^2\hspace{0.17em}{\text{log}}^2\hspace{0.17em}i).\end{array}$$

(9)

Hence, for any fixed t:

$$\begin{array}{l}H[{\overrightarrow{X}}^t]=\sum _{\mid w\mid =t}\mathbb{P}(w)\hspace{0.17em}\text{log\hspace{0.17em}}\left(\frac{1}{\mathbb{P}(w)}\right)\\ \ge \sum _{i=2}^{\lfloor t/2\rfloor }\sum _{w\in W_{i,t}}\frac{C}{i^2\hspace{0.17em}{\text{log}}^2(i)}\text{log\hspace{0.17em}}\left(\frac{i^2\hspace{0.17em}{\text{log}}^2(i)}{C}\right)\\ =\sum _{i=2}^{\lfloor t/2\rfloor }\frac{C}{i^2\hspace{0.17em}{\text{log}}^2(i)}\text{log\hspace{0.17em}}\left(\frac{i^2\hspace{0.17em}{\text{log}}^2(i)}{C}\right),\end{array}$$

so:

$$\underset{t\to \infty }{\text{lim}}\hspace{0.17em}H[{\overrightarrow{X}}^t]\ge \sum _{i=2}^{\infty }\frac{C}{i^2\hspace{0.17em}{\text{log}}^2(i)}\text{log\hspace{0.17em}}\left(\frac{i^2\hspace{0.17em}{\text{log}}^2(i)}{C}\right)=\infty ,$$

(10)

which proves Claim (i). Now, to prove Claim (ii) consider the quantity:

$$\begin{array}{l}h(t+1)=H[X_t\mid {\overrightarrow{X}}^t]\\ =\sum _{w\in U_t}\mathbb{P}(w)·H[X_t\mid {\overrightarrow{X}}^t=w]+\sum _{w\in V_t}\mathbb{P}(w)·H[X_t\mid {\overrightarrow{X}}^t=w].\end{array}$$

(11)

On the one hand, for w ∈ U_t, H [X_t|X⃗^t = w] = 0 since the current state and, hence, entire future are completely determined by any word w ∈ U_t. On the other hand, for w ∈ V_t, H [X_t|X⃗^t = w] ≤ 1 since the alphabet is binary. Moreover, the combined probability of all words in the set V_t is simply the probability of starting in some component M_i with i > t/2: ℙ(V_t) = ∑_i>t/2 μ_i. Thus, by Equation (11)h(t + 1) ≤ ∑ _i>t/2 μ_i. Since ∑_i μ_i converges, it follows that h(t) ↘ 0, which verifies Claim (ii).

3.2. Branching Copy Process: An infinitary ergodic process with a countable-state presentation

Figure 3 depicts a countable-state HMM M for the ergodic, infinitary Branching Copy Process. Essentially, the machine M consists of a binary tree with loop backs to the root node. From the root a path is chosen down the tree with each left-right (or 0–1) choice equally likely. But, at each step there is also a chance of turning back towards the root. The path back is a not a single step, however. It has length equal to the number of steps taken down the tree before returning back, and copies the path taken down symbol-wise with 0 s replaced by 2 s and 1 s replaced by 3 s. There is also a high self-loop probability at the root node on symbol 4, so some number of 4 s will normally be generated after returning to the root node before preceding again down the tree. The process generated by this machine is referred to as the Branching Copy (BC) Process, because the branch taken down the tree is copied on the loop back to the root.

By inspection we see that the machine is unifilar with synchronizing word w = 4, i.e., H [S₁|X₀ = 4] = 0. Since the underlying Markov chain over states (S_t) is positive recurrent, the state sequence (S_t) and symbol sequence (X_t) are both ergodic. Thus, a.e. infinite future ⃗ contains a 4, so the machine is exact. Therefore, Proposition 1 may be applied, and we know the entropy rate h is given by the standard formula of Equation (8): h = ∑_σ π_σh_σ. Since ℙ(S_t = σ) = π_σ for any t ∈ ℕ, we may alternatively represent this entropy rate as:

$$\begin{array}{l}h=\sum _{\sigma }\left(\sum _{w\in {\mathcal{L}}_t}\mathbb{P}(w)\phi {(w)}_{\sigma }\right)\hspace{0.17em}{h}_{\sigma }\\ =\sum _{w\in {\mathcal{L}}_t}\mathbb{P}(w)\hspace{0.17em}\left(\sum _{\sigma }\phi {(w)}_{\sigma }{h}_{\sigma }\right)\\ =\sum _{w\in {\mathcal{L}}_t}\mathbb{P}(w){\tilde{h}}_w,\end{array}$$

(12)

where $ℒ$_t = {w : |w| = t, ℙ(w) > 0} is the set of length t words in the process language $ℒ$, φ(w) is the conditional state distribution induced by the word w (i.e., φ(w)_σ = ℙ(S_t = σ|X⃗^t = w)), and h̃_w = ∑_σ φ(w)_σh_σ is the φ(w)-weighted average entropy in the next symbol given knowledge of the current state σ. Similarly, for any t ∈ ℕ the entropy-rate approximation h(t + 1) may be expressed as:

$$h(t+1)=H[X_t\mid {\overrightarrow{X}}^t]=\sum _{w\in {\mathcal{L}}_t}\mathbb{P}(w)h_w,$$

(13)

where h_w = H [X_t|X⃗^t = w] is the entropy in the next symbol after observing the word w. Combining Equations (12) and (13) we have for any t ∈ ℕ:

$$h(t+1)-h=\sum _{w\in {\mathcal{L}}_t}\mathbb{P}(w)\hspace{0.17em}(h_w-{\tilde{h}}_w).$$

(14)

As we will show in Claim 6, concavity of the entropy function implies the quantity h_w – h̃_w is always nonnegative. Furthermore, in Claim 5 we will show that h_w–h̃_w is always bounded below by some fixed positive constant for any word w consisting entirely of 2s and 3s. Also, in Claim 3 we will show that ℙ(W_t) scales as 1/t, where W_t is the set of length-t words consisting entirely of 2s and 3s. Combining these results it follows that h(t + 1) – h ≥̃ 1/t and, hence, the sum $\mathbf{E}={\sum }_{t=1}^{\infty }(h(t)-h)$ is infinite.

A more detailed analysis with the claims and their proofs is given below. In this we will use the following notation:

• ℙ_σ(·) = ℙ(·|S₀ = σ),

• V_t = {w ∈ $ℒ$_t : w contains only 0s and 1s} and W_t = {w ∈ $ℒ$_t : w contains only 2s and 3s},

• ${\pi }_{ij}^k=\mathbb{P}({\sigma }_{ij}^k)$ is the stationary probability of state ${\sigma }_{ij}^k$,

• $R_{ij}=\{{\sigma }_{ij}^1,{\sigma }_{ij}^2,\dots ,{\sigma }_{ij}^i\}$, and

• ${\pi }_{ij}={\sum }_{k=1}^i{\pi }_{ij}^k$ and ${\pi }_i^1={\sum }_{j=1}^{2^i}{\pi }_{ij}^1$.

Note that:

$${\mathbb{P}}_{{\sigma }_{01}^1}({\overrightarrow{X}}^t\in V_t)=\frac{1-p_0}{t^2},\hspace{0.17em}\text{for\hspace{0.17em}all\hspace{0.17em}}t\ge 1,$$

(15)

and:

$$p_i=\frac{2i+1}{{(i+1)}^2}\le \frac{2}{i},\hspace{0.17em}\text{for\hspace{0.17em}all\hspace{0.17em}}i\ge 1.$$

(16)

These facts will be used in the proof of Claim 1.

Claim 1

The underlying Markov chain over states for the HMM is positive recurrent.

Proof

Let ${\tau }_{{\sigma }_{01}^1}=\text{min}\{t>0:S_t={\sigma }_{01}^1\}$ be the first return time to state ${\sigma }_{01}^1$. Then, by continuity:

$$\begin{array}{l}{\mathbb{P}}_{{\sigma }_{01}^1}({\tau }_{{\sigma }_{01}^1}=\infty )=\underset{t\to \infty }{\text{lim}}{\mathbb{P}}_{{\sigma }_{01}^1}({\tau }_{{\sigma }_{01}^1}>2t)\\ =\underset{t\to \infty }{\text{lim}}{\mathbb{P}}_{{\sigma }_{01}^1}({\overrightarrow{X}}^{t+1}\in V_{t+1})\\ =\underset{t\to \infty }{\text{lim}}\frac{1-p_0}{{(t+1)}^2}\\ =0.\end{array}$$

Hence, the Markov chain is recurrent and we have:

$$\begin{array}{l}{\mathbb{E}}_{{\sigma }_{01}^1}({\tau }_{{\sigma }_{01}^1})=\sum _{t=1}^{\infty }{\mathbb{P}}_{{\sigma }_{01}^1}({\tau }_{{\sigma }_{01}^1}=t)·t\\ =p_0·1+\sum _{t=1}^{\infty }{\mathbb{P}}_{{\sigma }_{01}^1}({\tau }_{{\sigma }_{01}^1}=2t)·2t\\ =p_0+\sum _{t=1}^{\infty }{\mathbb{P}}_{{\sigma }_{01}^1}({\overrightarrow{X}}^t\in V_t)·p_t·2t\\ \le p_0+\sum _{t=1}^{\infty }\frac{1-p_0}{t^2}·\frac{2}{t}·2t\\ <\infty ,\end{array}$$

from which it follows that the chain is also positive recurrent. Note that the topology of the chain implies the first return time may not be an odd integer greater than 1.

Claim 2

The stationary distribution π has:

$${\pi }_{ij}^1=\frac{C}{i^2·2^i},\mathrm{\hspace{0.17em} }i\ge 1,\hspace{0.17em}1\le j\le 2^i,$$

(17)

$${\pi }_{ij}^k=\frac{C}{i^2·2^i}·\frac{2i+1}{{(i+1)}^2},\mathrm{\hspace{0.17em} }i\ge 2,\mathrm{\hspace{0.17em} }1\le j\le 2^i,2\le k\le i,$$

(18)

where$C={\pi }_{01}^1(1-p_0)$.

Proof

Existence of a unique stationary distribution π is guaranteed by Claim 1. Given this, clearly ${\pi }_1^1={\pi }_{01}^1(1-p_0)$. Similarly, for i ≥ 1, ${\pi }_{i+1}^1={\pi }_i^1(1-p_i)={\pi }_i^1\frac{i^2}{{(i+1)}^2}$, from which it follows by induction that ${\pi }_i^1={\pi }_{01}^1(1-p_0)/i^2$, for all i ≥ 1. By symmetry ${\pi }_{ij}^1={\pi }_i^1/2^i$ for each i ∈ ℕ and 1 ≤ j ≤ 2ⁱ. Therefore, for each i ∈ ℕ, 1 ≤ j ≤ 2ⁱ we have ${\pi }_{ij}^1={\pi }_{01}^1(1-p_0)/(i^2·2^i)=C/(i^2·2^i)$ as was claimed. Moreover, for i ≥ 2, ${\pi }_{ij}^2={\pi }_{ij}^1·p_i={\pi }_{ij}^1·\frac{2i+1}{{(i+1)}^2}$. Combining with the expression for ${\pi }_{ij}^1$ gives ${\pi }_{ij}^2=\frac{C}{i^2·2^i}·\frac{2i+1}{{(i+1)}^2}$. By induction, ${\pi }_{ij}^2={\pi }_{ij}^3=\dots ={\pi }_{ij}^i$, so this completes the proof.

Note that for all i ≥ 1 and 1 ≤ j ≤ 2ⁱ:

$${\pi }_{ij}=\frac{C}{2^i·i^2}+(i-1)\frac{C}{2^i·i^2}·\frac{2i+1}{{(i+1)}^2}\ge \frac{C}{2^i·i^2},\hspace{0.17em}\text{and}$$

(19)

$${\pi }_{ij}=\frac{C}{2^i·i^2}+(i-1)\frac{C}{2^i·i^2}·\frac{2i+1}{{(i+1)}^2}\le \frac{3C}{2^i·i^2}.$$

(20)

Also note that for any t ∈ ℕ and i ≥ 2t we have for each 1 ≤ j ≤ 2ⁱ:

(1)

$\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0={\sigma }_{ij}^k)=1$, for 2 ≤ k ≤ ⌈i/2⌉ + 1.

(2)

$\left({\sum }_{k=2}^i{\pi }_{ij}^k\right)/{\pi }_{ij}\ge 1/3$ and $\mid \{k:2\le k\le \lceil i/2\rceil +1\}\mid \ge \frac{1}{2}·\mid \{k:2\le k\le i\}\mid$. Hence, $\left({\sum }_{k=2}^{\lceil i/2\rceil +1}{\pi }_{ij}^k\right)/{\pi }_{ij}\ge 1/6$.

Therefore, for each t ∈ ℕ:

$$\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0\in R_{ij})\ge 1/6,\hspace{0.17em}\text{for\hspace{0.17em}all\hspace{0.17em}}i\ge 2t\hspace{0.17em}\text{and\hspace{0.17em}}1\le j\le 2^i.$$

(21)

Equations (19), (20), and (21) will be used in the proof of Claim 3 below, along with the following simple lemma.

Lemma 1 (Integral Test)

Let n ∈ ℕ and let f : [n,∞] → ℝ be a positive, continuous, monotone-decreasing function, then:

$${\int }_n^{\infty }f(x)dx\le \sum _{k=n}^{\infty }f(k)\le f(n)+{\int }_n^{\infty }f(x)dx.$$

Claim 3

ℙ(W_t) decays roughly as 1/t. More exactly, C/12t ≤ ℙ(W_t) ≤ 6C/t for all t ∈ ℕ.

Proof

For any state ${\sigma }_{ij}^k$ with i < t, $\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0={\sigma }_{ij}^k)=0$. Thus, we have:

$$\begin{array}{l}\mathbb{P}(W_t)=\mathbb{P}({\overrightarrow{X}}^t\in W_t)\\ =\sum _{i=t}^{\infty }\sum _{j=1}^{2^i}\mathbb{P}(S_0\in R_{ij})·\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0\in R_{ij})\\ =\sum _{i=t}^{\infty }{2}^i·\mathbb{P}(S_0\in R_{i1})·\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0\in R_{i1}),\end{array}$$

(22)

where the final equality follows from symmetry. We prove the bounds from above and below on ℙ(W_t) separately using Equation (22).

• Bound from below:

  $$\begin{array}{l}\mathbb{P}(W_t)=\sum _{i=t}^{\infty }{2}^i·\mathbb{P}(S_0\in R_{i1})·\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0\in R_{i1})\\ \ge \sum _{i=2t}^{\infty }{2}^i·\mathbb{P}(S_0\in R_{i1})·\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0\in R_{i1})\\ \stackrel{(a)}{\ge }\sum _{i=2t}^{\infty }{2}^i·\frac{C}{2^i·i^2}·\frac{1}{6}\\ =\frac{C}{6}\sum _{i=2t}^{\infty }\frac{1}{i^2}\\ \stackrel{(b)}{\ge }\frac{C}{6}{\int }_{2t}^{\infty }\frac{1}{x^2}dx\\ =\frac{C}{12t}.\end{array}$$

  (23)

  Here, (a) follows from Equations (19) and (21) and (b) from Lemma 1.

• Bound from above:

  $$\begin{array}{l}\mathbb{P}(W_t)=\sum _{i=t}^{\infty }{2}^i·\mathbb{P}(S_0\in R_{i1})·\mathbb{P}({\overrightarrow{X}}^t\in W_t\mid S_0\in R_{i1})\\ \stackrel{(a)}{\le }\sum _{i=t}^{\infty }{2}^i·\frac{3C}{2^i·i^2}·1\\ =3C\sum _{i=t}^{\infty }\frac{1}{i^2}\\ \stackrel{(b)}{\le }3C\left(\frac{1}{t^2}+{\int }_t^{\infty }\frac{1}{x^2}dx\right)\\ =3C·\left(\frac{1}{t^2}+\frac{1}{t}\right)\\ \le \frac{6C}{t}.\end{array}$$

  (24)

  Here, (a) follows from Equation (20) and (b) from Lemma 1.

Claim 4

ℙ(X_t ∈ {2, 3}|X⃗^t = w) ≥ 1/150, for all t ∈ ℕ and w ∈ W_t.

Proof

Applying Claim 3 we have for any t ∈ ℕ:

$$\begin{array}{l}\mathbb{P}(X_t\in \{2,3\}\mid {\overrightarrow{X}}^t\in W_t)=\mathbb{P}({\overrightarrow{X}}^{t+1}\in W_{t+1}\mid {\overrightarrow{X}}^t\in W_t)\\ =\mathbb{P}({\overrightarrow{X}}^{t+1}\in W_{t+1},{\overrightarrow{X}}^t\in W_t)/\mathbb{P}({\overrightarrow{X}}^t\in W_t)\\ =\mathbb{P}({\overrightarrow{X}}^{t+1}\in W_{t+1})/\mathbb{P}({\overrightarrow{X}}^t\in W_t)\\ \ge \frac{C/12(t+1)}{6C/t}\\ =\frac{1}{72}·\frac{t}{t+1}\\ \ge \frac{1}{150}.\end{array}$$

By symmetry, ℙ(X_t ∈ {2, 3}|X⃗^t = w) is the same for each w ∈ W_t. Thus, the same bound must also hold for each w ∈ W_t individually: ℙ(X_t ∈ {2, 3}|X⃗^t = w) ≥ 1/150 for all w ∈ W_t.

Claim 5

For each t ∈ ℕ and w ∈ W_t,

(i)

h̃_w ≤ 1/300 and

(ii)

h_w ≥ 1/150.

Hence, h_w –h̃_w ≥ 1/300.

Proof of (i)

$h_{{\sigma }_{ij}^k}=0$, for all i ≥ 1, 1 ≤ j ≤ 2ⁱ, and k ≥ 2. And, for each w ∈ W_t, $\phi {(w)}_{{\sigma }_{ij}^1}=0$, for all i ≥ 1 and 1 ≤ j ≤ 2ⁱ. Hence, for each w ∈ W_t, ${\tilde{h}}_w={\sum }_{\sigma \in \mathcal{S}}\phi {(w)}_{\sigma }{h}_{\sigma }=\phi {(w)}_{{\sigma }_{01}^1}{h}_{{\sigma }_{01}^1}$. By construction of the machine $h_{{\sigma }_{01}^1}\le 1/300$ and, clearly, $\phi {(w)}_{{\sigma }_{01}^1}$ can never exceed 1. Thus, h̃_w ≤ 1/300 for all w ∈ W_t.

Proof of (ii)

Let the random variable Z_t be defined by: Z_t = 1if X_t ∉ {2, 3} and Z_t = 0 if X_t ∉ {2, 3}. By Claim 4, ℙ(Z_t = 1|X⃗^t = w) ≥ 1/150 for any w ∈ W_t. Also, by symmetry, the probabilities of a 2 or a 3 following any word w ∈ W_t are equal, so ℙ(X_t = 2|X⃗^t = w, Z_t = 1) = ℙ(X_t = 3|X⃗^t = w, Z_t = 1) = 1/2. Therefore, for any w ∈ W_t:

$$\begin{array}{l}{h}_w=H\hspace{0.17em}[X_t\mid {\overrightarrow{X}}^t=w]\\ \ge H[X_t\mid {\overrightarrow{X}}^t=w,Z_t]\\ \ge \mathbb{P}(Z_t=1\mid {\overrightarrow{X}}^t=w)·H[X_t\mid {\overrightarrow{X}}^t=w,Z_t=1]\\ \ge 1/150·1.\end{array}$$

Claim 6

For each t ∈ ℕ and w ∈ $ℒ$_t, h_w –h̃_w ≥ 0.

Proof

For w ∈ $ℒ$_t, let P_w = ℙ(X_t|X⃗^t = w) denote the probability distribution over the next output symbol after observing the word w. Also, for σ ∈ , let P_σ = ℙ(X_t|S_t = σ) denote the probability distribution over the next output symbol given that the current state is σ. Then, by concavity of the entropy function H [·], we have that for any w ∈ $ℒ$_t:

$$h_w\equiv H[P_w]=H\left[\sum _{\sigma \in \mathcal{S}}\phi {(w)}_{\sigma }·P_{\sigma }\right]\ge \sum _{\sigma \in \mathcal{S}}\phi {(w)}_{\sigma }·H[P_{\sigma }]=\sum _{\sigma \in \mathcal{S}}\phi {(w)}_{\sigma }{h}_{\sigma }\equiv {\tilde{h}}_w.$$

Claim 7

The quantity h(t) – h decays at a rate no faster than 1/t. More exactly,$h(t+1)-h\ge \frac{C}{3600t}$, for all t ∈ ℕ.

Proof

As noted above, since the machine satisfies the conditions of Proposition 1, the entropy rate is given by Equation (8) and the difference h(t + 1) – h is given by Equation (14). Therefore, applying Claims 3, 5, and 6 we may bound this difference h(t + 1) – h as follows:

$$\begin{array}{l}h(t+1)-h=\sum _{w\in {\mathcal{L}}_t}\mathbb{P}(w)\hspace{0.17em}(h_w-{\tilde{h}}_w)\\ \ge \sum _{w\in W_t}\mathbb{P}(w)\hspace{0.17em}(h_w-{\tilde{h}}_w)\\ \ge \mathbb{P}(W_t)·\frac{1}{300}\\ \ge \frac{C}{3600t}.\end{array}$$

With the above decay on h(t) established we easily see the Branching Copy Process must have infinite excess entropy.

Proposition 3

The excess entropy E for the BC Process is infinite.

Proof. $\mathbf{E}={\sum }_{t=1}^{\infty }(h(t)-h)$. By Claim 7, this sum must diverge

4. Conclusions

Any stationary, finite-alphabet process can be presented by a stationary HMM with an uncountable state set. Thus, there exist stationary HMMs with uncountable state sets capable of generating infinitary, finite-alphabet processes. It is impossible, however, to have a finite-state, stationary HMM that generates an infinitary process. The excess entropy E is always bounded by the entropy in the stationary distribution H [π], which is finite for any finite-state HMM. Countable-state HMMs are intermediate between the finite and uncountable cases, and it was previously not shown whether infinite excess entropy was possible in this case, or not. We have demonstrated that it is indeed possible, by giving two explicit constructions of finite-alphabet, infinitary processes generated by stationary HMMs with countable state sets.

The second example, the Branching Copy Process, is also ergodic—a strong restriction. It is a priori quite plausible that infinite E might only occur in the countable-state case for nonergodic processes. Moreover, both HMMs we constructed are unifilar, so the ε-machines [12,16] of the processes have countable state sets as well. Again, unifilarity is a strong restriction to impose, and it is a priori conceivable that infinite E might only occur in the countable-state case for nonunifilar HMMs. Our examples have shown, though, that infinite E is possible for countable-state HMMs, even if one requires both ergodicity and unifilarity.

Following the original release of the above results [9] two additional examples of both ergodic and nonergodic infinitary, finite-alphabet processes with countable-state HMM presentations appeared [10]. For these examples it was shown that the mutual information E(t) = I [X⃖^t;X⃗^t] between length-t blocks diverges as a power law. Whereas, in our nonergodic example it diverges sublogarithmically and in our ergodic example, presumably, at most logarithmically. The ergodic example given in [10] is also somewhat simpler than ours. However, the HMM presentation for the ergodic process there is not unifilar and, moreover, one does not expect the ε-machine for this process to have a countable state set either. Taking this all into account leaves open the question: Is power law divergence of E(t) possible for ergodic processes with unifilar, countable-state HMM presentations?