Algorithmic randomness over general spaces

Posted on May 16, 2012 by miyabe

News
May, 2012. In preparation to resubmit
Sep, 2011. Resubmitted a revised version
May 25, 2010. Submitted to a Journal

Title
Algorithmic randomness over general spaces

Type
Fullpaper

Journal
submitted

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 Papers | Leave a comment

Algorithmic interpretation of probability

Posted on May 15, 2012 by miyabe

Title
Algorithmic interpretation of probability

Type
Talk at Graduate School of Letters, Kyoto University on 29 May 2012.

Abstract
Philosophy of probability is one of the big problem in science
discussed so far.
In this talk I first review the history of philosophy of probability.
Then I introduce theory of algorithmic randomness and its
related topic, which is produced by the study of the mathematical
formalization of probability.
Finally I discuss the notion of probability from the algorithmic
point of view by seeing the results that has got recently.

Download
Slide in Japanese

Posted in Talks | Leave a comment

The limit of prediction and randomness

Posted on April 26, 2012 by miyabe

Title
The limit of prediction and randomness

Type
Talk at CS seminar in RIMS, Kyoto University on 26 Apr 2012.

Abstract
The former half is about the relation between differentiability and randomness.
I talk about why more computability is needed to characterize Schnorr randomness by differentiability.
The latter half is about the relation between Solomonoff’s induction and the differentiability.
I use a little different setting from Solomonoff’s induction to get a Schnorr randomness version
with long prediction.
I talk more about future work.

Download
Slide in Japanese

Posted in Talks | Leave a comment

The convergence rate of SLLN in the case of non-i.i.d.

Posted on March 27, 2012 by miyabe

Title
The convergence rate of SLLN in the case of non-i.i.d.

Type
Talk at “Annual meeting of Mathematical Society of Japan” on 26-29 Mar 2012.

Abstract
Japanese abstract

Download
Slides

Posted in Talks | Leave a comment

At which points are functions differentiable?

Posted on March 26, 2012 by miyabe

Title
At which points are functions differentiable?

Type
Talk at “Annual meeting of Mathematical Society of Japan” on 26-29 Mar 2012.

Abstract
Japanese abstract

Download
Slides

Posted in Talks | Leave a comment

Why the event with probability 0 happen

Posted on March 20, 2012 by miyabe

Title
Why the event with probability 0 happen

Type
Young-RICE: Young-Researchers for Improvements of College Education
20 Mar 2012

Abstract
Go to the Japanese page to see the abstract in Japanese.

Download
Japanese slide (3.1MB)

Posted in Talks | Leave a comment

Weak L^1-computability and Limit L^1-computability

Posted on March 12, 2012 by miyabe

News
Mar 12, 2012, Draft

Title
Weak L^1-computability and Limit L^1-computability

Type
Extended abstract

Journal
in preparation

Abstract
The class of the differences between two integral tests for Schnorr ran- domness is an important class related to Schnorr randomness. In this paper we study other randomness versions. We also claim that Solovay reducibility for lower semicomputable functions generalizes layerwise com- putability.

Download
in preparation

Posted in Papers | Leave a comment

L^1-computability and weak L^1-computability

Posted on February 24, 2012 by miyabe

Title
L^1-computability and weak L^1-computability

Type
Talk at “Kyoto computable analysis Symposium 2012″ on 24-27 Feb 2012.

Abstract
Computable functions are simple functions and
in Weihrauch approach computable functions are always continuous.
However there are some simple discontinuous functions such as the
floor function.
Therefore we need another mathematical notion to measure simplicity.
One candidate is L^1-computability, which was introduced by Pour-El
and Richard 1989.
In this talk I show you that more effectivised version of L^1-computability
has a strong connection with Schnorr randomness
and that some weaker versions of L^1-computability has connections
with some stronger randomness notions.

Download
slides

Posted in Talks | Leave a comment

Schnorr Layerwise Computability

Posted on February 22, 2012 by miyabe

Title
Schnorr Layerwise Computability

Type
Talk at “Workshop on Proof Theory and Computability Theory 2012″ on 20-23 Feb 2012.
Workshop website

Abstract
In order to formalize the notion of randomness mathematically,
the theory of algorithmic randomness uses computability theory.
Recent researches show that some notions in algorithmic randomness conversely
are useful to study computable analysis.
One example is layerwise computability defined by Hoyrup and Rojas 2009.
In this talk I introduce Schnorr layerwise computability,
which is a Schnorr-randomness version,
and explain why this is a more natural notion.

Download
slides

Posted in Talks | Leave a comment

An integral test for Schnorr randomness and its application

Posted on January 26, 2012 by miyabe

News
Jan 26, 2012, Submitted to a conference

Title
An integral test for Schnorr randomness and its application

Type
Fullpaper

Journal
Submitted

Abstract
The author proposed in the previous paper that a characterization of a randomness notion by integral tests is a useful tool to study the relation between algorithmic randomness and computable analysis. In this paper we give a version of Schnorr randomness. With this result we show the connection between L1-computability and Schnorr layerwise computability. Finally we apply them to study the points on which two Radon-Nikodym derivatives are equal.

Download
preprint

Posted in Papers | Leave a comment