\section{Elementary Stat.\ Physics and Its Relation to IT}

\subsection{What is Statistical Physics?}

Statistical physics is a branch in Physics which deals with systems with a
huge number of particles (or any other elementary units), e.g., of the order
of magnitude of {\it Avogadro's number}, that is, about $10^{23}$ particles.
Evidently, when it comes to systems with such an enormously
large number of particles, there is no hope to keep track of the physical
state (e.g., position and momentum) of each and every individual particle by
means of the classical methods in physics, that is, by solving a gigantic system of
differential equations pertaining to Newton's laws for all particles.
Moreover, even if these differential equations could have been solved (at least
approximately), the information that they would give us would be virtually
useless. What we normally really want to know about our physical system boils down to a
bunch of {\it macroscopic} parameters, such as energy, heat, pressure,
temperature, volume, magnetization, and the like. In other words, while we
continue to believe in the good old laws of physics that we have known for
some time, even the classical ones,
we no longer use them in the ordinary way that we are familar with from elementary
physics courses. Rather, we think of the state of the system, at any given
moment, as a
realization of a certain {\it probabilistic ensemble}. This is to say that we
approach the problem from a probabilistic (or a statistical) point of view. 
The beauty of statistical physics is that it derives the {\it macroscopic} theory of thermodynamics
(i.e., the relationships between thermodynamical potentials, temperature,
pressure, etc.) as {\it ensemble averages} that stem from this probabilistic
{\it microscopic} theory -- the theory of statistical physics, in the limit of
an infinite number of particles, that is, the {\it thermodynamic limit}.
As we shall see throughout this course, this thermodynamic limit is parallel
to the asymptotic regimes that we are used to in Information Theory, 
most notably, the one pertaining to a certain `block
length' that goes to infinity. 

\subsection{Basic Postulates and the Microcanonical Ensemble}

For the sake of concreteness, let us consider the example where our many--particle system is
a {\it gas}, namely, a system with a very large number $n$ of mobile particles, which
are free to move in a given volume. 
The {\it microscopic state} (or {\it microstate}, for short) of the system, at
each time instant $t$,  consists, in this example,
of the position $\vec{r}_i(t)$
and the momentum $\vec{p}_i(t)$ of each and every particle,
$1\le i\le n$. Since each one of
these is a vector of three components, the microstate is then given by a
$(6n)$--dimensional vector
$\vec{\bx}(t)=\{(\vec{r}_i(t),\vec{p}_i(t)),~i=1,2,\ldots,n\}$, whose trajectory
along the time axis,
in the {\it phase space}, $\reals^{6n}$, is called the {\it phase trajectory}.

Let us assume that the system is closed, i.e., {\it isolated} from its environment, in
the sense that no energy flows inside or out.
Imagine that the phase space $\reals^{6n}$ is partitioned into very small hypercubes
(or cells) $\Delta\vec{p}\times\Delta\vec{r}$. One of the basic postulates of statistical
mechanics is the following: In the very long range, the relative
amount of time at which $\vec{\bx}(t)$ spends at each such cell
converges to a certain number between $0$ and $1$, which can be given the
meaning of the {\it probability} of this cell. Thus, there is an underlying
assumption of equivalence between temporal averages and ensemble averages,
namely, this is the assumption of {\it ergodicity}.

What are then the probabilities of these cells? We would like to derive these
probabilities from first principles, based on as few as possible
basic postulates. Our first such postulate is that for an isolated system
(i.e., whose energy is fixed) all microscopic states $\{\vec{\bx}(t)\}$ are
equiprobable. The rationale behind this postulate is twofold:
\begin{itemize}
\item In the absence of additional information, there is no apparent reason
that certain regions in phase space would have preference relative to any
others.
\item This postulate is in harmony with a basic result in kinetic theory of
gases -- {\it the Liouville theorem}, which we will not touch upon in this
course, but in a nutshell, it asserts that the phase trajectories must lie
along hypersurfaces of constant probability density.\footnote{This is a result of the
energy conservation law along with the fact that probability mass behaves
like an incompressible fluid in the sense that whatever mass that flows into a certain
region from some direction must be equal to the outgoing flow from some other
direction. This is reflected in the so called continuity equation.}
\end{itemize}

Before we proceed, let us slightly broaden the scope of our discussion.
In a more general context, associated with our $n$--particle physical system, 
is a certain instantaneous microstate, generically denoted by
$\bx=(x_1,x_2,\ldots,x_n)$, where each 
$x_i$, $1\le i\le n$, may itself be a vector of several
physical quantities associated particle number 
$i$, e.g., its position, momentum,
angular momentum, magnetic moment, spin, and so on,
depending on the type and the nature 
of the physical system. For each possible value of
$\bx$, there is a certain
{\it Hamiltonian} (i.e., energy function) that assigns to
$\bx$ a certain energy $\calE(\bx)$.\footnote{For example, in the case of an {\it ideal gas},
$\calE(\bx)=\sum_{i=1}^n\frac{\|\vec{p}_i\|^2}{2m}$, independently of
the positions
$\{\vec{r}_i\}$, namely, it accounts for the contribution of the kinetic energies only. 
In more complicated situations, there might be additional contributions of potential
energy, which depend on the positions.} Now, let us denote by $\Omega(E)$ 
the {\it density--of--states} function, i.e., the
volume of the shell $\{\bx:\calE(\bx)=E\}$, or, slightly more precisely,
$\Omega(E)dE=\mbox{Vol}\{\bx:~E\le\calE(\bx)\le E+dE\}$, 
which will be denoted also as
$\mbox{Vol}\{\bx:~\calE(\bx)\approx E\}$,
where the dependence on $dE$ will normally
be ignored since $\Omega(E)$ is typically exponential in $n$ and $dE$ will
have virtually no effect on its exponential order as long as it is small.
Then, our above postulate concerning the ensemble of an isolated system, which
is called the {\it microcanonincal ensemble}, is that the probability density
$P(\bx)$ is given by
\begin{equation}
P(\bx)=\left\{\begin{array}{ll}
\frac{1}{\Omega(E)} & \calE(\bx)\approx E\\
0 & \mbox{elsewhere}\end{array}\right.
\end{equation}
In the discrete case, things are, of course, a lot easier: Then, $\Omega(E)$ would be
the number of microstates with $\calE(\bx)=E$ (exactly) and $P(\bx)$ would be
the uniform probability mass function across this set of states. 
In this case,
$\Omega(E)$ is analogous to the size of a {\it type class} in Information
Theory, and $P(\bx)$ is the uniform distribution across this type class.

Back to the
continuous case, note that $\Omega(E)$ is, in general, not dimensionless: 
In the above example of a gas, it has the
physical units of $[\mbox{length}\times\mbox{momentum}]^{3n}$, but we must get
rid of these physical units because very soon we are going to apply non--linear
functions on $\Omega(E)$, like the logarithmic function. Thus, we must
normalize this volume by an elementary reference volume. In the gas example, this reference volume
is taken to be $h^{3n}$, where $h$ is {\it Planck's constant} $\approx 6.62\times 10^{-34}$ 
Joules$\cdot$sec. Informally, the
intuition comes from the fact that $h$ is our best available ``resolution'' in the plane
spanned by each component of $\vec{r}_i$ and the corresponding component of
$\vec{p}_i$, owing to the {\it uncertainty principle} in quantum mechanics,
which tells us that the product of the standard deviations $\Delta p_a\cdot\Delta
r_a$ of each component $a$ ($a=x,y,z$) is lower bounded by $\hbar/2$, where
$\hbar=h/(2\pi)$. More
formally, this reference volume is obtained in a natural manner 
from quantum statistical mechanics: by changing
the integration variable $\vec{p}$ to $\vec{k}$ by using
$\vec{p}=\hbar\vec{k}$, where $\vec{k}$ is the wave vector.
This is a well--known relationship pertaining to particle--wave duality. Now, 
having redefined $\Omega(E)$ in units of
this reference volume, which makes it then a dimensionless quantity, the {\it entropy} is
defined as
\begin{equation}
S(E)=k\ln\Omega(E),
\end{equation}
where $k$ is {\it Boltzmann's constant} $\approx 1.38\times 10^{-23}$
Joule/degree. We will soon see what is the relationship between $S(E)$
and the information--theoretic entropy.

To get some feeling of this, it should be noted that normally,
$\Omega(E)$ behaves as an exponential function of $n$ (at least
asymptotically), and so, $S(E)$ is roughly linear in $n$. For example,
if $\calE(\bx)=\sum_{i=1}^n\frac{\|\vec{p}_i\|^2}{2m}$, then $\Omega(E)$
is the volume of a shell or surface of a $(3n)$--dimensional sphere with
radius $\sqrt{2mE}$, which is proportional 
to $(2mE)^{3n/2}V^n$, but we should divide
this by $n!$ to account for the fact that the particles are indistinguishable
and we don't count permutations as distinct physical states in this
case.\footnote{Since the particles are mobile and since they have no colors and no
identity certficiates, there is no distinction between a state where particle
no.\ 15 has position $\vec{r}$ and momentum $\vec{p}$ while particle no.\ 437
has position $\vec{r}'$ and momentum $\vec{p}'$ and a state where these two
particles are swapped.} More precisely, one obtains:
\begin{equation}
S(E)=k\ln\left[\left(\frac{4\pi
mE}{3n}\right)^{3n/2}\cdot\frac{V^n}{n!h^{3n}}\right]+\frac{3}{2}nk\approx
nk\ln\left[\left(\frac{4\pi
mE}{3n}\right)^{3/2}\cdot\frac{V}{nh^{3}}\right]+\frac{5}{2}nk.
\end{equation}
Assuming $E \propto n$ and $V\propto n$, we get $S(E)\propto n$.
A physical quantity like this, that has a linear scaling with the size of the
system $n$, is called an {\it extensive quantity}. So, energy, volume and
entropy are 
extensive quantities. 
Other quantities, which are not extensive, i.e., independent of the
system size, like temperature and pressure, are called {\it intensive}.

It is interesting to point out that from the function $S(E)$, or actually,
the function $S(E,V,n)$,
one can obtain the entire information about the relevant
macroscopic physical quantities of the system, e.g., temperature,
pressure, and so on.
The {\it temperature} $T$ of the system is defined according to:
\begin{equation}
\frac{1}{T}=\left(\frac{\partial S(E)}{\partial E}\right)_V
\end{equation}
where $(\cdot)_V$ means that the derivative is taken in constant
volume.\footnote{
This definition of temperature is related to the classical thermodynamical
definition of entropy 
as $\dd S=\dd Q/T$, where $Q$ is heat, as in the absence of
external work, when the volume $V$ is fixed, all the energy comes from heat
and so, $\dd E=\dd Q$.} Intuitively, in most situations, 
we expect that $S(E)$ would be an increasing
function of $E$ (although this is not strictly always the case), which means
$T \ge 0$. But $T$ is also expected to be increasing with $E$ (or
equivalently, $E$ is increasing with $T$, as otherwise, the heat capacity
$\dd E/\dd T < 0$). Thus, $1/T$ should decrease with $E$, which means that the
increase of $S$ in $E$ slows down as $E$ grows. In other words, we expect
$S(E)$ to be a concave function of $E$. In the above example, indeed, $S(E)$
is logarithmic in $E$ and we get $1/T\equiv\partial S/\partial E=
3nk/(2E)$, which means $E=3nkT/2$. Pressure is obtained by $P=T\cdot\partial
S/\partial V$, which in our example, gives rise to
the state equation of the ideal gas, $P=nkT/V$.

How can we also see {\it mathematically} 
that under ``conceivable conditions'', $S(E)$ is
a concave function?  We know that the Shannon entropy is also a concave
functional of the probability distribution. Is this related?

As both $E$ and $S$ are extensive quantities, let
us define $E=n\epsilon$ and 
\begin{equation}
s(\epsilon)=\lim_{n\to\infty}\frac{S(n\epsilon)}{n},
\end{equation}
i.e., the per--particle entropy as a function of the per--particle energy.
Consider the case where the Hamiltonian is additive, i.e.,
\begin{equation}
\calE(\bx)=\sum_{i=1}^n\calE(x_i)
\end{equation}
just like in the above example 
where $\calE(\bx)=\sum_{i=1}^n\frac{\|\vec{p}_i\|^2}{2m}$. Then, obviously,
\begin{equation}
\Omega(n_1\epsilon_1+n_2\epsilon_2)\ge
\Omega(n_1\epsilon_1)\cdot\Omega(n_2\epsilon_2),
\end{equation}
and so, we get:
\begin{eqnarray}
\frac{ k\ln \Omega(n_1\epsilon_1+n_2\epsilon_2)}{n_1+n_2}&\ge&
\frac{k\ln \Omega(n_1\epsilon_1)}{n_1+n_2}+\frac{k\ln
\Omega(n_2\epsilon_2)}{n_1+n_2}\nonumber\\
&=&\frac{n_1}{n_1+n_2}\cdot\frac{k\ln \Omega(n_1\epsilon_1)}{n_1}+
\frac{n_2}{n_1+n_2}\cdot\frac{k\ln
\Omega(n_2\epsilon_2)}{n_2}.
\end{eqnarray}
and so, by taking $n_1$ and $n_2$ to $\infty$, with
$n_1/(n_1+n_2)\to\lambda\in(0,1)$, we get:
\begin{equation}
s(\lambda\epsilon_1+(1-\lambda)\epsilon_2)\ge
\lambda s(\epsilon_1)+(1-\lambda)s(\epsilon_2),
\end{equation}
which establishes the concavity of $s(\cdot)$ at least in the case of an
additive Hamiltonian, which means that the entropy of mixing two systems of
particles is greater than the total entropy before they are mixed (the second
law). A similar proof
can be generalized to the
case where $\calE(\bx)$ includes also a limited degree of 
interactions (short range interactions), e.g.,
$\calE(\bx)=\sum_{i=1}^n\calE(x_i,x_{i+1})$, but this requires somewhat more
caution. In general, however, concavity may no longer hold when there are long range
interactions, e.g., where some terms of $\calE(\bx)$ depend on a linear
subset of particles. Simple examples can be found in: H.~Touchette, ``Methods for calculating
nonconcave entropies,'' 
arXiv:1003.0382v1 [cond-mat.stat-mech] 1 Mar 2010.

\vspace{0.5cm}

\noindent
{\it Example -- Schottky defects.}
In a certain crystal, the atoms are located in a lattice, and at any positive
temperature there may be defects, where some of the atoms are dislocated (see
Fig.\ \ref{schottky}).
Assuming that defects are sparse enough, such that around each dislocated atom
all neighors are in place, the activation energy, $\epsilon_0$, required for dislocation
is fixed. Denoting the total number of atoms by $N$ and the
number of defected ones by $n$, the total energy is then $E=n\epsilon_0$, and
so,
\begin{equation}
\Omega(E)=\left(\begin{array}{cc} N \\ n
\end{array}\right)=\frac{N!}{n!(N-n)!},
\end{equation}
or, equivalently,
\begin{eqnarray}
S(E)&=&k\ln\Omega(E)=k\ln\left[\frac{N!}{n!(N-n)!}\right]\nonumber\\
&\approx& k[N\ln N-n\ln n -(N-n)\ln(N-n)] ~~~~\mbox{by the Stirling
approximation}\nonumber
\end{eqnarray}
Thus,
\begin{equation}
\frac{1}{T}=\frac{\partial S}{\partial E}= \frac{\dd S}{\dd n}\cdot\frac{\dd
n}{\dd E}=
\frac{1}{\epsilon_0}\cdot k\ln\frac{N-n}{n},
\end{equation}
which gives the number of defects as
\begin{equation}
n=\frac{N}{\exp(\epsilon_0/kT)+1}.
\end{equation}
\begin{figure}[ht]
\hspace*{5cm}\input{schottky.pstex_t}
\caption{\small Schottky defects in a crystal lattice.}
\label{schottky}
\end{figure}
At $T=0$, there are no defects, but their number increases gradually with $T$,
approximately according to $\exp(-\epsilon_0/kT)$. Note that from a slighly
more information--theoretic point of view,
\begin{equation}
S(E)=k\ln \left(\begin{array}{cc} N \\ n
\end{array}\right)\approx kN h_2\left(\frac{n}{N}\right)=kN
h_2\left(\frac{E}{N\epsilon_0}\right)=
kN h_2\left(\frac{\epsilon}{\epsilon_0}\right),
\end{equation}
where $$h_2(x)\dfn -x\ln x-(1-x)\ln(1-x).$$
Thus, the thermodynamical entropy is intimately related to the Shannon
entropy. We will see shortly that this is no coincidence. Note also that
$S(E)$ is indeed concave in this example. $\Box$

What happens if we have two independent systems with total energy $E$, which
lie in equilibrium with each other.
What is the temperature $T$? How does the energy split between them?
The number of combined microstates where system no.\ 1 has energy $E_1$ and
system no.\ 2 has energy $E_2=E-E_1$ is $\Omega_1(E_1)\cdot\Omega_2(E-E_1)$.
If the combined system is isolated, then the probability of such a combined
microstate is proportional to $\Omega_1(E_1)\cdot\Omega_2(E-E_1)$.
Keeping in mind that normally, $\Omega_1$ and $\Omega_2$ are exponential in
$n$, then for large $n$, this product is dominated by the value of $E_1$
for which it is maximum, or equivalently, the sum of logarithms,
$S_1(E_1)+S_2(E-E_1)$, is maximum, i.e., it is a {\bf maximum entropy} 
situation, which is {\bf the second law of thermodynamics}.
This maximum is normally achieved at the
value of $E_1$ for which the derivative vanishes, i.e.,
\begin{equation}
S_1'(E_1)-S_2'(E-E_1)=0
\end{equation}
or
\begin{equation}
S_1'(E_1)-S_2'(E_2)=0
\end{equation}
which means
\begin{equation}
\frac{1}{T_1}\equiv S_1'(E_1)=S_2'(E_2)\equiv\frac{1}{T_2}.
\end{equation}
Thus, in equilibrium, which is the maximum entropy situation, 
the energy splits in a way that temperatures are the same.


\subsection{The Canonical Ensemble}

So far we have assumed that our system is isolated, and therefore has a strictly
fixed energy $E$. Let us now relax this assumption and assume that our system
is free to exchange energy with its large environment (heat bath) and that the total energy of
the heat bath $E_0$ is by far larger than the typical energy of the system. The
combined system, composed of our original system plus the heat bath, is now an
isolated system at temperature $T$.
So what happens now?

Similarly as before, since the combined 
system is isolated, it is governed by the microcanonical
ensemble. The only difference is that now we assume that one of the systems
(the heat bath) is very large compared to the other (our test system).
This means that if our small system is in microstate $\bx$
(for whatever definition of the microstate vector) 
with energy $\calE(\bx)$, then the heat bath must have energy $E_0-\calE(\bx)$
to complement the total energy to $E_0$. The number of ways that the heat bath
may have energy $E_0-\calE(\bx)$ is $\Omega_{HB}(E_0-\calE(\bx))$,
where $\Omega_{HB}(\cdot)$ is the density--of--states function pertaining to the
heat bath. In other words, the number of microstates of the {\it combined}
system for which the small subsystem is in microstate $\bx$ 
is $\Omega_{HB}(E_0-\calE(\bx))$. Since the combined system is governed by the
microcanonical ensemble, the probability of this is proportional to 
$\Omega_{HB}(E_0-\calE(\bx))$. More precisely:
\begin{equation}
P(\bx)=\frac{\Omega_{HB}(E_0-\calE(\bx))}
{\sum_{\bx'}\Omega_{HB}(E_0-\calE(\bx'))}.
\end{equation}
Let us focus on the numerator for now, and  normalize the result at the end.
Then,
\begin{eqnarray}
P(\bx) &\propto& \Omega_{HB}(E_0-\calE(\bx))\nonumber\\
&=& \exp\{S_{HB}(E_0-\calE(\bx))/k\}\nonumber\\
&\approx&\exp\left\{\frac{S_{HB}(E_0)}{k}-\frac{1}{k}\frac{\partial
S_{HB}(E)}{\partial E}\bigg|_{E=E_0}\cdot\calE(\bx)\right\}\nonumber\\
&=&\exp\left\{\frac{S_{HB}(E_0)}{k}-\frac{1}{kT}
\cdot\calE(\bx)\right\}\nonumber\\
&\propto& \exp\{-\calE(\bx)/(kT)\}.
\end{eqnarray}
It is customary to work with the so called {\it inverse temperature}:
\begin{equation}
\beta=\frac{1}{kT}
\end{equation}
and so,
\begin{equation}
P(\bx)\propto e^{-\beta\calE(\bx)}.
\end{equation}
Thus, all that remains to do is to normalize, and 
we then obtain the {\it Boltzmann--Gibbs} (B--G) distribution, 
or the {\it canonical ensemble}, which
describes the underlying probability law in equilibrium:
\begin{center}
\fbox{
$P(\bx)=\frac{\exp\{-\beta\calE(\bx)\}}{Z(\beta)}$}
\end{center}
where $Z(\beta)$ is the normalization factor:
\begin{equation}
Z(\beta)=\sum_{\bx}\exp\{-\beta \calE(\bx)\}
\end{equation}
in the discrete case, or
\begin{equation}
Z(\beta)=\int \dd \bx\exp\{-\beta \calE(\bx)\}
\end{equation}
in the continuous case.

This is one of the most fundamental results in statistical mechanics, which
was obtained solely from the energy conservation law and the postulate that
in an isolated system the distribution is uniform. The function $Z(\beta)$
is called the {\it partition function}, and as we shall see, its meaning is by
far deeper than just being a normalization constant. Interestingly, a great
deal of the macroscopic physical quantities, like the internal energy, the
free energy, the entropy, the heat capacity, the pressure, etc., can be
obtained from the partition function.

The B--G distribution tells us then that the system ``prefers'' to visit its
low energy states more than the high energy states. And what counts
is only energy differences, not absolute energies: If we add to all states
a fixed amount of energy $E_0$, this will result in an extra factor of
$e^{-\beta E_0}$ both in the numerator and in the denominator of the B--G
distribution, which will, of course, cancel out. Another obvious observation
is that whenever the Hamiltonian is additive, that is,
$\calE(\bx)=\sum_{i=1}^n\calE(x_i)$, the various particles are statistically
independent: Additive Hamiltonians correspond to
non--interacting particles. In other words, the $\{x_i\}$'s
behave as if they were drawn from a memoryless source. And so, by the law of
large numbers $\frac{1}{n}\sum_{i=1}^n\calE(x_i)$ will tend (almost surely)
to $\epsilon=\bE\{\calE(X_i)\}$. Nonetheless, this is different from the
microcanonical ensemble where $\frac{1}{n}\sum_{i=1}^n\calE(x_i)$ was held
strictly at the value of $\epsilon$. The parallelism to 
Information Theory is as follows:
The microcanonical ensemble is parallel to the uniform distribution over
a type class and the
canonical ensemble is parallel to a memoryless source.

The two ensembles are asymptotically equivalent as far as
expectations go. They continue to be such even in cases of interactions,
as long as these are short range.
It is instructive to point out that the B--G distribution could
have been obtained also in a different manner, owing to the maximum--entropy
principle that we mentioned in the Introduction. Specifically, consider the
following optimization problem:
\begin{eqnarray}
& &\max~H(\bX)\nonumber\\
& &\mbox{s.t.}~\sum_{\bx}P(\bx)\calE(\bx)=E~~~~[\mbox{or in physicists'
notation:}~~
\langle\calE(\bX)\rangle=E]
\end{eqnarray}
By formalizing the equivalent Lagrange problem, where $\beta$ now plays the
role of a Lagrange multiplier:
\begin{equation}
\max~\left\{H(\bX)+\beta\left[E-\sum_{\bx}P(\bx)\calE(\bx)\right]\right\},
\end{equation}
or equivalently,
\begin{equation}
\min~\left\{\sum_{\bx}P(\bx)\calE(\bx)-\frac{H(\bX)}{\beta}\right\}
\end{equation}
one readily verifies that the solution to this problem is the B-G distribution
where the choice of $\beta$ {\bf controls} the average energy $E$. In many
physical systems, the Hamiltonian is a quadratic (or ``harmonic'') function,
e.g., $\frac{1}{2}mv^2$, $\frac{1}{2}kx^2$,
$\frac{1}{2}CV^2$, $\frac{1}{2}LI^2$, $\frac{1}{2}I\omega^2$, etc., in which
case the resulting B--G distribution turns out to be Gaussian. This is at
least part of the explanation why the Gaussian distribution is so frequently
encountered in Nature. Note also that indeed, we have
already seen in the Information Theory course that the Gaussian density maximizes the
(differential) entropy s.t.\ a second order moment constraint, which is
equivalent to our average energy constraint.

\subsection{Properties of the Partition Function and the Free Energy}

Let us now examine more closely the partition function and make a few
observations about its basic properties. For simplicity, we shall assume
that $\bx$ is discrete. First, let's look at the limits:
Obviously, $Z(0)$ is equal to the size of the entire set of microstates, which is also
$\sum_E\Omega(E)$, This is the high temperature limit, where
all microstates are equiprobable. At the other extreme, we have:
\begin{equation}
\lim_{\beta\to\infty} \frac{\ln Z(\beta)}{\beta}=-\min_{\bx} \calE(\bx)\dfn
-E_{GS}
\end{equation}
which describes the situation where the system is frozen to the absolute zero.
Only states with minimum energy -- the {\it ground--state energy}, prevail.

Another important property of $Z(\beta)$, or more precisely, of $\ln
Z(\beta)$,
is that it is a log--moment generating function: By taking derivatives of $\ln
Z(\beta)$, we can obtain moments (or cumulants) of $\calE(\bX)$. 
For the first moment, we have
\begin{equation}
\bE\{\calE(\bX)\}\equiv\langle\calE(\bX)\rangle
=\frac{\sum_{\bx}\calE(\bx)e^{-\beta\calE(\bx)}}{\sum_{\bx}e^{-\beta\calE(\bx)}}=
-\frac{\dd \ln Z(\beta)}{\dd \beta}.
\end{equation}
Similarly, it is easy to show (exercise) that
\begin{equation}
\mbox{Var}\{\calE(\bX)\}=\langle\calE^2(\bX)\rangle -
\langle\calE(\bX)\rangle^2=\frac{\dd^2\ln Z(\beta)}{\dd\beta^2}.
\end{equation}
This in turn implies that $\frac{\dd^2\ln Z(\beta)}{\dd\beta^2}\ge 0$,
which means that $\ln Z(\beta)$ must always be a convex function.
Higher order derivatives provide higher order moments.

Next, we look at $Z$ slightly differently than before. Instead of summing
$e^{-\beta \calE(\bx)}$ across all states, we go by energy levels (similarly
as in the method of types). 
This amounts to:
\begin{eqnarray}
Z(\beta)&=&\sum_{\bx}e^{-\beta\calE(\bx)}\nonumber\\
&=&\sum_{E}\Omega(E)e^{-\beta E}
\nonumber\\
&\approx&\sum_\epsilon e^{ns(\epsilon)/k}\cdot e^{-\beta
n\epsilon}~~~~~\mbox{recall that}~S(n\epsilon)\approx ns(\epsilon)\nonumber\\
&=&\sum_\epsilon \exp\{-n\beta[\epsilon-Ts(\epsilon)]\}\nonumber\\
&\exe&\max_\epsilon \exp\{-n\beta[\epsilon-Ts(\epsilon)]\}\nonumber\\
&=&\exp\{-n\beta\min_\epsilon[\epsilon-Ts(\epsilon)]\}\nonumber\\
&\dfn&\exp\{-n\beta[\epsilon^*-Ts(\epsilon^*)]\}\nonumber\\
&\dfn&e^{-\beta F}
\end{eqnarray}
The quantity $f\dfn \epsilon-Ts(\epsilon)$ is the (per--particle) {\it free
energy}. Similarly, the entire free energy, $F$, is defined as
\begin{equation}
F=E-TS=-\frac{\ln Z(\beta)}{\beta}.
\end{equation}
The physical meaning of the free energy is this: A change, or a difference,
$\Delta F=F_2-F_1$, in the free energy means the minimum amount of work 
it takes to transfer the system from equilibrium state 1 to another
equilibrium state 2 in an isothermal (fixed temperature) process. And this
minimum is achieved when the process is {\it quasistatic}, i.e., so slow that
the system is always almost in equilibrium. Equivalently, $-\Delta F$ is the
maximum amount of work that that can be exploited from the system, namely, the
part of the energy that
is {\it free} for doing work (i.e., not dissipated as heat) in fixed temperature.
Again, this maximum is attained by a quasistatic process.

We see that the value $\epsilon^*$ of $\epsilon$ that minimizes $f$, dominates
the partition function and hence captures most of the probability. 
As $n$ grows without bound, the energy probability distribution
becomes sharper and sharper around
$n\epsilon^*$. Thus, we see that
equilibrium in the canonical ensemble amounts to {\bf minimum free energy.}
This extends the second law of thermodynamics from the microcanonical ensemble
of isolated systems, whose equilibrium obeys the maximum entropy principle.
The maximum entropy principle is replaced, more generally, by the minimum free
energy principle.
Note that the Lagrange minimization problem that we
formalized before, i.e.,
\begin{equation}
\min~\left\{\sum_{\bx}P(\bx)\calE(\bx)-\frac{H(\bX)}{\beta}\right\},
\end{equation}
is nothing but minimization of the free energy, provided that we identify
$H$ with the physical entropy $S$ (to be done very soon) and the Lagrange
multiplier $1/\beta$ with $kT$. Thus, the B--G distribution minimizes the
free energy for a given temperature.

Although we have not yet seen this explicitly, but there were already hints
and terminology suggests that the thermodynamical entropy $S(E)$ is intimately
related to the Shannon entropy $H(\bX)$. 
We will also see it shortly in a more formal manner. But what is the
information--theoretic analogue of the free energy? 

Here is a preliminary guess based on a very rough consideration: The last chain of
equalities reminds us what happens when we sum over probabilities
type--by--type in IT problems: The exponentials $\exp\{-\beta\calE(\bx)\}$ are analoguous
(up to a normalization factor) to probabilities, which in the memoryless
case, are given by $P(\bx)=\exp\{-n[\hat{H}+D(\hat{P}\|P)]\}$. Each such
probability is weighted by the size of the type class, which as is known
from the method of types, is exponentially $e^{n\hat{H}}$, whose physical
analogue is $\Omega(E)=e^{ns(\epsilon)/k}$. The product gives
$\exp\{-nD(\hat{P}\|P)\}$ in IT and $\exp\{-n\beta f\}$ in statistical physics.
This suggests that perhaps the free energy has some analogy with the
divergence. Is this true? We will see shortly a somewhat more rigorous
argument.

More formally, let us define
\begin{equation}
\phi(\beta)=\lim_{n\to\infty}\frac{\ln Z(\beta)}{n}
\end{equation}
and, in order to avoid dragging the constant $k$, let us define
$\Sigma(\epsilon)=\lim_{n\to\infty}\frac{1}{n}\ln\Omega(n\epsilon)=s(\epsilon)/k$. Then,
the above chain of equalities, written slighlty differently, gives
\begin{eqnarray}
\phi(\beta)&=&\lim_{n\to\infty}\frac{\ln Z(\beta)}{n}\nonumber\\
&=&\lim_{n\to\infty}\frac{1}{n}\ln\left\{\sum_\epsilon 
e^{n[\Sigma(\epsilon)-\beta \epsilon]}\right\}\nonumber\\
&=&\max_\epsilon[\Sigma(\epsilon)-\beta\epsilon].\nonumber
\end{eqnarray}
Thus, $\phi(\beta)$ is (a certain variant of) the {\it Legendre
transform}\footnote{More precisely, the 1D Legendre transform of a real function
$f(x)$ is defined as $g(y)=\sup_x[xy-f(x)]$. If $f$ is convex, it can readily
be shown that: (i) The inverse transform has the very same form, i.e.,
$f(x)=\sup_y[xy-g(y)]$, and (ii) The derivatives $f'(x)$ and $g'(y)$ are inverses of each other.}
of $\Sigma(\epsilon)$. As $\Sigma(\epsilon)$ is (normally) a concave function,
then it can readily be shown (execrise) that the inverse transform is:
\begin{equation}
\Sigma(\epsilon)=\min_\beta[\beta\epsilon+\phi(\beta)].
\end{equation}
The achiever, $\epsilon^*(\beta)$, of $\phi(\beta)$ in the forward transform is obtained by
equating the derivative to zero, i.e., it is the solution to the equation
\begin{equation}
\beta=\Sigma'(\epsilon),
\end{equation}
or in other words, the inverse function of $\Sigma'(\cdot)$. By the same
token, the achiever, $\beta^*(\epsilon)$, of $\Sigma(\epsilon)$ in the backward transform
is obtained by
equating the other derivative to zero, i.e., it is the solution to the equation
\begin{equation}
\epsilon=-\phi'(\beta)
\end{equation}
or in other words, the inverse function of $-\phi'(\cdot)$.\\
{\bf Exercise}: Show that the functions $\Sigma'(\cdot)$ and $-\phi'(\cdot)$
are inverses of one another. $\Box$\\
This establishes a relationship between the
typical per--particle energy $\epsilon$ and the inverse temperature $\beta$
that gives rise to $\epsilon$ (cf.\ the Lagrange interpretation above, where we said
that $\beta$ controls the average energy).
Now, obersve that whenever $\beta$ and $\epsilon$ are related as explained
above, we have:
\begin{equation}
\Sigma(\epsilon)=\beta\epsilon+\phi(\beta)=\phi(\beta)-\beta\cdot\phi'(\beta).
\end{equation}
On the other hand, if we look at the Shannon entropy pertaining to the B--G
distribution, we get:
\begin{eqnarray}
\bar{H}(\bX)&=&\lim_{n\to\infty}\frac{1}{n}\bE\left\{\ln\frac{Z(\beta)}{e^{-\beta\calE(\bX)}}
\right\}\nonumber\\
&=&\lim_{n\to\infty}\left[\frac{\ln
Z(\beta)}{n}+\frac{\beta\bE\{\calE(\bX)\}}{n}\right]\nonumber\\
&=&\phi(\beta)-\beta\cdot\phi'(\beta).\nonumber
\end{eqnarray}
which is exactly the same expression as before,
and so, $\Sigma(\epsilon)$ and $\bar{H}$ are identical whenever $\beta$ and
$\epsilon$ are related accordingly. The former, as we recall, we defined as
the normalized logarithm of the number of microstates with per--particle 
energy $\epsilon$. Thus, we have learned that the number of such microstates
is exponentially $e^{n\bar{H}}$, a result that looks familar to what we
learned from the method of types in IT, using combinatorial arguments
for finite--alphabet sequences.
Here we got the same result from
substantially different considerations, which are applicable in situations
far more general than those of finite alphabets (continuous alphabets included).
Another look at this relation is
the following:
\begin{eqnarray}
1&\geq&\sum_{\bx:~\calE(\bx)\approx n\epsilon} P(\bx)=
\sum_{\bx:~\calE(\bx)\approx n\epsilon} \frac{\exp\{-\beta\sum_i\calE(x_i)\}}
{Z^n(\beta)}\nonumber\\
&\approx&\sum_{\bx:~\calE(\bx)\approx n\epsilon} 
\exp\{-\beta n\epsilon-n\phi(\beta)\}
=\Omega(n\epsilon)\cdot\exp\{-n[\beta\epsilon+\phi(\beta)]\}
\end{eqnarray}
which means that
$\Omega(n\epsilon)\le 
\exp\{n[\beta\epsilon+\phi(\beta)]\}$ for all $\beta$, and so,
\begin{equation}
\Omega(n\epsilon)\le 
\exp\{n\min_\beta[\beta\epsilon+\phi(\beta)]\}=
e^{n\Sigma(\epsilon)}=e^{n\bar{H}}.
\end{equation}
A compatible lower bound is obtained by observing that the minimizing $\beta$
gives rise to $\left<\calE(X_1)\right>=\epsilon$, which makes the event
$\{\bx:~\calE(\bx)\approx n\epsilon\}$ a high--probability event, by the
weak law of large numbers.
A good reference for further study and
from a more general perspective is:\\
M.~J.~W.~Hall, ``Universal geometric
approach to uncertainty, entropy, 
and information,'' {\it Phys.\ Rev.\ A}, vol.\ 59, no.\ 4, pp.\ 2602--2615,
April 1999.

Having established the identity between
the Shannon--theoretic entropy and the thermodynamical entropy, we now
move on,
as promised, to the free energy and seek its information--theoretic
counterpart. More precisely, we will look at the difference between the free energies
of two different probability distributions, one of which is the B--G
distibution. Consider first, the following chain of equalities concerning
the B--G distribution:
\begin{eqnarray}
P(\bx)&=&\frac{\exp\{-\beta\calE(\bx)\}}{Z(\beta)}\nonumber\\
&=&\exp\{-\ln Z(\beta)-\beta\calE(\bx)\}\nonumber\\
&=&\exp\{\beta[F(\beta)-\calE(\bx)]\}.
\end{eqnarray}
Consider next another probability distribution $Q$, different in general
from $P$ and hence corresponding to non--equilibrium. Let us now look at the
divergence:
\begin{eqnarray}
D(Q\|P)&=&\sum_{\bx}Q(\bx)\ln\frac{Q(\bx)}{P(\bx)}\nonumber\\
&=&-H_Q-\sum_{\bx}Q(\bx)\ln P(\bx)\nonumber\\
&=&-H_Q-\beta\sum_{\bx}Q(\bx)[F_P-\calE(\bx)]\nonumber\\
&=&-H_Q-\beta F_P+\beta\langle\calE\rangle_Q\nonumber\\
&=&\beta(F_Q-F_P)\nonumber
\end{eqnarray}
or equivalently,
\begin{center}
\fbox{
$F_Q=F_P+kT\cdot D(Q\|P)$}
\end{center}
Thus, the free energy difference is indeed related to the the divergence.
For a given temperature,
the free energy away from equilibrium is always larger than the free energy
at equilibrium. Since the system ``wants'' to minimize the free energy, it
eventually converges to the B--G distribution. More details on this can be
found in:
\begin{enumerate}
\item H.~Qian, ``Relative entropy: free energy ...,'' {\it Phys.\ Rev.\
E}, vol.\ 63, 042103, 2001.
\item G.~B.~Ba\'gci, arXiv:cond-mat/070300v1, 1 Mar.\ 2007.
\end{enumerate}
Another interesting relation between the divergence and physical quantities is
that the divergence is
proportional to the dissipated work ($=$average work $-$ free energy
difference) between two equilibrium states at the same temperature but
corresponding to two different values of some external control parameter.
Details can be found in: R.~Kawai, J.~M.~R.~Parrondo, and C.~Van den Broeck,
``Dissipation: 
the phase--space perspective,'' {\it Phys.\ Rev.\ Lett.}, vol.\ 98, 080602,
2007.

Let us now summarize the main properties of the partition function that we
have seen thus far:
\begin{enumerate}
\item $Z(\beta)$ is a continuous function. $Z(0)=|\calX^n|$ and
$\lim_{\beta\to\infty}\frac{\ln Z(\beta)}{\beta}=-E_{GS}$.
\item Generating moments: $\langle\calE\rangle =-\dd\ln Z/\dd\beta$,
$\mbox{Var}\{\calE(\bX)\}=\dd^2\ln Z/\dd\beta^2$ $\rightarrow$ convexity of
$\ln Z$, and hence also of $\phi(\beta)$.
\item $\phi$ and $\Sigma$ are a Legendre--transform pair. $\Sigma$ is
concave.
\item $\Sigma(\epsilon)$ coincides with the Shannon entropy of the B-G
distribution.
\item $F_Q=F_P+kT\cdot D(Q\|P).$
\end{enumerate}

\noindent
{\bf Exercise:} Consider $Z(\beta)$ for an {\it imaginary temperature}
$\beta=j\omega$, where $j=\sqrt{-1}$, and define $z(E)$ as the inverse
Fourier transform of $Z(j\omega)$. Show that $z(E)=\Omega(E)$ is the density of states,
i.e., for $E_1 < E_2$, the number of states with energy between $E_1$ and
$E_2$ is given by $\int_{E_1}^{E_2}z(E)\dd E$.$~~~~\Box$\\
Thus, $Z(\cdot)$ can be related to energy enumeration in two different ways:
one is by the Legendre transform of $\ln Z$ for real $\beta$, and the other
is by the inverse Fourier transform of $Z$ for imaginary $\beta$.
This double connection between $Z$ and $\Omega$ is no coincidence, as we shall
see later on.

\vspace{0.25cm}

\noindent
{\it Example -- A two level system.} Similarly to the
earlier example of Schottky defets, which was previously given in the context
of the microcanonical ensemble,
consider now a system of $n$ independent
particles, each having two possible states: state $0$ of zero energy and
state $1$, whose energy is $\epsilon_0$, i.e., $\calE(x)=\epsilon_0x$,
$x\in\{0,1\}$. The $x_i$'s are independent, each having a marginal:
\begin{equation}
P(x)=\frac{e^{-\beta\epsilon_0x}}{1+e^{-\beta\epsilon_0}}~~~x\in\{0,1\}.
\end{equation}
In this case,
\begin{equation}
\phi(\beta )=\ln(1+e^{-\beta\epsilon_0})
\end{equation}
and 
\begin{equation}
\Sigma(\epsilon)=\min_{\beta\ge
0}[\beta\epsilon+\ln(1+e^{-\beta\epsilon_0})].
\end{equation}
To find $\beta^*(\epsilon)$, we take the derivative and equate to zero:
\begin{equation}
\epsilon-\frac{\epsilon_0e^{-\beta\epsilon_0}}{1+e^{-\beta\epsilon_0}}=0
\end{equation}
which gives
\begin{equation}
\beta^*(\epsilon)=\frac{\ln(\epsilon/\epsilon_0-1)}{\epsilon_0}.
\end{equation}
On substituting this back into the above expression of $\Sigma(\epsilon)$, we
get:
\begin{equation}
\Sigma(\epsilon)=\frac{\epsilon}{\epsilon_0}\ln\left(\frac{\epsilon}{\epsilon_0}-1\right)
+\ln\left[1+\exp\left\{-\ln\left(\frac{\epsilon}{\epsilon_0}-1\right)\right\}\right],
\end{equation}
which after a short algebraic manipulation, becomes
\begin{equation}
\Sigma(\epsilon)=h_2\left(\frac{\epsilon}{\epsilon_0}\right),
\end{equation}
just like in the Schottky example. In the other direction:
\begin{equation}
\phi(\beta)=\max_\epsilon\left[h_2\left(\frac{\epsilon}{\epsilon_0}\right)-
\beta\epsilon\right],
\end{equation}
whose achiever $\epsilon^*(\beta)$ solves the zero--derivative equation:
\begin{equation}
\frac{1}{\epsilon_0}\ln\left[\frac{1-\epsilon/\epsilon_0}{\epsilon/\epsilon_0}\right]=\beta
\end{equation}
or equivalently,
\begin{equation}
\epsilon^*(\beta)=\frac{\epsilon_0}{1+e^{-\beta\epsilon_0}},
\end{equation}
which is exactly the inverse function of $\beta^*(\epsilon)$ above, and
which when plugged back into the expression of $\phi(\beta)$, indeed gives
\begin{equation}
\phi(\beta)=\ln(1+e^{-\beta\epsilon_0}).~~~~\Box
\end{equation}

\vspace{0.25cm}

\noindent
{\it Comment:} A very similar model 
(and hence with similar results)
pertains to non--interacting spins
(magnetic moments), where the only difference is that $x\in\{-1,+1\}$ rather
than $x\in\{0,1\}$. Here, the meaning of the parameter $\epsilon_0$
becomes that of a magnetic field, which is more customarily denoted by 
$B$ (or $H$), and which is either parallel or antiparallel to
that of the spin, and so the potential energy 
(in the appropriate physical units), $\vec{B}\cdot\vec{x}$, is either
$Bx$ or $-Bx$. Thus,
\begin{equation}
P(x)=\frac{e^{\beta Bx}}{2\cosh(\beta B)};~~~Z(\beta)=2\cosh(\beta B).
\end{equation}
The net {\it magnetization} per--spin is defined as
\begin{equation}
m\dfn \left< \frac{1}{n}\sum_{i=1}^nX_i\right> = \langle X_1\rangle=
\frac{\partial \phi}{\partial (\beta
B)}=\tanh(\beta B).
\end{equation}
This is the paramagnetic characteristic of the magnetization as a function of
the magnetic field: As $B\to\pm\infty$, the magnetization $m\to\pm 1$
accordingly. When the magnetic field is removed ($B=0$), the magnetization
vanishes too.
We will get back to this model and its extensions in the sequel. $\Box$

\vspace{0.25cm}

\noindent
{\bf Exercise:} Consider a system of $n$ non--interacting particles,
each having a quadratic Hamiltonian, $\calE(x)=\frac{1}{2}\alpha x^2$,
$x\in\reals$. Show that here, 
\begin{equation}
\Sigma(\epsilon)=\frac{1}{2}\ln\left(\frac{4\pi e\epsilon}{\alpha}\right)
\end{equation}
and 
\begin{equation}
\phi(\beta)=\frac{1}{2}\ln\left(\frac{2\pi}{\alpha\beta}\right).
\end{equation}
Show that $\beta^*(\epsilon)=1/(2\epsilon)$ and hence
$\epsilon^*(\beta)=1/(2\beta)$. 

\subsection{The Energy Equipartition Theorem}

From the last exercise, we have learned that 
for a quadratic Hamiltonian, $\calE(x)=\frac{1}{2}\alpha x^2$, we have
$\epsilon^*(\beta)$, namely,
the average per--particle energy, is given $1/(2\beta)=kT/2$,
independently of $\alpha$. If we have $n$ such quadratic terms, then of course, we
end up with $nkT/2$. In the case of the ideal gas, we have 3 such terms (one
for each dimension) per particle, thus a total of $3n$ terms, and so,
$E=3nkT/2$, which is exactly what we obtained also in the microcanonical
ensemble, which is equivalent (recall that this was obtained then 
by equating $1/T$ to the derivative of $S(E)=k\ln[\mbox{const}\times
E^{3n/2}]$).
In fact, we observe that in the canonical ensemble,
whenever we have an Hamiltonian of the form $\frac{\alpha}{2}x_i^2+$
some arbitrary terms that do not depend on $x_i$, 
then $x_i$ is Gaussian
(with variance $kT/\alpha$) and independent
of the other guys, i.e.,
$p(x_i)\propto
e^{-\alpha x_i^2/(2kT)}$.
Hence it contributes an amount of 
\begin{equation}
\left<\frac{1}{2}\alpha X_i^2\right> =\frac{1}{2}\alpha\cdot
\frac{kT}{\alpha}=
\frac{kT}{2}
\end{equation}
to the total
average energy, independently of $\alpha$. It is more precise to refer
to this $x_i$ as a
{\it degree of freedom} rather than a particle. This is because in
the 3D world, the kinetic energy, for example, is given by
$p_x^2/(2m)+p_y^2/(2m)+p_z^2/(2m)$, that is, each particle contributes {\it three}
additive quadratic terms rather than one (just like three independent one--dimensional
particles) and so, it contributes $3kT/2$. This principle is called the
{\it the energy equipartition theorem}. In the sequel, we will see that it is
quite intimately related to rate--distortion theory for quadratic distortion
measures. 

Below is a direct derivation of the equipartition theorem:
\begin{eqnarray}
\left<\frac{1}{2}aX^2\right> &=& \frac{\int_{-\infty}^{\infty}\dd
x(\alpha x^2/2) e^{-\beta\alpha x^2/2}}{\int_{-\infty}^{\infty}\dd
xe^{-\beta\alpha x^2/2)}}~~~\mbox{num.\ \& den.\ have closed
forms, but we use another way:}\nonumber\\
&=&-\frac{\partial}{\partial \beta}\ln\left[\int_{-\infty}^{\infty}\dd xe^{-\beta\alpha x^2/2}
\right]\nonumber\\
&=&-\frac{\partial}{\partial \beta}\ln\left[\frac{1}{\sqrt{\beta}}
\int_{-\infty}^{\infty}\dd(\sqrt{\beta}x)e^{-\alpha(\sqrt{\beta}x)^2/2}\right]\nonumber\\
&=&-\frac{\partial}{\partial \beta}\ln\left[\frac{1}{\sqrt{\beta}}
\int_{-\infty}^{\infty}\dd ue^{-\alpha u^2/2}\right]~~~\mbox{The integral is
now a constant, independent of $\beta$.}\nonumber\\
&=&\frac{1}{2}\frac{\dd
\ln\beta}{\dd\beta}=\frac{1}{2\beta}=\frac{kT}{2}.\nonumber
\end{eqnarray}
This simple trick, that bypasses the need to calculate integrals,
can easily be extended in two directions at least (exercise):
\begin{itemize}
\item Let $\bx\in\reals^n$ and let $\calE(\bx)=\frac{1}{2}\bx^TA\bx$, where $A$ is
a $n\times n$ positive definite matrix. This corresponds to a physical system
with a quadratic Hamiltonian, which includes also interactions between pairs (e.g.,
Harmonic oscillators or springs, which are coupled because they are tied
to one another). It turns out that here, regardless of $A$, we get:
\begin{equation}
\langle \calE(\bX)\rangle = \left<\frac{1}{2}\bX^TA\bX\right> = n\cdot\frac{kT}{2}.
\end{equation}
\item Back to the case of a scalar $x$, but suppose now a more general power--law
Hamiltoinan, $\calE(x)=\alpha|x|^\theta$. In this case, we get
\begin{equation}
\langle \calE(X)\rangle = \left<\alpha|X|^\theta\right> = \frac{kT}{\theta}.
\end{equation}
Moreover, if $\lim_{x\to\pm\infty} xe^{-\beta\calE(x)}=0$ for all $\beta > 0$,
and we denote $\calE'(x)\dfn \dd\calE(x)/\dd x$, then
\begin{equation}
\langle X\cdot\calE'(X)\rangle =kT.
\end{equation}
It is easy to see that the earlier power--law result is obtained as a special case of
this, as $\calE'(x)=\alpha\theta|x|^{\theta-1}\mbox{sgn}(x)$ in this case.
\end{itemize}

\vspace{0.25cm}

\noindent
{\it Example/Exercise -- Ideal gas with gravitation:} Let
\begin{equation}
\calE(x)= \frac{p_x^2+p_y^2+p_z^2}{2m}+mgz.
\end{equation}
The average kinetic energy of each particle is $3kT/2$, as said before.
The contribution of the average potential energy is $kT$ (one degree of
freedom with $\theta=1$). Thus, the total is $5kT/2$, where $60\%$ come from
kinetic energy and $40\%$ come from potential energy, universally,
that is, independent of $T$, $m$, and $g$. $\Box$

\input{grandcanonical}

\subsection{Gibbs' Inequality, the 2nd Law, and the Data Processing
Thm}

While the laws of physics draw the boundaries between the possible and the
impossible in Nature, the coding theorems of information theory, or
more precisely, their converses, draw the
boundaries between the possible and the impossible in coded communication
systems and data processing. Are there any relationships between these two
facts?

We are now going to demonstrate that there are some indications that
the answer to this question is affirmative. In particular, we are going to
see that there is an intimate relationship between the second law of
thermodynamics and the data processing theorem (DPT), asserting that
if $X\to U\to V$ is a Markov chain, then $I(X;U)\ge I(X;V)$. The reason for
focusing our attention on the DPT is that it is actually the most fundamental
inequality that supports most (if not all) proofs of converse theorems in IT.
Here are just a few points that make this quite clear.
\begin{enumerate}
\item {\it Lossy/lossless source coding}: Consider a source vector
$U^N=(U_1,\ldots U_N)$
compressed into a bitstream $X^n=(X_1,\ldots,X_n)$ from which the decoder
generates a reproduction $V^N=(V_1,\ldots,V_N)$ with distortion
$\sum_{i=1}^N \bE\{d(U_i,V_i)\}\le ND$. Then, by the DPT,
$I(U^N;V^N)\le I(X^n;X^n)=H(X^n)$, where $I(U^N;V^N)$ is further lower bounded
by
$NR(D)$ and $H(X^n)\le n$, which together lead to the converse to the lossy
data
compression theorem, asserting that the compression ratio $n/N$ cannot be
less than $R(D)$. The case of lossless compression is obtained as a special
case where $D=0$.
\item {\it Channel coding under bit error probability}: Let $U^N=(U_1,\ldots
U_N)$
be drawn from the binary symmetric course (BSS), designating $M=2^N$
equiprobable
messages of length $N$. The encoder maps $U^N$ into a channel input vector
$X^n$, which in turn, is sent across the channel. The receiver observes $Y^n$,
a noisy version of $X^n$, and decodes the message as $V^N$. Let
$P_b=\frac{1}{N}\sum_{i=1}^N\mbox{Pr}\{V_i\ne U_i\}$ designate
the bit error probability. Then, by the DPT, $I(U^N;V^N)\le I(X^n;Y^n)$, where
$I(X^n;Y^n)$ is further upper bounded by $nC$, $C$ being the channel capacity,
and $I(U^N;V^N)=H(U^N)-H(U^N|V^N)\ge N-\sum_{i=1}^N H(U_i|V_i)\ge
N-\sum_ih_2(\mbox{Pr}\{V_i\ne U_i\})\ge N[1-h_2(P_b)]$.
Thus, for $P_b$ to vanish, the coding rate, $N/n$ should not exceed $C$.
\item {\it Channel coding under block error probability -- Fano's inequality}:
Same as in the previous item, except that the error performance is the block
error probability $P_B=\mbox{Pr}\{V^N\ne U^N\}$. This, time $H(U^N|V^N)$,
which is identical to $H(U^N,E|V^N)$, with $E\equiv \calI\{V^N\ne U^N\}$, is
decomposed as $H(E|V^N)+H(U^N|V^N,E)$, where the first term is upper bounded
by 1 and the second term is upper bounded by $P_B\log(2^N-1) < NP_B$, owing to
the fact that the maximum of $H(U^N|V^N,E=1)$ is obtained when $U^N$ is
distributed uniformly over all $V^N\ne U^N$. Putting these facts all together,
we obtain Fano's inequality $P_B\ge 1-1/n-C/R$, where $R=N/n$ is the coding
rate. Thus, the DPT directly supports Fano's inequality,
which in turn is the main tool for proving converses to channel
coding theorems in a large variety of communication situations, including
network configurations.
\item {\it Joint source--channel coding and the separation principle}: In a
joint
source--channel situation, where the source vector $U^N$ is mapped to a
channel input vector $X^n$ and the channel output vector $Y^n$ is decoded into
a reconstruction $V^N$, the DPT gives rise to the chain
of inequalities $NR(D)\le I(U^N;V^N)\le I(X^n;Y^n)\le nC$, which is the
converse to the joint source--channel coding theorem, whose direct part can
be achieved by separate source- and channel coding. Items 1 and 2 above are
special
cases of this.
\item {\it Conditioning reduces entropy}: Perhaps even more often than the
term ``data processing theorem'' can be found as part of a proof of
a converse theorem,  one encounters an equivalent of this theorem
under the slogan ``conditioning reduces entropy''. This in turn is part of
virtually every
converse proof in the literature. Indeed, if $(X,U,V)$ is a triple of RV's,
then this statement means that $H(X|V)\ge H(X|U,V)$. If, in addition, $X\to
U\to V$
is a Markov chain, then $H(X|U,V)=H(X|U)$, and so, $H(X|V)\ge H(X|U)$, which
in turn is equivalent to the more customary form of the DPT, $I(X;U)\ge
I(X;V)$, obtained by subtracting $H(X)$ from both sides of the entropy
inequality. In fact, as we shall see shortly, it is this entropy inequality
that lends itself more naturally to a
physical interpretation. Moreover, we can think of the
conditioning--reduces--entropy inequality as another form of the DPT even in
the absence of the aforementioned Markov condition, because $X\to(U,V)\to V$
is always a
Markov chain.
\end{enumerate}

Turning now to the physics point of view,
consider a system
which may have two possibile Hamiltonians -- $\calE_0(\bx)$ and
$\calE_1(\bx)$.
Let $Z_i(\beta)$, denote the partition function pertaining to
$\calE_i(\cdot)$,
that is
\begin{equation}
Z_i(\beta)=\sum_{\bx} e^{-\beta\calE_i(\bx)},~~~i=0,1.
\end{equation}
The {\it Gibbs' inequality} asserts that
\begin{equation}
\ln Z_1(\beta)\ge \ln
Z_0(\beta)+\beta\langle\calE_0(\bX)-\calE_1(\bX)\rangle_0
\end{equation}
where $\langle\cdot\rangle_0$ denotes averaging w.r.t.\ $P_0$ -- the canonical
distribution
pertaining the Hamiltonian $\calE_0(\cdot)$. Equivalently, this inequality can
be presented as follows:
\begin{equation}
\langle\calE_1(\bX)-\calE_0(\bX)\rangle_0\ge
\left[-\frac{\ln Z_1(\beta)}{\beta}\right]-
\left[-\frac{\ln Z_0(\beta)}{\beta}\right]\equiv F_1-F_0, ~~~~~~~~\mbox{(*)}
\end{equation}
where $F_i$ is the free energy pertaining to the canonical ensemble of
$\calE_i$, $i=0,1$.

This inequality is easily proved by defining
an Hamiltoinan $\calE_\lambda(\bx)=(1-\lambda)\calE_0(\bx)+
\lambda\calE_1(\bx)=\calE_0(\bx)+\lambda[\calE_1(\bx)-\calE_0(\bx)]$
and using the convexity of the corresponding
log--partition function w.r.t.\ $\lambda$. Specifically, let us define the
partition
function:
\begin{equation}
Z_\lambda(\beta)=\sum_{\bx} e^{-\beta\calE_\lambda(\bx)}.
\end{equation}
Now, since $\calE_{\lambda}(\bx)$ is affine in $\lambda$, then it is easy
to show that $\dd^2\ln Z_\lambda/\dd\lambda^2\ge 0$ (just like this
was done with $\dd^2\ln Z(\beta)/\dd\beta^2\ge 0$ before) and so
$\ln Z_\lambda(\beta)$ is convex in $\lambda$ for fixed $\beta$.
It follows then that the curve of $\ln Z_\lambda(\beta)$, as a function of
$\lambda$, must lie above the straight line that is tangent to this curve
at $\lambda=0$ (see Fig.\ \ref{lnzconvex}), that is, the graph corresponding
to the affine function $\ln Z_0(\beta)+\lambda\cdot\left[\frac{\partial\ln
Z_\lambda(\beta)}{\partial\lambda}\right]_{\lambda=0}$.
\begin{figure}[ht]
\hspace*{3cm}\input{lnzconvex.pstex_t}
\caption{\small The function $\ln Z_\lambda(\beta)$ is convex in $\lambda$ and
hence lies above its tangent at the origin.}
\label{lnzconvex}
\end{figure}
In particular,
setting $\lambda=1$, we get:
\begin{equation}
\ln Z_1(\lambda)\ge \ln
Z_0(\beta)+\frac{\partial\ln
Z_\lambda(\beta)}{\partial\lambda}\bigg|_{\lambda=0}.
\end{equation}
and the second term is:
\begin{equation}
\frac{\partial\ln Z_\lambda(\beta)}{\partial\lambda}\bigg|_{\lambda=0}=
\frac{\beta\sum_{\bx}[\calE_0(\bx)-\calE_1(\bx)] e^{-\beta\calE_0(\bx)}}{
\sum_{\bx}e^{-\beta\calE_0(\bx)}}\dfn
\beta\left<\calE_0(\bX)-\calE_1(\bX)\right>_0,
\end{equation}
Thus, we have obtained
\begin{equation}
\ln \left[\sum_{\bx}e^{-\beta\calE_1(\bx)}\right]\ge
\ln \left[\sum_{\bx}e^{-\beta\calE_0(\bx)}\right]+
\beta\left<\calE_0(\bX)-\calE_1(\bX)\right>_0,
\end{equation}
and the proof is complete. In fact, the l.h.s.\ minus the r.h.s.\ is nothing
but
$D(P_0\|P_1)$, where $P_i$ is the B--G distribution pertaining to
$\calE_i(\cdot)$, $i=0,1$.

We now offer a possible physical interpretation to the Gibbs' inequality:
Imagine that a
system with Hamiltoinan $\calE_0(\bx)$ is in equilibrium for all $t < 0$, but
then, at time $t=0$, the Hamitonian changes {\it abruptly} from the
$\calE_0(\bx)$ to $\calE_1(\bx)$ (e.g., by suddenly applying a force on the
system),
which means that if the system is found at
state
$\bx$ at time $t=0$, additional energy of $W=\calE_1(\bx)-\calE_0(\bx)$ is
suddenly
`injected' into the system. This additional energy can be thought of as work
performed on the system, or as supplementary potential energy.
Since this passage between $\calE_0$ and $\calE_1$ is abrupt,
the average of $W$ should be taken
w.r.t.\ $P_0$,
as the state $\bx$ does not change instantaneously.
This average is exactly what we have at the left--hand side eq.\ (*).
The Gibbs inequality tells us then that
this average work is at least as large as
$\Delta F=F_1-F_0$, the increase in free energy.\footnote{This is
related to the interpretation
of the free--energy difference $\Delta F=F_1-F_0$
as being the maximum amount of work in an isothermal process.}
The difference $\langle W\rangle_0-\Delta F$ is due to the irreversible nature
of the abrupt energy injection, and this irreversibility
means an increase of the total entropy of the system and its environment, and
so, the Gibbs'
inequality is, in fact, a version of the second law of
thermodynamics.\footnote{
From a more general physical perspective, the Jarzynski equality tells
that under certain conditions on the test system and the heat bath,
and given any protocol $\{\lambda(t)\}$ of
changing the control variable $\lambda$ (of $\calE_\lambda(\bx)$), the work
$W$ applied to the system
is a RV which satisfies $\langle e^{-\beta W}\rangle = e^{-\beta\Delta F}$.
By Jensen's inequality, $\langle e^{-\beta W}\rangle$ is lower bounded by
$e^{-\beta\langle W\rangle}$,
and so, we obtain
$\langle W\rangle \ge \Delta F$ (which is known as the
minimum work principle), now in more generality than in the Gibbs'
inequality, which is limited to the
case where $\lambda(t)$ is a step function.
At the other extreme, when
$\lambda(t)$ changes very slowly, corresponding to a reversible process, $W$
approaches determinism, and then Jensen's inequality becomes tight, which
then gives (in the limit) $W=\Delta F$ with no increase in entropy.}
This excess work beyond the free--energy increase, $\langle W\rangle_0-\Delta
F$,
which can be thought of as the ``dissipated work,''
can easily shown (exercise) to be equal to $kT\cdot D(P_0\|P_1)$, where
$P_0$ and $P_1$ are the canonical distributions pertaining to $\calE_0$ and
$\calE_1$, respectively. Thus, the divergence is given yet another physical
significance.

Now, let us see how the Gibbs' inequality is related to the DPT.
Consider a triple of random variables $(\bX,\bU,\bV)$ which
form a Markov chain $\bX\to \bU\to \bV$.
The DPT asserts that $I(\bX;\bU)\ge I(\bX;\bV)$.
We can obtain the DPT as a special case of the Gibbs inequality as follows:
For a given realization $(\bu,\bv)$ of the random variables $(\bU,\bV)$,
consider
the Hamiltonians
\begin{equation}
\calE_0(\bx)=-\ln P(\bx|\bu)=-\ln P(\bx|\bu,\bv)
\end{equation}
and
\begin{equation}
\calE_1(\bx)=-\ln P(\bx|\bv).
\end{equation}
Let us also set $\beta=1$. Thus, for a given $(\bu,\bv)$:
\begin{equation}
\langle W\rangle_0=\langle\calE_1(\bX)-\calE_0(\bX)\rangle_0=
\sum_{\bx} P(\bx|\bu,\bv)[\ln P(\bx|\bu)-\ln P(\bx|\bv)]
=H(\bX|\bV=\bv)-H(\bX|\bU=\bu)
\end{equation}
and after further averaging w.r.t.\ $(\bU,\bV)$,
the average work becomes $H(\bX|\bV)-H(\bX|\bU)=I(\bX;\bU)-I(\bX;\bV)$.
Concerning the free energies, we have
\begin{equation}
Z_0(\beta=1)=\sum_{\bx} \exp\{-1\cdot[-\ln P(\bx|\bu,\bv)]\}=\sum_{\bx}
P(\bx|\bu,\bv)=1
\end{equation}
and similarly,
\begin{equation}
Z_1(\beta=1)=\sum_{\bx} P(\bx|\bv)=1
\end{equation}
which means that $F_0=F_1=0$, and so $\Delta F=0$ as well. So by the Gibbs
inequality, the
average work $I(\bX;\bU)-I(\bX;\bV)$ cannot be smaller than the free--energy
difference, which
in this case vanishes, namely, $I(\bX;\bU)-I(\bX;\bV)\ge 0$, which is the DPT.
Note that in this case, there is a maximum degree of irreversibility:
The identity $I(\bX;\bU)-I(\bX;\bV)=H(\bX|\bV)-H(\bX|\bU)$ means that
whole work $W=I(\bX;\bU)-I(\bX;\bV)$ goes for entropy increase
$S_1T-S_0T=H(\bX|\bV)\cdot
1-H(\bX|\bU)\cdot 1$, whereas the free energy remains unchanged, as mentioned
earlier. Note that the Jarzynski formula (cf.\ last footnote) holds in this
special case, i.e., $\langle e^{-1\cdot W}\rangle = e^{-1\cdot\Delta F}=1$.

The difference between $I(\bX;\bU)$ and $I(\bX;\bV)$,
which accounts for the rate loss in any suboptimal coded communication system,
is then given the meaning of irreversibility and entropy production in the
corresponding physical system. Optimum
(or nearly optimum) communication systems are corresponding to quasistatic
isothermal processes,
where the full free energy is exploited and no work is dissipated (or no work
is carried out at all, in the first place). In other
words, had there been a communication system that violated the converse to the
source/channel coding theorem, one could have created a corresponding physical
system that
violates the second law of thermodynamics, and this, of course, cannot be
true.

\subsection{Large Deviations Theory and Physics of Information Measures}

As I said in the Intro, large deviations theory, the branch of probability
theory that deals with exponential decay rates of probabilities of rare events, has strong
relations to IT, which we have already seen in the IT course through the
eye glasses of the method of types and Sanov's theorem. On the other hand,
large deviations theory has also a strong connection to statistical mechanics,
as we are going to see shortly. Therefore, one of the links between IT and
statistical mechanics goes through rate functions of large deviations theory, or more
concretely, Chernoff bounds. This topic is based on the paper:
N.~Merhav,
``An identity of Chernoff bounds
with an interpretation in statistical physics and
applications in information theory,''
{\it IEEE Trans.\ Inform.\ Theory}, vol.\ 54, no.\ 8, pp.\
3710--3721, August 2008.

Let us begin with a very simple question: We have a bunch of i.i.d.\ RV's\
$X_1,X_2,\ldots$ and a certain real function $\calE(x)$. How fast does the
probability of the event
$$\sum_{i=1}^n\calE(X_i)\le nE_0$$
decay as $n$ grows without bound, assuming that $E_0 <
\langle\calE(X)\rangle$ (so that this would be a rare event)?
One way to handle this problem, at least in the finite alphabet case, is the
method of types. Another method is the Chernoff bound:
\begin{eqnarray}
\mbox{Pr}\left\{\sum_{i=1}^n\calE(X_i)\le nE_0\right\}&=&
\bE \calI\left\{\sum_{i=1}^n\calE(X_i)\le nE_0\right\}~~~~\calI(\cdot)~\mbox{denoting
the indicator function}\nonumber\\
&\le&\bE \exp\left\{\beta\left[nE_0-\sum_{i=1}^n\calE(X_i)
\right]\right\}~~~~~\leftarrow~~\forall~\beta\ge 0:~\calI\{Z< a\}\le e^{\beta(a-Z)} \nonumber\\
&=&e^{\beta nE_0}\bE\exp\left\{-\beta\sum_{i=1}^n\calE(X_i)\right\}\nonumber\\
&=&e^{\beta nE_0}\bE\left\{\prod_{i=1}^n\exp\{-\beta\calE(X_i)\}\right\}\nonumber\\
&=&e^{\beta nE_0}\left[\bE\exp\{-\beta\calE(X_1)\}\right]^n\nonumber\\
&=&\exp\left\{n\left[\beta E_0+\ln\bE\exp\{-\beta\calE(X_1)\}\right]\right\}\nonumber
\end{eqnarray}
As this bound applies for every $\beta\ge 0$, the tightest bound of this
family is obtained by minimizing the r.h.s.\ over $\beta$, which yields
the exponential rate function:
\begin{equation}
\Sigma(E_0)=\min_{\beta\ge 0}[\beta E_0+\phi(\beta)],
\end{equation}
where
\begin{equation}
\phi(\beta)=\ln Z(\beta)
\end{equation}
and
\begin{equation}
Z(\beta)=\bE e^{-\beta\calE(X)}=\sum_x p(x)e^{-\beta\calE(x)}.
\end{equation}
Rings a bell? Note that $Z(\beta)$ here differs from the partition function that
we have encountered thus far only slighlty: the Boltzmann exponentials are
weighed by $\{p(x)\}$ which are independent of $\beta$. But this is not a
crucial difference: one can imagine a physical system where each microstate $x$
is actually a representative of a bunch of more refined microstates $\{x'\}$, whose
number is proportional to $p(x)$ and which all have the same energy as $x$,
that is, $\calE(x')=\calE(x)$. In the domain of the more refined system,
$Z(\beta)$ is (up to a constant) a non--weighted sum of exponentials, as it
should be. More precisely, if $p(x)$ is (or can be approximated by) a rational number
$N(x)/N$, where $N$ is independent of $x$, then imagine that each $x$ gives
rise to $N(x)$ microstates $\{x'\}$ with the same energy as $x$, so that
\begin{equation}
Z(\beta)=\frac{1}{N}\sum_xN(x)e^{-\beta\calE(x)}=\frac{1}{N}\sum_{x'}e^{-\beta\calE(x')},
\end{equation}
and we are back to an ordinary, non--weighted partition function, upto the
constant $1/N$, which is absolutely immaterial.

To summarize what we have seen thus far: the exponential rate function is given by the
Legendre transform of the log--moment generating function. The Chernoff
parameter $\beta$ to be optimized plays the role of the equilibrium temperature
pertaining to energy $E_0$.

Consider next what happens when $p(x)$ is itself a B--G distribution with
Hamiltonian $\calE(x)$ at a certain inverse temperature $\beta_1$, that is
\begin{equation}
p(x)=\frac{e^{-\beta_1\calE(x)}}{\zeta(\beta_1)}
\end{equation}
with
\begin{equation}
\zeta(\beta_1)\dfn\sum_xe^{-\beta_1\calE(x)}.
\end{equation}
In this case, we have
\begin{equation}
Z(\beta)=\sum_x p(x)e^{-\beta\calE(x)}=\frac{\sum_x
e^{-(\beta_1+\beta)\calE(x)}}{\zeta(\beta_1)}=\frac{\zeta(\beta_1+\beta)}{\zeta(\beta_1)}.
\end{equation}
Thus,
\begin{eqnarray}
\Sigma(E_0)&=&\min_{\beta\ge 0}[\beta
E_0+\ln\zeta(\beta_1+\beta)]-\ln\zeta(\beta_1)\nonumber\\
&=&\min_{\beta\ge 0}[(\beta+\beta_1)
E_0+\ln\zeta(\beta_1+\beta)]-\ln\zeta(\beta_1)-\beta_1E_0\nonumber\\
&=&\min_{\beta\ge \beta_1}[\beta
E_0+\ln\zeta(\beta)]-\ln\zeta(\beta_1)-\beta_1E_0\nonumber\\
&=&\min_{\beta\ge \beta_1}[\beta
E_0+\ln\zeta(\beta)]-[\ln\zeta(\beta_1)+\beta_1E_1]+\beta_1(E_1-E_0)\nonumber
\end{eqnarray}
where $E_1$ is the energy corresponding to $\beta_1$, i.e., $E_1$ is such that
\begin{equation}
\sigma(E_1)\dfn \min_{\beta\ge 0}[\beta E_1+\ln\zeta(\beta)]
\end{equation}
is achieved  by $\beta=\beta_1$. Thus, the second bracketted term of the
right--most side of the last chain is exactly $\sigma(E_1)$, as defined.
If we now assume that $E_0 < E_1$, which is reasonable, because $E_1$ is the
average of $\calE(X)$ under $\beta_1$, and we are assuming that we are dealing
with a rare event where $E_0 < \langle \calE(X)\rangle$. In this case, the
achiever $\beta_0$ of $\sigma(E_0)$ must be larger than $\beta_1$ anyway, and
so, the first bracketted term on the right--most side of the last chain
agrees with $\sigma(E_0)$. We have obtained then that the exponential decay
rate (the rate function) is given by
\begin{equation}
I=-\Sigma(E_0)=\sigma(E_1)-\sigma(E_0)-\beta_1(E_1-E_0).
\end{equation}
Note that $I\ge 0$ thanks to the fact that $\sigma(\cdot)$ is concave. 
It has a simple graphical intepretation as the height difference,
as seen at the point $E=E_0$, between
the tangent to the curve $\sigma(E)$ at $E=E_1$ and the function $\sigma(E)$
itself (see Fig.\ \ref{chernoff}).

\begin{figure}[ht]
\hspace*{5cm}\input{chernoff.pstex_t}
\caption{\small Graphical interpretation of the LD rate function $I$.}
\label{chernoff}
\end{figure}

Another look is the following: 
\begin{eqnarray}
I&=&\beta_1\left[\left(E_0-\frac{\sigma(E_0)}{\beta_1}\right)-
\left(E_1-\frac{\sigma(E_1)}{\beta_1}\right)\right]\nonumber\\
&=&\beta_1(F_0-F_1)\nonumber\\
&=&D(P_{\beta_0}\|P_{\beta_1})\nonumber\\
&=&\min\{D(Q\|P_{\beta_1}):~\bE_Q\calE(X)\le
E_0\}~~~~\leftarrow~\mbox{exercise}\nonumber
\end{eqnarray}
The last line is exactly what we would have obtained using the method of
types. This means that the dominant instance of the large deviations event
under discussion pertains to thermal equilibrium (minimum free energy)
complying with the constraint(s) dictated by this event. This will also be the
motive of the forthcoming results.

\vspace{0.2cm}

\noindent
{\bf Exercise:} What happens if $p(x)$ is B--G with an Hamiltonian
$\hat{\calE}(\cdot)$, different from the one of the LD event? $\Box$

Let us now see how this discussion relates to very fundamental information
measures, like the rate--distortion function and channel capacity.
To this end, let us first slightly extend the above Chernoff bound.
Assume that in addition to the RV's $X_1,\ldots,X_n$, there is
also a deterministic sequence of the same length, $y_1,\ldots,y_n$, where
each $y_i$ takes on values in a finite alphabet $\calY$. Suppose also
that the asymptotic regime is such that as $n$ grows without bound, the
relative frequencies $\{\frac{1}{n}\sum_{i=1}^n1\{y_i=y\}\}_{y\in\calY}$ converge to
certain probabilities $\{q(y)\}_{y\in\calY}$. Furthermore, the $X_i$'s
are still independent, but they are no longer necessarily identically
distributed: each one of them is governed by $p(x_i|y_i)$, that is,
$p(\bx|\by)=\prod_{i=1}^n p(x_i|y_i)$. Now, the question is how does
the exponential rate function behave if we look at the event
\begin{equation}
\sum_{i=1}^n\calE(X_i,y_i)\le nE_0
\end{equation}
where $\calE(x,y)$ is a given `Hamiltonian'. What is the motivation for this
question? Where and when do we encounter such a problem?

Well, there are many examples (cf.\ the above mentioned paper), but 
here are two very classical ones, where rate functions of LD events
are directly related to very important information measures.
In both examples, the distributions $p(\cdot|y)$ are
actually the same for all $y\in\calY$ (namely, $\{X_i\}$ are again i.i.d.).
\begin{itemize}
\item {\it Rate--distortion coding.} 
Consider the good old problem of lossy compression with a randomly selected code.
Let $\by=(y_1,\ldots,y_n)$ 
be a given source sequence, typical to $Q=\{q(y),~y\in\calY\}$
(non--typical sequences are not important). Now,
let us randomly select $e^{nR}$ codebook vectors $\{\bX(i)\}$ according to
$p(\bx)=\prod_{i=1}^np(x_i)$. Here is how the direct part of the source coding
theorem essentially works: We first ask ourselves what is the probability that 
a single randomly selected codeword $\bX=(X_1,\ldots,X_n)$ would happen to
fall at distance $\le nD$ from $\by$, i.e., what is the exponential rate of
the probability of the event 
\begin{equation}
\sum_{i=1}^nd(X_i,y_i)\le nD\mbox{?}
\end{equation}
The answer is that it is exponentially about $e^{-nR(D)}$, and that's why we
need slightly more than one over this number, namely, $e^{+nR(D)}$ times to
repeat this `experiment' in order to see at least one `success',
which means being able to encode $\by$ within distortion $D$. So this is
clearly an instance of the above problem, where $\calE=d$ and $E_0=D$.
\item {\it Channel coding.} 
In complete duality, consider the classical channel coding problem,
for a discrete memoryless channel (DMC),
using a randomly selected code. Again, we have a code of size $e^{nR}$,
where each codeword is chosen independently according to
$p(\bx)=\prod_{i=1}^np(x_i)$. Let $\by$ the channel output vector, which is
(with very high probabaility), typical to $Q=\{q(y),~y\in\calY\}$, where
$q(y)=\sum_xp(x)W(y|x)$, $W$ being the single--letter transition probability
matrix of the DMC. Consider a (capacity--achieving) 
threshold decoder which selects the {\it unique}
codeword that obeys
\begin{equation}
\sum_{i=1}^n[-\ln W(y_i|X_i)]\le n[H(Y|X)+\epsilon]~~~~\epsilon>0
\end{equation}
and declares an error whenever no such codeword exists or when there is more
than one such codeword. Now, in the classical proof of the direct part of the
channel coding problem, we first ask ourselves: what is the probability that
an independently selected codeword (and hence not the one transmitted) $\bX$
will pass this threshold? The answer turns out to be exponentially $e^{-nC}$,
and hence we can randomly select up to slightly less than one over this
number, namely, $e^{+nC}$ codewords, before we start to see incorrect
codewords that pass the threshold. Again, this is clearly an instance of our
problem with $\calE(x,y)=-\ln W(y|x)$ and $E_0=H(Y|X)+\epsilon$.
\end{itemize}
Equipped with these two motivating examples, let us get back to the generic
problem we formalized, and see what happens. Once this has been done, we shall return to the
examples. There are (at least) two different ways to address the problem using Chernoff
bounds, and they lead to
two {\it seemingly} different expressions, but since the Chernoff bounding
technique gives the correct exponential behavior, these two expressions must
agree. This identity between the two expressions will have a physical
intepretation, as we shall see. 

The first approach is a direct extension of what we did before: 
\begin{eqnarray}
& &\mbox{Pr}\left\{\sum_{i=1}^n\calE(X_i,y_i)\le nE_0\right\}\nonumber\\
&=&
\bE \calI\left\{\sum_{i=1}^n\calE(X_i,y_i)\le nE_0\right\}\nonumber\\
&\le&\bE \exp\left\{\beta\left[nE_0-\sum_{i=1}^n\calE(X_i,y_i)
\right]\right\}\nonumber\\
&=&e^{n\beta E_0}\prod_{y\in\calY}\bE_y\exp\left\{-\beta
\sum_{i:y_i=y}\calE(X_i,y)\right\}~~~~
\bE_y\dfn\mbox{expectation under}~p(\cdot|y)\nonumber\\
&=&e^{\beta
nE_0}\prod_{y\in\calY}\left[\bE_y\exp\{-\beta\calE(X,y)\}\right]^{n(y)}~~~~n(y)\dfn\mbox{num.\
of}~\{y_i=y\}\nonumber\\
&=&\exp\left\{n\left[\beta
E_0+\sum_{y\in\calY}q(y)\ln\sum_{x\in\calX}p(x|y)\exp\{-\beta\calE(x,y)\}\right]\right\}\nonumber
\end{eqnarray}
and so, the resulting rate function is given by
\begin{equation}
\Sigma(E_0)=\min_{\beta\ge
0}\left[\beta E_0+\sum_{y\in\calY}q(y)\ln Z_y(\beta)\right]
\end{equation}
where
\begin{equation}
Z_y(\beta)\dfn\sum_{x\in\calX}p(x|y)\exp\{-\beta\calE(x,y)\}.
\end{equation}
In the rate--distortion example, this tells us that
\begin{equation}
R(D)=-\min_{\beta\ge 0}\left[\beta
D+\sum_{y\in\calY}q(y)\ln\sum_{x\in\calX}p(x)e^{-\beta
d(x,y)}\right].
\end{equation}
This is a well--known parametric representation of $R(D)$, which can be
obtained via a different route (see, e.g., Gray's book {\it Source Coding
Theory}), where the minimizing $\beta$ is known to have the graphical
interpretation of the local negative slope (or derivative) of the curve
of $R(D)$.
In the case of channel capacity, we obtain in a similar manner:
\begin{eqnarray}
C&=&-\min_{\beta\ge 0}\left[\beta
H(Y|X)+\sum_{y\in\calY}q(y)\ln\sum_{x\in\calX}p(x)e^{-\beta[-\ln
W(y|x)]}\right]\nonumber\\
&=&-\min_{\beta\ge 0}\left[\beta
H(Y|X)+\sum_{y\in\calY}q(y)\ln\sum_{x\in\calX}p(x)W^\beta(y|x)
\right].\nonumber
\end{eqnarray}
{\bf Exercise:} Show that for channel capacity, the minimizing $\beta$ is
always $\beta^*=1$. $\Box$

The other route is to handle each $y\in\calY$ separately: First, observe that
\begin{equation}
\sum_{i=1}^n\calE(X_i,y_i)=\sum_{y\in\calY}\sum_{i:~y_i=y}\calE(X_i,y),
\end{equation}
where now, in each partial sum over $\{i:~y_i=y\}$, we have i.i.d.\ RV's.
The event $\sum_{i=1}^n\calE(X_i,y_i)\le nE_0$ can then be thought of as the
union of all intersections
\begin{equation}
\bigcap_{y\in\calY}\left\{\sum_{i:~y_i=y}\calE(X_i,y)\le n(y)E_y\right\}
\end{equation}
where the union is across all ``possible partial energy allocations''
$\{E_y\}$ which satisfy $\sum_y q(y)E_y\le E_0$. Note that at least when the
$X_i$'s take values on a finite alphabet, each partial sum $\sum_{i:~y_i=y}\calE(X_i,y)$
can take only a polynomial number of values in $n(y)$ (why?), and so, it is
sufficient to `sample' the space of $\{E_y\}$ by polynomially many vectors
in order to cover all possible instances of the event under discussion (see
more details in the paper).
Thus,
\begin{eqnarray}
&&\mbox{Pr}\left\{\sum_{i=1}^n\calE(X_i,y_i)\le nE_0\right\}\nonumber\\
&=&\mbox{Pr}\bigcup_{\{E_y:~\sum_y q(y)E_y\le E_0\}}
\bigcap_{y\in\calY}\left\{\sum_{i:~y_i=y}\calE(X_i,y)\le
n(y)E_y\right\}\nonumber\\
&\exe&\max_{\{E_y:~\sum_y q(y)E_y\le E_0\}}\prod_{y\in\calY}\mbox{Pr}\left\{
\sum_{i:~y_i=y}\calE(X_i,y)\le n(y)E_y\right\}\nonumber\\
&\exe&\max_{\{E_y:~\sum_y q(y)E_y\le
E_0\}}\prod_{y\in\calY}\exp\left\{n(y)\min_{\beta_y\ge 0}[\beta_yE_y+\ln
Z_y(\beta)]\right\}\nonumber\\
&=&\exp\left\{n\cdot\max_{\{E_y:~\sum_y q(y)E_y\le
E_0\}}\sum_{y\in\calY}q(y)\Sigma_y(E_y)\right\}\nonumber
\end{eqnarray}
where we have defined
\begin{equation}
\Sigma_y(E_y)\dfn \min_{\beta_y\ge 0}\left[\beta_yE_y+\ln
Z_y(\beta_y)\right].
\end{equation}
We therefore arrived at an alternative expression of the rate function,
which is 
\begin{equation}
\max_{\{E_y:~\sum_y q(y)E_y\le
E_0\}}\sum_{y\in\calY}q(y)\Sigma_y(E_y).
\end{equation}
Since the two expressions must
agree, we got the following identity:
\begin{center}
\fbox{
$\Sigma(E_0)=\max_{\{E_y:~\sum_y q(y)E_y\le
E_0\}}\sum_{y\in\calY}q(y)\Sigma_y(E_y)$}
\end{center}
A few comments:\\

\noindent
1. In the paper there is also a direct proof of this identity, without
relying on Chernoff bound considerations.\\

\noindent
2. This identity accounts for a certain generalized concavity property of
the entropy function. Had all the $\Sigma_y(\cdot)$'s been the same function,
then this would have been the ordinary concavity property. What makes it
interesting is that it continues to hold for different $\Sigma_y(\cdot)$'s
too.\\

\noindent
3. The l.h.s.\ of this identity is defined by minimization over one
parameter only -- the inverse temperature $\beta$. On the other hand, on the
r.h.s.\ we have a separate inverse temperature for every $y$, because each
$\Sigma_y(\cdot)$ is defined as a separate minimization problem with its own
$\beta_y$. Stated differently, the l.h.s.\ is the minimum of a sum, whereas
in the r.h.s., for given $\{E_y\}$, we have the sum of minima. When do these
two  things agree? The answer is that it happens if all minimizers
$\{\beta_y^*\}$ happen to be the {\it same}. But $\beta_y^*$ depends on $E_y$.
So what happens is that the $\{E_y\}$ (of the outer maximization problem)
are such that the $\beta_y^*$ would all be the same, and would agree also
with the $\beta^*$ of $\Sigma(E_0)$. 
To see why this is true, consider the following chain of inequalities:
\begin{eqnarray}
& &\max_{\{E_y:~\sum_y q(y)E_y\le E_0\}}\sum_yq(y)\Sigma_y(E_y)\nonumber\\
&=&
\max_{\{E_y:~\sum_y q(y)E_y\le E_0\}}\sum_yq(y)\min_{\beta_y} [\beta_yE_y+\ln
Z_y(\beta_y)]\nonumber\\
&\le& \max_{\{E_y:~\sum_y q(y)E_y\le E_0\}}\sum_yq(y)[\beta^*E_y+\ln
Z_y(\beta^*)]~~~~~~~~~\mbox{where $\beta^*$ achieves
$\Sigma(E_0)$}\nonumber\\
&\le& \max_{\{E_y:~\sum_y q(y)E_y\le E_0\}}[\beta^*E_0+\sum_yq(y)\ln
Z_y(\beta^*)]~~~~~~~~\mbox{because $\sum_yq(y)E_y\le E_0$}\nonumber\\
&=& \beta^*E_0+\sum_yq(y)\ln
Z_y(\beta^*)~~~~~~~~\mbox{the bracketted expression no longer depends on $\{E_y\}$}\nonumber\\
&=&\Sigma(E_0).\nonumber
\end{eqnarray}
Both inequalities become equalities 
if $\{E_y\}$ would be allocated such that:\footnote{Exercise: show that there
exists an energy allocation $\{E_y\}$ that satisfies both (i) and (ii)
at the same time.}
(i) $\sum_yq(y)E_y=E_0$ and (ii) $\beta_y^*(E_y)=\beta^*$ for all $y$.
Since the $\beta$'s have the meaning of
inverse temperatures, what we have here is {\bf thermal equilibrium}:
Consider a bunch of $|\calY|$ subsystems, each one of $n(y)$ particles and
Hamiltonian $\calE(x,y)$ indexed by $y$. If all these subsystems are thermally
separated, each one with energy $E_y$, then the total entropy per particle is
$\sum_yq(y)\Sigma_y(E_y)$. The above identity tells us then what happens when
all these systems are brought into thermal contact with one another: The total
energy per particle $E_0$ is split among the different subsystems in a way
that all temperatures become the same -- thermal equilibrium. It follows then
that the dominant instance of the LD event is the one where the contributions
of each $y$, to the partial sum of energies, would correspond to equilibrium.
In the rate--distortion example, this characterizes how much distortion each
source symbol contributes typically.

Now, let us look a bit more closely on the rate--distortion
function:
\begin{equation}
R(D)=-\min_{\beta\ge 0}\left[\beta
D+\sum_{y\in\calY}q(y)\ln\sum_{x\in\calX}p(x)e^{-\beta
d(x,y)}\right].
\end{equation}
As said, the Chernoff parameter $\beta$ has
the meaning of inverse temperature.
The inverse temperature $\beta$ required to `tune' the expected
distortion (internal energy) to $D$, is the solution to the equation
\begin{equation}
D=-\frac{\partial}{\partial \beta}\sum_y q(y)\ln \sum_x p(x)e^{-\beta d(x,y)}
\end{equation}
or equivalently,
\begin{equation}
D=\sum_y q(y)\cdot \frac{\sum_xp(x)d(x,y)e^{-\beta d(x,y)}}{\sum_x p(x)\cdot e^{-\beta d(x,y)}}.
\end{equation}
The Legendre transform relation between
the log--partition function and $R(D)$ induces a one--to--one mapping between
$D$ and $\beta$
which is defined by the above equation. To emphasize this dependency, we
henceforth denote the value of $D$, corresponding to a given $\beta$, by
$D_\beta$. This expected distortion is defined w.r.t.\ the probability
distribution:
\begin{equation}
P_\beta(x,y)=q(y)\cdot P_\beta(x|y)=q(y)\cdot\frac{p(x)e^{-\beta d(x,y)}}{\sum_{x'}p(x')e^{-\beta
d(x',y)}}.
\end{equation}
On substituting
$D_\beta$ instead of $D$ in the
expression of $R(D)$, we have
\begin{equation}
-R(D_\beta)=\beta D_\beta+\sum_yq(y)\ln\sum_x
p(x)e^{-\beta d(x,y)}.
\end{equation}
Note that $R(D_\beta)$ can be represented in an integral form as follows:
\begin{eqnarray}
R(D_\beta)&=&-\int_{0}^{\beta}
\mbox{d}\hat{\beta}\cdot\left(D_{\hat{\beta}}+
\hat{\beta}\cdot\frac{\mbox{d}D_{\hat{\beta}}}
{\mbox{d}\hat{\beta}}-D_{\hat{\beta}}\right)\nonumber\\
&=&-\int_{D_{0}}^{D_\beta}\hat{\beta}\cdot\mbox{d}D_{\hat{\beta}},
\end{eqnarray}
where $D_0=\sum_{x,y}p(x)q(y)d(x,y)$ 
is the value of $D$ corresponsing to $\beta=0$, and for which $R_Q(D)=0$,
This is exactly analogous 
to the thermodynamic equation $S=\int\mbox{d}Q/T$ (following
from $1/T=\mbox{d}S/\mbox{d}Q$), that builds up the entropy from the cumulative
heat. Note that the last equation, in its differential form, reads
$\mbox{d}R(D_\beta)=-\beta\mbox{d}D_\beta$, or $\beta=-R'(D_\beta)$, which means that
$\beta$ is indeed the negative
local slope of the rate--distortion curve $R(D)$.
Returning to the integration variable $\hat{\beta}$, we have:
\begin{eqnarray}
R(D_\beta)&=&-\int_{0}^{\beta}\mbox{d}\hat{\beta}\cdot \hat{\beta}
\cdot\frac{\mbox{d}D_{\hat{\beta}}}{\mbox{d}\hat{\beta}}\nonumber\\
&=&\sum_y q(y)\int_{0}^{\beta}\mbox{d}\hat{\beta}\cdot \hat{\beta}\cdot
\mbox{Var}_{\hat{\beta}}\{d(X,y)|Y=y\}\nonumber\\
&=&\int_{0}^{\beta}\mbox{d}\hat{\beta}\cdot \hat{\beta}\cdot
\mbox{mmse}_{\hat{\beta}}\{d(X,Y)|Y\}\nonumber
\end{eqnarray}
where $\mbox{Var}_{\hat{\beta}}\{\cdot\}$ and
$\mbox{mmse}_{\hat{\beta}}\{\cdot|\cdot\}$ are taken w.r.t.
$P_{\hat{\beta}}(x,y)$. We have 
therefore introduced an integral representation for
$R(D)$ based on the MMSE in estimating the distortion variable $d(X,Y)$ based
on $Y$. In those cases where an exact expression for $R(D)$ is hard to obtain,
this opens the door to upper and 
lower bounds on $R(D)$, which are based on upper and lower bounds
on the MMSE, offered by the plethora 
of bounds available in estimation theory.\\
{\it Exercise}: Show that
$D_\beta=D_{0}-\int_{0}^\beta\mbox{d}\hat{\beta}\cdot\mbox{mmse}_{\hat{\beta}}\{d(X,Y)|Y\}$.

Finally, a word about the high--resolution regime.
The partition function of each $y$ is
\begin{equation}
Z_y(\beta)=\sum_xp(x)e^{-\beta d(x,y)},
\end{equation}
or, in the continuous case,
\begin{equation}
Z_y(\beta)=\int_{\reals}\dd x p(x)e^{-\beta d(x,y)}.
\end{equation}
Consider the $L^\theta$ distortion measure $d(x,y)=|x-y|^\theta$, where
$\theta > 0$ and consider a uniform random coding distribution over
the interval $[-A,A]$, supposing that it is the optimal (or close to optimal)
one. Suppose further that we wish to work at a very small distortion level $D$
(high res), which means a large value of $\beta$ (why?). Then,
\begin{eqnarray}
Z_y(\beta)&=&\frac{1}{2A}\int_{-A}^{+A}\dd x e^{-\beta |x-y|^\theta}\nonumber\\
&\approx&\frac{1}{2A}\int_{-\infty}^{+\infty}\dd x e^{-\beta |x-y|^\theta}
~~~(\mbox{large}~\beta) \nonumber\\
&=&\frac{1}{2A}\int_{-\infty}^{+\infty}\dd x e^{-\beta |x|^\theta}
~~~(\mbox{the integral is independent of $y$}) \nonumber
\end{eqnarray}
Thus, returning to the expression of $R(D)$, let us minimize over $\beta$ by
writing the zero--derivative equation, which yields:
\begin{equation}
D=-\frac{\partial}{\partial
\beta}\ln\left[\frac{1}{2A}\int_{-\infty}^{+\infty}\dd x e^{-\beta
|x|^\theta}\right]
\end{equation}
but this is exactly the calculation of the (generalized) equipartition
theorem, which gives $1/(\beta\theta)=kT/\theta$. Now, we already said that
$\beta=-R'(D)$, and so, $1/\beta=-D'(R)$. It follows then that the function
$D(R)$, at this high res.\ limit, obeys a simple differential equation:
\begin{equation}
D(R)=-\frac{D'(R)}{\theta}
\end{equation}
whose solution is
\begin{equation}
D(R)=D_0e^{-\theta R}.
\end{equation}
In the case where $\theta=2$ (squared error distortion),
we get that $D(R)$ is proportional to $e^{-2R}$, which is a well--known result
in high res.\ quantization theory. For the Gaussian source, this is true for
all $R$.
{"config": "arxiv", "file": "1006.1565/chap1.tex"}