\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions

\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{12F}

%%%% FRI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% pset12 fall 01
\begin{problem} {\bf Attack of the Clones}
We want to determine the percentage of people $r$ who intend to watch
the {\em Episode II: Attack of the Clones}. Since we are still working
on our jedi mind tricks, we decide to conduct a poll.

\begin{problemparts}
\problempart Suppose that we poll 800 people. Use the Pairwise
Sampling Theorem to bound the confidence level that our estimated
value is within $\pm0.04$ of the actual value $r$.

\solution{The Pairwise Sampling Theorem gives us a bound on the
probability that the average of a sum of independent, identically
distributed random variables differs from their mean by more than a
certain amount $\epsilon$.  Call this probability $\delta$.  Our
confidence level, $c = 1 - \delta$. From the theorem we find,

\[
\pr{\abs{\frac{S_n}{n} - r} \geq \epsilon}
\leq 
\frac{\sigma^2}{n\epsilon^2}
\]

Recall that $\sigma^2$ is the variance of the random variables we are
summing. In this case, these are Bernoulli random variables, so the
variance is $p(p-1)$. Unfortunately, $p$ is also the value we are
trying to compute! However, we can take advantage of the fact that the
variance is maximized when $p=1/2$.  This gives us the following bound
on $\delta$.

\begin{eqnarray*}
\delta
& \leq & \frac{p(p-1)}{n\epsilon^2} \\
& \leq & \frac{0.5(0.5-1)}{n\epsilon^2} \\
& \leq & \frac{1}{4n\epsilon^2}
\end{eqnarray*}

Plugging in 800 for $n$, and $0.04$ for $\epsilon$ we find $\delta
\leq 0.195$.  Our confidence level is $1-\delta$, so $c \geq 1 -
0.195$, or 80\%.
}

\problempart Again using the Sampling Theorem, find the number of
people we would need to poll to if we wanted to be 95\% confident that
our estimated value was within 0.04 of the actual value $r$.

\solution{ 
In order to be at least 95\% confident in our measurement, we need the
probability that our measurement is outside the error margin to be
less than 0.05.  Using our formula from part \textbf{a}, it is easy to
see that $\delta \leq 0.05$ when the bound is less than 0.05.
\[
\delta \leq \frac{1}{4n\epsilon^2}  \leq  0.05
\]
Solving for $n$, we find, that in order to achieve this bound we have
to poll at least $3125$ people.

\begin{eqnarray*}
0.05 & \geq & \frac{1}{4n \cdot 0.04^2}\\
n & \geq & \frac{1}{4 \cdot 0.05 \cdot 0.04^2}\\
n & \geq & 3125
\end{eqnarray*}
}

\problempart Do you think it is reasonable to model people as
independent coin tosses? Why does the number of people chosen in this
poll not depend on the population size?

\solution{ 
This was intended to be a thought provoking question. The polling
theorems we have been using are based on the assumption that the
people polled are independent. However, people's behavior in voting is
often strongly correlated with other people in that region. For this
reason, it is important to be sure the people sampled in a poll are
genuinely independent, and the results are not extrapolated to a
larger population (for example, assuming a poll taken in California
applies to the entire United States).

The poll doesn't depend on population size or dependence between
individual people. It may be helpful to think of the people polled as
being colored balls in a (giant) box that we are sampling from.
Regardless of the number of balls in the box or whether or not the
color of some balls is dependent on that of other balls, the
probability that we draw a red ball is just the fraction of balls in
the box that are red.
}
\end{problemparts}
\end{problem}

%%%% FRI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
We really would like to poll less people. Rather than lower our
standards, we decide to recalculate the number of people using an
approximation of the binomial distribution.

Let $\delta$ be the probability that the experiment deviates more than
$\epsilon$ from the expected value, then

\begin{eqnarray*}
\delta \leq 2 F_{n,1/2} ((1/2 - \epsilon) n)\\
\end{eqnarray*}

\begin{problemparts} 

\problempart Suppose that we poll 800 people. How confident are we,
that our estimated value is within $\pm0.04$ of the actual value $r$?

\solution {Coming Soon.}

\problempart Find the number of people we would need to poll to if we
wanted to be 95\% confident that our estimated value was within 0.02
of the actual value $r$.

\solution{

\begin{equation}\label{delta bound}
\delta \leq F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n) +
   F_{n,1-\frac{1}{2}}((1-\frac{1}{2}-\epsilon) n)
 = 2 F_{n,\frac{1}{2}}((\frac{1}{2} - \epsilon) n).
\end{equation}

Now plugging in $\epsilon = 0.02$ into~(\ref{delta bound}) gives:
\begin{align*}
\delta \leq  2 F_{n,\frac{1}{2}}(0.48 n)
    & \leq 2 \cdot  \frac{1 - \alpha}{1 - 2\cdot\alpha} f_{n,1/2}(0.48 n)\\
    &  \approx 2 \cdot 0.6842 \cdot 2^{-n(1 - H(0.48))}/\sqrt{2\pi \cdot 0.48(1-0.48)n}\\
    & = 2 \cdot 0.6842 \cdot \frac{2^{-0.00115 n}}{1.2523 \sqrt{n}}.
\end{align*}

We want to poll enough people so that $\delta$ is less than $0.05$.
The easiest way is to plug in values for $n$, the number of people
polled:
\[
\begin{array}{c|l}
\mbox{$n$ = people polled} & \begin{array}{cc}
\mbox{upper bound on} \\
\mbox{probability poll is wrong}
\end{array} \\
\hline
1000 &  29.4\% \\
2000 &  9.3\% \\
3000 &  3.4\% \\
2500 &  5.6\% \\
2750 &  4.4\%\\
2616 &  5.004\%\\
2617 &  4.999\%
\end{array}
\]

So polling 2617 people is sufficient to determine public opinion to within
2\% with confidence of 95\%.  Again, the remarkable point is that the
population of the country has no effect on the poll size.  Whether there
are ten thousand people or a billion in a country, polling 2617 people
is sufficient!
}

\end{problemparts}
\end{problem}

%%%%%%%%%%%%%%  Fall 2000  PS 11.5   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%[[[expectation, variance]]]
%Spring 00, problem set 10.5, problem 5
\begin{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 slightly \emph{less} likely to correctly
diagnose a real sociopath than not---sociopaths are really good liars.

\begin{problemparts}

\problempart 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 judgements
independently.  Explain how to obtain a reliable diagnosis in this case.
Briefly explain why your method will be reliable, citing appropriate
results from class.  A qualitative answer is all that's required---you
need not come up with any numerical estimates or growth rates.

\solution{Get a reliable test by repeatedly asking randomly chosen
psychologists to do the diagnosis and computing the fraction, $f$, of
``normal'' diagnoses.  Let $s>1/2$ be the probability of a ``normal''
diagnosis on a sociopathic patient.  Diagnose normal if $f$ is closer
to $1/2$ than to $s$.

By diagnosing independently enough times, there is small probability that
$f$ differs from the expected value of a diagnosis by very much (the
expected value is either 1/2 or $s$ depending on whether or not the
patient is normal---we don't know which).  By the Law of Large Numbers, by
Chebyshev's bound, or by the estimation of the binomial distribution as
used in the Gallup Poll example in Lecture Notes, if we diagnose enough
times, we can make this probability as small as desired, so the
probability of a correct diagnosis can be as close to 1 as desired.
}

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

\solution{
Not really. It figures that some sociopaths would be particularly good
liars and be able to fool most psychologists.  Conversely, there figure to
be normal people whose anxious or defensive manner makes a sociopathic
diagnosis by many psychologists more likely.  Also, there may be some
specially expert psychologists whose diagnoses are more reliable than
average; this implies if one expert diagnoses ``normal,'' the diagnosis is
likely to be correct, making it more likely that another expert will also
correctly diagnose ``normal,'' so their diagnoses will not be independent
of each other.
}
\end{problemparts}
\end{problem}


\begin{problem}
Let $R:S\rightarrow \naturals$ be a random variable.
\begin{problemparts}
\problempart
Let $R'=cR$ for some positive constant~$c$.
If $\variance{R} = v$, what is $\variance{R'}$?
\solution{
\begin{eqnarray*}
\variance{R'} 
& = & \expect{{R'}^2} - \expectsq{R'} \\
& = & \expect{(cR)^2} - \expectsq{cR} \\
& = & \expect{c^2R^2} - c^2\expectsq{R} \\
& = & c^2\expect{R^2} - c^2\expectsq{R} \\
& = & c^2 v \\
\end{eqnarray*}
}
\problempart
If $\expect{R}=1$, how large can $\variance{R}$ be?

\solution{
The variance of R is unbounded. Suppose we let $R$ be a random variable
parameterized on $n$. $R$ takes on the value $n$ with probability $1/n$ and 0 otherwise. For all $n$, $\expect{R} = n/n = 1$ as required.  However, 

\[
\variance{R} = \expect{R^2} - \expectsq{R}= \frac{n^2}{n} - 1
\]

This quantity can grow arbitrarily large with $n$.  For a different
distribution, the variance can actually be \emph{infinite} and not
just unbounded.  Consider the random variable $R$ taking values over
$\set{0, 1, 2, \dots}$ with
\begin{eqnarray*}
\pr{R=i}&=&\frac{1}{i^3\zeta(2)}~~~~\forall i\geq 1\\
\pr{R=0}&=&1-\frac{\zeta(3)}{\zeta(2)}
\end{eqnarray*}
With $\zeta$ being the Reimann Zeta function,
\[
\zeta(k)=\sum_{i=1}^\infty\frac{1}{i^k}
\]
It's easy to see that this sum converges for $k>1$ and is strictly
decreasing in $k$, so $\frac{\zeta(3)}{\zeta(2)}<1$.  (Incidentally
$\zeta(2)=\frac{\pi^2}{6}=1.644...$ and $\zeta(3)=1.202...$).

$R$ is a well defined random variable since
\begin{eqnarray*}
\sum_{i=0}^\infty\pr{R=i}&=&\pr{R=0}+\sum_{i=1}^\infty\pr{R=1}\\
&=&1-\frac{\zeta(3)}{\zeta(2)}+\sum_{i=1}^\infty\frac{1}{i^3\zeta(2)}\\
&=&1-\frac{\zeta(3)}{\zeta(2)}+\frac{\zeta(3)}{\zeta(2)}=1
\end{eqnarray*}
Also
\begin{eqnarray*}
\expect{R}&=&\sum_{i=0}^\infty i\pr{R=i}\\
&=&0\left(1-\frac{\zeta(3)}{\zeta(2)}\right)+\sum_{i=1}^\infty\frac{i}{i^3\zeta(2)}\\
&=&0+\frac{1}{\zeta(2)}\sum_{i=1}^\infty\frac{1}{i^2}=1
\end{eqnarray*}
But
\begin{eqnarray*}
\variance{R}&=&\expect{(R-\expect{R})^2}\\
&=&\sum_{i=0}^\infty (i-1)^2\pr{R=i}\\
&>&\sum_{i=2}^\infty (i-1)^2\pr{R=i}=\sum_{i=2}^\infty
\frac{(i-1)^2}{i^3\zeta(2)}\\
&>&\sum_{i=2}^\infty\frac{(i-1)^2}{(i-1)^3\zeta(2)}=\frac{1}{\zeta(2)}\sum_{i=2}^\infty\frac{1}{i-1}=\infty\\
\end{eqnarray*}
From divergence of the harmonic series.
}

\problempart
If $R$ is always positive (nonzero), how large can $\expect{1/R}$ be?

\solution{ 
$\expect{1/R}$ is maximized at 1 when $R = 1$ with probability $1$.
Intuitively, this can be seen by trying to shift some of the
probability mass away from $1$.  No matter how you do it, you will
always wind up with an expectation that is less than $1$.

Formally, we can prove this as follows. Suppose $\pr{R=1} = 1-\delta$
for some $\delta > 0$. Then
\begin{eqnarray*}
\expect{R}
& = & 1\cdot(1-\delta) + \sum_{i=2}^{\infty}\frac{1}{n}\cdot \pr{R=n}\\
& \leq & 1\cdot(1-\delta) + \sum_{i=2}^{\infty}\frac{1}{2}\cdot \pr{R=n}\\
& \leq & 1\cdot(1-\delta) + \frac{1}{2}\sum_{i=2}^{\infty}\pr{R=n}\\
& \leq & 1\cdot(1-\delta) + \frac{1}{2}\cdot\delta\\
& \leq & 1-\delta\cdot\frac{3}{2}.\\
\end{eqnarray*}

So, for any positive $\delta$, $\expect{R}$ is less than 1. Therefore,
the given distribution maximizes $\expect{1/R}$.  }

\end{problemparts}
\end{problem}

\appendix
\section{Appendix}
\setcounter{secnumdepth}{0}

%%%%%%%%%%%%%%%%%%% PAIRWISE IND. SAMPLING %%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}
Let
\[
S_n \eqdef \sum_{i=1}^n G_i
\]
where $G_1, \dots, G_n$ are pairwise independent variables with the same
mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Snx}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x}
    \leq \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Approximations for the Binomial Distribution (lecture notes 10)}

\begin{lemma*}
\begin{equation}\label{Fbyf}
F_{n, p}(\alpha n) \leq
\left(\frac{1 - \alpha}{1 - \alpha/p}\right) f_{n, p}(\alpha n)
\end{equation}
for $\alpha < p$.
\end{lemma*}

\begin{lemma*}
\begin{equation}\label{unbiased alpha term}
f_{n,1/2}(\alpha n) = \binom{n}{\alpha n}2^{-n} \sim
2^{-n(1 - H(\alpha))}/\sqrt{2\pi \alpha(1-\alpha)n}.
\end{equation}

where
\[
H(\alpha) \eqdef - (\alpha\log_2 \alpha + (1-\alpha)\log_2 (1-\alpha)).
\]
\end{lemma*}

\end{document}


