Presented by:

T Petrovic University of Zagreb

Date:

Monday 2nd July 2012 -

17:00 to 17:30

Venue:

INI Seminar Room 1

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.

**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.

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

We'll get it fixed as soon as possible.