A martingale is a stochastic process that formalizes the idea of a fair game.
A stochastic process \(\{Z_n ,n \ge 1\}\) is said to be a martingale process if
\[E[||Z_n ||] \le \infty\] for all n
and
\[E[Z_{n+1} |Z_1 ,..,Z_n ]=Z_n\]
so if we think of \(Z_n\) as the fortune of a gambler than for a martingale process the expected fortune stays constant. Note
\[E[Z_{n+1}]=E\{E[Z_{n+1}|Z_1,..,Z_n]\}=E[Z_n]=..=E[Z_1]\]
let \(X_1, X_2,...\) be independent rv’s with mean 0 and let \(Z_n =X_1 +...+X_n\) , then
\[ \begin{aligned} &E[Z_{n+1}|Z_1,..,Z_n] = \\ &E[Z_{n}+X_{n+1}|Z_1,..,Z_n] = \\ &E[Z_{n}|Z_1,..,Z_n]+E[X_{n+1}|Z_1,..,Z_n] = \\ &Z_{n}+E[X_{n+1}] = Z_n\\ \end{aligned} \] and so \(\{Z_n ,n \ge 1\}\) is a martingale.
let \(X_1, X_2,...\) be independent rv’s with mean 0 and let \(Z_n = \prod_{i=1}^n =X_i\) , then
\[ \begin{aligned} &E[Z_{n+1}|Z_1,..,Z_n] = \\ &E[Z_{n}X_{n+1}|Z_1,..,Z_n] = \\ &Z_{n}E[X_{n+1}|Z_1,..,Z_n] = \\ &Z_{n}E[X_{n+1}] = Z_n\\ \end{aligned} \] and so \(\{Z_n ,n \ge 1\}\) is a martingale.
A positive integer-valued, possibly infinite, rv N is said to be a random time for the process \(\{Z_n ,n \ge 1\}\) if the event \(\{N=n\}\) is determined by the random variables \(Z_1,..., Z_n\). That is, knowing \(Z_1,..., Z_n\) tells us whether or not \(N=n\). If \(P(N<\infty)=1\), then N is called a stopping time.
say a gambler plays roulette. He starts with $100 and bets $1 in each round. He decides to stop if he reaches $200 (or goes broke). Then if N is the number of games he plays N is stopping time.
Let \(N\) be a random time for the process \(\{Z_n ,n\ge 1\}\), then
\[\bar{Z}_n=\left\{\begin{array}.Z_n&\text{ if }&n\le N\\Z_N&\text{ if }&n> N\end{array}\right.\]
is called the stopped process.
so once the event N has happened, the process stays in that state for ever.
If N is a random time for the martingale \(\{Z_n ,n\ge 1\}\), then the stopped process is also a martingale.
proof omitted
Here is the main result for martingales:
The Martingale Stopping Theorem
If either
and there is an \(M<\infty\) such that
\[E[|Z_{n+1} -Z_n | |Z_1 ,..,Z_n ]<M\]
then
\[E[\bar{Z}_n ]=E[Z_1 ]\] proof omitted
In other words, in a fair game if a gambler uses a stopping time to decide when to quit, then his expected final fortune is equal to his expected initial fortune. Thus in the sense of expected value, no successful gambling strategy is possible if one of the conditions of the theorem are satisfied.
There are many supposedly “guaranteed” strategies on how to win in a casino. A popular one is this: bet $1 on red in roulette. if you loose double your bet and so on. Say you loose 3 times and then win, then your net-win is -1+(-2)+(-4)+8=+1, so you win $1. In fact as soon as you win a “sequence” of n losses followed by a win always ends with an overall win of $1!
Great!
Unfortunately according to the martingale stopping theorem, even if roulette were a fair game this would still not work! Why not?
By the way, strategies of this type have a name, the St. Petersburg strategy.
Wald’s equation
If \(X_i , i \ge 1\) are iid with \(E[|X|]< \infty\) and if N is a stopping time for \(\{X_n, i=1,...\}\) with \(E[N]<\infty\), then
\[E\left[ \sum_{i=1}^N X_i \right]=E[N]E[X_1]\]
suppose a computer randomly generates integers. Let N be the number of integers it has to generate before we see a predetermined sequence, for example say 0 0 0 0.
To compute E[N] imagine a sequence of gambles, each initially having 1 unit, playing a fair game. Gambler i begins playing at the beginning of the ith day bets 1 unit that the value on that day is equal to 0. If he wins (and so has 10 units) he bets those 10 units on the second day, again to get 0. If he wins again he will have 100 units and so on. If 0 0 0 0 happens he wins $10000-$1 = $9999, if any of his bets fail he looses $1.
At the beginning of each day another gambler starts to play. If we let Xn denote the total winnings of the casino after the nth day, then since all bets are fair Xn is a martingale with mean 0.
Let N denote the time until 0 0 0 0 happens. Now at the end of day N each of the gamblers 1, .., N-4 would have lost 41, gambler N-3 would have won $9999, gambler N-2 would have won $999, gambler N-1 $99 and gambler N $9. So
\[X_N =N-4-9999-999-99-9=N-11110=0\]
so E[N]=11110.