Conditional normality and finite-state dimensions revisited

Alexander Shen

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.

Conditional normality and finite-state dimensions revisited

Résumé

Fichiers et liens (1)

Indicateurs

Détails