Discrete Time Markov Chains - Random Notes Go Brrrrrrr

Consider a sequence of random variables $(X_{n})$ that takes values from a countable set $I$ called **the state space**. * Usually the sequence is a change over time, e.g. the location of an elevator at time $n$, and the state space is the set of floors $\{0,1,2,\dots k\}$ * In some cases it can use a more abstract sense of time, e.g. the $n$th character in an email, with state space $\{ a,\dots, z\}$. If we treat $I$ as a vector $I=(I_{1},\dots)$, the distribution of $X_{n}$ can be written as a row vector $\lambda(t)$, where $(\lambda (t))_{i}=\mathbb{P}(X_{t}=I_{i})$. * In particular, $X_{0} \sim \lambda_{0}$ is the **initial distribution**. ### Homogeneous Markov Chains *Big idea: homogenous Markov chains are memoriless random processes.* * A sequence of random variables $X=(X_{1},X_{2},\dots)$ all taking values in some state space $I$ is called a **Markov chain** if for any $k\ge 1$, any states $i_{0},\dots,i_{k}$: $\mathbb{P}(X_{k}=i_{k}|X_{k-1}=i_{k-1})= \mathbb{P}(X_{k}=i_{k}|X_{k-1}=i_{k-1},\dots,X_{1}=i_{1})$*That is, the next state of the chain $X_{k}$ only depends on the present state $X_{k-1}$, not the past.* * A Markov chain is **time-homogeneous** if the **transition probability** $\mathbb{P}(X_{k}=j|X_{k-1}=i)=p_{ij}$is constant, i.e. invariant of $k$. All chains in this course are homogeneous. * *Hence transition probability $p_{ij}$ is the probability of going from state $i$ to state $j$.* * Homogeneous Markov chains satisfy the **Markov property**: for subsets $A_{1,\dots m+n}\subseteq I, \, i \in I,$$\begin{align*} \mathbb{P}(X_{m+1}\in A_{m+1},&\dots, X_{m+n}\in A_{m+n}|X_{m}=i, X_{m-1}\in A_{m-1},\dots, X_{1}\in A_{1})\\ \\ &=\mathbb{P}(X_{m+1}\in A_{m+1},\dots, X_{m+n}\in A_{m+n}|X_{m}=i) \\\\ &=\mathbb{P}(X_{1}\in A_{1},\dots, X_{n}\in A_{n}|X_{0}=i_{0}) \end{align*}$ - *The first equality: Markov chains do not remember what happened before the present.* - *The second equality: homogeneous Markov chains are **translation-invariant**. - A sufficient criterion for a Markov chain is that: a sequence of random variable $Y=(Y_{0},\dots)$ is a Markov chain if there exists a function $f$ and an sequence $X=(X_{0},\dots)$ such that: $Y_{n+1}=f(Y_{n},X_{n+1}),\, X_{n+1} \text{ independent of }Y_{1,\dots,n}$ ### N-Step Transition Probabilities * The **$n$-step transition probability** is defined to be$p_{ij}^{(n)}=\mathbb{P}(X_{n}=j|X_{0}=i)$ * For homogeneous chains, the **transition matrix** $P\in \mathbb{R}^{|I|^{2}}:\, P_{i,j}=p_{ij}$records the **transition probabilities**. The sequence $X$ can be described as $X\sim \text{Markov}(\lambda_{0},P)$. * The matrix can be (countably) infinite if $I$ is. * The **Chapman-Kolmogorov equations** describe n-step transitions with the transition matrix: for all homogeneous Markov chains, $\begin{align*} p_{ij}^{(n)}&=(P^n)_{ij}\\ p_{ij}^{(m+n)}&=(P^mP^n)_{ij}=\sum_{k \in I} p_{ik}^{(m)} p_{kj}^{(n)} \end{align*}$ * The first equation: applying the transition matrix represents a 1-step move in time. * The second equation: the probability of going from $i$ to $j$ in $m+n$ steps can be broken down by conditioning on it passing $k$ at the $m$th step. > Proof: > First equation: induction. > Second equation: immediate from the first, or use the law of total probabilities. - By the C-K equations, Markov chains can be represented by right-applying the transition matrix: for $n\ge m,$$\lambda(n)=\lambda(m)P^{n-m}$ ## Structures of DTMC ### Class Structures * Two states $i,j$ of a Markov chain **communicate**, denoted $i\leftrightarrow j$ if: $\exists m,n:p_{ij}^{(m)}\ne 0,\, p_{ji}^{(n)}\ne 0$ * *That is, there is a chance to go from $i$ to $j$, and vice versa.* * As an equivalence relation, communication partitions the state space into **communicating classes**. A Markov chain is **irreducible** if it only has one communicating class. * A **closed class** $C$ is a communicating class such that: $\forall c \in C, d \notin C, n\in \mathbb{N}:\, \,p_{cd}^{(n)}=0$It is also called an **absorbing state** if it has only one element. * *That is, it is impossible to leave $C$ once inside it.* * An **open class** is a communicating class that is not closed. ### Periodicity * The **period** of a state $i$ is $\gcd \big\{n:p_{ii}^{(n)}>0\big\}$and the state is **aperiodic** if its period is $1$. * For example, a random walk of a length-$n$ cycle has period $2$ if $n$ even; if $n$ is odd, then the chain has period $1$ hence is apeiodic. * The period is a class property: communicating states have the same period. > Proof: suppose $i \leftrightarrow j$, with $m,n: p_{ij}^{(m)}\ne 0,\, p_{ji}^{(n)}\ne 0$. > Define $S_{i}=\big\{k:p_{ii}^{(k)}>0\big\}$, similarly for $S_{j}$. > Then for any common divisor $d$ of $S_{i}$, > $ p_{ii}^{(m+n)}\ge p_{ij}^{(m)}p_{ji}^{(n)}>0 \Longrightarrow (m+n) \in S_{i}, d|(m+n)$and for any $a \in S_{j}$, $p_{ii}^{(m+a+n)}\ge p_{ij}^{(m)}p_{jj}^{(a)}p_{ji}^{(n)}>0\Longrightarrow (m+n+a) \in S_{i}, d|(m+n+a)$ Hence $d|a$, $d$ is also a divisor of the set $S_{j}$, > By symmetry, $S_{i}, S_{j}$ have the same divisors, hence the same $\mathrm{gcd}$, and so states $i,j$ have the same period. ### Hitting Probability * The **hitting probability** of a subset $A \subseteq I$ from state $i$ is$h_{i}^A=\mathbb{P}(X_{n} \in A \text{ for some }n \ge 0 \,|\, X_{0}=i)$ and if $A$ is closed, it is also called the **absorption probability**. * The hitting probabilities $(i\in I:h_{i}^A)$ of a Markov chain is the minimal non-negative solution to the equations $h_{i}^A=\begin{cases} 1 &\text{if }i\in A \\ \sum_{j\in I}p_{ij}h_{j}^A & \text{if } i\notin A \end{cases}$where minimality means that $(h_{i}^A)$ is term-wise no larger than any other solution. > Proof: we can verify that $(h_{i}^A)$ satisfies the equations by conditioning on $X_{0}=i,X_{1}=j$. > To prove minimality, take any solution $(x_{i})$, and we shall show that $\forall i \in I: x_{i}\ge h_{i}$. > Define the "probability of hitting before step $Nquot;: $q_{i}^{(N)}=\mathbb{P}(\exists n\le N: X_{n}\in A\,|\, X_{0}=i)$so $q_{i}^{(N)}=\sum_{j}p_{ij}q_{j}^{(N-1)}$, and induction on $N$ gives $\forall N, q_{i}^{(N)}\le x_{i}$. > Hence $\begin{align*} x_{i}\ge \lim_{ N \to \infty }q_{i}^{(N)}&=\mathbb{P}\Big\{\bigcup_{N}\{\exists n\le N: X_{n}\in A\,|\, X_{0}=i\} \Big\} \\&=\mathbb{P}\{\exists n: X_{n}\in A\}\\ &=h_{i}^{A} \end{align*}$ ### Recurrence and Transience *Big idea: recurrence and transcience describes whether a Markov chain will indefinitely return to a particular state.* * For convenience, we will denote the **return probability** as $r_{i}=\mathbb{P}(\exists n\ge{1}: X_{n}=i\,|\, X_{0}=i)$*but this notation is not standard.* * A state $i\in I$ is **transient** if $r_{i}<1$, which means that $\mathbb{P}(\text{the chain hits } i \text{ infinitely many times}\,|\, X_0=i)=\lim_{ k \to \infty }r_{i}^k =0$ * A state $i\in I$ is **recurrent** if $r_{i}=1$, which means that $\mathbb{P}(\text{the chain hits } i \text{ infinitely many times}\,|\, X_0=i)=\lim_{ k \to \infty }r_{i}^k =1$ * A state $i$ is recurrent if and only if $\sum_{n\ge 1} p_{ii}^{(n)}=\infty$. > Proof: the total number of hits has expectation $\sum_{n} \mathbb{E}[\mathbf{1}(X_{n}=i)\,|\, X_{0}=i]=\sum_{n}\mathbb{P}(X_{n}=i\,|\, X_{0}=i)=\sum_{n}p_{ii}^{(n)}$Then (the state is recurrent) $\iff$ (the expected number of hits is infinite) $\iff$ (the sum is infinite). * Recurrence/transience is a class property: states in the same communicating class are either all recurrent or all transient. * Recurrent classes are all closed; all finite, closed classes are recurrent. > The two propositions are proved in problem sheet 3. ### Hitting and Return Times * The (first) **hitting time** of set $A \subseteq I$ is the random variable$H^A=\inf\{n\ge 0: X_{n}\in A\}$ * The **mean hitting time** of $A$ from $i$ is $k_{i}^{A}=\mathbb{E}[H^{A}\,|\, X_{0}=i]$ * The mean hitting times of the Markov chain $(k_{i\in I}^A)$ is the minimal non-negative solution to the equations $k_{i}^A=\begin{cases} 0 &\text{ if }i\in A \\ 1+\sum_{j}p_{ij}k_{j}^{A} & \text{ if } i\notin A \end{cases}$ > The proof uses the same strategy as the proof for hitting probabilities. * The **mean return time** of a state $i$ is$m_{i}=\mathbb{E}[\,\inf\{n\ge 1: X_{n}=i\}\,|\, X_{0}=i\,]$*That is, the expected time to return to the state after starting from it.* * A recurrent state with a finite mean return time is called **positive recurrent**; else it is **null recurrent**. * A transient state always has a mean return time of $\infty$, since it has a positive probability of never returning. ### Gambler's Ruin as a Markov Chain * Model > Let the gambler's wealth at time $t$ be $X_{t}$, and the winning probability be $p$. They starts with $X_{0}=\textdollar n$. > The transition probabilities are $p_{ij}=\begin{cases} p &\text{ if } j=i+1,\ i\ne 0 \\ q=1-p &\text{ if } j=i-1,\ i\ne 0 \\ 0 &\text{ if otherwise} \end{cases}$ * Hitting probabilities > The probability of hitting zero starting from state $i$, $(h_{i})$, comes from the equations$\begin{align*} h_{0}&=1 \\ h_{i\ne 0} &= \sum_{j}p_{ij}h_{j}=ph_{i+1}+qh_{i-1} \end{align*}$which has the general solution $h_{i}=A+B\big( \frac{q}{p}\big)^i$, where $h_{0}=1$ requires $A+B=1$. > Then non-negativity and minimality requires $(A,B)=\begin{cases} (1,0) &\text{ if }p\le q \\ (0,1) &\text{ if }p>q \\ \end{cases}$So the hitting probability is $1$ in the first case, and $(q / p)^{i}$ in the second case. * Transience/Recurrence > The state $0$ is obviously recurrent, since it is an absorbing state. > > The rest of the chain communicate, so it is sufficient to find the transience/recurrence of the state $1$. Its return probability is $r_{1}<p<1$, so it is transient. Hence the entire class $\{1,2,\dots \}$ is transient. > > *The lecture notes studies the modified chain where $p_{01}>0$, which makes the chain irreducible, and we can find the return probability and mean return time to $0$.* * Mean hitting time of $0$ > If $p > q$, hitting probability is $(q / p)^i<1$, so the mean hitting time is infinite. > > If $p\le q$, the mean hitting times $(k_{i})$ solve the equations $\begin{align*} k_{0}&=1 \\ k_{i\ne 0} &= 1+\sum_{j}p_{ij}k_{j}=1+pk_{i+1}+qk_{i-1} \end{align*}$*The lecture notes involve some Olympic-level hand-waving to claim $k_{i}=\beta i$, and the answer follows. To see why, note that $\begin{align*} k_{i}&= \mathbb{E}[\text{time to hit }(i-1) \text{ from }i]+k_{i-1}\\ &= k_{1} +k_{i-1} \end{align*}$by memorilessness. Then $\beta=k_{1}$.* > > When $p<q$, solving gives $k_{i}=i / (q-p)$. > > When $p=q$, any finite $\beta=k_{1}$ failes, hence the mean hitting times $(k_{i})$ must be all be infinite. --- ## Equilibrium and Convergence of Markov Chains * Recall that the distribution of the Markov chain variable $X_{n}$ can be expressed as a row vector $\lambda(t)$, and right-applying the transition matrix $Plt;u> moves the distribution forward in time: for $n\ge m,$$\lambda(n)=\lambda(m)P^{n-m}$In particular, if $\lambda_{0}$ is the initial distribution, then $X_{n} \sim\lambda_{0} P^n$. - A distribution $\pi$ is a **stationary distribution** of a Markov chain with transition matrix $P$ if it is the left-eigenvector of $P$ with eigenvalue $1$: $\pi=\pi P$Note that it is the left-eigenvector, not the usual right-eigenvector. * *That is, the transition matrix does not change the stationary distribution over time.* ### Convergence Theorems * Existence and uniqueness of the stationary distribution: if $P$ is irreducible, then $P \text{ positive-recurrent} \iff\exists!\pi \text{ stationary, where }\,\pi_{i}=\frac{1}{m_{i}}$where $m_{i}$ is the mean return time to state $i$. * Convergence to the stationary distribution: if $P$ is irreducible and aperiodic with stationary distribution $\pi$, any initial distribution has $\forall i,j:$ $\begin{align*} \mathbb{P}(X_{n}=j)\to \pi_{j}\\ p_{ij}^{(n)}\to \pi_{j} \end{align*}$ - *Aperiodicity is important, as a periodic chain "remembers" its initial distribution.* * Ergodic Theorem: for irreducible chains, the proportion of time spent on state $i$ converges to $1 / m_{i}$ almost surely: $\begin{align*} \frac{\sum_{t=0}^{n-1}\mathbb{1}_{(X_{t}=1)}}{n}\to \frac{1}{m_{i}} \text{ a.s.} \end{align*}$where for null-recurrent and transient states ($m_{i}=\infty$), we interpret $1 / m_{i}$ to be $0$. ---