Probability Symposium, RIMS Workshop Dec. 19-22, 2016 Recent progress on conditional randomness Hayato Takahashi1 7 1 0 The set of Hippocratic random sequences w.r.t. P is defined as the com- 2 pliment of the effective null sets w.r.t. P and denote it by RP. In particular n if P is computable it is called Martin-Lo¨f random sequences. a Lambalgen’s theorem (1987) [9]says that apair of sequences (x∞,y∞) ∈ J Ω2 is Martin-Lo¨f (ML) random w.r.t. the product of uniform measures iff 2 x∞ is ML-random and y∞ is ML-random relative to x∞, where Ω is the ] set of infinite binary sequences. In [10, 5, 6, 7], generalized Lambalgen’s O theorem is studied for computable correlated probabilities. L Let S be the set of finite binary strings and ∆(s) := {sx∞|x∞ ∈ Ω} . h for s ∈ S, where sx∞ is the concatenation of s and x∞. Let X = Y = Ω t a and P be a computable probability on X × Y. P and P are marginal m X Y distribution on X and Y, respectively. In the following we write P(x,y) := [ P(∆(x)×∆(y)) and P(x|y) := P(∆(x)|∆(y)) for x,y ∈ S. 1 Let RP be the set of ML-random points and RPy∞ := {x∞ | (x∞,y∞) ∈ v RP}. In [5, 6], it is shown that conditional probabilities exist for all random 6 7 parameters, i.e., 4 6 ∀x ∈S, y∞ ∈ RPY P(x|y∞):= lim P(x|y) (the right-hand-side exist) 0 y→y∞ . 1 0 and P(·|y∞) is a probability on (Ω,B) for each y∞ ∈RPY. 7 LetRP(·|y∞),y∞ bethesetofHippocraticrandomsequencesw.r.t.P(·|y∞) 1 : with oracle y∞. v i X Theorem 1 ([5, 6, 7]) Let P be a computable probability on X×Y. Then r a RPy∞ ⊇ RP(·|y∞),y∞ for all y∞ ∈ RPY. (1) Fix y∞ ∈ RPY and suppose that P(·|y∞) is computable with oracle y∞. Then RPy∞ = RP(·|y∞),y∞. (2) 1 [email protected] This work was done when the author was with Gifu University and supported by KAK- ENHI (24540153). It is known that there is a non-computable conditional probabilities [4] and in [2] Bauwens showed an example that violates the equality in (2) when the conditional probability is not computable with oracle y∞. In [8], an example that for all y∞, the conditional probabilities are not computable with oracle y∞ and (2) holds. A survey on the randomness for conditional probabilities is shown in [1]. Nextwestudymutuallysingularconditionalprobabilities. In[3],Hanssen showed that for Bernoulli model P(·|θ), RP(·|θ) = RP(·|θ),θ for all θ. (3) We generalize Hanssen’stheorem (3)formutually singularconditional prob- abilities. In [5, 7], equivalent conditions for mutually singular conditional probabilities are shown. Theorem 2 ([5, 7]) Let P be a computable probability on X × Y, where X = Y = Ω. The following six statements are equivalent: (1) P(·|y)⊥ P(·|z) if ∆(y)∩∆(z) = ∅ for y,z ∈ S. (2) RP(·|y)∩RP(·|z) =∅ if ∆(y)∩∆(z) = ∅ for y,z ∈ S. (3) PY|X(·|x) converges weakly to Iy∞ as x → x∞ for (x∞,y∞) ∈ RP, where Iy∞ is the probability that has probability of 1 at y∞. (4) RPy∞ ∩RPz∞ = ∅ if y∞ 6= z∞. (5) There exists f : X → Y such that f(x∞) = y∞ for (x∞,y∞) ∈ RP. (6) There exists f : X → Y and Y′ ⊂ Y such that P (Y′) = 1 and f = Y y∞, P(·;y∞)−a.s. for y∞ ∈ Y′. Generalized form of Hanssen’s theorem (3) is as follows. Theorem 3 LetP beacomputable probability onX×Y, where X = Y = Ω. Under one of the condition of Theorem 2, we have RPy∞ ⊇ RP(·|y∞) for all y∞ ∈ RPY. Fix y∞ ∈ RPY and suppose that P(·|y∞) is computable with oracle y∞. Then RPy∞ = RP(·|y∞) = RP(·|y∞),y∞. References [1] B. Bauwens, A. Shen, and H. Takahashi. Conditional probabilities and van Lambalgen theorem revisited. arXiv:1607.04240, 2016. [2] Bruno Bauwens. Conditional measure and the violation of van Lambalgen’s theorem for Martin-l¨of randomness. http://arxiv.org/abs/1103.1529, 2015. [3] BjørnKjosHanssen. Theprobabilitydistributionasacomputationalresource for randomness testing. Journal of Logic and Analysis, 2(10):1–13,2010. [4] D. M. Roy. Computability, inference and modeling in probabilistic program- ming. PhD thesis, MIT, 2011. [5] H. Takahashi. Bayesian approach to a definition of random sequences and its applications to statistical inference. In 2006 IEEE International Symposium on Information Theory, pages 2180–2184,July 2006. [6] H.Takahashi. Onadefinitionofrandomsequenceswithrespecttoconditional probability. Inform. and Compt., 206:1375–1382,2008. [7] H. Takahashi. Algorithmic randomness and monotone complexity on product space. Inform. and Compt., 209:183–197,2011. [8] H. Takahashi. Generalization of van lambalgen’s theorem and blind random- ness for conditional probabilities, 2014. arXiv:1310.0709v3. [9] M. van Lambalgen. Random sequences. PhD thesis, Universiteit van Amster- dam, 1987. [10] V. G. Vovk and V. V. V’yugin. On the empirical validity of the Bayesian method. J. R. Stat. Soc. B, 55(1):253–266,1993.