\documentstyle[12pt,twoside]{article}
\input{macros-course}

\begin{document}

\psol{12}{May 6, 1996}


%{\huge  ROUGH DRAFT }
\begin{problems}

\problem The Three-Cornered Duel.

{\it 
$A$, $B$, and $C$ are to fight a three-cornered pistol duel.  They all know 
that $A$'s chance of hitting the target is $0.3$, $C$'s is $0.5$ and $B$ 
never misses.  They are to shoot in the sequence $A,B,C$ and fire at their 
choice of target until one person is left standing.  Show that $A$ is better
off missing deliberately the first shot than attempting to hit either $B$ or 
$C$.

First consider a scenario where only $A$ and $C$ are left.
Let $S$ be the event that $A$ survives if $C$ shoots first.
}

$$
P(S) = 0.5(0.3+0.7*P(S)) \Rightarrow P(S) = 0.23
$$

Let's calculate $A$'s chances of survival under the three possible strategies.

\begin{enumerate}
\item If $A$ shoots $B$ first, then with probability $0.3$ he kills him and
 then we are in the above scenario.  If $A$ misses $B$, then $B$ kills $C$ and 
than $A$ has $0.3$ chance to hit $B$ and survive. So $A$'s probability of
survival under this strategy is $.3*P(S) + .7*.3 = .28$.

\item If $A$ shoots $C$ and kills him then he will be killed by $B$, while
if he misses, $B$ will kill $C$ and then $A$ has $0.3$ probability to get $B$
So $A$'s probability of survival is $0.7*.3 = 0.21$.

\item If $A$ misses deliberately then $B$ will kill $C$ and $A$ has probability
$0.3$ to survive.  

\end{enumerate}

So $A$ best strategy is to shoot in the air.  Under either strategy, $A$'s
chances are slim.  I wonder how he got himself into that.

\problem %conditional probabilities 

{ \it 
If you repeatedly flip a fair coin, what is the probability you see
the sequence HTT before you see the sequence HHT?  (Hint: the answer
is {\bf not} 1/2).

}

First note that with an infinite number of tosses, we will eventually get
either an HHT or an HTT with 4 exceptions:  all heads, all tails, alternating
heads and tails (starting with a head, and again starting with a tail).  
Note that this is 4 out of an infinite number of possible sequences and is 
therefore neglible.

Let $P_{HTT}$ be the probability that we see the HTT sequence before we see the HHT 
sequence.

The probability that we see the HHT sequence before the HTT sequnces 
is therefore $P_{HHT} = 1-P_{HTT}$.

Find $P_{HHT}$:

First let's assume that we start out with a head, $H_S$.   The probabilities
of getting the following sequences are:\\
\begin{itemize}
\item $P(H_SHH) = 1/4$
\item $P(H_SHT) = 1/4$ 
\item $P(H_STH) = 1/4$ 
\item $P(H_STT) = 1/4$ 
\end{itemize}

Let $Q $ be the probability of getting HHT when you start with a head. 
\begin{itemize}
\item $H_SHH$

Note that we get HHT unless we have an infinite number of heads (the probability
of this is neglible though).

\item $H_SHT$

We have HHT.

\item $H_STH$ 

We can get either HHT or HTT.  We're in the same position as when we started--
we see a head.

\item $H_STT$ 

We have HTT.
\end{itemize}

\begin{eqnarray*}
Q &=& P(H_SHH) + P(H_SHT) + P(H_STH) \cdot Q  \\
&=& \frac{1}{4} + \frac{1}{4} + \frac{Q}{4}  \\
&=& \frac{1}{2} + \frac{Q}{4} \\
\frac{3}{4} Q &=& \frac{1}{2} \\
Q &=& \frac{2}{3} \\
\end{eqnarray*}

Now, if we start with a series of $n$ tails (T), then when we see the
first head (H), we know the probability of seeing HHT before HTT is $Q$, 
so the probability of getting HHT before HTT if we start with $n$ tails
is $(1/2)^n (1/2) Q$ (n tails at $p=1/2$ each, followed by one head at $p=1/2$).

Now, the probability of getting a head for the first throw is $1/2$, and
the probability of getting a tail is $1/2$.

\begin{eqnarray*}
P_{HHT} & = & \frac{1}{2} Q + \sum_{i=1}^{\infty} (\frac{1}{2})^{n +1}Q \\
& = & \frac{1}{2} Q + \frac{1}{2} Q \\
& = &  Q \\
& = &  \frac{2}{3}\\
\end{eqnarray*}

So, $P_{HTT} = 1 - P_{HHT} = \frac{1}{3}$.


\problem The Prisoner's Dilemma.

{ \it
Three Prisoners $A$,$B$, and $C$ have applied for parole.  The parole
board has decided to release two of the three, and the prisoners know
this but not which two.  A warder friend of prisoner $A$ knows who are
to be released.  $A$ realizes that it would be unethical to ask if he
is going to be released, but thinks of asking for the name of {\em one
  prisoner other than himself} who is to be released. Before he asks
his chances are $2/3$, but he thinks that if he asks and the warder
says ``$B$ will be released'', his own chances will become $1/2$ since
either $A$ or $C$ will be the only remaining candidates.  So $A$
decides not to reduce his chances asking.  Is $A$'s argument correct?
Show what his chances are after asking.
}


Let $E_{AB}, E_{AC}, E_{BC}$ be the events that the corresponding prisoners are
released.  Each of these events had probability $1/3$.  
Let $A=E_{AB} \cup E_{AC}$ be the event that $A$ is released.
We wish to evaluate $P(A|W_B)$ where $W_B$ is the event that the warder says
$B$ 

\begin{eqnarray*}
P(A|W_B) = \frac{P((E_{AB} \cup E_{AC}) \cap W_B)}{P(W_B)} 
       & = & \frac{P((E_{AB} \cap W_B) \cup (E_{AC} \cap W_B))}{P(W_B)} \\
       & = & \frac{P(E_{AB} \cap W_B)}{P(W_B)}
\end{eqnarray*}

Note that $P(E_{AB} \cap W_B) = P(W_B|E_{AB})P(E_{AB}) = 1/3$
and $P(W_B) = P(W_B|E_{BC})P(E_{BC}) + P(W_B|E_{AB})P(E_{AB}) = 1/6+1/3$.
So the total expression evaluates to $\frac{1/3}{1/6+1/3} = 2/3$ and the
chances of $A$ are not reduced by asking after all.


  
 
\problem
{ \it
Show that if two events $A$ and $B$ are independent, then the events $A$ 
and $\overline B$ are also independent.
}

$A$ and $B$ independent means $\Pr(A\cap B) = \Pr(A)\cdot \Pr(B)$.
We have to show $\Pr(A\cap \overline B) = \Pr(A)\cdot \Pr(\overline B)$.
Since  $A$ is the disjoint union of $(A\cap B)$ and $(A \cap \overline B)$ 
we have 
\[\Pr(A) = \Pr(A\cap B) + \Pr(A \cap \overline B)\] 
and therefore 
\begin{eqnarray*}
 \Pr(A\cap \overline B) &=& \Pr(A) - \Pr(A\cap B) \\
  &=& \Pr(A) - \Pr(A)\Pr(B) \\
  &=& \Pr(A)(1-\Pr(B)) \\
  &=& \Pr(A)\Pr(\overline B) \\
\end{eqnarray*}
proving that $A$ and $\overline B$ are independent.

%independence 
\problem 

{\it Two numbers $x$ and $y$ are selected at random from the set
 $\{1,\ldots,100\}$.  Let the events $A$, $B$ and $C$be defined
 as follows: $A = \{x > 50\}$, $B = \{y > 50\}$ and $C=\{x > y \}$.
 Are the events $A$ and $B$ independent? Are $A$ and $C$ independent?
}

We of all we compute
$\Pr(A) = \Pr(B) = 50/100 = 0.5$ and 
$\Pr(C) = {100 \choose 2}\cdot 100^{-2} = 0.495$.

Since $\Pr(A\cap B) = (50\cdot 50)/100^2 = 0.25 = \Pr(A)\cdot\Pr(B)$,
$A$ and $B$ are independent.
However $\Pr(A\cap C) = \Pr(C) - \Pr(C\setminus A)
= {100 \choose 2}\cdot 100^{-2} - {50 \choose 2}\cdot 100^{-2} = 
0.3725 \neq \Pr(A)\cdot \Pr(C) = 0.247$,
so $A$ and $C$ are not independent.

\problem %binomial distribution
{\it
A communication system transmits binary information over a channel
that introduces random bit errors with probability $10^{-3}$.  The
transmitter transmits each information bit 5 times and a decoder
takes a majority vote of the received bits to decide on what the the
transmitted bit was. Find the probability that the receiver will make
an incorrect decision (simplify your answer to a number).
}

An incorrect decision will happen if 3, 4 or 5 bits are incorrect.

$p = 10^{-3}$

\[ 
P(incorrect) = {5 \choose 3}  p^3 (1-p)^2 
+ {5 \choose 4}  p^4 (1-p) + {5 \choose 5}  p^5 = 9.98 \cdot 10^{-9}
\]

\problem 

{\it Given an experiment with a fair, six-sided die, where the die
is rolled until a '6' has come up three times. 
}

\bparts

\ppart {\it What is the probability that at most $n$ rolls are needed? }

First let's find the probability that { \it exactly} $n$  rolls are needed.
If exactly $n$ are needed, then the final 6 must come on the $n$th roll,
and the other two on any of the other rolls.  There cannot be more than 
3 6's otherwise we wouldn't need $n$ rolls.  So what is the probability
of having a 6 on the $n$th roll, and 2 other sixes somewhere in the other $n-1$ rolls?

\[ P = { n-1 \choose 2} (\frac{1}{6})^3 (\frac{5}{6})^{n-3} \]

The probability that we need at least n rolls is therefore:

\[ P = \sum_{i=3}^n{ i-1 \choose 2} (\frac{1}{6})^3 (\frac{5}{6})^{i-3} \]

\ppart {\it What if the die must come up '6' three times in a row?  What is the
probability that at most $n$ rolls are needed? }

\problem {\it In a sequence of Bernoulli trials with success probability
$p$, find the probability that $a$ successes will occur before $b$
failures.  }


If we want exactly $a$ successes will occur before $b$ failures, then the
last trial must be a failure.  So we can arrange $a$ successes and $b-1$ 
failures in any way before the $b$th failure.


\[ P = { a+b-1 \choose a} p^a (1-p)^b \]

The probability of at least $a$ successes before $b$ failures is:
\[ P = \sum_{i=a}^{\infty} { i+b-1 \choose i} p^i (1-p)^b \]




\eparts


\problem 
{\it
In this problem, we will prove that there is a tournament
graph with the following bizarre property: for every set of $k$ people
in the tournament, there is a certain person who has beaten all of
them---this makes it hard it identify the best $k$ players!  We'll use
a technique called the {\em probabilistic method} where you prove
something exists by showing that that the probability it exists is not
0.

Consider an $n$-vertex tournament that is generated randomly by
assigning each edge a random (equally probable) direction.
}

\bparts

\ppart 
{\it Consider a certain set of $k$ people.  What is the probability a
particular other person beats all of them?

}

This person has probability $1/2$ to beat each player in the set
and the events are independent.
By product rule the probability that beats all of them is $(1/2)^k$

\ppart {\it What is the probability that {\em nobody} beats all of them?
}

This is the intersection of the complements of the events considered
in part (a). 
There are $n-k$ such events (one for each person not in the set)
and they are all independent.
So, the overall probability is $(1 - (1/2)^k)^{n-k}$.

\ppart {\it Using the union bound, upper bound the probability that there
is some set of $k$ people for which nobody else beats all of them?
}

Using the union bound we get the upper bound
\[{n \choose k}(1 - (1/2)^k)^{n-k}.\]

\ppart {\it Using the identities $(1-x)< e^{-x}$ and ${n \choose k} <
(en/k)^k$, simplify your answer to the previous problem.

}
The upper bound simplifies to 
\[(en/k)^ke^{-{n-k\over 2^k}}\]

\ppart {\it Find the smallest $n$ (as a function of $k$) that you can for
which the above quantity is less than $1$.
}

\ppart {\it Show that there is a tournament on $n$ vertices ($n$ you just
found) with the claimed bizarre property.
}

\eparts

\end{problems}

\end{document}


% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
