Some preliminary definitions: Let be a probability space. An increasing sequence of sub--algebras of is called a filtration. A stochastic process said to be adapted to a filtration if is -measurable for each – that is, for an arbitrary Borel set . The natural filtration associated with a process is defined by .
Now, the more interesting ones. A discrete-time process is said to be a martingale with respect to a filtration if
- is adapted to .
- is integrable for all (i.e. ).
- for all .
Recall that the conditional expectation of a random variable with respect to a -algebra , denoted , is any random variable that satisfies for all , that is,
For example, if is an i.i.d. sequence with and , then
so the unbiased 1- random walk is a martingale. For a biased random walk on with , it is clear that is not a martingale. However, letting where , we have
so that is integrable, and
It follows that is a martingale. If and then
so is a Markov chain. Further, for any ,
so that is a harmonic function. In general, if is a harmonic function for a Markov chain , then is a martingale. This follows from the Markov property: