PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very low Entry average rating: No information on entry rating
[parent] gale (Definition)

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

  1. A $ \nu$-$ s$-supergale is a function $ d:\lbrace 0,1\rbrace ^{*}\rightarrow [0,\infty)$ that satisfies the condition
    $\displaystyle d(w)\nu(w)^{s}\geq d(w0)\nu(w0)^{s}+d(w1)\nu(w1)^{s}$ (1)

    for all $ w\in\lbrace 0,1\rbrace^{*}$, 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\lbrace 0,1\rbrace^{*}$.
  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:\lbrace 0,1 \rbrace^{*}\rightarrow [0,\infty)$ such that, for all $ w\in \lbrace 0,1 \rbrace^{*}$, $ d(w)=(d(w0)+d(w1))/2$.

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

$\displaystyle \limsup_{n\rightarrow \infty} d(S[0..n-1])=\infty.$
The success set of $ d$ is $ S^{\infty}[d]=\lbrace S\in\mathbf{C}\bigl \vert d$ succeeds on $ S\rbrace$. $ d$ succeeds on a language $ A\subseteq \lbrace 0,1 \rbrace^{*}$ if $ d$ succeeds on the characteristic sequence $ \chi_A$ of $ A$. We say that $ d$ succeeds strongly on a sequence $ S\in\mathbf{C}$ if
$\displaystyle \liminf_{n\rightarrow\infty}d(S[0..n-1])=\infty.$
The strong success set of $ d$ is $ S^{\infty}_{\text{str}}[d]=\lbrace S\in\mathbf{C}\bigl \vert d\text{ succeeds strongly on }S\rbrace$.

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.



Anyone with an account can edit this entry. Please help improve it!

"gale" is owned by skubeedooo. [ full author list (2) ]
(view preamble)

View style:

Also defines:  supergale, gale, supermartingale, succeed, succeed strongly, success set, strong success set
Keywords:  gale, supergale

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: infinity, unbounded, parameter, strategy, characteristic sequence, language, sequence, martingale, equality, empty string, strings, finite, function, Cantor space, probability measure
There are 3 references to this entry.

This is version 2 of gale, born on 2007-02-22, modified 2007-02-22.
Object id is 8948, canonical name is Gale2.
Accessed 1521 times total.

Classification:
AMS MSC60G42 (Probability theory and stochastic processes :: Stochastic processes :: Martingales with discrete parameter)
 60G44 (Probability theory and stochastic processes :: Stochastic processes :: Martingales with continuous parameter)
 60G46 (Probability theory and stochastic processes :: Stochastic processes :: Martingales and classical analysis)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)