BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Two betting strategies that predict all compressible sequences - P
 etrovic\, T (University of Zagreb)
DTSTART:20120702T160000Z
DTEND:20120702T163000Z
UID:TALK38798@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:A new type of betting games that charaterize Martin-L&ouml\;f 
 randomness\nis introduced. These betting games can be compared to martinga
 le\nprocesses of Hitchcock and Lutz as well as non-monotonic betting\nstra
 tegies. Sequence-set betting is defined as successive betting on\nprefix-f
 ree sets that contain a finite number of words. In each iteration\nwe star
 t with an initial prefix-free set $P$ and an initial capital\n$c$\, then w
 e divide $P$ into two prefix-free sets $P_{0}$ and $P_{1}$\nof equal size 
 and wager some amount of capital on one of the sets\, let's\nsay $P_{0}$. 
 If the infinite sequence we are betting on has a prefix\nin $P_{0}$ then i
 n the next iteration the initial set is $P_{0}$ and\nthe wagered amount is
  doubled. If the infinite sequence we are betting\non does not have a pref
 ix in $P_{0}$ then in the next iteration the\ninitial set is $P_{1}$ and t
 he wagered amount is lost. In the first\niteration the initial prefix-free
  set contains the empty string. The\nplayer succeeds on the infinite seque
 nce if the series of bets increases\ncapital unboundedly. Non-monotonic be
 tting can be viewed as sequence-set\nbetting with an additional requiremen
 t that the initial prefix-free set\nis divided into two prefix-free sets s
 uch that sequences in one set have\nat some position bit 0 and in the othe
 r have at that same position bit\n1. On the other hand if the requirement 
 that the initial prefix-free set\n$P$ is divided into two prefix-free sets
  of equal size is removed\, and\nwe allow that $P_{0}$ may have a differen
 t size from $P_{1}$ we have a\nbetting game that is equivalent to martinga
 le processes in the sense that\nfor each martingale process there is a bet
 ting strategy that succeeds on\nthe same sequences as martingale process a
 nd for each betting strategy\na martingale process exists that succeeds on
  the the same sequences as\nthe betting strategy. It is shown that\, unlik
 e martingale processes\,\nfor any computable sequence-set betting strategy
  there is an infinite\nsequence on which betting strategy doesn't succeed 
 and which is not\nMartin-L&ouml\;f random. Furthermore it is shown that th
 ere is an algorithm\nthat constructs two sets of betting decisions for two
  sequence-set\nbetting strategies such that for any sequence that is not M
 artin-L&ouml\;f\nrandom at least one of them succeeds on that sequence.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR