Random Processes for Engineers

This chapter builds on the brief introduction to martingales given in Chapter 4, to give a glimpse of how martingales can be used to obtain bounds and prove convergence in many contexts, such as for estimation and control algorithms in a random environment. On one hand, the notion of a martingale is weak enough to include processes arising in applications involving estimation and control, and on the other hand, the notion is strong enough that important tools for handling sums of independent random variables, such as the law of large numbers, the central limit theorem, and large deviation estimates, extend to martingales.

Two other topics in this book are closely related to martingales. The first is the use of linear innovations sequences discussed in Chapter 3. As explained in Example 10.7 below, martingale difference sequences arise as innovations sequences when the linearity constraint on predictors, imposed for linear innovations sequences, is dropped. The other topic in this book closely related to martingales is the Foster–Lyapunov theory for Markov processes, discussed in Chapter 6. A central feature of the Foster–Lyapunov theory is the drift of a function of a Markov process: E[V(Xt+1) − V(Xt)|Xt = x]. If this drift were zero then V(Xt) would be a martingale. The assumptions used in the Foster–Lyapunov theory allow for a controlled difference from the martingale assumption. In a sense, martingale theory is what is left when the linearity and Markov assumptions are both dropped.

The chapter is organized as follows. The definition of a martingale involves conditional expectations, so to give the general definition of a martingale we first revisit the definition of conditional expectation in Section 10.1. The standard definition of martingales, in which σ-algebras are used to represent information, is given in Section 10.2. Section 10.3 explains how the Chernoff bound, central to large deviations theory, readily extends to sequences that are not independent.