% -------------------------------------------------------- hw1.tex
%
% --------------------------------------------------------

\newcommand{\remove}[1]{}

\documentclass[12pt]{article}%
\usepackage{rand}%
\usepackage{rand_extra}

\HomeworkStart%
{2} % Homework number
{7} % Week of semester submitted
{1.2} % Version

\SaveIndent%
\HWInstructions{%
   Instructions: As in first homework.}{}{}

\medskip%
\hrule %
\medskip

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

% \section{Introduction}

\SaveIndent


\begin{questions}[start=4]
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % 4: Skip in peace
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Skip in peace.}%

    You are given a set of $n$ elements $e_1, \ldots, e_n$. Consider
    the following randomized algorithm -- in step one, it creates a
    node $n_1$ that stores $e_1$. In the $i$\th step, it creates a
    node $n_i$ (that stores $e_i$), randomly picks a random number
    $\alpha_i \in \IRX{i-1} = \brc{1,2,\ldots, i-1}$, and creates a
    directed edge from $n_i$ to $n_{\alpha_i}$.

    This algorithm computes a random directed tree $T$ with $n$ nodes
    (the tree is a \emph{reverse tree}). Let $L$ be the length of the
    longest path in $\Tree$.

    \begin{questions}
        \item Prove an upper bound on the expected length of $L$.

        \item Prove a lower bound on the expected length of $L$ (it
        should match the bound from (A) up to a constant).

        \item Prove that the bounds above hold with high probability
        on $L$ itself (i.e., not on the expectation). That is your
        upper/lower bound has to hold with probability
        $\geq 1 -1/n^{c}$, where $c \geq 4$.

        (The upper bound is not difficult, the lower bound requires
        some cleverness.)
    \end{questions}



    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % 4: Chernoff is tight
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Chernoff inequality is tight by direct
       calculations.}%


    For this question use only basic argumentation -- do not use
    Stirling's formula, Chernoff inequality or any similar ``heavy''
    machinery. This question is more tedious than hard.
    \begin{questions}
        \item Prove that
        $\ds \sum_{i=0}^{n - k} \binom{2n}{i} \leq \frac{n}{4k^2}
        2^{2n}$.

        Hint: Consider flipping a coin $2n$ times. Write down
        explicitly the probability of this coin to have at most $n-k$
        heads, and use Chebyshev inequality.

        \item Using (A), prove that
        $\Bigg. \binom{2n}{n} \geq 2^{2n}/4 \sqrt{n}$ (which is a
        pretty good estimate).

        \item Prove that
        $\ds \binom{2n}{n + i + 1} = \pth{ 1- \frac{2i+1}{n+i+1}}
        \binom{2n}{n+i}$.

        \item Prove that
        $\ds \binom{2n}{n + i}\leq \exp\pth{ \frac{- i(i-1)}{2n}}
        \binom{2n}{n}$.

        \item Prove that
        $\ds \binom{2n}{n + i} \geq \exp\pth{ -\frac{ 8 i^2}{n}}
        \binom{2n}{n}$.

        \item Using the above, prove that
        $\ds \binom{2n}{n} \leq c \frac{2^{2n}}{\sqrt{n}}$ for some
        constant $c$ (I got $c =0.824...$ but any reasonable constant
        will do).

        \item Using the above, prove that
        \[
            \sum_{i=t\sqrt{n} + 1}^{(t+1)\sqrt{n}} \binom{2n}{n - i}
            \leq c 2^{2n} \exp \pth{-t^2/ 2}.
        \]
        In particular, conclude that when flipping fair coin $2n$
        times, the probability to get less than $n - t\sqrt{n}$ heads
        (for $t$ an integer) is smaller than $c' \exp \pth{-t^2/2}$,
        for some constant $c'$.

        \medskip

        \item Let $X$ be the number of heads in $2n$ coin flips.
        Prove that for any integer $t > 0$ and any $\delta >0$
        sufficiently small, it holds that
        $\Prob{ X < (1- \delta) n} \geq \exp \pth{-c''\delta^2 n }$,
        where $c''$ is some constant. Namely, the Chernoff inequality
        is tight in the worst case.
    \end{questions}


    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % 6: Tail for geometric variables...
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Tail inequality for geometric
       variables.}%

    Let $X_1, \ldots, X_m$ be $m$ independent random variables with
    geometric distribution with probability $p$ (i.e.,
    $\Prob{X_i = j} = (1-p)^{j-1} p$). Let $Y = \sum_{i} X_i$, and let
    $\mu = \Ex{Y} = m/p$. Prove that
    \begin{math}
        \ds \Prob{\bigl. Y \geq (1+\delta) \mu }%
        \leq%
        \exp \pth{ - \frac{ \delta^2}{8} m}.
    \end{math}
    Here $\delta \in (0,1/4)$. (A proof with a different constant than
    $8$ is also fine.)

    Hint: Consider an infinite sequence $B$ of \IID (independent and
    identically distributed) random bits $b_1, b_2, \ldots$, where
    $b_i =1$ with probability $p$.


\end{questions}




\end{document}


%
% hw2.tex - end of file
% --------------------------------------------------------
