Definability of Randomness via Another Randomness
NingNing Peng
Join work with Kojiro Higuchi
Mathematical Institute, Tohoku University.
sa8m42@math.tohoku.ac.jp

May. 15, 2013
ELC Workshop on Randomness and Probability Through Computability

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Outline

1

Questions

2

Randomness Notions

3

Answers to Questions
Positive Answer
Negative Answer

4

SummaryMay. 15, 2013 ELC Workshop on RandomNingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Questions

1. Questions

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
Another
University.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Questions

Questions
Question 1
Can we define some randomness notions in terms of another randomness
notions?

Question 2
How can we define it?

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Questions

Questions
Question 1
Can we define some randomness notions in terms of another randomness
notions?

Question 2
How can we define it?
Liang Yu: Characterizing strong randomness via Martin-Löfrandomness. Annals of Pure and Applied Logic, vol. 163, no. 3, pp.
214-224 (2012).

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohokuAnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Questions

Question 1
Can we define some randomness notions in terms of another randomness
notions?
Question 2
How can we define it?

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Questions

Question 1
Can we define some randomness notions in terms of another randomness
notions?
Question 2
How can we define it?
Let R and S be two randomness notions.
Questoin 1’TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?

where X -R and X -S are relativizations of R and S to X , respectively.
Question 2’
What kinds ofsatisfy above relations ?

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
Another
University.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

2. Randomness Notions

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

ML-randomness
ML-randomness is a central notion of algorithmic randomness for subsets
of N, which defined in the following way.
Definition (Martin-Löf , 1966)(i) A Martin-Löf test, or ML-test for short, is a uniformly c.e. sequence(Gm )m2N of open sets such that 8m 2 N µ(Gm )  2 m .
T(ii) A set Z ✓ N fails the test if Z 2 m Gm , otherwise Z passes the test.

(iii) Z is ML-random if Z passes each ML-test.

Let MLR = {X | X is ML-random }.
Let X-MLR={Z | Z is ML-random relative to X }May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

Weak 2-randomness

Weak 2-randomness, like ML-randomness, is defined in terms of tests.
Definition (Kurtz, 1981)(i) A generalized ML-test
is a uniformly c.e. sequence (Gm )m2N of open
Tsets such that µ( m Gm ) = 0.

(ii) Z is weakly 2-random if it passes every generalized ML-test.
Let W 2R = {X | X is weakly 2-random }.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

Schnorr randomness

Definition (Schnorr, 1971)
A Schnorr test is a ML-test (Gm )m2N such that µG
Tm is computableuniformly in m. A set Z ✓ N fails the test if Z 2 m Gm , otherwise Z
passes the test. Z is Schnorr random if Z passes each Schnorr test.
Let SR = {X | X is Schnorr-random }.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

Martingale
Another important notion of randomness is computable randomness, whose
definition involves the concept of a martingle.
Definition
A martingale is a function d : 2<N ! R 0 that satisfies for every1)
the averaging condition d ( ) = d( 0)+d(.
22 2<NA martingale d succeeds on a set A if lim supn!1 d (A n) = 1.
Definition
We say that Z is computably random if no computable martingale succeeds
on Z .

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions......
weak 2-randomness

ML-randomnesscomputably randomness
Schnorr randomness......

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

Lowness and Higness

Definition
Let R and S be two randomness notions. We identify these notions withthe sets of all random reals in the sense of these notions.
Low(R, S) = {X 2 2! : R ⇢ X -S}

High(R, S) = {X 2 2! : X -R ⇢ S}

where X -R and X -S are relativizations of R and S to X , respectively.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Randomness Notions

RemarkQuestoin 1’TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?
We can prove easily Q1’ is equivalent to Q1”:

Questoin 1”
TS
R = X 2Low(R,S) X -S orX 2High(R,S) X -R = S ?

TTThis is because that: R ⇢ X 2low (R,S) X S ⇢ X 2 X S for any⇢ low (R, S). And if satisfies the first equality of Q1’, then⇢ low (R, S).

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
Another
University.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

3. Answers to Questions

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer;0 -SR vs MLR
Questoin 1’TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?

where X -R and X -S are relativizations of R and S to X , respectively.
Question 2’
What kinds ofsatisfy above relations ?

Theorem (Yu, 2012);0 -Schnorr randomness =T

X 2L X

MLR.

where L is the set of all the low sets.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof RandomnessInstitute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer;0 -SR vs MLR
Questoin 1’
TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?

where X -R and X -S are relativizations of R and S to X , respectively.
Question 2’
What kinds ofsatisfy above relations ?

Theorem (Yu, 2012);0 -Schnorr randomness =T

X 2L X

MLR.

where L is the set of all the low sets.
Question, (Yu, 2012)
Does ;0 -Schnorr randomness =TX 2L\G X

where G is the set of all the 1-generic sets.

MLR?

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer;0 -SR vs MLR
Theorem
For any ;0 -Schnorr test {Ue }e2! ,Tthere exist T
a low 1-generic real Z and a
Z -Martin-Löf test {Ve }e2! with e2! Ue ⇢ e2! Ve .
Proof.
A finite injury argument.
Corollary;0 -Schnorr randomness =T

X 2L\G X

MLR.

This give an aﬃrmative answer to Yu’s problem.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer

Application
Recall that a real A is said to be LR-reducible to B, abbreviated A LR B,
if every real Martin-Löf random relative to B is also Martin-Löf random
relative to A.
Theorem (Diamondstone, 2012)For any low real X , Y , there exists a low c.e. real Z such that X , Y LR Z .

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer

Application
Recall that a real A is said to be LR-reducible to B, abbreviated A LR B,
if every real Martin-Löf random relative to B is also Martin-Löf random
relative to A.
Theorem (Diamondstone, 2012)For any low real X , Y , there exists a low c.e. real Z such that X , Y LR Z .
We have the following similar theorem:
Theorem
For any low real X , Y , there exists a low 1-generic real Z such thatX , Y LR Z .

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
Another
University.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer;0 -SR vs MLR
Questoin 1’TS
(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?
Theorem (Yu, 2012)
S0X 2High(MLR,;0 -SR) X -MLR = ; -SR

This is a positive answer for Q1’ in the uniou part.
In fact, Yu also shown that can be MLR \ High(ML, ;0interesting answer of Q2.

SR). This is aMay. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Positive Answer

Questoin 1’TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?
Question 2’
What kinds ofsatisfy above relations ?

A New Characterization of MLR.
TheoremS
X 2PA X -CR = MLR.

Proof.
Franklin, Stephan and Yu (2011) proved that High(CR, MLR) includes all
PA-complete reals. Reimann and Slaman showed that any Martin-Löf
random is Martin-Löf relative to some PA-complete real. Since
X -MLR ⇢ X -CR, it is known that any Martin-Löf random is computably
random relative to some PA-complete real. This implies the desiredequality.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Negative Answer

Negative Answer: W2R vs MLR

Questoin 1’TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?
Theorem (Yu, 2012)¬9 ⇢ 2! such that W 2R =Tx2

X

MLR.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Negative Answer

Negative Answer: W2R vs MLR

Questoin 1’TS(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?
Theorem (Yu, 2012)¬9 ⇢ 2! such that W 2R =Tx2

X

MLR.

Theorem (Merkle and Yu, unpublished)S¬9 ⇢ 2! such that W 2R = x2 X MLR.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Answers to Questions

Negative Answer

Negative Answer: SR vs CR
Questoin 1’TS
(9 ⇢ 2! )[R = X 2 X -S] or (9 ⇢ 2! )[R = X 2 X -S]?
TheoremT
SR = X 2Low(CR,SR) X -SR 6= CR

Proof.
Kjos-Hanssen, Nies and Stephan (2006) proved thatLow(CR, SR) = Low(SR, SR) holds.
Theorem
S;0 SR = X 2High(SR,CR) X -SR 6= CR

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Summary

Summary of Results

SR

T0’-SR0’-SR

X 2Low(R,S) X -S = R

W2R

MLR

CR

SR

Yes

Yes?

Yes

No

No

No?

?

W2R?

MLR

Yes

NoCR?

?

Yes

SR

Yes

No

NoS

No
No

X 2High(R,S) X -R = S

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26Summary

Summary of Results
TR

S0’-SR0’-SR

S

X 2Low(R,S) X -S = R

W2R

MLRCR

SRYes

Yes?

Yes

NoNoNo?

?

W2R?

MLR

Yes

NoCR?

?

Yes

SRYes

No

No

X 2High(R,S) X -R = S

No
NoMay. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Summary

Summary of Results
TR

S0’-SR0’-SR

S

X 2Low(R,S) X -S = R

W2R

MLR

CRSRYes

Yes?

Yes

NoNoNo?

?

W2R?

MLRYesNoCR?

?

YesSRYesNoNo

X 2High(R,S) X -R = S

NoNoMay. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

Summary

References

Liang Yu:
Characterizing strong randomness via Martin-Löf randomness. Annalsof Pure and Applied Logic, vol. 163, no. 3, pp. 214-224 (2012)
David Diamondstone:
Low upper bounds in the LR degrees. Annals of Pure and AppliedLogic, vol. 163, no.3, pp. 314-320, 2012.

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26

SummaryThank you very much!

May. 15, 2013 ELC Workshop on Random
NingNing Peng Join work with Kojiro Higuchi
Definability(Mathematicalof Randomness
Institute,
viaTohoku
AnotherUniversity.
Randomness
sa8m42@math.tohoku.ac.jp)/ 26