Show simple item record

dc.contributor.authorBienvenu, Laurenten_US
dc.contributor.authorGacs, Peteren_US
dc.contributor.authorHoyrup, Mathieuen_US
dc.contributor.authorRojas, Cristobalen_US
dc.contributor.authorShen, Alexanderen_US
dc.date.accessioned2018-06-19T13:24:15Z
dc.date.available2018-06-19T13:24:15Z
dc.date.issued2011-10-01
dc.identifierhttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000295983200004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e74115fe3da270499c3d65c9b17d654
dc.identifier.citationLaurent Bienvenu, Peter Gacs, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen. 2011. "Algorithmic tests and randomness with respect to a class of measures." Proceedings Of The Steklov Institute Of Mathematics, Volume 274, Issue 1, pp. 34 - 89 (56).
dc.identifier.issn0081-5438
dc.identifier.issn1531-8605
dc.identifier.urihttps://hdl.handle.net/2144/29413
dc.description.abstractThis paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B p have the important property that p can be recovered from each random sequence of B p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.en_US
dc.description.sponsorshipThe paper was written with the financial support of the grant NAFIT ANR-08-EMER-008-01 and of the Russian Foundation for Basic Research (project no. 09-01-00709-a). (09-01-00709-a - Russian Foundation for Basic Research; NAFIT ANR-08-EMER-008-01)en_US
dc.format.extentp. 34 - 89en_US
dc.languageEnglish
dc.publisherMAIK NAUKA/INTERPERIODICA/SPRINGERen_US
dc.relation.ispartofProceedings Of The Steklov Institute Of Mathematics
dc.subjectScience & technologyen_US
dc.subjectPhysical sciencesen_US
dc.subjectMathematics, applieden_US
dc.subjectMathematicsen_US
dc.subjectMartin-Löf randomnessen_US
dc.subjectProbability measuresen_US
dc.subjectRandom sequencesen_US
dc.subjectPure mathematicsen_US
dc.subjectApplied mathematicsen_US
dc.titleAlgorithmic tests and randomness with respect to a class of measuresen_US
dc.typeArticleen_US
dc.identifier.doi10.1134/S0081543811060058
pubs.elements-sourceweb-of-scienceen_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US


This item appears in the following Collection(s)

Show simple item record