Discrete time Markov chains §

Definition and basic properties §

Let $I$ be a countable set. Each $i\in I$ is called a state and $I$ is called the state-space.

We say that $\lambda =\{{\lambda }_i:i\in I\}$ is a measure on $I$ if $0\le {\lambda }_i<\infty$ for all $i\in I$. If the total mass ${\sum }_{i\in I}{\lambda }_i$ equals $1$, then we call $\lambda$ a distribution.

We will work with a probability space $(\Omega ,\mathcal{F},\mathbb{P})$. A random variable taking values in $I$ is a measurable function $X:\Omega \to I$.

Suppose we set

$${\lambda }_i=\mathbb{P}(X=i)=\mathbb{P}(\{\omega \in \Omega :X(\omega )=i\})$$

this defines the distribution of $X$. We think of $X$ as modelling a random state which takes value $i$ with probability ${\lambda }_i$.

It’s natural to define a matrix $P=(p_{ij}:i,j\in I)$ which entries correspont to the probability to get from state $i$ to state $j$. It follows that each row shoud be a distribution, i.e. ${\sum }_J{p}_{ij}=0$. Such matrices are called stochastic.

Def A stochastic process $(X_n{)}_{n\ge 0}$ is a Markov Chain with initial distribution $\lambda$ and a transition matrix $P$ if

1. $X_0$ has a distribution $\lambda$;
2. for $n\ge 0$, conditional $X_n=i$, $X_{n+1}$ has distribution $(p_{ij}:j\in I)$ and is independent of $X_0,\dots ,X_{n-1}$.

Written explicitly, these condition are

1. $\mathbb{P}(X_0=i)={\lambda }_i$;
2. $\mathbb{P}(X_{n+1}=i|X_0=i_0,\dots ,X_{n-1}=i_{n-1},X_n=j)=p_{ji}$

We say that $(X_n{)}_{n\ge 0}$ is $Markov(\lambda ,P)$ for short.

DUBBIO ??? §

Il professore aggiunge che gli stati $i_0,\dots ,i_n$ devono avere probabilità positiva???

$$\mathbb{P}(X_0=i_0,X_1=i_i,\dots )>0$$

My answer: non vuole condizionare su eventi di probabilità nulla!

Meaning: Markov chains are discrete time stochastic processes with “no memory”. The r.v. $X_n$ is the state at time $n$.

We can give a more comprehensive description of Markov Chains, i.e. an equivalent characterization.

Theorem 1.1.1 A Discrete time random process $(X_n{)}_{0\le n\le N}$ is $Markov(\lambda ,P)$ is and only if for all $i_0,\dots ,i_N\in I$

$$\mathbb{P}(X_0=i_0,X_1=i_1,\dots X_N=i_N)={\lambda }_{i_0}{p}_{i_0{i}_1}{p}_{i_1{i}_2}\dots p_{i_{N-1}{i}_N}$$

Proof $(⟹)$ Suppose $X$ is $Markov(\lambda ,P)$, then

$$\mathbb{P}(X_0=i_0,\dots X_N=i_N)$$ $$=\mathbb{P}(X_N=i_N|X_0=i_0,\dots X_{N-1}=i_{N-1})\mathbb{P}(X_0=i_0,\dots X_{N-1}=i_{N-1})$$

which follows from the definition of conditional probability. The first term is, by property $2$ equal to $p_{i_{N-1}{i}_N}$. By iterating $N$ times we get our thesis.

$(⟸)$ It’s clear by induction that for each $0\le n\le N$

$$\mathbb{P}(X_0=i_0,\dots ,X_n=i_n)=\sum _{i_{n+1},\dots ,i_N\in I}\mathbb{P}(X_0=i_0,X_1=i_1,\dots X_N=i_N)={\lambda }_0{p}_{i_1}\dots p_{i_n}$$

in particular this implies

$$\mathbb{P}(X_0=i_0)={\lambda }_0$$

By computing the conditional probability

$$\mathbb{P}(X_{n+1}=i_{n+1}|X_0=i_0,X_1=i_1,\dots )=\frac{\mathbb{P}(X_0=i_0,\dots ,X_{n+1}=i_{n+1})}{\mathbb{P}(X_0=i_0,\dots ,X_n=i_n)}=p_{i_n{i}_{n+1}}$$

this is Markov property $2$. $\square$