MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a discrete memoryless channel with input and output alphabets each composed of $n$ symbols $\{x_j\}$ and $\{y_k\}$, respectively, and specified by the matrix $W_{jk} := \mathbb{P}(y_k|x_j)$.

While in general one must resort to numerics and use the Blahut-Arimoto algorithm to compute the capacity $C$ as a function of $W$, we have the following partial result: if $M := W^{-1}$ exists, \begin{equation} H_j := -\sum_k W_{jk} \log W_{jk} \end{equation} are the conditional entropies given $x_j$, \begin{equation} d_j := \sum_i M_{ij} \exp \left ( - \sum_k M_{ik} H_k \right ), \end{equation} and if $d_j > 0$ identically, then (see, e.g. theorem 3.3.3 of Ash) \begin{equation} e^C = \sum_j \exp \left ( - \sum_k M_{jk} H_k \right ), \end{equation} and moreover $e^{-C} d$ is a capacity-achieving distribution.

Meanwhile, we can consider the partition function $Z$ of a well-behaved distribution $p$ defined via \begin{equation} -\log Z(p) := \frac{1}{n} \sum_j \log p_j \end{equation}

I have observed that when taking all but two of the entries of $W$ fixed, and with $p$ given by the capacity-achieving distribution (ignoring any possible degeneracies), that $-\log Z$ (as a function of the free entries of $W$) tends to have a plateau where it is nearly constant and equal to its maximum value. I am not certain, but I think the region of this plateau corresponds roughly to the region $d > 0$ referenced above. Obviously, the shape of this region will be fairly complicated.

My question is: why (and how precisely) is $-\log Z$ approximately constant on a large region of parameter space?

I'm looking for insight, but calculations are welcome. However, I find the algebra to be quite difficult, though I will remark as an aside (probably uselessly) that if we take $W_{jj} = 1 - \sum_{k \ne j} W_{jk}$ as dependent variables, then \begin{equation} \frac{\partial C}{\partial W_{jk}} = \psi^{(jk)} \cdot p_j, \end{equation} where \begin{equation} \psi^{(jk)} := \sum_m \left ( M_{km} - M_{jm} \right ) H_m + \log \frac{W_{jk}}{W_{jj}}, \end{equation} and furthermore that \begin{equation} \frac{\partial p_\ell}{\partial W_{jk}} = -\psi^{(jk)} \cdot p_j p_\ell + (M_{j \ell} - M_{k \ell}) p_j + e^{-C} \psi^{(jk)} \sum_i M_{ij} M_{i \ell} \exp \left (-\sum_a M_{ia} H_a \right ). \end{equation}

We also have that $-\partial \log Z/\partial W_{jk}$ equals \begin{equation} -\psi^{(jk)} \cdot p_j + \frac{1}{n} p_j \sum_\ell \frac{M_{j \ell} - M_{k \ell}}{p_\ell} + \frac{1}{n} e^{-C} \psi^{(jk)} \sum_i M_{ij} \sum_\ell \frac{M_{i \ell}}{p_\ell} \exp \left (-\sum_a M_{ia} H_a \right ). \end{equation}

share|cite|improve this question
BTW, I mean to say that $\nabla_{W'} (-\log Z) \approx 0$, where $W'$ is a small subset of entries of $W$: and I would guess that something like the Sherman-Morrison-Woodbury formula might have something to say about this, since this amounts to looking at low-rank perturbations to $W$. However, and as I said above, the algebra is formidable. It's not clear to me that doing error estimates this way might be fruitful even if I could carry them through. – Steve Huntsman Oct 15 '12 at 11:24
I also want to note that it's not clear to me how show a correspondence between $(MH)_j$ and a sort of $\beta E_j$ term with $E_j$ an energy function and $\beta$ an inverse temperature. In some sense this is the entire problem. – Steve Huntsman Oct 16 '12 at 12:22
What exactly do you mean by "all but two of the entries of $W$ fixed"? Since $W$ is a stochastic matrix they have to be from the same row and have a constant sum, so that the function you are taking about is defined on an interval. Right? – R W Oct 17 '12 at 5:35
@R W: I am taking the $W_{jj}$ to be dependent variables, so varying any single $W_{jk}$ implies a corresponding adjustment to $W_{jj}$. In my numerical studies I am varying two independent entries: $W_{jk}$ and $W_{j'k'}$, usually with $j \ne j'$. In general, it would be nice to be able to speak to the situation where more or all $W_{jk}$ with $k \ne j$ are being varied, but for obvious reasons this is difficult to examine numerically. – Steve Huntsman Oct 17 '12 at 12:18
I see what you mean now. In your first comment you also conjecture that something similar should hold for a bigger number of parameters. However, do your numerical experiments refer to the case of 2 parameters only? – R W Oct 17 '12 at 12:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.