Integer Valued Randoms
Rod Downey
Victoria University
Wellington
New Zealandjoint with George Barmpalias,
Beijing, andwith Michael McInerney
Also currently at VUWTokyo, May 2013

Martin-Löf randomness-reminder
Sc.e. open set is one of the form i (qi , ri ) where {qi : i 2 !} and{ri : i 2 !} are c.e.. U = {[ ] : 2 W }. Here [ ] = { ↵ | ↵ 2 2! },and has measure µ([ ]) = 2| | .

I A

I A

Martin-Löf test is a uniformly c.e. sequence U1 , U2 , . . . of c.e. opensets s.t.
8i(µ(Ui )  2 i ).
(Computably shrinking to measure 0)

Definition↵ is Martin-Löf random if for every Martin-Löf test,\↵2/Ui .
i>0The martingale view
I Back to von Mises 1919. Think about predicting the next bit of asequence. Then you bet on the outcome. You should not win!
I (Levy) A

all ,martingale is a function f : 2<! 7! R+ [ {0} such that forf ( 0) + f ( 1).
2
I the martingale succeeds on a real ↵, if lim supn F (↵ n) ! 1.
f( )=I Think of betting on sequence where you know that every 2nd bit was

1. Then every second bit you could double you stake. This martingale
exhibits exponential growth and that can be used to characterize
computable reals.
I Ville proved that null sets correspond to success sets for martingales.

They were used extensively by Doob in the study of stochastic
processes.

I A,

supermartingale is a function f : 2<! 7! R+ [ {0} such that for allf ( 0) + f ( 1).
2I Schnorr showed that Martin-Löf randomness corresponded to e↵ective(super-)martingales failing to succeed.
f( )

I f

as being e↵ective or computably enumerable if f ( ) is a left-c.e.
real, and at every stage we have e↵ective approximations to f in thesense that f ( ) = lims fs ( ), with fs ( ) a computable increasing
sequence of rationals.

Schnorr
Theorem (Schnorr)
A is Martin-Löf random i↵ no e↵ective martingale succeeds on it.
I Also lead to variations on randomness:

1. Schnorr randomness (µ(Un ) = 2 n ),2. computable randomness (only computable martingales),3. Kurtz randomness Un is a canonical clopen set-or A 2 Vn for all open
Vn of measure 1.

Integer Valued Randoms
I Many notions of randomness.... I know a good book or two.
I If you actually go to a casino, and try to bet Y

accept the bet.

1
10000000 , they will not

I What about if you ask that bets should be in multiplies of certain

discrete amounts. The canonical example being $0, 1, 2, 3, . . . .
I By multiplying, we can regard the the values as integers in themartingale.

Definition (Beinvenu, Stephan, Teutsch)
X is IVR i↵ no computable integer valued martingale succeeds on X .
I We can similarly define single valued if the set of possible bets is asingleton, (either no bet or) a.
I Similarly finitely valued.

Theorem (Bienvenu, Stephan, Teutsch)
1. Computably random implies IVR implies FVR implies SVR
2. Kurtz random implies SVR
3. FVR implies bi-immune.
I As we already know, Computable implies Schnorr implies Kurtz (withno reversals)
I Schnorr implies law of large numbers.

Theorem ([Bienvenu, Stephan, Teutsch)
No other implications hold.

The essential di↵erence
I There are finitary strategies to defeat IV martingales.
I If m bets on an outcome, say

1 in favour of 0, then if we choose

0 he must lose at least $1.

Definition (Actually a Theorem-Jockusch and Posner)
A is called n-generic if A meets or avoids each ⌃0n set S of strings. That iseither
I

9 2 S(I9A), orA8⌧ 2 S( 6⌧ ).

(Kurtz) B is weakly n-generic if A meets all dense S’s.

Theorem (BST)
If A is weakly 2-generic then A is IVR. Hence IVR’s are co-meager.
However:Theorem (BST)
There is a 1-generic which is not IRV.

Corollary
IVR does not imply Schnorr randomness.

Other strangenesses of IVR’s
I One of the classic methods for martingales is called the savings trick.
I This says, given a martingale m convert it into a new one n by; after

you win a dollar, put it in the bank, and bet the same proportion asm, till you make another dollar.
I The result has the property that it is (up to ±1) nondecreasing.

Theorem (Teutsch)
There is an X which is not IRV but is IVR for martingales with the savings
property.
I Of course, the reason is that proportions are not available. His

method exploits this.

Theorem (Chalcraft, Dougherty, Freiling, Teutsch)
If B and A are finite integer value sets, then every B-IVR is A-IVR i↵ there
is a c with B ◆ c · A some c 2 Q.

I The proof of the easy direction is that if B ◆ c · A then any bet A

makes B can simply make a multiple of, so “essentially” the same betup to scaling.

I The hard direction observes that if B 6◆ c · A, then we construct areal that SA succeeds on and B does not.

I SA ’s strategy is to always bet on 0, and cycle through its values,{a1 , . . . , an }I We can always assume that B bets on 0 else we makre easy progress.
I We compare
I If the first

SA ’s capitalwith SA ’s bet .
MB ’s capital
MB ’s bet

second bet 0 S wins more proportionally to it capital, if
the second exceeds first bet 1 M loses more proportionally to itscapital.
S ’s capital
I It can be proven that A! 1 unless it has a limit C , andMB ’s capitalthen c = C1 is the multiple

Our questions
I What kinds degrees have/bound IVR’s?
I Are these degree notions?
I What kinds of genericity might align itself to IVR’s. We know weak2- is enough, and 1- is not enough.
I Does it matter for left c.e. reals?
I What about partial IVR’s? That is in a casino I won’t tell you what I

would bet in advance. So consider the definition with m’s partialcomputable.
I What about c.e. degrees? Do they relate to any known degree class?

Multiply generic reals
I A new genericity notion. Recall that a ⌃0 set is the range of a1computable f . What about if this is !-c.a., and with the property
that it has an approximation g such that for all n,g (n, s) g (n, s + 1). We call this proper.
I Recall that an order is a computable function h with h(n + 1)h(n)and h(n) ! 1.

I For an order h, say that fis h-c.a. if the approximation hasg (n, s + 1) 6= g (n, s) at most h(n) many times.

Definition
Let h be an order. We say that A is h-multiply generic if A meets ofavoids all sets S which are the ranges of proper h-c.a. functions. Similarly
for weakly and dense sets.
I Evidently for any computable h, ;0 can compute an h-multiply generic.

Theorem
If h and h0 are orders and G is h-(weakly) multiply generic, then it is also
h0 (weakly) multiply generic. Thus A is multiply generic i↵ A ish-multiply generic for some h.

Lemma
If G is weakly multiply generic then it is also IVR. The converse is not truesince MLR’s are not weakly 1-generic.
The proof is modelled on that by Bienvenu et. al. noting that all that isneeded is the weak multiple genericity.

Array noncomputable degrees
Definition (Downey, Joskusch, Stob)
A degree a is called array noncomputable i↵ for all functions f wtt ;0
there is a a function g computable from a such that
91 x(g (x) > f (x).
I Looks like “non-low2 .”I Indeed many nonlow2 constructions can be run with only the above.

For example, every anc degree bounds a generic.
I The c.e. ones are of special interest.

A ubiquituos class
I c.e. anc degree are those that:I (Kummer) Contain c.e. sets of infinitely often maximal Kolmogorov

complexity C (A n) = 2 log n.
I Have e↵ective packing dimension 1 (Downey and Greenberg)
I Compute left c.e. reals ↵ (halting probabilities) and B <T ↵ suchthat if V is a presentation of ↵ (that is V is prefix free, c.e. and↵ = µ(V )), then V T B. (Downey and Greenberg)

I (Downey, Jockusch, and Stob) bound disjoint c.e. sets A and B suchthat every separating set for A and B computes the halting problem
I have strong minimal covers (Ishmukhametov).
I (Cholak, Coles, Downey, Herrmann) The array noncomputable c.e.
degrees form an invariant class for the lattice of ⇧01 classes via thethin perfect classes

TheoremEvery array noncomputable degree a bounds bounds a weakly multiplygeneric and hence a IVR.
The proof models itself on the classical one that each c.e. degree bounds a1-generic.

What about multiply generics?
I These need another concept.

Definition (Downey, Greenberg, Weber)We say that a c.e. degree a is totally !-c.e. i↵ for all functions g T a, g
is !-c.e.. That is, there is a computable approximationg (x) = lims g (x, s), and a computable function h, such that for all x,|{s : g (x, s) 6= g (x, s + 1)}| < h(x).
I array computability is a uniform version of this notion where h can bechosen independent of g .
I Every array computable degree (and hence every contiguous degree)
is totally !-c.e..
I Can extend to computable ordinals (Downey and Greenberg).
I These degrees are definable in the c.e. degrees (DGW), and (Downeyand Ng) correspond to the degree containing computably finitelyrandom reals.

Theorem
I Every not totally !-c.a. c.e. set computes a multiply generic set.
I Every not totally ! 2 -c.a. set computes a multiply generic set.

I The left c.e. case.
I Notably, there are left c.e. computably random reals (and hence IVR)

in each high c.e. degree.

Theorem
If X is left c.e. and IVR then X is of high degree.
I We want to construct a procedure

X (e, s) such that lims

X (e, s) =Tot(e).
I The cycle for (x, s) is to use the smallest new place in theapproximation of Xs with Xs (n) = 1. For s 0 s we set
X (e, s 0 )[t 0 ] = 0 until Tot(e) looks more total as more arguments

converge. We have inductively defined a partial computable m = meup to strings of length s.
I If Tot(e) looks more total at stage t > s we play m conservatively

except on n(t) playing to win $1 there on the 1 outcome.
I The key is that almost always he must move away, and he cannot

play where we have lost.

Theorem
I There are IVR’s that are not partial IVR.
I There are partial IVR’s that are not partial computably random.

Theorem
Each anc c.e. (wtt-)degree contains a partial IVR.
The proof uses “big uses” to create space.

Thank You