% -*- 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%