State Space, Initial Distribution and Transition Probabilities

• The stochastic model of a discrete-time Markov chain with finitely many states consists of three components: state space, initial distribution and transition matrix.
  • The model is based on the (finite) set of all possible states called the state space of the Markov chain. W.l.o.g. the state space can be identified with the set $E=\{1,2,\ldots,\ell\}$ where $\ell\in\mathbb{N}=\{1,2,\ldots\}$ is an arbitrary but fixed natural number.
  • For each $i\in E$, let $\alpha_i$ be the probability of the system or object to be in state $i$ at time $n=0$, where it is assumed that

    $$\alpha_i\in[0,1]\,,\qquad\sum\limits_{i=1}^\ell \alpha_i=1\,.$$ (1)

    
    
    The vector ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ of the probabilities $\alpha_1,\ldots,\alpha_\ell$ defines the initial distribution of the Markov chain.

  • Furthermore, for each pair $i,j\in E$ we consider the (conditional) probability $p_{ij}\in[0,1]$ for the transition of the object or system from state $i$ to $j$ within one time step.

  • The $\ell\times\ell$ matrix ${\mathbf{P}}=(p_{ij})_{i,j=1,\ldots,\ell}$ of the transition probabilities $p_{ij}$ where

    $$p_{ij}\ge0\,,\qquad \sum_{j=1}^\ell p_{ij}=1\,,$$ (2)

    
    
    is called one-step transition matrix of the Markov chain.
• For each set $E=\{1,2,\ldots,\ell\}$, for any vector ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ and matrix ${\mathbf{P}}=(p_{ij})$ satisfying the conditions (1) and (2) the notion of the corresponding Markov chain can now be introduced.

Definition

 

• Let $X_0,X_1,\ldots:\Omega\to E$ be a sequence of random variables defined on the probability space $(\Omega,\mathcal{F},P)$ and mapping into the set $E=\{1,2,\ldots,\ell\}$.
• Then $X_0,X_1,\ldots$ is called a (homogeneous) Markov chain with initial distribution ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ and transition matrix ${\mathbf{P}}=(p_{ij})$, if

  $$P(X_0=i_0,X_1=i_1,\ldots, X_n=i_n) =\alpha_{i_0}p_{i_0i_1}\ldots p_{i_{n-1}i_n}$$ (3)

  
  
  for arbitrary $n=0,1,\ldots$ and $i_0,i_1,\ldots,i_n\in E$.

Remarks

 

• A quadratic matrix ${\mathbf{P}}=(p_{ij})$ satisfying (2) is called a stochastic matrix.
• The following Theorem 2.1 reveals the intuitive meaning of condition (3). In particular the motivation for the choice of the words ``initial distribution'' and ``transition matrix'' will become evident.
• Furthermore, Theorem 2.1 states another (equivalent) definition of a Markov chain that is frequently found in literature.

Theorem 2.1   The sequence $\{X_n\}$ of $E$-valued random variables is a Markov chain if and only if there is a stochastic matrix ${\mathbf{P}}=(p_{ij})$ such that

$$P(X_{n}=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0=i_{0}) =p_{i_{n-1}i_n}$$ (4)

for any $n=1,2,\ldots$ and $i_0,i_1,\ldots,i_n\in E$ such that $P( X_{n-1}=i_{n-1},\ldots,X_0=i_{0})>0$.

Proof

 

• Clearly condition (4) is necessary for $\{X_n\}$ to be a Markov chain as (4) follows immediately from (3) and the definition of the conditional probability; see section WR-2.6.1.
• Let us now assume $\{X_n\}$ to be a sequence of $E$-valued random variables such that a stochastic matrix ${\mathbf{P}}=(p_{ij})$ exists that satisfies condition (4).
• For all $i\in E$ we define $\alpha_i=P(X_0=i)$ and realize that condition (3) obviously holds for $n=0$.
• Furthermore,
  • $P(X_0=i_0)=0$ implies $P(X_0=i_0,X_1=i_1)=0$,
  • and in case $P(X_0=i_0)>0$ from (4) we can conclude that
    $$P(X_0=i_0,X_1=i_1)=P(X_0=i_0)P(X_1=i_1\mid X_0=i_0)\stackrel{(\ref{mar.pro.for})}{=}\alpha_{i_0}p_{i_0i_1}\,.$$

• Therefore
  $$P(X_0=i_0,X_1=i_1)=\left\{ \begin{array}{ll} 0\,, & \mbox{if ... ...p_{i_0i_1}\,, & \mbox{if $\alpha_{i_0}>0$}, \end{array}\right.$$
  i.e., we showed that (3) also holds for the case $n=1$.
• Now assume that (3) holds for some $n=k-1\ge 1$.
  • By the monotonicity of probability measures (see statement 2 in Theorem WR-2.1)
    $P(X_0=i_0,X_1=i_1,\ldots,X_{k-1}=i_{k-1})=0$ immediately implies
    $P(X_0=i_0,X_1=i_1,\ldots,X_k=i_k)=0$.
  • On the other hand if $P(X_0=i_0,X_1=i_1,\ldots,X_{k-1}=i_{k-1})>0$, then
    

    $${P(X_0=i_0,X_1=i_1,\ldots,X_k=i_k)}$$

    $$= P(X_0=i_0,X_1=i_1,\ldots,X_{k-1}=i_{k-1}) P(X_k=i_k\mid X_{k-1}=i_{k-1},\ldots,X_0=i_0)$$

    $$= \alpha_{i_0}p_{i_0i_1}\ldots p_{i_{k-2}i_{i-1}}p_{i_{k-1}i_k}\,.$$

    
    

• Thus, (3) also holds for $n=k$ and hence for all $n\in\mathbb{N}$.
  
  $\Box$

Corollary 2.1   Let $\{X_n\}$ be a Markov chain. Then,

$$P(X_{n}=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0=i_{0})= P(X_{n}=i_n\mid X_{n-1}=i_{n-1})$$ (5)

holds whenever $P( X_{n-1}=i_{n-1},\ldots,X_0=i_{0})>0$.

Proof

 

• Let $P(X_{n-1}=i_{n-1},\ldots,X_0=i_{0})$ and hence also $P(X_{n-1}=i_{n-1})$ be strictly positive.
• In this case (3) yields
  

  $$P(X_{n}=i_n\mid X_{n-1}=i_{n-1}) = \frac{P(X_n=i_n,X_{n-1}=i_{n-1})}{P(X_{n-1}=i_{n-1})}$$

  $$= \frac{\sum\limits_{i_0,\ldots,i_{n-2}\in E}P(X_{n}=i_n,\ldots, X_0=i_0)}{\sum\limits_{i_0,\ldots,i_{n-2}\in E}P(X_{n-1}=i_{n-1},\ldots, X_0=i_0)}$$

  $$\stackrel{(\ref{def.mar.for})}{=} \frac{\sum\limits_{i_0,\ldots,i_{n-2}\in E}\alpha_{i_0} p_{i_0i_1... ...n-2}\in E}\alpha_{i_0} p_{i_0i_1}\ldots p_{i_{n-2}i_{n-1}}} = p_{i_{n-1}i_n}\,.$$

  
  

• This result and (4) imply (5).
  
  $\Box$

Remarks

 

• Corollary  2.1 can be interpreted as follows:
  • The conditional distribution of the (random) state $X_n$ of the Markov chain $\{X_n\}$ at ``time'' $n$ is completely determined by the state $X_{n-1}=i_{n-1}$ at the preceding time $n-1$.
  • It is independent from the states $X_{n-2}=i_{n-2},\ldots,X_1=i_1,X_0=i_0$ observed in the earlier history of the Markov chain.
• The definition of the conditional probability immediately implies
  • the equivalence of (5) and
    

    $${ P(X_{n}=i_n,X_{n-2}=i_{n-2}\ldots,X_0=i_{0}\mid X_{n-1}=i_{n-1})}$$

    $$= P(X_{n}=i_n\mid X_{n-1}=i_{n-1})\;P(X_{n-2}=i_{n-2}\ldots,X_0=i_{0}\mid X_{n-1}=i_{n-1})\,.$$ (6)

    
    

  • The conditional independence (6) is called the Markov property of $\{X_n\}$.
• The definitions and results of Section 2.1.1 are still valid,
  • if instead of a finite state space $E=\{1,2,\ldots,\ell\}$ a countably infinite state space such as the set of all integers or all natural numbers is considered.
  • It merely has to be taken into account that in this case ${\boldsymbol{\alpha}}$ and ${\mathbf{P}}$ possess an infinite number of components and entries, respectively.