Examples

1. Weather Forecast
   (see. O. Häggström (2002) Finite Markov Chains and Algorithmic Applications. CU Press, Cambridge)
   • We assume to observe the weather in an area whose typical weather is characterized by longer periods of rainy or dry days (denoted by rain and sunshine), where rain and sunshine exhibit approximately the same relative frequency over the entire year.
     • It is sometimes claimed that the best way to predict tomorrow's weather is simply to guess that it will be the same tomorrow as it is today.
     • If we assume that this way of predicting the weather will be correct in 75% of the cases (regardless whether today's weather is rain or sunshine), then the weather can be easily modelled by a Markov chain.
     • The state space consists of the two states $1=$rain and $2=$ sunshine.
     • The transition matrix is given as follows:

       $${\mathbf{P}}=\left(\begin{array}{ll} 0.75 & 0.25\\ 0.25 & 0.75\end{array}\right)\,.$$ (7)

       
       

   • Note that a crucial assumption for this model is the perfect symmetry between rain and sunshine in the sense that the probability that today's weather will persist tomorrow is the same regardless of today's weather.

   • In areas where sunshine is much more common than rain a more realistic transition matrix would be the following:

     $${\mathbf{P}}=\left(\begin{array}{ll} 0.5 & 0.5\\ 0.1 & 0.9\end{array}\right)$$ (8)

     
     

   
   

2. Random Walks; Risk Processes 
   • Classic examples for Markov chains are so-called random walks. The (unbounded) basic model is defined in the following way:
     • Let $Z,Z_1,Z_2,\ldots:\Omega\to\mathbb{Z}$ be a sequence of independent and identically distributed random variables mapping to $\mathbb{Z}=\{\ldots,-1, 0,1,\ldots\}$.
     • Let $X_0:\Omega\to\mathbb{Z}$ be an arbitrary random variable, which is independent from the increments $Z_1,Z_2,\ldots$, and define

       $$X_n=X_{n-1}+Z_n\,,\qquad\forall\,n\ge 1\,.$$ (9)

       
       

     • Then the random variables $X_0,X_1,\ldots$ form a Markov chain on the countably infinite state space $E=\mathbb{Z}$ with initial distribution ${\boldsymbol{\alpha}}=(\alpha_1,\alpha_2,\ldots)^\top$, where $\alpha_i=P(X_0=i)$. The transition probabilities are given by $p_{ij}=P(Z=j-i)$.

     
     

   • Remarks
     • The Markov chain given in (9) can be used as a model for the temporal dynamics of the solvability reserve of insurance companies. $X_0$ will then be interpreted as the (random) initial reserve and the increments $Z_n$ as the difference $Z_n=a-Z_n^\prime$ between the risk-free premium income $a>0$ and random expenses for the liabilities $Z_n^\prime$ in time period $n-1$.
     • Another example for a random walk are the total winnings in $n$ roulette games already discussed in Section WR-1.3. In this case we have $X_0=0$. The distribution of the random increment $Z$ is given by $P(Z=i)=1/2$ for $i=-1,1$ and $P(Z=i)=0$ for $i\in\mathbb{Z}\setminus\{-1,1\}$.

   
   

3. Queues
   • The number of customers waiting in front of an arbitrary but fixed checkout desk in a grocery store can be modelled by a Markov chain in the following way:
     • Let $X_0=0$ be the number of customers waiting in the line, when the store opens.
     • By $Z_n$ we denote the random number of new customers arriving while the cashier is serving the $n$th customer ( $n=1,2,\ldots$).
     • We assume the random variables $Z,Z_1,Z_2,\ldots:\Omega\to\{0,1,\ldots\}$ to be independent and identically distributed.
   • The recursive definition

     $$X_n= \max\{0,X_{n-1}+Z_n-1\}\,,\qquad\forall\,n\ge 1\,,$$ (10)

     
     
     yields a sequence of random variables $X_0,X_1,\ldots\Omega\to\{0,1,\ldots\}$ that is a Markov chain whose transition matrix ${\mathbf{P}}=(p_{ij})$ has the entries
     $$p_{ij}=\left\{\begin{array}{ll} P(Z=j+1-i)\,, &\mbox{if $j+1\ge i... ... P(Z=0)+P(Z=1)\,, &\mbox{if $j=i=0$,}\\ 0\,, &\mbox{else} \end{array}\right.$$

   • $X_n$ denotes the random number of customers waiting in the line right after the cashier has finished serving the $n$th customer, i.e., the customer who has just started checking out and hence already left the line is not counted any more.

4. Branching Processes
   • We consider the reproduction process of a certain population, where $X_n$ denotes the total number of descendants in the $n$th generation; $X_0=1$.
   • We assume that

     $$X_n= \sum\limits_{i=1}^{X_{n-1}} Z_{n,i}\,,$$ (11)

     
     
     where $\{Z_{n,i},\, n,i\in\mathbb{N}\}$ is a set of independent and identically distributed random variables mapping into the set $E=\{0,1,\ldots\}$.
   • The random variable $Z_{n,i}$ is the random number of descendants of individual $i$ in generation $(n-1)$.
   • The sequence $X_0,X_1,\ldots:\Omega\to\{0,1,\ldots\}$ of random variables given by $X_0=1$ and the recursion (11) is called a branching process.
   • One can show (see Section 2.1.3) that $X_0,X_1,\ldots$ is a Markov chain with transition probabilities
     $$p_{ij}=\left\{\begin{array}{ll} P\Bigl(\sum\limits_{k=1}^i Z_{1,k... ...$i>0$,}\\ 1\,, &\mbox{if $i=j=0$,}\\ 0\,, &\mbox{else.} \end{array}\right.$$

5. Cyclic random walks 
   • Further examples of Markov chains can be constructed as follows (see E. Behrends (2000) Introduction to Markov Chains. Vieweg, Braunschweig, p.4).
     • We consider the finite state space $E=\{0,1,\ldots,999\}$, the initial distribution

       $${\boldsymbol{\alpha}}=(1/16,4/16,6/16,4/16,1/16,0,\ldots,0)^\top$$ (12)

       
       
       and the transition probabilities
       $$p_{ij}=\left\{\begin{array}{ll} \displaystyle\frac{1}{6}\;, & \mb... ...mod(1000)\in\{1,\ldots,6\}$,}\\ [3\jot] 0\,, &\mbox{else.} \end{array}\right.$$

     • Let $X_0,Z_1,Z_2,\ldots:\Omega\to\{0,1,\ldots,999\}$ be independent random variables, where the distribution of $X_0$ is given by (12) and
       $$P(Z_1=i)=P(Z_2=i)=\ldots=1/6\,,\qquad\forall\,i=1,\ldots,6\,.$$

     • The sequence $X_0,X_1,\ldots\Omega\to\{0,1,\ldots,999\}$ of random variables defined by the recursion formula

       $$X_n= (X_{n-1}+Z_n)\mod(1000)$$ (13)

       
       
       for $n\ge 1$ is a Markov chain called cyclic random walk.

     
     

   • Remarks 
     • An experiment corresponding to the Markov chain defined above can be designed in the following way. First of all we toss a coin four times and record the frequency of the event ``versus''. The number $x_0$ of these events is regarded as realization of the random initial state $X_0$; see the Bernoulli scheme in Section WR-3.2.1.
     • Afterwards a dice is tossed $n$ times. Die outcome $z_i$ of the $i$th experiment, is interpreted as a realization of the random ``increment'' $Z_i$; $i=1,\ldots,n$.
     • The new state $x_n$ of the system results from the update of the old state $x_{n-1}$ according to (13) taking $z_{n-1}$ as increment.
     • If the experiment is not realized by tossing a coin and a dice, respectively, but by a computer-based generation of pseudo-random numbers $x_0,z_1,z_2,\ldots$ the procedure is referred to as Monte-Carlo simulation.
     • Methods allowing the construction of dynamic simulation algorithms based on Markov chains will be discussed in the second part of this course in detail; see Chapter 3 below.