\documentclass[12pt,letterpaper]{article}
\usepackage{fullpage}
\usepackage[top=2cm, bottom=4.5cm, left=2.5cm, right=2.5cm]{geometry}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd}
\usepackage{lastpage}
\usepackage{ulem}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{graphicx}

\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.05in}
% Edit these as appropriate
\newcommand\course{CSCI 1550 / 2540}
\newcommand\hwnumber{4}             % <-- homework number
\newcommand\Namea{Partner 1}           % <-- Name of partner #1
\newcommand\Nameb{Partner 2}     
\newcommand\Namec{Partner 3}  
\newcommand{\DUEDATE}{April 10th, 2025}
\usepackage{subfiles} % Best loaded last in the preamble

\pagestyle{fancyplain}
\headheight 35pt
\lhead{\Namea \\ \Nameb \\ \Namec}
\chead{\textbf{\Large Homework \hwnumber}}
\rhead{\course \\ March 20th, 2025}
\lfoot{}
\cfoot{}
\rfoot{\small\thepage}
\headsep 1.5em

\begin{document}

\begin{center}
    \vspace{10pt}
    \textit{Due:} \DUEDATE\\
    Remember to show your work for each problem to receive full credit.
\end{center}

\section*{Problem 1 (30 points)} 
\begin{enumerate}
\item  Let $X_1,X_2,\ldots,$ be a sequence of independent exponential
random variables, each with mean $1$.  Given a positive real number $k$,
let $N$ be defined by 
$$N = \min \left \{n: \sum_{i=1}^n X_i > k \right \}.$$
That is, $N$ is the smallest number for which the sum of the first $N$ of the $X_i$ is larger than $k$.  
Use Wald's equation to determine $E[N]$.
\item  Let $X_1,X_2,\ldots,$ be a sequence of independent uniform 
random variables on the interval $(0,1)$.  
Given a positive real number $k$, with $0 < k < 1$,
let $N$ be defined by 
$$N = \min \left \{n: \prod_{i=1}^n X_i < k \right \}.$$
That is, $N$ is the smallest number for which the product of the first $N$ of the $X_i$ is smaller than $k$.  
Determine $E[N]$.
(Hint: Prove that $\log 1/X_i$ has an exponential distribution.)
\end{enumerate}

\newpage

\section*{Problem 2 (40 points)}
A random graph $G_{n,m}$ has $n$ vertices and $m$ edges. The $m$ edges are chosen uniformly at random (without repetition) among all the possible ${ n \choose 2}$ edges. 
Consider a random graph $G_{n,m}$, where $m = cn$ for some constant $c > 0$. 
Let $X$ be the number of isolated vertices (i.e., vertices of degree $0$).

\begin{enumerate}
    \item Compute $E(X)$
    \item For any $\lambda > 0$, show that $\Pr( |X - E(X)| \geq 2\lambda \sqrt{cn}) \leq 2e^{-\lambda^2/2}$
    (\textit{Hint}: Use a martingale that reveals the locations of the edges in the graph, one at a time).
\end{enumerate}

\newpage

\section*{Problem 3 (25 points)}
Consider a random walk on the infinite two dimension integer grid:
$$G=\left \{(x,y)~|~ x\in \{-\infty,\infty\},~y\in \{-\infty,\infty\}\right \}.$$
The random walk starts at $(0,0)$, and if the walk is at $(x_t,y_t)$ at time $t$, then with equal probabilities the walk moves to one of the adjacent nodes $(x_t-1,y_t)$, $(x_t,y_t -1)$, $(x_t+1,y)$, or $(x_t,y_t +1)$. I.e.

\[Pr((x_{t+1},y_{t+1}))~|~(x_t,y_t))= \left \{\begin{array}{ccc} 
1/4 & \mbox{if} & (x_{t+1},y_{t+1}) = (x_t-1,y_t) \\
1/4 & \mbox{if} & (x_{t+1},y_{t+1}) = (x_t+1,y_t) \\
1/4 & \mbox{if} & (x_{t+1},y_{t+1}) = (x_t,y_t-1) \\
1/4 & \mbox{if} & (x_{t+1},y_{t+1}) = (x_t,y_t+1) 
\end{array} \right .
\]

Prove that for $\lambda > 0$
 $$Pr\left (|x_t+y_t|\geq\lambda\sqrt{t}\right)\leq 2e^{-\lambda^2/2}.$$

\newpage

\section*{Problem 4 (25 points)}
Let $f(X_1, X_2, \dots, X_n)$ satisfy the Lipschitz condition so that, for any $i$ and any values $x_1, \dots, x_n$ and $y_i$,
\begin{equation*}
    |f(x_1, \dots, x_{i - 1}, x_i, x_{i + 1}, \dots, x_n) - f(x_1, \dots, x_{i - 1}, y_i, x_{i + 1}, \dots, x_n)| \le c.
\end{equation*}
We set
\begin{equation*}
    Z_0 = \mathbb{E}(f(X_1, \dots, X_n))
\end{equation*}
and
\begin{equation*}
    Z_i = \mathbb{E}(f(X_1, \dots, X_n) \mid X_1, \dots, X_i).
\end{equation*}

Give an example to show that, if the $X_i$ are not independent, then it is possible that $|Z_i - Z_{i - 1}| > c$ for some $i$.

\newpage

\section*{Problem 5 (30 points)}
Consider a bin with $N>1$ balls. The balls are either black or white.
Let $X_0=\frac{m}{N}<1$ be the fraction of black balls in the bin at time $0$. Let $X_i$ be the fraction of black balls at time $i$. At step $i\geq 1$ one ball, chosen uniformly at random, is replace with a new ball. With probability $X_i$ the new ball is black, otherwise it is white. All random choices are independent.

Consider the stopping time $\tau := \inf_i\{X_i \in \{0,1\}\}$. That is, the process stops when all balls have the same color.

\begin{enumerate}[(a)]
    \item Show that $X_1,X_2,\dots$ is a martingale with respect to itself.
    \item Show that $E[\tau] < \infty$.\\
    \textbf{Hint:} Show that at any step there is probability $\geq (\frac{1}{2N})^{N/2}$ to terminate in the next $N/2$ steps. Conclude that $E[\tau]\leq (2N)^{N/2} \cdot N/2$.
    \item Calculate $\mathbb{P}(X_\tau = 1)$
\end{enumerate}
\end{document}