\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx}
\def\e{\mathrm{e}}
\def\d{\mathrm{d}}
\def\Var{\operatorname{Var}}

\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows.meta}
\tikzset{->, % makes the edges directed
         >={Stealth[scale=1.4]}, % makes the arrow heads bold and slightly larger
         shorten >=1pt, % small gap before the arrowhead touches the target node
         shorten <=1pt, % small gap after the arrow leaves the source node
         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{Final Exam}
\date{July 20, 2026}
\maketitle
% \vfill
% {\baselineskip=40pt
% \begin{tabbing}\
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}
% \vfill\vfill\mbox{}


% \newpage
\begin{enumerate}

\item Let $\xi_n$ denote the \emph{asymmetric} random walk
\[
  \xi_n = \eta_1 + \dots + \eta_n \,,
\]
where the $\eta_i$ are independent random variables with
$P(\eta_i=2) = P(\eta_i=-1)=\tfrac12$.

Compute the following.
\begin{enumerate}
\item $P(\xi_4=3|\xi_0=1)$
\item $P(\xi_4=3|\xi_0=2)$
\end{enumerate}
\hfill (5+5)
%\newpage

\item Let $\xi_i$, $i=1,2, \dots$ be independent Bernoulli-distributed
random variables with parameter $p \in [0,1]$.  Let $\nu$ be the
number of trials until the first ``success'' is obtained.

\begin{enumerate}
\item Show that
\[
  \mathbb E[\nu | \xi_1]
  = \xi_1 + (1 + \mathbb E[\nu])(1 - \xi_1) \,.
\]
\item Show that
\[
  \mathbb E[\nu] = \frac1p \,.
\]
(Hint: argue first that  (a) implies $\mathbb E[\nu] = p + (1+\mathbb
E[\nu])(1-p)$.) 
\end{enumerate}
\hfill (5+5)
%\newpage

\item Let $\xi_i$, $i \in \mathbb N$, be i.i.d.\ integrable random
variables taking positive values.  Set $\mu = \mathbb E[\xi_i]$.
\begin{enumerate}
\item Show that
\begin{equation*}
  \eta_n = \frac{\xi_1 \, \xi_2 \dots \xi_n}{\mu^n}
\end{equation*}
is a martingale.

\item Find a constant $\alpha$ such that
\[
  \zeta_n = \ln \eta_n - n \, \alpha
\]
is a martingale.
\end{enumerate}
\hfill(5+5)
%\newpage

\item In the setting of Problem 3, suppose that $\eta_0=1$ and
\[
  \xi_i =
  \begin{cases}
    \tfrac12 & \text{with probability } \frac23 \\
    2 & \text{with probability } \frac13 \,.
  \end{cases}
\]
The process is stopped when $\eta_n=\tfrac14$ or $\eta_n=4$.

\begin{enumerate}
\item Argue why the optional stopping theorem is applicable.  No need
to prove anything, argue by analogy with a standard problem.

\item Compute the probabilities that the process is stopped at
$\eta_n=\tfrac14$ or $\eta_n=4$, respectively.

\item Compute the expected stopping time.

(Hint: use Problem~3(b).)

\item Now suppose the process is only stopped when $\eta_n=\tfrac12$.
Is the optional stopping theorem still applicable?  Explain!
\end{enumerate}
\hfill(2+3+3+2)
%\newpage
%(Problem 4 ctd.)
%\newpage

\item Consider the following Markov chain.

\begin{tikzpicture}[baseline=(q1.base)]
  \node[state] (q1) {$1$};
  \node[state, right of=q1] (q2) {$2$};
  \node[state, right of=q2] (q3) {$3$};
  \node[state, above of=q2] (q4) {$4$};
  \node[state, below of=q2] (q5) {$5$};
  \draw (q1) edge[above left] node{$\tfrac12$} (q4)
        (q1) edge[below left] node{$\tfrac12$} (q5)
        (q2) edge[above] node{$\tfrac12$} (q1)
        (q2) edge[above] node{$\tfrac12$} (q3)
        (q3) edge[above right] node{$\tfrac12$} (q4)
        (q3) edge[below right] node{$\tfrac12$} (q5)
        (q5) edge[right] node{$1$} (q2)
        (q4) edge[left] node{$1$} (q2);  
\end{tikzpicture}
\begin{enumerate}
\item Write out the transition matrix.
\item Identify the classes.
\item Find the periods of all states.
\item Find the stationary distribution(s).
\end{enumerate}


\hfill(2+2+2+4)
%\newpage
%(Problem 5 ctd.)




\end{enumerate}



\end{document}