Xref: utzoo sci.math:3226 comp.theory:12
Path: utzoo!utgpu!water!watmath!clyde!att-cb!att-ih!pacbell!ames!pasteur!ucbvax!ernie.Berkeley.EDU!jwl
From: jwl@ernie.Berkeley.EDU (James Wilbur Lewis)
Newsgroups: sci.math,comp.theory
Subject: Martingales (was Re: a little problem)
Message-ID: <23501@ucbvax.BERKELEY.EDU>
Date: 2 Apr 88 23:17:18 GMT
References: <19063@labrea.STANFORD.EDU> <457@osupyr.mast.ohio-state.edu> <26494@cca.CCA.COM>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: jwl@ernie.Berkeley.EDU.UUCP (James Wilbur Lewis)
Organization: University of California, Berkeley
Lines: 74

In article <26494@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes:
>In article <457@osupyr.mast.ohio-state.edu> gae@osupyr.mast.ohio-state.edu.UUCP (Gerald Edgar) writes:
>>In article <19063@labrea.STANFORD.EDU> dmc@Coyote.UUCP (Dave Chelberg) writes:
>>>Suppose you have $100 and you decide to play a little game. 
>>>The game consists of betting ANY amount of money with the odds of doubling it
>>>being 1/2 and the odds of losing the bet being 1/2. If your strategy is to
>>>always bet one half of whatever amount you have at a given time, then what
>>>is the average amount of money you will have over the long run?
>>>Is there a strategy which will give you a higher average?
>
>>The process described is a martingale.  SO the expected amount you
>>have after n steps is $100.  If A(n) is the average amount you have
>>in the first n steps, its expectation is $100.
>
>	No, it's not a martingale.  The classic martingale strategy is
>to double your bet after each losing bet on the theory that you get all
>your losses back after only one win.

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...").

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:

A martingale is a sequence of random variables Y0,Y1,...Yn such that:

E[Y sub (i+1) | Y0,Y1,...Yi] = Yi for all i s.t. 0 <= i < n

In other words, one can view Yi as a gambler's capital after the ith 
bet if he started with Y0.  The result of the i+1st bet depends on
the previous results, but the bet is fair; E[Y(i+1) - Yi] = 0.

(So the sequence described by the original article *is* a martingale.)

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).

Note that Yn is the final "capital", while Y0 is the _a priori_ expectation
(which we don't need to know to use this theorem).  The probability that
Yn deviates significantly from its expectation drops off exponentially
with the size of the deviation, so Yn is closely concentrated around its
expectation.

(Note that the MTI is not applicable to the original problem, since there's
no house limit, and the gambler's change in capital can be arbitrarily
large between bets.)

Example: Consider the chromatic number of a random graph on n vertices.
Let Yi = the expected number of colors necessary given the subgraph on
vertices 1,2..i.  It is easy to show that |Yi - Y(i-1)| <= 1, since
in the best case, we can color Vi any color we like, while in the worst 
case, we need to add exactly 1 new color.  

It then follows immediately from the Martingale Tail Inequality that
chi(G) is closely concentrated around its expectation:

P( |Yn-Y0| >= z*sqrt(n)) <= 2e^(-z^2/2)

where Yn is, of course, chi(G).

-- Jim Lewis
   U.C. Berkeley