Let ν be a probability measureMathworldPlanetmath on Cantor space 𝐂, and let s[0,).

  1. 1.

    A ν-s-supergale is a function d:{0,1}*[0,) that satisfies the condition

    d(w)ν(w)sd(w0)ν(w0)s+d(w1)ν(w1)s (1)

    for all w{0,1}*, the set of all finite strings of 0’s and 1’s (including e, the empty string).

  2. 2.

    A ν-s-gale is a ν-s-supergale that satisfies the condition with equality for all w{0,1}*.

  3. 3.

    A ν-supermartingalePlanetmathPlanetmath is a ν-1-supergale.

  4. 4.

    A ν-martingale is a ν-1-gale.

  5. 5.

    An s-supergale is a μ-s-supergale, where μ is the uniform probability measure.

  6. 6.

    An s-gale is a μ-s-gale.

  7. 7.

    A supermartingale is a 1-supergale.

  8. 8.

    A martingale is a 1-gale.

Put in another way, a martingale is a function d:{0,1}*[0,) such that, for all w{0,1}*, d(w)=(d(w0)+d(w1))/2.

Let d be a ν-s-supergale, where ν is a probability measure on 𝐂 and s[0,). We say that d succeeds on a sequence S𝐂 if

lim supnd(S[0..n-1])=.

The success set of d is S[d]={S𝐂|d succeeds on S}. d succeeds on a languagePlanetmathPlanetmath A{0,1}* if d succeeds on the characteristic sequence χA of A. We say that d succeeds strongly on a sequence S𝐂 if

lim infnd(S[0..n-1])=.

The strong success set of d is Sstr[d]={S𝐂|d succeeds strongly on S}.

Intuitively, a supergale d is a betting strategy that bets on the next bit of a sequence when the previous bits are known. s is the parameter that tunes the fairness of the betting. The smaller s is, the less fair the betting is. If d succeeds on a sequence, then the bonus we can get from applying d as the betting strategy on the sequence is unboundedPlanetmathPlanetmath. If d succeeds strongly on a sequence, then the bonus goes to infinityMathworldPlanetmath.

Title gale
Canonical name Gale
Date of creation 2013-03-22 16:43:37
Last modified on 2013-03-22 16:43:37
Owner skubeedooo (5401)
Last modified by skubeedooo (5401)
Numerical id 5
Author skubeedooo (5401)
Entry type Definition
Classification msc 60G46
Classification msc 60G44
Classification msc 60G42
Defines supergale
Defines gale
Defines supermartingale
Defines succeed
Defines succeed strongly
Defines success set
Defines strong success set