Derandomization in game-theoretic probability

News
13 Nov 2014, the slide file was uploaded

Title
Derandomization in game-theoretic probability

Type
GTP 2014: Fifth Workshop on Game-Theoretic Probability and Related Topics

Download
miyabe-gtp2014

Posted in Talks | Leave a comment

Using Almost-Everywhere Theorems from Analysis to Study Randomness

News
3 Nov 2014. Submitted

Title
Using Almost-Everywhere Theorems from Analysis to Study Randomness
(with Jing Zhang and Andre Nies)

Type
Full paper

Journal
Submitted
arXiv

Abstract
We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin-Lo ̈f (ML) randomness. We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent.
(1) all effectively closed classes containing z have density 1 at z.
(2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z.
(3) z is a Lebesgue point of each lower semicomputable integrable function.
We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff’s pointwise ergodic theorem. Lastly we study randomness notions for density of $\Pi^0_n$ and $\Sigma^1_1$ classes.

Posted in Publication | Leave a comment

Mathematical Seminar, Oct 2014

An article was published in Mathematical Seminar Oct 2014.

Posted in Publication | Leave a comment

NII Shonan Meeting “Algorithmic Randomness and Complexity”, 8-12 Sep, 2014

NII Shonan Meeting “Algorithmic Randomness and Complexity”

The webpage for participants.

Posted in Diary | Leave a comment

Betting game and mathematics

News
17 Aug 2014, the slide file was uploaded

Title
Betting game and mathematics

Type
Summer Seminar of Meiji University for high school students

Download
miyabe-summer-seminar-2014

Posted in Talks | Leave a comment

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

Posted in Publication | Leave a comment

Schnorr randomness versions of K, C, LR, vL-reducibilities

News
19 June 2014, the slide file was uploaded
13 June 2014, the talk was given

Title
Schnorr randomness versions of K, C, LR, vL-reducibilities

Type
Conference on Computability, Complexity and Randomness CCR 2014

Download
miyabe-ccr2014

Posted in Talks | Leave a comment

Mathematical formulation of “unpredictability” ~Non-use of probabilistic models~

News
13 May 2014, Abstract in Japanese was uploaded

Title
Mathematical formulation of “unpredictability” ~Non-use of probabilistic models~

Type
Seminar Talk
語ろう「数理解析」

Download

Posted in Talks | Leave a comment

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.

Posted in Publication | Leave a comment

Reducibilities relating to Schnorr randomness

News
22 Sep 2014. Accepted to publish in TOCS
24 Mar 2014. Submitted

Title
Reducibilities relating to Schnorr randomness

Type
Full paper

Journal
Theory of Computing Systems.
DOI: 10.1007/s00224-014-9583-3

Abstract
Some measures of randomness have been introduced for Martin- L ̈of randomness such as K-reducibility, C-reducibility and vL-reducibility. In this paper we study Schnorr-randomness versions of these reducibilities. In particular, we characterize the computably-traceable reducibility via relative Schnorr randomness, which was asked in Nies’ book (Problem 8.4.22). We also show that Schnorr reducibility implies uniform-Schnorr-randomness version of vL-reducibility, which is the Schnorr-randomness version of the result that K-reducibility implies vL-reducibility.

Download
preprint

Posted in Publication | Leave a comment