\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

%% TUTORIAL 10: Basic Probability, Monty Hall, Conditional Probability,
%% Baye's rule

\ifshowsolutions
  \tutsol{10}{November 8, 2001}{\stamp}
\else
  \tutprobn{10}{November 8, 2001}{\stamp}
\fi

\begin{problems}
%Spring 99 Tutorial 10, Problem 1

\problem Suppose the game {\em Let's Make A Deal} is changed
slightly. Instead of having 3 doors with 1 grand prize, in the new game
there are 4 doors with 2 grand prizes. The rule of the game remains the
same. Therefore the game now becomes:

\begin{quote}
At one stage of the game, a contestant is shown 4 doors. The contestant
knows that there are 2 grand prizes behind 2 of the doors and that there
are goats behind the 2 other doors. At the beginning, the contestant picks
a door. To build suspense, the assistant of the game then opens a {\em
different} door, revealing a goat. The contestant can then stick with his
original door or switch to another unopened door. He wins a prize only if
he now picks the door with the prize.
\end{quote}

In the new game, what is the probability of winning with the ``stick''
strategy? How about the ``switch'' strategy? Can you explain why the two
probabilities do not sum up to 1?

\solnospace{The player wins with a ``stick'' strategy iff he chooses the
``correct door'' in the first place. Therefore the probability of winning
with the ``stick'' strategy is $\frac{1}{2}$.

To calculate the probability of winning with a ``switch'' strategy, let
$E_1$ be the event that ``the player chooses the correct door at his first
chance''. Let $E_2$ be the event that ``the player switches to the correct
door at his second chance''.
\begin{eqnarray*}
\pr{\text{winning with ``switch''
strategy}}&=&\pr{E_2|E_1}\pr{E_1}+\pr{E_2|\overline{E_1}}\pr{\overline{E_1}}\\
&=&\frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{1}{2}\\ &=&\frac{3}{4}
\end{eqnarray*}

The two probabilities do not need to sum up to 1. They are calculated in a
different probability space.  In particular, the player winning by the
``switch'' strategy does not imply he will lose by the ``stick'' strategy,
and vice versa. Therefore, the same winning event can be counted in both
cases at the same time.}

%Spring 2000 Miniquiz 12
\problem
Suppose a game involves tossing a fair coin until a head first arises.
\bparts
\ppart
What is the probability that a head first arises on an
even-numbered throw?

\solnospace{
The probability that a head first arises on an
even-numbered throw can be easily broken into two cases based on the
first flip. Half the time, a head comes up on the first flip and thus the
first head does not appear on an even toss. The other half of the time,
the first head will be on an even toss only if it is on a odd toss in
the remaining sequence of tosses. Thus:
\begin{eqnarray*}
p & = & \frac{1}{2}(1 - p) \\
p & = & \frac{1}{2} - \frac{1}{2}p \\
\frac{3}{2}p & = & \frac{1}{2} \\
p & = & \frac{1}{3} 
\end{eqnarray*}
}

\ppart
What is the sample space and probability space of this experiment?

\solnospace{
The sample space is set of all sequences $\{T\}^{k}H$ where
$\{T\}^k$ is a string of $k$ Tails and $k \in {\mathrm{I\!N}}$.

For the probability space we assign a probability to each of these
possible events:
$$\prob{\text{a Head first appears in the n-th throw}}=
\prob{\{T^{n-1}\}H}= \biggl( \frac{1}{2}\biggr)^{n-1}\biggl(
\frac{1}{2}\biggr)= \biggl( \frac{1}{2}\biggr)^n$$ }

\ppart
What is the probability, if any, that we never flip a Head in
an even numbered throw?

\solnospace{

This is the same event as flipping a Head always in an odd numbered
throw and the probability is $1-\frac{1}{3}=\frac{2}{3}$ since
the probability of never flipping a Head is $0$.

Alternatively:
\begin{eqnarray*}
\prob{\text{a Head always appears on an odd numbered throw}}= \\
\sum_{k=0}^{\infty}{ \prob{\text{a Head first appears in a $2k+1$ throw}}}= \\
\sum_{k=0}^{\infty}{\biggl(\frac{1}{2}\biggr)^{2k+1}}= \\
\frac{1}{2}\sum_{k=0}^{\infty}{\biggl(\frac{1}{4}\biggr)^k}= \\
\frac{1}{2}\times \frac{4}{3}=\frac{2}{3}\\
\end{eqnarray*}
}

\eparts

%%Spring 98 Tutorial 11, Problem 1 (sols by nikos)
%\problem You toss a coin twice. What is the probability that you
%get two heads given that you get {\em at least one head.}
%What is the probability that you  get two heads given that 
% {\em the first toss} gives a head?

% \solnospace{
% Let $H$ be the event that there is at least one head.

% Let $HH$ be the event that there are two heads.

% Let $1H$ be the event that the first toss comes heads.

% For the first part, 
% \begin{eqnarray*}
% \pr{HH|H}&=&\frac{\pr{HH \cap H}}{\pr{H}}\\
% &=&\frac{\pr{HH}}{\pr{H}} \\
% &=&\frac{\frac{1}{4}}{\frac{3}{4}}\\
% &=&\frac{1}{3}
% \end{eqnarray*}

% Or more intuitively, given event $H$, our sample space is reduced to
% the events $HH$, $HT$, $TH$, each having the same probability of
% occuring (which is $\frac{1}{4})$. Therefore $HH$ will occur with
% probability $\frac{1}{3}$ (one out of the three possibilities).

% For the second part, given $1H$ we fix the first toss to be heads.
% Then we either have heads or tails for the second toss with
% probability $\frac{1}{2}$.  This implies that the event $HH$ will 
% occur with probability $\frac{1}{2}$, therefore 
% $\pr{HH|1H}=\frac{1}{2}$.
% }

%Spring 99 Tutorial 11, Problem 2
\problem Suppose you repeatedly flip a fair coin.
\bparts
\ppart What is the probability you see the sequence \texttt{HTT} before
you see the sequence \texttt{HHT} (where \texttt{H} is a head and
\texttt{T} is a tail)? \hint First evaluate the conditional probability of
seeing \texttt{HHT} before \texttt{HTT} given that that the first toss
comes up \texttt{H}. Then show that this is the same as the required
probability.  $1/2$ is not the answer!

\solnospace{
Let $A$ be the event that we see the sequence HHT before we see 
HTT. Our first observation is the following:

\begin{lemma}
\[\prob{A} = \prob{A \mid H}\]
\end{lemma}

That is, the probability of seeing HHT before HTT is the same as
the probability of seeing HHT before HTT given that we have
seen a head (H).
 
\begin{proof}
$$\prob{A} = \prob{A \cap H} + \prob{A \cap T}$$
$$ = \prob{A \mid H} \prob{H} + \prob{A \mid T} \prob{T}$$

Now
$$\prob{A \mid T} = \prob{A}$$
since for any outcome $w$ of coin tosses
$Tw \in A$ iff $w \in A$.  Therefore
$$\frac{1}{2}\prob{A} = \frac{1}{2}\prob{A \mid H}$$
$$\implies \prob{A} = \prob{A \mid H}$$
\end{proof}

To evaluate $\prob{A \mid H}$ 
consider the outcomes of the two coin tosses immediately following the first
head.
There are four possible outcomes for these two tosses: HH,HT,TH,TT.
From the result in last week's tutorial,
$$\prob{A \mid H} = \prob{A \cap HH \mid H} + \prob{A \cap HT \mid H} + \prob{A \cap TH \mid H} + \prob{A \cap TT \mid H}$$
$$ = \frac{1}{4}(\prob{A \mid HHH} + \prob{A \mid HHT} + \prob{A \mid HTH} + \prob{A \mid HTT})$$
$$ = \frac{1}{4}(\prob{A \mid HHH} + 1 + \prob{A \mid HTH} + 0)$$

Next we evaluate these terms:
\begin{lemma}
$$\prob{A \mid HHH} = 1$$
\end{lemma}
{\em Proof. }
If we ever see a T in the remaining flips, then HHT occurs before
HTT. The probability of never seeing a T is $\lim_{n \rightarrow \infty} \frac{1}{2^n} = 0$. Hence we see a T with probability 1.
\qed

\begin{lemma}
$$\prob{A \mid HTH} = \prob{A \mid H}$$
\end{lemma}

{\em Proof. }
For any string of outcomes $w$ of coin tosses,
$HTHw \in A$ iff $Hw \in A$.
\qed


Substituting in the equation,
$$\prob{A \mid H} = \frac{1}{4}(2+\prob{A\mid H})$$
That is 
$$\frac{3}{4}\prob{A \mid H} = \frac{1}{2}$$
$$\implies \prob{A \mid H} = \frac{2}{3}$$
So $$\prob{A} = \frac{2}{3}$$}


\ppart If you repeatedly flip a fair coin as above, what is the probability
that you see the sequence \texttt{HHT} before you see the sequence
\texttt{TTH}?
\hint There is an easier way to solve this part than the previous one.

\solnospace{ In this case the answer is $1/2$.  The proof is by a bijection
argument on the sample space.  Let $A$ denote the event that you see HHT
before TTH, and $B$ denote the event that you see TTH before HHT.  We will
define a bijection, $g$, between $A$ and $B$ so that the probability of
$g(w)$ is equal to the probability of $w$.  The bijection is quite simple.
Given a sample point $w \in A$, define $g(w) = \bar{w}$, where $\bar{w}$
is the outcome where every H is replaced by a T and vice versa. For
example $g(HHT) = \overline{HHT} = TTH$.  We first observe that $g:A
\rightarrow B$.  This follows from the fact that HHT precedes TTH in $w$
iff $\overline{HHT} = TTH$ precedes $\overline{TTH} = HHT$ in
$\bar{w}$. And $g$ is onto by the same reasoning.  Since $g$ is clearly an
injection, we can conclude that it is a bijection.

Then we observe that $\prob{w} = \prob{g(w)}$ for any $w$. This is because
$\prob{H} = \prob{T}$ and $g(w)$ has the same length as $w$. (Note: this is
a critical step in probability calculations.  Otherwise, step 2 below
can fail.)
Hence,
\begin{eqnarray}
\prob{A} &=& \sum_{w \in A} \prob{w} \\
&=&\sum_{w\in A} \prob{g(w)}\\
&=&\sum_{w' \in B} \prob{w'}\\
 = \prob{B}
\end{eqnarray}

Step 2 is valid because $g$ preserves the probability, and step 3 is
by the bijection property with $w' = g(w)$.

Finally we have to show that $\prob{A \cup B} = 1$. This follows
from the fact that 
$$\overline{A \cup B} = \{HHH\ldots, TTT\ldots, HTTT\ldots, THHH\ldots\}$$
Each of these strings has probability $0$ of occuring. 

Hence,
$$\prob{\overline{A \cup B}} = 0 \implies \prob{A \cup B} = 1$$
Since $A$ and $B$ are disjoint, this means that $\prob{A} + \prob{B} = 1$ 
and hence $\prob{A} = \frac{1}{2}$.
}
\eparts


%%Spring 99 Problem set 10, Problem 4
%\problem
%Given a biased coin that comes up heads $2/3$ of the time and tails
%$1/3$ of the time, simulate a fair coin by applying repeated flips of
%the unfair coin.  In other words, design a procedure involving tosses
%of the unfair coin which has two outputs, ``tail'' and ``head'', and
%which outputs them with equal probability.  Your procedure should
%return ``head'' or ``tail'' with probability at least
%$1-(\frac{1}{2})^n$, using $O(n)$ tosses of the unfair coin, which
%means that your procedure can have a tiny probability of not returning
%any answer after using reasonably many tosses of the unfair coin.
%
%
%\solnospace{ The procedure is this: Flip the unfair coin twice.  If you
%get HT then output ``tail'' and if TH then output ``head''.  Otherwise
%repeat.  Probability of outputting ``tail'' is equal to probability of
%outputting ``head''.  Furthermore, probability of failure to output
%anything at all after using $2k$ tosses is
%$(\frac{2}{3}*\frac{2}{3}+\frac{1}{3}*\frac{1}{3})^k = (\frac{5}{9})^k
%= (\frac{1}{2})^{ck}$ for some small $c=(\ln \frac{5}{9}/\ln
%\frac{1}{2}) \approx 0.85$.}

% %A first course in Probability,S.Ross,p.73
% \problem
% In answering a question on a multiple-choice test, a student either
% knows the answer or guesses. Let $p$ be the probability that the student
% knows the answer and $1-p$ the probability that the student guesses.
% Assume that a student who guesses at the answer will be correct with
% probability $1/m$, where $m$ is the number of multiple-choice
% alternatives. What is the conditional probability that a student knew
% the answer to a question, given that he or she answered it correctly?

% \solnospace{
% Let $C$ and $K$ denote, respectively, the events that the student asnwers
% the question correctly and the event that he or she actually knows the
% answer. Now
% \begin{eqnarray*}
% \pr{K|C}&=& \frac{\pr{K \cap C}}{\pr{C}}\\
% &=& \frac{\pr{C|K}\pr{K}}{\pr{C|K}\pr{K}+\pr{C|\overline K}\pr{\overline K}}\\
% &=& \frac{p}{p+(1/m)(1-p)}\\
% &=& \frac{mp}{1+(m-1)p}\\
% \end{eqnarray*}
% }

%The Probabilistic Method, J. Spencer, p.1.
%modified to fit 6.042 material

\problem
The {\em Ramsey number} $R(k,l)$ is the smallest integer $n$ 
such that in any two-coloring of the edges of a complete graph of $n$ vertices
$K_n$ by red and blue, either there is a red $K_k$ (i.e., a complete
subgraph on $k$ vertices all of whose edges are colored red) or there
is a blue $K_l$. Ramsey (1929) showed that $R(k,l)$ is finite for any
two integers $k$ and $l$. Let us obtain a lower bound for the diagonal
Ramsey numbers $R(k,k)$.

\bparts
\ppart
Consider a random two-coloring of the edges of $K_n$ obtained by coloring
each edge independently either red or blue, where each color is equally
likely. For any fixed set $R$ of $k$ vertices, let $A_R$ be the event
that the induced subgraph of $K_n$ on $R$ is {\em monochromatic}
(i.e., that either all its edges are red or they are all blue).
What is $\pr{A_R}$?

\solnospace{
The number of edges connecting the $k$ vertices is ${k \choose 2}$.
The total number of colorings of these edges is $2^{{k \choose 2}}$.
Of all these possible colorings only 2 belong to $A_R$, namely
when all edges are red or when all edges are blue, so
$$\pr{A_R}=\frac{2}{2^{{k \choose 2}}}=\frac{1}{2^{{k \choose 2}-1}}$$
}
\ppart
How many choices are there for the set $R$?

\solnospace{ There are ${n \choose k}$ possible choices for $R$.  }


\ppart In reality the $A_R$ events are not disjoint, since we can
have edges that overlap. For now, assume that the $A_R$ events are
disjoint. What is the probability $p_u$ that at least one of the events
$A_R$ occurs?
\hint Use the sum rule.

\solnospace{
$$p_u={n \choose k}\frac{1}{2^{{k \choose 2}-1}}$$ }

\ppart
Briefly explain why this is an upper bound for the general case,
when the $A_R$ events are not disjoint.

\solnospace{
Simply because from inclusion-exclusion we know that the union of
$k$ sets has fewer elements than the sum of the elements of each set.
}

\ppart
Suppose we set $p_u<1$, what does this tell us about $R(k,k)$ with 
respect to $n$?
\hint Consider the complement of the event that has probability $p_u$
and what it says about the coloring of $K_k$.

\solnospace{
If $p_u<1$ then with positive probability, no event $A_R$ occurs and there
is a two-coloring of $K_n$ without a monochromatic $K_k$. Therefore
the Ramsey number must be greater than $n$ i.e. $R(k,k)>n$.
}
%this will need Stirling's formula
\ppart 
Now we want to find a lower bound for $R(k,k)$ that is as tight
as possible so we push the value of $n$ as high as possible, but
always trying to hold $p_u<1$.  After a lot of thought someone comes up
with $n= {\floor {2^{k/2}}}$ as the highest possible $n$. Assuming $k \geq 4$
can you prove that this bound we still have $p_u<1$?
\hint You will need to apply Stirling's approximation. Also assume that
you can bound ${a \choose b}$ from above by $\frac{a^b}{b!}$.

\solnospace{

\begin{eqnarray*}
{n \choose k}\frac{1}{2^{{k \choose 2}-1}}&<& \\
\frac{n^k}{k!} \frac{2}{2^{{k \choose 2}}}&<&\\
\frac{n^k}{k!} \frac{2}{2^{\frac{k^2}{2}-\frac{k}{2}}}&<&\\
\frac{2^{1+k/2}}{k!} \frac{n^k}{2^{k^2/2}}&<&\\
\frac{2^{1+k/2}}{k!} \frac{n^k}{n^k}&<&\\
\frac{2(\sqrt{2})^k}{(\sqrt{2\pi k})k^k e^{-k}}&<&\\
\frac{2}{\sqrt{2\pi k}}\biggl(\frac{\sqrt{2}e}{k}\biggr)^k &<& 1\\
\end{eqnarray*}

since $\sqrt{2}e=3.844$ and $k_{min}=4$ then
$\biggl(\frac{\sqrt{2}e}{k}\biggr)^k < (\frac{3.844}{4})^k < 1$
}

\ppart
What is therefore a lower bound for $R(k,k)$?

\solnospace{
$R(k,k)> {\floor{ 2^{k/2}}}$
}
\eparts


\end{problems}

\end{document}
