# Two betting strategies that predict all compressible sequences

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.

Tell a friend about this talk:

## This talk is included in these lists:

Note that ex-directory lists are not shown.

© 2006-2013 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity