\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}}}

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

\newcommand{\workspace}{\bigskip \bigskip \bigskip \bigskip}

\askaboutsolutions

\ifshowsolutions 
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
  \typeout{}
  \typeout{Solutions *INCLUDED*}
  \renewcommand{\solution}[1]{
    \textbf{Solution.} \par %
    #1
    \mbox{} \\
    \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
    \raisebox{-0.25\baselineskip}{$\square$}%
    \hspace*{1ex}\ignorespaces\hrulefill%
  }
\else
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*}
  \renewcommand{\solution}[1] {
  	\workspace
  }
\fi
    

%\renewcommand{\solution}[1]{%
%  \ifshowsolutions %
%%  \cbstart
%%  \cbend
%  \nopagebreak%
%  \else
%%  \vspace*{2in}
%    \fi}

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


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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut11}
\newcommand{\tutnum}{11}
\newcommand{\tutdate}{April 21, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\begin{enumerate}
\item Write your name:

\bigskip

\item %
  (Rosen, Section 4.4, Exercise 13) What is the probability that a five card poker hand contains at least one ace?

\solution{
\[1 - 
\frac{\left( \begin{array}{c} 48 \\ 5 \end{array} \right) }
{\left( \begin{array}{c} 52 \\ 5 \end{array} \right) } \]
}

  \vspace*{3in}

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

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

\begin{problems}


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

% Source: Spring 99

\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.

\begin{problemparts}

\problempart 

%Part (a):
The \emph{Maxwell-Boltzmann} model assumes that the particles are 
\emph{distinguishable}, say, numbered $1,2,\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, 
independently of where the other particles are.
Nature follows these rules when all the particles are
distinguishable (e.g., different atoms).

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{
Each of the $r$ particles can be in any of the $n$ boxes, so
\[
n^r
\]
}

\problempart 
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?]]]
% rjr: It is saying that He II acts as a Boson.

%Part (b): 
How many possible states are there under the Bose-Einstein model?

\solution{
$\binom{n+r-1}{r}$ 

Balls in bins, stars and bars.
}


\problempart
%Part (c):

There is another variation of models for particle system behavior. The
\emph{Fermi-Dirac} model assumes that the particles are indistinguishable, 
but that no two particles can occupy the same box. 
(This is known as the \emph{Pauli exclusion principle}.) 

How many possible states are there under the Fermi-Dirac model?

%Ans:
\solution{
The configurations are simply determined by which $r$ of the $n$ boxes
are occupied, so
\[
\binom{n}{r}
\]
}


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

%Part (d):
Prove that in the Maxwell-Boltzmann model, 
%the fraction of empty boxes is about
the probability of a given box being empty is about
\[
e^{-\lambda}
\]
Assume that $n$ is very large.

\solution
{
The probability that a given box 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 boxes.
}

\problempart
%Part (e):
Prove that under Bose-Einstein Statistics, 
%the fraction of empty boxes is about
the probability of a given box being empty is about
\[
\frac{1}{1+\lambda}
\]
Again, assume $n$ is very large.

%Ans:
\solution{
The probability that a given box is empty is just the ratio of
the number of states in which that box is empty to the total number
of states.
The total number of states is $\binom{n+r-1}{r}$.
The number of states in which the given box is empty is
the same as the number of states for a system with $n-1$ tiny boxes
and $r$ particles, namely, $\binom{n+r-2}{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.
}

\problempart
%Part (f):
Under Fermi-Dirac Statistics, 
what is the probability of a given box being empty?

%Ans:
\solution{
This is simply the probability that the box is not one of the $r$
filled boxes, so
\[
\frac{n-r}{n} = 1 - \frac{r}{n} = 1 - \lambda
\]
}


\problempart
%Part (g):

It turns out that the Fermi-Dirac model holds for electrons, protons, 
and other ``solid'' particles called {\em fermions}; they follow the
aptly-named Fermi distribution. The Bose-Einstein model holds for 
photons and phonons and other particles that can effectively 
interpenetrate. These are called {\em bosons} and follow the resulting
Bose distribution. 

In `classical' non-quantum-mechanical situations, however, both of these
models approach the Maxwell-Boltzmann model. In this case, `classical' 
means ``high energy,'' which equates to a small $\lambda$.
When $\lambda$ is large, $1 - \lambda < e^{-\lambda} < \frac{1}{1+\lambda}$.  
In other words, Maxwell-Boltzmann predicts a less spread-out
gas than you would actually find for fermions, 
and a more spread-out gas than you would actually find for bosons. 
But as $\lambda$ decreases, 
these differences become less significant.

Show that for very small $\lambda$, the probability of a box being empty
is approximately the same for all three models.

%Ans:
\solution{
For Boltzman distribution, $e^{-\lambda}$ is approximately $(1-\lambda)$ 
for small $\lambda$, as used in the above solution.

The Bose distribution produces $\frac{1}{1+\lambda}$, which a Taylor series
expansion around $0$ easily shows to be $1 + (-\lambda)$.

The Fermi distribution directly predicts a probability of $(1-\lambda)$.

\medskip

\emph{A note on the Taylor series expansion}: This is a useful tool for mathematical
approximations, especially in physics. It lets you generate a polynomial 
approximation of a function near a particular point to arbitrary accuracy.
The basic expansion for $f(x)$ around a point $\alpha$ is:
\[
f(x) \; = \; f(\alpha) \; + \; 
\frac{f'(\alpha)}{1!} \cdot (x - \alpha) \; + \;
\frac{f''(\alpha)}{2!} \cdot (x - \alpha)^2 \; + \;
\frac{f'''(\alpha)}{3!} \cdot (x - \alpha)^3 \; + \;
\ldots
\]
It is easy to see that the first two terms form a linear approximation of
the original function based on its value at $x = \alpha$.

For values of $x$ close to $\alpha$, the higher-order terms are not 
significant, since $(x - \alpha)$ is small. In fact, the error in 
truncating the summation at the $n^{th}$ term (of degree $(n - 1)$)
is less than 
\[
\abs{\frac{f^{(n)}(\alpha)}{n!} \cdot (\gamma - \alpha)^n}
\]
for some $\gamma$ between $\alpha$ and $x$.

An expansion for ``small values,'' around $x = 0$, is somewhat simpler:
\[
f(x) \; = \; f(0) \; + \; 
f'(0) \cdot x \; + \;
\frac{f''(0)}{2!} \cdot x^2 \; + \;
\frac{f'''(0)}{3!} \cdot x^3 \; + \;
\ldots
\]
The error in ending this summation at the $n^{th}$ term is less than 
\[
\abs{\frac{f^{(n)}(0)}{n!} \cdot \gamma^n}
\]
for some $\gamma$ between $0$ and $x$.
}

\bigskip

Interestingly, the Fermi-Dirac model implies that gases
made up of just one atom behave differently than gases made up of
more than one atom.  In particular, the {\em entropy} of a gas, a
physically measurable quantity, depends on the number of states. This
fact is supported by experiment.


\end{problemparts}

\newpage

\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{
\[
\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{
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{
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{
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}

\end{problems}

\end{document}

\end{input}





