\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
%change it back!
%\input{../macros-course}
%\newcommand{\ssl}{
%\medskip
%\textbf{Solution:}
%\medskip
%}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\given}{\mid}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}
\newcommand{\Intersect}{\bigcap}
\newcommand{\Union}{\bigcup}


%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}
%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\handout{tut12}{Mini-Quiz 12}{May 4, 2001}
\begin{enumerate}
\item Write your name:
\item What are each of the following probabilities when $n$ independent Bernoulli trials are carried out with probability of success $p$?
\begin{itemize}
\item The probability of no failures
\item The probability of at most one failure
%\item The probability of at least two failures
\end{itemize}
\end{enumerate}

\newpage
\thispagestyle{empty}
\mbox{}
\setcounter{page}{0}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{tut12}{Tutorial 12 Problems}{May 4, 2001}


\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{\em Polling}

Suppose you are heading a scientific polling organization. Candidate
Al Gore wants you poll a group of voters in Florida to determine his
popularity.  Furthermore, he would like a margin of error of 1.5\%.  How
large a sample size do you need to be able to tell him with 95 percent
confidence that the error attributable to sampling and other random
effects is within plus or minus 1.5 percentage points?

\solution{ 
Let $p$ be the probability that a person will vote for Al
Gore, $\epsilon$ be the margin of error and let $\delta$ be the
probability that our result lies outside this margin.  Therefore we
have $\epsilon = 0.015$, and $\delta = 0.05$.  Since we get the
maximum value of $\delta$ when $p=0.5$ 

\begin{eqnarray*}
\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) \\
	& = &   2 F_{n\frac{1}{2}}((\frac{1}{2} - 0.015) n)\\
	& = &   2 F_{n\frac{1}{2}}(0.485n)\\
	& \leq & 2 \frac{1 - 0.485}{1 - \frac{0.485}{0.5}} f_{n,0.5}(0.485n)\\
        & = &   2 \cdot 17.167 f_{n,0.5}(0.485n)
\end{eqnarray*}

Solving for $n$, we get $n=300,455$. Therefore, if the sample size is $n\geq 300,455$ we get the desired property.
}

\problem
{\em The Probabilistic Method}

A round robin tournament of $n$ contestants is one in which each of the
$\binom{n}{2}$
pairs of contestants play each other exactly once, with the outcome of any play
being that one of the contestants wins and the other loses. For a fixed integer
$k$, $k < n$, a question of interest is whether it is possible that the
tournament outcome is such that for every set of $k$ players there is a player
who beat each player of this set. Show that if:
\[ \binom{n}{k} \left[1 - \left(\frac{1}{2}\right)^k \right]^{n-k} < 1 \]
then such an outcome is possible.

\begin{problemparts}

\problempart

Start by numbering the  sets of $k$ contestants. How many such sets are there?

\solution{\ssl
\[
\binom{n}{k}
\]
}

\problempart

Let $B_i$ be the event that no contestant beat all the $k$ contestants in set
$i$. Compute $\Pr(B_i)$. (Note that you must choose probabilities for each match
in order to compute this).

\solution{\ssl
Suppose that the results of the game are independent and that each game is
equally likely to be won by either contestant. This is an arbitrary choice, but
it is easy to work with (and any probability will suffice to prove existance).
The probability that a person inside group $i$ beats everyone in $i$ is 
clearly $0$. The probability that a person outside group $i$ beats everyone
in $i$ is $\left(\frac{1}{2}\right)^k$, so the probability the person they did not
beat everyone in $i$ is $1 - \left(\frac{1}{2}\right)^k$. There are $n-k$ people
outside of group $i$. Thus, $B_i$ has probability 
\[
\left[1 - \left(\frac{1}{2}\right)^k \right]^{n-k}
\]
}

\problempart

Give an upper bound on $\Pr(\cup B_i)$.


\solution{\ssl
Then use Boole's inequality to bound: $\Pr(\cup B_i) \leq \sum \Pr(B_i)$.
In other words, $\Pr(\cup B_i)$ can be no greater than if all of the
$B_i$ are disjoint. (Overlap will merely reduce the total probability of
the union). Since the expression for $B_i$ does not depend on $i$ -- the
probability is the same for each $k$-sized group $i$ -- the sum of all of
the $B_i$ is simply 
\[
\binom{n}{k} \left[1 - \left(\frac{1}{2}\right)^k \right]^{n-k}
\]
}

\problempart

Explain why this result can be used to prove the existence of the desired
tournament outcome.

\solution{\ssl
Probabilistic proof. If the overall probability of $\cup B_i$ is less 
than 1 then there must be an occurrence that is not in $\cup B_i$. It
does not matter that we chose the probabilities arbitrarily; the fact that
there is \emph{any} probaility at all left over means some outcome that we
had not accounted for is possible.

\medskip 
For interest, some numbers that work are:

$k = 1, n = 3; k = 2, n = 21;  k = 3, n = 33; k = 4, n = 46;$ \\
$k = 5, n = 59; k = 6, n = 72; k = 7, n = 85; k = 8, n = 98$
}

\end{problemparts}

\problem {\em Statistical Mechanics} studies the behavior of large systems of
particles (such as a kettle of boiling water).  One of the most basic
physical systems is a {\em gas:} a collection of particles (electrons,
atoms, photons) floating around in a large container. 

One way to describe this system is to divide the container into lots
of tiny boxes.  
The ``state'' of the system says how the particles are distributed among
the tiny boxes. 
The system is equally likely to be in any one of its states (assuming
they all have the same energy, but discussing this would take us too
far afield).  
Many facts about the aggregate behavior of the system arise from
averaging over all its possible states.

It turns out that different kinds of particles exhibit different kinds
of aggregate behavior.
These differences can be explained by different assumptions about the 
system states.

The {\em Maxwell-Boltzmann\/} model assumes that the particles are 
{\em distinguishable}, say, numbered $1,\ldots$.
A state is described by where particle $1$ is, where particle $2$ is,
and so on. 
In the Maxwell-Boltzmann model, a single particle is equally
likely to be in any one of the tiny boxes.
Nature follows these rules when all the particles are
distinct (e.g., different atoms).

\bparts

\ppart Suppose that there are $r$ particles in
the container and $n$ tiny boxes.
How many possible states are there under the Maxwell-Boltzmann model?

\solution{
Number of states: $n^r$
}

On the other hand, the {\em Bose-Einstein\/} model assumes that the
particles are {\em indistinguishable\/}.
A state is described by the {\em number\/} of particles appearing in
each tiny box. 
In the Bose-Einstein model, all the distributions of numbers of
particles in tiny boxes are equally likely.
Gases made up of photons obey this model.
% Photons are a kind of {\em Boson}
% and so is Helium 2 (the superconducting stuff).
% [[[ What is this last sentence saying?]]]

\ppart How many possible states are there under the Bose-Einstein model?

\solution{
Using the stars and bars model, we get that the number of possible states is ${n+r-1 \choose r}$.
}

The Maxwell-Boltzmann and Bose-Einstein models predict very different
aggregate system behavior.
For example, suppose $r/n = \lambda$ is the average number of particles per cell.  

\ppart Prove that in the Maxwell-Boltzmann model, the fraction of empty
cells is about
\[
e^{-\lambda}
\].

\solution{
The probability that a given cell is empty is just $(1 -
\frac{1}{n})^r$.
Using the approximation $(1 - \frac{1}{n}) \approx e^{-\frac{1}{n}}$
(valid for large $n$), 
this yields approximately $e^{-\frac{r}{n}} = e^{-\lambda}$.
This probability should be close to the fraction of empty cells.
}

\ppart Prove that under Bose--Einstein Statistics, the fraction of empty
cells is about
\[
\frac{1}{1+\lambda}
\]

\solution{
The probability that a given cell is empty is just the ratio of
the number of states in which that cell is empty to the total number
of states.
The total number of states is ${n+r-1 \choose r}$.
The number of states in which the given cell is empty is
the same as the number of states for a system with $n-1$ tiny boxes
and $r$ particles, namely, ${n+r-2 \choose r}$.
The ratio works out to $\frac{n-1}{n+r-1} = \frac{1 - \frac{1}{n}}{1 +
\frac{r}{n} - \frac{1}{n}}$.
Since we assume $n$ is very large, 
this is approximately $\frac{1}{1 + \frac{r}{n}}$, as needed.

When $\lambda$ is large, the first quantity is a lot less than the
second.  In other words, Maxwell-Boltzmann predicts a more spread-out
gas than you would actually find.
}

\eparts

\problem Remember the game demonstrated in lecture: David shows you two
envelopes, each lying face down on a table.  He tells you there are
natural numbers between zero and $n$ in each envelope, and the numbers are
not equal.  You choose an envelope, and David shows you the number
written in it.  He now tells you that you can either choose to stay with
that envelope, or switch to the other envelope.  You {\em win} if the
number in the envelope you finally choose is the larger of the two.

\bparts

\ppart A \emph{randomized strategy} for you in this game is a function
that, for each number $i$, assigns a probability $p_i$ of switching {\em
given} that the number in the envelope you picked first was $i$.  Prove
that the strategy described in class for winning with probability at least
$1/2 + 1/2n$ is \emph{optimal} for you.  In particular, if David picks $i
\in [0,n-1]$ with uniform probability, and then places $i$ and $i+1$ in
each envelope with equal probability, then your probability of winning is
\emph{at most} $1/2 + 1/2n$.

\solution{Let $p_i$ denote the probability that you switch if you see the
number $i$.  Then, the probability that you win if David picks the pair
$(i,i+1)$ is the probability that you will see the smaller number and
switch, or that you will see the bigger number and stay.  Since the
probability of picking either number is $1/2$, the probability that you
win is
\[(1/2)p_i + (1/2)(1-p_{i+1}).
\]

Then, the probability that you win is:
\[
\sum_{i=0}^{n-1} \frac{1}{n} \left(\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})\right)
= \frac{1}{2} + \frac{1}{2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= \frac{1}{2} + \frac{1}{2n} (p_0 - p_n) \leq \frac{1}{2} + \frac{1}{2n}
\]
}

\ppart Now suppose the numbers from the problem above are drawn from the
set of all natural numbers, $\naturals$.  Design a randomized strategy for
playing this game such that, no matter what two numbers, $i \neq j$, that
David might pick, you will still have \emph{more} than an even chance of
winning.

\solution{Choose \emph{any} distribution on $\naturals$ with a positive
probability, $p_i$, assigned to each $i \in \naturals$, so that larger
numbers have smaller probability.  For example, let $p_i = 2^{-i-1}$.  Now
suppose that David chooses the pair $\set{i,j}$ with $i<j$.  Then as
above with this randomized strategy, the probability that you win is the
probability that you see $i$ and switch, or that you see $j$ and don't
switch, namely,
\[
\prob{\mbox{win}} = \frac{1}{2}p_i +\frac{1}{2}(1-p_{j}) =  
\frac{1}{2} + \frac{1}{2}(p_i - p_j)  > \frac{1}{2}.
\]

\iffalse

Of course in this case, in contrast to the case when the choice of numbers
is bounded, David can force the probability that you win as close
to---but not equal to---1/2 as he chooses, by choosing sufficiently large
$i,j$,

\fi

}

\eparts

\problem Let $A,B,C$ be events over some probability space, and let
$I_A,I_B,I_C$ be the corresponding index variables, e.g., the event
$\set{I_A = 1}$ is the same as the event $A$ and $\set{I_A = 0}$ is the
same as $\bar{A}$.  Prove that $A,B,C$ are mutually independent iff the
random variables $I_A,I_B,I_C$ are mutually independent.

\solution{
($\Longrightarrow$):  
\begin{eqnarray*}
\lefteqn{\prob{I_A = 1 \wedge I_B= 0 \wedge I_C = 1}}\\
 & = & \prob{A \intersect \bar{B} \intersect C}\\
& = & \prob{(A \intersect C) - B}\\
& = & \prob{A \intersect C} - \prob{A \intersect C \intersect B}\\
& = & \prob{A} \cdot \prob{C} - \prob{A} \cdot \prob{C} \cdot \prob{B}
    \hspace{0.5in}\mbox{[because $A,B,C$ independent]}\\
& = & \prob{A} \cdot \prob{C} (1 -  \prob{B})\\
& = & \prob{A} \cdot \prob{C} \prob{\bar{B}}\\
& = & \prob{I_A = 1} \cdot \prob{I_C = 1} \prob{I_B = 0}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 0} \cdot \prob{I_C = 1}
\end{eqnarray*}
and similarly for any other three binary values in place of 101.

($\Longleftarrow$):  
\begin{eqnarray*}
\prob{A \intersect B \intersect C} & = & 
        \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 1}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 1 } \cdot \prob{I_C = 1}\\
& = & \prob{A} \cdot \prob{B} \cdot \prob{C}
\end{eqnarray*}
Also,
\begin{eqnarray*}
\prob{A \intersect B} & = & \prob{A \intersect B \intersect C}
                       + \prob{A \intersect B \intersect \bar{C}}\\
& = & \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 1} + \prob{I_A = 1 \wedge I_B = 1 \wedge I_C = 0}\\
& = & \prob{I_A = 1} \cdot \prob{I_B = 1} \cdot \prob{I_C = 1}
       + \prob{I_A = 1} \cdot \prob{I_B = 1} \cdot \prob{I_C = 0}\\
& = & \prob{A} \cdot \prob{B} \cdot \prob{C} + \prob{A} \cdot \prob{B}
                       \cdot \prob{\bar{C}}\\
& = & \prob{A} \cdot \prob{B} (\prob{C} + \prob{\bar{C}})\\
& = & \prob{A} \cdot \prob{B}
\end{eqnarray*}
and similarly for ${B \intersect C}$ and ${A \intersect C}$.
}

\end{problems}



\end{document}
