%&latex
\documentclass[a4paper,11pt]{article}
\usepackage{amsmath,amsfonts}

\usepackage[margin=2.5cm]{geometry}




\begin{document}

%+Title
\title{Statistical Inference and Learning- Ex-1}
\author{Yiqing Wang and Boaz Nadler}
\date{due on Wed. Nov. 25 2015}
\maketitle
%-Title


\begin{description}
{\item Q1}
The mean height in Israel is $169$cm, with standard deviation of $9$cm. What is the probability of an Israeli being taller than $190$cm according to Markov? Chebychev? Assuming a Gaussian distribution? Can you use Hoeffding ?

\end{description}

\begin{description}
{\item Q2}

Let \(X_{1},\ldots,X_n\) be $n$ i.i.d. random variables from a distribution \(F\) with mean \(\mu\) and finite variance \(\sigma^2\). Recall that the standard error of the sample mean, namely $\sqrt{\mathbb{E}(\bar{X}_n-\mu)^2}$ decays like $1/\sqrt n$. 
Interestingly, there are cases where one can estimate population parameters (such as the mean) at a much \textit{faster} rate. If they exist, these are known as \textit{superefficient} estimators. 

In this question we consider one such case: Let $X_i$ be i.i.d. from  a uniform distribution $U[0,\theta]$, where $\theta$ is an unknown parameter. Clearly the mean of \(X_{i}\) is $\mu=\theta/2$.  

i) One method to estimate $\mu$ is by the sample mean $\frac1n\sum_i X_i$. What is the standard deviation of this estimator ?

ii) A different method is based on the maximum observed value of the \(X_i\)'s.
Let $Y_n=\max X_i$. What is $\mathbb{E}[Y_n]$ and what is $Var[Y_n]$. 
How can these be used to construct a different estimator for $\mu$, and what is its error as a function of sample size $n$. 

\end{description}

%Q3
%(a)Can you construct an estimator $T_1$ for $\theta$ with $Var[T_1]=0$?
%(b)How about $E[(T_1-\theta)^2]=0$?

%Can you construct an estimator that satisfies (a) and (b) for all possible %values of $\theta$? (i.e.- uniformly in \theta\in\Theta$).

%Q4
%``There is a chance of $90\%$ of my hypothesis being correct''. 

%Is this statement compatible with the hypothesis testing framework we presented?




  

\begin{description}
\item Q3
The Kullback - Leibler divergence between two distributions with densities $p,q$ is defined as
\[
D_{KL}[p||q]=\int p(x) \log\left( \frac{p(x)}{q(x)}\right)dx
\]
\begin{enumerate}
\item Show that $D_{KL}[p||q]\geq0$ and $D_{KL}[p||q]=0$ if and only if $p=q$ almost everywhere.
Hint: use the fact that 
\[
\log\left( \frac{p(x)}{q(x)} \right)\leq \frac{p(x)}{q(x)}-1
\]
and equality holds i.f.f. $p(x)=q(x)$.
\item Show that $D_{KL}[p||q]$ is not necessarily symmetric, that is
 $D_{KL}[p||q]\neq D_{KL}[q||p]$.
\item
Compute  $D_{KL}[p_1||p_2]$ for the following Gaussian distributions: 
\begin{eqnarray}\label{eq:gauss-def1}
p(x)&=&\frac{1}{\sqrt{2\pi\sigma_1^2}}e^{-\frac{(x-\mu_1)^2}{2\sigma_1^2}}\\
q(x)&=&\frac{1}{\sqrt{2\pi\sigma_2^2}}e^{-\frac{(x-\mu_2)^2}{2\sigma_2^2}}\label{eq:gauss-def2}
\end{eqnarray}

\item Suppose $p$ and $q$ both have the same support (e.g. are absolutely continuous w.r.t. each other). Does this imply that their KL divergence is finite, $D_{KL}[p||q] <\infty$ ?  


\end{enumerate}


\end{description}


\begin{description}
\item Q4
Consider a real-valued random variable $X$ for which there is some constant $c > 0$ such that
\begin{align*}
\forall \lambda \in (-c, c), \; \quad \mathbb{E} e^{\lambda X} < +\infty.
\end{align*}
\begin{enumerate}
\item Show that the expectation of the absolute value of $X$, $\mathbb{E}|X|$, is finite.
\item Show that the function
\begin{align*}
f: \lambda \in (-c, c) \mapsto \mathbb{E} [e^{\lambda X}]
\end{align*}
is infinitely differentiable and its $k$-th derivative is
\begin{align*}
\forall \lambda \in (-c, c), \quad f^{(k)}(\lambda) = \mathbb{E[} X^k e^{\lambda X}].
\end{align*}
\item Show that there is some constant $s > 0$ such that
\begin{align*}
\forall \lambda \in [-c/2, c/2], \;\; \mathbb{E} e^{\lambda (X - \mathbb{E}X)} \leq e^{s\lambda^2}.
\end{align*}
\item Show that as a result, we have
\begin{align*}
\mathbb{P}(X \geq \mathbb{E}X + t) \leq 
\begin{cases}
e^{-\frac{t^2}{4s}}, \; &t \in [0, sc]\\
e^{-\frac{ct}{4}},\; &t \in (sc, +\infty).
\end{cases}
\end{align*}
\item Let $Z = \sum_{i=1}^m X_i^2$ where $(X_i)_{1\leq i\leq m}$ are $m$ i.i.d. Gaussian r.v. $\mathcal{N}(0, 1)$. The random variable $Z$ follows a chi-squared distribution with $m$\ degrees of freedom, and is denoted as \(Z\sim \chi^2_m\). Compute the mean and standard deviation of $Z$. Then, show
\begin{align*}
\forall t > 0, \;\; \mathbb{P}(\chi_m^2 \geq m + 2mt + 2m \sqrt{t}) \leq e^{-mt}.
\end{align*} 
\end{enumerate}


\end{description}




\end{document}


