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

\begin{document}
\psetnum{1}
\date{2004/02/09}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      We return 1 with probability $p_1$ and 2 with probability $p_2 =
      1-p_1$ by generating successive random bits and comparing them
      to the binary representation of $p_1$. If the $i$th random bit
      differs from the $i$th bit of $p_1$, we stop and return 1 if the
      bit of $p_1$ is greater and 0 if the random bit is greater.

      Because each random bit has probability $\nicefrac12$ of
      differing from the corresponding bit of $p_1$, in expectation
      two random bits are required.
    \end{subproblem}

    \begin{subproblem}
      To sample from $n$ items, we generate a balanced binary tree and
      augment each node with the sum of the weights in its subtree. If
      the weight of the root is $p_r$ and the weights of its children
      are $p_a$ and $p_b$, we first use the algorithm above to return
      the root with probability $\frac{p_r}{p_r + p_a + p_b}$.
      Otherwise, we traverse one of the subtrees. With probability
      $\frac{p_a}{p_a + p_b}$, we choose subtree $a$, and $b$ with
      probability $\frac{p_b}{p_a + p_b}$. We then recursively apply
      this procedure.
      
      The expected runtime is $\bigO{\log n}$ because each at each
      node we perform two calls to the algorithm from part a, which
      requires constant time, and the depth of the tree is $\bigO{\log
        n}$.
    \end{subproblem}

    \begin{subproblem}
      Consider the problem of sampling uniformly from
      $\set{1,2,3}$. Each result occurs with probability
      $\nicefrac13$. In the worst case, it is impossible to generate
      a result with the appropriate distribution with only a finite
      number of random bits. Note that the binary representation of
      $\nicefrac13$ continues infinitely. But if a finite number of
      bytes is used, then the precision of output probability is
      limited: if $n$ bits are used, then the probability of any
      result must be a multiple of $\frac{1}{2^n}$. This precludes the
      correct probability $\nicefrac13$.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      Let $n$ be the size of $S$, and $s$ be the number of elements
      smaller than the pivot $x$. The size of the subset in the
      recursive call is at most $\max \set{s, n-s-1}$. Since the pivot
      is selected uniformly at random, the expectation is
      \[ \frac{1}{n} \sum_{i=0}^{n-1} \max \set{s, n-s-1} =
      \frac{2}{n} \sum_{i = 0}^{\floor {\frac{n-1}{2}}} s
      = \frac{1}{n} \left( \frac{(n-1)^2}{4} +  \frac{n-1}{2} \right)
      = \frac{n}{4} + \frac{3}{4n} < bn \]
      for, e.g. $b = \nicefrac12$ and large $n$.
    \end{subproblem}

    \begin{subproblem}
      Assume for purposes of induction that the expected runtime
      $\Exp{T(\frac{n}{2})} = c\frac{n}{2}$. Then consider solving a
      problem of size $n+1$. This requires comparing the $n$ other
      elements to the randomly-selected pivot, then applying the
      algorithm recursively to one of the two subsets (call it $S_i$):
      \begin{align}
        \Exp{T(n + 1)} &= \Exp{n + T(\abs{S_i})} \\
        \label{eq:linearity-required}
        &= n + \Exp{T(\abs{S_i})} = n + T(\frac{n}{2}) = n +
        c\frac{n}{2} \le cn
      \end{align}
      for $c = 2$.

      The base case is trivial: for a set with small constant size, we
      can simply sort the set and pick the $k$th smallest element in
      constant time.
    \end{subproblem}

    \begin{subproblem}
      Equation~\ref{eq:linearity-required} uses linearity of
      expectation for the fact that $\Exp{n + T(\abs{S_i})} = n +
      T(\frac{n}{2})$. If the recurrence is non-linear, this equality
      does not necessarily hold.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    The MST-based minimum-cut algorithm is precisely equivalent to the
    randomized contraction algorithm. Assume for simplicity that we
    are using Kruskal's MST algorithm. The algorithm repeatedly
    selects the remaining edge with smallest weight --- since the
    weights are random, this selects a random remaining edge. If the
    edge connects two distinct trees in the forest, it adds the edge
    to the minimum spanning tree, or otherwise deletes the edge. Each
    tree in the forest is equivalent to a (meta)vertex in the
    contraction algorithm.  The process of adding an edge between two
    vertices to the MST is equivalent to contracting the two
    vertices, since all other edges between the two trees (internal
    edges in the contracted metavertices) will be discarded and not
    considered later in the procedure.

    The edge with highest weight in the minimum spanning tree is
    necessarily the one that was inserted last; it is therefore
    equivalent to the final remaining edge in the contraction
    procedure. So with probability $\bigOmega{\frac{1}{n^2}}$, the cut
    it produces will be the minimum cut.
  \end{problem}

  \begin{problem}
    As in the analysis of the contraction algorithm, let $k$ be the
    size of the minimum cut. Then every vertex must have degree at
    least $k$, so $m \ge \frac{kn}{2}$. Further let $\varkappa$ be
    the size of the second smallest cut. Every
    vertex must have degree at least $\varkappa$, except possibly for
    the one vertex with smallest degree. Thus, $m \ge
    \frac{\varkappa(n-1)}{2}$.
    
    The remainder of the algorithm proceeds in largely the same way as
    in the minimum-cut analysis. However, we stop when \emph{three}
    vertices remain. The probability of not randomly
    choosing an edge of the second-smallest cut on the $i$th
    step is at least
    \[ 1 - \frac{\varkappa}{\frac{\varkappa((n-i+1)-1)}{2}} = 1
    - \frac{2}{n-i} = \frac{n-i-2}{n-i}\]
    and so the probability of never choosing an edge of the
    second-smallest cut is at least
    \[ \prod_{i = 1}^{n-3} \frac{n-i-2}{n-i} = \prod_{j=3}^{n-1}
    \frac{j-2}{j} = \frac13 \frac24 \frac35 \cdots \frac{n-4}{n-2}
    \frac{n-3}{n-1} = \frac{2}{(n-2)(n-1)}\]

    Once three vertices remain, we choose one of the edges between
    them at random and use it to define the cut. There are at most
    three such edges, so the probability of returning the minimum cut
    is $\frac{2}{3(n-2)(n-1)} = \bigOmega{\frac{1}{n^2}}$.
  \end{problem}
\end{pset}
\end{document}