Stochastic Process Note

Random Vector

Definition

$\mathbf{X}:(\Omega ,\mathcal{F})\to ({\mathbb{R}}^d,{\mathcal{R}}^d),\mathbf{X}=(X_1,X_2,\dots ,X_d)$

Column vector whose components are random variables $X:(\Omega ,\mathcal{F})\to (\mathbb{R},\mathcal{R})$.

$\mathbf{X}(\omega )=(X_1,X_2,\dots ,X_d)(\omega )=(X_1(\omega ),X_2(\omega ),\dots ,X_d(\omega ))=(x_1,x_2,\dots ,x_d)$

Link to original

Stochastic Process

Definition

$\{X_i|i\in I\}$ where each $X_i$ is a Random Variable.

Stochastic process is a collection of random variables defined on a common probability space $(\Omega ,\mathcal{F},P)$, and whose index represents time.

Notation

Stochastic Process whose Initial Distribution is a Delta Distribution

If a random variable $X$ has a positive probability only at $X=x$ and otherwise $0$, then the distribution $\mathbf{\mu }$ is expressed as ${\mathbf{\delta }}_x$. Also, the probability and expectation of $X$ are expressed as $P_{{\mathbf{\delta }}_x}(X=x)=1$, $P_{{\mathbf{\delta }}_x}(X\ne x)=0$ and $E_{{\mathbf{\delta }}_x}(X)=x$ respectively.

The probability of $X_t$ given some initial distribution is expressed as following

• $P_i(X_t=k):=P_{{\mathbf{\delta }}_i}(X_t=k)=P(X_t=k|X_0=i)$ where $i$ is the initial state
• $P_{\mathbf{\pi }}(X_t=k)={\pi }_k$ where $\mathbf{\pi }$ is the initial distribution

where $\{X_t\}$ is a HMC defined on the state space $E$

Averages

For a sequence of random variables $X_1,X_2,X_3,\dots ,X_i,\dots ,X_n$

Ensemble Average

$E(X_t)$

Time Average

$\frac{1}{T}{\sum }_{t=1}^T{X}_t$

Facts

If the random variables of a stochastic process satisfy i.i.d condition, then the ensemble average is equal to time average

Summary

The Distributions of Stochastic Process

	Empirical distribution	Stationary Distribution	Limiting Distribution
Used for	Every stochastic process	Every stochastic process	Markov chain
Expression	$\bar{\mathbf{\pi }}=\frac{1}{T}\left[\begin{array}{c}\mathtt{sum}(X_t=0)\\ \mathtt{sum}(X_t=1)\end{array}\right]$	$\mathbf{\pi }=\left[\begin{array}{c}E(I(X=0))\\ E(I(X=1))\end{array}\right]$	${\mathbf{p}}_{\star }={\lim }_{t\to \infty }\left[\begin{array}{c}{p}_{?0}^{(t)}\\ p_{?1}^{(t)}\end{array}\right]$
Consideration of $\omega$	use single $\omega$	use every $\omega$	don’t consider $\omega$
Statistical distribution?	O	O	X
Analytic value?	X	O	O
Related to data?	O	X	X
Related to limit?	O	X	O
Related to LLN?	O	O	X
Description	Averaged calculated by the data	Theoretical expectation	Theoretical convergence value

${\bar{\mathbf{\pi }}}^{⊺}$: the empirical distribution of $\{X_t\}$ with consideration of single $\omega$ (use time average)
${\mathbf{\pi }}^{⊺}$: the Stationary Distribution of $\{X_t\}$ with consideration of every $\omega$ ${\mathbf{p}}_{\star }^{⊺}$: the Limiting Distribution of $\{X_t\}$ obtained by the limit of $\mathbf{P}$ without consideration of $\omega$. Used with Markov Chain

where $\{X_t\}$ is a sequence of random variables

Link to original

Markov Property

Definition

Markov property refers to the memoryless property of a Stochastic Process.

Consider a Probability Space $(\Omega ,\mathcal{F},P)$ with a Filtration $({\mathcal{F}}_s,s\in I)$, and a Measurable Space $(S,\mathcal{S})$. A Stochastic Process $X=\{X_t|\Omega \to S{\}}_{t\in I}$ is said to possess the Markov property if $\forall A\in \mathcal{S},\forall s,t\in I\text{s.t.}s<t,P(X_t\in A|{\mathcal{F}}_s)=P(X_t\in A|X_s)$ Here, ${\mathcal{F}}_s$ in the LHS represents all information up to time $s$, whereas $X_s$ conditions only on the single value at time $s$.

In the case where $S$ is a discrete set and $I=\mathbb{N}$, this can be reformulated as follows $\forall n\in \mathbb{N},P(X_{t+1}=x_{n+1}|X_n=x_n,\dots ,X_1=x_1)=P(X_{n+1}=x_{n+1}|X_n=x_n)$

Link to original

Markov Chain

Definition

$(S,P)$ A Markov chain is a Stochastic Process $\{X_t\}$ that satisfies Markov Property. It consists of a set of states $S$ and a Transition Probability Matrix $P$

Summary

Conditions and Properties of Markov Chain (Finite States)

Example	Finite	IRR	Aperiodicity	$\exists !{\mathbf{p}}^{\star }$^[a unique Limiting Distribution]	$\exists !\mathbf{\pi }$^[a unique Stationary Distribution]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }$^[Ergodic Theorem]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }={\mathbf{p}}^{\star }$^[Ergodicity]
	O	X	X	X	X	X	X
Identity/Block matrix	O	X	O	X	X	X	X
Exchange matrix	O	O	X	X	O	O	X
Ergodic Markov Chain	O	O	O	O	O	O	O

flowchart LR
  mc[HMC] --> finite
  
  subgraph finiteness
    finite([finite])
  end
  
  finite --> finite_mc
  finite_mc --> irreducible
  finite_mc --> reducible
  
  subgraph Irreducibility
    irreducible([irreducible])
    reducible([reducible])
  end
  irreducible --> irr_mc[Irreducible MC]
  reducible -->|divide|irr_mc

  irr_mc ---|holds|egt([Ergodic Theorem])
  irr_mc --> aperiodic
  
  subgraph Aperiodicity
    aperiodic([aperiodic])
  end
  
  aperiodic --> ergmc[Ergodic MC]

Conditions and Properties of Markov Chain (Infinite States)

IRR	Nature	Aperiodicity	$\exists !{\mathbf{p}}^{\star }$^[a unique Limiting Distribution]	$\exists !\mathbf{\pi }$^[a unique Stationary Distribution]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }$^[Ergodic Theorem]	$\bar{\mathbf{\pi }}\to \mathbf{\pi }={\mathbf{p}}^{\star }$^[Ergodicity]
O	Transient	can’t define	X	X	X	X
O	Null recurrent	no matter	X	X	X	X
O	Positive recurrent	X	X	O	O	X
O	Positive recurrent	O	O	O	O	O

flowchart LR
  mc[HMC]
  mc --> irreducible
  mc --> reducible
  
  subgraph Irreducibility
    irreducible([irreducible])
    reducible([reducible])
  end
  
  irr_mc[Irreducible MC]
  irreducible --> irr_mc
  reducible -->|divide|irr_mc
  
  irr_mc --> pr
  irr_mc --> nr
  irr_mc --> tr
  
  subgraph Recurrence
    pr([positive recurrent])
    nr([null recurrent])
    tr([transient])
  end
    
  pr_mc[Recurrent MC]
  pr --> pr_mc
  pr_mc --> aperiodic

  egt([Ergodic Theorem])
  pr_mc ---|holds|egt

  subgraph Aperiodicity
    aperiodic([aperiodic])
  end
  
  aperiodic --> ergmc[Ergodic MC]

Link to original

Homogeneous Markov Chain

Definiotion

Markov Chain that $P(X_{t+1}=j|X_t=i)$ are the same for any $t$, $\{X_t\}$

Link to original

Transition

Definition

${\mathbf{\mu }}_{t+1}={\mathbf{P}}^{⊺{\mathbf{\mu }}_t}\iff {\mathbf{\mu }}_{t+1}^{⊺}={\mathbf{\mu }}_t^{⊺}\mathbf{P}$

where $\mathbf{\mu }$ is the distribution of states and $\mathbf{P}$ is Transition Matrix

Link to original

Transition Probability

Definition

$p_{ij}=P(j|i)=P(X_{t+1}=j|X_t=i)$ where $\{X_t{\}}_{t\ge 0}$ is HMC that has countable state space $E$

The conditional probability of the Transition from state $i$ to $j$

Facts

$p_{ij}\ge 0$

Link to original

Transition Probability Matrix

Definition

$P=[P_{ij}]$ A transition probability matrix $P$ is a matrix whose $(i,j)$-th element is $p_{ij}$. where each $p_{ij}$ is a Transition Probability of HMC $\{X_t{\}}_{t\ge 0}$ having countable state space

Facts

Since the number of elements of state space can be infinity, strictly speaking $P$ is not a matrix. However, several operations of matrix are satisfied for the $P$

${\sum }_{j\in E}{p}_{ij}=1$ The sum of each row of a transition matrix is one

Link to original

Invariant Measure

Definition

${\tilde{\mathbf{\pi }}}^{⊺}\mathbf{P}={\tilde{\mathbf{\pi }}}^{⊺}$ The Measure ${\tilde{\mathbf{\pi }}}^{⊺}$ that satisfies the above

where $\mathbf{P}$ is a Transition Matrix of the Markov Chain $\{X_t\}$

Link to original

Stationary Distribution

Definition

Invariant Measure satisfying definition of distribution

distribution $\mu$ that satisfies $\mu p=\mu$ where $\mu$ is a Distribution defined on Measurable Space $(E,\mathcal{B}(E))$ and $\mu p(\{x\}):={\sum }_{y\in E}\mu (\{y\})p_{yx}$

distribution $\mu$ that satisfies ${\mu }^{⊺}\mathbf{P}={\mu }^{⊺}$ where $\mathbf{P}$ is a Transition Matrix of the Markov Chain $\{X_t\}$

Facts

When $\mu$ is a stationary distribution of the finite stochastic process $\{X_t\}$, it becomes a PMF of the random variable $X_{\infty }$

For the finite states case, the stationary distribution can be obtained using Eigendecomposition. The stationary distribution is the unit eigenvector^[whose Norm is one] corresponding to the eigenvalue with value one.

Finite HMC has at least one Stationary Distribution

If we set the initial distribution ${\mathbf{\mu }}_0$ of the stochastic process to a stationary distribution $\mu$, the stochastic process $\{X_t\}$ has the same distributions for every $t$ (not independent)

$\{X_t\}$ is a IRR-HMC $\to \exists \mathbf{\pi }\iff \exists !\mathbf{\pi }\iff$ PR

If $\{X_t\}$ is a IRR HMC, then the $\{X_t\}$ has a Stationary Distribution $\iff$ $\{X_t\}$ has a unique Stationary Distribution $\iff$ Positive recurrent

Link to original

Accessibility

Definition

$i\to j\iff \exists T_0\in {\mathbb{N}}_0:p_{ij}^{(T_0)}>0$

$\forall i,j\in E$, $j$ is accessible from $i$

where $\{X_t\}$ is a HMC defined on the state space $E$ and the $\mathbf{P}$ is a transition matrix of $\{X_t\}$ and $p_{ij}^{(T_0)}$ is a $(i,j)$-th element of ${\mathbf{P}}^{T_0}$

Link to original

Equivalence Relation

Definition

A binary Relation $\sim$ on set $X$ that satisfies the following conditions for all $a,b,c\in X$

• Reflective: $a\sim a$
• Symmetric: $a\sim b\Rightarrow b\sim a$
• Transitive: $a\sim b\wedge b\sim c\Rightarrow a\sim c$

Facts

The equivalence relation may be constructed from the Partition

Link to original

Communication

Definition

$i\leftrightarrow j\iff i\to j\wedge j\to i$

$\forall i,j\in E$: $i,j$ are accessible from each other

where $E$ is a state space

Facts

Communication is an Equivalence Relation

• $i\leftrightarrow i$
• $i\leftrightarrow j\Rightarrow j\leftrightarrow i$
• $i\leftrightarrow j,j\leftrightarrow k\Rightarrow i\leftrightarrow k$

Link to original

Communication Class

Definition

$E_k$ where $E=\underset{k=1}{\overset{\infty }{⨄}}{E}_k$ The Equivalence Class of the state space $E$ by the Communication $\leftrightarrow$

Example

Divide Transition Matrix $\mathbf{P}$ by Communication

where $R_i$ are Recurrent block matrix and $T$ is Transient block matrix

Facts

$E_1,E_2,\dots$ are pairwise coprime

$\forall k:E_k$ are IRR

$\forall k:E_k$ is PR, NR or TR

Facts

The quotient set form a Partition

Link to original

Therefore the set of communication classes^[Quotient Set] form a Partition.

Link to original

Irreducible Markov Chain

Definition

State space $E$ which has only one Communication Class. where $\{X_t\}$ is a HMC defined on the state space $E$ and the $\mathbf{P}$ is a Transition Matrix of $\{X_t\}$

$\forall x,y,\in E:\exists \text{ path }x\to \cdots \to y\text{ or }y\to \cdots \to x$ where $x\to y\iff \exists T_0\in {\mathbb{N}}_0:p_{ij}^{(T_0)}>0$ and $p_{ij}^{(T_0)}$ is the probability of departing from $x$ and reaching $y$ after $T_0$

Facts

If HMC $\{X_t\}$ has finite state space and is irreducible, then the unique Stationary Distribution $\mathbf{\pi }$ of $\{X_t\}$ exists, and the probability of every state is positive.

Since Communication is a Equivalence Class, the reducible Markov chain can be partitioned into the irreducible Markov chains.

Link to original

Recurrence

Definition

Continuous Version

Let $\{X_t\}$ be a HMC defined on the state space $E$, and $T_i$ be the return time for the state $i\in E$

Recurrent

$P_i(T_i<\infty )=1$

Positive recurrent

$P_i(T_i<\infty )=1\wedge E_i[T_i]<\infty$

Null recurrent

$P_i(T_i<\infty )=1\wedge E_i[T_i]=\infty$

Transient

$P_i(T_i<\infty )<1$

Incomplete Discrete Version

Let $\{X_t\}$ be a HMC defined on the state space $E$, $i\in E$, and $p$ be the element of the transition matrix of $\{X_t\}$

Recurrent

${\sum }_{t=0}^{\infty }{p}_{ii}^{(t)}=\infty$

Transient

${\sum }_{t=0}^{\infty }{p}_{ii}^{(t)}<\infty$

Notation

$T_y:=\min \{t|X_t=y,t\ge 1\}=\min \{t\ge 1|X_t=y\}$

The first time to return to state $y$

$P_y(T_y<\infty )$

The probability of returning to $y$ from $y$ within a finite time.

Example

Let the $\{X_t\}$ be a HMC and $\mathbf{P}$ be a transition matrix.

$\mathbf{P}=\left[\begin{array}{cccccc}1-p& p& 0& 0& 0& \dots \\ 1-p& 0& p& 0& 0& \dots \\ 0& 1-p& 0& p& 0& \dots \\ 0& 0& 1-p& 0& p& \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \end{array}\right]$

$\mathbf{P}$ is an Irreducible Markov Chain. Whether recurrent or transient is determined by $p$

• $p>1/2\Rightarrow {\sum }_{t=0}^{\infty }{p}_{00}^{(t)}<\infty$: transient
• $p<1/2\Rightarrow {\sum }_{t=0}^{\infty }{p}_{00}^{(t)}=\infty$ with $p_{00}^{(t)}\to c>0$: positive recurrent
• $p=1/2\Rightarrow {\sum }_{t=0}^{\infty }{p}_{00}^{(t)}<\infty$ with $p_{00}^{(t)}\to 0$: null recurrent

Facts

If a HMC $\{X_t\}$ is Irreducible Markov Chain, then every state $i$ has the same nature. In other words, it has one among the following

• every state is transient
• every state is null recurrent
• every state is positive recurrent

$\frac{1}{E(T_i)}\approx \frac{1}{T}{\sum }_{t=1}^T\#1(X_t=i)$ The number of times that returning to oneself for a time $T$ approximates the inverse of $E(T_i)$.

Link to original

Period of Markov Chain

Definition

Let $\{X_t\}$ be a HMC defined on the state space $E$, and the set $I_i$ be the set of the time steps returning from the $i\in E$ to oneself $I_i=\{t:p_{ii}^{(t)}>0,t\ge 1\}$.

The period of $i$ is the G.C.D of every element of $I$

Link to original

Aperiodic Markov Chain

Definition

Markov Chain whose period is one.

Facts

If there is a probability of returning to oneself after 1 period or there exist non-zero diagonal elements of the Transition Matrix, then the Markov always aperiodic

Every state $x\in E$ of finite IRR HMC has the same period.

If HMC is IRR and recurrent, then every state $x\in E$ has the same period.

Examples

Periodic Markov Chain with 3-period

flowchart LR  
  0 -->|1| 1  
  1 -->|1| 3  
  2 -->|1| 1  
  3 -->|1/3| 0   
  3 -->|2/3| 2  

Aperiodic Markov Chain with 1-period

flowchart LR
  0 -->|1| 1
  1 -->|1/2| 0
  1 -->|1/2| 2
  2 -->|1| 3
  3 -->|1| 1

Link to original

Ergodic Theorem

Definition

A finite IRR HMC $\{X_t{\}}_{t\in {\mathbb{N}}_0}$ holds the following for an arbitrary function $f:E\to \mathbb{R}$ ${\lim }_{T\to \infty }\frac{1}{T}{\sum }_{t=0}^{T-1}f(X_t)=E_{\mathbf{\pi }}[f(X_0)]$ where $\mathbf{\pi }$ is the unique Stationary Distribution, and $\mathbf{P}$ is a Transition Matrix of $\{X_t\}$

IRR PR HMC $\{X_t\}$ holds the following for a function $f:E\to \mathbb{R}$ that satisfies ${\sum }_{i\in E}|f(i)|{\pi }_i<\infty$ ${\lim }_{T\to \infty }\frac{1}{T}{\sum }_{t=0}^{T-1}f(X_t)=E_{\mathbf{\pi }}[f(X_0)]$ where $\mathbf{\pi }$ is the unique Stationary Distribution, and $\mathbf{P}$ is a Transition Matrix of $\{X_t\}$

Facts

Approximate Stationary Distribution Using Ergodic Theorem (Finite)

If the Markov Chain has a unique Stationary Distribution, it can be approximated using the time average by the ergodic theorem.

Let function $f$ be $f(i)=I(i=0)=\{\begin{array}{ll}1& i=0\\ 0& o.w\end{array}$, The stationary distribution can be approximated by using the ergodic theorem ${\lim }_{T\to \infty }\frac{1}{T}{\sum }_{t=0}^{T-1}I(X_t=0)=E_{\pi }[I(X_0=0)]=P_{\pi }[X_0=0]={\pi }_0$

Approximate Stationary Distribution Using Ergodic Theorem (Infinite)

IRR PR HMC $\{X_t\}$ holds $\bar{\mathbf{\pi }}\to \mathbf{\pi }$

where $\bar{\mathbf{\pi }}$ is the time average, and $\mathbf{\pi }$ is the Stationary Distribution, of $\{X_t\}$

Examples

Identity Matrix

$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$

Since the IRR condition is not satisfied, there is no unique Stationary Distribution. So the Ergodic theorem cannot be used.

Exchange Matrix

$\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$

$(\frac{1}{T}{\sum }_{t=0}^{T-1}I(X_t=0),\frac{1}{T}{\sum }_{t=0}^{T-1}I(X_t=1))=({\hat{\pi }}_0,{\hat{\pi }}_1)\approx (1/2,1/2)$

Link to original

Ergodic Markov Chain

Definition

The HMC $\{X_t\}$ that satisfies the following conditions is an ergodic Markov chain

• has finite states
• irreducible
• aperiodic

The HMC $\{X_t\}$ that satisfies the following conditions is an ergodic Markov chain

• irreducible
• Positive recurrent
• aperiodic

Link to original

Limiting Distribution

Definition

If $\underset{t\to \infty }{\lim }{\mathbf{P}}^t={\mathbf{P}}^{\star }$ exists and the every row of ${\mathbf{P}}^{\star }$ are the same, an arbitrary row vector ${\mathbf{p}}_{\star }^{⊺}$ of the ${\mathbf{P}}^{\star }$ is called the limiting distribution of the stochastic process $\{X_t\}$.

where the $\mathbf{P}$ is the transition matrix of the finite HMC $\{X_t\}$

Facts

$\exists {\mathbf{p}}_{\star }^{⊺}\to \exists !{\mathbf{p}}_{\star }^{⊺}$

If a limiting distribution exists, it is unique.

$\exists {\mathbf{p}}_{\star }^{⊺}\to {\mathbf{p}}_{\star }^{⊺}\mathbf{P}={\mathbf{p}}_{\star }^{⊺}$

If a finite HMC $\{X_t\}$ has a limiting distribution ${\mathbf{p}}_{\star }^{⊺}$, then the limiting distribution ${\mathbf{p}}_{\star }^{⊺}$ satisfies the definition of Stationary Distribution

Ergodic Markov Chain $\to \exists !{\mathbf{p}}_{\star }^{⊺}$

Ergodic Markov Chain $\{X_t\}$ has a unique limiting distribution ${\mathbf{p}}_{\star }^{⊺}$

IRR TR HMC $\{X_t\}$ doesn’t have a limiting distribution because the converged Transition Matrix ${\mathbf{P}}^{\star }=0$

IRR NR HMC $\{X_t\}$ doesn’t have a limiting distribution because the converged Transition Matrix ${\mathbf{P}}^{\star }=0$

Link to original

Detailed Balance Condition

Definition

$\forall i,j\in E:{\mu }_i{p}_{ij}={\mu }_j{p}_{ji}$ where $\{X_t\}$ is IRR HMC, $\mathbf{P}$ is the Transition Matrix of the $\{X_t\}$, and $\mathbf{\mu }$ is a Distribution

The probability of the transition from the state $i$ to $j$ is equal to the probability from the $j$ to $i$

Facts

$\forall i,j\in E:{\mu }_i{p}_{ij}={\mu }_j{p}_{ji}\Rightarrow {\mathbf{\mu }}^{⊺}\mathbf{P}={\mathbf{\mu }}^{⊺}$ The detailed balanced condition implies the stationarity of the distribution $\mathbf{\mu }$ In other words, the distribution $\mathbf{\mu }$ satisfying the detailed balanced condition is a Stationary Distribution.

Link to original

Reversible Markov Chain

Definition

The Markov Chain satisfying Detailed Balance Condition

Link to original