\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{30 October 2014}{14}

\begin{center}
\Large{\bf Problem Set 5 (due Monday, November 10)}
\end{center}

{\bf 1. (10 points) Single-variable linear program}

Exercise 29.5-9 of text.

{\bf 2. (10 points) LP for single-source shortest paths}

Exercise 29.2-3 of text.

{\bf 3. (20 points) Complementary slackness}

Problem 29-2 of text.

{\bf 4. (3 + 7 = 10 points) Markov chains and LP duality}

A Markov chain is a set of states (of a system) and the probability,
for each pair of states, of transitioning from one state to the other.
Markov chains have a wide range of applications including as models
for several physical or biological processes, in economics and the
social sciences, web search, and statistics.

Formally, a Markov chain is an $n \times n$ matrix $P$ where $p_{ij}$
denotes the probability of transitioning from state $i$ to state $j$;
if the system is in state $i$ at time $t$, then the probability that
it is in state $j$ at time $t+1$ is $p_{ij}$.  Clearly, $P$ satisfies
the property that the sum of the entries along any row is $1$.  

One nice, and very useful, property of Markov chains is the existence
of a stationary distribution $\pi$ over the state space, where $\pi$
is an $n \times 1$ vector with $\pi_i$ being the probability of the
system being in state $i$.  We say that $\pi$ is stationary if the
following holds: if at any time $t$, $\pi$ gives the probability
distribution for the state of the given system, then $\pi$ is also the
probability distribution for the state in time $t+1$.

For any Markov chain matrix, the existence of a stationary
distribution $\pi$ can be shown easily using LP duality, as we
establish in this exercise.
\begin{itemize}
\item[{\bf (a)}] Consider the following LP (over variables $\pi_i$)
  whose constraints define the stationary distribution.  

\begin{eqnarray*}
\min & \sum_i \pi_i &\\
\left(\sum_{j}p_{ji} \pi_j \right) - \pi_i & = & 0 \; \; \forall i\\
\sum_j \pi_j & \ge & 1\\
\pi_i & \ge & 0 \; \;  \forall i
\end{eqnarray*}

Show that the above LP is feasible if and only if the Markov chain has
a stationary distribution.

\item[{\bf (b)}] Derive the dual for the above LP.  Analyze the dual
  and argue using duality that the primal is always feasible.
\end{itemize}

\end{document}
