### Two betting strategies that predict all compressible sequences

Petrovic, T *(University of Zagreb)*

Monday 02 July 2012, 17:00-17:30

Seminar Room 1, Newton Institute

#### Abstract

A new type of betting games that charaterize Martin-Löf randomness
is introduced. These betting games can be compared to martingale
processes of Hitchcock and Lutz as well as non-monotonic betting
strategies. Sequence-set betting is defined as successive betting on
prefix-free sets that contain a finite number of words. In each iteration
we start with an initial prefix-free set $P$ and an initial capital
$c$, then we divide $P$ into two prefix-free sets $P_{0}$ and $P_{1}$
of equal size and wager some amount of capital on one of the sets, let's
say $P_{0}$. If the infinite sequence we are betting on has a prefix
in $P_{0}$ then in the next iteration the initial set is $P_{0}$ and
the wagered amount is doubled. If the infinite sequence we are betting
on does not have a prefix in $P_{0}$ then in the next iteration the
initial set is $P_{1}$ and the wagered amount is lost. In the first
iteration the initial prefix-free set contains the empty string. The
player succeeds on the infinite sequence if the series of bets increases
capital unboundedly. Non-monotonic betting can be viewed as sequence-set
betting with an additional requirement that the initial prefix-free set
is divided into two prefix-free sets such that sequences in one set have
at some position bit 0 and in the other have at that same position bit
1. On the other hand if the requirement that the initial prefix-free set
$P$ is divided into two prefix-free sets of equal size is removed, and
we allow that $P_{0}$ may have a different size from $P_{1}$ we have a
betting game that is equivalent to martingale processes in the sense that
for each martingale process there is a betting strategy that succeeds on
the same sequences as martingale process and for each betting strategy
a martingale process exists that succeeds on the the same sequences as
the betting strategy. It is shown that, unlike martingale processes,
for any computable sequence-set betting strategy there is an infinite
sequence on which betting strategy doesn't succeed and which is not
Martin-Löf random. Furthermore it is shown that there is an algorithm
that constructs two sets of betting decisions for two sequence-set
betting strategies such that for any sequence that is not Martin-Löf
random at least one of them succeeds on that sequence.

#### Presentation

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

## Comments

Start the discussion!