Coin-Turning, Random Walks and Inhomogeneous Markov Chains

The following sections are included:

• Dedication
• Preface
• Acknowledgment
• About the Authors
• Contents

This book discusses aspects of time-inhomogeneous Markov chains and related random walks. In this brief chapter, we review notation, as well as some technical tools that are needed in the rest of the chapters. Some of these are related to the Borel–Cantelli lemma, some are anti-concentration inequalities, some are basic results on martingales, while the last two parts concern moment problems, random measures and point processes. The first-time reader may want to skip straight to Chapter 2 and come back here when needed…

The idea of Markov chains was born in 1906 in Russia, when P. Chebyshev’s student A. A. Markov (1856–1922, Figure 2.1) invented them, as an “extension of the law of large numbers to dependent quantities” as well as a tool for statistical text analysis, which he later used when analyzing Pushkin’s Eugene (Yevgeniy) Onegin. It was around the same time that the theory of finite matrices with non-negative entries was developed, mainly by O. Perron and G. Frobenius in Germany…

In this chapter, we discuss an important technique for the analysis of reversible Markov chains: the method of electric networks

Consider a time-homogeneous Markov chain on a finite state space $\text{S}≔\left\{0,1,2,\dots ,r\right\}$, $r\ge 1$, so that S has at least two states. Suppose that the state r is an absorbing state, that is, $P_{rr}=1$ and $P_{rj}=0$ for all $j\ne r$, and that it is the only absorbing state (or communication class), that is, r is accessible from any state. It is easy to see that in this case

For a Markov chain, time inhomogeneity means that the transition probabilities p_ij(k) := P(X_k = j | X_k−1 = i) depend on k. Hence, we have a sequence of transition matrices P_k := {p_ij(k)}, k ≥ 1, to deal with. We again assume that the state space S is finite, |S| = N ≥ 1.

In this chapter, we study a specific time-inhomogeneous Markov chain. It is the simplest case in the sense that the state space has only two elements. Using a more intuitive language, we examine what happens if, instead of tossing a coin, we turn it over (from heads to tails and from tails to heads), with certain probabilities. So, now we are working with a Markov chain on the state space S := {T, H} or S := {0, 1}…

In Chapter 5, the coin-turning process X₁, X₂, … has been studied with a focus on ${\overline{X}}_N≔\frac{1}{N}\sum _{n=1}^N{X}_n$, that is, the empirical frequency of 1’s (“heads”) in the sequence of X_n’s, and the centered version $Y_n≔2X_n-1\in \{-1,+1\}$ was introduced too. Recall also Remark 5.1 and that the latter can be defined equivalently as

where W₁, W₂, W₃, … are independent Bernoulli variables with parameters P₁, P₂, P₃, …, respectively, and P₁ = 1/2, and that

As mentioned in Section 2.6, the Pólya (more precisely, Pólya–Eggenberger) urn and its generalizations have been studied intensely in the last hundred years since their discovery in 1923, see, e.g., Mahmoud (2009). Probabilistic studies of urns go back in history way beyond the Pólya urn though; in fact, they were already proposed in Jacob Bernoulli’s Ars Conjectandi, published in 1713, which is often considered the first scientific discussion of a theory of probability. Thus, not surprisingly, the theory of urn models is much more standard and available than the general theory of inhomogeneous Markov chains. It is therefore beneficial to find a connection between the two. This short chapter is devoted to some initial exploration of this connection. Our two keywords will be “mimicking” and “Markovization”…

The following sections are included:

• Introduction
• Integer-Valued A-Walks
• A Non-Trivial Recurrent Example
• Continuous Example
• Sublinear Growth of Step Sizes
• Rademacher Walk in Higher Dimensions
• Appendix: Generalization of Blair Sullivan’s Results

The process described in this chapter is a higher-dimensional analog of the coin-turning walk, and it shall henceforth be referred to as the “conservative random walk.” We opted for this term because this process demonstrates a tendency to retain its direction over long intervals. It is worth noting that analogous processes, albeit under varying nomenclature, have been studied in the literature, particularly within continuous-time frameworks…

The following sections are included:

• Introduction
• Some Technical Tools
• Transience
• Recurrence
• Some Particular Cases
  • Case α = β ≥ 0
  • Case α ≤ 0, β = 0
  • Case 2β − α = 1, −1 ≤ α ≤ 1: open problem
• Application to Urn Models

The following sections are included:

• Bibliography
• Index