jwl@ernie.Berkeley.EDU (James Wilbur Lewis) (04/03/88)
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
g-rh@cca.CCA.COM (Richard Harter) (04/03/88)
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.