Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.16034 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914606286372864 |
|---|---|
| author | Cruz, Julianne Glashausser, Sho Li, Xiaoyuan Lutz, Neil |
| author_facet | Cruz, Julianne Glashausser, Sho Li, Xiaoyuan Lutz, Neil |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_16034 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Adaptive Multi-Head Finite-State Gamblers Cruz, Julianne Glashausser, Sho Li, Xiaoyuan Lutz, Neil Information Theory 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. |
| title | Adaptive Multi-Head Finite-State Gamblers |
| topic | Information Theory |
| url | https://arxiv.org/abs/2603.16034 |