Published January 24, 2014
| Version v1
Journal article
A notion of graph likelihood and an infinite monkey theorem
- 1. Department of Computer Science, and Centre of Mathematics and Physics in the Life Sciences and Experimental Biology, University College London, London WC1E 6BT (United Kingdom)
- 2. Department of Mathematics, University of Haifa, Haifa 31905 (Israel)
- 3. Department of Computer Science, and Department of Physics and Astronomy, University College London, WC1E 6BT London (United Kingdom)
Description
We play with a graph-theoretic analogue of the folklore infinite monkey theorem. We define a notion of graph likelihood as the probability that a given graph is constructed by a monkey in a number of time steps equal to the number of vertices. We present an algorithm to compute this graph invariant and closed formulas for some infinite classes. We have to leave the computational complexity of the likelihood as an open problem. (paper)
Availability note (English)
Available from http://dx.doi.org/10.1088/1751-8113/47/3/035101Additional details
Identifiers
Publishing Information
- Journal Title
- Journal of Physics. A, Mathematical and Theoretical (Online)
- Journal Volume
- 47
- Journal Issue
- 3
- Journal Page Range
- [8 p.]
- ISSN
- 1751-8121
INIS
- Country of Publication
- United Kingdom
- Country of Input or Organization
- International Atomic Energy Agency (IAEA)
- INIS RN
- 46035396
- Subject category
- S71: CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSICS;
- Descriptors DEI
- ALGORITHMS; DIAGRAMS; GRAPH THEORY; PROBABILITY
- Descriptors DEC
- INFORMATION; MATHEMATICAL LOGIC; MATHEMATICS