Two betting strategies that predict all compressible sequences

Add to your list(s) Download to your calendar using vCal

• Petrovic, T (University of Zagreb)
• Monday 02 July 2012, 17:00-17:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.