\documentclass{article}[12pt]

\newtheorem{thm}{Theorem}
\usepackage{hyperref}

\newfont{\bssten}{cmssbx10}

\newcommand{\p}{\ensuremath{\mbox{Pr}}}
\newcommand{\E}{\ensuremath{\mbox{E}}}

%%---------------------------------------------------------------------------
%%      Margins:
%%---------------------------------------------------------------------------
%\oddsidemargin  0in
%\evensidemargin 0in
%\topmargin -0.5in
%\headheight 0.25in
%\headsep 0.25in
%\textwidth   6.5in
%\textheight 9in
%\marginparsep 0pt \marginparwidth 0pt
%\parskip 1.5ex  \parindent 0ex \footskip 20pt



\title{MS\&E 337 Information Networks \\ Autumn '07 \\ Homework \#1 \\
Due Wed. 10/31}
\date{}

\begin{document}

\begin{center}
{\Large \bf MS\&E 337 Information Networks \\ Fall 2007 \\ Homework
\#1 \\ Due Wed. 10/31}
\end{center}
\vspace{3pt}

%\maketitle
\begin{enumerate}
\item Suppose we run the P\'olya urn scheme starting with an urn with $r$ red and $b$ blue balls.  What is the probability that a ball chosen at step $k$ is red?

\item Let $X$ be the number of triangles in the $G(n,p)$ model.  Set $p=c/n$ for constant $c > 0$.
\begin{enumerate}
\item Find $\lim_{n \rightarrow \infty} \E[X]$.
\item Find $\lim_{n \rightarrow \infty} \p[X=0]$.

Hint: use Janson's inequality:
\begin{thm} (Janson's inequality) Let $A_i$, $i \in I$, be subsets of
$\Omega$, $I$ a finite index set. Let $B_i$ be the event $A_i \in R$,
where $R$ is a random subset of $\Omega$.  Let $i \sim j$ denote $i
\neq j$ and $A_i \cap A_j \neq \emptyset$.
Define \[\Delta = \sum_{i\sim j} \p[B_i \wedge B_j],\]
\[M = \prod_{i\in I} \p[\bar B_i]\]
\[\mu = \E[X] = \sum_{i \in I}\p[B_i].\]
Note that $\Delta$ is over all ordered pairs $i \sim j$, so $\Delta/2$
is the sum over unordered pairs.
 Assume $\p[B_i]
\leq \epsilon$ for $i\in I$.  Then
\[M \leq \p[\wedge_{i\in I} \bar B_i] \leq M
\exp\left(\frac{1}{1-\epsilon}\frac{\Delta}{2}\right)\]
\end{thm}

\item (Bonus) A graph $H(V,E)$ is \emph{balanced} if the maximal value of
$|E|/|V|$ among all subgraphs of $H$ is achieved for $H$ and
\emph{strictly balanced} if that ratio is only achieved for $H$.  Let
$H(V,E)$ be a strictly balanced graph with $a$ automorphisms.  \\ \\ Show
that for $p = cn^{-|V|/|E|}$, $c > 0$ constant,
\[\lim_{n \rightarrow \infty} \p[G \in G(n,p) \mbox{ contains no
copy of } H] = \exp({-c^{|E|}/a}).\]



\newpage
\end{enumerate}

\item Consider the following model for a collection of wireless
devices trying to form a network using line-of-sight communications in
an urban environment.  The model is based on a simple abstraction of
the idea that there are $n$ streets running east-west, $n$ avenues
running north-south, and wireless nodes can be placed at intersections
of streets and avenues.  Due to the line-of-sight constraints, any
pair of these wireless nodes can communicate if and only if they are
on the same street or the same avenue.

More concretely, we have an $n \times n$ grid of equally spaced points
in the plane (representing the intersections), and we have $k$
wireless nodes residing at $k$ of the points.  Two nodes can
communicate iff they belong to the same row or column of the grid.
Base on this definition, we define the \emph{communication graph} $G$
on the $k$ nodes, with an edge connecting two nodes if they
communicate.  Note that $G$ may not be connected.

Problem: given the grid as above with $k$ wireless nodes already placed at
points in it, find a polynomial time algorithm that makes $G$ connected by adding the
minimum possible number of wireless nodes to points in the grid.

\item
Look at the internet toplogy network snapshots available at: \\
\url{http://topology.eecs.umich.edu/data.html}. \\ \\
Parse the graph and plot its degree sequence, connected components,
etc. using David Gleich's MatlabBGL software: \\
\url{http://www.stanford.edu/~dgleich/programs/matlab_bgl/}.\\ \\
What do you observe?


\end{enumerate}

\end{document}