7.11: Summary

Each term in a random walk {\(S_n; n ≥ 1\)} is a sum of IID random variables, and thus the study of random walks is closely related to that of sums of IID variables. The focus in random walks, however, as in most of the processes we have studied, is more in the relationship between the terms (such as which term first crosses a threshold) than in the individual terms. We started by showing that random walks are a generalization of renewal processes, are central to studying the queueing delay for G/G/1 queues, and to sequential analysis for hypothesis testing.

A major focus of the chapter was on estimating the probabilities of very unlikely events, a topic known as large deviation theory. We started by studying the Chernoff bound to \(\text{Pr}\{S_n ≥ α\}\) for \(α> 0\) and \(\mathsf{E} [X] < 0\). We then developed the Wald identity, which can be used to find tight upper bounds to the probability that a threshold is ever crossed by a random walk. One of the insights gained here was that if a threshold at α is crossed, it is likely to be crossed at a time close to \(n^∗ = α/\gamma' (r^∗)\), where \(r^∗\) is the positive root of \(\gamma(r)\). We also found that \(r^∗\) plays a fundamental role in the probability of threshold crossings. For questions of typical behavior, the mean and variance of a random variable are the major quantities of interest, but when interested in atypically large deviations, \(r^∗\) is the major parameter of interest.

We next introduced martingales, submartingales and supermartingales. These are some­times regarded as somewhat exotic topics in mathematics, but in fact they are very useful in a large variety of relatively simple processes. For example, we showed that all of the random walk issues of earlier sections can be treated as a special case of martingales, and that martingales can be used to model both sums and products of random variables. We also showed how Markov modulated random walks can be treated as martingales.

Stopping trials, as first introduced in chapter 4, were then applied to martingales. We defined a stopped process {\(Z^∗_n; n ≥ 1\)} to be the same as the original process {\(Z_n;n\geq 1\)} to the stopping point, and then constant thereafter. Theorems 7.8.1 and 7.8.2 showed that the stopped process has the same form (martingale, submartingale, or supermartingale) as the original process, and that the expected values \(\text{E} [Z_n^∗]\) are between \(\mathsf{E} [Z_1]\) and \(\mathsf{E} [Z_n]. We also looked at \(\mathsf{E} [Z_J ]\) and found that it is equal to \(\mathsf{E} [Z_1]\) iff (7.8.9) is satisfied. The Wald identity can be viewed as \(\mathsf{E} [Z_J ] = \mathsf{E} [Z_1] = 1\) for the Wald martingale, \(Z_n = \exp \{rS_n − n\gamma (r)\}\). We then found a similar identity for Markov modulated random walks. In deriving results for Markov modulated random walks, it was necessary to define martingales relative to other processes in order to find suitable stopping trials, also defined on martingales relative to other processes. This added restriction on martingales is useful in other contexts.

The Kolmogorov inequalities were next developed. They are analogs of the Markov in­equality and Chebyshev inequality, except they bound initial segments of submartingales and martingales rather than single rv’s. They were used, first, to prove the SLLN with only a second moment and, second,the martingale convergence theorem.

A standard reference on random walks, and particularly on the analysis of overshoots is [Fel66]. Dembo and Zeitouni, [5] develop large deviation theory in a much more general and detailed way than the introduction here. The classic reference on martingales is [6], but [4] and [16] are more accessible.