\documentstyle[12pt,psfig,epsf]{cmu-art}

\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in
\begin{document}
\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ QUIZ 3 Solutions \hfil Bruce Maggs \hfil April 27, 1998\ \ \ }

\vskip 0.1in
}}}

\newcommand{\problem}[3]{\noindent {\bf #1}. [#2 points] \\ {\small {\it #3}}}

\newcommand{\wisdom}[2]{ }

\wisdom{The easy stuff.}{This part is to test your ability to study 
material that has been pre-digested and labeled as useful or
likely to appear on exams. If you do not do well on this section, your
study habits could use adjustment.}

%
% Questions for the ``Repeat After Me'' section
%


\problem{1}{5}{Suppose that $A$ and $B$ are events in a probability space, and
that $\Pr[A] = 0.5$, $\Pr[B] =0.2$, and $\Pr[A \cup B] = 0.6$.  What
is $\Pr[A \cap B]$?}

\begin{eqnarray*}
\Pr[A \cup B] & = & \Pr[A] + \Pr[B] - \Pr[A \cap B] \\
0.6 & = & 0.5 + 0.2 - \Pr[A \cap B] \\
\Pr[A \cap B] & = & 0.1
\end{eqnarray*}

\problem{2}{5}{Suppose that $X$ is a non-negative integer random variable that
takes on the value $i$ with probability $\Pr[X=i]$.  What is the
definition of $E[X]$, the expectation of $X$?}

$$E[X] = \sum_{i=0}^{\infty} i \Pr[X=i]$$

\problem{3}{5}{Suppose that each of the 112 students in 15-299 is
assigned uniformly and independently at random to one of four
recitation sections.  What is the probability that all six students named
``Pat'' are assigned to the same recitation section?}

Here's one way to answer the question.  The first Pat can be assigned to any recitation 
(probability 1), but the second through sixth Pats must be assigned to the same recitation 
as the first (probability $1/4$ for each).  So the answer is $$\left({1 \over 4}\right)^5$$


\problem{4}{5}{Draw all of the 5-node undirected graphs (with no
self-loops and no multi-edges) that are not planar.}

\centerline{\psfig{figure=k5.eps,height=0.5in}}

The only nonplanar 5-node graph is $K_5$, the complete graph on 5 nodes.  (Why are
there no others?  Removing one edge from $K_5$ results in a planar graph, which contains
every other 5-node graph as a subgraph.)


\problem{5}{5}{Suppose that an $N$-node planar graph is drawn in the plane
(with no edges crossing) with $F$ faces.  How many edges does the
graph have?}

Euler's formula: $$E = N + F - 2$$

%\wisdom{Reading Solutions.}{This section tests your understanding of
%the homework assignments, including your ability to read the
%homework solutions that we hand out.}

\wisdom{Basic Techniques.}{This part will test your ability to apply
techniques for which I have given explicit recipes. If you do not do
well on this section, your study habits could use adjustment.}

\problem{6}{10}{Suppose that $A$ and $B$ are events in a probability space.
Using the fact that $A = (A \cap B) \cup (A \cap \overline{B})$, prove
that $\Pr[A] = \Pr[A | B] \cdot \Pr[B] + \Pr[A | \overline{B}] \cdot
\Pr[\overline{B}]$.}

\begin{eqnarray*}
\Pr[A | B] \cdot \Pr[B] + \Pr[A | \overline{B}] \cdot \Pr[\overline{B}]
& = & {\Pr[A \cap B] \over \Pr[B]} \Pr[B] + {\Pr[A \cap \overline{B}] \over \Pr[\overline{B}]} \Pr[\overline{B}] \\
& = & \Pr[A \cap B] + \Pr[A \cap \overline{B}] \\
& = & \Pr[(A \cap B) \cup (A \cap \overline{B})]  \mbox{ since $A \cap B$ and $A \cap \overline{B}$ are disjoint} \\
& = & \Pr[A]
\end{eqnarray*}

\problem{7}{10}{Suppose that a resident of Pittsburgh chosen at random is
a Steelers fan with probability $0.90$, that a resident chosen at
random is a Penguins fan with probability $0.75$, and that a resident
Steelers fan chosen at random is a Penguins fan with probability
$0.80$.  Now suppose that a resident is chosen at random from among
those that are {\it not\/} Steelers fans.  What is the probability
that such a resident is a Penguins fan?}

Let $P$ represent the event that a resident is a Penguins fan, and $S$ represent the event
that the resident is a Steelers fan.  Then:
 
\begin{eqnarray*}
\Pr[P] & = & \Pr[P | S] \Pr[S] + \Pr[P | \overline{S}] Pr[\overline{S}] \\
\Pr[P | \overline{S}] & = & {\Pr[P] - \Pr[P | S] * \Pr[S] \over Pr[\overline{S}]} \\
& = & {0.75 - 0.80 \cdot 0.90 \over 1 - 0.9} \\
& = & 0.3
\end{eqnarray*}

\problem{8}{10}{Suppose that a fair coin is tossed 100 times.  What is
the expected number of pairs of consecutive flips in which the coin
takes on the same value?}

Define a random variable $X_i$ for each pair of consecutive flips, where $X_i = 1$ if 
flip $i$ and flip $i+1$ are identical (HH or TT), and $X_i=0$ if they are different 
(HT or TH).  Thus the expected value of each $X_i$ is $1/2$.  The number of identical
pairs in the entire sequence is just the sum of the $X_i$ over the entire sequence.  By
linearity of expectation, the expected value of this quantity is just the sum of the
$E[X_i]$.  Since there are 99 consecutive pairs, the expected number of identical
pairs is $$49.5$$  


\wisdom{A Moment's Thought!}
{This section tests your ability to think a little bit more
insightfully. You must give complete explanations of your answers.}

%The {\it degree\/} of a node in a graph is the number of edges
%incident on that node.

\problem{9}{10}{Prove that the average node degree in a finite tree
is less than two.}

For any tree with $n$ nodes and $e$ edges, we must have $n = e + 1$.  The 
sum of the degrees of the nodes is $2e$ (since summing the degrees counts both ends
of each edge).  Thus the average node degree is $2e/n = 2e/(e+1) < 2$.


\problem{10}{15}{Prove that if the maximum degree in a finite tree is
$d$, then the tree must have at least $d$ nodes of degree one.}

Here are two simple proofs for this fact.  The first proof is graphical.  
If the maximum degree in a tree is $d$, there must be some node
with degree $d$.  Each of this node's $d$ outgoing edges is the start of
a path that eventually ends at a leaf, because the tree is finite and acyclic.
Furthermore, leaves reached through different neighbors must be different, 
because the path between two nodes in a tree is unique.  Thus the tree
must have at least $d$ leaves.

The second proof is algebraic.  Suppose the tree has $x$ leaves, one node of 
degree $d$, and $y$ other nodes (degree $\geq 2$), for a total of $x+y+1$ nodes.
Then the sum of node degrees is at least $x + d + 2y$.  From the previous problem, 
we know that the sum of the degrees is $2e$, that $e = (x + 1 + y) - 1 = x+y$.  
Combining all these facts gives

\begin{eqnarray*}
2e & \geq & x+d+2y \\
2(x+y) & \geq & x+d+2y \\
x & \geq & d
\end{eqnarray*}



\problem{11}{20}{Suppose that an $n$-node random undirected graph is
formed as follows.  For each pair of distinct vertices $u$ and $v$,
the edge $\{u,v\}$ is present with probability $p$ and not present
with probability $1-p$, independent of whether any other edge is or is
not in the graph.  What should the probability $p$ be set to so that
the expected number of cliques of size $k$ is one?}

First we compute the expected number of cliques of size $k$, then solve for $p$.

The strategy for computing the expected number of cliques is identical to 
problem 8 (identical pairs of coin flips): linearity of expectation.  
Define an indicator random variable for every possible $k$-clique.  Every $k$-subset
of the $n$ nodes is a possible $k$-clique, so there are ${n \choose k}$ such random variables.
The random variable for a particular $k$-clique is 1 if the $k$-clique is found in the graph
and 0 if not, so its expected value is just the probability that a particular $k$-clique
occurs in the graph.  This happens if and only if all $k$ nodes are connected by edges; there
are ${k \choose 2}$ such edges, so the probability of a particular $k$-clique is $p^{k \choose 2}$.
Summing the expected values of all the $k$-cliques gives the expected number of $k$-cliques:
$${n \choose k} p^{k \choose 2}$$

Setting this quantity to 1 and solving for $p$ gives:
$$p = \left({1 \over {n \choose k}}\right)^{\left({1 \over {k \choose 2}}\right)}$$

\end{document}
