gale

Let $\nu$ be a probability measure on Cantor space $𝐂$, and let $s\in [0,\mathrm{\infty })$.

1. A $\nu$-$s$-supergale is a function $d:{\{0,1\}}^{*}\to [0,\mathrm{\infty })$ that satisfies the condition

   $$d(w)\nu {(w)}^s\ge d(w0)\nu {(w0)}^s+d(w1)\nu {(w1)}^s$$ (1)

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

2. A $\nu$-$s$-gale is a $\nu$-$s$-supergale that satisfies the condition with equality for all $w\in {\{0,1\}}^{*}$.

3. A $\nu$-supermartingale is a $\nu$-1-supergale.

4. A $\nu$-martingale is a $\nu$-1-gale.

5. An $s$-supergale is a $\mu$-$s$-supergale, where $\mu$ is the uniform probability measure.

6. An $s$-gale is a $\mu$-$s$-gale.

7. A supermartingale is a 1-supergale.

8. A martingale is a 1-gale.

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

Let $d$ be a $\nu$-$s$-supergale, where $\nu$ is a probability measure on $𝐂$ and $s\in [0,\mathrm{\infty })$. We say that $d$ succeeds on a sequence $S\in 𝐂$ if

$$\underset{n\to \mathrm{\infty }}{lim\; sup}d(S[0..n-1])=\mathrm{\infty }.$$

The success set of $d$ is $S^{\mathrm{\infty }}[d]=\{S\in 𝐂|d\text{ succeeds on }S\}$. $d$ succeeds on a language $A\subseteq {\{0,1\}}^{*}$ if $d$ succeeds on the characteristic sequence ${\chi }_A$ of $A$. We say that $d$ succeeds strongly on a sequence $S\in 𝐂$ if

$$\underset{n\to \mathrm{\infty }}{lim\; inf}d(S[0..n-1])=\mathrm{\infty }.$$

The strong success set of $d$ is $S_{\text{str}}^{\mathrm{\infty }}[d]=\{S\in 𝐂|d\text{ 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 unbounded. If $d$ succeeds strongly on a sequence, then the bonus goes to infinity.

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