\documentstyle[11pt]{article} \newcommand{\ben}{\begin{enumerate}} \newcommand{\een}{\end{enumerate}} \newcommand{\lam}{\lambda} \newcommand{\eps}{\epsilon} \newcommand{\gam}{\gamma} \newcommand{\ah}{\alpha} \newcommand{\del}{\delta} \newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\noi}{\noindent}
\pagestyle{empty}
\begin{document}
\begin{center} \Large\bf{Random Graphs G22.3033-007\\
Assignment 4. Due Monday, February 27,2006}\end{center}
\noi {\tt Note: NO CLASS President's Day, Monday, February 20!!}
\ben
\item
Let $P,Q,R,S$ be uniformly and independently selected from the
unit square. Let $f(\epsilon)$ be the probability that triangles
$PQR$ and $QRS$ both have area less than $\epsilon$. Find the
asymptotics of $f(\epsilon)$ (neglecting constant factors) as
$\epsilon$ approaches zero. [Idea: Look first at the length
$QR$. There is a tricky part - if you get an integral that
looks infinite you are on the right track but you'll have to
fix it.]
\item
Let $X$ be the number of triangles in $G(n,p)$ with $p=c/n$. Find
the asymptotic [$c$ fixed, $n\rightarrow\infty$, in terms of $c$]
values for the expectation and variance of $X$.
\item
Let $X$ be the number of isolated triangles in $G(n,p)$ with $p=c/n$. Find
the asymptotic [$c$ fixed, $n\rightarrow\infty$, in terms of $c$] value
for the expectation of $X$. (A triangle $v,w,u$ is isolated if there are
no other edges including any one of those three vertices.)
\item For $1\leq i\leq n$ let $X_i$ be independent random variables with
$\Pr[X_i=1]=\frac{1}{i}$, $\Pr[X_i=0]=1-\frac{1}{i}$.
Set $Y_n=\sum_{i=1}^n X_i$. Let $\mu_i,\sig_i^2$ equal the mean and variance
of $X_i$ and let $\mu,\sig^2$ denote the mean and variance of $Y_n$.
\ben
\item Find asymptotic formulae of $\mu,\sig^2$.
\item
Use Chebyschev's Inequality to show that for any $\epsilon>0$
\[ \lim_{n\rightarrow\infty} \Pr[|Y_n-E[Y_n]|>\epsilon E[Y_n]] = 0 \]
\item Show that {\em if} $\lam=o(1)$ then
\[ E[e^{\lam (X_i-\mu_i)}] = 1 + \frac{\lam^2}{2}\sig_i^2(1+o(1)) \]
(Hint: For $t\geq 3$ bound $E[(X_i-\mu_i)^t] \leq E[(X_i-\mu_i)^2]$ \\ as
$|X-i-\mu_i|\leq 1$ always.)
\item Deduce that $\ln[E[e^{\lam (Y_n-\mu)}]] \sim \frac{1}{2}\lam^2\sig^2$.
\item Use Chernoff bounds to show that {\em if} $a=o(\sig)$ then
\[ \Pr[Y_n-E[Y_n]>a\sig] < e^{-\frac{a^2}{2} (1+o(1))} \]
\een
\item Let $X_i$, $1\leq i\leq n$, be uniform on $\{1,\ldots,6\}$
(throws of a fair die),
$Y_i=X_i-\frac{7}{2}$ (to move to zero mean)
and $Y=\sum_{i=1}^n Y_i$. Use Chernoff Bounds to give $A$ as
small as possible (include the constant factor!) so that
\ben
\item $\Pr[Y>A] < n^{-1}$
\item $\Pr[Y>A] < n^{-10}$
\item $\Pr[Y>A] < e^{-\sqrt{n}}$
\een
\een
\begin{quote}
I was interviewed in the Israeli Radio for five minutes and I said that more
than 2000 years ago, Euclid proved that there are infinitely many primes.
Immediately the host interrupted me and asked ``Are there still infinitely
many primes?''
\\ Noga Alon
\end{quote}
\end{document}