1 Introduction↩︎

Multi-head finite-state dimensions quantify the predictability of an infinite sequence to a finite-state gambler that is granted restricted access to past data. These dimensions were introduced by Huang, Li, Lutz, and Lutz [1] as modest generalizations of finite-state dimension, which was introduced by Dai, Lathrop, Lutz, and Mayordomo [2] and is closely connected to compression, entropy rates, and normality [3], [4]. Unlike finite-state dimension, multi-head finite-state dimension can capture certain long-range dependencies, such as in a sequence \(S\) that satisfies \(S[2n]=S[n]\) for all natural numbers \(n\).

The prediction is performed by a multi-head finite-state gambler that has both a leading head, which moves continually forward through the sequence, and a set of trailing heads, each of which can start and stop moving forward. This allows the trailing heads to lag behind the leading head and access data it has read in the distant past. The gambler has finite memory, but it updates its state based on the observations of all heads. Huang et al. [1] showed that each additional trailing head strictly increases the gambler’s predictive power, and Lutz [5] showed that the same model can be characterized in terms of data compression.

In the original setting of Huang et al. [1], the movement of the heads is oblivious or data-independent, meaning that the heads follow the same schedule of movement on every sequence. Cruz, Glashausser, Li, and Lutz [6] studied an adaptive or data-dependent version, where the gambler can use the sequence to determine which trailing heads to move forward in each step. Cruz et al. [6] showed that adaptivity strictly increases the gambler’s predictive power compared to obliviousness.

Specifically, Cruz et al. [6] proved that for each \(h\geq 2\), there is a sequence \(X\) whose adaptive \(h\)-head finite-state predimension is strictly less than its oblivious \(h\)-head finite-state predimension, and whose \(h\)-head finite-state strong predimension is strictly less than its oblivious \(h\)-head finite-state strong predimension. Using their notation, \[\label{eq:cgllsep} \mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h)}(X)<\mathop{\mathrm{odim}}_{\mathrm{FS}}^{(h)}(X)\text{ and }\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(h)}(X)<\mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(X).\tag{1}\] Roughly, \(\mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h)}(X)\) and \(\mathop{\mathrm{odim}}_{\mathrm{FS}}^{(h)}(X)\) quantify the infinitely-often predictability of the sequence, while the strong variants \(\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(h)}(X)\) and \(\mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(X)\) quantify its almost-everywhere predictability. Directly analogous to the hierarchy Huang et al. [1] proved in the oblivious setting, Cruz et al. [6] further proved that, for each \(h\geq 2\), there is a binary sequence \(Y\) such that \[\label{eq:cgllhier} \mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h)}(Y)\leq\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(h)}(Y)<\mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h-1)}(Y)\leq\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(h-1)}(Y).\tag{2}\]

Combined, these results describe the situation one might expect: more heads help, and adaptivity helps. In this work, we consider the tradeoffs between these two types of enhancement, and we establish a much stronger separation between adaptivity and obliviousness. Namely, we prove as our main theorem that there is a binary sequence \(S\) such that for all \(h\geq 1\), \[\label{eq:cglsep} \mathop{\mathrm{adim}}_{\mathrm{FS}}^{(2)}(S)\leq\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(2)}(S)<\mathop{\mathrm{odim}}_{\mathrm{FS}}^{(h)}(S)-0.3\leq\mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(S)-0.3.\tag{3}\] This strengthens the separations 1 from [6] in three ways. First, our separation is quantitatively much larger and uniform in \(h\); the gaps in 1 proved in [6] depend on \(h\) and on the size of the sequence’s alphabet, but they are all less than \(\frac{3}{160}=0.01875\) and converge to 0 as \(h\) approaches \(\infty\), decreasing on the order of \(h^{-4}\). Second, we separate adaptive strong predimension from oblivious ordinary predimension. Third, and most importantly, in our separation the number of heads on the adaptive side is fixed at two. This means that an adaptive two-head finite state gambler—which has only a single trailing head with adaptive movement rules—is able to predict \(S\) more successfully than any oblivious multi-head finite-state gambler could.

We prove the separation 3 using a sequence \(S\) that references itself and also describes its own self-referential structure. This allows an adaptive gambler to optimally position its trailing head and thereby predict every odd-indexed bit with certainty. We use a Kolmogorov complexity argument, combined with the observation that oblivious trailing heads must move at asymptotically rational speeds, to bound the performance of oblivious multi-head finite-state gamblers on the same sequence.

As we describe in Section 7, it follows from results of Huang et al. [1] and Cruz et al. [6] that for all \(h\geq 2\) there is a sequence \(Y\) such that \(\mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(Y)<\mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h-1)}(Y)\). Combined with 3 , this means the usefulness of adaptive trailing head movement is incomparable to the usefulness of additional trailing heads; which of these enhancements adds more predictive power depends on the type of sequence being predicted. This suggests a rich structure of tradeoffs for multi-head finite-state gamblers, analogous to the nuances of the varieties of multi-head automata [7], [8], and we expect future work to further explore these tradeoffs.

The rest of the paper is organized as follows. In Section 2 we briefly overview information-theoretic preliminaries, including a discussion of Kolmogorov complexity with respect to a given measure, and in Section 3 we recap the definitions of oblivious and adaptive multi-head finite-state predimensions and dimensions introduced by [1] and [6]. In Section 4, we describe the family of sequences we will use to prove our main theorem. We prove the adaptive upper bound (Theorem 2) and oblivious lower bound (Theorem 3) in Sections 5 and 6, respectively, before presenting and discussing our main theorem (Theorem 6) in Section 7.

2 Algorithmic Information Preliminaries↩︎

For \(m,n\in\mathbb{N}\), we write \([m:n]\) for the integer interval \(\{m,\ldots,n-1\}\); if \(m\geq n\), then this interval is empty. The space of all infinite binary sequences is \(\{0,1\}^\omega\). Given any sequence \(X\in\{0,1\}^\omega\) and \(A\subseteq\mathbb{N}\), we write \(X[A]\) for the sequence or string containing the bits of \(X\) whose indices are in \(A\), concatenated in increasing order of index. For \(m,n\in\mathbb{N}\), we write \(X[m:n]\) as shorthand for \(X[[m:n]]\), so \(X[m:n]=X[m]\ldots X[n-1]\); if \(m\geq n\), then this is the empty sequence, denoted \(\lambda\). More generally, for \(A\subseteq\mathbb{R}\), we define \(X[A]=X[A\cap\mathbb{N}]\).

A finite string \(w\in\{0,1\}^*\) is a prefix of a sequence \(x\in\{0,1\}^\omega\), and write \(w\sqsubseteq X\), if there is some sequence \(Y\in\{0,1\}^\omega\) such that \(X=wY\). For each finite string \(w\in\{0,1\}^*\), the cylinder of \(w\) is \([\![w]\!]\), the set of all binary sequences that have \(w\) as a prefix: \[[\![w]\!]=\left\{X\in\{0,1\}^\omega:w\sqsubseteq X\right\}.\]

2.1 Bernoulli Measures and Binary Entropy↩︎

For each \(p\in[0,1]\), define the \(p\)-biased Bernoulli distribution \[\mathop{\mathrm{Bern}}_p:\{0,1\}\to[0,1]\] by \(\mathop{\mathrm{Bern}}_p(1)=p\) and \(\mathop{\mathrm{Bern}}_p(0)=1-p\), and define the \(p\)-biased Bernoulli measure \(\mu_p:\{0,1\}^\omega\to[0,1]\) by, for all strings \(w\in\{0,1\}^*\), \[\mu_p([\![w]\!])=p^{\#_1(w)}(1-p)^{\#_0(w)},\] where \(\#_1(w)\) and \(\#_0(w)\) denote the number of ones in \(w\) and number of zeros in \(w\), respectively. Thus, \(\mu_p([\![w]\!])\) is exactly the probability that a sequence of \(p\)-biased Bernoulli trials will begin with \(w\).

The binary entropy of \(p\in[0,1]\) is the entropy of the Bernoulli distribution with success probability \(p\), denoted \[\label{eq:H} \mathop{\mathrm{H}}(p)=p\log\left(\frac{1}{p}\right)+(1-p)\log\left(\frac{1}{1-p}\right),\tag{4}\] where the logarithms, like all others in this paper, are base-2.

2.2 \(s\)-Gales and Martingales↩︎

For \(s\in[0,\infty)\), an \(s\)-gale on binary strings is a function \(d:\{0,1\}^*\to[0,\infty)\) that satisfies, for all \(w\in\{0,1\}^*\), \[d(w)=\frac{d(w0)+d(w1)}{2^s}.\] Informally, an \(s\)-gale represents the capital of a gambler betting on successive bits of some sequence \(S\in\{0,1\}^\omega\), where the parameter \(s\) quantifies the favorability of the betting environment. After betting on the bits in some prefix \(S[0:n]\), the gambler has capital \(d(S[0:n])\). The gambler then places bets on the next bit \(S[n]\), allocating fraction \(\beta\) of its current capital to the event \(S[n]=1\) and the remaining \((1-\beta)\) fraction of its capital to the event \(S[n]=0\). If \(S[n]=1\), then the gambler’s capital is updated to \[d_G(S[0:n+1])=2^s\beta d_G(S[0:n]);\] otherwise, \(S[n]=0\) and its capital is updated to \[d_G(S[0:n+1])=2^s(1-\beta) d_G(S[0:n]).\] A martingale is a 1-gale.

An \(s\)-gale \(d\) succeeds on a sequence \(S\in\{0,1\}^\omega\) if \[\limsup_{n\to\infty}d(S[0:n])=\infty,\] and it strongly succeeds on \(S\) if \[\liminf_{n\to\infty}d(S[0:n])=\infty.\]

2.3 Kolmogorov Complexity↩︎

Let \(U\) be a fixed universal prefix-free Turing machine. For binary strings \(x,y\in\{0,1\}^*\), the (prefix) conditional Kolmogorov complexity of \(x\) given \(y\) is \[K(x\mid y)=\min\{|z|:z\in\{0,1\}^*\text{ and }U(z,y)=x\}.\] Intuitively, \(z\) is interpreted as a program that outputs \(x\) when it is given \(y\) as an input. The (prefix) Kolmogorov complexity of \(x\) is the conditional Kolmogorov complexity of \(x\) given the empty string: \[K(x)=K(x\mid \lambda).\] Our lower-bounding arguments in Section 6 will use basic properties of Kolmogorov complexity, as described in Chapter 3 of [9]. While many details of that chapter concern error terms that are logarithmic or sublogarithmic in \(|x|\), our Kolmogorov complexity arguments are robust to logarithmic error and can therefore be presented more simply. For example, when \(|x|,|y|\leq n\), we will use symmetry of information in the simplified form \[\label{eq:soi} |K(x,y)-K(x\mid y)-K(y)|=O(\log n),\tag{5}\] in place of the more precise statement \(|K(x,y)-K(x\mid y,K(y))-K(y)|=O(1)\).

2.4 Martin–Löf Randomness with Respect to a Measure↩︎

Given any computable measure \(\mu\), a sequence \(X\in\{0,1\}^\omega\) is Martin-Löf random with respect to \(\mu\) (or \(\mu\)-Martin-Löf random) if, for all prefixes \(w\) of \(X\), \[\label{eq:random} K(w)\geq \log\left(\frac{1}{\mu([\![w]\!])}\right)-O(1).\tag{6}\] Here we interpret \(\frac{1}{0}\) as \(\infty\), so this condition cannot be satisfied when \(\mu([\![w]\!]=0\). This Kolmogorov complexity characterization for arbitrary computable measures is due to Gács [10], generalizing the Levin–Schnorr theorem; see Theorem 4.11 of Reimann [11]. The theory of Martin-Löf randomness, especially with respect to the uniform measure, is covered in depth by Downey and Hirschfeldt [12].

It is well-known that inequality 6 is almost tight, in the sense that, for every computable measure \(\mu\) and every \(w\in\{0,1\}^*\), \[\label{eq:maxcomp} K(w)\leq \log\left(\frac{1}{\mu([\![w]\!])}\right)+O(\log|w|).\tag{7}\] The uniform-measure case \(K(w)\leq |w|+O(\log|w|)\) is given by Theorem 3.2.1 of [9], and the generalization is straightforward via Shannon–Fano coding.

In particular, for each computable \(p\in[0,1]\), if a sequence \(R\in\{0,1\}^\omega\) is Martin-Löf random with respect to the \(p\)-biased Bernoulli measure \(\mu_p\) and \(w\) is a substring of \(R\) (meaning \(w=R[m:n]\) for some \(m,n\in\mathbb{N}\) with \(m<n\)), then \[\label{eq:bernoullirandom} \left|K(w)-\left(\#_1(w)\log\left(\frac{1}{p}\right)+\#_0(w)\log\left(\frac{1}{1-p}\right)\right)\right|=O(\log|w|).\tag{8}\] Intuitively, such a sequence \(R\) is a “typical” outcome of an infinite sequence of \(p\)-biased Bernoulli trials.

It will be important for our lower bound in Section 6 that the density of ones in any prefix of a \(\mu_p\)-Martin-Löf random binary sequence is close to \(p\), which we quantify in the following lemma.

The \(p=1/2\) case is immediate from Lemma 2.6.1 in the book of Li and Vitányi [9], using the deficiency function \(\delta(n)=2\log n\). That result originally appeared in those authors’ earlier paper [13], generalizing Vovk [14]. The argument for arbitrary computable \(p\in[0,1]\) is similar; we include it here for completeness.

By combining Lemma 1 with 8 , we have that if \(R\in\{0,1\}^\omega\) is \(\mu_p\)-Martin-Löf random and \(w\) is a substring of \(R\), then \[\label{eq:bernoullirandoment} \big|K(w)-\mathop{\mathrm{H}}(p)|w|\big|=O\big(\sqrt{|w|\log|w|}\big).\tag{9}\]

3 Multi-Head Finite-State Dimensions↩︎

We now recall the definitions of multi-head finite-state gamblers, predimensions, and dimensions. The oblivious variants were introduced first, by Huang et al. [1], but here we treat oblivious gamblers as a special case of the more general adaptive gamblers studied by Cruz et al. [6].

3.1 Multi-Head Finite-State Gamblers↩︎

For \(h\geq 1\), an (adaptive) \(h\)-head finite-state gambler or \(h\)-FSG is a 6-tuple \[G=(Q,\Sigma,\delta,\beta,q_0,c_0),\] where \(Q\) is the finite state space, \(\Sigma\) is a finite alphabet of size \(\geq 2\), \[\delta:Q\times\Sigma^h\to Q\times\{0,1\}^{h-1}\] is the transition function, \(\beta:Q\to\Delta_\mathbb{Q}(\Sigma)\) is the betting function, \(q_0\in Q\) is the initial state, and \(c_0\in[0,\infty)\) is the initial capital. Here \(\Delta_\mathbb{Q}(\Sigma)\) denotes the class of all rational-valued discrete probability distributions over \(\Sigma\). For the remainder of this paper, the alphabet \(\Sigma\) will always be \(\{0,1\}\).

The gambler has \(h\) heads, numbered \(1,\ldots,h\). Head \(h\) is the leading head, and the others are trailing heads. Given a sequence \(S\in\{0,1\}^\omega\), the gambler proceeds in discrete time steps. At each step \(n\in\mathbb{N}\), each head \(i\) has position \(\pi_i(S[0:n])\), and the state is \(q(S[0:n])\). Initially, the state is \(q(S[0:0])=q_0\) and all heads are at position 0, meaning \(\pi_i(S[0:0])=0\) for \(1\leq i\leq h\).

During step \(n\in\mathbb{N}\), in some state \(q\in Q\), the gambler \(G\) does the following. First, \(G\) places a bet \(\beta(q)\) on bit \(S[n]\). Second, \(G\) applies its transition function to its current state and the \(h\)-tuple of bits at the current positions of each head, yielding a new state \(q'\) and an \((h-1)\)-tuple \((r_1,\ldots,r_{h-1})\in\{0,1\}^{h-1}\): \[\delta(q(S[0:n]),(S[\pi_1(S[0:n])],\ldots,S[\pi_h(S[0:n])]))=(q',(r_1,\ldots,r_{h-1})).\] Third, \(G\) updates its state to \(q(S[0:n+1])=q'\) and, defining \(r_h=1\), moves each head \(i\) forward if \(r_i=1\). That is, for each \(i\in\{1,\ldots,h\}\), \[\pi_i(S[0:n+1])=\pi_i(S[0:n])+r_i.\] In particular, \(\pi_h(S[0:n])=n\) holds for all \(n\in\mathbb{N}\); the leading head moves forward in every step.

3.2 Obliviousness and Adaptivity↩︎

An \(h\)-head finite-state gambler is oblivious or data-independent if its trailing head movements are independent of the input sequence, meaning that for all sequences \(R,S\in\{0,1\}^\omega\), all \(n\in\mathbb{N}\), and all \(i\in\{1,\ldots,h\}\), we have \[\pi_i(R[0:n])=\pi_i(S[0:n]).\] Formally, oblivious multi-head finite-state gamblers are a special case of adaptive \(h\)-head finite-state gamblers, but we primarily use the adjective adaptive to contrast the general model with the oblivious special case.

Huang et al. [1] observed that as a consequence of oblivious, finite-state movement, each trailing head \(i\) must have a fixed speed \(\sigma_i\in[0,1]\) such that, whenever the position of the leading head is \(n\), the position of head \(i\) is within a constant of \(\sigma_i\). It is implicit in the proof of this observation in [1] that \(\sigma_i\) must be rational, as it is the integer number of times the head advances in a particular cycle, divided by the integer length of the cycle.

It follows that a trailing head with speed 0 or 1 can be simulated by the leading head using finite states, so we will assume \(\sigma_i\in(0,1)\) for \(1\leq i\leq h-1\). The rationality of each \(\sigma_i\) is a key ingredient in the current paper; our adaptive gambler’s trailing head will move at an asymptotically irrational speed, thereby accessing information that is unavailable to heads moving at rational speeds.

3.3 Varieties of Multi-Head Finite-State Dimension↩︎

The martingale of a multi-head finite-state gambler is the function \(d_G:\{0,1\}^*\to[0,\infty)\) defined recursively by \(d_G(S[0:0])=c_0\) and, for all \(n\in\mathbb{N}\), \[\label{eq:dG} d_G(S[0:n+1])=2\beta(q(S[0:n]))(S[n])d_G(S[0:n])\tag{10}\] and the \(s\)-gale of \(G\) is the function \(d_G^{(s)}:\{0,1\}^*\to[0,\infty)\) given by \[\label{eq:dGs} d_G^{(s)}(S[0:n])=2^{(s-1)n}d_G(S[0:n]).\tag{11}\]

For each \(h\geq 1\) and \(S\in\{0,1\}^\omega\), the adaptive \(h\)-head finite-state predimension, adaptive \(h\)-head finite-state strong predimension, oblivious \(h\)-head finite-state predimension, and oblivious \(h\)-head finite-state strong predimension of \(S\) are, respectively: \[\begin{align} \mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h)}(S)&=\inf\{s:\exists\text{ h-FSG G s.t. d_G^{(s)} succeeds on }S\},\\ \mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(h)}(S)&=\inf\{s:\exists\text{ h-FSG G s.t. d_G^{(s)} succeeds strongly on }S\},\\ \mathop{\mathrm{odim}}_{\mathrm{FS}}^{(h)}(S)&=\inf\{s:\exists\text{ oblivious h-FSG G s.t. d_G^{(s)} succeeds on }S\},\\ \mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(S)&=\inf\{s:\exists\text{ oblivious h-FSG G s.t. d_G^{(s)} succeeds strongly on }S\}. \end{align}\] These quantities directly generalize the one-head cases, which are finite-state dimension as defined by Dai et al. [2] and finite-state strong dimension as defined by Athreya, Hitchcock, Lutz, and Mayordomo [4]. Obliviousness and adaptivity do not come into play in the one-head case since these properties only concern the trailing heads.

It is immediate from the above definitions that, for each \(S\in\{0,1\}^\omega\), \[\label{eq:comparevariants} \begin{align} \mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h)}(S)&\leq \mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(h)}(S)\leq \mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(S),\\ \mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h)}(S)&\leq \mathop{\mathrm{odim}}_{\mathrm{FS}}^{(h)}(S)\leq \mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(S), \end{align}\tag{12}\] and each of these quantities is non-increasing in \(h\).

The oblivious multi-head finite state dimension, oblivious multi-head finite-state strong dimension, adaptive multi-head finite state dimension, and adaptive multi-head finite-state strong dimension of \(S\) are, respectively, the limits inferior, over all positive integers \(h\), of the four quantities above.

4 Constructing the Family of Sequences↩︎

Define the function \(F:\{0,1\}^\omega\to\{0,1\}^\omega\) by, for all sequences \(R\in\{0,1\}^\omega\), for all \(n\in\mathbb{N}\), \[\label{eq:F} \begin{align} F(R)[2n]&=R[n]\\ F(R)[2n+1]&=F(R)\left[2\#_1(R[0:n])\right]. \end{align}\tag{13}\] Thus, at even indices, \(F(R)\) takes a new bit directly from \(R\), and at odd indices, it copies a bit from earlier in the sequence \(F(R)\). Note that this earlier bit is always even-indexed, so the recursive structure only has depth one. The exact index of the copied bit depends on how many ones appeared in \(R\) prior to \(R[n]\), which is the bit most recently taken from \(R\).

For \(p\in[0,1]\), we will apply the function \(F\) to \(\mu_p\)-Martin-Löf random sequences. For such a sequence \(R\), Lemma 1 tells us that \(\#_1(R[0:n])\) will be approximately \(pn\), so \(F(R)[2n+1]\) will copy a bit from an earlier in \(F(R)\) that is close to index \(2pn\).

5 Upper Bound on Adaptive Two-Head Strong Predimension↩︎

We now prove our upper-bound on the adaptive two-head strong finite-state predimension of sequences of the form \(F(R)\), where \(R\) is random with respect to a Bernoulli measure \(\mu_p\), by defining an adaptive two-head finite state gambler whose \(s\)-gale strongly succeeds on \(F(R)\) for all \(s>\mathop{\mathrm{H}}(p)/2\). By always positioning its trailing head near the currently pertinent information, the gambler will predict odd-indexed bits with certainty. It will treat the even-indexed bits as \(\tilde{p}\)-biased Bernoulli trials, where \(\tilde{p}\) is a rational number very close to \(p\). This small complication is due to the restriction that the betting function of a multi-head finite-state gambler is a rational-valued distribution.

For each \(p\in[0,1]\cap\mathbb{Q}\), define the adaptive \(2\)-head finite-state gambler \[G_p = (Q,\{0,1\},\delta,\beta_p,q_0,1)\] as follows.

• The state space is \(Q = \{0, 1 \}^3\); in each state \((b_1,b_2,b_3)\), \(b_1\) stores the last bit read by the trailing head, \(b_2\) stores the last even-indexed bit read by the leading head, and \(b_3\) indicates the parity of the leading head’s position.

• The transition function \(\delta:Q\times\{0,1\}^2\to Q\times\{0,1\}\) is given by \[\delta((b_1, b_2, b_3), (a_1, a_2)) = \begin{cases} ((a_1,a_2,1), a_2)&\text{if }b_3=0\\ ((a_1,b_2,0), b_2)&\text{if }b_3=1. \end{cases}.\] Informally, the trailing head moves forward twice each time the leading head reads a one at an even index. Since it can move forward at most once per step, this is implemented by the trailing head moving forward immediately when the one is read by the leading head at an even index, then again in the next step, when the leading head is at an odd index. Thus, the trailing head moves when \(b_3=0\) and \(a_2=1\), and when \(b_3=1\) and \(b_2=1\), which are exactly the conditions for the last entry in \(\delta((b_1, b_2, b_3), (a_1, a_2))\) to be 1.

• The betting function \(\beta_p:Q\to\Delta_\mathbb{Q}(\{0,1\})\) is given by \[\beta_p((b_1, b_2, b_3)) = \begin{cases} \mathop{\mathrm{Bern}}_{b_1} & \text{if } b_3 = 1\\ \mathop{\mathrm{Bern}}_p & \text{otherwise.} \end{cases}\] Note that \(\mathop{\mathrm{Bern}}_{b_1}\) is a point distribution at 0 or 1, which informally means that \(G_p\) has total confidence when predicting the odd-indexed bits.

• The initial state is \(q_0 = (0, 0, 0)\).

Now let \(p\in(0,1)\), let \(R\in\{0,1\}^\omega\) be Martin-Löf random with respect to \(\mu_p\), and let \(S=F(R)\). To prove Theorem 2, it suffices to show that for all \(s>\frac{\mathop{\mathrm{H}}(p)}{2}\), there is an adaptive two-head finite-state gambler whose \(s\)-gale strongly succeeds on \(S\). For this, let \(\varepsilon\in (0,\min\{p,1-p\}/2)\), and let \(\tilde{p}\in\left(p-\varepsilon,p+\varepsilon\right)\cap\mathbb{Q}\) satisfy \(|\mathop{\mathrm{H}}(p)-\mathop{\mathrm{H}}(\tilde{p})|<\varepsilon;\) such a \(\tilde{p}\) exists because \(\mathop{\mathrm{H}}\) is continuous. Let \[\label{eq:s} s=\frac{\mathop{\mathrm{H}}(p)}{2}+\left(3-\log(p)-\log(1-p)\right)\varepsilon.\tag{14}\]

As \(G_{\tilde{p}}\) was an adaptive two-head finite-state gambler and \(s\) can be made arbitrarily close to \(\frac{\mathop{\mathrm{H}}(p)}{2}\) by letting \(\varepsilon\) approach 0, it follows from Lemma 2 that \[\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(2)}(F(R))\leq\frac{\mathop{\mathrm{H}}(p)}{2}\] completing the proof of Theorem 2.

6 Lower Bound on Oblivious Multi-Head Dimension↩︎

The trailing head movement of the adaptive gamblers described in Section 5 depend on the sequence \(R\); its asymptotic speed is exactly the asymptotic density \(p\) of ones in the underlying sequence \(R\). We now prove that when \(p\) is irrational, no oblivious multi-head finite-state gambler can match the performance of an adaptive gambler on \(F(R)\).

To prove this theorem, let \(p\in[0,1]\setminus \mathbb{Q}\) be computable, \(R\in\{0,1\}^\omega\) a \(\mu_p\)-Martin-Löf random sequence, \(h\geq 1\), and \(S=F(R)\). By the definition of \(\mathop{\mathrm{odim}}_{\mathrm{FS}}^{\mathop{\mathrm{MH}}}\), it suffices to show that \[\mathop{\mathrm{odim}}_{\mathrm{FS}}^{(h)}(S)\geq (1+p)\frac{\mathop{\mathrm{H}}(p)}{2}.\] For this \(h\)-head finite-state predimension lower bound, we will follow the same overall approach taken by Huang et al. [1] and Cruz et al. [6]. That is, we will prove conditional Kolmogorov complexity lower bounds on substrings \(S[m:n]\), where the string being conditioned on includes all information that the trailing heads might have accessed while the leading head reads \(S[m:n]\). From this lower bound, we will use the following lemma to infer an upper bound on the capital growth of \(G\)’s martingale during this period, from which we will then derive a lower bound on the string’s \(h\)-head finite-state predimension.

To prove the conditional Kolmogorov complexity lower bound that satisfy the fourth condition in Lemma 3, we will consider substrings of the form \(S[2m:2n]\), to make the endpoints conveniently even. We will argue that each such substring contains almost all the information from two substrings of \(R\): Speaking informally, the even-indexed bits in \(S[2m:2n]\) come from \(R[m:n]\). As the density of ones in \(R\) is approximately \(p\), the odd-indexed bits in \(S[2m:2n]\) will copied forward from approximately \(S[2pm:2pn]\), and these bits ultimately come from approximately \(R[pm:pn]\). Thus, \(S[2m:2n]\) contains all the information in approximately \((n-m)(1+p)\) bits of \(R\), meaning its Kolmogorov complexity cannot be much less than \((n-m)(1+p)\mathop{\mathrm{H}}(p)\).

Furthermore, we argue that this approximate bound holds (for appropriate choices of \(m\) and \(n\)) even when we condition on the information provided by the trailing heads. This is because, for sufficiently large \(n\) and \(m\) sufficiently close to \(n\), oblivious trailing heads with rational speeds can’t access \(S[2pm:2pn]\) while the leading head reads \(S[m:n]\). All information they access during this period is about other parts of \(R\), which are not informative about the pertinent substrings \(R[pm:pn]\) and \(R[m:n]\).

To formalize this intuitive argument, let \(G\) be an oblivious \(h\)-head finite-state gambler. Let \(\sigma_1,\ldots,\sigma_{h-1}\) be the rational trailing head speeds of \(G\), as in Observation 1, noting that \(p\), being irrational, is distinct from each of these speeds. Thus, each \(|\sigma_i n-pn|\) is linear in \(n\). We therefore have the following.

Fix \(\gamma_0,n_0\) as in Observation 5, and choose rational constants \(\gamma\in(\gamma_0,1)\), \(\varepsilon\in (0,1)\), and \[\alpha\in\left(1-(1+p)\frac{\mathop{\mathrm{H}}(p)}{2},1-(1+p)\frac{\mathop{\mathrm{H}}(p)}{2}+\varepsilon\right).\] Let \(n\geq n_0\) and \(m=\lfloor\gamma n\rfloor\) be sufficiently large to satisfy the first condition of Lemma 3 with this choice of \(\varepsilon\) and \(\alpha\). Let \[U=[0:2m]\cap\bigcup_{i=1}^{h-1}[2\sigma_i m-c_G,2\sigma_in+c_G],\] which satisfies the second condition of Lemma 3 and, by Observation 1, also satisfies the third condition. Then by Observation 5, we have \[\label{eq:disjoint} U\cap [\lfloor 2pm\rfloor,\lceil 2pn\rceil]=\emptyset.\tag{24}\]

Let \(A=[\lfloor pm\rfloor :\lfloor pn\rfloor]\cup[m:n]\) and \(B=[0:\lfloor pm\rfloor]\cup[\lfloor pn\rfloor:m]\), noting that \(A\) and \(B\) partition \([0:n]\). Roughly, \(R[A]\) is the part of \(R\) that pertains to \(S[2m:2n]\).

We now prove technical lemmas to assist in the proof of Theorem 3. Briefly, Lemma 4 tells us that \(S[2m:2n]\) contains almost all the information in \(R[A]\), and Lemma 5 tells us that \(R[B]\) contains almost all the information in \(S[U]\), which is approximately the part of \(S\) read by the trailing heads while the leading head reads \(S[2m:2n]\). Since \(R[A]\) and \(R[B]\) are disjoint parts of a \(\mu_p\)-Martin-Löf random sequence, they are essentially independent of each other, so these two lemmas imply that \(S[U]\) contains almost no information about \(S[m:n]\), yielding Lemma 6.

Proof. By the definition of \(F\), the even-indexed bits of \(S[2m:2n]\) are exactly \(R[m:n]\). Furthermore, given \(S[2m:2n]\), we can computationally recover \[R[\#_1(R[0:m]):\#_1(R[0:n])]\] using Algorithm 2.

By Lemma 1, the symmetric difference \[[\lfloor pm\rfloor:\lfloor pn\rfloor]\:\triangle\:[\#_1(R[0:m]):\#_1(R[0:n])]\] has cardinality \(O\big(\sqrt{n\log n}\big)\). Therefore, there is a computational process that, given \(R[\#_1(R[0:m]):\#_1(R[0:n])]\) and \(O\big(\sqrt{n\log n}\big)\) bits of additional information, could output \(R[\lfloor pm\rfloor :\lfloor pn\rfloor]\). By combining this with Algorithm 2, we have \[K(R[A]\mid S[2m:2n])=O\big(\sqrt{n\log n}\big).\qedhere\] ◻

Recalling our choice of \(\alpha\), Lemma 6 tells us that the fourth condition of Lemma 3 is satisfied if our choice of \(n\) is sufficiently large for the \(O\big(\sqrt{n\log n}\big)\) term to be at most \((n-m)(\alpha-(1-(1+p)\mathop{\mathrm{H}}(p)/2))\). We now apply Lemma 3 to prove the following.

We can choose \(\varepsilon\) arbitrarily close to 0, \(\alpha\) arbitrarily close to \(1-(1+p)\mathop{\mathrm{H}}(p)/2\), and \(\gamma\) arbitrarily close to \(1\), making \(1-(\alpha+\varepsilon)/\gamma\) arbitrarily close to \((1+p)\mathop{\mathrm{H}}(p)/2\). Although we only made this argument for rational values of \(\alpha\), \(\gamma\), and \(\varepsilon\), success on a sequence is a monotone property in \(s\), in that if \(s'<s\) and \(d_G^{(s')}\) succeeds on \(S\), then \(d_G^{(s)}\) also succeeds on \(S\); this is immediate from the definition of success. Thus, \[\inf\left\{s:d_G^{(s)}\text{ succeeds on }S\right\}\geq(1+p)\frac{\mathop{\mathrm{H}}(p)}{2}.\] As \(G\) was an arbitrary oblivious multi-head finite-state gambler, we conclude that \[\mathop{\mathrm{odim}}_{\mathrm{FS}}^{\mathop{\mathrm{MH}}}(S)\geq (1+p)\frac{\mathop{\mathrm{H}}(p)}{2}.\qedhere\]

7 Main Theorem↩︎

Given Theorems 2 and 3, proving our separation theorem is simply a matter of choosing an appropriate bias \(p\) for the underlying sequence \(R\).

While \(p=\frac{\sqrt{2}}{2}\) has the advantage of simplicity, the maximum separation from Theorems 2 and 3, namely, \(\max_{p\in[0,1]}p\frac{\mathop{\mathrm{H}}(p)}{2}\), is slightly greater. It is open whether this is the maximum possible separation between adaptive two-head finite-state strong predimension and oblivious multi-head finite-state dimension.

Building on the hierarchy theorem of Huang et al. [1], Cruz et al. [6] proved that for each \(h\geq 2\) there is a sequence \(Y\in\{0,1\}^\omega\) such that \[\mathop{\mathrm{adim}}_{\mathrm{FS}}^{(h-1)}(Y)\geq \mathop{\mathrm{oDim}}_{\mathrm{FS}}^{(h)}(Y)+\frac{1}{p_h},\] where \(p_h\) is the \(h\)^th prime. Choosing \(h=3\) and recalling 12 , this implies there is a sequence \(Y\in\{0,1\}^\omega\) with \[\mathop{\mathrm{aDim}}_{\mathrm{FS}}^{(2)}(Y)\geq\mathop{\mathrm{odim}}_{\mathrm{FS}}^{\mathop{\mathrm{MH}}}(Y)+0.2,\] in sharp contrast to the sequence \(S\) in Theorem 6. This points to a complex interplay between data access and sequence structure for multi-head gamblers, which merits further investigation.

References↩︎