{"ID":2865627,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.22912","arxiv_id":"2509.22912","title":"Multi-Head Finite-State Dimension","abstract":"We introduce multi-head finite-state dimension, a generalization of finite-state dimension in which a group of finite-state agents (the heads) with oblivious, one-way movement rules, each reporting only one symbol at a time, enable their leader to bet on subsequent symbols in an infinite data stream. In aggregate, such a scheme constitutes an $h$-head finite state gambler whose maximum achievable growth rate of capital in this task, quantified using betting strategies called gales, determines the multi-head finite-state dimension of the sequence. The 1-head case is equivalent to finite-state dimension as defined by Dai, Lathrop, Lutz and Mayordomo (2004). In our main theorem, we prove a strict hierarchy as the number of heads increases, giving an explicit sequence family that separates, for each positive integer $h$, the earning power of $h$-head finite-state gamblers from that of $(h+1)$-head finite-state gamblers. We prove that multi-head finite-state dimension is stable under finite unions but that the corresponding quantity for any fixed number $h\u003e1$ of heads--the $h$-head finite-state predimension--lacks this stability property.","short_abstract":"We introduce multi-head finite-state dimension, a generalization of finite-state dimension in which a group of finite-state agents (the heads) with oblivious, one-way movement rules, each reporting only one symbol at a time, enable their leader to bet on subsequent symbols in an infinite data stream. In aggregate, such...","url_abs":"https://arxiv.org/abs/2509.22912","url_pdf":"https://arxiv.org/pdf/2509.22912v2","authors":"[\"Xiang Huang\",\"Xiaoyuan Li\",\"Jack H. Lutz\",\"Neil Lutz\"]","published":"2025-09-26T20:40:46Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.FL\",\"math.OC\"]","methods":"[]","has_code":false}