تقرير
Finite-State Relative Dimension, dimensions of A. P. subsequences and a Finite-State van Lambalgen's theorem
| العنوان: | Finite-State Relative Dimension, dimensions of A. P. subsequences and a Finite-State van Lambalgen's theorem |
|---|---|
| المؤلفون: | Nandakumar, Satyadev, Pulari, Subin, S, Akhil |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Information Theory, 03D32, 68P30, 68Q45 |
| الوصف: | Finite-state dimension (Dai, Lathrop, Lutz, and Mayordomo (2004)) quantifies the information rate in an infinite sequence as measured by finite-state automata. In this paper, we define a relative version of finite-state dimension. The finite-state relative dimension $dim_{FS}^Y(X)$ of a sequence $X$ relative to $Y$ is the finite-state dimension of $X$ measured using the class of finite-state gamblers with an oracle access to $Y$. We show its mathematical robustness by equivalently characterizing this notion using the relative block entropy rate of $X$ conditioned on $Y$. We derive inequalities relating the dimension of a sequence to the relative dimension of its subsequences along any arithmetic progression (A.P.). These enable us to obtain a strengthening of Wall's Theorem on the normality of A.P. subsequences of a normal number, in terms of relative dimension. In contrast to the original theorem, this stronger version has an exact converse yielding a new characterization of normality. We also obtain finite-state analogues of van Lambalgen's theorem on the symmetry of relative normality. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2305.06570 |
| رقم الأكسشن: | edsarx.2305.06570 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |