Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Generative Complexity and Randomness of Finite Sequence of Symbols

Generative Complexity and Randomness of Finite Sequence of Symbols Here proposed are complexity measures of finite sequences of symbols, based on finite automata. Basic properties of these measures are demonstrated. The relation between the complexity for generating a sequence and the randomness of the generated sequence is also discussed. First, the notion of A-complexity is defined and characterized using ultimately periodic sequences (Theorem 1). A refined measure, F-complexity, is then introduced. It is shown that highly random sequences have large F-complexities (Theorem 2), but the converse is not always true (Theorem 3). Finally, the c-complexity is proposed to remedy this shortcoming of F-complexity. It includes as special cases both A-complexity and F-complexity. It is shown that certain sequences with high c-complexities, complete periodic sequences, are equidistributed (Theorem 4). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Behaviormetrika Springer Journals

Generative Complexity and Randomness of Finite Sequence of Symbols

Nozaki, Akihiro
Behaviormetrika , Volume 3 (3) – Feb 15, 1976
Download PDF
9 pages

Loading next page...
 
/lp/springer-journals/generative-complexity-and-randomness-of-finite-sequence-of-symbols-jK1EricsdD
Publisher
Springer Journals
Copyright
Copyright
Subject
Statistics; Statistical Theory and Methods; Statistics for Business, Management, Economics, Finance, Insurance; Statistics for Engineering, Physics, Computer Science, Chemistry and Earth Sciences
ISSN
0385-7417
eISSN
1349-6964
DOI
10.2333/bhmk.3.29
Publisher site
See Article on Publisher Site

Abstract

Here proposed are complexity measures of finite sequences of symbols, based on finite automata. Basic properties of these measures are demonstrated. The relation between the complexity for generating a sequence and the randomness of the generated sequence is also discussed. First, the notion of A-complexity is defined and characterized using ultimately periodic sequences (Theorem 1). A refined measure, F-complexity, is then introduced. It is shown that highly random sequences have large F-complexities (Theorem 2), but the converse is not always true (Theorem 3). Finally, the c-complexity is proposed to remedy this shortcoming of F-complexity. It includes as special cases both A-complexity and F-complexity. It is shown that certain sequences with high c-complexities, complete periodic sequences, are equidistributed (Theorem 4).

Journal

Behaviormetrika – Springer Journals

Published: Feb 15, 1976

References

  • On the length of programs for computing finite binary sequences
    Chaitin, GJ
  • On the length of programs for computing finite binary sequences: statistical consideration
    Chaitin, GJ
  • The Art of Computer Programming vol. 2
    Knuth, DE
  • Three approaches to the definition of the concept “quantity of information,”
    Kolmogorov, AN