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: \begin{equation} - \sum p_i \log p_i - \sum q_i \log q_i \end{equation}
Where $p_i = 1 - q_i$ is the probability of the $i$th bit being 1, i.e.: \begin{equation} p_i = \sum_x \mathrm{Pr}(X=x) m(x)_i \end{equation}
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: \begin{equation} \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)} \end{equation}
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.
