Random Walk, Brownian Motion, and Martingales

Frontmatter

Chapter 1. What Is a Stochastic Process?

Abstract

This chapter provides the mathematical framework and example illustrations of stochastic processes as families of random variables with values in some measurable (state) space S, such as the integers or the real line or higher dimensional Euclidean space, and indexed by some set Λ. Examples include i.i.d. sequences, random walks, Brownian motion, Poisson processes, branching processes, queue processes, Markov processes, and various martingale processes. Special emphasis is given to existence and constructions of these important classes of stochastic processes.

Rabi Bhattacharya, Edward C. Waymire

Chapter 2. The Simple Random Walk I: Associated Boundary Value Distributions, Transience, and Recurrence

Abstract

The simple random walk is the generic example of a discrete time temporal evolution on an integer state space. In this chapter it is defined and simple combinatorics are provided in the computation of its distribution. Two possible characteristic long-time properties, (point) recurrence and transience, are identified in the course of the analysis. Recurrence is a form of “stochastic periodicity” in which the process revisits a state (or arbitrarily small neighborhood) infinitely often, while transience refers to the phenomena in which there are at most finitely many returns.

Rabi Bhattacharya, Edward C. Waymire

Chapter 3. The Simple Random Walk II: First Passage Times

Abstract

In view of recurrence vs transience phenomena, the time \(T_y^0\) to reach a fixed integer state y starting at, say, the origin, may or may not be a finite random variable. Nevertheless, one may consider the possibly defective distribution of \(T_y^0\). An important stochastic analysis tool, referred to as the reflection principle, is used to make this calculation. With this analysis another important refinement of the recurrence property is identified for symmetric random walk, referred to as null recurrence, showing that while the walker is certain to reach y, the expected time \({\mathbb {E}}T_y^0 = \infty \). This refinement involves an application of Stirling’s asymptotic formula for n!, for which a proof is also provided. An extension to random walks on the integers that do not skip integer states to the left is also given.

Rabi Bhattacharya, Edward C. Waymire

Chapter 4. Multidimensional Random Walk

Abstract

The simple symmetric random walk on the integers readily extends to that of a simple symmetric random walk on the k-dimensional integer lattice, in which at each step the random walk moves with equal probability to one of its 2k neighboring states on the lattice. A celebrated theorem of Pólya provides a role for dimension k in distinguishing between recurrent and transient properties of the random walk. Namely, it is shown by combinatorial methods that the simple symmetric random walk on the k-dimensional integer lattice \({\mathbb Z}^k\) is recurrent for k = 1, 2 and transient for k ≥ 3.

Rabi Bhattacharya, Edward C. Waymire

Chapter 5. The Poisson Process, Compound Poisson Process, and Poisson Random Field

Abstract

Poisson processes broadly refer to stochastic processes that are the result of counting occurrences of some random phenomena (points) in time or space such that occurrences of points in disjoint regions are statistically independent, and counts of two or more occurrences in an infinitesimally small region are negligible. This chapter provides the definition and some characteristic properties of both homogeneous and inhomogeneous Poisson processes, and more general random fields; the latter refers to occurrences in non-linearly ordered (e.g., non-temporal) spaces. The compound Poisson process is a fundamentally important example from the perspective of both applications and general representations of processes with independent increments. As such it may be viewed as a continuous parameter generalization of the random walk.

Rabi Bhattacharya, Edward C. Waymire

Chapter 6. The Kolmogorov–Chentsov Theorem and Sample Path Regularity

Abstract

While constructions of probability distributions of stochastic processes indexed by uncountable parameter spaces, e.g., intervals, can be readily achieved via the Kolmogorov extension theorem, the regularity of the sample paths is not mathematically accessible in such constructions, for the simple reason that sample path properties that depend on uncountably many time points, e.g., continuity, do not define measurable events in the Kolmogorov model. In this chapter we consider a criterion, also due to Kolmogorov (Published in Slutsky (Giorn Ist Ital Attuari 8:183–199, 1937).) and to Chentsov (Chentsov (Theor Probab Appl 1:140–144, 1956)) for Hölder continuous versions of processes and random fields. In addition to providing a tool for construction of k-dimensional Brownian motion, it yields the construction of continuous random fields such as the Brownian sheet. The chapter concludes with a demonstration of nowhere differentiability of the (continuous) Brownian paths.

Rabi Bhattacharya, Edward C. Waymire

Chapter 7. Random Walk, Brownian Motion, and the Strong Markov Property

Abstract

In this chapter the strong Markov property is derived as an extension of the Markov property to certain random times, called stopping times. A number of consequences of the strong Markov property of Brownian motion and the simple random walk are derived. A derivation of the law of the iterated logarithm for Brownian motion is included in this chapter, from which some fine scale sample path properties of Brownian motion are derived as well.

Rabi Bhattacharya, Edward C. Waymire

Chapter 8. Coupling Methods for Markov Chains and the Renewal Theorem for Lattice Distributions

Abstract

The coupling method is a powerful tool of stochastic analysis that has enjoyed many successes since its original introduction by Doeblin (Revue Math de l’Union Interbalkanique 2:77–105, 1938) to prove convergence to a unique invariant probability for finite state Markov chains. In fact it was applied in Chapter 5 to obtain an error bound in the Poisson approximation to the binomial distribution, i.e., the law of rare events. The convergence to steady state for a class of finite state Markov chains together with a proof of a related powerful result, the renewal theorem, is presented. In the latter one seeks to find how much time a general random walk on the integers with increasing paths, i.e., having non-negative integer-valued displacements, spends in an interval of length m, say (n, n + m]. Renewal theory computes the precise amount asymptotically as n →∞. This chapter is devoted to a cornerstone theorem in the case of integer-valued renewal times, while the much more general theory is provided as a special topic in Chapter 25.

Rabi Bhattacharya, Edward C. Waymire

Chapter 9. Bienaymé–Galton–Watson Simple Branching Process and Extinction

Abstract

The Bienaymé–Galton–Watson simple branching process is defined by the successive numbers X _n of progeny at the n-th generation, n = 0, 1, 2, …, recursively and independently generated according to a given offspring distribution, starting from a non-negative integer number of initial X ₀ progenitors. The state zero, referred to as extinction, is an absorbing state for the process. In this chapter a celebrated formula for the probability of extinction is given as a fixed point of the moment generating function of the offspring distribution. The mean μ of the offspring distribution is observed to play a characteristic role in the determination of the behavior of the generation sizes X _n as n →∞. The critical case in which μ = 1 is analyzed under a finite second moment condition to determine the precise asymptotic nature of the survival probability, both unconditionally and conditionally on survival, in a theorem referred to as the Kolmogorov–Yaglom–Kesten–Ney–Spitzer theorem.

Rabi Bhattacharya, Edward C. Waymire

Chapter 10. Martingales: Definitions and Examples

Abstract

Martingale theory is a cornerstone to stochastic analysis and is included in this book from that perspective. This chapter introduces the theory with examples and their basic properties. For some readers this chapter may serve as a review.

Rabi Bhattacharya, Edward C. Waymire

Chapter 11. Optional Stopping of (Sub)Martingales

Abstract

The development of martingale theory is continued for discrete time martingales with a focus on the use of stopping times in their analysis. An application to the ruin problem in insurance is included as an application.

Rabi Bhattacharya, Edward C. Waymire

Chapter 12. The Upcrossings Inequality and (Sub)Martingale Convergence

Abstract

Doob’s intriguing and delicate upcrossing inequality is derived in this chapter. One of its consequences is the (sub) martingale convergence theorem, which in turn leads to a proof of the strong law of large numbers and a derivation of DeFinetti’s representation of exchangeable (symmetrically dependent) sequences of random variables. Other applications include regularity of sample paths of continuous parameter stochastic processes to be derived in Chapter 13.

Rabi Bhattacharya, Edward C. Waymire

Chapter 13. Continuous Parameter Martingales

Abstract

In this chapter some of the main theorems for discrete parameter martingales obtained in previous chapters are extended to continuous parameter martingales. A central point is the use of martingale theory for the regularization of sample paths of stochastic processes.

Rabi Bhattacharya, Edward C. Waymire

Chapter 14. Growth of Supercritical Bienaymé–Galton–Watson Simple Branching Processes

Abstract

In this chapter the goal is to provide a precise calculation of the rate of growth of a branching process under a mild moment condition on the offspring distribution. The method illustrates the use of the size-bias change of measure technique for an alternative model of branching processes that permits more detailed description of the genealogy. For a given single progenitor the tree graph structure then makes it possible to uniquely trace any given progeny to its root. A natural distance between trees is also introduced that makes the collection of all such family trees a complete and compact metric space.

Rabi Bhattacharya, Edward C. Waymire

Chapter 15. Stochastic Calculus for Point Processes and a Martingale Characterization of the Poisson Process

Abstract

The main purpose of this chapter is to provide a martingale characterization of the Poisson process obtained in Watanabe (1964). This will be aided by the development of a special stochastic calculus that exploits its non-decreasing, right-continuous, step-function sample path structure when viewed as a counting process; i.e., for which stochastic integrals can be defined in terms of standard Lebesgue integration theory.

Rabi Bhattacharya, Edward C. Waymire

Chapter 16. First Passage Time Distributions for Brownian Motion with Drift and a Local Limit Theorem

Abstract

A local limit theorem for convergence of probability density functions is provided as a tool for the computation of hitting time distributions for Brownian motion, with or without drift, as a limit of hitting times for random walk, and other asymptotic limit theorems of this nature.

Rabi Bhattacharya, Edward C. Waymire

Chapter 17. The Functional Central Limit Theorem (FCLT)

Abstract

The functional central limit theorem, or invariance principle, refers to convergence in distribution of centered and rescaled random walks having finite second moments to Brownian motion. This provides a tool for computing asymptotic limits of functionals of rescaled random walks by analyzing the corresponding functional of Brownian motion. The term “invariance principle”refers to the invariance of the distribution of the limit, namely Brownian motion, regardless of the specific random walk increments, with a finite second moment. The proof given here is by a beautiful technique of Skorokhod in which the random walk paths are embedded within the Brownian motion.

Rabi Bhattacharya, Edward C. Waymire

Chapter 18. ArcSine Law Asymptotics

Abstract

Suppose two players A and B are engaged in independent repeated plays of a fair game in which each player wins or loses one unit with equal probability. The implicit symmetry of this scenario results in the counterintuitive phenomena that in a long series of plays it is not unlikely that one of the players will remain on the winning side while the other player loses for more than half of the series. This chapter derives the distribution of (a) the last time in 2m steps that a simple symmetric random walk visits zero in a finite interval, (b) the time spent on the positive side in a finite interval, and (c) the time of the last zero in a finite interval and the arcsine limit distribution for corresponding functionals of Brownian motion. The reference to first, second, and third arcsine laws largely follows nomenclature of Feller (Feller W (1968, 1971) An introduction to probability theory and its applications, vol 1, 3rd edn., vol 2, 2nd edn. Wiley, New York), commonly cited in the probability literature, although they are not derived in that order here, the first being due to Lévy. Apart from its aid in illustrating an important nuance for decision makers when dealing with random phenomena, the arcsine law involves rather non-intuitive distribution of natural functionals of the random walk and Brownian motion. The asymptotic results for random walk are obtained by an application of the local limit theorem from Chapter 16. Although the functional central limit theorem of the previous Chapter 17 can also be applied, it is not required beyond identifying the random walk limits with corresponding functionals of Brownian motion.

Rabi Bhattacharya, Edward C. Waymire

Chapter 19. Brownian Motion on the Half-Line: Absorption and Reflection

Abstract

Two important Markov processes derived from Brownian motion starting from a point x ≥ 0 are (i) Brownian motion absorbed at zero and (ii) Brownian motion reflected at zero. The precise definitions of these two processes are given and their structure delineated, including the Markov property and the computation of the transition probabilities.

Rabi Bhattacharya, Edward C. Waymire

Chapter 20. The Brownian Bridge

Abstract

The Brownian bridge, or tied-down Brownian motion, is derived from the standard Brownian motion on [0, 1] started at zero by constraining it to return to zero at time t = 1. A precise definition is provided and its (Gaussian) distribution is computed. The Brownian bridge arises in a wide variety of contexts. An application is given to a derivation of the Kolmogorov–Smirnov statistic in non-parametric statistics in this chapter. An application to the Hurst statistic in special topics Chapter 27, to mention a few.

Rabi Bhattacharya, Edward C. Waymire

Chapter 21. Special Topic: Branching Random Walk, Polymers, and Multiplicative Cascades

Abstract

The proof of the Kesten–Stigum theorem presented in Chapter 14 involved the application of size-bias methods to branching processes. Related techniques apply to the analysis of a natural class of multiplicative cascades, random polymer models, and to branching random walks. In this chapter we will introduce these three classes of models and provide some basic results for each; specifically a proof of the Kahane–Peyriére theorem for multiplicative cascades based on distinguished path analysis (size-biasing), the infinite volume limit at critical strong disorder in Bolthausen’s conception of weak and strong disorder for tree polymers, and, lastly, for the Biggins–Kingman–Hammersley theorem the calculation of the speed of the leftmost particle in branching random walk. The first example further illustrates the distinguished path analysis, the second introduces the derivative martingale, and the third introduces the many-to-one lemma.

Rabi Bhattacharya, Edward C. Waymire

Chapter 22. Special Topic: Bienaymé–Galton–Watson Simple Branching Process and Excursions

Abstract

The tree contours and heights are identified as two natural discrete parameter stochastic processes associated with the branching process introduced in Chapter 14 as a probability distribution on a metric space of family trees. Analysis of contour paths in the special case of critical (shifted) geometric offspring distributions leads naturally to consideration of continuous parameter processes in terms of Brownian motion excursions.

Rabi Bhattacharya, Edward C. Waymire

Chapter 23. Special Topic: The Geometric Random Walk and the Binomial Tree Model of Mathematical Finance

Rabi Bhattacharya, Edward C. Waymire

Chapter 24. Special Topic: Optimal Stopping Rules

Abstract

Optimal stopping rules are developed to maximize a reward or minimize a loss in a martingale framework by stopping the process at the right time. Applications include the pricing of American options and the “search for the best” (secretary problem) algorithm.

Rabi Bhattacharya, Edward C. Waymire

Chapter 25. Special Topic: A Comprehensive Renewal Theory for General Random Walks

Abstract

This chapter extends the analysis of renewal processes initiated in Chapter 8. The renewal theorem has a rich history that culminated in a unified approach due to David Blackwell.^Fn1 Among the most important ideas introduced by Blackwell in this context is the notion of ladder variables. A comprehensive treatment of this theory is presented here. Example applications include the computation of certain self-similar fractal dimensions arising in iterated function systems in this chapter, and ruin problems in insurance in special topics Chapter 26.

Rabi Bhattacharya, Edward C. Waymire

Chapter 26. Special Topic: Ruin Problems in Insurance

Abstract

The ruin problem of insurance is another catalyst for many interesting methods in the historic development of probability. The basic question asks how the probability of eventual ruin of a company depends on the initial capital of the company. In standard models, one seeks to provide an answer in terms of the premium rate and the distribution of claims, be they relatively moderate or possibly catastrophically large. In the latter case, martingale theory proves useful. The first task for the asymptotic analysis of ruin probabilities is therefore to precisely delineate the roles of light- and heavy-tailed claim size distributions. Martingale theory proves useful for this analysis, especially for the light-tailed case. For the general analysis of ruin in the renewal model, also known as the Sparre–Andersen model, Blackwell’s ingenious notion of ladder heights and epochs, together with his deep general renewal theorem, plays essential roles.

Rabi Bhattacharya, Edward C. Waymire

Chapter 27. Special Topic: Fractional Brownian Motion and/or Trends: The Hurst Effect

Abstract

This chapter involves efforts to understand a phenomenon first reported in connection with the Nile River data by Charles Edwin Hurst (Trans Am Soc Civil Engrs, 116:770–779, 1951), referred to as the Hurst phenomena, and identified as an anomaly by William Feller (Ann Math Statist 22:427–432, 1951). The history is rich by way of consideration of various possible scenarios ranging from heavy tails, long range dependence, or climatic trends. The chapter is concluded with a brief survey of mathematical aspects of the fractional Brownian motion model (Mandelbrot and Wallis, Water Resources Res, 4:909–918, 1968) motivated by this application, as well as in other contexts such as mathematical finance (An interesting construction of Rogers (Math Fin, 7(1):95–105, 1997) shows that the fractional Brownian motion model is not arbitrage-free unless it is Brownian motion. That is, unless it is Brownian motion, it is not a semi-martingale, and consequently there cannot exist an equivalent martingale measure; see Chapter 23 for the financial math implications.) and economics. This includes its extension to a random field model indexed by k-dimensional Euclidean space.

Rabi Bhattacharya, Edward C. Waymire

Chapter 28. Special Topic: Incompressible Navier–Stokes Equations and the Le Jan–Sznitman Cascade

Abstract

The three-dimensional incompressible Navier–Stokes equations are nonlinear partial differential equations formulated in an effort to embody the basic physics of fluid flow in accordance with Newton’s laws of motion (See Landau and Lifshitz. Fluid mechanics, course of theoretical physics, vol. 6, 2nd revised edn. Pergamon Press, Oxford (1987)). The equations are involved in models of fluid flow with applications ranging from modeling ocean currents in oceanography to blood flow in medicine, among many others. However, understanding the existence and/or uniqueness of smooth solutions to these equations, when the initial data is smooth, presents one of the great unsolved mathematical challenges of the twentieth and twenty-first centuries (Ladyzhenskaya (Russian Math Surv 58(2):25–286, 2003), Fefferman (Existence and smoothness of the Navier–Stokes equation. In: Millennium prize problems. Clay Mathematics Institute, Cambridge, pp 57–67 (2006)). The main goal of the present chapter is to present a probabilistic cascade model of LeJan and Sznitman (LeJan and Sznitman (Prob Theory Rel Fields 109:343–366, 1997)) and its subsequent extensions, in which solutions may be represented as expected values of a certain vector product over a random tree, provided the expectations exist.

Rabi Bhattacharya, Edward C. Waymire

Backmatter