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

\newcommand{\remove}[1]{}

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

\HomeworkStart%
{3} % Homework number
{10} % Week of semester submitted
{1.0} % Version

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

\medskip%
\hrule %
\medskip

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

% \section{Introduction}

\SaveIndent


\begin{questions}[start=7]
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % 7: Lazy choices
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Lazy choices.}%

    Question 17.2 from \cite{mu-pcrpt-17}.

    
    Consider the following variant of the balanced allocation
    paradigm: $n$ balls are placed sequentially in $n$ bins, with the
    bins labeled from $0$ to $n - 1$. Each ball chooses a bin $i$
    uniformly at random, and the ball is placed in the least loaded of
    bins
    \begin{equation*}
        i, \quad
        (i + 1) \bmod n,
        \quad
        (i + 2) \bmod n, \quad \ldots, \quad
        (i + d - 1) \bmod
        n.        
    \end{equation*}
    Argue that, when $d$ is a constant, the maximum load grows as
    $\Theta(\log n/ \log \log n)$. That is, the power of two chocies
     does not yield an $O( \log \log n)$ result in this case.




    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % 8: Parallel choices
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Parallel choices.}

    Question 17.6 from \cite{mu-pcrpt-17}.

    Consider a parallel version of the balanced allocation paradigm in
    which we have $n/k$ rounds, where $k$ new balls arrive in each
    round. Each ball is placed in the least loaded of its $d$ choices,
    where in this setting the load of each bin is the load at the end
    of the previous round. Ties are broken randomly. Note that the $k$
    new balls cannot affect each other’s placement. Give an upper
    bound on the maximum load as a function of $n$, $d$, and $k$.


    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % 9: Tail for geometric variables...
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Birthday with choices.}%

    Question 17.14 from \cite{mu-pcrpt-17}.

    
    The birthday shows that if
    balls are sequentially thrown randomly into $n$ bins, with constant
    probability there will be a collision after $\Theta(\sqrt{n})$  balls are
    thrown.

    \begin{questions}
        \item \points{50} Suppose that balls are placed sequentially, each ball
        has two choices of where to be placed, and a ball will choose
        a bin that avoids a collision if that is possible. Show that
        there are constants $c_1$ and $c_2$ so that after
        $c_1 n^{2/3} - o(n^{2/3})$ balls are thrown no collision has
        occurred with probability at least $1/2$, and after
        $c_2n^{2/3} + o(n^{2/3} )$ balls are thrown at least one
        collision has occurred with probability at least $1/2$.

        \item \points{10} How close can you make the constants $c_1$ and $c_2$?

        \item \points{30} Extend your analysis to more than two
        choices. Specifically, show that if each ball has $k$ choices
        for some constant $k$, there are constants $c_{1,k}$ and
        $c_{2,k}$ so that after $c_{1,k} n^{1-1/k} - o(n6{1-1/k} )$
        balls are thrown no collision has occurred with probability at
        least $1/2$, and after $c_{2,k} n^{1-1/k} + o(n^{1-1/k} )$
        balls are thrown at least one collision has occurred with
        probability at least $1/2$.

        \item \points{10} How close can you make the constants
        $c_{1,k}$ and $c_{2,k}$ ?

    \end{questions}

\end{questions}


\bibliographystyle{alpha} 
\bibliography{refs}

\end{document}


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