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?

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?

(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?

(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?

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

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

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

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

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?

(b) Let B_{i} be the event that no contestant beat all the k contestants in set i. Compute Pr(B_{i}).

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

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