\documentclass{article}

\usepackage{latexsym}
\usepackage{bbm}
\usepackage[small,bf]{caption2}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{amsmath,amssymb,amsthm,amsfonts}
\usepackage{url}
\usepackage{hyperref}
\usepackage{enumerate}

\usepackage{tikz}
\usetikzlibrary{shapes.geometric, arrows}

%% Page size
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}

% Footnote commands.
\newcommand{\footnotenonumber}[1]{{\def\thempfn{}\footnotetext{#1}}}
\newcommand{\footnotetight}[1]{\footnote{\renewcommand\baselinestretch{1}\footnotesize #1}}

\newtheorem{propo}{Proposition}[section]
\newtheorem{lemma}[propo]{Lemma}
\newtheorem{definition}[propo]{Definition}
\newtheorem{coro}[propo]{Corollary}
\newtheorem{thm}[propo]{Theorem}
\newtheorem{conj}[propo]{Conjecture}
\newtheorem{fact}[propo]{Fact}
\newtheorem{remark}[propo]{Remark}
\newtheorem{claim}[propo]{Claim}

\newcommand{\T}{{\sf T}}
\newcommand{\Tk}{{\mathbb T_k^{\phi}}}
\newcommand{\Tl}{{\sf T(\ell)}}
\newcommand{\uH}{{\underbar{H}}}
\newcommand{\mulH}{{ \mu^{\ell,H}}}
\newcommand{\dTl}{{ \partial \T(\ell)}}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\prob}{\mathbb{P}}
\newcommand{\IS}{{\rm IS}}
\newcommand{\ind}{\mathbb{I}}
\newcommand{\naturals}{\mathbb{N}}
\def\vE{\vec{E}}
\def\reals{\mathbb R}
\def\tp{\tilde{p}}
\def\hx{\hat{x}}
\def\cX{{\cal X}}
\def\cN{{\cal N}}
\def\hx{\widehat{x}}
\def\hs{\widehat{s}}
\def\hz{\widehat{z}}
\def\<{\langle}
\def\>{\rangle}
\def\cN{{\cal N}}
\def\Cost{{\cal C}}

\def\meas{{\sf M}}
\def\vE{{\vec{E}}}
\def\F{{\sf F}}
\def\Fv{{\sf F^v}}
\def\hT{\widehat{T}}
\def\cE{{\cal E}}
\def\Tmix{T_{\rm mix}}
\def\ones{\mathds 1}
\def\dBall{\partial{\sf B}}
\def\SAW{\mbox{\tiny SAW}}
\def\pe{P_{\rm error}}
\def\tnu{\tilde{\nu}}
\def\IS{{\rm IS}}
\def\ind{{\mathbb I}}
\def\reals{{\mathbb R}}
\def\naturals{{\mathbb N}}
\def\root{\o}
\def\vE{\vec{E}}
\def\te{\theta_{\rm e}}
\def\tv{\theta_{\rm v}}
\def\be{b_{\rm e}}
\def\bv{b_{\rm v}}
\def\Bethe{{\mathbb F}}
\def\E{{\mathbb E}}
\def\prob{{\mathbb P}}
\def\hs{{\hat t}}
\def\htt{{\hat t}}
\def\hw{{\hat w}}
\def\E{{\mathbb E}}
\def\sign{{\rm sign}}
\def\BP{{\bf P}}
\def\pvar{{q}}
\def\pmean{{\alpha}}
\def\reals{{\mathbb{R}}}
\def\cX{{\cal X}}
\def\cY{{\cal Y}}
\def\cZ{{\cal Z}}
\def\hx{{\hat x}}
\def\da{{\partial a}}
\def\di{{\partial i}}
\def\ind{{\mathbb I}}
\def\deg{{\rm deg}}
\def\tA{{\widetilde A}}
\def\cI{{\cal I}}
\def\cC{{\cal C}}
\def\cC{{\cal C}}
\def\cG{{\cal G}}
\def\normeq{{\propto}}
\def\tol{\leftarrow}
\def\normal{{\rm N}}
\def\root{{o}}
\def\tmu{{\tilde \mu}}
\def\id{{\mathbb I}}
\def\cN{{\cal N}}
\def\hh{\hat{h}}
\def\hJ{\hat{J}}
\def\bone{{\bf 1}}
\def\bx{\overline{x}}
\def\Lap{{\cal L}}
\def\BP{{\sc\rm BP}}
\def\CTree{{\sf CT}_G}
\def\cL{{\cal L}}
\def\Gibbs{{\mathbb G}}
\def\Bethe{{\mathbb F}}
\def\TRW{{\mathbb F}_{\mbox{\tiny TRW}}}
\def\MARG{{\rm MARG}}
\def\cR{{\cal \bf R}}
\def\cT{{\cal T}}
\def\LOC{{\rm LOC}}
\def\Cov{{\rm Cov}}
\def\Var{{\rm Var}}
\def\conv{{\rm conv}}
\def\cR{{\cal \bf R}}
\def\det{{\rm det}}
\def\by{\overline{y}}

\def\rank{{\rm rank}}
\def\<{\langle}
\def\>{\rangle}
\def\tX{\widetilde{X}}
\def\tx{\widetilde{x}}
\def\hx{\widehat{x}}

\def\de{\text{d}}
\def\deg{\text{deg}}
\def\ind{{\mathbb I}}
\def\ve{\varepsilon}
\def\eps{\epsilon}
\def\M{{\sf M}} 
\def\N{{\sf N}} 
\def\Z{{\sf Z}} 
\def\V{{\sf V}} 
\def\U{{\sf U}} 
\def\hM{\hat{\sf M}} 
\def\E{{\mathbb E}}
\def\te{\tilde{\epsilon}}
\def\reals{\mathbb{R}}

\def\tM{\widetilde{\sf M}}
\def\tN{\widetilde{\sf N}}
\def\de{\text{d}}
\def\ux{\underline{x}}
\def\uy{\underline{y}}
\def\uz{\underline{z}}
\def\us{\underline{s}}
\def\ind{{\mathbb I}}
\def\cX{{\cal X}}
\def\cY{{\cal Y}}
\def\me{{\nu}}
\def\diam{{\rm diam}}
\def\sTV{\mbox{\tiny TV}}
\def\ve{\varepsilon}
\def\di{\partial i}
\def\T{{\rm T}}
\def\Ball{{\sf B}}
\def\M{{\sf M}} 
\def\normeq{{\cong}}
\def\atanh{\text{atanh}}
\def\P{{\sf P}}
\def\prob{{\mathbb P}}
\def\F{{\sf F}}
\def\H{{\mathbb H}}
\def\uX{\underline{X}}
\def\cD{{\cal D}}
\def\f{{\mathfrak f}}
\def\E{{\mathbb E}}
\def\me{\nu}
\def\mh{\widehat{\nu}}
\def\naturals{{\mathbb N}}
\def\rationals{{\mathbb Q}}
\def\da{{\partial a}}
\def\perr{{\rm P}_{\rm err}}
\def\Em{{\rm E}_{\rm m}}
\def\Xh{\widehat{X}}
\def\eps{\epsilon}
\def\hm{\hat{m}}

\def\vv{\vec{v}}
\def\vu{\vec{u}}
\def\uv{\underline{v}}
\def\uu{\underline{u}}
\def\reals{\mathbb{R}}
\def\RMSE{{\sf RMSE}}
\def\cF{{\cal F}}
\def\cP{{\mathcal P}}
\def\id{{\mathbf 1}}
%\def\Z{\mathbb{Z}}
\def\xm{{\bf x}}
\def\um{{\bf u}}

\def\td{\widetilde{d}}
\def\tD{\widetilde{D}}
\def\porth{{\sf P}^{\perp}}
\def\id{{\bf I}}
\def\one{{\bf 1}}
\def\b0{{\bf 0}}
\def\Rperp{R^{\perp}}
\def\supp{{\rm supp}}
\def\Tr{{\rm Tr}}
\def\cS{{\cal S}}
\def\cX{{\cal X}}
\def\cC{{\cal C}}
\def\Cost{{\cal C}}
\def\String{{\sf S}}
\def\Poly{{\rm Poly}}

\def\uS{\underline{S}}
\def\uc{\underline{c}}
\def\hZ{\widehat{Z}}
\def\cut{{\rm cut}}
\def\tol{\leftarrow}
\def\normal{{\rm N}}
\def\root{{o}}

\def\meas{{\sf M}}
\def\vE{{\vec{E}}}
\def\F{{\sf F}}
\def\Fv{{\sf F^v}}
\def\hT{\widehat{T}}
\def\cE{{\cal E}}
\def\Tmix{T_{\rm mix}}
\def\ones{\mathds 1}
\def\dBall{\partial{\sf B}}
\def\SAW{\mbox{\tiny SAW}}
\def\pe{P_{\rm error}}
\def\tnu{\tilde{\nu}}


% Commands for handout headers
\newcommand{\handout}[5]{
%   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{ \vbox{ \hbox to 5.78in { \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #3  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #4 \hfill #5} }
     }
   }
   \end{center}
   \vspace*{4mm}
   \newcommand{\lecturenum}{#1}
}


%% the format for the lecture environment is
% \begin{lecture}{lecture number}{lecture title}{scribe(s)}{lecture date}
\begin{document}
\handout{}{}{HW0 (4 problems)}{Sewoong Oh}{CSE515}



\bigskip
\noindent
{\bf Basic probability.}

\begin{itemize}

 \item[1.] {\em [2 points]} For three discrete random variables $x$, $y$, and $z$ 
 with a joint probability distribution $p(x,y,z)$, we say $x$ is {\bf conditionally independent} of $y$
 given $z$ if and only if $p(x,y|z)=p(x|z)p(y|z)$, 
 where $p(x|z)=\frac{p(x,z)}{p(z)}=\frac{\sum_{y'}p(x,y',z)}{\sum_{x',y'}p(x',y',z)}$ is the conditional probability 
 distribution of $x$ given $z$, and $p(x,y|z)$ and $p(y|z)$ are defined similarly. 
 We use the notation $x\text{--}z\text{--}y$ to denote that $x$ and $y$ are independent conditioned on $z$. 
 We use $x\text{--}()\text{--}(y,z)$ to denote that $x$ is independent of the pair of random variables $(y,z)$ (that is $p(x,y,z)=p(x)p(y,z)$). 
 Here is an example of a formal proof I expect from your solutions. 
 I will prove that 
 $x\text{--}()\text{--}(y,z)$ implies $x\text{--}()\text{--}z$, that is $x$ independent of $(y,z)$ implies $x$ independent of $z$. This sounds obviously true, and it is true. The point is to teach you how to write the proof. 
 \begin{proof}
 By the assumption $x\text{--}()\text{--}(y,z)$, we have $p(x,y,z)=p(x)p(y,z)$. This implies that 
 \begin{eqnarray}
    p(x,z) &=& \sum_{y'} p(x,y',z) \nonumber \\
    &=& \sum_{y'} p(x)p(y',z) \nonumber \\
    &=&  p(x)p(z) \;, \label{eq:1.1}
 \end{eqnarray}
 where in the last equality we used the fact that $p(z) = \sum_{x',y'}p(x',y',z)=\sum_{x',y'}p(x')p(y',z) = \sum_{y'}p(y',z)$ as probability measures sum to one and $\sum_{x'}p(x')=1$. By Eq.\eqref{eq:1.1} we have the desired claim: $x\text{--}()\text{--}z$.
 \end{proof}
 
 This is a little excessive. You don't have to write all the details like I did in this example. It was just to make sure everyone can follow every step. In your solutions, you can skip some obvious steps but have to write enough details to make sure that we know what you are doing. 
 
 Now, prove each of the following properties.
  \begin{enumerate}
  \item[$(a)$]  $x\text{--}()\text{--}(y,z)$ implies $x\text{--}z\text{--}y$
  \item[$(b)$]  $x\text{--}z\text{--}(y,w)$ implies $x\text{--}z\text{--}y$
  \item[$(c)$]  $x\text{--}z\text{--}(y,w)$ and $y\text{--}z\text{--}w$ implies $(x,w)\text{--}z\text{--}y$
  \end{enumerate}
  
  \item[]
  \item[]
 \item[2.] {\em [2 points]} There are two coins, one is a fair coin and the other is biased. 
 The outcome of tossing a fair coin is a head (H) with probability half. 
 The outcome of tossing a biased coin is a head (H) with probability $3/4$. 
 We are given a coin at random (equal probability of getting a fair or biased coin), 
 and want to test whether the coin is biased or not based on $n$ coin tosses. 
 We toss the coin $5$ times independently and get $(H,H,T,T,H)$. 
 Let $x\in\{\text{fair,biased}\}$ denote the random variable for the choice of the coin and let $y=(H,H,T,T,H)\in\{H,T\}^5$ denote the observation from 5 tosses of the coin.
 \begin{itemize}
     \item [$(a)$] What is the probability that the coin is a biased coin given the observations? In other words, compute ${\mathbb P}(x=\text{biased}|y=(H,H,T,T,H))$. 
     \item[$(b)$]  What is your {\bf maximum a posteriori (MAP) estimate}?  A MAP estimate is defined as the most likely estimate of the hidden variable $x$ given the observations:  $\arg\max_{x\in\{\text{fair,biased}\}} {\mathbb P}(x|y)$. 
     \item[$(c)$] 
 We want to show that the count of the number of heads is a sufficient statistic. Prove that the MAP estimate does not depend on the order of the outcome. 
 \end{itemize}
 
\end{itemize}

\bigskip
\noindent
{\bf Basic linear algebra.}
\begin{itemize}
 \item[3.] {\em [2 points]} An $n\times n$ dimensional symmetrix matrix $A$ is {\bf positive definite} if $x^TAx >0$ for any vector $x\in\reals^n$, 
 where $x^T$ is the transpose of the column vector $x$. It is {\bf positive semidefinite} if 
 $x^TAx \geq 0$ for any $x$. Prove that if $A$ has eigen values which are all positive, then $A$ is positive definite. 
 \item[]
 $[$Hint: A symmetric matrix $A$ can be factorized by eigen decomposition as $A=Q\Lambda Q^T$.  
   $Q$ is a unitary matrix such that $QQ^T=Q^TQ=I$, where $I$ is the $n$-dimensional identity matrix, 
   and $\Lambda$ is a diagonal matrix with the eigen values $\lambda_i$ of matrix $A$ in the diagonals.
   Then, we are left to show that if $\Lambda$ is a diagonal matrix with strictly positive entries, 
   then $y^T\Lambda y>0$, where we changes variables by setting $y=Q^T x$. $]$.
  \item[]
  \item[]
 \item[4.] {\em [2 points]} Find a vector $y^*$ in terms of $A_{ij}$'s, $h_i$'s and $x$ that minimizes a {\bf quadratic function} 
	\begin{eqnarray*}  
	 f(x,y) \;\; =\;\;  \begin{bmatrix} x^\top & y^\top  \end{bmatrix} \begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix} 
	 \;+\;   \begin{bmatrix}h_1^\top &h_2^\top \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}\;,
	\end{eqnarray*}
	where $A_{22}$ is 
	a positive definite matrix. 
	Here, $x\in{\mathbb R}^{d_x}$,
	$y\in{\mathbb R}^{d_y}$, 
	$A_{11}\in{\mathbb R}^{d_x\times d_x}$, 
	$A_{12}\in{\mathbb R}^{d_x\times d_y}$, 
	$A_{21}\in{\mathbb R}^{d_y\times d_x}$, 
	$A_{22}\in{\mathbb R}^{d_y\times d_y}$, 
	$h_1\in{\mathbb R}^{d_x}$, and  
	$h_2\in{\mathbb R}^{d_y}$. 
	You need to show your derivation. 
	[Note: the minimizer $y^*(x)$ is a linear function of $x$.]
\end{itemize}

% -------------------------------------------------------------------------------------------------------------------------------------------------------

\end{document}
\theend

