Relation between the rate of convergence of strong law of large numbers and the rate of concentration of Bayesian prior in game-theoretic probability

履歴
2017年8月8日 オンライン
2017年7月28日 SPA受理

タイトル
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)

種類
正論文

国際会議と雑誌
Stochastic Processes and their Applications
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.

ダウンロード
arXiv

Coherence of reducibilities with randomness notions

履歴
2017年2月1日 TOCS受理

タイトル
Coherence of reducibilities with randomness notions

種類
正論文

国際会議と雑誌
TOCS, post proceedings of CCR2016

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.

ダウンロード
preprint

Using Almost-Everywhere Theorems from Analysis to Study Randomness

履歴
2016年10月10日 オンライン出版
2016年2月29日 BSL受理
2015年5月 再投稿
2014年11月3日 投稿

タイトル
Using Almost-Everywhere Theorems from Analysis to Study Randomness
(with Jing Zhang and Andre Nies)

種類
正論文

国際会議と雑誌
The Bulletin of Symbolic Logic, Volume 22, Issue 3
September 2016, pp. 305-331
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.

ダウンロード

Reducibilities relating to Schnorr randomness

履歴
2014年9月22日 受理
2014年3月24日 投稿

タイトル
Reducibilities relating to Schnorr randomness

種類
正論文

雑誌
Theory of Computing Systems, 58(3), 441-462, 2016.
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.

ダウンロード
プレプリント