\documentclass[twoside]{article} \newcommand{\assgnnum}{5} \newcommand{\duedate}{Thursday, 4 June, 2009} \usepackage{amsmath} %\usepackage{fullpage} \usepackage{amssymb} \usepackage{bbm} \usepackage{fancyhdr,lastpage} \usepackage{paralist} \oddsidemargin 0in \evensidemargin 0in \topmargin -0.5in \headheight 0.25in \headsep 0.25in \textwidth 6.5in \textheight 9in \parskip 6pt \parindent 0in \footskip 20pt % set the header up \fancyhead{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % UPDATE THIS SECTION FOR YOUR HOMEWORK SUBMISSION % \fancyhead[LE,RO]{CME308: Assignment \assgnnum} % Put your name here \fancyhead[RE,LO]{Due: \duedate} %Put the date here, or whatever else you want... %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \renewcommand\headrulewidth{0.4pt} \setlength\headheight{15pt} \newcommand{\p}{\ensuremath{\mathbf{P}}} \renewcommand{\Pr}[1]{\ensuremath{\p \left \{ #1 \right \}}} \newcommand{\nti}{\ensuremath{n \to \infty}} \newcommand{\I}{\ensuremath{\operatorname{I}}} \newcommand{\One}[1]{\ensuremath{\mathbbm{1}_{\left \{ #1 \right \}}}} \newcommand{\E}{\ensuremath{\mathbf{E}}} \newcommand{\Ex}[2][]{\ensuremath{\E_{#1} \left[ #2 \right]}} \newcommand{\var}[1]{\ensuremath{\operatorname{Var}\left( #1\right)}} \newcommand{\cov}[2]{\ensuremath{\operatorname{Cov}\left( #1, #2\right)}} \newcommand{\F}{\ensuremath{\mathcal{F}}} \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\NormRV}[2]{\ensuremath{\operatorname{N}\left(#1, #2\right)}} \newcommand{\BetaRV}[2]{\ensuremath{\operatorname{Beta}\left(#1, #2\right)}} \newcommand{\eqD}{\ensuremath{\overset{\mathcal{D}}{=}}} \setlength{\parindent}{0in} \newcounter{pbctr} \setcounter{pbctr}{0} \newenvironment{problem}[1]{\refstepcounter{pbctr}\begin{trivlist} \item {\bf Problem \arabic{pbctr}: {\sc #1}\:}} {\end{trivlist}} \begin{document} \pagestyle{fancy} %\vspace*{15pt} {\bf Due Date: } This assignment is due on \duedate(with the natural 1 day extension for SCPD students), by 5pm in the box outside Durand 112. The \LaTeX{} incentive policy is in effect. % Problem 1 \begin{problem}{} In this problem, you will provide an alternative proof of the fact that finite state Markov chains typically converge to equilibrium exponentially rapidly. In particular, consider an irreducible finite state Markov chain having a transition matrix of the form \[P=\alpha\Lambda+\left(1-\alpha\right)Q\] for some $\alpha\in(0,1]$. where $\Lambda$ is a rank one stochastic matrix with identical rows. \begin{enumerate} \item Argue that if $P$ has a strictly positive column, it is of the above form. \item Prove that $Q\Lambda=\Lambda^{2}=\Lambda$. \item Using the equilibrium calculated in Problem 7 of Assignment 4, compute \[P^{n}-\Pi\] in terms of $\alpha$, $\Lambda$, and $Q$, where $\Pi$ is the rank one matrix having all rows equal to the equilibrium distribution $\pi$. \item Use matrix norms to show that there exists $a>0$ such that $\exp\left(an\right)\|P^{n}-\Pi\|\rightarrow0$ as $n\rightarrow\infty$. \end{enumerate} \end{problem} %Problem 2 \begin{problem}{} In this problem, we will use Lyapunov method, to study equilibrium behavior for state space models. Let $\left(X_{n}:n\geq0\right)$ be an $\mathbb{R}^{d}$-valued stochastic sequence defined by \[X_{n+1}=FX_{n}+Z_{n+1},\] where $\left(Z_{i}:i\geq1\right)$ is an iid sequence of $\mathbb{R}^{d}$-valued random vectors having a continuous and positive density and $F$ is a matrix having spectral radius less than one. \begin{enumerate} \item Compute \[P_{x}\left(X_{1}\leq y\right)\] in terms of the distribution of $Z_{1}$. \item Compute the conditional density of $X_{1}$ (i.e. the transition density), namely the function $p\left(x,y\right)$ such that \[P_{x}\left(X_{1}\in B\right)=\int_{B}p\left(x,y\right)dy.\] \item Prove that for any compact set $K$, \[\underset{x\in K}{\inf}p\left(x,y\right)>0.\] \item Prove that if $\mathrm{E}\|Z_{1}\|<\infty$, then $g\left(x\right)=\|x||$ is a Lyapunov function for $\left(X_{n}:n\geq0\right)$. (Hence, according to Theorem 8.15 of the Course Notes, $X$ has an equilibrium distribution $\pi$.) \\Note: $\| \cdot \|$ is not a 2-norm in general, and please specify the norm you use. \item (Extra Credit). Prove that if $\mathrm{E}\log\left(1+\|Z_{1}\|\right)<\infty$, Theorem 8.15 can still be applied. (You must modify the Lyapunov function.) \end{enumerate} \end{problem} %Problem 3 \begin{problem}{} (Heyman and Sobel, Exercise 3-16) Consider a small commercial catfish farming pond. Harvests occur annually and the harvest takes only a few days. The farmer can accurately estimate the amount (tons) of fish in the pond and then decide on the harvest quantity. The farmer's experience and U.S. Department of Agriculture data lead to the following probabilities: \bigskip{} \begin{minipage}[t]{0.2\paperwidth}% Tons of fish remaining after harvest this year% \end{minipage}\begin{tabular}{|r|cccccc|} \hline & \multicolumn{6}{c|}{Tons of fish at}\tabularnewline & \multicolumn{6}{c|}{harvest time next year}\tabularnewline \cline{2-7} & 0 & 1 & 2 & 3 & 4 & 5\tabularnewline \hline 0 & 1 & 0 & 0 & 0 & 0 & 0\tabularnewline 1 & 0 & 0.9 & 0.1 & 0 & 0 & 0\tabularnewline 2 & 0 & 0 & 0.8 & 0.1 & 0.1 & 0\tabularnewline 3 & 0 & 0 & 0 & 0.7 & 0.2 & 0.1\tabularnewline 4 & 0 & 0 & 0 & 0 & 0.6 & 0.4\tabularnewline 5 & 0 & 0 & 0 & 0 & 0 & 1\tabularnewline \hline \end{tabular} \bigskip{} The farmer's annual discount factor is 0.9 and the net profit (i.e., revenue - cost) is \$500 per ton. The farmer is young and optimistic and use an infinitely long planning horizon. There are 5 tons in the pond at the present harvest time. How many tons should be harvested now to maximize the expected present value of the net profit? What will the expected present value of the profit be when an optimal policy is used? Justify your answer. \end{problem} % Problem 4 \begin{problem}{} Consider a system that represents a conventional (``circuit-switched'') network. The network has $R$ routes. Each route connects a source node to a destination node along a set of links. The $i$-th link has the capacities to simultaneously handle $c_i$ calls. Customers attempt to initiate calls on route $r$ at rate $\lambda_r$ ($1\leq r\leq R$). A call is accepted on route $r$ only if there is sufficient link capacity on each link along the route. If insufficient capacity exists somewhere along the route, the customer's call is dropped (i.e. the customer gets a busy signal). A customer that successfully places a call completes the call at rate $\gamma_r$, at which time all the ``circuit links'' are released. We model this system as a network through an ``incidence matrix'' $A = (A_{ij}:1\leq i\leq m,1\leq r\leq R)$, with $A_{ir}=1$ if route $r$ uses link $i$ and is $0$ otherwise (where $m$ is the number of links). If we model the network as a Markov jump process $X(t) = (X_1(t),\ldots,X_R(t))^T$, the state space is $\mathbb{S} = \{n = (n_1,\ldots,n_R)^T \in \mathbb{Z}_+^R:A \cdot n \leq c\}$, where $c = (c_1,\ldots,c_m)^T$. \begin{enumerate} \item Specify the rate matrix $Q$ for this model. \item Show that the equilibrium distribution $\pi = (\pi(n):n\in\mathbb{S{}})$ is given by \[\pi(n) = \frac{\nu(n)}{\sum_{m\in\mathbb{S}}\nu(m)},\] where \[\nu(m) = \prod_{r=1}^R \frac{(\lambda_r/\gamma_r)^{m_r}}{m_r!}.\] \item Now, suppose that we look at the asymptotic setting in which the arrival rates are large and capacities are large (which is typical of the real world). We let $\lambda_r = \hat{\lambda}_r s$ and $c_i = \hat{c}_i s$ and let $s\rightarrow\infty$. Let $n^*$ be the mode of $(\pi(n):n\in\mathbb{S})$, so that $\pi(n^*)\geq \pi(n)$ for $n\in\mathbb{S}$ (i.e. $n^*$ is the ``most likely point''). Argue heuristically that \[n*\approx sx^*,\] where $x^*$ is the solution of a convex optimization problem. (Hint: you will need to use Sterling's approximation.) Remark: This scaling limit is sometimes called the ``thermodynamic limit''. It can be shown that if $X(\infty)$ is the equilibrium of $(X(t):t\geq0)$, then $s^{-1}X(\infty)\Rightarrow x^*$ as $s\rightarrow\infty$. \end{enumerate} \end{problem} %Problem 5 \begin{problem}{} Suppose that $X=(X(t):t\geq0)$ is a Markov jump process representing the price of an asset. We have an option on the asset under which we collect $\exp(-\alpha T)r(X(T))$ if we exercise the option at time $T$. Provide the HJB equation which characterizes the value function for computing \[\sup_T\E_x[\exp(-\alpha T)r(X(T))]\] and describe the optimal exercise time $T^*$ in terms of the value function. \end{problem} \end{document}