Computability, Unsolvability, Randomness Math 497A: Homework #9

Stephen G. Simpson

Due Monday, October 29, 2007

1. Hoeffding’s Inequality says that the probability space 2^{ℕ} with the fair coin probability measure satisfies

Prob (|\frac{∑_{i=0}^{n−1} X(i)}{n} − \frac{1}{2}| > ϵ) < \frac{2}{exp 2nϵ^{2}} .

Use Hoeffding’s Inequality to prove that if a point X ∈ 2^{ℕ} is random (i.e., random in the sense of Martin-Löf), then X obeys the Strong Law of Large Numbers:

\frac{∑_{i=0}^{n−1} X(i)}{n} → \frac{1}{2} as n → ∞ .

2. Prove that there exist weakly 1-random points in 2^{ℕ} which do not obey the Strong Law of Large Numbers.

Hint: Use finite approximation.

3. In problem 1, can you say anything about the rate of convergence to 1/2?

4. Prove that if X ⊕ Y ∈ 2^{ℕ} is random (i.e., random in the sense of Martin-Löf), then X ≰_{T} Y and Y ≰_{T} X.

5. Prove that there exist points X, Y ∈ 2^{ℕ} such that X ⊕ Y is weakly 1-random yet X ≡_{T} Y.

6. A set B ⊆ ℕ is said to be biimmune if both B and its complement ℕ \ B are immune. Prove that if X ∈ 2^{ℕ} is weakly 1-random then X is the characteristic function of a biimmune set.

7. Let f be a Turing oracle.

For each i ∈ ℕ define

U_{i}^{f} = {X ∈ 2^{ℕ} | φ_{i}^{(1),f⊕X}(0) ↓}.

Thus U_{i}^{f}, i = 0, 1, 2, … is the standard recursive enumeration of all Σ_{1}^{0,f} subsets of 2^{ℕ}.

Given a sequence of sets V_{n} ⊆ 2^{ℕ}, n = 0, 1, 2, …, prove that the following are pairwise equivalent.

(a) There exists a total recursive function g such that V_{n} = U_{g(n)}^{f} for all n.

(b) There exists a total f-recursive function h such that V_{n} = U_{h(n)}^{f} for all n.

(c) The predicate P ⊆ 2^{ℕ} × ℕ given by

P (X, n) ≡ X ∈ V_{n}

is Σ_{1}^{0,f}.

In this case we say that the sequence of sets V_{n}, n = 0, 1, 2, … is uniformly Σ_{1}^{0,f} or uniformly Σ_{1}^{0} relative to f.

Note: This concept will be part of the definition of what it means for a point X ∈ 2^{ℕ} to be random relative to the oracle f.