\documentstyle[12pt,macpsfig,amssymb]{article}
\input{macros-course}

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

\setcounter{page}{0}

%\newcommand{\pr}{\problem}
\newcommand{\pr}{\newpage\problem}
\renewcommand{\bparts}{\begin{testproblemparts}}
\renewcommand{\eparts}{\end{testproblemparts}}

\begin{document}

\examinitials{Quiz 3}{December 6, 1995}


\begin{closeitemize}
%\item This quiz is open book. 

\item Put your name on the top of each page---the pages of this booklet  
will be separated for grading.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please do not
put part of the answer to one problem on the back of the sheet for
another problem.

\item Do not spend too much time on any problem.  Read them all
through first and attack them in the order that allows you to make the
most progress. If you are unsure about something then state your assumptions.

\item Show your work, as partial credit will be given. Full credit will not be given for unjustified answers. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  {\bf Be neat}.

\item This quiz ends at 9 {\sc p.m.} It contains seven problems.  
You will get 2 points for writing your name and circling your tutorial
TA clearly.

\item GOOD LUCK!
\end{closeitemize}

\bigskip
\bigskip

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
name & 2 & \\& &\\ \hline & &\\
1 &  15 & \\& &\\\hline & &\\
2 &  15 & \\& &\\\hline& &\\
3 &  20 & \\& &\\\hline& &\\
4 &  20 & \\& &\\\hline& &\\
5 &  25 & \\& &\\\hline& &\\
6 &  10 & \\& &\\\hline& &\\
7 &  15 & \\& &\\\hline& &\\
8 &  15 & \\& &\\
\hline
\hline
& &\\
Total & 137 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip

\noindent Please circle your tutorial TA: 
\hspace{.5in} Matt 
\hspace{.5in} Andrew
\hspace{.5in} Jon
\hspace{.5in} Miklos

\bigskip

\noindent
{Name:\underline{\hspace*{2in}}}

\newpage
\begin{problems}

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

\cleardoublepage
\pr  
\points{15}
Suppose I roll three independent standard dice and subtract the smallest value from the largest
value.
\bparts
\ppart 
\points{5}
What is the probability distribution for the resulting difference? (i.e. give the probability of getting the result $k$ for all $k$)
\newpage
\ppart 
\points{5}
What is the mean of the result?
\newpage
\ppart 
\points{5}
What is the variance of the result?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cleardoublepage
\pr 
\points{15}
Suppose I roll ten independent standard dice, and consider the
following three events:
\begin{itemize}
\item the sum of the first six is congruent to $1$ modulo $3$.
\item the sum of the last six is congruent to $1$ modulo $3$.
\item the product of all the dice is a power of two.
\end{itemize}
\bparts
\ppart 
\points{9}
Are these events pairwise independent?  Why, or why not?
\newpage
\ppart 
\points{6}
Are they mutually independent?  Why, or why not?
\eparts

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

\cleardoublepage
\pr  
\points{20}
For some number $k$, there is a bag with $1000 - k$ regular 
nickels and $k$ two-headed nickels.
Experiment X1 consists of pulling a coin out of the bag at
random and flipping it once before putting it back in.
\bparts
\ppart
\points{5}
You perform X1 once. What is the
probability you get 1  head?
\newpage
\ppart
\points{5}
You repeat X1 10 times (i.e. you pull a coin out, flip it and put it
back in, repeating the whole process 10 times). What is the
probability you get 10 heads?
\newpage
\ppart
\points{10}
What is the smallest value of $k$ so that
when you repeat X1 10 times,
the most likely number of heads is $6$? (Justify your answer)
\eparts

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

\cleardoublepage
\pr  
\points{20}
There is a bag with $1000$ nickels, and we assign each one a
heads probability $1/3$ with probability $2/3$, and 
a heads probability $2/3$ with probability $1/3$.
Experiment X2$(k)$ consists of pulling a coin out of the bag at
random and then flipping the same coin $k$ times before putting it
back.
\bparts
\ppart
\points{5}
You perform X2$(10)$. What is the probability you get 10 heads?
\newpage
\ppart
\points{5}
You perform X2$(10)$. Given that you get $10$ heads what is the probability 
that the heads probability of the coin you pulled out is equal to $2/3$?
\newpage
\ppart
\points{10}
You perform X2$(10)$. Given that you get $10$ heads what is the
probability that another $10$ flips with the coin you pulled out will
all come up heads?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cleardoublepage
\pr 
\points{25} 
A space station can tolerate up to $k$ meteor hits in its
lifetime.  Each year there is a probability $p$ that it gets hit by
exactly one meteor and probability $1-p$ that it gets hit by none.
Each year there is also a probability of $q < p$ that each of the current
hits will be repaired, provided that it happened within the last ten
years.  Finally, there is a probability $w$ that a nuclear war will
destroy the entire world, and the space station too, and a probability
$u$ that a UFO will arrive and restore the station to its original condition.
\bparts
\ppart 
\points{10}
What is the probability $P(n)$ that the space-station survives exactly
$n$ years, i.e. the $k$'th meteor hits the space-station in year $n$?
\newpage
%%\ppart 
%%\points{7}
%%What is the expected life of the space-station? (You will get partial
%%credit for a non-closed form solution, but do not waste time
%%evaluating hairy sums.)
\newpage
\ppart
\points{8}
Suppose there are $r$ different types of meteors, and the space station
is only destroyed if it gets hit by all $r$ types within a period of $y$
years.  Assuming UFO's but no risk of a nuclear war, what is the 
expected lifetime of a space station?
\newpage
\ppart
\points{7}
Suppose the probability of a hit in year $m$ is $1/(m+1)$.  What
is the probability that it gets hit sometime in the first $n$
years?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\cleardoublepage
\pr  
\points{10}
Suppose I have an urn with $N$ balls of $n$ different colors.
We draw a ball at random, put it back, and then draw balls
repeatedly until we again get a ball of this first color.
What is the expected number of balls drawn?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cleardoublepage
\pr  
\points{15}
Adam and Eve marry and begin having children.  Each child is a boy
or a girl independently with probability 1/2, and Adam and Eve stop
having children once they have two children of the {\bf same} sex.   Let $c$
be the expected number of children they have.
\bparts
\ppart 
\points{5}
What is the value of $c$?
\iffalse
\newpage
\ppart 
\points{10}
Suppose each child grows up, marries a non-child of Adam and
Eve, and follows the same childbearing process as Adam and Eve.  In
terms of $c$, what is the expected number of Adam and Eve's
grandchildren?  Justify your answer! 
\fi
\newpage
\ppart 
\points{10}
Among the children in a generation, as many children as possible
marry each other and have children according to the same rule.
What is the expected number of descendents in year $n$?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cleardoublepage
\pr  
\points{15}
Recall the hashing problem from tutorial.  
Show that with high probability, the maximum number of items 
hashed to one location is $\Omega(\log n / \log \log n)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
%\cleardoublepage
\pr  
\points{15}
\bparts
\ppart
\points{5}
A pair of dice are repeatedly rolled. What is the probability that a
$6$ will appear before a $7$?
%\newpage
\ppart 
\points{5}
What is the probability of getting exactly $k$ $6$'s in $n$ rolls of a
die given that no $3$ appears?
%\newpage
\ppart 
\points{5}
A pair of dice are rolled and the resulting number $k$ is noted. Then,
a pair of dice are rolled $k$ times and the resulting numbers $X_1,
X_2, \ldots X_k$ are noted. What is $E(\sum_{i=1}^k X_i^2)$?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\cleardoublepage
\pr 
\points{20}
There are two phone companies - AT\&T and MCI. At the start of year
$1$ all the $P$ people in a certain town are customers of AT\&T. Each
year, at year-end, each person switches companies with probability
$\frac13$. Compute the expected number of people that are AT\&T
customers at the beginning of year $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\cleardoublepage
\pr 
\points{20}
\bparts
\ppart
\points{10}
A binary tree is a rooted tree where each node has either $2$ children
or $0$ children. A computer network is structured in the form of a
binary tree with ATM switches at each node. The server is hooked up to
the root and the clients to the leaves. Given that each ATM switch
fails independently with probability $\frac12$ compute the expected
number of clients that maintain their connection to the server.
%\newpage
\ppart
\points{10}
There are $n$ different baseball cards.  Since the baseball cards come
in sealed packets you may assuming that each time you buy a card you
are likely to get any one of the $n$ cards with equal
probability. Given that you buy them one at a time and stop when you
get $n/2$ different ones, what is the expected number of cards you
buy?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\cleardoublepage
\pr 
\points{20}
\bparts
\ppart
\points{10}
There is a bag with $999$ regular nickels and $1$ two-headed
nickel. You pull out a nickel from this bag at random and toss it $10$
times. Each time it comes up heads. What is the probability that this
is the two-headed coin?
%\newpage
\ppart
\points{10}
Prove that the probability that a random string of length
$\Omega(\sqrt{n\ln n})$ over an alphabet of size $n$ has all distinct
letters is $O(n^{-2})$.
\eparts
\fi

\end{problems}

\end{document}









