\documentclass{article}
\input{18440-preamble}

\begin{document}
\pset{10}{Dan Ports}{2003/12/05}{drkp@mit.edu}

\newcommand{\nmo}[1]{|| #1 ||_1]}


\begin{ppart}{Problem 1}
\paragraph{Part a}
Let $X$ be the constant random variable that takes value 1 with probability 1. Then, with $a=1$, \[\Pr{X \ge a} = \Pr{X \ge 1} = \Pr{X = 1} = 1 = \frac{1}{1} = \frac{\E{X}}{a}\]
\paragraph{Part b}
Suppose equality holds. Then for some $a$, $\Pr{X \ge a} = \frac{\E{X}}{a}$. 
$X$ can have non-zero values only at $0$ and $a$. Then $\Pr{X \ge a} = \Pr{X = a}$, and $\frac{\E{X}}{a} = \frac{a}{\Pr{X  = a}}{a} = \Pr{X=a}$, so equality holds in this case. 

\end{ppart}

\begin{ppart}{Problem 2}
\paragraph{Part a}
Consider the random variable that takes value $0$ with probability $\frac{1}{2}$ and value 2 with probability $\frac{1}{2}$. $\E{X} = 1$, and $\Var X = \E{X^2} - \E{X}^2 = 2 - 1 = 1$. Let $a = 1$. Then \[\Pr{(X-\mu)^2 \ge a^2} = \Pr{{X-1}^2 \ge 1} = 1 = \frac{Var X}{a^2}\] since both values $X$ can take are 1 unit away from the mean.
\paragraph{Part b}
\end{ppart}

\begin{ppart}{Problem 3 (option 2)}
\paragraph{Part a}
Consider element $i$ of $TC$:
\[(TC)_i = \sum{j=0}^M C_j T_{ij} = \sum{j=0}^M 1 T_{ij} = 1 \]
Hence each element of $TC$ is 1, so $TC=C$. Thus, $(T-I)C = TC-IC = C-C = 0$. Therefore the vector $C$ is in the nullspace of $T-I$. So the nullspace of $T-I$ has dimension at least $1$, and $T-I$ cannot have full rank. Therefore, it and its transpose, $(T-I)^t = T^t - I^t = T^t - I$ have rank at most $M$.
\paragraph{Part b}
$T^t - I$ is a square matrix with rank at most $M$, so it has a left nullspace of dimension at least 1, and there exists some column vector $v^t$ such that $(T^t - I)v^t = 0$. Hence, $((T^t - I)v^t)^t = 0^t$, so $v(T-I) = 0$ and $vT = v$.
\paragraph{Part c}
\paragraph{Part d}
Let $E$ be the $(M+1) \times (M+1)$ square matrix of all ones. Consider $wE$. This is a row vector in which each entry is equal to $\sum_{i=0}^M 1 w_i = 0$ by definition. Hence, $w(T-\epsilon E) = wT - \epsilon w E = wT - 0 = wT$. Since every entry of $T$ has value at least $\epsilon$, $(T-\epsilon E)$ has only non-negative entries; since $T$ is a Markov matrix, each row $(T-\epsilon E)$ sums to $1 - (M+1)\epsilon$. 
\begin{align*}
\nmo{wT} &= \nmo{w(T-\epsilon E)} \\
&= \sum_{i=0}^M \abs{\sum_j=0^M w_j (T-\epsilon E)_{ij}} \\
&\le \sum_{i=0}^M \sum_j=0^M \abs{w_j (T-\epsilon E)_{ij}} \\
&\le \sum_{i=0}^M \left(\sum_j=0^M \abs{w_j}\right) \left(\sum_j=0^M \abs{(T-\epsilon E)_{ij}}\right) \\
&= \sum_{i=0}^M \left(\sum_j=0^M \abs{w_j}\right) \left(\sum_j=0^M {(T-\epsilon E)_{ij}}\right) \\
&= \sum_{i=0}^M \nmo{w} (1-(M+1)\epsilon) \\
\end{align*}

\paragraph{Part e}
\end{ppart}
\end{document}