Tests, Complexities and Martingales
Kojiro Higuchi
October 12, 2012 at Tohoku University
Background
• In the biginning of this year, Takayuki Kihara and I studied the concept, effective strong nullness, on the subsets of Cantor space 2ω introduced by Kihara.
• Later, Takayuki Kihara and Kenshi Miyabe studied this concept as well as its variants, e.g., strong Martin-L¨of nullness, strong Schnorr nullness and so on, as concepts on the points of 2ω.
• They gave some characterizations including ones in terms of tests and complexities.
Goal
• In this talk, we study strong Martin-L¨of nullness as a concept on the subsets of 2ω.
Strong Martin-L¨of nullness is defined in terms of tests.
• The goal of my talk is to introduce characterizations of strong Martin-L¨of null sets in terms of complexities and martingales.
Motivation
• Tests, complexities and martingales are important
concepts in algorithmic randomness theory and probability theory.
• Null sets are naturally obtained from these concepts. Relations between those null sets are well studied.
• Tests is a sequence of open sets whose intersection is null.
• Complexities give compressible sets.
• Martingales give winnable sets.
• Fact. Martin-L¨of null sets
= Compressible sets of (a priori) complexities of semimeasures
= Winnable sets by c.e. martingales.
• This study gives new results along this line.
Cantor Space 2
ωWe use the following notations:
• 2<ω = the set of all finite binary strings.
• 2ω = Cantor space, i.e.,
the set of all infinite binary strings together with the topology generated by {[[σ]] : σ ∈ 2<ω},
where [[σ]] = {f ∈ 2ω : σ ≺ f }.
• For a set A ⊂ 2<ω, [[A]] = {f ∈ 2ω : (∃σ ∈ A)[σ ≺ f ]}.
Outer Measures on the subsets of 2
ω• In this talk, we restricted ourselves to use outer measures for the ones defined by some function from 2<ω into [0, ∞).
• Thus, for any outer measure µ, we assume there is a function µ∗: 2<ω→ [0, ∞) such that
∀σ µ([[σ]]) = µ∗(σ) &
∀X ⊂ 2ω µ(X ) = inf{∑σ∈Aµ∗(σ) : X ⊂ [[A]]}.
• We sometimes identify µ with µ∗.
• An outer measure µ is computable ⇐⇒
the above µ∗ is computable (or, equivalently, computably approximable).
• An outer measure µ is atomless ⇐⇒
∀f ∈ 2ω µ({f }) = 0.
Martin-L¨ of Null Sets
• Let µ be an outer measure on 2ω.
• {Un}n∈ω is a µ-test ⇐⇒
∀n ∈ ω Un is open & Un ⊃ Un+1 & µ(Un) ≤ 2−n.
• Clearly, ∀ µ-test {Un}n µ(∩nUn) = 0.
• We write λ for the fair-coin measure. We say just “test” instead of “λ-test”.
• A µ-test {Un}n is Martin-L¨of ⇐⇒
∃ a computable sequence {An}n∈ω of c.e. subsets of 2<ω
∀n ∈ ω Un = [[An]].
• X ⊂ 2ω is Martin-L¨of µ-null ⇐⇒
∃ M.-L. µ-test {Un}n X ⊂∩nUn.
• We say “Martin-L¨of null” instead of “Martin-L¨of λ-null”.
• X ⊂ 2ω is strong Martin-L¨of null ⇐⇒
∀ computable atomless outer measure µ X is M.-L. µ-null.
Remarks
• f ∈ 2ω is Martin-L¨of random ⇐⇒ f is not in any M.-L. null set.
• Any M.-L. random sequence can be considered to satisfy any “simple” property, like law of large number, which almost all infinite binary sequence obtained by tossing a fair coin satisfy.
• On the otherhand, an element of some strong M.-L. null set can be considered to fail to satisfy any “simple” property which almost all infinite binary sequence
obtained by tossing an unfair and deformable coin satisfy.
Compressible Sets 1
• F : 2<ω → [0, 1] is a semimeasure ⇐⇒
∀σ ∈ 2<ω F(σ) ≥ F (σ0) + F (σ1).
• We define the (a priori) complexity KF of a semimeasure F by
KF : 2<ω → [0, ∞] & ∀σ ∈ 2<ω KF(σ) = − log2F(σ).
• Fix an outer measure µ and a semimeasure F .
• X ⊂ 2<ω is KF-µ-compressible ⇐⇒
∀g ∈ X ∀k ∈ ω∃n ∈ ω KF(g ↾ n) ≤ µ(g ↾ n) − k.
• When µ is the length function, we just say
“KF-compressible” instead of “KF-µ-compressible”.
• (Folklore?) ∀X ⊂ 2ω [λ(X ) = 0 ⇐⇒
∃ semimeasure F X is KF-compressible].
Compressible Sets 2
• Theorem(Schnorr?). ∀X ⊂ 2ω [X is M.-L. null ⇐⇒
∃ left-c.e. semimeasure F X is KF-compressible].
• Theorem(essentially,
Higuchi-Hudelson-Simpson-Yokoyama).
∀ computable atomless outer measure µ ∀X ⊂ 2ω [X is M.-L. µ-null ⇐⇒
∃ left-c.e. semimeasure F X is KF-µ-compressible].
• Corollary. ∀X ⊂ 2ω
[X is strong M.-L. null ⇐⇒
∀ c.a.o.m. µ ∃ l.-c.e.s. F X is KF-µ-compressible].
Remarks
• Usually(?), complexities mean Kolmogorov complexities using partial functions from 2<ω into 2<ω.
• If we use Kolmogorov complexities, then it is easy to explain an intuitive idea of compressible sets. But, in the case of priori complexities, I have no idea.
• On the other hand, sometimes priori complexities behave nicer than Kolmogorov complexities. See the paper by Higuchi-Hudelson-Simpson-Yokoyama!
Winnable Sets 1
• O : 2<ω\ {∅} → [1, 2] is called an odds.
• M : 2<ω → [0, ∞) is an O-(super)martingale ⇐⇒
∀σ ∈ 2<ω
M(σi) = M(σ(1 − i)) + O(σi)(M(σ) − M(σ(1 − i))), where i satisfies M(σi) = max{M(σ0), M(σ1)}.
• When O is the constant function 2, we just say
“martingale” instead of “O-martingale”.
• Martingales are characterized by the condition 2M(σ) = M(σ0) + M(σ1) instead of the preceding condition.
• X ⊂ 2ω is winnable by an O-martingale M ⇐⇒
∀g ∈ X supnM(g ↾ n) = ∞.
• ∀X ⊂ 2ω [λ(X ) = 0 ⇐⇒
X is winnable by some martingale M].
Winnable Sets 2
• Theorem(Schnorr). ∀X ⊂ 2ω [X is M.-L. null ⇐⇒ X is winnable by some left-c.e. martingale].
• An odds O is acceptable ⇐⇒
∀g ∈ 2ω supn
∏
m<nO(g ↾ m + 1) = ∞.
• For an odds O, we define an outer measure µO by µO([[σ]]) = (∏τ ⊂σO(τ ))−1.
• µO is indeed an outer measure.
• If µO is acceptable, then µO is atomless.
• For an outer measure µ such that µ(2ω) = 1 and
0 < µ([[σ0]]) + µ([[σ1]]) ≤ 2µ([[σ]]), we define an odds Oµ
by Oµ(σi) = µ([[σi]])/µ([[σ]]).
• Oµ is indeed an odds.
• If µ is atomless, then Oµ is acceptable.
• OµO = O and µOµ= O.
Winnable Sets 3
• Theorem. ∀ computable atomless outer measure µ with some additional conditions ∀X ⊂ 2ω
[X is M.-L. µ-null ⇐⇒
X is winnable by some left-c.e. Oµ-martingale].
• Theorem. ∀ computable acceptable odds O ∀X ⊂ 2ω [X is M.-L. µO-null ⇐⇒
X is winnable by some left-c.e. O-martingale].
• Corollary. ∀X ⊂ 2ω
[X is strong M.-L. null ⇐⇒
∃ c.a.o. O X is winnable by some l.-c.e.O-m.].
Remarks
• If the fair gamble, i.e. the odds O is the constant
function 2, goes on along a Martin-L¨of random sequence, then any gambler cannot always earn however he wants by her/his strategy.
• If the gamble goes on along an infinite sequence of some strong Martin-L¨of null set, then some gamble always earns however he wants by her/his strategy even when acceptable but quite unfair odds are used.
Summary
For X ⊂ 2ω, the following are pairwise equivalent:
• X is strong Martin-L¨of null.
• X is KF-µ-compressible for some left-c.e. semimeasure F and some computable atomless outer measure µ.
• X is winnable by some left-c.e. O-martingale M for some computable acceptable odds O.
