Julianne Cruz

Julianne Cruz, Sho Glashausser, Neil Lutz

In the setting of multi-head finite-state dimensions, trailing heads lag behind a leading head, accessing past data to aid a finite-state gambler placing bets on successive bits read by the leading head. Cruz, Glashausser, Li, and Lutz (2026) proved that, for any fixed number of trailing heads, adaptive (data-dependent) movement rules can strictly outperform oblivious (data-independent) movement schedules. In this paper we strengthen that separation by proving that a single trailing head with adaptive movements can outperform, by a large and uniform margin, arbitrarily many trailing heads with oblivious movements. Formally, our main theorem states that there is a binary sequence whose adaptive two-head finite-state strong dimension is less than its oblivious multi-head finite-state dimension, and that the gap is greater than 0.3.

Julianne Cruz, Sho Glashausser, Xiaoyuan Li et al.

Multi-head finite-state dimensions and predimensions quantify the predictability of a sequence by a gambler with trailing heads acting as "probes to the past." These additional heads allow the gambler to exploit patterns that are simple but non-local, such as in a sequence $S$ with $S[n]=S[2n]$ for all $n$. In the original definitions of Huang, Li, Lutz, and Lutz (2025), the head movements were required to be oblivious (i.e., data-independent). Here, we introduce a model in which head movements are adaptive (i.e., data-dependent) and compare it to the oblivious model. We establish that for each $h\geq 2$, adaptivity enhances the predictive power of $h$-head finite-state gamblers, in the sense that there are sequences whose oblivious $h$-head finite-state predimensions strictly exceed their adaptive $h$-head finite-state predimensions. We further prove that adaptive finite-state predimensions admit a strict hierarchy as the number of heads increases, and in fact that for all $h\geq 1$ there is a sequence whose adaptive $(h+1)$-head finite-state predimension is strictly less than its adaptive $h$-head predimension.