Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProbability Measures and Effective Randomness
195
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the question, ``For which reals $x$ does there exist a measure $mu$ such that $x$ is random relative to $mu$? We show that for every nonrecursive $x$, there is a measure which makes $x$ random without concentrating on $x$. We give several conditions on $x$ equivalent to there being continuous measure which makes $x$ random. We show that for all but countably many reals $x$ these conditions apply, so there is a continuous measure which makes $x$ random. There is a meta-mathematical aspect of this investigation. As one requires higher arithmetic levels in the degree of randomness, one must make use of more iterates of the power set of the continuum to show that for all but countably many $x$s there is a continuous $mu$ which makes $x$ random to that degree.
rate research
Read More
We investigate which infinite binary sequences (reals) are effectively random with respect to some continuous (i.e., non-atomic) probability measure. We prove that for every n, all but countably many reals are n-random for such a measure, where n indicates the arithmetical complexity of the Martin-Lof tests allowed. The proof is based on a Borel determinacy argument and presupposes the existence of infinitely many iterates of the power set of the natural numbers. In the second part of the paper we present a metamathematical analysis showing that this assumption is indeed necessary. More precisely, there exists a computable function G such that, for any n, the statement `All but countably many reals are G(n)-random with respect to a continuous probability measure cannot be proved in $ZFC^-_n$. Here $ZFC^-_n$ stands for Zermelo-Fraenkel set theory with the Axiom of Choice, where the Power Set Axiom is replaced by the existence of n-many iterates of the power set of the natural numbers. The proof of the latter fact rests on a very general obstruction to randomness, namely the presence of an internal definability structure.
We show that if a real $x$ is strongly Hausdorff $h$-random, where $h$ is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure $mu$ such that the $mu$-measure of the basic open cylinders shrinks according to $h$. The proof uses a new method to construct measures, based on effective (partial) continuous transformations and a basis theorem for $Pi^0_1$-classes applied to closed sets of probability measures. We use the main result to give a new proof of Frostmans Lemma, to derive a collapse of randomness notions for Hausdorff measures, and to provide a characterization of effective Hausdorff dimension similar to Frostmans Theorem.
We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the dissipation function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing degrees. In particular, we show that every $Delta^0_2$-degree contains an NCR element.
We show that the (truth-table) Medvedev degree KLR of Kolmogorov--Loveland randomness coincides with that of Martin Lof randomness, MLR, answering a question of Miyabe. Next, an analogue of complex packing dimension is studied which gives rise to a set of weak truth-table Medvedev degrees isomorphic to the Turing degrees.
The paper considers quantitati
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
