\documentclass{article}
\usepackage{titling}

\title{MATH 418/544, Assignment 1}
\date{Due 2023-10-16, 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{defn}{Definition}
\newtheorem{problem}{Problem}
\newtheorem{starproblem}[problem]{*Problem}
\newtheorem{sstarproblem}[problem]{**Problem}

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

\noindent \thetitle \hfill \thedate

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

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

\begin{problem}
  \begin{enumerate}
  \item Find $n$ events so that any $n-1$ are independent but all together are not.
  \item Show that if these events are in some probability space $\Omega$ then $\Omega$ has at least $2^{n-1}$ points.
  \end{enumerate}
  
\end{problem}

%your solution here

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

\begin{problem}
  \begin{enumerate}
  \item Let $(A_i)_{i\leq n}$ be independent events with probability $1/n$ each.
    Find the probability that exactly $k$ of them occur, and the limit
    as $n\to\infty$.
  \item Consider a random uniform permutation $\sigma\in S_n$.
    What is the probability that it has exactly $k$ fixed points?
    What is the limit as $n\to\infty$?
  \item Is there a direct connection between parts a and b?
  \end{enumerate}
\end{problem}


%your solution here

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

  
\begin{problem}
  Let $A_n$ be independent events with $\P(A_n)\neq 1$ for every $n$.
  Prove that $\P(\cup A_n) = 1$ if and only if $\P(A_n \text{ i.o.}) = 1$.
\end{problem}

%your solution here

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

\begin{defn}
  The $m$-ary tree is a graph with a single vertex on level 0.
  Each vertex on level $k$ has $m$ edges to vertices on level $k+1$, all distinct (so there are $m^k$ vertices on level $k$).
\end{defn}

\begin{problem}
  Consider percolation on the $m$-ary tree, where each edge is open  independently with probability $p$.
  Let $C_0$ be the cluster of the root vertex.
  Prove that if $p<1/m$ then  $\P(|C_0|=\infty) = 0$. \\
  (*) Prove the same also for $p=1/m$.
\end{problem}


\begin{starproblem}
  Construct a graph with $0<p_c<1$ where $\theta(p_c)>0$. Prove your
  claims. (There are many different solutions.)
\end{starproblem}


% your solution here

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

\begin{problem}
  If $X_n$ are independent random variables on some probability space, show
  that $\P(\sum X_n \text{ converges}) \in\{0,1\}$.
\end{problem}

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

\begin{problem}
  Let $X_1,X_2,\dots$ be i.i.d.\ (independent and identically distributed)  random variables with standard exponential distribution:
  \[\P(X_i>t) = e^{-t} \qquad\text{for $t>0$.} \]
  For any $a>0$ compute $\P(X_n>a\log n \text{ i.o.})$.
  Deduce that $\limsup \frac{X_n}{\log n} =  1$ a.s.
\end{problem}


% your solution here

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

\begin{problem}
  Show that for any sequence of random variables $X_n$ there is a sequence of constants $a_n>0$ so that $a_n X_n \to 0$ a.s.
\end{problem}


\end{document}
