\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}
\usepackage{changebar}
%\newcommand{\cbstart}{\chgbarbegin}
%\newcommand{\cbend}{\chgbarend}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\askaboutsolutions

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

\newcommand{\problembreak}{%
  \ifshowsolutions %
  \newpage
  \else
  \newpage
  \fi%
}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut13}
\newcommand{\tutnum}{13}
\newcommand{\tutdate}{May 5, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item What is your name?

\solution {

Sir Galahad of Camelot. 

}


\item What is your favorite color?

\solution {

Blue. No yel-- Auuuuuuuugh!

}

\item Suppose you gamble at a roulette wheel with an equal number of red and
black slots.  If you bet \$1000 on red the first spin and double your bet
on each successive spin. What is your expected winnings after any finite
number of spins?   

\solution {
\$0.
}

\item If you bet on red until the first time you win, how much do you expect
to win?

\solution {
\$1000.
}


\item Why wouldn't you try this strategy?

\solution {
You expect to spend an infinite stake before you win.
}

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage
\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\newcommand{\Ex}{\mbox{Ex}}
\begin{problems}

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

\problem Kyle is playing his favorite computer game: X-Files Adventures.
The game begins with Mulder in the main hallway of a space ship searching
for clues to the Truth.  The hallway has 5 doors.  One door exits the space
ship.  Another door leads back to the main hallway after a journey that
passes through one intermediate room.  A third door leads back to the main
hallway after a journey that passes through two intermediate rooms.  A
fourth door leads back to the main hallway after a journey that passes
through three intermediate rooms.  The fifth door leads directly back to
the main hallway.  What is behind each door is permuted at random using a
uniform distribution each time Mulder returns to the main hallway.

\bparts

\ppart How many times can Mulder expect to be in the main hallway before he
leaves the ship?  

\solution{ 

Let the random variable $R$ be the number of times Mulder selects a door
before he selects the exit.  We need to find $\Ex(R)$.  This is just a
mean-time-to-failure style calculation.  $\Ex(R) =
\sum_{i=0}^{\infty}\Pr(R>i) = \frac{1}{p} = 5$ Since Mulder expects to be
in the main hallway each time he selects a door, the desired value is 5. }

\ppart Any time Mulder enters a room (not the hallway), there is an even
chance that he will find a new clue (independent of whether he found a clue
in any previous time he may have entered this room). 

Let $J$ be the number of journeys Mulder takes before leaving the ship. 
Let the random variable $C_i$ be the number of clues Mulder finds on his
$i$th journey around the ship.  If $i > J$, we define $C_i = 0$.

Let the random variable $C$ the number of clues Mulder would find on any
trip through a uniformly chosen, non-exit door.  Argue that 
\[\Pr(C_i=x \mid J \geq i) = \Pr(C = x)\]
for all $i \geq 1$ and all $x$ in the range of $C$.

\solution {

If $J \geq i$ then Mulder selects a nonexit door on the $i$th try.  In that
case, $C_i$ and $C$ have the same distribution.  Thus, $\Pr(C_i=x) = \Pr(C
= x)$.  

}
\ppart How many clues should Mulder expect to find before he exits the ship?

\solution {

We want to compute $\Ex(C_1 + C_2 + \cdots + C_J)$.
In the previous part we have shown that the variables $C$, $C_i$, and $J$
have the properties necessary for the application of Wald's Theorem.
Therefore we know that
\[ \Ex(C_1 + C_2 + \cdots + C_J) = \Ex(C_1)\cdot\Ex(J).\]

Since the last door Mulder selects is always the exit, $J$ = $R-1$ (where
$R$ is as in the previous part). Thus, the expected number of journeys,
$\Ex(J) = 4$.

To find $\Ex(C_1)$, the expected number of clues in the first journey,
consider four equally likely cases.  Case $i$, $0 <= i <= 3$ corresponds to
a journey with $i$ intermediate rooms.  

By linearity of expectation, the expected number of clues found during the
journey is \[Ex(C_1) = \sum_{i=0}^{3}Ex(C_{1i})\] where $C_{1i}$ is 
the expected number of clues found during a journey through $i$
intermediate rooms.

Again we can use linearity of expectations again to decompose $C_{1i}$ into
$i$ individual rooms where Mulder can expect to find 1/2 a clue.  So on any
journey Mulder expects to find $\sum_{i=0}^{3} i/2 \cdot 1/4 = 3/4$ clues.
Therefore, Mulder expects to find $3$ clues before he exits the ship.

}

\eparts

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


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

\problem Psychological diagnosis of sociopaths is notoriously unreliable.
For example, a random psychologist is as likely to diagnose a normal
patient as sociopathic as he is to recognize that the patient is normal.
A random psychologist is actually somewhat \emph{less} likely to correctly
diagnose a real sociopath than not---sociopaths are really good liars.
Suppose the probability of an errant diagnosis by a random psychologist is
known. 

In these circumstances it might seem there was no reliable way to diagnose
sociopaths, but in theory there is a way---if we have a large enough
population of psychologists who reach their judgments independently.

\bparts

\ppart

Given a set of independent diagnoses of a patient by $n$ randomly chosen
psychologists, give a reliable function to decide if a patient is a
sociopath.

\solution{

Let $p_{fn}>1/2$ be the probability of a random psychologist diagnosing a
sociopath as normal (false negative).  Let $p_{fp}=1/2$ be the probability of
a random psychologist diagnosing normal patient as a sociopath (false
positive).  (Similarly, define the probability of a true negative diagnosis
to be $p_{tn} = 1 - p_{fp} = 1/2$ and the probability of a true positive
diagnosis to be $p_{tp} = 1 - p_{fn} < 1/2$.)

After $n$ independent trials, we will have $s$ ``sociopath'' diagnoses.
Compute the fraction $s/n$ such diagnoses.  Decide 1 (the patient is a
sociopath) if $s/n$ is closer to $p_{tp}$ than to $p_{fp}$. Decide 0
otherwise. In other words, let the ``decision value''
$d =\frac{p_{tp}+p_{fp}}{2}$. Decide 1 iff $s/n < d.$
Note that $p_{tp} < d < 1/2 = p_{fp}$ so we decide the patient is a
sociopath only if substantially \textbf{fewer} than 1/2 our chosen
psychologists say so!
}

\ppart

Use the binomial distribution to compute the probability of an erroneous
decision after $n$ trials, given that the patient is not a sociopath.

\solution{
We can compute the probability of a wrong decision given that the patient
is not a sociopath as follows:
\begin{eqnarray*}
\delta_{\textrm{norm}}
& = & \Pr(s/n < d) \textrm{ (The probability we decided the patient was a sociopath.)}\\
& = & \Pr(s < nd) \\
& = & F_{n,p_{fp}}(nd) \textrm{ (Cumulative binomial distribution for the random
variable s.)} \\
& = & F_{n,1/2}(d) \textrm{ (Note: } d < 1/2.) \\
& = & \frac{1 - d}{1 - 2 d}f_{n,1/2}(nd) \textrm{ (Theorem 4.1, Lecture 22.)} \\
\end{eqnarray*}
}

\ppart

Use the binomial distribution to compute the probability of an erroneous
decision after $n$ trials, given that the patient is a sociopath.

\solution{

We can compute the probability of a wrong decision given that the patient
is a sociopath as follows:
\begin{eqnarray*}
\delta_{\textrm{soc}}
& = & \Pr(s/n > d) \textrm{ (The probability we decided the patient was not
a sociopath.)}\\
& = & \Pr(\frac{n-s}{n} < 1-d)
	\textrm{ }(n-s = \textrm{number of ``normal'' diagnoses}) \\
& = & \Pr(n-s < n(1-d)) \\
& = & F_{n,1-p_{tp}}(n(1-d))
	\textrm{ (Note: } d > p_{tp} \Rightarrow  1 - d < 1 - p_{tp} )  \\
& = & F_{n,p_{fn}}(n(1-d))
	\textrm{ }(\Pr(\textrm{``normal''diagnosis})
             = 1 - \Pr(\textrm{``sociopath'' diagnosis})) \\
& = & \frac{1 - (1 - d)}{1 - (1-d)/p_{fn}}f_{n,p_{fn}}(n(1-d)) \textrm{ (Theorem 4.1, Lecture 22.)} \\
& = & \frac{dp_{fn}}{p_{fn} - 1 + d}f_{n,p_{fn}}(n(1-d))  \\
\end{eqnarray*}
}

\ppart

Bound the error of this decision method with a closed-form formula.

\solution{
\begin{eqnarray*}
\delta 
& \leq & \max\left( \delta_{\textrm{norm}}, \delta_{\textrm{soc}} \right ) \\
& =   & \max\left( \frac{1 - d}{1 - 2 d}           f_{n,1/2}   (nd),
              \frac{d p_{fn}}{p_{fn} - 1 + d} f_{n,p_{fn}}(n(1-d)) \right) \\
& = & \max 
\left( 
  \left( \frac{1 - d}{1 - 2 d}\right)
	 \frac{2^{\left( d \log_2\left( 2d \right) +
                 (1-d) \log_2\left( \frac{1}{2(1-d)} \right)\right) \cdot n}
              \overbrace{e^{a_n - a_{d n} - a_{n-d n}}}^{\sim 1}}
             {\sqrt{2 \pi d (1 - d) n}}, \right. \\
&  & \qquad \qquad 
  \left.
	\left( \frac{dp_{fn}}{p_{fn} - 1 + d} \right)
        \frac{2^{\left( (1-d) \log_2\left( \frac{p_{fn}}{1-d} \right) +
                 d \log_2\left( \frac{1-p_{fn}}{d} \right)\right) \cdot n}
              \overbrace{e^{a_n - a_{(1-d) n} - a_{n-(1-d) n}}}^{\sim 1}}
             {\sqrt{2 \pi (1-d) d n}}
\right) \\
\end{eqnarray*}
}

\ppart

How many independent diagnoses would be needed to get less than $1\%$ error?

\solution{

The question is under specified.  The number of diagnoses depends on
$p_{fn}$.  In the worst case, $p_{fn} = 1/2$ and sociopaths are completely
indistinguishable from normal patients.  Notice that in this case,
$d = 0$ and $\delta$ is undefined.  

If $p_{fn}$ is known and greater than 1/2 we can find $n$ by trial and error.

}

\ppart Is it plausible to assume that psychologists will make their
diagnoses independently?  Briefly explain.

\solution{

Not really.  The psychologists decisions are not independently random.
They are based on observations of the patients behavior.  A psychologist
diagnoses sociopathy if the patients exhibits certain behavior that the
psychologist believes differentiates a sociopath from a normal patient.  If
the patient's behavior is consistent from one trial to the next and a group
of psychologists agree on the behavior typical of sociopaths, then the
diagnoses will not be independent of each other.

}

\eparts

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

\end{problems}

\end{document}

