\documentstyle[12pt,amstex,epsf]{article}
\input{macros-course}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

%\newcommand{\pr}{\problem}
%\newcommand{\newgcd}[2]{{\ms{gcd}}(#1, #2)}
%\newcommand{\npg}{}
%\renewcommand{\bparts}{\begin{testproblemparts}}
%\renewcommand{\eparts}{\end{testproblemparts}}

\newcommand\answer[1]{{\bf Answer: {#1}}}
\newcommand{\pr}{\problem}

\newcommand{\E}{\mbox{\bf Ex}}
\renewcommand{\Pr}{\mbox{\bf Pr}}
\newcommand\vari{\mbox{ \bf Var}}
\newcommand\cov{\mbox{Cov}}
\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}

\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

\begin{document}

\handout{oldfinalsol}{Practice Final Solutions}{December 8, 1998}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
%Induction


\problem
\points{8}


Recall the definition of the Fibonacci numbers:

$$
F_n = 
\begin{cases}
0 & \text{if $n=0$}\\
1 & \text{if $n=1$}\\
F_{n-1}+F_{n-2} & \text{if $n > 1$}
\end{cases}
$$

\bparts

\ppart{\bf [2 points]}

Which Fibonacci numbers are even? (I.e., find a necessary and sufficient
condition on $n$ that characterizes when $F_n$ is even).
State a theorem of the form: $F_n$ is even if and only if$\dots$

\answer{}

$F_n$ is even if and only if $3 | n$.

\ppart{\bf [6 points]}

Prove that your answer to part (a) is correct.

\answer{}

There are many ways to proceed.
We will use strong induction on the hypothesis
$P(n) = ``2 |F_n \Leftrightarrow 3|n''$.

{\bf Base case:}  
$P(0)$ is true since $3|0$ and $F_0 = 0$ is even.

{\bf Inductive step:}
We will show that $\forall n \geq 0, 
(P(0)\wedge \ldots \wedge P(n)) \Rightarrow P(n+1)$

In other words, we will assume that $P(k)$ is true for $0 \leq k \leq n$
in order to prove that $P(n+1)$ is true.

There are three cases to consider:

\begin{description}

\item[\underline{Case 1}] $n \equiv 0 \mod 3$.

In this case, $3$ does not divide $n+1$ and so it suffices to show that
$F_{n+1}$ is odd.
If $n=0$, then $P(n+1)$ is true since $F_{n+1} = F_1 = 1$ is odd.
If $n > 0$, then $n \geq 3$ and $F_{n+1} = F_n + F_{n-1}$.
Since $3 | n$, we know that $3$ doesn't divide $(n-1)$.
By the inductive assumption, this means that $F_n$ is even and $F_{n-1}$
is odd. Hence, $F_{n+1}$ is odd, as desired.

\item[\underline{Case 2}] $n \equiv 1 \mod 3$.

In this case 3 does not divide $(n+1)$ and so it suffices to show that
$F_{n+1}$ is odd. Since 3 does not divide $n$ and $3 | (n-1)$,
we know by the inductive assumption that $F_n$ is odd and $F_{n-1}$
is even.
Hence, $F_{n+1}=F_n + F_{n-1}$ is odd, as desired.

\item[\underline{Case 3}] $n \equiv 2 \mod 3$.

In this case, $3 | (n+1)$ and so it suffices to show that $F_{n+1}$ is even.

Since 3 does not divide $n$ or $(n-1)$, we know from the inductive 
assumption that $F_n$ and $F_{n-1}$ are odd.  This means that
$F_{n+1}=F_n + F_{n-1}$ is even, as desired.

\end{description}

This concludes the inductive step of the proof. Hence,
$P(n)$ is true for all $n \geq 0$.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%logic, graphs

\pr
\points{10}

Consider an $n$-player tournament for $n \geq 2$ in which there is a match
between each pair of players.  In each match, there is one winner and one
loser (no ties allowed).  Let $P$ denote the set of players and let 
$W \subseteq P$ denote the subset of players who won the most games 
(I.e., $x \in W$ if $x$ wins $k$ games and no other player wins more 
than $k$ games).
Let $B(x,y)$ be a predicate which is true if and only if
$x$ beats $y$. (Note: $B(x,x)$ is always false).

\bparts

\ppart{\bf [2 points]}

Express the following statement using quantifiers and logical notation.

``For any player $x \in W$ and any other player $z$, either $x$ beats
$z$ or there exists a player $y$ such that $x$ beats $y$ and $y$ beats $z$
(or both)''.

\answer{}

$$
\forall x \in W \text{ }\forall z \in P\text{ }
((x \neq z) \Rightarrow  (B(x,z) \vee \exists y \in P \text{ }
(B(x,y) \wedge B(y,z))))
$$

\ppart{\bf [2 points]}

Write the negation of the preceding statement in logical notation 
without using the negation or complement symbol. Also, do not use the
$\neq$ symbol for this part. (Note: $B(z,x)$ implies $z \neq x$).
You do not need to prove your answer is correct.

\answer{}

$$
\exists x \in W \text{ }\exists z \in P \text{ }(B(z,x) \wedge 
(\forall y \in P \text{ }(B(y,x) \vee B(z,y))))
$$

\ppart{\bf [6 points]}

Prove the statement in part (a).

\answer{}

The proof is by contradiction. Assume for the purposes of contradiction that
the statement in part (a) is not true.
This means that the statement in part (b) is true.
Hence, there exists a player $x \in W$ and a different player $z \in P$
such that $z$ beats $x$ and $\forall y \in P$, $z$ beats $y$ or $y$ beats $x$.

Let $P_x$ denote set of players beaten by $x$, and 
$P_z$ denote set of players beaten by $z$.
Note that $x \not\in P_x$.
Since $\forall y \in P$, $z$ beats $y$ or $y$ beats $x$,
we know that $z$ beats every player in $P_x$.  In addition $z$ beats $x$.

Since $x \not\in P_x$, this means that $|P_z| \geq |P_x|+1$,
which contradicts the assumption that $x \in W$.


%Let $x \in W$.  Let $P_x = \{ y \in P | B(x,y) \}$
%i.e., $P_x$ is the set of players beaten by $x$.
%Note that $|P_x| = k$.

%Let $z \in P$. If $z \in P_x$ then $B(x,z)$, so we are done. 
%If not, we know that $z$ won at most $k$ matches, so he lost
%more than $n-1-k$ matches. Since there are only $n-k-1$ players
%in $P - P_x - \{z\}$, $z$ must have lost at least one match from some player
%in $P_x$, so the theorem is proved.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3

\pr
\points{8}

Find a closed form expression for $T(n)$ in each of the following sums
and recurrences.  In order to save time in calculations, you can express
your answer using $\Theta$ notation.  You do not need to prove your answer.
(In each case $n \in \nat$, but you can ignore the case 
when $n=0$).

\bparts

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = \sum_{i=1}^{n} {2 \over i}
\end{displaymath}

\answer{}

$\Theta(\ln n)$ by the integral method or the formulas given in class.

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = \sum_{i=1}^{n} (i+3)
\end{displaymath}

\answer{}

$\Theta(n^2)$ by the integral method or the formulas given in class. 

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = 
\begin{cases}
1  & \text{if $n \leq 4$}\\
T\left(\floor{{n\over 4}}\right)+T\left(\floor{{n\over 3}}\right)+n^2
&  \text{if $n > 4$}\\
\end{cases}
\end{displaymath}


\answer{}

We will use the Akra-Bazzi formula.

We observe that $p < 1$.

$\Theta \left( n^p\left(1+ \int_1^n {x^2 \over x^{p+1}} dx \right)\right) = 
\Theta \left(  n^p n^{2-p} \right) = \Theta(n^2)$

\ppart{\bf [2 points]}

\begin{displaymath}
T(n) = 
\begin{cases}
1 & \text{if $n \leq 4$}\\
2T\left(\floor{{n\over 4}+ \sqrt{n}}\right)+\sqrt{n}
&  \text{if $n > 4$}\\
\end{cases}
\end{displaymath}

\answer{}

We use the Akra-Bazzi formula. $p$ is the solution to
$2 \left({1 \over 4}\right)^p =  1$, so 
$p = 1/2$

\begin{eqnarray*}
\Theta \left( n^{1/2} + n^{1/2} \int_1^n {\sqrt{x} \over x^{3/2}} \right)
 & =  & \Theta \left( n^{1/2} + n^{1/2} \int_1^n {1 \over x} \right)\\
& = & \Theta ( n^{1/2} +  n^{1/2}\ln n)\\
& = & \Theta (n^{1/2}\ln n) 
\end{eqnarray*}

\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
%Linear recurrence


\pr
\points{6}

Solve the following recurrence for $T(n)$.

$$
T(n+1) = 6T(n) - 9T(n-1) + 2^n
$$

with the initial conditions $T(0) = 1, T(1) = -1$.

\answer{}

A particular solution is of the form $k2^n$.
Plugging in the equation we obtain $k=2$.

The characteristic polynomial $x^2-6x+9$ has a double root at 3.

So the general solution has the form

$a3^n + bn3^n + 2^{n+1}$

We use the initial conditions to solve for $a,b$ to obtain
$a = -1$, $b = -2/3$

So the answer is

$$
T(n) = -3^n -2n 3^{n-1} + 2^{n+1}
$$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
%Counting


\pr
\points{10}

\bparts

\ppart{\bf [5 points]}

Calculate the number of ways the integers from 1 to 9 can be arranged
so that no even integer is in its natural position. (For example 2 is not
in the second position, and so on).
Specify your answer as an integer or as the sum of products of integers.
(You may include factorials in your answer but not binomial coefficients).

\answer{}

Let $A_i$ be the set of ways of arranging the integers such that integer
$i$ {\em is} in it's natural position.

We observe that $|A_i| = 8!$, 
$|A_i \cap A_j| = 7!$, $|A_i \cap A_j \cap A_k| = 6!$, and
$|A_i \cap A_j \cap A_k \cap A_l| = 5!$, for $i,j,k$, and $l$ distinct
integers in $\{1,\ldots,9\}$.

We use inclusion/exclusion to calculate the number of ways to arrange the
integers such that {\em some} even integer is in it's natural position.

$|A_2 \cup A_4 \cup A_6 \cup A_8| = 
{4 \choose 1} 8! - {4 \choose 2} 7! + {4 \choose 3} 6! - 5! =
4 \cdot 8! - 6 \cdot 7! + 4 \cdot 6! - 5!$

So the number of ways of arranging the integers such that none of the 
even integers is in it's natural position is 

$9! - |A_2 \cup A_4 \cup A_6 \cup A_8| = 
9! - 4 \cdot 8! + 6 \cdot 7! - 4 \cdot 6! + 5!$

\ppart{\bf [5 points]}

How many strings are there with $n$ 1's, $2n$ 2's, and $3n$ 3's?
Leave your answer in the form of a ratio of factorials.
You do not need to prove your answer.

\answer{}

${ (6n)! \over n!(2n)!(3n)! }$

by the formula for multinomial coefficients.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
%Graph + prob


\pr
\points{8}

Consider an $n$-node undirected graph $G = (V,E)$.
A simple $k$-cycle $(2 < k \leq n)$ in $G$ is a sequence of distinct
nodes $v_1, v_2, \ldots, v_k$ for which $(v_1,v_2) \in E,
(v_2,v_3) \in E,\ldots,(v_{k-1},v_k) \in E$, and $(v_k,v_1) \in E$.
Note that $v_1, v_2, \ldots, v_k$ is the same cycle as 
$v_2, v_3, \ldots, v_k,v_1$, and so forth.
Also, $v_1,v_2,\ldots,v_k$ is the same cycle as $v_k, \ldots, v_2, v_1$.

\bparts

\ppart{\bf [4 points]}

What is the maximum possible number of distinct $k$-cycles in $G$
(assuming all possible edges are present in $G$)?

({\em Note: for $n=3$ the answer is 1}).

\answer{}

The number of ways of choosing $k$ vertices in some particular order
is ${n! \over (n-k)!}$. Since $v_1, v_2, \ldots, v_k$ is the same cycle as 
$v_2, v_3, \ldots, v_k,v_1$ ($k$ such cycles), and 
$v_1,v_2,\ldots,v_k$ is the same cycle as $v_k, \ldots, v_2, v_1$ 
(2 such cycles), the answer is
${n! \over 2k(n-k)!}$ by the division rule.


\ppart{\bf [4 points]}

Now suppose that $G$ is constructed randomly as follows:
For every pair of nodes $\{v_i,v_j\}$, toss a coin of bias $p$.  
Include the edge $\{v_i,v_j\}$ if the coin comes up heads.
Assume that the coin tosses are mutually independent.
What is the expected number of $k$-cycles in $G$~?
(If you were not able to solve part (a), you may let
$X$ denote the answer to part (a) and express your answer in terms of 
$X$, $k$, and $p$).

\answer{}

Let $I_e$ be the indicator random variable of the event ``edge $e$ appears
on the graph''.

Let $C_k$ be the number of simple $k$-cycles in the graph.

Then 
$$C_k = \sum_{e_1,\ldots,e_k} I_{e_1} \cdot \ldots \cdot I_{e_k}$$

where  $e_1,\ldots,e_k$ runs through all possible simple $k$-cycles.

Taking expectations of the above sum and using linearity of expectation
and the fact that the events 
of edges appearing on the graph are independent, we obtain

$$C_k = \sum_{e_1,\ldots,e_k} \E[I_{e_1}] \cdot \ldots \cdot \E[I_{e_k}]$$

Since $\E[I_e] = p$ for every edge,
$\E[C_k] = Xp^k = {n! p^k \over 2k(n-k)!}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%Counting,exp,var
%Dimitri


\pr
\points{9}


The gambling game Yahtzee is played with five fair, mutually independent
 six-sided dice. In the following questions, you may leave factorials
and binomial coefficients in your answer.

\bparts

\ppart{\bf [3 points]}


The gambling game Yahtzee is played with five fair, mutually independent
 six-sided dice. In the following questions, you may leave factorials
and binomial coefficients in your answer.

\answer{}

There are six choices for the number that occurs five times.
There are $6^5$ possible rolls, so the answer is 
$6 \left({ 1\over 6} \right)^5 = {1 \over 6^4}$

\ppart{\bf [3 points]}

Find the probability of a straight. A {\em straight} is either a throw of
$\{1,2,3,4,5\}$ or $\{2,3,4,5,6\}$. (Note that the dice are unordered -
e.g., any roll which results in one 1, one 2, one 3, one 4, and one 5
counts as a straight).

\answer{}

There are two ways to choose the type of straight, and $5!$ ways of arranging
the numbers on the faces of the dice. Since the total number of resulting
dice throws is $6^5$, the answer is ${2 \cdot 5! \over 6^5}$.

\ppart{\bf [3 points]}

A {\em  full house} is a result in which there is a group of three dice with
the same number, and a group of two dice with the same number
(for example $\{2,2,5,5,5\}$ is full-house). A Yahtzee doesn't count as a full
house. Find the probability of a full house.

\answer{}

There are $6$ ways to choose the triple and $5$ ways to choose the pair
(once the triple is chosen).
There ${5 \choose 2}$ ways to pick the dice that will be assigned to the
pair.

$\Pr(\text{fullhouse}) = {6 \cdot 5 {5 \choose 2} \over 6^5}
= {50 \over 6^4}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8

\pr
\points{12}

Bobo decides to bet one dollar at a casino.  However, he's not sure
what game he wants to play.

\begin{itemize}
\item The probability that Bobo plays poker is 20\%, 
in which case he has a 30\%
chance of winning {\bf \$2}  and a 70\% chance of losing {\bf \$1}.

\item
The probability that Bobo plays blackjack is 20\%, in which case he has a 40\%
chance of winning {\bf \$1} and a 60\% chance of losing {\bf \$1}.

\item
The probability that Bobo plays the slot machines is 60\%,
in which case he has
a 30\% chance of winning {\bf \$1} and an 70\% chance of losing {\bf \$1}.
\end{itemize}

Let $X$ denote Bobo's winnings when he makes one bet according to the
above probabilities.


\bparts

\ppart{\bf [2 points]}

What is $\E[X]$?

\answer{}

If Bobo plays poker his expected winings are $0.3(2)-0.7(1) = -0.1$\\
If Bobo plays blackjack his expected winnings are $0.4(1) - 0.6(1) = -0.2$\\
If Bobo plays the solt machines his expected winnings are $0.3(1) - 0.7(1) = -0.4$\\
Therefore, 
$\E[X] = 0.2(-0.1)+0.2(-0.2)+.6(-0.4) = -0.3$

\ppart{\bf [2 points]}

What is $\E[X^2]$?

\answer{}

If Bobo plays poker $\E[X^2|\text{poker}] = 0.3(4)+0.7(1) = 1.9$\\
If Bobo plays blackjack $\E[X^2|\text{blackjack}] = 0.4(1) + 0.6(1) = 1$\\
If Bobo plays the solt machines $\E[X^2|\text{machines}] = 0.3(1) + 0.7(1) = 1$\\
Therefore, 
$\E[X^2] = 0.2(1.9)+0.2+.6 = 1.18$

\ppart{\bf [4 points]}

What is $\vari[X]$?

$\vari[X] = \E[X^2] - \E[X]^2 = 1.18 - (0.3)^2 = 1.09$



\ppart{\bf [4 points]}

If we know that Bobo won one dollar at the casino, what
is the probability that he played blackjack?


\answer{}

Let $W$ be the event that Bobo won \$1,$B$ be event that
he played blackjack, $P$ be the event he played poker,
 and $M$ the event that he played the slot machines.

%We know that $\Pr(W|B) = 0.4$ and $\Pr(B) = 0.2$.
%The probability that Bobo won \$ 1 is
%$\Pr(W) = \Pr(W|B)\Pr(B) + \Pr(W|M)\Pr(M) = (0.4)(0.2)+(0.3)(0.6) = 0.26$,
%where $M$ is the event that Bobo played on the slot machines.  Note that
%it's impossible for Bobo to win one dollar if he played poker.

From Bayes Law, we know that 

\begin{eqnarray*}
\Pr(B|W) & = & {\Pr(W|B)P(B) \over \Pr(W)}\\
& = & {\Pr(W|B)P(B) \over \Pr(W|B)\Pr(B) + \Pr(W|M)\Pr(M)+\Pr(W|P)\Pr(P)}\\
& = & {(0.4)(0.2) \over (0.4)(0.2)+(0.3)(0.6)+(0)(0.2)}\\
& = & {0.08 \over 0.26}\\
& = & {4 \over 13}
\end{eqnarray*}

Note that $\Pr(W|P) = 0$, since Bobo won precisely one dollar.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Consider the following game, played with a coin that has probability $p$
%of being heads ($0<p<1$) 
%One player flips the coin.  If it is heads, that player wins, otherwise
%the other player flips the coin.  The game continues, with
%the coin changing hands on a tails until one player flips
%a heads and wins. Assume all coin tosses are mutually independent.

%What is the probability that the first player will win?


%\answer{} 

%Let $W = \Pr(\text{first player wins})$

%\begin{eqnarray*}
%W  =  p + ((1-p)^2)W & \Rightarrow & W  =  p + (1 - 2p + p^2)W\\
% & \Rightarrow & W  =  p + W - 2Wp + Wp^2\\
% & \Rightarrow & 0  =  p - 2Wp + Wp^2\\
% & \Rightarrow & 0  =  1 - 2W + Wp\\
% & \Rightarrow & 2W - Wp  =  1\\
% & \Rightarrow & W  =  1/(2-p)
%\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9

\pr
\points{14}

The spider is expecting guests and wants to catch 500 flies for her
dinner.  The expected number of flies caught in the web per hour is $40$.

\bparts

\ppart{\bf [4 points]}
 
What is an upper bound to the probability that the spider will have caught 500
flies in 10 hours?

\answer{}

Using Markov's inequality we obtain
$\Pr(X =(5/4)400) \leq \Pr(X \geq (5/4)400) \leq 4/5$
 
\ppart{\bf [2 points]}

What is a lower bound to the probability that the spider will have to 
wait more than 10 hours to catch 50 flies?

\answer{}

The event that the fly has to wait more than 10 hours to catch 500 flies
is the same as the event that the spider will catch less than 500 flies
in 10 hours.
This is the complement of the event that the spider catches at least 500 flies
in 10 hours,
so by part (a) the answer is $1 - 4/5 = 1/5$.

\ppart{\bf [4 points]}

The spider checks her log and discovers that the standard deviation
for the number of flies caught in an hour is 20.
Find an upper bound on the probability that the spider will catch 500 flies
within 10 hours, using this additional information.

\answer{}

Since the standard deviation for the number of flies caught in one hour is 20, 
the standard deviation for the number of flies caught in 10 hours is 
$\sqrt{(10 \cdot 20^2)} = 20 \sqrt{10}$

Using Chebychev's inequality we obtain
$$
\Pr(X = 500) \leq \Pr(X \geq 400 +  {\sqrt{10} \over 2} \cdot 20\sqrt{10}) 
\leq {1 \over 1+{\sqrt{10} \over 4}^2} = {2 \over 7}
$$

\ppart{\bf [4 points]}

The spider discovers additional interesting information.  
The standard deviation is not 20 after all, but
100 flies pass by her web every hour.  
60 of these flies are quite small and are caught with probability $1/6$ each.
40 of the flies are big and are caught with probability $3/4$ each.
Assume all fly interceptions are mutually independent.
Using this information, find an upper bound on the probability that 
the spider will catch 500 flies within 10 hours.
(Since you don't have a calculator, you may leave $\ln$ and $e$ in 
your answer).

\answer{}

We use the Chernov bound. The expected number 
of flies caught every hour is $(1/6)60+(3/4)40 = 40$,
so the expected number of flies in 10 hours is 400.

$\Pr(X = 500) \leq \Pr(X \geq {5 \over 4} 400) \leq 
e^{-(\ln{5 \over 4} + {4 \over 5} - 1)500} =
e^{-(\ln{5 \over 4} - {1 \over 5})500} = 9.45 \cdot 10^{-6}$

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10

\pr
\points{8}

Six computers $c_1,\ldots,c_6$ are connected in a circle so that
$c_1$ is connected to $c_2$ and $c_6$, $c_2$ is connected to $c_1$ and $c_3$
and so forth.
There is also a seventh computer $c_0$ with direct connections to the other six
computers.  When two computers 
want to communicate the signal is transmitted through the shortest path on the
network.  Ties are resolved in favor of the path that does {\bf not}
pass through $c_0$.  
During each second of time, each computer sends one signal.
Each signal is sent to a randomly selected computer (the source and destination
of any signal are always different).
All random selections are drawn from the uniform distribution,
but there may be dependencies.

\bparts

\ppart{\bf [2 points]}
 
Draw the graph of the network.

\bigskip

\begin{figure}[h]
\centerline{\epsfxsize 3.8in
\epsfbox{network.eps}}
\end{figure}


\ppart{\bf [6 points]}


For each edge, calculate the expected traffic per second
through the edge.
Edges are bidirectional so a signal passing through the edge in either 
direction counts as traffic through the edge.

\answer{}

Consider an internal edge, say $\{c_0,c_1\}$.  This edge is used if computer
$c_0$ wants to communicate with $c_1$, which happens with probability $1/6$,
or if $c_1$ wants to communicate with $c_0$ or $c_4$ which happen with 
probability $2/6$, or if $c_4$ wants to communicate with $c_1$
which happens with probability $1/6$. So the expected total traffic 
through  $\{c_0,c_1\}$ is $2/3$. By symmetry, the expected total traffic
through any inner edge is $2/3$.

Now consider an external edge, say $\{c_1,c_2\}$.  This edge is used
if computer $c_1$ wants to communicate with $c_2$ or $c_3$ (prob. 2/6),
if $c_2$ wants to communicate with $c_1$ or $c_6$ (prob. 2/6), if
$c_3$ wants to communicate with $c_1$ (prob. 1/6), 
and if $c_6$ wants to communicate with $c_2$ (prob. 1/6).
So the expected total traffic 
through  $\{c_1,c_2\}$ is $1$. By symmetry, the expected total traffic
through any external edge is $1$.

Note that since we are using linearity of expectation, the dependencies in 
signals do not affect the analysis.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 12

\pr
\points{7}

A job queue is operating under the following assumptions.

\begin{enumerate}

\item At the start of each minute (beginning at time zero),
a job is removed from the queue for processing ( if the queue is nonempty)
This job is processed during the ensuing 60 seconds.

\item During the course of each minute (in between the times when jobs are
removed from the queue), new jobs can arrive in the queue.
The probability that one new job arrives is $1/2$.  The probability that
two new jobs arrive is $1/4$. The probability that no new jobs arrive
is $1/4$.  The number of job arrivals at each step are mutually independent.

\item The queue overflows if it ever has 10 or more jobs.

\end{enumerate}

Let $R$ be the minute during which the queue first overflows.
(If there are 10 or more jobs in the queue before we start, then
$R = 0$).

Let $J_n = \E[R| \text{$n$ jobs in the spooler before we start}]$.
Set up a recurrence for $J_n$. State special cases and initial conditions.
{\bf Do NOT solve the recurrence}

\answer{}

$J_{10} = 0$, since the queue overflows with 10 jobs.

$J_0 = 1+ {1 \over 4}J_0 + {1 \over 2}J_1 + {1 \over 4}J_2$

for $ 1 \leq n < 10$,

$J_n = 1 + {1 \over 4}J_{n-1} + {1 \over 2}J_n + {1 \over 4}J_{n+1}$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}




