\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage{amsmath}
\usepackage{url}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\bfzero}{\mbox{{\bf 0}}}

\newif\ifanswer
\answertrue
\ifanswer
\newcommand{\answer}[1]{{\bf Answer:} #1}
\else
\newcommand{\answer}[1]{}
\fi

\ifanswer
\head{CS7880}{Network Algorithms and Analysis}{Spring 2016}{14 February 2016}{2}
\else
\head{CS7880}{Network Algorithms and Analysis}{Spring 2016}{16 February 2016}{3}
\fi

\ifanswer
\begin{center}
\Large{\bf Sample Solution to Problem Set 2}
\end{center}
\else
\begin{center}
\Large{\bf Problem Set 2 (due Tuesday, March 1)}
\end{center}
\fi

\ifanswer
\else
\noindent
{\bf Remarks:} 
\begin{itemize}
\item
Since the background of the students in the class varies, some may
find these problems easy while others may find some problems
challenging.  The main purpose of these problem sets is for you to
learn the course material better by applying ideas learnt in class
and/or exploring related problems.  
\item
Please work on these problems on your own, or in collaboration with
fellow students in class.  Please do not seek out solutions or
solution approaches from the web.  If you need hints, ask the course
instructor.  
\item
Please typeset your solution.  Latex, plain text, pdf, and Word are
all acceptable formats.
\item
  The total points for the problem set is 75, worth 7.5\% of the
  grade.
\end{itemize}
\fi

{\bf Problem 1. (5 + 5 = 10 points) Condition for decoding in gossip
  protocol}

In our study of gossiping using network coding, we considered the
following scenario.  We have a network of $n$ nodes, each having an
$L$-bit message that they want to share with all the other nodes.
Each message $\vec{m_i}$ is an element of ${\cal F}_2^L$.  We studied
a network coding algorithm in which each node broadcast a packet
consisting of two vectors, an $n$-bit vector $\vec{\mu}$ from ${\cal
  F}_2^n$, and an $L$-bit message vector $\vec{m}$ equaling the linear
combination $\sum_i \mu(i) \vec{m_i}$, where $\mu(i)$ represents the
$i$th component of the $\vec{\mu}$ and the sum is the component-wise
addition mod 2.  The particular message vector that a node transmits
is drawn uniformly at random from the subspace spanned by the messages
that it has received thus far.

We further showed the following statement: if $S_v$ denotes the
coefficient vectors received by $v$, and there is no vector in ${\cal
  F}_2^n$ that is orthogonal to the subspace spanned by $S_v$, then
$v$ can decode all of the $n$ original messages.

Let $B_n$ denote the set of $n$ vectors in $F_2^n$:

\[
\{(1,0,0,\ldots,0), (0,1,0,\ldots,0), \ldots, (0,0,\ldots,1)\}.
\]

\begin{itemize}
\item[{\bf (a)}] Prove or disprove: $B_n$ is a basis for $F_2^n$ in
  the sense that every vector in $F_2^n$ can be written as a linear
  combination of vectors in $B_n$.

  \answer{True.  Let $n$ vectors in $B_n$ be denoted $e_i$ through
    $e_n$.  Any vector $v = (v_1, \ldots, v_n)$ is simply $\sum_{1 \le
      i \le n} v_i e_i$.
    }

\item[{\bf (b)}] Show why the following condition is not sufficient
  for decoding: none of the $n$ vectors in $B_n$ is orthogonal to the
  subspace spanned by $S_v$.

  \answer{Let $n$ be even, and $S_v$ be the subspace spanned by the
    singleton set $\{x = (1,1,1,\ldots,1)\}$.  Then $e_i \cdot x$
    equals $1$ for each $i$.  Yet, none of the $n$ messages can be
    decoded.}
\end{itemize}

\answer{ 
}

{\bf Problem 2. (10 + 5 + 15 = 30 points) SIS model on the star network}

Let $S_n$ denote the star graph with $n$ vertices: a root node $0$
with edges to the remaining $n-1$ nodes labeled $1$ through $n-1$.

\begin{itemize}
\item[{\bf (a)}]
  Show that the largest eigenvalue of the adjacency matrix of $S_n$ is
  $\sqrt{n-1}$.

  \answer{By Courant-Fischer, the largest eigenvalue is given by the
    following, where $A$ is the adjacency matrix of $S_n$

    \[
    \max_{x \neq 0} \frac{x^T A x}{x^T x}.
    \]

    For $x = (x_1, \ldots, x_n)$, we have
    \[
    x^T A x = 2x_1(x_2+x_3+\ldots+x_n).
    \]
    We need to maximize this subject to the condition that $\sum_i
    x_i^2 = 1$.  It is easy to see that all $x_i$, for $i > 1$, are
    equal.  So we need to maximize $2(n-1)x_1x_2$ subject to the
    condition that $x_1^2 + (n-1)x_2^2 = 1$.  Setting $x_1^2 = 1 -
    (n-1)x_2^2$, we obtain $2(n-1)x_1x_2 = 2(n-1)\sqrt{1 -
      (n-1)x_2^2}x_2$, which is maximized when $(n-1)x_2^2 = 1 -
    (n-1)x_2^2$, or when $x_2 = 1/\sqrt{2(n-1)}$.  So we obtain $x_1 =
    1/sqrt{2}$ and the largest eigenvalue equal to $\sqrt{n-1}$.
    }
    
\item[{\bf (b)}]
  Show that the edge expansion of $S_n$ is $1$.

  \answer{Consider any cut $(X, \overline{X})$ in $S_n$.  Without loss
    of generality, let $X$ have size at most $n/2$.  If $X$ contains
    the root, then the number of edges from $X$ to $\overline{X}$ is
    $|\overline{X}| \ge |X|$; otherwise, the number of edges from $X$
    is $|X|$.  So the ratio of the number of edges to the size of the
    smaller set of the cut is at least $1$.  And there exists a cut
    (with one side being any leaf node) that has an expansion of
    exactly 1.}
\end{itemize}
    
From the results that we have shown in class it follows that for $S_n$
(i) if the infection rate $\beta < 1/\sqrt{n}$, then the epidemic
die-out occurs in expected $O(\log n)$ time, assuming a recovery rate
of 1 (per unit time); and (ii) if the infection rate $\beta > 1$, then
the epidemic die-out occurs in expected exponential time.

We want to understand what happens when $1/\sqrt{n} \le \beta \le 1$.

\begin{itemize}
\item[{\bf (c)}] In this exercise you need to derive an upper bound on
  the expected epidemic die-out time when $\beta = C/\sqrt{n}$ for a
  constant $C > 1$.

  We will consider a simplified discrete variant of the process.
  Assume that every node is infected at time $0$.  Let $S_j(t)$ be $1$
  if $j$ is infected at $t$, and $0$ otherwise.  Let $H_j(t)$ denote a
  random variable that takes $1$ with probability $1/2$, and $0$
  otherwise (this represents healing of node $j$, if infected).  Let
  $R_j(t)$ denote a random variable that is $1$ with probability
  $\beta$, and $0$ otherwise (this represents receipt of an infection
  from $0$).  Finally, let $T_j(t)$ denote a random variable that is
  $1$ with probability $\beta$, and $0$ otherwise (this represents
  transmitting an infection from $0$).  Define for $0 < j < n$ and $t
  > 0$:

  \[S_j(t+1) = \max\{0,  S_j(t) - H_j(t), S_0(t)R_j(t)\}.\]

  Finally, define for $t > 0$:

  \[S_0(t+1) = \max \{0, S_0(t) - H_0(t), \max_{j > 0} (S_j(t)T_j(t))\}.\]

  Show that in $\tau = O(\log n)$ steps, $S_j(\tau)$ is $0$ for all
  $j$ with probability $1 - 1/n^{\alpha}$ for some constant $\alpha >
  0$.

  \answer{ We provide a sketch of the proof, leaving the details.  We
    will establish that the expected time to die-out is $O(\log n)$,
    as opposed to establishing a high probability bound as mentioned
    above. A high probability bound can be established by a much more
    careful argument in the second phase of the analysis below.

    The first thing to observe is that if the root is infected, the
    expected number of leaves it will infect is at most $C \sqrt{n}$.
    Using a standard Chernoff bound, this number is at most $C(1 +
    \eps) \sqrt{n}$ for any constant $\eps > 0$, with very high
    probability ($1 - e^{-\Omega(\sqrt{n})}$).

    Our second observation is that if $x$ be the number of leaves that
    are infected at the start of a round, then the number of leaves
    that will recover during this round is $x/2$ (ignoring the
    possibility that they will be infected by the root).  Furthermore,
    by a Chernoff bound, the probability that the number of recovered
    leaves is at most $x/4$ is at most $e^{-x/8}$.  Thus, with
    probability at least $1 - e^{-x/8}$, the number of remaining
    infected leaves is at most $3x/4$.

    Putting the above two observations together, we obtain that in a
    sequence of $O(\log n)$ rounds, the number of infected leaves is
    $O(\sqrt{n})$ with probability at least $1 -
    e^{-\Omega(\sqrt{n})}$.  Let us call this the first phase, which
    succeeds with probability at least $1 - e^{-\Omega(\sqrt{n})}$.

    We now reach an interesting second phase of the analysis.  The key
    challenge is that if the root is infected in some round,
    $\Omega(\sqrt{n})$ leaves may be infected the next.  Consequently,
    for the infection to die out, the root should be cured and not be
    infected for a non-trivial period of time, while the number of
    infected leaves gets smaller and smaller.

    Let us suppose first that the root recovers and is remains
    infection-free.  Starting with a state of $L$ infected leaves,
    under the assumption that the root is continually not infected,
    the probability that the number of infected leaves decreases by a
    factor of at least $3/4$ every round until no leaves are infected,
    is at least the following product, where $k$ is the largest
    integer such that $L3^k/4^k > 1$.
    \begin{eqnarray*}
      \prod_{0 \le i \le k} \left(1 - e^{-3^iL/(8\cdot4^i)}\right) &
      \ge & \delta \left(1  - e^{-x/8} - e^{-4x/(3\cdot 8)} - \cdots - e^{-4^i x/(3^i \cdot 8)} + \cdots \right),
    \end{eqnarray*}
    where $x$ is a sufficiently large integer constant, and $\delta$
    is a sufficiently small positive constant, dependent on $x$.  For
    $\delta$ and $L$ suitably chosen, the above bound is at least
    $\gamma$ for some positive constant $\gamma$.

    The above probability was under the assumption that the root
    remains infected.  We now argue that there is a constant
    probability that the root is not infected during the above
    process.

    Let $L$ denote the number of infected leaves in a given round.
    The probability that the root is not infected by any of the leaves
    equals $(1 - C/\sqrt{n})^L \ge e^{-2LC/\sqrt{n}}$, where we use
    the fact that $1 - x \ge e^{-2x}$ for $x > 0$ sufficiently small.
    By the above argument,the probability that the number of infected
    leaves is at most $3L/4$ the following round, and continues to
    decrease by a factor of $3/4$ (assuming the root is not infected)
    is at least $\gamma$.  Since the events of one round are
    independent of the events of subsequent rounds, the probability
    that root never becomes infected during the above process in which
    the number of infected leaves decreases by a factor of at least
    $3/4$ is at least
    \[
    \prod_{0 \le i < k} e^{-2CL3^i/(4^i \sqrt{n})} =  e^{-(CL/sqrt{n})\sum_{0 \le i < k} 3^i/4^i} \ge e^{-8CL/\sqrt{n}},
    \]
    which is at least a positive constant $\eta$ for $L = \Theta(\sqrt{n})$.

    We thus obtain that the probability that once we have a state of
    $L$ infected leaves, the probability that the root recovers and
    then remains infection free, and all the infected leaves recover
    over $O(\log n)$ rounds is at least $\gamma\eta/2$ for positive
    constants $\gamma$ and $\eta$.  This is the probability of success
    of the second phase of the process.

    Let $\nu$ equal the product of $\gamma\eta/2$ and $1 -
    e^{-\Omega(\sqrt{n})}$, the success probabilities of the first two
    phases, each of which run for, say $T = O(\log n)$ rounds.  The
    expected number of rounds before which all nodes are infection
    free is at most
    \[
    T(\nu + 2(1 - \nu)\nu + 3(1 - \nu)^2\nu + \cdots) \le T/\nu = O(\log n). 
    \]
  }
\end{itemize}
  
{\bf Problem 3. (15 + 5 + 15 = 35 points) Myopic routing on a network
  with randomly chosen long-range links}

Consider $n$ nodes labeled $0$ through $n-1$ organized in a ring
network; so every node has exactly two neighbors.  Now suppose each
node has two additional {\em long-range links}, each of which is to a
node in the ring drawn uniformly at random, with replacement.  Let $G$
denote the resulting random graph.  The total number of edges is
exactly $3n$.  (Note that the graph is undirected; even though the
long-range links are selected by each node in a directional manner,
the edges formed are undirected.)

\begin{itemize}
\item[{\bf (a)}] Show that the diameter of $G$ is $O(\log n)$ with
  high probability, i.e., with probability at least $1 - 1/n^c$ for
  some constant $c > 0$, where the hidden constant in the big-Oh
  notation bound for the diameter may depend on $c$.

  \answer{Fix arbitrary nodes $u$ and $v$.  Let $B_u$ (resp., $B_v$)
    denote the set of $2c \log n$ nodes nearest to $u$ (resp., $v$) in
    the ring, for a constant $c$ that will be chosen sufficiently
    large.  For any set $S$ of nodes let $L(S)$ denote the set of
    nodes that are one-hop away from $S$ through the long-range links
    from the nodes in $S$.  We first prove that there exists a
    constant $c' > 0$ such that for any set $S$ of size in $[2c \log
      n, n/c']$, the size of $L(S)$ is at least $3|S|/2$ with
    probability $1 - 1/n^c$.  The event that $|L(S)|$ is smaller than
    $3|S|/2$ implies that all of the $2|S|$ long-range links land in a
    region of size less than $3|S|/2$.  We calculate this probability
    as follows:

    \begin{eqnarray*}
      \binom{n}{3|S|/2} \left(\frac{3|S|}{2n}\right)^{2|S|} & \le & \left(\frac{2en}{3|S|}\right)^{3|S|/2} \cdot \left(\frac{3|S|}{2n}\right)^{2|S|}\\
      & = & \left(\frac{3e^3 |S|}{2n}\right)^{|S|/2}\\
      & \le & \frac{1}{n^c},
    \end{eqnarray*}
    for $2c\log n \le |S| \le n/(3e^3)$; so our claim is true with $c'
    = 3e^3$.  (In the above inequality, we use the inequality
    $\binom{a}{b} \le (ea/b)^b$, for integers $a > b > 0$.)

    Consider the sequence of sets defined as follows.  Let $L_0 =
    B_u$, and $L_i = L(L_{i-1})$ for $i > 0$.  By the above argument,
    there exists $i = O(\log n)$ such that with probability at least
    $1 - O(\log n)/n^c$, $L_i$ exceeds $n/(3e^3)$.

    Since the destination of long-range links are drawn uniformly at
    random from the ring, the set of nodes that constitute $L_i$ is
    drawn at random from the set of all $n$ nodes.  What is the
    probability that $L_i \cap B_v$ is empty?  This is at most
    \[
    \frac{\binom{n-c\log n}{n/(3e^3)}}{\binom{n}{n/(3e^3)}} \le \left(1 - \frac{c\log n}{n}\right)^{n/(3e^3)} \le \frac{1}{n^c},
    \]
    for $c$ chosen to be a sufficiently large constant.

    \junk{
    Let us consider the graph induced by
    directed long-range links.  Let $L_j$ denote the set of nodes
    whose shortest distance in this graph is exactly $j$.  We estimate
    the size of $L_j$ for $j < \lg n - \alpha$ for a constant
    $\alpha$.  Let $L_{\le j}$ denote the set $\cup_{1 \le i \le j}
    L_i$.

    The size of $L_1$ is at least $2$ with probability at least $1 -
    1/n$.  In the following, we will show that for each with
    probability at least $1 - 1/n$, $|L_j| \ge 4 |L_{j-1}|/3$.

    Since $|L_j| \le 2^j$, we have $|L_{\le j}|$ is at most
    $2^{j+1} - 1$.  We estimate $|L_{j+1}|$ by counting how many of
    the long-range neighbors of nodes $L_j$ are outside $L_{\le j}$.
    There are two hurdles in estimating this.  First, we need to bound
    the number of long-range links that land in $L_{\le j}$.  Second,
    some of the links may be to the same node, so we must make sure
    that we are not double-counting.

    We first upper bound the probability that the number of long-range
    neighbors of $L_j$ is at most $5|L_j|/3$ as follows:
    \begin{eqnarray*}
      \binom{n}{5|L_j|/3} \left(\frac{5|L_j|}{3n}\right)^{2|L_j|} & \le & \left(\frac{3en}{5|L_j|}\right)^{5|L_j|/3} \cdot \left(\frac{5|L_j|}{3n}\right)^{2|L_j|}\\
      & = & \left(\frac{3^5 \cdot e^5 \cdot 5 \cdot |L_j|}{n}\right)^{|L_j|/3}\\
      & \le & \left(\frac{1}{2}\right)^{|L_j|/3},
      \end{eqnarray*}
    as long as $|L_j| \le n/(3^5\cdot e^5 \cdot 5)$.
    
    We next upper bound the probability that at least $|L_j|/3$ of the
    $2|L_j|$ long-range links land in $L_{\le j}$, whose size is at
    most $2^{j+1} - 1$.  This probability is at most
    \[
    \binom{2|L_j|}{|L_j|/3} \left(\frac{}{}\right)
    \]

    Thus, with probability at least $1 - O(\lg n/n)$, the size of
    $|L_j|$ for $j = lg n - \alpha$ is at least $n/c$ for some
    constant $c > 0$.  Now, the elements of $L_j$ are drawn uniformly
    at random from the entire ring.  The probability that a set of
    size $n/c$ does not intersect with a neighborhood of size $\beta
    \log n$ around $v$ is at most
    \[
    \frac{\binom{n - \beta \lg n}{n/c}}{\binom{n - \beta \lg n}{n/c}} \le 1/n^{c'}
    \]
    for some constant $c' > 0$, depending on $\beta$.

    We thus obtain that with probability at least $1 - 1/n^{c'}$, the
    shortest-hop distance from $u$ to $v$ is $O(\log n)$.
    }
  }
\end{itemize}

Consider the myopic search algorithm for routing a message from a
source $s$ to destination $t$.  Every intermediate node $u$ forwards
the message to its neighbor $v$ (on the ring or via a long-range edge)
such that $v$ is the node nearest to $t$ along the ring among all
neighbors of $v$, breaking ties arbitrarily; formally, $(v - t) \bmod
n$ is minimum among all neighbors $v$ of $u$.

\begin{itemize}
\item[{\bf (b)}]
  Show that the myopic search algorithm always terminates.

  \answer{ In every step, the distance to the destination decreases by
    at least 1; hence the routing eventually reaches the destination.
    Therefore, the algorithm terminates.

    }
\item[{\bf (c)}] Show that there exist $s$ and $t$ such that the
  expected time for myopic search to complete is $\Omega(\sqrt{n})$.

  \answer{The main point about this exercise is to observe that even
    though any two vertices are within $O(\log n)$ distance in the
    graph, with high probability, the maximum, over all $s$ and $t$,
    of the expected time myopic search takes to go from $s$ to $t$ is
    $\Omega(\sqrt{n})$.

    Let $s$ and $t$ be two diametrically opposite nodes on the ring.
    Consider the following process, starting from $s = v_0$, $i = 0$.
    If $v_i$ is $t$, the process stops; otherwise, we select two
    random nodes $x$ and $y$ chosen uniformly at random from the ring,
    and set $v_{i+1}$ to be the vertex that is closest to $t$ along
    the ring among four vertices: $\{x, y\}$ and the two neighbors of
    $v_i$ on the ring.  If we move to one of $x$ or $y$, we refer to
    this as a {\em long-range step}; otherwise, we refer to this as a
    {\em ring step}.

    We would like to determine how long does the process take before
    it stops.  We claim that with probability at least $1/2$, the
    process takes $\Omega(\sqrt{n})$ rounds.  The selection of the
    random nodes $x$ and $y$ in each step is independent of all other
    selections.  So the probability that in $\sqrt{n}$ rounds, none
    of the long-range steps hit the interval $[t - \sqrt{n}, t + 
      \sqrt{n}]$ is at least
    \[
    \left(1 - \frac{2\sqrt{n}}{n}\right)^{\sqrt{n}} = \left(1 -
    \frac{2}{\sqrt{n}}\right)^{\sqrt{n}} \le \frac{1}{e^2}.
    \]
    The total amount of progress made by the ring steps is at most $
    \sqrt{n}$.  So with probability at least $1 - 1/e^2$, the myopic
    search procedure does not reach $t$ in $\sqrt{n}$ steps.
    Therefore, the expected time for myopic search to complete is
    $\Omega(\sqrt{n})$.}
  \end{itemize}
\end{document}
