Probability and Statistics 2

Markov chains

• example 1
  • machine in 2 states – working × broken
  • w → b … probability 0.01
  • w → w … 0.99
  • b → w … 0.9
  • b → b … 0.1
• example 2
  • a fly which may get caught in a web … absorbing states
• df: stochastic process (náhodný proces)
  • sequence of random variables $X_0,X_1,\dots$ such that "all probabilities are defined"
    • e.g. $P(X_0=1\land X_1=2\land X_3=0)$ is defined
• df: Markov process/chain
  • stochastic process such that
    • $\exists$ finite/countable set $S:\text{Im}X_t\subseteq S\;\forall t$
      • elements of $S$ … states
      • $t$ … time
    • $(\forall i,j\in S)(\exists p_{ij}\in [0,1])(\forall t)(\forall a_0,a_1,\dots,a_t,a_{t+1})$
  • notes
    • this is a discrete time Markov chain
    • discrete space … $|S|\leq |\mathbb N|$
    • time-homogeneous
      • $p_{ij}$ not depeding on $t$
    • Markov condition
      • only applies if the condition probabilities are defined
    • Markov condition … "forgetting the past"
• df: transition matrix $P=(p_{ij})$
• df: transition diagram/graph
  • vertices … $S$
  • directed edges … $\set{(i,j):p_{ij}\gt 0}$
• observation: every row of $P$ sums to 1
• Markov chain is equivalent to a random walk on the transition diagram
  • from state $i$ we go to $j$ with the probability of $p_{ij}$ independent of the past
• in example 1, assume $X_0$, what is $P(X_2=w)$?
  • $P(X_1=w)=p_{11}=0.99$
  • $P(X_2=w)=p_{11}\cdot p_{11}+p_{12}\cdot p_{21}=0.99\cdot 0.99+0.01\cdot 0.9$
    • using the total probability theorem
• probability mass function (PMF, pravděpodobnostní funkce) for $X_0,X_1,\dots$
  • $\pi_i^{(t)}=P(X_t=i)$
    • $t\in\mathbb N_0$
    • $i\in S$
• theorem
  • $\pi^{(t+1)}=\pi^{(t)}\cdot P$
    • where $\pi^{(t)}=(\pi_1^{(t)},\dots,\pi_n^{(t)})$ row vector
  • proof … definition of matrix multiplication & total probability theorem
• theorem
  • $P(X_0=a_0,X_1=a_1,\dots,X_t=a_t)=\pi_{a_0}^{(0)}\cdot P_{a_0a_1}\cdot P_{a_1a_2}\cdot\ldots\cdot P_{a_{t-1}a_t}$
  • proof by induction
• df: probability of $k$-step transition … $r_{ij}(k)$
  • $r_{ij}(k)=P(X_{t+k}=j\mid X_t=i)$
  • $r_{ij}(1)=P(X_{t+1}=j\mid X_t=i)=p_{ij}$
  • it is independent of $t$
• theorem (Chapman-Kolmogorov)
  • $\forall$ Markov chain, $\forall i,j,k:$
    • $r_{ij}(k+1)=\sum_{u=1}^n r_{iu}(k) p_{uj}$
    • $r_{ij}(k+\ell)=\sum_{u=1}^n r_{iu}(k) r_{uj}(\ell)$
    • $r_{ij}(k)=(P^k)_{ij}$
  • proof
    • 1 is a special case of 2 ($r_{uj}(1)=p_{uj})$
    • $1\implies 3$ … matrix multiplication & induction
    • …
• df: $j$ is accessible from $i$ (where $i,j\in S$)
  • $i\to j$
  • $j\in A(i)$
  • $j$ is accessible from $i\equiv$ $\exists t:\underbrace{P(X_t=j\mid X_0=i)}_{r_{ij}(t)}\gt 0$
  • $\iff$ in the transition digraph exists directed path $i\to j$ of length $t$
• df: $i\leftrightarrow j$ ($i$ and $j$ communicate) $\equiv i\in A(j)\land j\in A(i)$
• theorem: $\leftrightarrow$ is an equivalence relation
• proof
  • reflexive: $i\in A(i)$ … $t=0$ in the definition
  • symmetric: the formula $i\in A(j)\land j\in A(i)$ is symmetric
  • transitive: in the digraph $\exists$ path $i$ to $j$, $\exists$ path $j$ to $k$ $\implies\exists$ walk $i\to k$
• decomposition of the transition digraph to components of strong connectivity $\equiv$ finding equivalence classes of $\leftrightarrow$
• df: a state $i\in S$ is recurrent if we return to it with probability 1
  • it is transient otherwise
  • česky rekurentní, tranzientní
• df: Markov chain is irreducible if $\forall i,j\in S:i\leftrightarrow j$
• df: $T_i=\min\set{t\geq 1:X_t=i}$
  • $T_i=\infty$ if the set is empty (there is no such $t$)
  • $T_i$ … random variable
  • $f_{ij}(n)=P(\text{we get to }j\text{ first at time }n\mid X_0=i)=P(T_j=n\mid X_0=i)$
    • we define it for $n\gt 0$
  • $f_{ij}=P(T_j\lt\infty\mid X_0=i)=\sum_{n\geq 1} f_{ij}(n)$
• $i$ is transient
  • $f_{ii}\lt 1$ … probability of ever getting back
  • $\iff P(T_i=\infty)\gt 0$
  • $\iff P(\text{get back infinitely often})\lt 1$
• example – random walk on a line
  • with probability 1/2 we go to the left
  • $f_{00}(2)=(\frac12)^2+(\frac12)^2=\frac12$
  • $f_{00}(1)=f_{00}(3)=\dots=0$
  • $f_{00}(4)=\frac{1}{2^4}\cdot 2$
    • $r_{00}(4)\neq f_{00}(4)$
    • $r_{00}(4)=\frac{1}{2^4}\cdot 4$
  • is 0 recurrent?
    • by definition, we should add $f_{00}(2)+f_{00}(4)+\dots$ and check if it equals 1
    • theorem: $i$ is a recurrent state $\iff\sum_{n=1}^\infty r_{ii}(n)=\infty$
      • $B_n=\begin{cases} 1&\text{ if }X_n=i\\ 0 &\text{ otherwise}\end{cases}$
        • we got back
        • $\mathbb E(B_n\mid X_0=i)=P(X_n=i\mid X_0=i)=r_{ii}(n)$
      • $r_{00}(2n)=$ probability that out of the $2n$ steps, $n$ were to the left, $n$ were to the right
        • $=\frac1{2^{2n}}\cdot{2n\choose n}\doteq\frac c{\sqrt n}$ … see Matoušek, Nešetřil
      • $\sum_{n=1}^\infty \frac{c}{\sqrt n}=\infty$ (taught in calculus)
      • $\mathbb E(T_0\mid X_0=0)=\infty$ (we did not prove that)
• theorem
  • if $i\leftrightarrow j$, then either both $i$ and $j$ are recurrent or both $i$ and $j$ are transient
• for finite Markov chains
  • $C$ … equiv class of $\leftrightarrow$ in a finite Markov chain
  • $C$ is recurrent ($\forall i\in C$ is recurrent) $\iff(\forall i \in C)(\forall j\in S):$ if $i\to j$ then $j\in C$
    • → $C$ is closed
• stationary distribution / steady state distribution
  • df: $\pi:S\to [0,1]$ such that $\sum_{i\in S}\pi_i=1$ is called a stationary distribution if $\text{``}\pi P=\pi\text{"}$
    • $\forall i:\sum_i\pi_i p_{ij}=\pi_j$
  • if $\pi^{(0)}$ (the PMF of $X_0$) is $\pi$, then $\pi^{(1)}$ is $\pi$ as well
  • $\pi^{(1)}=\pi^{(0)}P$
• theorem: if a Markov chain is finite, aperiodic (→ not periodic) and irreducible, then
  1. $\exists$ unique stat. distribution $\pi$
  2. $\forall i:\lim_{n\to\infty}(P^n)_{ij}=\pi_j$
• example of periodic Markov chain: two states, we change the state with probability 1
• df: $i\in S$ has period $d_i:=\text{gcd}\set{t:r_{ii}(t)\gt 0}$
  • $i\in S$ is aperiodic if $d_i=1$
• df: $i$ is null recurrent if $i$ is recurrent and $\mathbb E(T_i\mid X_0=i)=\infty$
  • $i$ is positive recurrent if $i$ is recurrent and $\mathbb E(T_i\mid X_0=i)\lt\infty$
• example: random walk on a line
• theorem
  • if $i,j\in S$, $i\leftrightarrow j$, then
    • $d_i=d_j$
    • $i$ is transient $\iff j$ is trainsient
    • $i$ is recurrent $\iff j$ is recurrent
    • $i$ is null recurrent $\iff j$ is null recurrent
    • $i$ is positive recurrent $\iff j$ is positive recurrent
  • these are properties of the class of $\leftrightarrow$
• theorem
  • if a Markov chain is irreducible, aperiodic and finite, then
    • there exists a unique stationary distribution $\pi$: $\pi P=\pi$
    • $\forall ij:\lim(P^t)_{ij}=\pi_j$
      • $P(X_t=j\mid X_0=i)\doteq\pi_j$
  • actually, MC does not have to be finite, it suffices if all states are positive recurrent (?)
  • steady state (?)
    • if $\pi^{(0)}=\pi$ then $\pi^{(1)}=\pi$
• the proof is not easy, here is a cheat proof
  • $Pj=Ij$ (row sums are 1)
  • $(P-I)j=0$
  • $P-I$ is sungular matrix
  • $\exists x:x(P-I)=0\implies xP=x$
  • $\pi=\frac xc$ such that $\sum \pi_i=1$
  • problem
    • $x$ may have negative coordinates
    • to fix: use Perron-Frobenius theorem
    • the correct proof is shown in class of probabilistic techniques
• to find $\pi$, solve system of linear equations $\pi P=\pi$, add $\sum_{i\in S}\pi_i=1$
  • $\pi$ describes long-term behavior of the MC
  • Page Rank (original google search) … MC model of people browsing WWW
  • given $\pi$, we can find a MC such that $\pi$ is its stationary distribution; then we can run the MC to generate random objects with distribution $\pi$
    • Markov chain Monte Carlo (MCMC)
• detailed balance equation
  • MC may have this property
  • $\forall i\neq j:\pi_iP_{ij}=\pi_jP_{ji}$
• to imagine this: ant colony moving independently according to a Markov chain
  • stationary distribution $\iff$ the same number of ants at each state at each time – ants don't "accumulate"
• detailed balance equation implies $\pi P=\pi$
  • detailed balance equation is stronger than $\pi P=\pi$
• MCMC algo. sketch
  • choose aperiodic irreducible digraph
  • $p_{ij}=\min\set{1,\frac{\pi _j}{\pi_i}}\cdot C$
  • $p_{ji}=\min\set{1,\frac{\pi_i}{\pi_j}}\cdot C$
  • choose $C$ such that
    • $\forall i:\sum_{j\neq i} p_{ij}\lt 1$
    • df. $p_{ii}=1-\sum_{j\neq i}p_{ij}\gt 0$
    • $\implies d_i=1$
  • tune the process to make convergence fast
• absorbing state $i:p_{ii}=1$
  • $A$ … set of absorbing states
  • question 1: which $i\in A$ we end at?
  • question 2: how fast?
• example: $0\in A$ (?)
  • $a_i=P(\exists t:X_t=0\mid X_0=i)$
• $\mu_i=\mathbb E(T\mid X_0=i)$
  • $T=\min\set{t: X_t\in A}$
• theorem: $(a_i)_{i\in S}$ are the unique solution to
  • $a_0=1$
  • $a_i=0$ if $i\in A,\,i\neq 0$
  • $a_i=\sum_j p_{ij}\cdot a_j$ otherwise
• theorem: $(\mu_i)_{i\in S}$ are unieque solutions to
  • $\mu_i=0$ if $i\in A$
  • $\mu_i=1+\sum_j p_{ij}\mu_j$ if $i\notin A$
• proof
  • $P(\exists t:X_t=0\mid X_0=0)=1$
  • $P(\exists t: X_t=0\mid X_0=i\in A\setminus\set{0})=0$
  • $i\notin A$
    • $B_j=\set{\exists t:X_t=0}$
    • $P(B_i)=\sum_{j\in S} p_{ij}\cdot \underbrace{P(B_i\mid X_1=j)}_{P(B_j)=a_j}$
• example: drunk person on their way home
  • $A=\set{0}$
  • $\mu_0=0$
  • $\mu_1=1+\frac12\mu_0+\frac12\mu_2$
  • $\mu_2=1+\frac12\mu_1+\frac12\mu_3$
  • $\mu_{n-1}=1+\frac12\mu_{n-2}+\frac12\mu_{n}$
  • $\mu_n=1+\mu_{n-1}$
  • solution
    • $\mu_1=2n-1$
    • $\mu_n=n^2$