Samuel R. Buss and Mia Minnes
"Algorithmic Randomness with Probabilistic Strategies and Intermediate Success"
Submitted for publication, July 2013.
Download manuscript: PDF.
Abstract: Probabilistic betting strategies provide a method of characterizing algorithmically random sequences, including Martin-Löf random sequences and (partial) computably random sequences. We generalize probabilistic betting strategies to allow probabilistic moves at every step, not just at betting steps; we also consider restricting randomness to binary choices (or, "coin flips"). We prove that these modifications do not change the strength of probabilistic betting strategies. We introduce probabilistic strategies with intermediate success probabilities, and prove some simulation results. We give a new proof of the separation of Martin-Löf randomness and partial computable randomness using probabilistic betting strategies.
Back to Sam Buss's publications page.