\documentclass{article}
\input{6856-preamble}

\begin{document}
\psetnum{3}
\date{2005/02/23}
\collab{Collaborators: \{\texttt{sarahl,gpickard}\}}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      Let $X_i$ be independent geometrically distributed random
      variables with mean 2. Thus $X_i$ is the number of flips of an
      unbiased coin until the first heads. We can view these sequences
      of coin flips as being performed in sequence, and since the $n$
      geometric random variables are independent and each performs
      coin flips until it reaches a heads, we can consider this to be
      a sequence of flips of a single coin, and $X_i$ to be the number
      of coin flips between the $i$th and $i-1$th head. Thus $X =
      \sum_{i=1}^n X_i$ is the number of coin flips performed before
      the $n$th head. We can express this as sum of Bernoulli random
      variables $Y_i$, where $Y_i$ is simply the outcome from the
      $i$th single coin flip. The probability that $X$ is greater than
      some $x$ is the probability that more than $x$ flips are
      required to find $n$ heads, which is the probability that
      $\sum_{i=1}^x Y_i$ is less than $n$. In particular, we want to
      consider $x = (1+\epsilon)\mu_X = (1+\epsilon)2n$. Write $Y =
      \sum_{i=1}^{(1+\epsilon)2n} Y_i$. Then $\Exp{Y} =
      (1+\epsilon)n$, and 
      \begin{align*}
        \Pr{X > (1+\epsilon)2n} &= \Pr{Y < n} \\
        &= \Pr{Y < \frac{n}{1+\epsilon} \Exp{Y}} \\
        &= \Pr{Y < \left(1 + \frac{-\epsilon}{1+\epsilon}
        \right)\Exp{Y}} \\
        &\le e^{-\frac{\epsilon^2 (1+\epsilon)n}{2(1+\epsilon)^2}} =
        e^{-\frac{\epsilon^2 n}{2(1+\epsilon)}}
      \end{align*}
      since $Y$ is a sum of Bernoulli random variables and hence the
      Chernoff bound applies. 
    \end{subproblem}

    \begin{subproblem}
      As in the Chernoff bound analysis, we note that the desired
      probability is equivalent to $\Pr{e^{tX} >
        e^{t(1+\epsilon)2n}}$. By the Markov bound, this is less than
      $\frac{\Exp{e^{tX}}}{e^{t(1+\epsilon)2n}}$. Because $X$ is the
      sum of independent $X_i$s, the expectation is $\prod_i
      \Exp{e^{tX_i}}$. Now note that
      \begin{align*}
        \Exp{e^{tX_i}} &= \sum_{j=1}^\infty e^{tj} \frac{1}{2}^{j} =
        \sum_{j=1}^\infty \left(\frac{e^t}{2}\right)^j \\
        &= \frac{\frac{e^t}{2}}{1 - \frac{e^t}{2}} = \frac{2e^t}{2 -
          e^t}
      \end{align*}
      assuming $t < \ln 2$ so that the series converges. So
      \begin{align*}
        \Pr{X > (1 + \epsilon)2n} &\le \frac{\left(\frac{2e^t}{2 -
        e^t}\right)^n}{e^{t(1+\epsilon)2n}} = \frac{1}{\left((2-e^t)
        e^{t+2t\epsilon} \right)^n}
      \end{align*}
      
      The TI-89 does not flinch in fear at this equation (like I do)
      and tells us that the derivative is equal to zero at $t = \ln
      \frac{2\epsilon +1}{\epsilon + 1}$. Thus this is the minimum. So
      \begin{align*}
        \Pr{X > (1 + \epsilon)2n} &\le
        \frac{1}{\left(\left(2-\frac{2\epsilon +1}{\epsilon + 1}\right)
            \left(\frac{2\epsilon +1}{\epsilon +
                1}\right)^{(1+2\epsilon)} \right)^n} \\
        &= \frac{(\epsilon + 1 )^n}{\left(\frac{2\epsilon +1}{\epsilon +
                1}\right)^{(1+2\epsilon)n}} \\
          &= \frac{\left(\epsilon + 1\right)^{2n\epsilon}}
          {\left(2\epsilon +1\right)^{(1+2\epsilon)n}}
      \end{align*}
      By choosing $\epsilon$ sufficiently large, we can make this
      quantity arbitrarily small.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    Define a pivoting round to be ``good'' for a given item $x$ if $x$
    is in a subproblem with size at most $\nicefrac{9}{10}$ of the
    problem from which it was partitioned. So each ``good'' round
    reduces the size of the problem by $\nicefrac{9}{10}$. Thus for
    any $x$, $x$ will not be involved in more than
    $\log_{\nicefrac{10}{9}} n$ good rounds, because this would reduce
    the size of a subproblem below 1.

    For any subproblem of size $m$ and any element $x$, the partition
    is a good pivoting round for $x$ with probability at least
    $\frac{1}{2}$, since the pivot is chosen uniformly at random.
    Suppose $x$ has rank $r$ among the $m$ elements. Assume without
    loss of generality that $r \le \frac{m}{2}$ (if not, simply
    reverse the order of the ranking). Let $p$ be the rank of the
    pivot. If $r < p \le \nicefrac{9}{10}$ or $\nicefrac{1}{10} \le p
    < r$, then this is a good pivoting round. This occurs with
    probability at least $\nicefrac{1}{2}$. Moreover, the probability
    of any given pivoting round being good is independently above
    $\frac{1}{2}$ since they depend only on the relative rankings of
    the elements in the subproblem.

    Let $f(n) = k \log_{\nicefrac{10}{9}} n$. If $f(n)$ partitions are
    performed, then the expected number of good pivots is $\frac{k}{2}
    \log_{\nicefrac{10}{9}} n$. Moreover, by the independence, we can
    apply the Chernoff bound and find that the number of good pivots
    is less than $(1-\epsilon) \frac{k}{2} \log_{\nicefrac{10}{9}}$
    with probability $e^{\frac{-\epsilon^2\frac{k}{2}
        \log_{\nicefrac{10}{9}} n}{2}}$ = $e^{\frac{-\epsilon^2 k
        \log_{\nicefrac{10}{9}} n}{4}}$. So the probability of having
    more than $\frac{k}{4} \log_{\nicefrac{10}{9}} n$ good pivots
    ($\epsilon = \nicefrac12$) is at least $e^{\frac{- k
        \log_{\nicefrac{10}{9}} n}{16}}$. If we choose $k = 16$, then
    the probability of having at least $4 \log_{\nicefrac{10}{9}} n$
    is at least $e^{-\log_{\nicefrac{10}{9}} n} =
    \left(\frac{1}{n}\right)^{\frac{1}{\log \frac{10}{9}}} \approx
    \frac{1}{x^{9.49}}$.

    Thus, with high probability, a sequence of $16
    \log_{\nicefrac{10}{9}} n = \bigTheta{\log n}$ pivots gives at
    least $4 \log_{\nicefrac{10}{9}} n$ good pivots for any $x$, which
    we showed was enough to reduce the size of a subproblem below 1,
    and end the algorithm. So the algorithm has runtime $\bigO{n \log
    n}$ with high probability.
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      Consider the transpose permutation, mapping $a_i b_i$ to $b_i
      a_i$. We assume that the bit-fixing algorithm fixes bits from
      left to right. So if we fix some $b$, for all $a_i$, $a_i b$
      will be converted to $bb$ at some point in the process of being
      routed to $ba_i$. If the leftmost bit of $a_i$ (call it
      $a_1^0$) differs from the corresponding bit of $b$ (call it
      $b^0$ and the remainder $b^{1..\frac{n}{2}}$), then the
      $\nicefrac{n}{2}+1$th bit will be fixed and it will be
      routed through the link from $bb$ to
      $ba^0b^{1..\frac{n}{2}}$. There are $2^{\nicefrac{n}{2}}$
      choices for $a_i$ in $a_i b$, and exactly half of these will
      have bit $a_i^0$ differing from bit $b^0$. So
      $\frac{2^{\nicefrac{n}{2}}}{2} = \bigOmega{\sqrt{N}}$ packets
      are routed through this edge, and so $\bigOmega{\sqrt{N}}$
      routing steps are required.
    \end{subproblem}

    \begin{subproblem}
      Consider the transpose permutation again, mapping $a_i b_i$ to
      $b_i a_i$, and again fix some $b$. Now, however, the bits are
      fixed in random order, so it is not guaranteed that $a_i b$ will
      be converted to $bb$. Suppose $a_i$ differs from $b$ at $k$
      bits. Then it will be converted to $bb$ if all of the $k$ bits
      in the $a_i$ half are fixed before the $k$ bits in the $b$ half.
      The probability of this is the probability that the first $k$
      bits chosen to be fixed from the $2k$ bits that differ are the
      $k$ in the first half, i.e. $\frac{1}{\binom{2k}{k}}$. The
      number of bit strings that end in $b$ and begin with some $a_i$
      that has $k$ bits differing from $b$ is
      $\binom{\nicefrac{n}{2}}{k}$ since we choose the $k$ bits that
      differ from the $\nicefrac{n}{2}$ bits in $a_i$. Thus, combining
      these and applying the inequality, the expected number of
      packets that route through $bb$ is
      \[ \sum_{k=1}^{\nicefrac{n}{2}}
      \frac{\binom{\frac{n}{2}}{k}}{\binom{2k}{k}} \ge \sum_{k=1}^{\nicefrac{n}{2}}
      \frac{\left(\frac{\frac{n}{2}}{k}\right)^k}{\left(\frac{2ek}{k}\right)^k}
      = \sum_{k=1}^{\nicefrac{n}{2}} \left(\frac{n}{4ek}\right)^k \]

      The value of the sum is certainly bounded below by any of its terms, so
      consider the term with $k  = \ceil{\frac{n}{8e}}$. This reduces
      to $2^{\ceil{\frac{n}{8e}}}$ (to a constant factor), which is
      $2^{\bigOmega{n}}$. Since this is the expected number of packets
      that pass through $b b$, the routing algorithm must require this
      many steps in expectation.

      Since the expectation is $2^{\bigOmega{n}}$, and this can be
      represented as the sum of Bernoulli random variables that
      indicate whether the $i$th packet has its bits flipped in the
      order that forces it to go through $bb$, we can apply the
      Chernoff bound. This tells us that the probability that the
      number of steps required deviates from its mean is small, and
      gives us a bound of $2^{\bigOmega{n}}$ with high probability.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      Let $X_k$ that bin 1 contains $k$ balls. It is given by the
      binomial distribution:
      \[ \Pr{X_k} = \binom{n}{k} \left(\frac{1}{n}\right)^k \left(1 -
        \frac{1}{n}\right)^{n-k} \]
      which is bounded below by
      \begin{align*}
        \Pr{X_k} &\ge \left(\frac{n}{k}\right)^k \left(\frac{1}{n}\right)^k
      \left(\frac{n-1}{n}\right)^{n}\\
      &\ge \frac{1}{k^k}\left(\frac{1}{2}\right)^n
      \end{align*}
      We want this probability to be at least
      $\frac{1}{\sqrt{n}}$. This gives us the constraint:
      \begin{align*}
        \Pr{X^k} \ge \frac{1}{k^k}\left(\frac{1}{2}\right)^n & \ge
        \frac{1}{\sqrt{n}} \\
        k^k & \le \sqrt{n} \\
        2 k \log k \log n &\le \frac{1}{2} \log n \\
        k \log k &\le \frac{3}{4} \log n
      \end{align*}
      Setting $k = \alpha \frac{\log n}{\log \log n}$,
      \begin{align*}
        \alpha \frac{\log n}{\log \log n} \log \left(\alpha \frac{\log
            n}{\log \log n}\right) &\le \frac{3}{4} \log n \\
        \alpha \frac{1}{\log \log n} \left(\log \alpha + \log \log n -
        \log \log \log n\right) &\le
        \frac{3}{4} \\
        \frac{\alpha \log \alpha}{\log \log n} + \alpha \le
        \frac{3}{4}
      \end{align*}
      For large $n$ (greater than $e^e$), $\log \log n$ is greater
      than 1, so ignoring the denominator only strengthens the
      constraint. Thus we simply need to choose $\alpha$ small enough
      that $\alpha \log \alpha + \alpha \le \nicefrac34$. Note that
      $k$ is still $\bigOmega{\frac{\log n}{\log \log n}}$. We have
      shown that the probability that bin 1 contains exactly $k$ balls
      is at least $\frac{1}{\sqrt{n}}$, so this is certainly a bound
      on the probability of it having at least $k$ balls.

      The probability that bin 1 contains at least $k$ balls is at
      least $\frac{1}{\sqrt{n}}$, and for each $i$, the probability
      that bin $i$ contains at least $k$ balls given that bins $1$
      through $i-1$ did not is the same. So the total probability is
      bounded below by the finite geometric series
      \[ \sum_{i = 0}^{n-1} \frac{1}{\sqrt{n}} \left(1 -
        \frac{1}{\sqrt{n}}\right)^i = \frac{1}{\sqrt{n}}
      \frac{1 - \left(1 -\frac{1}{\sqrt{n}}\right)^n}{\frac{1}{\sqrt{n}}} =
      \frac{1}{n} = 1 - \left(1 -\frac{1}{\sqrt{n}}\right)^n \]
    which can be made arbitrarily close to 1 for large $n$. 
    \end{subproblem}

    \begin{subproblem}
      The previous analysis for bin 1 does not depend on the number of
      balls in the other bins. If it is known that bin 1 contains less
      than $k$ balls, then this increases the probability that balls
      will be assigned to some other bin $x$. If $k-1$ balls are already in bin
      1, then no subsequent balls will be placed in bin 1, so the
      probability that any particular one will be placed in bin $x$
      increases from $\frac{1}{n}$ to $\frac{1}{n-1}$. This only
      increases the probability that bin $x$ will contain more balls,
      which improves the probability that it will contain at least $k$
      balls. So any bin contains at least $k$ balls with probability
      at least $\frac{1}{\sqrt{n}}$. 
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      If there are $\alpha n$ balls at the beginning of a round, this
      is the problem of placing $\alpha n$ balls randomly in $n$
      bins. As the $i$th ball is added, there are at most $i-1$
      non-empty bins (if all balls previously went to empty
      bins; if there were earlier collisions than there are less). So
      the probability of the $i$th ball landing in a previously occupied bin
      is bounded above by $\frac{i-1}{n}$. By linearity of
      expectation, the expected number of balls landing in previously
      occupied bins is
      \[\sum_{i = 1}^{\alpha n} \frac{i-1}{n} =
      \frac{1}{n}\left(\sum_{i=1}^{\alpha n} i - \sum_{i=1}^{\alpha n}
        1\right) = \frac{1}{n}\left(\frac{(\alpha n)(\alpha n +1)}{2}
        - \alpha n\right) = \frac{\alpha n(\alpha n - 1)}{2n} =
        \frac{\alpha^2n - \alpha}{2} < \frac{\alpha^2 n}{2} \]

      This probability is a sum of indicator random variables
      indicating whether the $i$th ball is placed in a previously
      occupied bin; thus, the Chernoff bound applies. By the
      Chernoff bound, the probability that the number of balls
      remaining is more than $\frac{2}{1.9}$ times the expectation,
      or $\frac{\alpha^2}{1.9}$, is $e^{-\frac{\frac{\alpha^2 n}{2}
          \left(\frac{2}{1.9}\right)^2}{2}}$, so at most
      $\frac{\alpha^2}{1.9}$ balls remain with high probability.
    \end{subproblem}

    \begin{subproblem}
      We begin with $n$ balls, i.e. $\alpha = 1$. At each stage, we
      have the recurrence
      \[ T(\alpha n) = 1 + T\left(\frac{\alpha^2 n}{1.9}\right) \]

      Define $\alpha_1$ to be 1 and $\alpha_n =
      \frac{\alpha_{n-1}^2}{2}$. Then the recurrence is
      \[T(\alpha_i n) = 1 + T(\alpha_{i+1} n)\]

      This recurrence continues until an $i$ such that $\alpha_i <
      \frac{1}{n}$, at which point with high probability no balls
      remain. Taking the log of the recurrence for $\alpha_n$, we find
      that $\log \alpha_n = \log \frac{\alpha_{n-1}^2}{2} = 2 \log
      \alpha_{n-1} - \log 2 \le 2 \log \alpha_{n-1}$. The recurrence
      until $\log \alpha_i \le - \log n$. Changing variables to
      $\beta_i = \log \alpha_i$ and $m = \log n$, we have $\beta_i \le
      2 \beta_{i-1}$, a simple exponential recurrence that terminates
      once $\beta_i$ reaches $m$. So the solution in terms of $m$ is
      $\bigO{\log m} = \bigO{\log \log n}$.
    \end{subproblem}
  \end{problem}
\end{pset}
\end{document}
