Xref: utzoo sci.math:3239 comp.theory:15
Path: utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!husc6!cca!g-rh
From: g-rh@cca.CCA.COM (Richard Harter)
Newsgroups: sci.math,comp.theory
Subject: Re: Martingales (was Re: a little problem)
Message-ID: <26506@cca.CCA.COM>
Date: 3 Apr 88 06:32:10 GMT
References: <19063@labrea.STANFORD.EDU> <457@osupyr.mast.ohio-state.edu> <26494@cca.CCA.COM> <23501@ucbvax.BERKELEY.EDU>
Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge, MA
Lines: 46

In article <23501@ucbvax.BERKELEY.EDU> jwl@ernie.Berkeley.EDU.UUCP (James Wilbur Lewis) writes:

]Hmmm, I think there's some confusion here regarding terminology; Gerald
]seems to be using the sense of "martingale" that refers to a sequence of
]random variables having certain properties (as in "_a_ martingale"), while 
]Richard is talking about a particular betting strategy ("_the_ classic 
]martingale...").

	Quite right.  Betting systems are quite old, and many have names.
Of them, the martingale, is the oldest, best known, and the most commonly
reinvented.  Since all such schemes can be subsumed under the mathematical
concept, and the martingale scheme is the archetypal betting scheme...
Incidentally, for those who don't know, the martingale system simply
consists of doubling your bet every time you lose and going back to your
base unit bet when you win.  

]Coincidentally enough, I'm taking a course in probabilistic analysis of
]algorithms this semester, so I just happen to have the notes from Dick
]Karp's lectures on martingales:

	... definition of martingales as sequences deleted

]There is a beautiful inequality involving martingales that turns out
]to be extremely useful in probabalistic analysis, because it allows
]one to show that a random variable is very concentrated around its
]expectation, without knowing what the expectation is!

]Martingale Tail Inequality:

]Let Y0, Y1,...Yn be a martingale, with the additional condition that
]| Y(i+1) - Yi | <= c, a constant.  This is analogous to a house limit.
]Then the probability that Yn - Y0 >= cz*sqrt(n) is <= e^(-z^2/2).

	An interesting point about this is that this is essentially
the same inequality that you get if you bet the house limit each time.
This is certainly plausible -- any scheme which involves smaller bets
than the maximum should produce less variation in the expectation than
betting the maximum each time.  However it is only plausible, since the
amounts bet are not independent random variables.  The result essentially
says that it doesn't matter whether they are independent random variables
or not. Interesting.
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.