\[ \newcommand{\Exg}{\operatorname{\mathbb{E}}} \newcommand{\Ex}{\mathbb{E}} \newcommand{\Ind}{\mathbb{I}} \newcommand{\Var}{\operatorname{Var}} \newcommand{\Cov}{\operatorname{Cov}} \newcommand{\Corr}{\operatorname{Corr}} \newcommand{\ee}{\mathrm{e}} \]

17  Markov chains in discrete space

\[ \]

Summary:

• A Markov chain is a stochastic process where the next step \(X_{i+1}\) depends on the current step \(X_i\), but, given current step \(X_{i}\), does not depend on the past \(X_1, \dots, X_{i-1}\).

• A Markov chain is governed by its transition probabilities \(p(x, y) = \mathbb P(X_{i+1} = y \mid X_i = x)\). These are written in the transition matrix \(\mathsf P\), whose rows add up to 1.

• The simple random walk on the integers at each step goes up 1 with probability \(p\) and down 1 with probability \(q\). If \(p = q = \tfrac12\), it is a simple symmetric random walk.

Read more:

• Voss, An Introduction to Statistical Computing, Subsections 2.3.1

• my notes for MATH2750 Introduction to Markov Processes, Lectures 1, 2 and 5.