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

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial12}{Solutions for Tutorial 12}{May 12, 1997}

\begin{problems}

\problem 

{ \it
You have found favor in the eyes of a king from the small, unknown country,
called Xyzzy.  The king likes to reward his subjects for their cleverness
and intelligence, and so he has offered you the following opportunity:

You are given $n$ gold coins and $n$ silver coins, and two clay jars.  You
may place the coins in the jars in any way you like, and will be given the 
opportunity to take a coin from one of the jars.  (You have an equal likelihood
of choosing either jar, and then an equal likelihood of choosing any coin
from that jar.)  How should you place the coins so as to
maximize the probability of getting a gold coin?
}

Put one gold coin in one jar, and the rest of the coins in the other jar.
The probability of getting a gold coin is then 

$P = \frac{1}{2} (1.0) + \frac{1}{2} \frac{n-1}{2n-1}$

A problem like this was given to Alex in a job interview (so now you too can
impress your future employer ). 

Proving this requires partial integrals, so the way you'd have solved this
(in reasonable time) was to observe trends in how moving coins into different
bins affected your probability.

\problem

In another small, unknown country with unknown name an unknown king
is known to have a known number $n$ of bags of gold coins hidden away in
his treasury.
It is also known that each bag contains exactly $n$ gold coins.
A well-known craftsman has been commissioned by the king to create a
jewel-encrusted sculpture.  What the king doesn't know is that the
craftsman is also a counterfeiter.  Unfortunately for the counterfeiter,
he doesn't know how to countefeit jewels or anything else that would
be useful in faking part of his sculpture.  He does, however, know that
he will have access to the treasury to deposit his sculpture and that
he will have the opportunity to replace as many of the king's gold coins
with counterfeit coins as he likes.  He also knows that before he can
flee the (small, unknown) country, a well-known auditor will give the bags a check.
The craftsman knows that the check will consist of choosing one coin uniformly at
random from each of the bags and giving it to a well-known expert to check
whether it is counterfeit.
He also knows that each selected coin is checked carefully enough
that if it is one of his counterfeits, he will get caught.
He doesn't know what the best strategy is for distributing coins to
minimize his chances of getting caught (crafstman, yes; counterfeiter, yes;
mathematician, no), so he determines to replace exactly $m$ coins from
each bag with counterfeit coins.  He does not yet know what value of $m$
he will use.
\bparts
\ppart
For each value of $m$, what is the probability that he will get caught?

The probability that he {\it doesn't} get caught is the probability that
the expert chooses all good coins.  $P(\overline{caught}) = (\frac{n-m}{n})^n$.

So, $P(caught) = 1- (\frac{n-m}{n})^n$.

\ppart
Give an expression for what your answer above approaches as $n$ approaches
infinity.

First, let's show that 
$\lim_{n \rightarrow \infty} (\frac{n-m}{n})^n = e^{-m}$

\begin{eqnarray*}
Y &=& \lim_{n \rightarrow \infty} (\frac{n-m}{n})^n \\
\ln (Y) & =& \ln [\lim_{n \rightarrow \infty} (\frac{n-m}{n})^n] \\
& =& \lim_{n \rightarrow \infty} \ln [(\frac{n-m}{n})^n] \\
& =& \lim_{n \rightarrow \infty} n \ln (\frac{n-m}{n}) \\
& =& \lim_{n \rightarrow \infty} \frac {\ln (\frac{n-m}{n})}{1/n} \\
\end{eqnarray*}

Using L'Hopital's rule:

\begin{eqnarray*}
Y & =& \lim_{n \rightarrow \infty} \frac {\ln (\frac{n-m}{n})}{1/n} \\
& =& \lim_{n \rightarrow \infty} \frac {(\frac{1}{\frac{n-m}{n}}) \cdot 
\frac{m}{n^2}}{\frac{-1}{n^2}} \\
& =& \lim_{n \rightarrow \infty} \frac {-m}{\frac{n-m}{n}}  \\
& =& -m \\
\end{eqnarray*}

Since $\ln Y = -m$, $Y = e^{-m}$, and 

$\lim_{n \rightarrow \infty} (1- \frac{n-m}{n})^n = 1- e^{-m}$



\ppart
Use the expression from the above part to compute the craftsman's
expected ill-gotten gain.  What value of $m$ maximizes this?

The gain for $m$ coins per bag, and $n$ bags is $nm$.  The expected value
is the sum over $m$ of the profit times the probability of getting away with
it.

\[ Ex(gain)  = \sum_{i=0}^{m} i n (\frac{n-i}{n})^{n}
\]

\eparts


\newpage
\problem Statistical Mechanics

Statistical Mechanics is the branch of Physics that studies the statistical 
behavior of large collections of particles (e.g a gas in a container, an 
electron cloud in a conductor, radiation in a room).  It turns out that 
``large'' particles obey different statistics than particles that lie in the 
quantum mechanical regime.

In the classical theory developed by Maxwell and Boltzmann, particles are 
treated as distinguishable balls.  They are considered distinguishable because
they obey Newtonian mechanics therefore in principle they could be observed 
and labeled.
Consider a collection of $r$ distinguishable particles, and divide the 
container in which they lie into $n$ cells \footnote{We formulate the problem
in this way for visualization purposes.  In statistical mechanics what gets 
divided into cells is not the volume, but the state space, i.e. the space 
defined by the positions and momenta of the particles. Correspondingly, we 
don't consider $r$ particles, but rather $r$ points in the state space}.
Then the classical statistical mechanics problem becomes a balls and bins
problem.


\begin{enumerate}
\item What is the total number of arranging the particles in the cells?

answer :$n^r$

\item What is the probability $p_k$, of having exactly $k$ particles in a 
particular cell?

answer $p_k = {r \choose k} (\frac{1}{n})^k(1-\frac{1}{n})^k$

\item Calculate the expected number of empty cells.

Answer $np_0$

\item Calculate the average number of empty cells.

answer $p_0$

\item Let $\lambda = \frac{r}{n}$, the average number of particles/cell, be
constant, while $n \rightarrow \infty$ and $r \rightarrow \infty$.
Show that the average number of empty cells goes to $e^{-\lambda}$.

\end{enumerate}

 
In the quantum mechanical regime particles can not be treated as 
distinguishable entities.  The explanation is involved and relies on the
Heisenberg uncertainty principle \footnote{The Heisenberg uncertainty principle
states that the product of uncertainties in position and momentum always
exceeds some constant $\Delta x \Delta p \geq \frac{\hslash}{2}$. If the
size of the cells in the state space is of that order, then the positions
and momenta of particles lying in the same cell are ``blurred'' by the
uncertainty principle and they become indistinguishable}.
The statistics derived by the assumption that particles are indistinguishable
are called Bose-Einstein statistics.
Now consider $r$ indistinguishable particles in $n$ cells.

\begin{enumerate}
\item What is the total number of arranging the particles in the cells?

answer :${n+r-1 \choose r}$

\item What is the probability $q_k$, of having exactly $k$ particles in a 
particular cell?

answer $q_k = \frac{{{n+r-k-2} \choose {r-k}}}{{{n+r-1} \choose r}}$

\item Calculate the expected number of empty cells.

answer $nq_0$

\item Calculate the average number of empty cells.

answer $q_0$

\item Let $\lambda = \frac{r}{n}$, the average number of particles/cell, be
constant, while $n \rightarrow \infty$ and $r \rightarrow \infty$.
Show that the average number of empty cells goes to $\frac{1}{1+\lambda}$.

\end{enumerate}

Observe that when $\lambda$ is large the two expectations are quite different,
while when  $\lambda$ is very small (corresponding to either a large number of 
cells, i.e. an almost free system, or a small number of particles , i.e. a
weekly interacting system) then the two quantities become identical. 
What are they equal to if second order terms are ignored?

answer $1-\lambda$

In order to make our exposition complete, let us mention that there is a
third kind of statistics, the Fermi-Dirac statistics, that applies to 
particles known as Fermions (electrons for example are Fermions).  In this
case the cells in state space correspond to different quantum states of the
system.  The Pauly exclusion principle states that no more than one Fermion
can occupy the same quantum state, therefore this is a case where we can have
 at most one ball per bin.  As a consequence there are only 
${n \choose r}$ possible
configurations.


\end{problems}

\end{document}













