Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2403.01534 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916988721299456 |
|---|---|
| author | Shen, Alexander |
| author_facet | Shen, Alexander |
| contents | The notion of a normal bit sequence was introduced by Borel in 1909; it was the first definition of an individual random object. Normality is a weak notion of randomness requiring only that all $2^n$ factors (substrings) of arbitrary length~$n$ appear with the same limit frequency $2^{-n}$. Later many stronger definitions of randomness were introduced, and in this context normality found its place as ``randomness against a finite-memory adversary''. A quantitative measure of finite-state compressibility was also introduced (the finite-state dimension) and normality means that the finite state dimension is maximal (equals~$1$).
Recently Nandakumar, Pulari and S (2023) introduced the notion of relative finite-state dimension for a binary sequence with respect to some other binary sequence (treated as an oracle), and the corresponding notion of conditional (relative) normality. (Different notions of conditional randomness were considered before, but not for the finite memory case.) They establish equivalence between the block frequency and the gambling approaches to conditional normality and finite-state dimensions.
In this note we revisit their definitions and explain how this equivalence can be obtained easily by generalizing known characterizations of (unconditional) normality and dimension in terms of compressibility (finite-state complexity), superadditive complexity measures and gambling (finite-state gales), thus also answering some questions left open in the above-mentioned paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_01534 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conditional normality and finite-state dimensions revisited Shen, Alexander Information Theory Statistics Theory 68Q45 F.1.1 The notion of a normal bit sequence was introduced by Borel in 1909; it was the first definition of an individual random object. Normality is a weak notion of randomness requiring only that all $2^n$ factors (substrings) of arbitrary length~$n$ appear with the same limit frequency $2^{-n}$. Later many stronger definitions of randomness were introduced, and in this context normality found its place as ``randomness against a finite-memory adversary''. A quantitative measure of finite-state compressibility was also introduced (the finite-state dimension) and normality means that the finite state dimension is maximal (equals~$1$). Recently Nandakumar, Pulari and S (2023) introduced the notion of relative finite-state dimension for a binary sequence with respect to some other binary sequence (treated as an oracle), and the corresponding notion of conditional (relative) normality. (Different notions of conditional randomness were considered before, but not for the finite memory case.) They establish equivalence between the block frequency and the gambling approaches to conditional normality and finite-state dimensions. In this note we revisit their definitions and explain how this equivalence can be obtained easily by generalizing known characterizations of (unconditional) normality and dimension in terms of compressibility (finite-state complexity), superadditive complexity measures and gambling (finite-state gales), thus also answering some questions left open in the above-mentioned paper. |
| title | Conditional normality and finite-state dimensions revisited |
| topic | Information Theory Statistics Theory 68Q45 F.1.1 |
| url | https://arxiv.org/abs/2403.01534 |