%%%
% Kyle, there may be latex'ing problems with these, since I don't 
% know all the macros you are using.  But I think they should be 
% fine.  They may need to be cleaned up some--I haven't bothered to do this.
% I will try to note for each one what the problem tests, and anything
% I think will need to be fixed up.


%% Will we be testing the basic stuff from PS1 again?
% That's the problem set I did with Josh. 
% Since induction and proofs will be checked by other material, 
% I'm only including stuff about logic

% Logic
\kproblem 
Transcribe the following arguments into logic, 
and for each argument, 
show that it is valid, 
or give a counterexample. 
State clearly what your propositions and/or predicates are.

\bparts

\ppart
Either Jane or Bob ate the cheesecake. 
Neither Bob nor David drank the soda. 
If Bob ate the cheesecake, he also drank the soda. 
So Jane ate the cheesecake. 

\ppart
Unless we get up early, 
we won't make it to the game on time. 
If we go to sleep early then we will get up early. 
Therefore, if we go to sleep, we will get to the game on time. 

\ppart
Suppose all circles are round, 
no squares are round, 
and some triangles are round. 
Then some circles are triangles. 

\eparts

%% More logic: proofs of logical equivalence
\kproblem
Prove which of the following statements imply which other statements. 
(This includes showing that a statement does not imply another.)
\begin{enumerate}

\item
$\forall x (P(x) \implies Q(x))$ 

\item
$\exists x Q(x) \implies \forall x P(x)$ 

\item
$\exists x Q(x) \implies \exists x P(x)$ 

\item
$\exists x (Q(x) \implies P(x))$ 

\item
$\forall x \neg P(x) \lor \exists x Q(x)$ 

\item 
$\exists x P(x) \lor \forall x \neg Q(x)$ 

\end{enumerate}

%% Bounding deviation from the mean
\kproblem
There are sixty people in a basketball league. 
No one is shorter than 5'6'', nor is anyone taller than 6'6''. 
The average height is 5'10''. 

\bparts

\ppart
Without any other information, 
what is the best possible upper bound 
for the number of people taller than 6'4''? 

\solution{Use Markov's bound.  The answer is 40\%, I believe, 
so twenty-four people.}

\ppart
Without any other information, 
what is the best possible upper bound 
for the number of people who are 5'6''?

\solution{Markov again, this time flipping the variable. 
I believe the answer is $8/12 = 2/3$, 
so forty people.} 

\ppart
You are now told that the standard deviation 
of the heights of these sixty people is 2''.
What is the best upper bound you can give now 
for the two previous parts?

\solution{Use one-sided Chebyshev inequality: 
$\Pr(H - 5'10'' > 6'') \leq \frac{\variance{H}}{\variance{H} + 6^2}
			= 2/38 = 1/19$. 
So at most $\floor{60/19} = 3$ people who are at least 6'4''. 

$\Pr(5'10 - H > 4'') \leq \frac{\variance{H}}{\variance{H} + 4^2}
			= 2/18 = 1/9$. 
So at most $\floor{60/9} = 6$ people who are 5'6''.
%Can we do better because we can bound the deviation from 
% the mean?
}

\eparts

%% Wald's Theorem
% From Fall98 sample problems
\kproblem
A miner, lost in some abandoned mine, finds himself in a room 
containing three doors.  Door 1 leads him to freedom after two 
hours travel; door 2 returns him to the same room after four hours travel, and 
door 3 returns him to the room after eight hours travel.
Each time he finds himself in the room, 
the miner picks a door with equal probability.  
Let $T$ denote the time until he finds the exit. \\

\bparts

\ppart Define a sequence of iid random variables $X_i$ and a stopping rule 
$N$ such that
% Have we defined stopping rule?
\[T = \sum_{i=1}^{N}{X_i}\]


\solution{
We view this as an experiment where at each step we make a choice between
three equiprobable outcomes.

Let $X_i$ = number of hours to return to room on $i$th step.

Let $N$ = number of steps until good door is selected.

Then $N$ is geometrically distributed with probability $1/3$.
}

\ppart Use Wald's Identity to find $\Ex[T]$

\solution{
$\Pr(X_i = 2) = 1/3$

$\Pr(X_i = 4) = 1/3$

$\Pr(X_i = 8) = 1/3$

$\Ex[X_i] = 14/3$

$\Ex[N] = 3$

By Wald's Identity

\[
\Ex[\sum_{i=1}^N X_i] = 14
\]
}

\eparts   
