\documentstyle[12pt,twoside,amssymb]{article}

\input{/a/class/6.042/fall94/handouts/macros-course}
%	\addtolength{\topmargin}{-.3in}
%	\setlength{\textheight}{9in}

\newcommand\npage{\bigskip}
%\newcommand\npage{\npage}
%\setcounter{page}{0}

\newcommand\tfitem{\item [{\bf T / F \hspace*{.1in} }]}
\renewcommand{\theproblem}{Problem \arabic{problemnum}}

\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\vari[1]{\mbox{Var}(\, #1 \,)}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}



\begin{document}

\handout{prac-exam}{Final exam information and practice problems}{December 13, 1994}

\noindent
{\bf When:} Tuesday, December 20, 9:00--12:00.

\bigskip \noindent  {\bf Where:} 4--370.

\bigskip \noindent 
{\bf Crib sheet:} The final is {\em closed book}.  
You may, however, bring {\em two handwritten \/}
$8\frac{1}{2}'' \times 11''$ sheets of paper as crib sheets.  
Preparing a crib sheet can be a useful study aid, so
take time in selecting material for it. You may use both sides of the
paper and write as small as you like, but in any case, you are allowed
only two sheets.  

\bigskip  \noindent 
{\bf Material covered:} 
The final exam will cover material from the entire semester.
Roughly one-third will cover material through Quiz~1, 
one-third will cover material through Quiz~2,
and one-third will cover material since Quiz~2.

\bigskip \noindent
{\bf Review:} 
The TA's will generously be available for help and review on Sunday from 
2:00--4:00 {\sc p.m.}, here in 6--120.
Of course, you are always welcome to contact any of the TA's for help.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent
\mbox{}\hrulefill\mbox{}

\begin{center}
{\Large \bf Practice problems}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem
If you roll five fair, (mutually) independent dice, what is the
probability of getting a full house (two dice with one value and
three dice with a different value)?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
True or false.\\
Let $p,r,s$ and $t$ be functions from $\nat$ to $\reals$.
\begin{itemize}
\setlength\itemindent{.5in}
\tfitem  $2^{\lg^2 n}$ is $\Theta(n^2)$.
\tfitem  $p(n) = 10(\frac{1}{5} + \frac{1}{5^2} + \cdots + \frac{1}{5^n})$
	 is $O(1)$.
\tfitem  If $t(n)$ is $\omega(1)$ and $p(n)$ is $O(1)$, 
	  then $t(n) + p(n) \sim t(n)$.
\tfitem  If $p(n)=5$ then $p(n)$ is $O(1)$.
\tfitem If $p(n) \sim s(n)$ and $t(n) = o(1)$, then $p(n) \sim s(n)+t(n)$.
\tfitem If $p(n)$ is $O\left( s(n)t(n) \right)$ then $p(n)$ is $O(s(n))$
	and $O(t(n))$.
\tfitem  $p(n)=2n$ is a bijection between $\nat$ and $2\nat$	
		(the even natural numbers).
%\tfitem  If $f\circ g$ is the identity function, then $f$ maps $A$ onto $B$.
\tfitem  $p(n) = \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2n}$
		is $\sim \ln(\sqrt{n})$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Suppose $p_1, p_2, \ldots, p_5$ are any five points in the interior of 
the unit square in the plane, and let $d_{ij}$ denote the (Euclidean) distance
between $p_i$ and $p_j$.  Prove that there exist $p_i$ and $p_j$ such
that $d_{ij} < \sqrt{2}/2$.  [Use the pigeonhole principle.]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Prove that
\[
{1\over\sqrt{1}} + {1\over\sqrt{2}} + {1\over\sqrt{3}} + \cdots + 
	{1\over\sqrt{n}}
 > \sqrt{n} \mbox{\hspace*{.3in} for $n=2,3,4,\ldots$}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Give asymptotic upper bounds for $T(n)$ in each of the following recurrences.
Assume that $T(n)$ is constant for $n\leq 2$.
Make your bounds as tight as possible.
\begin{problemparts}
\problempart
$T(n) = 2 T(n/2) + n^3$
\problempart
$T(n) = T(9n/10) + n$
\problempart
$T(n) = 16 T(n/4) + n^2$
\problempart
$T(n) = 7 T(n/3) + n^2$
\problempart
$T(n) = 7 T(n/2) + n^2$
\problempart
$T(n) = 2 T(n/4) + \sqrt{n}$
\problempart
$T(n) = T(n-1) + n$
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem
{\bf Communication complexity.}
You and I are each given a string of $n$ bits---I get $x\in\{0,1\}^n$
and you get $y\in\{0,1\}^n$.
Neither of us knows the other's string, but we know that they are different,
$x\neq y$.
We must determine a position in which our strings differ---a bit $i$, 
$1\leq i\leq n$, such that $x_i \neq y_i$.
We communicate by sending one-bit messages back and forth
according to some algorithm, and we would like to minimize the total number
of bits sent in the worst case.  At the end of the algorithm, both of us must 
agree on a position in which our strings differ.
For example, a simple
algorithm would be for me simply to send my whole string, and for you
to tell me the answer ($i$).  This requires exactly $n+\lg n$ bits.
%	$n$ for my message and $\lg n$ for yours.

In fact, this problem can be solved with only $n+\lg^*n$ bits\footnote{%
	Recall that $\lg^*n$ is the least integer $i$ such that $\lg^in\leq 1$.
	Note that $\lg*n$ has a different ``type'' than 
	$\lg^in= \underbrace{\lg\lg\cdots\lg}_i n$
	(undefined if $\lg^{i-1}\leq 0$).
	For $\lg^*n : \reals\to\nat$ but $\lg^in : \reals\to\reals$.
	Also, $\lg^* n$ grows extremely slowly---$\lg^*(2^{65536})=5$---so 
	$n+\lg^*n$ is much better than $n+\lg n$.}, 
using a clever recursive algorithm:
I send you my first $n-\lg n$ bits,
and either (1) you now know a bit in which our strings differ, in
which case you first send me a 1 (to tell me this is the case) and then
you send me the answer, or (2) our strings are the same in the first 
$n-\lg n$ bits, in which case you first send me a 0 (to tell me 
this is the case) and then we recurse on the remaining $\lg n$ bits.

Write a recurrence for $T(n)$, the total number of bits required
by the algorithm.  Note that in case (1) above, we finish with a total
of only $(n-\lg n) + (1+\lg n) = n+1$ bits; you should convince yourself
that it's the recursive case (2) that costs the most and therefore determines
maximum number of bits required.
Solve the recurrence by iterating it and discovering a telescoping sum.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
Say random variable $X:S\to \nat$ has distribution
\[
X = \left\{ \begin{array}{ll} 	1 & \mbox{with probability } 1/3\\
				3 & \mbox{with probability } 1/6\\
				4 & \mbox{with probability } 1/2
	\end{array}
	\right.
\]
and random variable $Y:S\to\nat$ has distribution 
\[
Y = \left\{ \begin{array}{ll} 	2 & \mbox{with probability } 3/4\\
				5 & \mbox{with probability } 1/4
	\end{array}
	\right.
\]
and $X$ and $Y$ are independent. 
\begin{problemparts}
\problempart
What is the probability generating function for $X$?  For $Y$?
\problempart
Let random variable $R:S\to\nat$ be given by $R=X+Y$.\\
Compute the probability generating function for $R$.\\
How is it related to the probability generating functions for $X$ and $Y$?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem\label{genfunc}

Let's generalize the result from the last problem.
Let $X:S\to\nat$ and $Y:S\to\nat$ be independent random variables
and let $R=X+Y$ be their sum.
\begin{problemparts}
\problempart
Show that the probability generating function $G(x)$
for $R$ is the product of those for $X$ and $Y$.
Is true in general if $X$ and $Y$ are not independent?
\problempart
Recall that $\Ex{R} = G'(1)$ where $G'$ denotes the derivative
with respect to $x$.  Verify that this gives $\Ex{R} = \Ex{X} + \Ex{Y}$.
\problempart
Show that $G''(1) = \Ex{R^2} - \Ex{R}$.
\problempart
Deduce that $\vari{R} = G''(1) + G'(1) - (G'(1))^2$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem

Let's use the last result of the last problem to compute the variance
of ``the time until the first success''.
If each trial has probability $p$ of success, then random variable 
$R: S\to\nat$, denoting the trial in which the first success is obtained, 
has distribution $\Prob{R=k} = (1-p)^{k-1}p$.
\begin{problemparts}
\problempart
Compute the probability generating function $G_R(x)$
and check that $G_R(1) = 1$.
\problempart
Compute $\vari{R}$ as outlined in the previous problem.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem
(Problem 33 on page 492 of [MR].)
Balls labeled 1 to $n$ are put in an urn.
A ball is picked (uniformly) at random, it's number is recorded, 
and it is put back in the urn.
%	this may be computed as the sum of the 
%	expected values of each of the balls taken from the urn.
%	Each ball is equally likely to be any of the $n$, and so has expected 
%	value $\frac{1}{n}(1+2+\cdots+n)=\frac{n+1}{2}$, so the expected sum is
%	$k(n+1)/2$ (just as the case {\em with} replacement).

\begin{problemparts}
\ppart
Let $X_k$ be the sum of the numbers recorded if this is repeated $k$ times.
Compute $\Ex{X_k}$.
\ppart
Now suppose a ball is picked at random, it's number is recorded, and it 
is thrown away.  
Let $Y_k$ be the sum of the numbers recorded if this is repeated $k$ times.
Compute $\Ex{Y_k}$.
\problempart
Solve part {\bf (b)} in a different way, using $n$ indicator variables $B_i$,
one for each of the $n$ balls in the urn, to indicate the event that
ball $i$ is one of the $k$ balls selected.

Write an equation for the sum of the $k$ balls using the indicator
variables $B_i$.  Now compute $\Prob{B_i = 1}$ and use your equation to 
compute the  expected value of the sum.
\\ (Of course you should get the same answer!)
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem
A cadet at the Naval Academy takes a multiple-choice test with 100 questions
on which he gets 2 points for every correct answer and $-1$ point for every 
incorrect answer.
He has mastered the material to only a small extent; he has a strategy for
making educated guesses in such a way that his expected score is~50.
Luckily, he has obtained a copy of a portion of the exam in advance,
so he will not score less than~$-50$.
Let random variable $S$ denote the cadet's score.
We don't know how the cadet is making his guesses, so we don't know anything
about the distribution $S$ obeys, except that $\Ex{S}= 50$
and $-50\leq S\leq 200$.
\begin{problemparts}
\problempart
Recall from lecture one form of Markov's Inequality:
\begin{quotation}
For random variable $R:{\cal S}\to\reals$, if $R$ is always at most $L$, then
\[  \Prob{ R > k} \geq {\Ex{R} - k \over L - k}. \]
\end{quotation}
Prove this using a proof by contradiction:  assume the conclusion is false
and reach a contradiction by showing that $\Ex{R} < \Ex{R}$.
\problempart
What is a lower bound on $\Prob{S>20}$?
\problempart
What is a lower bound on $\Prob{S>50}$?\\
Why is this?
What distribution achieves this probability?
\problempart
What is a lower bound on $\Prob{S>0}$?\\
What is an upper bound on $\Prob{S<0}$?
\problempart
What is an upper bound on $\Prob{S<50}$?
\problempart
What is a lower bound on $\Prob{S<100}$?
\problempart
Suppose we are told that the cadet guesses in such a way that 
$\vari{S} = 625$.
What is an upper bound on $\Prob{S \geq 100}$?
\problempart
Suppose we are told that the cadet guesses in such a way that the
sixth {\em central} moment, $\Ex{(S-\Ex{S})^2}$, 
is~$10^6$.
What is an upper bound on $\Prob{S\geq 100}$?\\
Derive a bound by imitating the proof of Chebyshev's Theorem:
 Write 
	\[ \Prob{R-\Ex{R} > 50} \leq \Prob{(R-\Ex{R})^6 > 50^6} \]
 and use Markov's Inequality to get the upper bound for the latter.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
{\bf The baseball-card-collecting problem.}
You buy baseball cards one at a time.  Each card is wrapped in 
Topps$^{\sc r}$ patented opaque wax paper, so you don't know until you open
it which card you are buying---it is equally likely to be any card 
in the set.
If the set contains $n$ cards,
calculate the expected number of cards you will buy before collecting
the entire set.  
(\hint Let random variable $R_i$ denote
the number of cards you buy to get a new card if you already have $i$ 
different cards.)  You should get a familiar function of $n$.
%	The total number of cards you buy is therefore
%	$R = \sum_{i=0}^{n-1} R_i$ and $\Ex{R} = \sum \Ex{R_i}$.
%	$R_i$ obeys the distribution from the last problem with 
%	$p={n-i\over n}$, so $E[R_i] = {n\over n-i}$.  So 
%	\[
%	\Ex{R} = \frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} =
%		n\left( \frac{1}{n} + \cdots + 1\right) \sim n\ln n.
%	\]

Calculate the variance of $R=\sum_i R_i$ using the calculation from 
\ref{genfunc} and the fact that 
$\vari{X+Y} = \vari{X} + \vari{Y}$ for $X,Y$ independent.
(An asymptotic $\sim$ bound is sufficient.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\npage
\problem
Suppose you are offered a betting game in which you keep flipping a fair coin
until you get a head and if you flip the coin $k$ times without getting a head,
you win $\$ 2^k$.
If the game costs \$1 to play, what is your expected return (net winnings)?\\
Would you be willing to play this game?
Would you be willing to play this game if it cost \$1000?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
\remove{
  \npage
  \problem
  When designing VLSI circuits, a good rule of them is that the
  probability that the circuit will work is $e^{-pA}$ for some constant $p$,
  where $A$ is the area of the circuit.  Give a justification for this rule
  under the assumption that every unit of area on the chip fails independently
  with probability $p$ and that the circuit will fail if any unit of area fails.
  %   Idea we want is prob of working is $(1-p)^A$ which is at most $e^{-pA}$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{center}
\fbox{\fbox{\bf The following problems are taken from last semester's final exam.}}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Show that for all positive integers $m$ and $n$, there exist positive
integers $i \neq j$ such that $m$ evenly divides $n^i-n^j$.  (\hint
Pigeonhole principle.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem

Circle {\bf T} or {\bf F} to answer true or false for each of the
following statements.  Wrong answers will be penalized, so do not
guess unless you are reasonably sure.

Let $f:A\rightarrow B$ and $g:B\rightarrow C$ and let
$p,r,s$ and $t$ be functions from $\nat$ to $\reals$.
Recall that $g\circ f$ is defined as $(g\circ f)(x) = g(f(x))$.
\bigskip
\begin{itemize}
\setlength\itemindent{.5in}
%\setlength\itemsep{2in}
% \tfitem If $f$ maps $A$ onto $B$ and $g$ maps $B$ onto $C$,
% then $g\circ f$ maps $A$ onto~$C$.
\tfitem If $f$ and $g$ are both bijections, then so is $g\circ f$.
\tfitem If $g\circ f$ is a bijection, then so are $f$ and $g$.
% \tfitem 
%  If $p(n) \sim s(n)$ and $r(n) \sim t(n)$, then $p(n)r(n) \sim s(n)t(n)$.
% \tfitem If $p(n)=5$, then $p(n)=O(n^2)$.
\tfitem If $p(n) = \left\{ \begin{array}{ll}
 \frac{1}{100} + \frac{1}{101} + \frac{1}{102} + \cdots + \frac{1}{n} & 
 \mbox{ if $n\geq 100$} \\
 \rule{0pt}{15pt} 0 & \mbox{ if $n<100$}
			\end{array} \right. $ ,
	then $p(n)=\Omega(\lg n)$.
\tfitem  If $p(n)=o(t(n))$, then $e^{t(n)+p(n)} \sim e^{t(n)}$.
\tfitem  $\lg\sqrt{n}=o(\lg n)$.
% \tfitem  $\lg^2(\lg n)=o(\lg n)$.
\tfitem ${n \choose n/3} =\Omega \left( 2^n/\sqrt{n}\right)$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem

Prove by induction that the recurrence $T(n)=4T(n/5)+n$ has 
solution $T(n)= O(n)$. (Assume that $T(n)$ is constant for $n\leq 2$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem 

Consider the set $F$ of all functions from set $A$ to set $B$, where
$|A|=m$ and $|B|=n$.
That is, $F = \{ f \mid f:A\rightarrow B\}$.

\begin{problemparts}
%\setlength\itemsep{2.5in}
\problempart
What is the size of $F$?
\problempart
How many functions $f\in F$ are injective (one-to-one) if\ldots
	\begin{enumerate}
%	\setlength\itemsep{1.5in}
	\item \ldots $m < n$? 
	\item \ldots $m = n$? 
	\item \ldots $m > n$?
	\end{enumerate}

\problempart
How many functions $f\in F$ are surjective (onto) if\ldots
	\begin{enumerate}
%	\setlength\itemsep{1.5in}
	\item \ldots $m < n$? 
	\item \ldots $m = n$? 
	\item \ldots $m > n = 2$?
	\end{enumerate}

\problempart
Assume now that $B=\{0,1\}$.
Suppose a function $f$ is chosen uniformly at random from~$F$.
What is the probability that $f$ maps exactly $n/2$ elements of $A$ to~$1$?
%	That is, what is Prob$[|f^{-1}(1)| = n/2]$?
Give an exact asymptotic ($\sim$) bound in terms of $n$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem

In the lottery game Keno, a participant selects 20 different numbers from 
the set $S=\{1,\ldots, 80\}$.  
To determine winners, the lottery randomly selects 10 different numbers from 
$S$, and anyone who selected those 10 numbers (among his or her 20 numbers)
wins.  

\begin{problemparts}
%\setlength\itemsep{3in}
\problempart
What is the probability of winning Keno?
(You may leave factorials and powers in your answer.)

\problempart
The game Teno is the played in the same manner as Keno, except that 
the lottery selects 11 numbers instead of 10, and anyone who selects
10 of those 11 (from among his or her 20 numbers) wins.
What is the probability of winning Teno?
(You may leave factorials and powers in your answer.)

\npage
\problempart
By what factor, rounded to the closest integer, is the probability of
winning Teno greater than the probability of winning Keno?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem

Let $S$ be a sample space.
Say random variable $X:S\to \nat$ has distribution
\[
X = \left\{ \begin{array}{ll} 	2 & \mbox{with probability } 1/4,\\
				3 & \mbox{with probability } 1/4,\\
				5 & \mbox{with probability } 1/2;
	\end{array}
	\right.
\]
and random variable $Y:S\to\nat$ has distribution 
\[
Y = \left\{ \begin{array}{ll} 	1 & \mbox{with probability } 2/3,\\
				4 & \mbox{with probability } 1/3;
	\end{array}
	\right.
\]
where $X$ and $Y$ are independent.

Let random variable $Z:S\to \nat$ be given by $Z = \max (X,Y)$.
\bigskip
\begin{problemparts}
%\setlength\itemsep{2.5in}
\problempart
What is the expected value of~$Z$?
\problempart
What is the variance of~$Z$?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem

Let $R$ be a random variable with distribution
$$\Prob{R=m}=\lambda^m/(m!e^\lambda)$$ for $m\in\nat$, where $\lambda$ is a 
positive constant.
Let $S_n=R_1+\cdots+R_n$ where $R_i$ are (mutually) independent identically  
distributed random variables with same distribution as~$R$.
\begin{problemparts}
%\setlength\itemsep{3.5in}
\problempart
Show that the probability generating function for $R$ is
$G(x)=e^{\lambda (x-1)}$.  State any identities you use to derive
this formula.  

\problempart Use the generating function $G(x)$ to verify that $\sum_m
\Prob{R=m} = 1$.

\problempart
What is the probability generating function for $S_n$?

\problempart
What is $\Prob{S_n=m}$?  

\npage
\problempart
What is $\Ex{R}$?


\problempart
What is $\Ex{S}$?

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \npage\problem
% 
% Let $S$ be a sample space, and 
% let $R:S\rightarrow \reals$ be a random variable with $\Ex{R}=10$.
% \begin{problemparts}
% \setlength\itemsep{4in}
% 
% \problempart Give the tightest upper and lower bounds that you can for
% $\Prob[R\geq20]$.  That is, give the greatest $p\in\reals$ and the
% least $q\in\reals$ such that $p\leq \Prob[R\geq 20] \leq q$.
% 
% \problempart Suppose the standard deviation of $R$ is 2.  Give the
% tightest upper and lower bounds that you can for $\Prob[R\geq 20]$.
% 
% \problempart Suppose the kurtosis of $R$ is 16.  Give the tightest
% upper and lower bounds for $\Prob[R\geq 20]$.  Recall that the
% kurtosis of $R$ is defined as $\Ex{(R-\Ex[R])^4}$.
% 
% \end{problemparts}
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem 

Recall the Gambler's Ruin problem from lecture.  Assume the game is
fair---that is, $p=1/2$.  Suppose you have a goal of reaching $\$ T$.
Let $P_n$ be the probability that, starting with $\$n$, where $n\leq
T$, you reach your goal before going broke.  In lecture we showed that
$P_n = n/T$.

Suppose you start with $\$n$ and continue to play until you are broke.
Let random variable $M$ be the maximum number of dollars you ever
have.  Determine the expected value of~$M$.




\end{problems}
\end{document}
