Category: Publication

News
May 4, 2018. Accepted by AOP

Title
Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales: a game-theoretic approach
(with T. Sasai and A. Takemura)

Type
Full paper

Journal
Annals of Probability,
Annals of Probability, Vol. 47, No. 2, 1136-1161, March 2019.

Abstract
We prove an Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales. Our proof is given in the framework of the game-theoretic probability of Shafer and Vovk. As many other game-theoretic proofs, our proof is self-contained and explicit.

download
arXiv

News
Sep 2018, accepted
11 Mar 2018, submitted to a Journal

Title
Muchnik degrees and Medvedev degrees of the randomness notions

Type
Research paper

Publication
The joint post-proceedings for ALC2015 and ALC2017 published via World Scientific

Proceedings of the 14th and 15th Asian Logic Conferences, pp. 108-128 (2019) January

Abstract
The main theme of this paper is computational power when a machine is allowed to access random sets.
The computability depends on the randomness notions and we compare them by Muchnik and Medvedev degrees.
The central question is whether, given an random oracle, one can compute a more random set.
The main result is that, for each Turing functional,
there exists a Schnorr random set whose output is not computably random.

download
Muchnikdegrees

News
1 Feb 2016, accepted by TOCS

Title
Coherence of reducibilities with randomness notions

Type
Full paper

Journal
Theory of Computing Systems – October 2018, Volume 62, Issue 7, pp 1599–1619
DOI: https://doi.org/10.1007/s00224-017-9752-2

Abstract
Loosely speaking, when $A$ is “more random” than $B$ and $B$ is “random”,
then $A$ should be random.
The theory of algorithmic randomness has some formulations of “random” sets
and “more random” sets.
In this paper, we study which pairs $(R,r)$ of randomness notions $R$
and reducibilities $r$ have the follwing property:
if $A$ is $r$-reducible to $B$ and $A$ is $R$-random,
then $B$ should be $R$-random.
The answer depends on the notions $R$ and $r$.
The implications hold for most pairs, but not for some.
We also give characterizations of $n$-randomness via complexity.

download
preprint

News
8 Aug, 2017. Online
28 July 2017. accepted by SPA

Title
Relation between the rate of convergence of strong law of large numbers and the rate of concentration of Bayesian prior in game-theoretic probability
(with R. Sato and A. Takemura)

Type
Full paper

Journal
Stochastic Processes and their Applications
Volume 128, Issue 5, May 2018, Pages 1466-1484
The page at SPA

Abstract
We study the behavior of the capital process of a continuous Bayesian mixture of fixed proportion
betting strategies in the one-sided unbounded forecasting game in game-theoretic probability. We
establish the relation between the rate of convergence of the strong law of large numbers in the selfnormalized
form and the rate of divergence to infinity of the prior density around the origin. In
particular we present prior densities ensuring the validity of Erdos–Feller–Kolmogorov–Petrowsky ˝
law of the iterated logarithm.

download
arXiv

News
19 Mar 2018, online
5 Mar 2018, accepted by JLA

Title
Randomness and Solovay degrees
(with A. Nies and F. Stephan)

Type
Full paper

Journal
Journal of Logic and Analysis, Vol 10, pp.1–13, 2018.
Open access

Abstract
We consider the behaviour of Schnorr randomness, a randomness notion weaker than Martin-L\”of’s, for left-r.e. reals under Solovay reducibility. Contrasting with results on Martin-L\”of-randomenss, we show that Schnorr randomness is not upward closed in the Solovay degrees. Next, some left-r.e. Schnorr random $\alpha$ is the sum of two left-r.e. reals that are far from random. We also show that the left-r.e. reals of effective dimension $>r$, for some rational $r$, form a filter in the Solovay degrees.

download
coromandel_JLA_final