% -*- LaTeX -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Template for homeworks
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%**start of header

\documentclass[12pt,theorems]{mts-hw}

%**end of header
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsmath}
\newtheorem{fact}[theorem]{Fact}
\def\ZZ{\mathbb{Z}}
\def\CF{{\cal F}}
\def\CA{{\cal A}}
\def\CB{{\cal B}}
\def\pr{\mbox{P}}
\def\ex{\mbox{E}}


\begin{document}

\class {CSL857}{Randomized algorithms}      % Note: two arguments.

\author{Your name here}            

\prof {Amitabha Bagchi}                                                       
%
% Lecturer's name
%

\hwnumber{2}
% Homework number

\sem{II Sem, 2012-13}
% semester name

\due{22nd February 2013, 11:59PM}
        
\makeheader  

\noindent{\bf Q1. (Billingsley 5.17, page 83)} 
\begin{description}
\item{(a)} Suppose that $X_n \rightarrow_P X$ and that $f$ is a
  continuous function. Show that $f(X_n) \rightarrow_P f(X)$.
\item{(b)} Show that $\ex[|X - X_n|] \rightarrow 0$ implies $X_n
  \rightarrow_P X$. Show that the converse is false.
\end{description}

% insert answer here.

\noindent{\bf Q2. (Billingsley 6.1, page 89)} Show that $Z_n
\rightarrow Z$ with probability 1 if and only if for every positive
$\epsilon$ there exists an $n$ such that $\pr[|Z_k - Z| < \epsilon, n
\leq k \leq m] > 1 - \epsilon$ for all $m$ exceeding $n$. This
describes convergence with probability 1 in ``finite'' terms.

% insert answer here.
In all the following problems $S_n = X_1 + \cdots + X_n$.

\noindent{\bf Q3. (Billingsley 6.7, page 90)} 
\begin{description}
\item{(a)} Let $x_1, x_2, \ldots$ be a sequence of real number and put
  $s_n = x_1 + \cdots + x_n$. Assuming that $n^{-2} s_{n^2}
  \rightarrow 0$ and that the $x_n$ are bounded (i.e. each of them is
  finite), show that $n^{-1}s_n \rightarrow 0$.
\item{(b)} Suppose that $n^{-2} S_{n^2} \rightarrow 0$ with
  probability 1 and that the $X_n$ are uniformly bounded
  (i.e. $\sup_{n,\omega} |X_n(\omega)| $ is finite). Show that
  $n^{-1}S_n \rightarrow 0$ with probability 1. Here the $X_n$ need
  not be identically distributed or independent.
\end{description}

% insert answer here.

\noindent{\bf Q4. (Billingsley 6.11, page 90)} 
Suppose that $X_1,X_2,\ldots$ are $m$-dependent in the sense that
random variables more than $m$ apart in the sequence are
independent. More precisely, let $\CA_j^k = \sigma(X_k,\ldots,X_k)$
and assume that $\CA_{j_1}^{k_1}, \ldots, \CA_{j_l}^{k_l}$ are
independent if $k_{i-1} + m < j_i$ for $i = 2, \ldots, l$. Suppose
that $X_n$ have this property and are uniformly bounded and that
$\ex[X_n] = 0$. Show that $n^{-1} S_n \rightarrow 0$. 

% insert answer here.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%