text:
\subsection{The Generalized Random Energy Model (GREM) and Hierarchical
Coding}

In the mid--eighties of the previous century, Derrida extended the REM to
the generalized REM (GREM), which has an hierarchical tree sturcture to
accommodate possible correlations between
energy levels of various configurations (and hence is somewhat closer to
reality). It turns out to have direct
relevance to performance analysis of codes with a parallel hierarchical
structure. Hierarchicial structured codes are frequently encountered in many
contexts, e.g., tree codes, multi--stage codes for progressive coding and successive
refinement, codes for the degraded broadcast channel, codes with a binning
structure (like in G--P and W--Z coding and coding for the wiretap channel),
and so on. This part is based on the following papers:

\begin{itemize}
\item
B.~Derrida, ``A generalization of the random energy model which includes
correlations
between energies,'' {\it J.\ de Physique -- Lettres}, vol.\ 46, L--401-107,
May 1985.
\item
B.~Derrida and E.~Gardner, ``Solution of the generalised random
energy model,'' {\it J.\ Phys.\ C: Solid State Phys.}, vol.\ 19,
pp.\ 2253--2274, 1986.
\item
N.~Merhav, ``The generalized random energy model and its
application to the statistical physics of
ensembles of hierarchical codes,''
{\it IEEE Trans.\ Inform.\ Theory},
vol.\ 55, no.\ 3, pp.\ 1250--1268, March 2009.
\end{itemize}

We begin from the physics of the GREM. For simplicity, we limit ourselves to
two stages, but the discussion and the results extend to any fixed, finite
number of stages. The GREM is defined by a few parameters: (i) a number $0 <
R_1 < \ln 2$ and $R_2=\ln 2-R_1$.
(ii) a number $0< a_1<1$ and $a_2=1-a_1$. Given these parameters, we now
partition the set of $2^n$ configurations into $e^{nR_1}$ groups, each having
$e^{nR_2}$ configurations.\footnote{
Later, we will see that in the analogy to hierarchical codes,
$R_1$ and $R_2$ will have the meaning of coding rates
at two stages of a two--stage code.} The easiest way to describe it is with a tree
(see Fig.\ \ref{grem}), each leaf of which represents one spin configuration.
Now, for each branch in this tree, we randomly draw
an independent random variable, which will be referred to as an {\it energy component}:
First, for every branch outgoing from the root, we randomly draw
$\epsilon_i\sim\calN(0,a_1nJ^2/2)$, $1\le i\le e^{nR_1}$. Then, for each
branch $1\le j\le e^{nR_2}$, emanating from node no. $i$, $1\le
i\le e^{nR_1}$, we randomly draw $\epsilon_{i,j}\sim\calN(0,a_2nJ^2/2)$.
Finally, we define the energy associated with each configuration, or
equivalently, each
leaf indexed by $(i,j)$, as $E_{i,j}=\epsilon_i+\epsilon_{i,j}$,
$1\le i\le e^{nR_1}$, $1\le j\le e^{nR_2}$.

\begin{figure}[ht]
\hspace*{4cm}\input{grem.pstex_t}
\caption{\small The GREM with $K=2$ stages.}
\label{grem}
\end{figure}

Obviously, the marginal pdf of each $E_{i,j}$ is $\calN(0,nJ^2/2)$, just like in the
ordinary REM. However, unlike in the ordinary REM, here the configurational
energies $\{E_{i,j}\}$ are correlated: Every two leaves with a common parent
node $i$ have an energy component $\epsilon_i$ in common and
hence their total energies are correlated.

An extension of the
GREM to $K$ stages is parametrized by $\sum_{\ell=1}^K R_\ell =\ln 2$ and
$\sum_{\ell=1}^Ka_\ell =1$, where one first divides the entirety of $2^n$
configurations into $e^{nR_1}$ groups, then each such group is subdivided
into $e^{nR_2}$ subgroups, and so on. For each branch of generation no.\ $\ell$,
an independent energy component is drawn according to $\calN(0,a_\ell
nJ^2/2)$ and the total energy pertaining to each configuration, or a leaf, is
the sum of energy components along the path from the root to that leaf. An
extreme case of the GREM is where $K=n$, which is referred to as the {\it
directed polymer on a tree} or a {\it directed polymer in a random medium}. We
will say a few words about it later, although it has a different asymptotic
regime than the GREM, because in the GREM, $K$ is assumed fixed while $n$ grows
without bound in the thermodynamic limit.

Returning back to the case of $K=2$ stages, the analysis of the GREM is conceptually a
simple extension of that of the REM: First, we ask ourselves what is the
typical number of branches emanating from the root whose first--generation
energy component,
$\epsilon_i$, is about $\epsilon$? The answer is very similar to that of the
REM: Since we have $e^{nR_1}$ independent trials of an experiment for which
the probability of a single success is exponentially
$e^{-\epsilon^2/(nJ^2a_1)}$, then for a typical realization:
\begin{equation}
\Omega_1(\epsilon)\approx\left\{\begin{array}{ll}
0 & |\epsilon| >nJ\sqrt{a_1R_1}\\
\exp\left\{n\left[R_1-\frac{1}{a_1}\left(\frac{\epsilon}{nJ}\right)^2\right]\right\}
& |\epsilon| <nJ\sqrt{a_1R_1}\end{array}\right.
\end{equation}
Next, we ask ourselves what is the typical
number $\Omega_2(E)$ of configurations with total energy about $E$? Obviously,
each such configuration should have a first--generation energy component
$\epsilon$ and second--generation energy component $E-\epsilon$, for some
$\epsilon$. Thus,
\begin{equation}
\Omega_2(\epsilon)\approx
\int_{-nJ\sqrt{a_1R_1}}^{+nJ\sqrt{a_1R_1}} \dd\epsilon \Omega_1(\epsilon)\cdot
\exp\left\{n\left[R_2-\frac{1}{a_2}\left(\frac{E-\epsilon}{nJ}\right)^2\right]\right\}.
\end{equation}
It is important to understand here the following point: Here, we {\it no
longer} zero--out the factor
\begin{equation}
\exp\left\{n\left[R_2-\frac{1}{a_2}\left(\frac{E-\epsilon}{nJ}\right)^2\right]\right\}
\end{equation}
when the expression in the square brackets at the exponent becomes negative,
as we did in the first stage and in the REM. The reason is simple:
Given $\epsilon$, we are conducting $\Omega_1(\epsilon)\cdot e^{nR_1}$
indepenent trials of an experiment whose success rate is
\begin{equation}
\exp\left\{-\frac{n}{a_2}\left(\frac{E-\epsilon}{nJ}\right)^2\right\}.
\end{equation}
Thus, whatever counts is whether the {\it entire} integrand has a positive
exponent or not.

Consider next the entropy. The entropy behaves as follows:
\begin{equation}
\Sigma(E)=\lim_{n\to\infty}\frac{\ln
\Omega_2(E)}{n}=\left\{\begin{array}{ll}
\Sigma_0(E) & \Sigma_0(E)\ge 0\\
-\infty & \Sigma_0(E)< 0\end{array}\right.
\end{equation}
where $\Sigma_0(E)$ is the exponential rate of the above integral, which after
applying the Laplace method, is shown to be:
\begin{equation}
\Sigma_0(E)=\max_{|\epsilon|\le +nJ\sqrt{a_1R_1}}\left[
R_1-\frac{1}{a_1}\left(\frac{\epsilon}{nJ}\right)^2+R_2-
\frac{1}{a_2}\left(\frac{E-\epsilon}{nJ}\right)^2\right].
\end{equation}
How does the function $\Sigma(E)$ behave like?

It turns out that to answer
this question, we will have to distinguish between two cases: (i) $R_1/a_1 <
R_2/a_2$ and (ii) $R_1/a_1\ge R_2/a_2$.\footnote{Accordingly, in coding, this
will mean a distinction between two cases of the relative coding rates at the
two stages.} First, observe that $\Sigma_0(E)$ is an even function, i.e., it
depends on $E$ only via $|E|$, and it is monotonoically non--increasing in
$|E|$. Solving the optimization problem pertaining to $\Sigma_0$, we readily
find:
\begin{equation}
\Sigma_0(E)=\left\{\begin{array}{ll}
\ln 2-\left(\frac{E}{nJ}\right)^2 & |E|\le E_1\nonumber\\
R_2-\frac{1}{a_2}\left(\frac{E}{nJ}-\sqrt{a_1R_1}\right)^2 & |E|>
E_1\end{array}\right.
\end{equation}
where $E_1\dfn nJ\sqrt{R_1/a_1}$. This is a phase transition due to the fact
that the maximizing $\epsilon$ becomes an edgepoint of its allowed interval.
Imagine now that we gradually increase $|E|$ from zero upward. Now the
question is what is encountered first: The energy level $\hat{E}$,
where $\Sigma(E)$ jumps to $-\infty$, or $E_1$ where this phase transition
happens? In other words, is $\hat{E}< E_1$ or $\hat{E}> E_1$? In the former
case, the phase transition at $E_1$ will not be apparent because $\Sigma(E)$
jumps to $-\infty$ before, and that's it. In this case, according to the
first line of $\Sigma_0(E)$, $\ln 2-(E/nJ)^2$ vanishes at $\hat{E}=nJ\sqrt{\ln
2}$ and we get:
\begin{equation}
\Sigma(E)=\left\{\begin{array}{ll}
\ln 2-\left(\frac{E}{nJ}\right)^2 & |E|\le \hat{E}\\
-\infty & |E|> \hat{E}\end{array}\right.
\end{equation}
exactly like in the ordinary REM. It follows then that in this case,
$\phi(\beta)$ which is the Legendre transform of $\Sigma(E)$ will also be like
in the ordinary REM, that is:
\begin{equation}
\phi(\beta)=\left\{\begin{array}{ll}
\ln 2 +\frac{\beta^2J^2}{4} & \beta\le\beta_0\dfn \frac{2}{J}\sqrt{\ln 2}\\
\beta J\sqrt{\ln 2} & \beta>\beta_0\end{array}\right.
\end{equation}
As said, the condition for this is:
\begin{equation}
nJ\sqrt{\ln 2}\equiv \hat{E}\le E_1\equiv nJ\sqrt{\frac{R_1}{a_1}}
\end{equation}
or, equivalently,
\begin{equation}
\frac{R_1}{a_1}\ge \ln 2.
\end{equation}
On the other hand, in the opposite case, $\hat{E}> E_1$, the phase transition
at $E_1$ is apparent, and so, there are now {\it two} phase
transtions:
\begin{equation}
\Sigma(E)=\left\{\begin{array}{ll}
\ln 2-\left(\frac{E}{nJ}\right)^2 & |E|\le E_1\\
R_2-\frac{1}{a_2}\left(\frac{E}{nJ}-\sqrt{a_1R_1}\right)^2 & E_1< |E|\le
\hat{E}\\
-\infty & |E| > \hat{E}\end{array}\right.
\end{equation}
and accordingly (exercise: please show this):
\begin{equation}
\phi(\beta)=\left\{\begin{array}{ll}
\ln 2 +\frac{\beta^2J^2}{4} & \beta\le\beta_1\dfn
\frac{2}{J}\sqrt{\frac{R_1}{a_1}}\\
\beta J\sqrt{a_1R_1} + R_2+\frac{a_2\beta^2J^2}{4} & \beta_1\le
\beta<\beta_2\dfn \frac{2}{J}\sqrt{\frac{R_2}{a_2}}\\
\beta J(\sqrt{a_1R_1}+\sqrt{a_2R_2}) & \beta \ge \beta_2\end{array}\right.
\end{equation}
The first line is a purely paramagnetic phase. In the second line, the
first--generation
branches are glassy (there is a subexponential number of dominant
ones) but the second--generation is still paramagnetic. In the third line,
both generations are glassy, i.e., a subexponential number of
dominant first--level branches, each followed by
a subexponential number of second--level ones, thus a total of a
subexponential number of dominant configurations overall.

Now, there is a small technical question: what is it that guarantees that
$\beta_1 <\beta_2$ whenever $R_1/a_1 < \ln 2$? We now argue that these two
inequalities are, in fact, equivalent. In a paper by Cover and Ordentlich
(IT Transactions, March 1996), the following inequality is proved for
two positive vectors $(a_1,\ldots,a_n)$ and
$(b_1,\ldots,b_n)$:
\begin{equation}
\min_i\frac{a_i}{b_i}\le \frac{\sum_{i=1}^n a_i}{\sum_{i=1}^n b_i}
\le \max_i\frac{a_i}{b_i}.
\end{equation}
Thus,
\begin{equation}
\min_{i\in\{1,2\}}\frac{R_i}{a_i}\le \frac{R_1+R_2}{a_1+a_2}\le
\max_{i\in\{1,2\}}\frac{R_i}{a_i},
\end{equation}
but in the middle expression the numerator is $R_1+R_2=\ln 2$ and
the denominator is $a_1+a_2=1$, thus it is exactly $\ln 2$. In other words,
$\ln 2$ is always in between $R_1/a_1$ and $R_2/a_2$. So $R_1/a_1 < \ln 2$ iff
$R_1/a_1 < R_2/a_2$, which is the case where $\beta_1<\beta_2$.
To summarize our findings thus far, we have shown that:\\
{\it Case A}: $R_1/a_1 < R_2/a_2$ -- two phase transitions:
\begin{equation}
\phi(\beta)=\left\{\begin{array}{ll}
\ln 2 +\frac{\beta^2J^2}{4} & \beta\le\beta_1\\
\beta J\sqrt{a_1R_1} + R_2+\frac{a_2\beta^2J^2}{4} & \beta_1\le
\beta<\beta_2\\
\beta J(\sqrt{a_1R_1}+\sqrt{a_2R_2}) & \beta \ge \beta_2\end{array}\right.
\end{equation}
{\it Case B}: $R_1/a_1 \ge R_2/a_2$ -- one phase transition, like in the REM:
\begin{equation}
\phi(\beta)=\left\{\begin{array}{ll}
\ln 2 +\frac{\beta^2J^2}{4} & \beta\le\beta_0\\
\beta J\sqrt{\ln 2} & \beta>\beta_0\end{array}\right.
\end{equation}

We now move on to our coding problem, this time it is about source coding
with a fidelity criterion. For simplicity, we will assume a binary symmetric
source (BSS) and the Hamming distortion. Consider the following hierarchical
structure of a code: Given a block length $n$, we break it into two segments
of lengths $n_1$ and $n_2=n-n_1$. For the first segment, we randomly select
(by fair coin tossing) a codebook $\hat{\calC}=\{\hat{\bx}_i,~1\le i\le
e^{n_1R_1}\}$. For the second segment, we do the following: For each $1\le
i\le e^{n_1R_1}$, we randomly select (again, by fair coin tossing) a codebook
$\tilde{\calC}_i=\{\tilde{\bx}_{i,j},~1\le j\le e^{n_2R_2}\}$.
Now, given a source vector $\bx\in\{0,1\}^n$, segmentized as $(\bx',\bx'')$,
the encoder seeks a pair $(i,j)$, $~1\le i\le e^{n_1R_1}$, $1\le j\le
e^{n_2R_2}$, such that $d(\bx',\hat{\bx}_i)+d(\bx'',\tilde{\bx}_{i,j})$ is
minimum, and then transmits $i$ using $n_1R_1$ nats and $j$ -- using
$n_2R_2$ nats, thus a total of $(n_1R_1+n_2R_2)$ nats, which means an
average rate of $R=\lambda R_1+(1-\lambda)R_2$ nats per symbol, where
$\lambda=n_1/n$. Now, there are a few questions that naturally arise:
\begin{itemize}
\item {\it What is the motivation for codes of this structure?}
The decoder has a reduced delay. It can decode the first $n_1$ symbols after
having received the first $n_1R_1$ nats, and does not have to wait until
the entire transmission of length $(n_1R_1+n_2R_2)$ has been received.
Extending this idea to $K$ even segments of length $n/K$, the decoding delay
is reduced from $n$ to $n/K$. In the limit of $K=n$, in which case it is a
tree code, the decoder is actually delayless.
\item {\it What is the relation to the GREM?} The hierarchical structure of
the code is that of a tree, exactly like the GREM. The role of the energy
components at each branch is now played by the segmental
distortions $d(\bx',\hat{\bx}_i)$ and $d(\bx'',\tilde{\bx}_{i,j})$.
The parameters $R_1$ and $R_2$ here are similar to those of the GREM.
\item {\it Given an overall rate $R$, suppose
we have the freedom to choose $\lambda$, $R_1$ and $R_2$, such that
$R=\lambda R_1+(1-\lambda)R_2$, are some choice better than others in
some sense?} This is exactly what we are going to check out..
\end{itemize}

As for the performance criterion, here,
we choose to examine performance in terms of the characteristic
function of
the overall distortion, $\bE[\exp\{-s\cdot\mbox{distortion}\}]$.
This is, of course, a much more informative figure of merit than
the average distortion, because in principle, it gives information on the
{\it entire probability
distribution} of the distortion. In particular, it generates all the moments of
the distortion
by taking derivatives at $s=0$, and it is useful in deriving Chernoff bounds on
probabilities of
large deviations events concerning the distortion.
More formally, we make the following definitions:
Given a code $\calC$ (any block code, not necessarily of the class we defined),
and a source vector $\bx$, we define
\begin{equation}
\Delta(\bx)=\min_{\hbx\in\calC} d(\bx,\hbx),
\end{equation}
and we will be interested in the exponential rate of
\begin{equation}
\Psi(s)\dfn\bE\{\exp[-s\Delta(\bX)]\}.
\end{equation}
This quantity can be easily related to the ``partition function'':
\begin{equation}
Z(\beta|\bx)\dfn\sum_{\hbx\in\calC} e^{-\beta d(\bx,\hbx)}.
\end{equation}
In particular,
\begin{equation}
\bE\{\exp[-s\Delta(\bX)]\}=\lim_{\theta\to
\infty}\bE\left\{[Z(s\cdot\theta|\bX)]^{1/\theta}\right\}.
\end{equation}
Thus, to analyze the characteristic function of the distortion,
we have to assess (noninteger) moments of the partition function.

Let's first see
what happens with ordinary random block codes, without any structure.
This calculation is very similar the one we did before in the context
of channel coding:
\begin{eqnarray}
\bE\left\{[Z(s\cdot\theta|\bX)]^{1/\theta}\right\}&=&
\bE\left\{\left[\sum_{\hbx\in\calC} e^{-s\theta
d(\bx,\hbx)}\right]^{1/\theta}\right\}\nonumber\\
&=&\bE\left\{\left[\sum_{d=0}^n\Omega(d)e^{-s\theta
d}\right]^{1/\theta}\right\}\nonumber\\
&\exe&\sum_{d=0}^n\bE\left\{\left[\Omega(d)\right]^{1/\theta}\right\}\cdot e^{-s
d}\nonumber
\end{eqnarray}
where, as we have already shown in the past:
\begin{equation}
\bE\left\{\left[\Omega(d)\right]^{1/\theta}\right\}\exe\left\{\begin{array}{ll}
e^{n[R+h_2(\delta)-\ln 2]} & \delta\le\delta_{GV}(R)~\mbox{or}~
\delta\ge 1-\delta_{GV}(R)\\
e^{n[R+h_2(\delta)-\ln 2]/\theta} & \delta_{GV}(R)\le \delta\le
1-\delta_{GV}(R)\end{array}\right.
\end{equation}
Note that $\delta_{GV}(R)$ is exactly the distortion--rate function of the BSS
w.r.t.\ the Hamming distortion.
By plugging the expression of
$\bE\{[\Omega(d)]^{1/\theta}\}$ back into that of
$\bE\{[Z(s\cdot\theta|\bX)]^{1/\theta}\}$ and carrying out the
maximization pertaining to the dominant contribution, we eventually (exercise:
please show that) obtain:
\begin{equation}
\Psi(s)\exe e^{-nu(s,R)}
\end{equation}
where
\begin{eqnarray}
u(s,R)&=&\ln
2-R-\max_{\delta\le\delta_{GV}(R)}[h_2(\delta)-s\delta]\nonumber\\
&=&\left\{\begin{array}{ll}
s\delta_{GV}(R) & s\le s_R\\
v(s,R) & s > s_R\end{array}\right.
\end{eqnarray}
with
\begin{equation}
s_R\dfn \ln\left[\frac{1-\delta_{GV}(R)}{\delta_{GV}(R)}\right]
\end{equation}
and
\begin{equation}
v(s,R)\dfn\ln 2-R+s-\ln(1+e^s).
\end{equation}
The function $u(s,R)$ is depicted qualitatively in Fig.\ \ref{usrn}.
\begin{figure}[ht]
\hspace*{4cm}\input{usrn.pstex_t}
\caption{\small Qualitative graph of the function $u(s,R)$ as a function of
$s$ for fixed $R$.}
\label{usrn}
\end{figure}

Let's now move on to the hierarchical codes. The analogy with the GREM is
fairly clear. Given $\bx$, there are about $\Omega_1(\delta_1)\exe
e^{n_1[R_1+h_2(\delta_1)-\ln 2]}$ first--segment codewords $\{\hat{\bx}_i\}$
in $\hat{\calC}$ at distance $n_1\delta_1$ from the first segment $\bx'$ of
$\bx$, provided that $R_1+h_2(\delta_1)-\ln 2 >0$ and $\Omega_1(\delta_1)=0$
otherwise. For each such first--segment codeword, there are about
$e^{n_2[R_2+h_2(\delta_2)-\ln 2]}$ second--segment codewords
$\{\tilde{\bx}_{i,j}\}$ at distance $n_2\delta_2$ from the second segment
$\bx''$ of $\bx$. Therefore, for $\delta=\lambda\delta_1+(1-\lambda)\delta_2$,
\begin{eqnarray}
\Omega_2(\delta)&=&\sum_{\delta_1=\delta_{GV}(R_1)}^{1-\delta_{GV}(R_1)}
e^{n_1[R_1+h_2(\delta_1)-\ln 2]}\cdot
e^{n_2[R_2+h_2((\delta-\lambda\delta_1)/(1-\lambda))-\ln
2]}\nonumber\\
&\exe&\exp\left\{n\cdot\max_{\delta_1\in[\delta_{GV}(R_1),1-\delta_{GV}(R_1)]}
\left[R+\lambda
h_2(\delta_1)+(1-\lambda)h_2\left(\frac{\delta-\lambda\delta_1}{1-\lambda}\right)\right]\right\}\nonumber
\end{eqnarray}
In analogy to the analysis of the GREM, here too, there is a distinction between
two cases: $R_1\ge R\ge R_2$ and $R_1 < R < R_2$.
In the first case, the behavior is just like in the REM:
\begin{equation}
\Sigma(\delta)=\left\{\begin{array}{ll}
R+h_2(\delta)-\ln 2 & \delta\in[\delta_{GV}(R),1-\delta_{GV}(R)]\\
-\infty & \mbox{elsewhere}\end{array}\right.
\end{equation}
and then, of course, $\phi(\beta)=-u(\beta,R)$ behaves exactly like that of
a general random code, in spite of the hierarchical structure.
In the other case, we have two phase transitions:
\begin{equation}
\phi(\beta,R)=\left\{\begin{array}{ll}
-v(\beta,R) & \beta < \beta(R_1)\\
-\lambda\beta\delta_{GV}(R_1)-(1-\lambda)v(\beta,R_2) & \beta(R_1) < \beta <
\beta(R_2)\\
-\beta[\lambda\delta_{GV}(R_1)+(1-\lambda)\delta_{GV}(R_2)] & \beta >
\beta(R_2)\end{array}\right.
\end{equation}
The last line is the purely glassy phase and this is the relevant phase because of the
limit $\theta\to 0$ that we take in order to calculate $\Psi(s)$.
Note that at this phase the slope is
$\lambda\delta_{GV}(R_1)+(1-\lambda)\delta_{GV}(R_2)$
which means that code behaves as if the two segments were coded {\it
separately}, which is worse that $\delta_{GV}(R)$ due to convexity arguments.
Let's see this more concretely on the characteristic function:
This time, it will prove convenient to define $\Omega(d_1,d_2)$ as an
enumerator of codewords whose distance is $d_1$ at the first segment
and $d_2$ -- on the second one.
Now,
\begin{equation}
\bE\left\{Z^{1/\theta}(s\cdot\theta)\right\}=\bE\left\{\left[\sum_{d_1=0}^n\sum_{d_2=0}^n
\Omega(d_1,d_2)\cdot e^{-s\theta(d_1+d_2)}\right]^{1/\theta}\right\}\exe
\sum_{d_1=0}^n\sum_{d_2=0}^n\bE\left\{\Omega^{1/\theta}(d_1,d_2)\right\}\cdot
e^{-s(d_1+d_2)}.
\end{equation}
Here, we should distinguish between four types of terms depending on whether
or not $\delta_1\in[\delta_{GV}(R_1),1-\delta_{GV}(R_1)]$ and whether or not
$\delta_2\in[\delta_{GV}(R_2),1-\delta_{GV}(R_2)]$. In each one of these
combinations, the behavior is different (the details are in the paper).
The final results are as follows:
\begin{itemize}
\item For $R_1 < R_2$,
\begin{equation}
\lim_{n\to\infty}\left[-\frac{1}{n}\ln\bE \exp\{-s\Delta(\bX)\}\right]=
\lambda u(s,R_1)+(1-\lambda)u(s,R_2)
\end{equation}
which means the behavior of two independent, decoupled codes for the
two segments, which is bad, of course.
\item For $R_1 \ge R_2$,
\begin{equation}
\lim_{n\to\infty}\left[-\frac{1}{n}\ln\bE \exp\{-s\Delta(\bX)\}\right]=
u(s,R)~~~~\forall s\le s_0
\end{equation}
where $s_0$ is some positive constant. This means that the code behaves like
an unstructured code (with delay) for all $s$ up to a certain $s_0$ and the
reduced decoding delay is obtained for free. Note that the domain of small $s$
is relevant for moments of the distortion. For $R_1=R_2$, $s_0$ is unlimited.
\end{itemize}
Thus, the conclusion is that if we must work at different rates, it is better
to use the higher rate first.

Finally, we discuss a related model that we mentioned earlier,
which can be thought of as an extreme case of the GREM with $K=n$.
This is the {\it directed polymer in a
random medium} (DPRM):
Consider a {\it Cayley tree}, namely, a full balanced tree with branching
ratio $d$ and depth $n$ (cf.\ Fig.\ \ref{tree}, where $d=2$ and $n=3$). Let us index
the branches by a pair of integers $(i,j)$, where $1\le i\le n$ describes the
generation (with $i=1$ corresponding to the $d$ branches that emanate from the
root), and $0\le j\le d^i-1$ enumerates the branches of the $i$--th generation, say,
from left to right (again, see Fig.\ \ref{tree}).
For each branch $(i,j)$, $1\le j\le d^i$, $1\le i\le n$,
we randomly draw an independent random variable $\varepsilon_{i,j}$ according
to a fixed probability function $q(\varepsilon)$ (i.e., a probability mass
function in the discrete
case, or probability density function in the continuous case). As explained
earlier, the asymptotic regime here is different from that of the GREM: In the GREM we
had a fixed number of stages $K$ that didn't grow with $n$ and exponentially
many branches emanating from each internal node. Here, we have $K=n$ and a
fixed number $d$ of branches outgoing from each note.

\begin{figure}[ht]
\hspace*{5cm}\input{tree.pstex_t}
\caption{A Cayley tree with branching factor $d=2$ and depth $n=3$.}
\label{tree}
\end{figure}

A {\it walk} $\bw$, from the root of the tree to one of its leaves, is
described
by a finite
sequence $\{(i,j_i)\}_{i=1}^n$, where $0\le j_1\le d-1$ and $dj_i\le
j_{i+1}\le dj_i+d-1$, $i=1,2,\ldots,(n-1)$.\footnote{In fact, for a given $n$,
the
number $j_n$ alone dictates the entire walk.} For a given realization of the
RV's
$\{\varepsilon_{i,j}:~i=1,2,\ldots,n,~j=0,1,\ldots,d^i-1\}$, we define the
Hamiltonian associated with $\bw$ as
$\calE(\bw)=\sum_{i=1}^n\varepsilon_{i,j_i}$,
and then the partition function as:
\begin{equation}
\label{pftree}
Z_n(\beta)=\sum_{\bw} \exp\{-\beta\calE(\bw)\}.
\end{equation}
It turns out that this model is exactly solvable (in many ways) and one can
show (see e.g., E.~Buffet, A.~Patrick, and J.~V.~Pul\'e, ``Directed polymers
on trees: a martingale approach,'' {\it J.\ Phys.\ A: Math.\ Gen.}, vol.\ 26,
pp.\ 1823--1834, 1993) that it admits a glassy phase transition:
\begin{equation}
\phi(\beta)=\lim_{n\to\infty}\frac{\ln Z_n(\beta)}{n}=\left\{\begin{array}{ll}
\phi_0(\beta) & \beta < \beta_c\\
\phi_0(\beta_c) & \beta \ge \beta_c\end{array}\right.~~~~\mbox{almost surely}
\end{equation}
where
\begin{equation}
\phi_0(\beta)\dfn \frac{\ln [d\cdot \bE e^{-\beta\rho(\epsilon)}]}{\beta}
\end{equation}
and $\beta_c$ is the value of $\beta$ that minimizes $\phi_0(\beta)$.

In analogy to the hierachical codes inspired by the GREM, consider now an ensemble
of tree codes for encoding source $n$--tuples,
$\bx=(x_1,\ldots,x_n)$, which is
defined as follows: Given a coding rate $R$ (in nats/source--symbol), which is
assumed to be the natural logarithm of some positive integer
$d$, and given a
probability distribution on the reproduction alphabet,
$Q=\{q(y),~y\in\calY\}$,
let us draw $d=e^R$ independent copies of $Y$ under $Q$, and denote them by
$Y_1,Y_2,\ldots,Y_d$. We shall refer to the randomly chosen set,
$\calC_1=\{Y_{1},Y_{2},\ldots,Y_{d}\}$, as our `codebook' for the first
source symbol, $X_1$. Next, for each $1\le j_1\le d$, we randomly select
another
such codebook under $Q$,
$\calC_{2,j_1}=\{Y_{j_1,1},Y_{j_1,2},\ldots,Y_{j_1,d}\}$, for the second
symbol,
$X_2$. Then, for each $1\le j_1\le d$ and $1\le j_2\le d$, we again draw under
$Q$
yet another codebook
$\calC_{3,j_1,j_2}=\{Y_{j_1,j_2,1},Y_{j_1,j_2,2},\ldots,Y_{j_1,j_2,d}\}$, for
$X_3$, and so on.
In general, for each $t\le n$, we randomly draw $d^{t-1}$ codebooks under
$Q$, which are indexed by $(j_1,j_2,\ldots,j_{t-1})$, $1\le j_k\le d$, $1\le
k\le t-1$.

Once the above described random code selection process is complete, the
resulting
set of codebooks $\{\calC_1,\calC_{t,j_1,\ldots,j_{t-1}},~2\le t\le n,~1\le
j_k\le
d,~1\le k\le t-1\}$
is revealed to both the
encoder and decoder, and the encoding--decoding system works as follows:
\begin{itemize}
\item {\it Encoding:} Given a source $n$--tuple $X^n$, find a vector of
indices $(j_1^*,j_2^*,\ldots,j_n^*)$ that minimizes the overall distortion
$\sum_{t=1}^n \rho(X_t,Y_{j_1,\ldots,j_t})$. Represent each component $j_t^*$
(based on $j_{t-1}^*$)
by $R=\ln d$ nats (that is, $\log_2d$ bits), thus a total of $nR$ nats.
\item {\it Decoding:}
At each time $t$ ($1\le t\le n$), after having decoded
$(j_1^*,\ldots,j_t^*)$, output the reproduction symbol
$Y_{j_1^*,\ldots,j_t^*}$.
\end{itemize}

In order to analyze the rate--distortion performance of this ensemble of
codes, we now make the following assumption:

\vspace{0.15cm}

\noindent
{\it The random coding distribution $Q$ is such that the
distribtion of the RV $\rho(x,Y)$ is the same for all $x\in\calX$.}

It turns out that this assumption is fulfilled
quite often -- it is the case whenever the random
coding distribution together with distortion function exhibit a sufficiently
high degree of symmetry. For example, if $Q$ is the uniform distribution over
$\calY$ and the rows of the distortion matrix $\{\rho(x,y)\}$ are permutations
of each other, which is in turn the case, for example,
when $\calX=\calY$ is a group and $\rho(x,y)=\gamma(x-y)$
is a difference distortion function w.r.t.\ the group difference operation.
Somewhat more generally, this assumption
still holds when the different rows of the
distortion matrix
are formed by permutations of each other subject to the following
rule: $\rho(x,y)$ can be
swapped with $\rho(x,y')$ provided that $q(y')=q(y)$.

For a given $\bx$ and a given realization of the set of codebooks, define
the partition function in analogy to that of the DPRM:
\begin{equation}
Z_n(\beta)=\sum_{\bw} \exp\{-\beta\sum_{t=1}^n\rho(x_t,Y_{j_1,\ldots,j_t})\},
\end{equation}
where the summation extends over all $d^n$ possible walks,
$\bw=(j_1,\ldots,j_n)$,
along the Cayley tree.
Clearly, considering our symmetry assumption,
this falls exactly under the umbrella of the DPRM, with the distortions
$\{\rho(x_t,Y_{j_1,\ldots,j_t})\}$ playing the role of the branch energies
$\{\varepsilon_{i.j}\}$. Therefore, $\frac{1}{n\beta}\ln Z_n(\beta)$ converges
almost surely, as $n$ grows without bound, to $\phi(\beta)$, now defined as
\begin{equation}
\label{physresult1}
\phi(\beta)=\left\{\begin{array}{ll}
\phi_0(\beta) & \beta\le\beta_c\\
\phi_0(\beta_c) & \beta>\beta_c
\end{array}\right.
\end{equation}
where now
\begin{eqnarray}
\phi_0(\beta)&\dfn&\frac{\ln[d\cdot\bE\{e^{-\beta\rho(x,Y)}\}]}{\beta}\nonumber\\
&=&\frac{\ln[e^R\cdot\bE\{e^{-\beta\rho(x,Y)}\}]}{\beta}\nonumber\\
&=&\frac{R+\ln[\bE\{e^{-\beta\rho(x,Y)}\}]}{\beta},\nonumber
\end{eqnarray}
Thus, for every $(x_1,x_2,\ldots)$, the distortion is
given by
\begin{eqnarray}
\limsup_{n\to\infty}\frac{1}{n}\sum_{t=1}^n\rho(x_t,Y_{j_1^*,\ldots,j_t^*})
&\dfn&\limsup_{n\to\infty}\frac{1}{n}\min_{\bw}
\left[\sum_{t=1}^n\rho(x_t,Y_{j_1,\ldots,j_t})\right]\nonumber\\
&=&\limsup_{n\to\infty}\limsup_{\ell\to\infty}\left[-\frac{\ln
Z_n(\beta_\ell)}{n\beta_\ell}\right]\nonumber\\
&\le&\limsup_{\ell\to\infty}\limsup_{n\to\infty}\left[-\frac{\ln
Z_n(\beta_\ell)}{n\beta_\ell}\right]\nonumber\\
&\eqas&-\liminf_{\ell\to\infty}\phi(\beta_\ell)\nonumber\\
&=& -\phi_0(\beta_c)\nonumber\\
&=&\max_{\beta\ge
0}\left[-\frac{\ln[\bE\{e^{-\beta\rho(x,Y)}\}]+R}{\beta}\right]\nonumber\\
&=& D(R)\nonumber,
\end{eqnarray}
where: (i) $\{\beta_\ell\}_{\ell\ge 1}$ is an arbitrary sequence tending to
infinity, (ii) the almost--sure equality in the above mentioned paper,
and (iii)
the justification of the inequality at the third line is left as an exercise.
The last equation is easily obtained by inverting the function $R(D)$ in its
parametric representation that we have seen earlier:
\begin{equation}
R(D)=-\min_{\beta\ge 0}\min_Q\left\{\beta
D+\sum_{x\in\calX}p(x)\ln\left[\sum_{y\in\calY}q(y)e^{-\beta\rho(x,y)}\right]\right\}.
\end{equation}
Thus, the ensemble of tree codes achieves $R(D)$ almost surely.