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

\examinitials{Review Problems}{May 17, 1995}

\bigskip

\begin{problems}

% Problem 1
\problem (Negative Binomial Distribution) 
Let $p$ be the probablility that a biased coin is heads.
Let random variable $N$ be the number of tosses 
up to and including the $k$th heads. 
\bparts
%       \ppart Describe the associated sample space.
\ppart What is the probability distribution obeyed by $N$?
That is, what is ${\rm Pr}(N=\ell)$?
%\ppart Let random variable $Y$ be the length of the sequence. Compute $E(Y)$.
\ppart Compute $E(N)$.
\eparts

% Problem 2
\problem
Let $X_1, X_2$ be Poisson random variables with parameters $\lambda_1$ and
$\lambda_2$ respectively. 
Show that random variable $X=X_1+X_2$ also obeys a Poisson distribution. 
What is its parameter?

% Problem 3
\problem Suppose a person walks along a straight line at a point
$0$. He walks at a uniform speed of $1$ step per minute.  But at the
end of each minute he is likely to reverse his direction with
probability $1/2$. State your assumptions and bound the probability
that he will be at a spot $100$ steps away from $0$ at the end of $t$
minutes.

% Problem 4
\problem 
If $m$ identical balls are thrown randomly into $n$ identical bins, 
what is the expected number of empty bins?

% Problem 5
\problem
What is the expected number of runs of heads in $n$ (fair) coin flips?
(Hint:  Define an indicator random variable for the event that 
        the $i$th flip ends a run of heads, and use linearity of expectation.)

% Problem 6
\problem
How many $n \times n$ (0-1)-matrices have no all-$0$ columns?

% Problem 7
\problem
In  $400$ rolls of a fair six-sided die, are you more likely to get $220$
even numbers or to get $85$ sixes? Justify your answer.

% Problem 8
\problem
Let $G$ be an undirected graph with $2n$ vertices. Argue carefully that if
$G$ contains no triangles, then $G$ contains at most $n^2$ edges, and that
this bound is tight.

% Problem 9
\problem
Let $X$ be a set of size $n$, and let $S_1,S_2, \cdots, S_b$ be a collection
of (not necessarily distinct) subsets of $X$, all of size $l$. Suppose there
exist integers $t$ and $\lambda$ such that if $Y$ is any subset of $X$ of size
$t$, then $Y \subseteq S_i$ for exactly $\lambda$ of the sets $S_i$. (Of
course, $1 \leq t \leq l$ and $1 \leq \lambda \leq b$.) Suppose that $R$ is a
subset of $X$ of size $k$, for some $k$, where $1 \leq k \leq t$. Argue that
$R$ is a subset of exactly $\displaystyle \lambda { n-k \choose t-k }/
{ l-k \choose t-k }$ of the subsets $S_i$.

% Problem 10
\problem 
Let $T(n) = T(2n/3) + T(n/4) + \sqrt{n}$ and $T(n)$ constant for small $n$.
Is $T(n) = O(\sqrt{n})$? 

(As is often the case, it is helpful to expand the recurrence by drawing 
the tree.)

% Problem 11
\problem
Let $X$ and $Y$ be the outcomes of two independent rolls of a six-sided die.
(An unbiased die with faces labelled $1,2,\ldots,6$ as usual).  Let $Z =
X\cdot2^Y$.  Find $E(Z)$ and ${\rm Var}(Z)$.


\end{problems}

\end{document}


