\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amssymb,amsfonts}

\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows}

\tikzset{->, % makes the edges directed
         >=stealth', % makes the arrow heads bold
         node distance=3cm, % specifies the minimum distance between
                            % two nodes. Change if necessary.
         every state/.style={thick, fill=gray!10}, % sets the
                            % properties for each `state` node
         initial text=$ $,  % sets the text that appears on the start arrow
}

\begin{document}

\title{Stochastic Processes}
\author{Summer Semester 2026, Exercise 6}
\date{Due Thursday, July 2, 2026}
\maketitle


\begin{enumerate}

\item Let $\xi_n$, $n \in \mathbb N$, be a Markov chain with state
space $S$.  Recall that $p_n(j|i)$ is the probability that state $i$
transitions to state $j$ in $n$ steps; $f_n(j|i)$ denotes the
probability that state $i$ transitions for the first time to state $j$
in $n$ steps.

Determine if the following statements are true or false.  If true,
provide a short argument, if false, provide a counterexample.

\begin{enumerate}
\item $p_n(j|i) \geq f_n(j|i)$ for all $n \in \mathbb N$ and $i,j \in
S$.

\item $\displaystyle p_n(j|i) = \sum_{k = 1}^n f_k(j | i) \,
p_{n-k}(j|j)$ for $n \geq 1$.

\item If $i \leftrightarrow j$, there exists $n \in \mathbb N$ such
that $p_n(i|j)>0$ and $p_n(j|i)>0$.

\item If all columns of the transition matrix are equal, then all
states belong to the same class.  (We take the convention that the
transition matrix acts on a distribution by multiplication from the
left, where the distribution is represented by a column vector.)

\item If $\displaystyle \sum_{n=1}^\infty f_n(j|i) < 1$ and
$\displaystyle \sum_{n=1}^\infty f_n(i|j) < 1$, then $i$ and $j$ do
not intercommunicate.

\item If $p_n(i|j) \to \delta_{ij}$ (the Kronecker delta) as $n \to
\infty$ for all $i,j \in S$, then all states are recurrent.

  
\end{enumerate}


\item Two urns are filled with balls.  The red urn has initially $10$
red balls, the blue urn has initially $10$ blue balls.  Each round,
one urn is selected, each with probability $\tfrac12$.  Then, a ball
from that container is selected uniformly at random and moved to the
other urn.  If the selected urn is empty, no ball is moved.

The game is stopped when all red balls are in the blue urn and all
blue balls are in the red urn.

\begin{enumerate}
\item Argue that this problem can be modeled as a Markov chain.  What
is the state space $S$?

\item What is the initial distribution?

\item Write out a general expression for the elements of the
transition matrix, $p_{ij}$ for $i,j \in S$.

\item Which states are transient?  Explain!
\end{enumerate}

\item Consider the following Markov chain.

\begin{tikzpicture}[baseline=(q1.base)]
  \node[state] (q1) {$1$};
  \node[state, above right of=q1] (q2) {$2$};
  \node[state, right of=q2] (q3) {$3$};
  \node[state, below right of=q1] (q4) {$4$};
  \node[state, right of=q4] (q5) {$5$};
  \node[state, right of=q5] (q6) {$6$};
  \draw (q1) edge[loop left] node{$\tfrac12$} (q1)
        (q1) edge[above] node{$\tfrac13$} (q2)
        (q1) edge[below] node{$\tfrac16$} (q4)
        (q2) edge[bend right, below] node{$1$} (q3)
        (q3) edge[bend right, above] node{$1$} (q2)
        (q4) edge[above] node{$1$} (q5)
        (q5) edge[bend left, above] node{$1$} (q6)
        (q6) edge[bend left, below] node{$\tfrac12$} (q5)
        (q6) edge[bend right=60, above] node{$\tfrac12$} (q4);  
\end{tikzpicture}
\begin{enumerate}
\item Write out the transition matrix.
\item Identify the classes.
\item Find the periods of all states.
\item Compute $f_n(3|1)$ for all $n \in \mathbb N$.
\item Find the stationary distributions of the recurrent classes.
\end{enumerate}

\end{enumerate}
\end{document}