Computational Mechanics

(a) Two histories belong to the same cell when they receive the same summary value. In particular, $R_A(u_1)=R_A(u_2)$.

(b) Both $R_A$ and $R_B$ are sufficient. Every cell of ${\Pi }_A$ and every cell of ${\Pi }_B$ contains histories carrying only one of the distributions $P$, $Q$, or $S$.

The statistic $R_C$ is not sufficient. Its first cell contains $u_1$ and $u_4$, for example, but $u_1$ induces $P$ while $u_4$ induces $Q$. Since $P\ne Q$, these histories cannot be assigned the same value by a sufficient statistic.

(c) The cell $\{u_1,u_2\}$ can be merged with $\{u_3\}$ because all three histories induce $P$. Similarly, $\{u_4\}$ can be merged with $\{u_5\}$ because both histories induce $Q$. No cell can be merged with $\{u_6\}$, and no $P$-cell can be merged with a $Q$-cell. After all permissible merges, the resulting partition is

(d) The three cells of ${\Pi }_B$ correspond respectively to the three distinct future distributions $P$, $Q$, and $S$. Merging any two cells would therefore place histories with different future distributions in the same cell and destroy sufficiency. Hence $R_B$ is minimal sufficient.

(e) Let ${\Pi }^{\prime }$ refine a sufficient partition $\Pi$. Any two histories in the same cell of ${\Pi }^{\prime }$ also belong to the same cell of $\Pi$. Since $\Pi$ is sufficient, those histories induce the same future distribution. Therefore ${\Pi }^{\prime }$ is sufficient.

In the example, ${\Pi }_A$ refines ${\Pi }_B$, and both are sufficient. A coarsening need not remain sufficient: ${\Pi }_C$ is obtained from the sufficient partition ${\Pi }_A$ by merging its cells $\{u_1,u_2\}$, $\{u_3\}$, and $\{u_4\}$. The resulting cell contains histories inducing both $P$ and $Q$, so ${\Pi }_C$ is not sufficient.

(f) Every cell of ${\Pi }_D$ lies within one predictive class, so ${\Pi }_D$ is sufficient. The same was established for ${\Pi }_A$.

The cell $\{u_1,u_2\}$ of ${\Pi }_A$ is split between $\{u_1\}$ and $\{u_2,u_3\}$ in ${\Pi }_D$, so ${\Pi }_A$ does not refine ${\Pi }_D$. Conversely, $\{u_2,u_3\}$ in ${\Pi }_D$ is split between $\{u_1,u_2\}$ and $\{u_3\}$ in ${\Pi }_A$, so ${\Pi }_D$ does not refine ${\Pi }_A$. Both partitions nevertheless refine ${\Pi }_B$, because every one of their cells is contained in one of the three predictive classes represented by $P$, $Q$, and $S$.

(a)

1. For every $x\in {\mathcal{X}}_{+}^{\ast }$ and every continuation $y$, the conditional probability after $x$ equals itself. Hence $x\sim x$, so $\sim$ is reflexive.
2. If $x\sim x^{\prime }$, then the two continuation probabilities are equal for every $y$. Reversing the equality shows that $x^{\prime }\sim x$, so $\sim$ is symmetric.
3. Suppose $x\sim x^{\prime }$ and $x^{\prime }\sim x^{\prime \prime }$. For every $y$, the continuation probability after $x$ equals that after $x^{\prime }$, which equals that after $x^{\prime \prime }$. Thus $x\sim x^{\prime \prime }$, so $\sim$ is transitive.

Therefore $\sim$ is an equivalence relation.

(b) If $ϵ(x)=ϵ(x^{\prime })$, then $x$ and $x^{\prime }$ belong to the same equivalence class, so $x\sim x^{\prime }$. By the definition of $\sim$, the two histories induce the same probability for every finite continuation $y$. This is precisely the definition of sufficiency for prediction, so $ϵ$ is sufficient.

(c) Suppose $R(x)=R(x^{\prime })$. Since $R$ is sufficient, $x$ and $x^{\prime }$ induce the same probability for every finite continuation. Hence $x\sim x^{\prime }$, and equivalent histories have the same equivalence class: $ϵ(x)=ϵ(x^{\prime })$.

Thus any two histories in the same cell induced by $R$ also lie in the same causal state. Every cell induced by $R$ is therefore contained in a causal state, so the partition induced by $R$ refines the causal-state partition. Since $R$ was arbitrary, every sufficient partition has this property.

(d) Part (b) shows that $ϵ$ is sufficient. Part (c) shows that its partition is refined by the partition of every sufficient statistic. Hence the causal-state partition is the coarsest sufficient partition, so $ϵ$ is a minimal sufficient statistic.

(e) Since $T$ is sufficient, part (c), with $R=T$, shows that the partition induced by $T$ refines the causal-state partition. Since $T$ is minimal and $ϵ$ is sufficient, the causal-state partition must also refine the partition induced by $T$. The two partitions are therefore equal.

Define $\psi (ϵ(x)):=T(x)$. Equality of the two partitions shows that this definition is independent of the representative $x$ and that distinct causal states receive distinct $T$-values. It also reaches every value in $\mathrm{im}(T)$. Hence $\psi$ is a bijection.

(a)

1. All four length-two histories are possible. Their resulting hidden phases are

Thus $00$, $01$, and $11$ identify the phase exactly, while $10$ is ambiguous. 2. From the phases compatible with $10$, only $s_0$ can emit $0$, and only $s_1$ can emit $1$. Consequently, $100$ identifies the new phase as $s_1$, while $101$ identifies it as $s_R$. From each phase, the emitted symbol determines the next phase, so every later observation preserves synchronization. 3. The histories $00$, $01$, and $11$ identify $s_1$, $s_R$, and $s_0$, respectively. These phases induce distinct next-token distributions: $s_1$ emits only $1$, $s_0$ emits only $0$, and $s_R$ can emit either symbol. Hence they give three distinct causal states.

They are also distinct from the four states assumed in the question. This can be seen without calculating probabilities by comparing possible length-two continuations:

The only repeated continuation set belongs to $0$ and $10$, whose causal states are assumed to be distinct. Finally, every history of length at least three identifies the phase by part (ii), and so belongs to one of the states represented by $00$, $01$, and $11$. No further causal states arise. 4. Appending each possible symbol gives the causal-state update:

Here a dash denotes an impossible extension. Drawing one node for each row and the indicated symbol-labelled edges gives the required automaton.

(b)

1. The history $0$ identifies the current state as $A$: only $A$ can emit $0$, and this transition returns to $A$. The history $1$ is ambiguous. If $S_0=A$, it leads to $B$, while if $S_0=B$, it leads to $A$.
2. From the two states compatible with the history $1$, only $A$ can emit $0$. Therefore $10$ resolves the ambiguity and identifies the new state as $A$. The extension $11$ remains ambiguous. Using the given equality and recursively updating after pairs of $1$s gives

3. If a history contains a $0$, its final $0$ synchronizes the generator to $A$. An even number of trailing $1$s then leaves it in $A$, represented by $0$, while an odd number leaves it in $B$, represented by $01$. If the history contains no $0$, part (ii) shows that its causal state is represented by $\varnothing$ or $1$, according to the parity of its length. Thus no additional causal states arise.

These four states are distinct. The state represented by $01$ cannot emit $0$, whereas the other three can. The continuation $10$ is impossible after $0$ but possible after $\varnothing$ and $1$. Finally, $ϵ(\varnothing )\ne ϵ(1)$ by assumption. Hence the displayed representatives are also shortest. 4. Appending each possible symbol gives the causal-state update:

Here a dash denotes an impossible extension. Drawing one node for each row and the indicated symbol-labelled edges gives the required automaton.

(c)

1. The only transition that emits $1$ starts from $B$, and that transition leads to $A$. Thus the hidden state immediately after observing $1$ is $A$.
2. One path remains in $A$ while emitting all $n$ zeros. Each of the other $n$ paths moves from $A$ to $B$ on one of the $n$ transitions and then remains in $B$. Thus there are $n+1$ paths, each with probability $2^{-n}$, and

The $n$ paths that end in $B$ can subsequently emit $1$. Including this final transition, each has probability $2^{-(n+1)}$, so

3. Since

this probability is strictly increasing with $n$. Hence every pair of histories $10^n$ and $10^m$, with $n\ne m$, already has a different next-token distribution. They must lie in different causal states. The source consequently has infinitely many causal states despite its two-state generator.

(a) Appending one symbol $a$ gives

Repeatedly applying this deterministic update along $z_{1:j}$ gives

If $R(x_{1:n})=R(x_{1:m}^{\prime })$ and both extended histories are allowable, applying the same composite function to the equal starting representations gives

(b) Suppose that the prefixes through $z_{1:j}$ are allowable after both histories. Part (a) gives

The two representations give the same arguments to $g_{\theta }$, so exact next-token prediction gives

Thus the next extension has positive probability after one history exactly when it has positive probability after the other. Following the word from left to right, either both encounter their first zero at the same position or all its prefixes are allowable after both.

(c) If every prefix is allowable, the conditional chain rule gives the product in the question and

Part (b) shows that the factors in the two products are equal, so the products are equal. If a first zero-probability extension is encountered instead, part (b) shows that it occurs after both histories; consequently both probabilities of the complete continuation are zero.

Therefore equal values of $R$ imply equal conditional probabilities for every finite continuation. By the definition of sufficiency,

is a sufficient statistic for predicting the entire future.

(a) In the diagram, $i$ is the current hidden state, $j$ is the next hidden state, $a$ is the emitted symbol, and $r$ is the probability of that joint emission-transition event conditional on starting in $i$. Thus the edge records $T_{ij}^{(a)}=\mathrm{Pr}(X_{t+1}=a,S_{t+1}=j\mid S_t=i)=r$. A zero entry means that no such emission-transition pair is possible. For a fixed current state $i$, the events indexed by all pairs $(a,j)$ exhaust the possible emitted symbols and next states. Consequently,

Since

every entry of $T$ is nonnegative and its $i$th row sums to

Hence $T$ is row-stochastic.

(b)

1. The nonzero entries give the transitions

Thus the diagram is a three-state cycle, with two differently labelled edges from $R$ to $0$. State $0$ is the phase that emits $0$ deterministically, state $1$ is the phase that emits $1$ deterministically, and state $R$ is the random phase, which emits $1$ with probability $p$ and $0$ with probability $1-p$. 2. For $011$, the only possible initial state is $0$. The model then follows

Including the initial probability $1/3$ gives $\mathrm{Pr}(011)=p/3$. Matrix multiplication gives the same result:

No state permits a path labelled $000$: starting from $0$, the first $0$ moves to state $1$, which cannot emit $0$; starting from $1$, even the first $0$ is impossible; and starting from $R$, the first two zeros move through $R\to 0\to 1$, after which a third zero is impossible. Correspondingly,

(c)

1. In state order $(A,B)$, the matrices are

In $T^{(0)}$, the entry $(A,B)$ is zero because no $0$-edge connects $A$ to $B$, while the entire $B$ row is zero because state $B$ cannot emit $0$. In $T^{(1)}$, the diagonal entries are zero because neither $1$-edge is a self-loop. The two off-diagonal entries record $A\stackrel{1:1-q}{\to }B$ and $B\stackrel{1:1}{\to }A$. 2. We have

Its entries are nonnegative and both rows sum to one. 3. The word $011$ can be produced only by starting from $A$ and following

Thus

The matrix calculation is

The word $010$ would require the path to emit a $0$ immediately after the transition $A\stackrel{1}{\to }B$, but state $B$ cannot emit $0$. Hence there is no such path. Equivalently,

This is the shortest example of an odd run of $1$s occurring between two $0$s, which the Even Process forbids.

(d) Expanding the product of the sum of the symbol matrices gives

Multiplying on the left by ${\eta }^{(\varnothing )}$ and on the right by $1$ therefore yields

Since $T$ is row-stochastic, $T1=1$ and hence $T^{n}1=1$. Finally, ${\eta }^{(\varnothing )}1=1$, because the initial vector is a probability distribution. The required sum is therefore one.

(a) Multiplying the initial belief by the two symbol matrices gives

Their row sums are respectively $(2-p)/3$ and $(1+p)/3$. Normalising therefore gives

After observing $0$, the current phase is either $0$ or $1$ with the displayed posterior probabilities, and cannot be $R$. After observing $1$, it is either $0$ or $R$, and cannot be $1$.

(b) Direct evaluation gives

Thus the pure beliefs are ${\eta }^{(11)}$, ${\eta }^{(00)}$, and ${\eta }^{(01)}$. The pure beliefs are distinct. The beliefs ${\eta }^{(\varnothing )}$, ${\eta }^{(0)}$, and ${\eta }^{(1)}$ have different supports from one another and from the pure beliefs. The only remaining comparison is between ${\eta }^{(0)}$ and ${\eta }^{(10)}$, which both have support $\{0,1\}$. Equality would require $1/(2-p)=p$, or $(1-p{)}^2=0$, contrary to $p<1$.

The allowable updates are

This table specifies the requested symbol-labelled diagram and shows that every allowable update stays in $\mathcal{B}$.

(c)

1. Under the assumptions used in Part 2, the correspondence is

The transition table from part (b) agrees with the causal-state automaton after making these substitutions. 2. The pure beliefs ${\eta }^{(11)}$, ${\eta }^{(00)}$, and ${\eta }^{(01)}$ identify the hidden phase exactly. The other four beliefs assign positive probability to more than one phase and therefore represent uncertainty. After two observations only the history $10$ leaves a mixed belief. Either allowable third symbol sends ${\eta }^{(10)}$ to a pure belief. Once the belief is pure, every allowable transition in the table leads to another pure belief, so the phase remains known. 3. The generator has access to its actual hidden phase and needs only the three states $0$, $1$, and $R$. An observer begins with an unknown phase and must also represent four transient posterior distributions before synchronising with the generator. This example therefore shows that inference can require a richer state description than a particular generative presentation.

(d) The probability of each symbol from a hidden phase is obtained by summing the corresponding row of its symbol matrix over destination states. With column order $(0,1)$, this gives

Hence

On the belief $2$-simplex, ${\eta }^{(11)}$, ${\eta }^{(00)}$, and ${\eta }^{(01)}$ are the three vertices, while ${\eta }^{(\varnothing )}$ is the barycentre. The beliefs ${\eta }^{(0)}$ and ${\eta }^{(10)}$ lie on the edge joining ${\eta }^{(11)}$ to ${\eta }^{(00)}$, and ${\eta }^{(1)}$ lies on the edge joining ${\eta }^{(11)}$ to ${\eta }^{(01)}$.

On the next-token $1$-simplex, each point is located by the second coordinate in the table, namely its probability of emitting $1$. The relation $p^{(x_{1:n})}={\eta }^{(x_{1:n})}A$ maps the two distinct beliefs ${\eta }^{(01)}$ and ${\eta }^{(10)}$ to the same point $p^{(01)}=p^{(10)}=(1-p,p)$.

(e) Starting from ${\eta }^{(10)}=(1-p,p,0)$, observing a $0$ can only come from phase $0$ and moves the process to phase $1$, which cannot emit a second $0$. Hence

Starting from ${\eta }^{(01)}=(0,0,1)$, the first $0$ has probability $1-p$ and moves the process to phase $0$, which emits the second $0$ deterministically. Therefore

The histories agree about the next symbol but disagree about a two-symbol continuation, so their shared next-token vector is not sufficient for the entire future.

(f) We have

Direct multiplication gives

Thus the difference between the beliefs is invisible to the one-step readout but visible to a readout associated with the two-symbol future $00$.