5
$\begingroup$

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}

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2012 at 11:24
  • $\begingroup$ 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. $\endgroup$ Oct 16, 2012 at 12:22
  • $\begingroup$ 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? $\endgroup$
    – R W
    Oct 17, 2012 at 5:35
  • $\begingroup$ @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. $\endgroup$ Oct 17, 2012 at 12:18
  • $\begingroup$ 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? $\endgroup$
    – R W
    Oct 17, 2012 at 12:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.