An article was published in Mathematical Seminar Oct 2014.
Derandomization in Game-Theoretic Probability
News
27 Sep 2014, Online
3 Aug 2014, Accepted in SPA
12 Feb 2014. Submitted
Title
Derandomization in Game-Theoretic Probability
(with A. Takemura)
Type
Full paper
Journal
Stochastic Processes and their Applications 125, 39-59, 2015
Abstract
We give a general method for constructing a deterministic strategy
of Reality from a randomized strategy in game-theoretic probability.
The construction can be seen as derandomization in game-theoretic probability.
Download
preprint
Algorithmic randomness over general spaces
News
7 May 2014. Published online
Dec 2013. Accepted
May, 2012. Resubmit
Sep, 2011. Resubmitted a revised version
25 May, 2010. Submitted to a Journal
Title
Algorithmic randomness over general spaces
Type
Fullpaper
Journal
Math. Log. Quart. 60, No. 3, 184–204 (2014)
DOI 10.1002/malq.201200051
Download
preprint
Abstract
The study of Martin-Löf randomness on a computable metric space with a computable measure has had much progress recently.
In this paper we study Martin-Löf randomness on a more general space, that is, a computable topological space with a computable measure.
On such a space, Martin-Löf randomness may not be a natural notion because there is not a universal test, and Martin-Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT3 is a sufficient condition for the existence and the coincidence and study how much we can weaken the condition.
$L^1$-computability, layerwise computability and Solovay reducibility
News
17 July 2013, published
27 Mar 2013, accepted
19 Sep 2012, submitted
Title
L1-computability, layerwise computability and Solovay reducibility
Type
Full paper
Journal
Computability, 2:15-29, 2013.
Abstract
We propose a hierarchy of classes of functions that corresponds to the hierarchy of randomness notions. Each class of functions converges at the corresponding random points. We give various characterizations of the classes, that is, characterizations via integral tests, L1-computability and layerwise computability. Furthermore, the relation among these classes is formulated using Solovay reducibility for lower semicomputable functions.
Download
preprint
Correction
Proposition 2.3.
Let $\mu$ be a computable measure on a computable metric space.
Then there exists a computable sequence $\{r_n\}$ such that $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.
This statement should be the following.
Proposition 2.3.
Let $\mu$ be a computable measure on a computable metric space.
Then there exists a computable sequence $\{r_n\}$ such that
$\{ r_0,r_1, … \}$ is dense in the interval $(0 , \infty)$ and $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.
This problem was pointed out by K. Weihrauch on 19 Jan 2014. I appreciate his notice.
Uniform Kurtz randomness
News
4 Nov 2013, Published online
16 May 2013, Submitted to a Journal
Title
Uniform Kurtz randomness
(with Takayuki Kihara)
Type
Fullpaper
Journal
Journal of Logic and Computation, 24 (4): 863-882, 2014
doi: 10.1093/logcom/ext054
Abstract
We propose studying uniform Kurtz randomness, which is the uni- form relativization of Kurtz randomness. This notion has more natural properties than the usual relativization. For instance, van Lambalgen’s theorem holds for uniform Kurtz randomness while not for (the usual relativization of) Kurtz randomness. Another advantage is that lowness for uniform Kurtz randomness has many characterizations, such as those via complexity, martingales, Kurtz tt-traceability, and Kurtz dimensional measure.
Download
preprint