Massachusetts Institute of Technology Handout 39 6.042J/18.062J: Mathematics for Computer Science April 21, 2000 Professors David Karger and Nancy Lynch

Mini-Quiz 11

1. Write your name:

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

Solution.

1 − \begin{matrix}( & {48 \atop 5} & ) \\ ( & {52 \atop 5} & ) \end{matrix}

□

Tutorial 11 Problems

Problem 1 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 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.

(a) The Maxwell-Boltzmann model assumes that the particles are distinguishable, say, numbered 1, 2, . . .. 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}

□

(b) On the other hand, the Bose-Einstein model assumes that the particles are indistinguishable. A state is described by the 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.

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

Solution.

\binom{n+r−1}{r}

Balls in bins, stars and bars.

□

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

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

Solution.

The configurations are simply determined by which r of the n boxes are occupied, so

\binom{n}{r}

□

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

Prove that in the Maxwell-Boltzmann model, the probability of a given box being empty is about

e^{−λ}

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}) ≈ e^{− \frac{1}{n}} (valid for large n), this yields approximately e^{− \frac{r}{n}} = e^{−λ}. This probability should be close to the fraction of empty boxes.

□

(e) Prove that under Bose-Einstein Statistics, the probability of a given box being empty is about

\frac{1}{1 + λ}

Again, assume n is very large.

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. □ (f) Under Fermi-Dirac Statistics, what is the probability of a given box being empty?

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 − λ

□

(g) It turns out that the Fermi-Dirac model holds for electrons, protons, and other “solid” particles called 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 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 λ. When λ is large, 1 − λ < e^{−λ} < \frac{1}{1+λ}. In other words, Maxwell-Boltzmann predicts a less spread-out gas than you would actually find for fermions, and a more spreadout gas than you would actually find for bosons. But as λ decreases, these differences become less significant.

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

Solution.

For Boltzman distribution, e^{−λ} is approximately (1 − λ) for small λ, as used in the above solution.

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

The Fermi distribution directly predicts a probability of (1 − λ).

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 α is:

f(x) = f(α) + \frac{f′(α)}{1!} · (x − α) + \frac{f′′(α)}{2!} · (x − α)^{2} + \frac{f′′′(α)}{3!} · (x − α)^{3} + …

It is easy to see that the first two terms form a linear approximation of the original function based on its value at x = α.

For values of x close to α, the higher-order terms are not significant, since (x − α) is small. In fact, the error in truncating the summation at the n^{th} term (of degree (n − 1)) is less than

|\frac{f^{(n)}(α)}{n!} · (γ − α)^{n}|

for some γ between α and x.

An expansion for “small values,” around x = 0, is somewhat simpler:

f(x) = f(0) + f′(0) · x + \frac{f′′(0)}{2!} · x^{2} + \frac{f′′′(0)}{3!} · x^{3} + …

The error in ending this summation at the n^{th} term is less than

|\frac{f^{(n)}(0)}{n!} · γ^{n}|

for some γ between 0 and x.

□

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 entropy of a gas, a physically measurable quantity, depends on the number of states. This fact is supported by experiment.

Problem 2 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} [1 − (\frac{1}{2})^{k}]^{n−k} < 1

then such an outcome is possible.

(a) Start by numbering the sets of k contestants. How many such sets are there?

Solution.

\binom{n}{k}

□

(b) 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 (\frac{1}{2})^{k}, so the probability the person they did not beat everyone in i is 1 − (\frac{1}{2})^{k}. There are n − k people outside of group i. Thus, B_{i} has probability

[1 − (\frac{1}{2})^{k}]^{n−k}

□

(c) Give an upper bound on Pr(∪B_{i}).

Solution.

Then use Boole’s inequality to bound: Pr(∪B_{i}) ≤ ∑ Pr(B_{i}). In other words, Pr(∪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} [1 − (\frac{1}{2})^{k}]^{n−k}

□

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

Solution.

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

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

□