# Find a minimum entropy code for a simple gibbs random field.

Just to make precise what I am talking about, I will include the definition of a minimum entropy code. I will then define the precise markov random field I am asking about.

In the rest of this question, if $b$ is a binary string, I will use $b_i$ to refer to the $i$th bit of this string.

Minimum entropy codes were defined by Barlow, Kaushal, and Mitchison in 1989: http://www.mitpressjournals.org/doi/abs/10.1162/neco.1989.1.3.412?journalCode=neco. The idea is quite simple. Given a discrete random variable $X$, a probability mass function $f$ for $X$, and a positive integer $N$, find a one-to-one mapping $m$ from the set of possible outcomes of $X$ to the set of all binary strings of length $N$ (call it $B^N$ where $B$={0,1}), such that the following is minimized: $$- \sum p_i \log p_i - \sum q_i \log q_i$$

Where $p_i = 1 - q_i$ is the probability of the $i$th bit being 1, i.e.: $$p_i = \sum_x \mathrm{Pr}(X=x) m(x)_i$$

Now, on to the Markov random field (MRF). The specific MRF in this question is the Gibbs random field defined by $N$ binary nodes: $(s_1, s_2, \cdots, s_N) \in B^N$, with the nodes arranged circularly and each one inhibiting its immediate neighbors. In more precise terms, the probability of each state is: $$\mathrm{Pr}(s_1, s_2, \cdots, s_N) = \frac{\exp(-\sum_{i=1}^N (s_i s_{i+1} + s_i s_{i-1})/T)}{Z(T)}$$

Where $T$ is a positive real number that is a free variable, and $Z(T)$ is a normalizing factor that is required so that the sum taken over all states is equal to 1 (the partition function). As mentioned, the nodes are connected circularly. That is, in the subscripts, $i+1$ and $i-1$ are assumed to 'wrap around'. In other words, if $i=N$, then $s_{i+1}=s_1$. And if $i=1$, $s_{i-1}=s_N$.

The question is: find a minimum entropy code for the given MRF. This is a question with very important implications for pattern recognition and neural signal processing.

• I'm confused by the many minus signs in the formula for the probability of a state. Their overall effect is that the probability is greatest when all the $s_i$ are 1, which seems unlikely to be what you meant by "inhibiting". Did you perhaps intend to have a minus sign either before the summation or on the individual terms but not both? As long as I'm asking naive questions, do you really intend the $s_i$ to be in $B$, i.e., to be 0 or 1 (as opposed to perhaps being $-1$ or 1)? – Andreas Blass Nov 5 '12 at 16:27
• Thanks for spotting the typo. The minus signs in the sum were by mistake. The definition for $s_i$ is correct; they binary and not in {-1,1}. I double-checked the rest of the post just to make sure to find any other possible typos. – Alin Nov 5 '12 at 16:44