The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

SAS

Seminar

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

[pdf ]

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.

Back to top ∧