\documentclass{article}
\usepackage{titling}

\title{MATH 418/544, Assignment 0}
\date{Due 2023-09-29, 23:59} %replace by your name and student id

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\usepackage{amsmath,amsthm,amsfonts,amssymb}  %math stuff
\usepackage{graphicx} %to embed images
\usepackage{enumitem} %fancy lists
\usepackage{fullpage} %smaller margins
\usepackage{color} %guess

\setlist[itemize,1]{nosep}
\setlist[enumerate,1]{nosep,label=(\alph*)}

\renewcommand{\P}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\cA}{\mathcal A}
\newcommand{\cB}{\mathcal B}
\newcommand{\cF}{\mathcal F}
\newcommand{\eps}{\varepsilon}
\renewcommand{\phi}{\varphi}
\newcommand{\ind}{{\mathbf 1}}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Poi}{Poi}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\Exp}{Exp}
\DeclareMathOperator{\Bin}{Bin}
\DeclareMathOperator{\Geom}{Geom}

\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{starproblem}[problem]{*Problem}
\newtheorem{sstarproblem}[problem]{**Problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\noindent \thetitle \hfill \thedate

\noindent\rule{\textwidth}{.1mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  A $\sigma$-algebra $\cF$ is said to be generated by a partition if there is some partition $\cB = \{B_i\}$ of $\Omega$ so that every set $A\in\cF$ is a union of some parts in the partition, and every such union is in $\cF$.
  \begin{enumerate}
  \item If $\cA\subset 2^\Omega$ is finite, show that the generated $\sigma$-algebra has $|\sigma(\cA)|\leq 2^{2^{|\cA|}}$.
  \item Show that any $\sigma$-algebra on a countable set $\Omega$ is
    generated by a partition of $\Omega$.
  \end{enumerate}
\end{problem}

% your solution here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  Give an example of a measure space $(\Omega,\cF)$ and function $\mu$ on
  $\cF$ that is additive but not $\sigma$-additive, i.e.\ $\mu(\cup
  A_i)=\sum \mu(A_i)$ for a finite collection of disjoint $A_i$, but not for
  some infinite collections.
\end{problem}


%your solution here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  What is the $\sigma$-algebra generated by all singletons $\{x\}$ for
  $\Omega=\R$?
\end{problem}

%your solution here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  Show that the following collections generate the same $\sigma$-algebra (Borel) on $\R$:
  \begin{itemize}
  \item Open intervals: $\{(a,b) : a<b\}$.
  \item Closed intervals: $\{[a,b] : a<b\}$.
  \item Half open intervals: $\{(a,b] : a<b\}$.
  \item Half-lines: $\{[a,\infty) : a\in\R\}$.
  \end{itemize}
\end{problem}

%your solution here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  For a function $f:[0,1]\to\R$, let $C$ be the set of points where $f$ is
  continuous.  Prove that $C$ is in the Borel $\sigma$-algebra.
\end{problem}

%your solution here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  A permutation $\sigma$ is called a \textbf{derangement} if $\forall i, \sigma(i)\neq i$.
  Consider a uniform random permutation $\sigma$ of $\{1,\dots,n\}$, and let $D_n$ be the event that $\sigma$ is a derangement.
  Use the inclusion-exclusion principle to find a formula for the number of derangements, and show that $\P(D_n)\xrightarrow[n\to\infty]{} e^{-1}$.
\end{problem}

%your solution here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
  Consider the space $\Omega=\{0,1\}^\N$ of binary sequences $(\omega_i)$, with the product probability measure $\P$ where $\P(\omega_i=1) = 1/2$.
  Let $R_n$ be the longest consecutive run of 1s in the first $n$ terms.
  For example, if $\omega = (1,0,1,1,1,0,1,1,\dots)$ then $R_4=2$ and $R_8=3$.

  Prove that almost surely $\lim_{n\to\infty} \frac{R_n}{\log_2 n} = 1$.
\end{problem}

%your solution here
\end{document}
