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


\begin{document}

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

\author{Your name here}            

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

\hwnumber{1}
% Homework number

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

\due{24th January 2013, 11:59PM}
        
\makeheader  

\noindent{\bf Q1. (Billingsley 1.3, page 15)} Define a set $A$ to be
{\em trifling} if if for each $\epsilon > 0$ there exists a {\em
  finite} sequence of intervals $I_k$ satisfying $A \subset \cup_k
I_k$ and $\sum_k |I_k| < \epsilon$. This definition applies to all
subsets of the real line, not just to all subsets of $(0,1]$.
\begin{enumerate}
\item Show that a trifling set is negligible (as defined in
  Billingsley).
\item Show that the closure of a trifling set is trifling (where
  closure is defined as in analysis).
\item Find an example of a bounded negligible set that is not
  trifling.
\item Show that the closure of a negligible set may not be negligible.
\item Show that the finite unions of trifling sets are trifling but
  that this may not be true for countable unions.
\end{enumerate}

% insert answer here.

\noindent{\bf Q2. (Billingsley 1.4, page 15)} For $i = 0, 1, \ldots,
r-1$, let $A_r(i)$ be the set of numbers in $(0,1]$ whose
nonterminating expansions in base $r$ do {\em not} contain the digit
$i$.
\begin{enumerate}
\item Show that $A_i(r)$ is trifling as defined in the previous
  question.
\item Find a trifling set $A$ such that every point in $(0,1]$ can be
  represented in the form $x + y$ where $x,y \in A$.
\end{enumerate}

% insert answer here.

\noindent{\bf Q3. (Billingsley 2.3, page 33)} Let $\CF_1, \CF_2,
\ldots$ be classes of sets in a common space $\Omega$. 
\begin{enumerate}
\item Suppose that $\CF_1, \CF_2, \ldots$ are fields satisfying $\CF_n
  \subset \CF_{n+1}$. Show that $\cup_{n=1}^{\infty} \CF_n$ is an field.
\item  Suppose that $\CF_1, \CF_2, \ldots$ are $\sigma$-fields satisfying $\CF_n
  \subset \CF_{n+1}$. Show by example that $\cup_{n=1}^{\infty} \CF_n$
  need not be a  $\sigma$-field.
\end{enumerate}

% insert answer here.

\noindent{\bf Q4. (Billingsley 4.5, page 65)} 
\begin{enumerate}
\item Show that $\lim_n \pr(\lim \inf_k A_n \cap A_k^c) =
  0$. Hint: Show that $\lim \sup_n \lim \inf_k A_n \cap A_k^c$ is empty.
\item Put $A^* = \lim \sup_n A_n$ and $A_* = \lim \inf_n A_n$. Show
  that $\pr(A_n \setminus A^*) \rightarrow 0$ and $\pr(A_* \setminus
  A_n) \rightarrow 0$.
\end{enumerate}
% insert answer here.

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