\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol6}
  \newcommand{\handouttitle}{Problem Set 9 Solutions}
  \newcommand{\handoutdate}{April 27, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps6}
  \newcommand{\handouttitle}{Problem Set 9}
  \newcommand{\handoutdate}{April 18, 2000}
  \newcommand{\duedate}{April 25, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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


\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Rosen, Section 4.4 \\
    Self-study problems: 9, 11, 13, 15, 17 
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[Rosen:] Section 4.5
    \item[6.042 Fall 97 Lecture notes (available from course webpage):] %
      Lecture 20
    \end{description}
  \end{description}
  }

\section*{Problems:}

% [[[Coverage:
% The probability identities
% Independence
% Mutual independence, pairwise independence
% Uniform probability spaces
% Independent trials
% Birthday problem
% ]]]


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem %
%(Probability identities)

\begin{problemparts}
\problempart
Carefully prove the following theorem:
\begin{quote}
If $A$ and $B$ are events in a probability space with
$\Pr(B) \neq 0$ and $\Pr(\bar{B}) \neq 0$,
then
$\Pr(A) = \Pr(A \mid B) \Pr(B) + \Pr(A \mid \bar{B}) \Pr(\bar{B})$.
\end{quote}
Show all steps, and justify them with basic facts about probability.

\solution{
\begin{eqnarray*}
\Pr(A) & = & \Pr  ((A \cap B) \cup (A \cap \bar{B})) \\
      & = & \Pr  (A \cap B) + \Pr (A \cap \bar{B}) \text{(Because they are disjoint.)} \\ 
      & = & \Pr  (A \mid B) \Pr(B) + \Pr (A \mid \bar{B}) \Pr(\bar{B}) \\
\end{eqnarray*}
}


\problempart
A space probe near Mars communicates with Earth using bit strings. 
Suppose that in its transmissions it sends a 1 one-third of the time and 
a 0 two-thirds of the time. When a 0 is sent, the probability that it is 
correct is 0.9, and the probability it is received incorrectly (as a 1) is
0.1. When a 1 is sent, the probability it is received correctly is 0.8, and
the probability it is received incorrectly (as a 0) is 0.2.

Use the formula above to find the probability that a 0 was transmitted,
given that a 0 was received.

\solution{
Let R be the event that a 0 was received. Let S be the event that a 0 was transmitted. 

So we are trying to find $\Pr(S \mid R)$.

Then we have:
\begin{eqnarray*}
\Pr(S) & = & 2/3 \\
\Pr(\bar{S}) & = & 1/3 \\
\\
\Pr(R \mid S) & = & 0.9 \\
\Pr(\bar{R} \mid S) & = & 0.1 \\
\\
\Pr(\bar{R} \mid \bar{S}) & = & 0.8 \\
\Pr(R \mid \bar{S}) & = & 0.2 \\
\end{eqnarray*}

Now rearranging:
\begin{eqnarray*}
\Pr(S \mid R) & = & \frac{\Pr (S \cap R) }{\Pr (R)} \\
              & = & \frac{\Pr (R \mid S) \Pr (S) }{\Pr(R)} \\
              & = & \frac{\Pr (R \mid S) \Pr (S) }{\Pr(R \mid S) \Pr (S) 
                                                 + \Pr(R \mid \bar{S}) \Pr(\bar{S})} \\
              & = & \frac{0.9 * 2/3}{0.9 * 2/3 + 0.2 * 1/3} \\
              & = & \frac{1.8}{1.8+.2}\\
              & = & .9
\end{eqnarray*}
}

\problempart
Generalize the theorem above. 
Namely, given an event $A$ and mutually exclusive events $B_1, B_2,
... B_k$ with nonzero probability, prove that:
\[
Pr(B_1 \cup B_2 \cup B_3 \cup ... B_k ) = 1
\]
implies:
\[
\Pr(A) = \sum_{i=1}^k \Pr(A | B_i) \Pr(B_i)
\]

\solution{
\begin{eqnarray*}
\Pr(A) & = & \Pr (A \cup (B_1 \cap B_2 \cap ... \cap B_k  ) )  \\
       & = & \Pr((A \cap B_1) \cup (A \cap B_2) ... \cup (A \cap B_k)) \\
       & = & \Pr(A \cap B_1) + \Pr(A \cap B_2) + ... +  \Pr(A \cap B_k) \longrightarrow \text{Disjoint} \\ 
       & = & \Pr(A \mid B_1) \Pr(B_1) + \Pr(A \mid B_2) \Pr(B_2) + ... +  \Pr(A \mid B_k) \Pr(B_k) \\
       & = & \sum_{i=1}^k \Pr(A | B_i) \Pr(B_i)
\end{eqnarray*}
}
%[[[IThis doens't make sense either. I changed it to Pr(A). Otherwise you have Bayes law. 
% And we need some constraints on the B_i ]]]
\end{problemparts}

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

\problem 
% (Independence, mutual independence, independent trials,...)

\begin{problemparts}

\problempart
Consider families with 3 children, assume events that the 
lst, 2nd and 3rd child are girls are all independent, and have
probability 1/2.

Let $H$ be the event that "the family has children of both sexes", and
$G$ the event that "the family has at most one girl".
Are these events independent?  Prove or disprove.

\solution{

These two events are not independent. The probability that a family has children
of both sexes obviously depends on whether or not the family has a girl. 

}

\problempart
%Part (b):
Consider the same question for a family of 2 children.

\problempart
%Part (c)
Consider the same question for a family of 4 children.

\end{problemparts}

%[[[How could these be independent? Seems unreasonable]]]

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

%\problem
%
%In Ross, problem 62 on p. 113 looks nice---based on circuits.
%If you don't have the book, I can describe it in email.

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

\problem
Shishir, David, and Ken went target shooting last weekend.
They shot simultaneously at an empty soda can, which fell over.
They have probabilities $p_s$, $p_d$ and $p_k$ of hitting it.
Calculate the following probabilities; state any independence
assumptions you need.

\begin{problemparts}
\problempart The probability that all three hit the can.

\solution{
Let S, D, and K be the events that each hit the can respectivelly. 
And let F be the event that the can fell over. 

Assume that the can needs to be hit to fall over. Also assume mutual exclusivity 
on whether or not each person hits the can.

So we want $\Pr (S \cap D \cap K | F)$.

\begin{eqnarray*}
\Pr(S \cap D \cap K \mid F) & = & \frac{\Pr (S \cap D \cap K \cap F) }{\Pr(F)}\\
& = & \frac{\Pr(F \mid S \cap D \cap K) \Pr (S \cap D \cap K)}{\Pr(F)} \\
& = & \frac{p_sp_dp_k}{\Pr(F)}
\end{eqnarray*}

To calculate $\Pr(F)$:
\begin{eqnarray*}
\Pr(F) & = & Pr (F \mid S \cup D \cup K) \Pr(S \cup D \cup K) \\
       & = & p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k 
\end{eqnarray*}

Altogether:
\begin{eqnarray*}
\Pr(S \cap D \cap K \mid F) & = & \frac{p_sp_dp_k}{\Pr(F)} \\
         & = & \frac{p_sp_dp_k}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k} \\
\end{eqnarray*}
}

\problempart The probability that Shishir hit the can.

\solution{
\begin{eqnarray*}
\Pr(S) & = & \frac{\Pr (S \cap F) }{\Pr(F)}\\
& = & \frac{\Pr(F \mid S) \Pr (S)}{\Pr(F)} \\
& = & \frac{p_s}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k }
\end{eqnarray*}
}

\problempart The probability that exactly two of them hit the can.

\solution{
\begin{eqnarray*}
\Pr(\text{exactly two hit the can} \mid F) & = & 
\frac{\Pr(F \mid \text{exactly two hit can}) \Pr(\text{exactly two hit can})}{\Pr(F)} \\
& = & 
\frac{\Pr(\text{exactly two hit can})}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k }\\
& = & 
\frac{p_sp_d(1-p_k) + (1-p_s)p_dp_k + p_s(1-p_d)p_k}{p_s+p_d+p_k - p_sp_d - p_dp_k - p_sp_k + p_sp_dp_k }\\
\end{eqnarray*}
}


\end{problemparts}


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

%\problem
%
%Could set up a scenario consisting of a population of students,
%divided into male vs. female; freshmen vs. sophs vs. juniors
%vs. seniors; one or two other classifications.
%Ask them to give numbers (maybe we give them some and ask them to fill
%in the others), so that we achieve various independence conditions,
%for a randomly chosen student.
%E.g.:
%
%(a) Mutual independence.
%
%(b) Pairwise but not mutual.
%
%(c) Pairwise and 3-way but not 4-way?

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

\problem
% ( independent trials)

Imagine a random length n string of 0s and 1s. We would like to find a
method for determining the probability of a length k substring of all 0s. 

\problempart 

Develop a recurrence for the probability of seeing 00 in a random bit string
of length n.

\solution{
Let p(n) be the probability of seeing 00 in a random string of length n. Now 
segment across three possibilities for the start of the string: 
\begin{enumerate}
\item Starts with 00: This happens with probability $1/4$. When it happens, then we are done.
\item Starts with 1: This happens with probability $1/2$. When it happens, then our chance of having a 00 in the string is now p(n-1).
\item Starts with 01: This happens with probability $1/4$. When it happens, then our chance of having a 00 in the string is now p(n-2).
\end{enumerate}
All total, our recurrence is:
\[ p(n) = 1/4 + (1/2) p(n-1) + (1/4) p(n-2) \]
}

\problempart
Solve the recurrence.

\solution{

NOT FINISHED

From Victor:

The roots are $(1 + \sqrt{5})/4$ and $(1-\sqrt{5})/4$
and the particular solution is $p(n) = 1.$
I think the coefficients are something like
$(5+3\sqrt{5})/10$ and $(5-3\sqrt{5})/10$, 
but you should check this.

}



\problempart
Write a general recurrence for seeing a k-length string of all 0s within a
random string of length n.

\solution{
The strings partion by starting points again. The partions are strings that start with 1, 01, 001, 0001, .... 0000000 (of length k).

This means the recurrence is:

\[p(n) = \frac{1}{2^k} + \frac{p(n-1)}{2} + \frac{p(n-2)}{4} + ... \frac{p(n-i)}{2^i} 
+ ... \frac{p(n-k)}{2^k} 
\]
}


%
%I'm trying to formulate a problem involving the probability of
%occurrence of certain length k substrings in a random length n string
%of 0s and 1s. 
%
%E.g., what's the probability of the occurrence of a string of k
%consecutive 0s?
%
%Of any particular other string of length k?
%
%Is the probability the same for each such string?
%
%Are the events of having substring 0000000 (k of them) and 1111111
%independent?
%
%What about arbitrary pairs of length k strings?
%
%I haven't worked this out, am not sure of the answers.  Please work
%out.

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

\problem
% (Birthday problem)

%I'm trying to think of some variants of the Birthday Problem.
%
%E.g., how many students do we have to have to have a 95% probability
%of two with the same birthday?
%(Too easy, just plug into the final formula.)
%
%E.g., apply the nice estimate to some other problems, so they
%get a feeling for what the 50% point is for some real problems
%(various values of N and m)
%Or maybe the 95% point. 
%
%Is it tractable to get a decent estimate on the probability that there
%are three students out of 100 (or whatever) with the same birthday?
%(Seems too hard.)
%
%Problem 2 from pset 11 of last term involves birthdays, though only in
%a very trivial way.
%
%???
%
%Help...

Suppose there are 120 people in a room. Assume that their
birthdays are independent and uniformly distributed. As stated in
lecture notes, with probability $> 99\%$ there will be two that have
the same birthday.

Now suppose you find out the birthdays of all the people in the room
except one---call her ``Jane''---and find all 119 dates to be different.

\begin{problemparts}

\problempart 
What's wrong with the following argument:
\begin{quotation}\noindent
With probability greater than 99\%, some pair of people in the room have
the same birthday.  Since the 119 people we asked all had different
birthdays, it follows that with probability at greater than 99\% Jane has
the same birthday as some other person in the room.
\end{quotation}

\solution{
%\begin{solution}

Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
119 people we asked all have different birthdays.

It is true that $\prob{A} > 0.99$ (that is indeed the probability
spoken about in the lecture notes). However, that is the \emph{a
priori} probability, i.e., assuming all the birthdays are
uniform and independent, with no other constraints. The argument
above makes the erroneous assumption that event $A$ has
probability of at least $99\%$ even once we know that event $B$
holds. But once we know that event $B$ holds, the birthdays are
no longer independent. Thus $\prob{A \mid B}$ is not necessarily
equal to $\prob{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).
%\end{solution}
}


\problempart 
What is the actual probability that Jane has the same birthday
as some other person in the room?

\solution{
%\begin{solution}
Let $S$ be the set of birthdays of the 119 people in the room
other than Jane. By assumption, $|S| = 119$. Let $b$ be the date
of Jane's birthday. Since $b$ is uniformly distributed over a
set of size 365, and $b$ is independent of all the birthdays in
$S$, we have
\begin{align*}
\prob{b\in S\mid B} = \frac{|S|}{365} = \frac{119}{365} \approx
32.6\%,
\end{align*}
where $B$ is the event that the 119 people we asked all have
different birthdays.
%\end{solution}
}
\end{problemparts}


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

\problem
% (Probabilistic method, independence)
%[[[I like this one a lot.  We should also include something of this
%kind on the tutorial.]]]

% [[[From Sheldon Ross' book, "a first course in probability", p. 95]]]

% [[[Needs writing]]]

Consider a complete graph on $6$ vertices (a complete graph means there is
an edge between every pair of vertices).

We would like to prove the following theorem:
\begin{quote}
It is
possible to color the {\em edges\/} of the complete graph on 6
vertices, with colors red or blue, in
such a way that no set of 4 vertices has all of its $\left( \begin{array}{c}
4 \\ 2 \end{array} \right)$
connecting edges colored the same way.
Call such a coloring a "mixed-up" coloring.
\end{quote}

One way of solving this problem would be to actually exhibit a mixed-up
coloring.  But that's not the way they're going to do it in this
problem...

%The preferred way is to demonstrate that, if all the edges are
%colored by independent coin tosses (1/2 probability red, 1/2
%probability blue) for each edge, then the probability of a non-mixed-up
%coloring (one in which some 4-subset has all its edges colored the same)
%is strictly less than 1.
%That will imply that there has to be at least one mixed-up coloring in
%the sample space.
%
%Here are some parts that should guide them toward the solution:
%
%We might ask them to show their work, especially saying where they are
%using various facts about probability.

\begin{problemparts}

\problempart
Start by numbering all the 4-subsets of the vertices, 1,2,...
%Part (a):
How many 4-subsets are there? 

\solution{
[[[6 choose 4 = 15]]]
}

\problempart
Define $A_i$ to be the event that the ith 
subset (in the numbered list) has all its edges colored the same color.
Compute $\Pr(A_i)$. 

\solution{
[[[$2 times (1/2)^6 = 1/32$.  Uses independence, product rule.]]]
}

\problempart
%Part (c):
Give an upper bound for $\Pr( \cup_i A_i)$. 
Your bound should come out less than 1.

\solution{
%\begin{solution}
[[[15/32]]]

[[[Use Boole's law, just adding up the probabilities---that is, just
multiply the probability from part b by 6-choose-4.]]]
%\end{solution}
}

\problempart
Explain in your own words why that shows that a mixed-up coloring
exists. 

\problempart
(Optional)
Can you come up with a specific mixed-up coloring for this graph?

\problempart
%Part (f):
(Optional)
Try to generalize your reasoning in this problem to a condition on a
pair of numbers $n$ and $k$ that allows such a theorem to be proved (for
size $k$ subsets of an $n$-vertex graph).

%[[[Worked out in detail in Ross, if you want to check it.]]]
\end{problemparts}
\end{problems}

\end{document}
