PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: 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 \begin{equation} d(w)\nu(w)^{s}\geq d(w0)\nu(w0)^{s}+d(w1)\nu(w1)^{s} \end{equation}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}$ i $$ \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 | 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}$ i $$ \liminf_{n\rightarrow\infty}d(S[0..n-1])=\infty $$ The strong success set of $d$ is $S^{\infty}_{{str}}[d]=\lbrace S\in\mathbf{C}\bigl | d{ 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 | get metadata)

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 4 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 3784 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)