Ran_6.tex

\documentclass[11pt,a4paper]{report}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,suetterl}
\usepackage{lmodern}
\usepackage[T1]{fontenc}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage[utf8]{inputenc}

\usepackage{fontawesome}
\DeclareUnicodeCharacter{2212}{-}
\usepackage{mathrsfs}

\usepackage[nodisplayskipstretch]{setspace}

\setstretch{1.5}

\fancyfoot[C]{\thepage}

\renewcommand{\footrulewidth}{0pt}
\parindent 0ex
\setlength{\parskip}{1em}

\newenvironment{psmallmatrix}
  {\left(\begin{smallmatrix}}
  {\end{smallmatrix}\right)}

\begin{document}
    \textbf{MTH6141 Random Processes, 2018, Exercise Sheet 5}\par
    Please drop your answer in the Random Processes coursework box by Thursday 15th February. You are encouraged to attempt all questions, and a minimum of Q1, Q3 and Q4.
    \begin{enumerate}
        \item Look back to your answer to Question 1 on Sheet 4. For which of the five parts (a)-(e) is it the case that for each $i \in S$, as $T \to \infty$, the expected proportion of time spent in state $i$ up to time $T$ tends to a limit which is independent of the starting distribution? In each of the parts (a)-(e), determine the expected proportion of time spent in state $2$ in the long run, whenever this quantity is well defined.
        \item Let $(X_0, X_1, X_2, \ldots)$ be a Markov chain with state space $S$. Show that $\leftrightarrow$ (the “intercommunicates” relation) is an equivalence relation on $S$. Recall that if $S$ is a set, and $R$ is a binary relation on the set $S$, then $R$ is said to be an equivalence relation if it is reflexive $(xRx for all x \in S)$, symmetric (if $xRy$ then $yRx$, for any $x, y \in S$), and transitive (if $xRy$ and $yRz$, then $xRz$, for any $x, y, z \in S$).
        \item  Consider the Markov chain with state space $\{1, 2, 3, 4, 5, 6, 7\}$ and transition matrix
        $$
        P
        =
        \begin{pmatrix}
            \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{6} & 0 & 0 & 0\\
            \frac{4}{5} & 0 & 0 & 0 & \frac{1}{5} & 0 & 0\\
            0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\
            0 & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4}\\
            0 & 0 & 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0\\
            0 & 0 & 0 & 0 & 0 & 0 & 1\\
            0 & 0 & 0 & 0 & 0 & \frac{1}{4} & \frac{3}{4}
        \end{pmatrix}
        $$
        \begin{enumerate}
            \item Determine the communicating classes of states of the chain.
            \item Calculate the first return probabilities $f^{(t)}_{1,1}$ and the return probability $f_{1,1}$. Is the state $1$ recurrent or transient?
            \item  Calculate the first return probabilities $f^{(t)}_{6,6}$ and the return probability $f_{6,6}$. Is the state $6$ recurrent or transient?
            \item Without computing $f_{3,3}$ exactly, provide a simple argument that it is strictly less than $1$, and hence that the state $3$ is transient.\\
            (We will see later that recurrence and transience are class properties, i.e., states in the same communicating class are either all recurrent or all transient Given this additional fact, you have in fact determined recurrence/transience of all seven states.)
        \end{enumerate}
        \item Consider the Markov chain on state space $\{0, 1, 2, \ldots \} = \mathbb{N} \cup \{0\}$, with transition probabilities as follows.
        $$
        p_{i,j}
        =
        \begin{cases}
            1, & \text{if}\ i = 0\ \text{and}\ j =1;\\
            \frac{1}{3}, & \text{if}\ i \geq 1\ \text{and}\ j = i+1;\\
            \frac{2}{3}, & \text{if}\ i \leq 1\ \text{and}\ j = i-1;\\
            0, & \text{otherwise.}
        \end{cases}
        $$
        Does this Markov chain have an equilbrium distribution? If so, what is it?
        \item {[}This is a harder question. Actually, I don’t know the exact answer!{]} Consider a regular Markov chain with a finite state space $S$. Let
        $$m = min \{ t : p^{(t)}_{ij} > 0\ \text{for all}\ i, j \in S \}.$$
        (We know from the definition of ‘regular’ that $m$ exists.) How large can $m$ be as a function of $n = |S|$? (In other words, for each value of $n = |S|$, try to find an example where $m$ is as large as you can make it.)
    \end{enumerate}
\end{document}