Hierarchies of Randomness Tests
| dc.contributor.author | REIMANN, Jan | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2006-02-10T06:54:28Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:00Z | |
| dc.date.available | 2006-02-10T06:54:28Z | en_US |
| dc.date.available | 2017-01-23T07:00:00Z | |
| dc.date.issued | 2006-02-10T06:54:28Z | en_US |
| dc.description.abstract | It is well known that Martin-Loef randomness can be characterized by a number of equivalent test concepts, based either on effective nullsets (Martin-Loef and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper entropy). These equivalences are not preserved as regards the partial randomness notions induced by effective Hausdorff measures or partial incompressibility. Tadaki as well as Calude, Staiger and Terwijn studied several concepts of partial randomness, but for some of them the exact relations remained unclear. In this paper we will show that they form a proper hierarchy of randomness notions, namely for any rho where rho(x) is 2 to the power of -|x|s and s is a rational number satisfying 0<s<1, the Martin-Loef rho-tests are strictly weaker than Solovay rho-tests which in turn are strictly weaker than strong Martin-Loef rho-tests. These results also hold for a more general class of rho introduced as unbounded premeasures. | en_US |
| dc.format.extent | 883931 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1912 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRB2/06 | en_US |
| dc.title | Hierarchies of Randomness Tests | en_US |
| dc.type | Technical Report | en_US |