\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}


\usepackage[english]{babel}
\usepackage{tabularx}
\usepackage{hhline}
%\usepackage[leqno,intlimits]{amsmath}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage{enumerate}
\usepackage{mdwlist}

% \setlength{\marginparwidth}{0pt}
% \addtolength{\textwidth}{100pt}
% \addtolength{\hoffset}{-50pt}
% \addtolength{\textheight}{160pt}
% \setlength{\voffset}{-80pt}

\setlength{\marginparwidth}{0pt}
\addtolength{\textwidth}{4cm}
\addtolength{\hoffset}{-2cm}
\addtolength{\textheight}{4cm}
\setlength{\voffset}{-3cm}

\def\diff{\,\mathrm{d}}
\def\prob{\mathbb{P}}
\def\expect{\mathbb{E}}

\def\IR{\mathbb{R}}
\def\IN{\mathbb{N}}

\def\sigalg{\mathcal{F}}
\def\Leb{\mathrm{Leb}}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}



\begin{document}
\begin{center}
{\bf Probability 1\\
CEU Budapest, fall semester 2013}\\
Imre Péter Tóth\\
{\bf Homework sheet 1 -- solutions}\\
\end{center}



\begin{enumerate}[{1}.1]
%
 \item Define a $\sigma$-algebra as follows:
  \begin{definition}
   For a nonempty set $\Omega$, a family $\sigalg$ of subsets of $\omega$ (i.e. $\sigalg\subset 2^\Omega$, where $2^\Omega:=\{A:A\subset\Omega\}$ is the power set of $\Omega$) is called a $\sigma$-algebra over $\Omega$ if
    \begin{enumerate}[(i)]
     \item \label{it:sigalg0} $\emptyset\in\sigalg$
     \item \label{it:sigalgcompl} if $A\in \sigalg$, then $A^C:=\Omega\setminus A\in \sigalg$ (that is, $\sigalg$ is closed under complement taking)
     \item \label{it:sigalgunion} if $A_1,A_2,\dots\in\sigalg$, then $(\cup_{i=1}^\infty A_i)\in \sigalg$ (that is, $\sigalg$ is closed under countable union).
    \end{enumerate}
  \end{definition}
Show from this definition that a $\sigma$-algebra is closed under countable intersection, and under finite union and intersection.

\textbf{Solution:}\\
If $B_1,B_2,\dots\in\sigalg$ then $A_i:=\Omega\setminus A_i \in \sigalg$ as well, for $i=1,2,\dots$ due to (\ref{it:sigalgcompl}), and thus $C:=(\cup_{i=1}^\infty A_i)\in \sigalg$ by (\ref{it:sigalgunion}). Finally, $\Omega\setminus C\in\sigalg$ by (\ref{it:sigalgcompl}), but $\Omega\setminus C=\cap_{i=1}^\infty B_i$ by the basics of set algebra, so we have shown that $\sigalg$ is closed under countable intersection. For finite union, notice that if $A_1,A_2,\dots,A_n\in\sigalg$, then we can choose $A_{n+1}=A_{n+2}=\dots =\emptyset\in\sigalg$ by (\ref{it:sigalg0}), to get $(\cup_{i=1}^n A_i)=(\cup_{i=1}^\infty A_i)\in \sigalg$ by (\ref{it:sigalgunion}). So $\sigalg$ is shown to be closed under finite union. Closedness under finite intersection can be seen similarly.
%
 \item
  \begin{enumerate}
   \item We toss a biased coin, on which the probability of heads is some $0\le p \le 1$. Define the random variable $\xi$ as the indicator function of tossing heads, that is
    $$
      \xi:=\begin{cases}
            0, \text{ if tails}\\
            1, \text{ if heads}
            \end{cases}.
    $$
    \begin{enumerate}
     \item Describe the distribution of $\xi$ (called the Bernoulli distribution with parameter $p$) in the ``classical'' way, listing possible values and their probabilities,
     \item and also by describing the distirbution as a measure on $\IR$, giving the weight $\prob(\xi\in B)$ of every Borel subset $B$ of $\IR$.
     \item Calculate the expectation of $\xi$.
    \end{enumerate}
   \item We toss the previous biased coin $n$ times, and denote by $X$ the \emph{number of heads} tossed.
    \begin{enumerate}
     \item Describe the distribution of $X$ (called the Binomial distribution with parameters $(n,p)$) by listing possible values and their probabilities.
     \item Calculate the expectation of $X$ by integration (actually summation in this case) using its distribution,
     \item and also by noticing that $X=\xi_1+\xi_2+\dots +\xi_n$, where $\xi_i$ is the indicator of the $i$-th toss being heads, and using linearity of the expectation.
    \end{enumerate}
   \end{enumerate}

\textbf{Solution:}
  \begin{enumerate}
   \item 
    \begin{enumerate}
     \item The possible values are $0$ and $1$, their probabilities are $\prob(\xi=0)=1-p$ and $\prob(\xi=1)=p$.
     \item $\mu(B)=\prob(\xi\in B)=
           \begin{cases}
            1, &\text{ if $0\in B$ and $1\in B$},\\
            1-p, &\text{ if $0\in B$ but $1\notin B$},\\
            p, &\text{ if $1\in B$ but $0\notin B$},\\
            0, &\text{ if $0\notin B$ and $1\notin B$}.
           \end{cases}
           $
     \item $\expect\xi=0\cdot \prob(\xi=0)+1\cdot \prob(\xi=1)=0\cdot(1-p)+1\cdot p=p$.
    \end{enumerate}
   \item
    \begin{enumerate}
     \item The possible values are $0,1,2,\dots,n$, their probabilities are 
      $$\prob(X=k)=\binom{n}{k}p^k(1-p)^{n-k}, \quad k=0,1,2,\dots,n.$$
     \item If we denote the distribution of $X$ by $\mu$, then 
      $$\expect X=\int_\IR x\diff\mu(x)=\sum_{k=0}^n k\cdot\mu(\{k\})=\sum_{k=0}^n k\cdot\prob(X=k)=\sum_{k=0}^n k\binom{n}{k}p^k(1-p)^{n-k}.$$
      To calculate this sum, one of the many ways is to consider the two-variable function
      $$f(u,v):=\sum_{k=0}^n k\binom{n}{k}u^k v^{n-k}.$$
      Then what we want to know is $\expect X=f(p,1-p)$, but of course we are even more happy if we can calculate $f(u,v)$ for every $(u,v)$. Now we notice that
      $$f(u,v)=u\,\frac{\partial}{\partial u}g(u,v)\text{ where }g(u,v)=\sum_{k=0}^n \binom{n}{k}u^k v^{n-k}.$$
      This is now easy: by the binomial theorem $g(u,v)=(u+v)^n$, so
      $$f(u,v)=u\,\frac{\partial}{\partial u}(u+v)^n=nu(u+v)^{n-1},$$
      and
      $$\expect X=f(p,1-p)=np(p+1-p)^n=np.$$
     \item This is much easier:
      $$\expect X=\expect(\sum_{i=1}^n \xi_i)=\sum_{i=1}^n\expect \xi_i=\sum_{i=1}^n p=np.$$
    \end{enumerate}
   \end{enumerate}
%
 \item \emph{The Fatou lemma} is the following
  \begin{theorem}
   Let $(\Omega,\sigalg,\mu)$ be a measure space and $f_1$, $f_2$, \dots a sequence of measureabale functions $f_n:\Omega\to\IR$, which are nonneagtive, e.g. $f_n(x)\ge 0$ for every $n=1,2,\dots$ and every $x\in\Omega$. Then
    $$\int_\Omega \liminf_{n\to\infty} f_n(x) \diff \mu(x)\le \liminf_{n\to\infty} \int_\Omega f_n(x)\diff \mu(x)$$
   (and both sides make sense).
  \end{theorem}
 Show that the inequality in the opposite direction is in general false, by choosing $\Omega=\IR$, $\mu$ as the Lebesgue measure on $\IR$, and constructing a sequence of nonnegative $f_n:\IR\to\IR$ for which $f_n(x)\xrightarrow{n\to\infty} 0$ for every $x\in\IR$, but $\int_\IR f_n(x) \diff x\ge 1$ for all $n$.

\textbf{Solution:}
The standard counterexample is
$$f_n(x):=\begin{cases}
           1, &\text{if $n\le x\le n+1$,}\\
           0, &\text{if not.}
          \end{cases}
$$
The phenomenon behind the counteraxample -- as often -- is that exchangeability of integral and limit can fail if mass ``escapes to infinity''.
%
 \item The \emph{ternary} number $0.a_1 a_2 a_3 \dots$ is the analogue of the usual decimal fraction, but writing numbers in base $3$. That is, for any sequence $a_1,a_2,a_3,\dots$ with $a_n\in\{0,1,2\}$, by definition
 $$0.a_1 a_2 a_3 \dots:=\sum_{n=1}^\infty \frac{a_n}{3^n}.$$
 Now let us construct the ternary fraction form of a random real number $X$ via a sequence of fair coin tosses, such that we rule out the digit $1$. That is,
 $$a_n:=\begin{cases}
        0, \text{ if the $n$-th toss is tails,}\\
        2, \text{ if the $n$-th toss is heads}\\
       \end{cases},
 $$
 and setting $X=0.a_1 a_2 a_3 \dots$ (ternary). In this way, $X$ is a ``uniformly'' chosen random point of the famous \emph{middle-third Cantor set} $C$ defined as
 $$C:=\left\{\sum_{n=1}^\infty \frac{a_n}{3^n}\, ,\, a_n\in\{0,2\}\, (n=1,2,\dots)\right\}.$$ 
 Show that
  \begin{enumerate}
   \item The distribution of $X$ gives zero weight to every point -- that is, $\prob(X=x)=0$ for every $x\in\IR$. (As a consequence, the cumulative distribution function of $X$ is continuous.)
   \item The distribution of $X$ is not absolutely continuous w.r.t the Lebesgue measure on $\IR$.
  \end{enumerate}

\textbf{Solution:}
  \begin{enumerate}
   \item Similarly to a decimal expansion, the ternary expansion of a real number $x\in[0,1]$ is essentially unique: every $x$ can be written in the form $x=0.a_1 a_2 a_3 \dots$ in only one, or possibly two ways. (There are actually two ways for some rational numbers, since e.g. $0.1022222\dot{2}=0.1100000\dot{0}$.) However, every individual sequence $a_1,a_2,a_3,\dots$ has probability $\frac12\cdot\frac12\cdot\frac12\cdot\dots=0$, so every $x$ is given weight at most twice zero which is still zero.
   \item The distribution of $X$ cannot be absolutely continuous w.r.t. Lebesgue measure, since it gives positive measure to $C$ ($\prob(X\in C)=1$), which has Lebesgue measure zero ($\Leb(C)=0$). To see that the Lebesgue measure of $C$ is indeed zero, notice that the set in the $n$-t level of the construction of $C$,
   $$C_n:=\left\{\sum_{k=1}^\infty \frac{a_k}{3^k}\, ,\, a_k\in\{0,2\}\text{ for } k=1,2,\dots,n\text{ but }a_k\in\{0,1,2\}\text{ for } k\ge n+1\right\},$$
   has Lebesgue measure
   $$\Leb(C_n)=\left(\frac23\right)^n.$$
   Now $C\subset C_n$ for every $n\in\IN$, so
   $$\Leb(C)\le\Leb(C_n)=\left(\frac23\right)^n\text{ for every }n,$$
   which implies that $\Leb(C)=0$.

   (Actually, this means not only that the distribution $\mu$ of $X$ is not absolutely continuous w.r.t. Lebesgue measure, but that the two measures are singular w.r.t each other, which means that $\IR$ can be decomposed into two disjoint subsets (namely $C$ and $\IR\setminus C$,) such that one is ``unseen'' by one measure ($\Leb(C)=0$), while the other is ``unseen'' by the other measure ($\mu(\IR\setminus C)=0$).)
  \end{enumerate}
%
\end{enumerate}

\end{document}

