Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Bounds on the Entropy of a Binary System with Known Mean and Pairwise Constraints

  • Author(s): Albanna, Badr Faisal
  • Advisor(s): DeWeese, Michael R
  • et al.

Maximum entropy models are increasingly being used to describe the collective activity of neural populations with measured mean neural activities and pairwise correlations, but the full space of probability distributions consistent with these constraints has not been explored.

In this dissertation, I provide lower and upper bounds on the entropy for both the minimum and maximum entropy distributions over binary units with any fixed set of mean values and pairwise correlations, and we construct distributions for several relevant cases.

Surprisingly, the minimum entropy solution has entropy scaling logarithmically with system size, unlike the possible linear behavior of the maximum entropy solution, for any set of first- and second-order statistics consistent with arbitrarily large systems.

I find the following bounds on the maximum and minimum entropies for fixed values of $\{\mu_i\}$ and $\{\nu_{ij}\}$.

For the \emph{maximum entropy}:


x N - \mathcal{O}(\log_2{N}) \leq S_2 \leq N.


In the case of uniform constraints, $x = 4(\mu - \nu)$ if $\nu \geq \nicefrac{1}{2}\,\mu$ and $\nu \geq \nicefrac{3}{2}\, \mu - \nicefrac{1}{2}$; otherwise $x = \frac{\nu - \mu^2}{\nicefrac{1}{4} - (\mu - \nu)}$.

For the \emph{minimum entropy}:


\log_2 \left( \frac{N}{1 + (N-1) \bar\alpha } \right) \leq \tilde{S}_2 \leq \log_2 \left( 1+\frac{N(N+1)}{2} \right),


where $\bar\alpha$ is the average of $\alpha_{ij} = (4\nu_{ij} - 2\mu_i - 2\mu_j + 1)^2$ over all $i,j \in \{1,\dots,N\}$, $i \neq j$.

Perhaps surprisingly, the scaling behavior of the minimum entropy does not depend on the details of the sets of constraint values --- for large systems the entropy floor does not contain tall peaks or deep valleys comparable to the scale of the maximum entropy.

I also demonstrate that some sets of low-order statistics can only be realized by small systems.

My results show how only small amounts of randomness are needed to mimic low-order statistical properties of highly entropic distributions, and I discuss some applications for engineered and biological information transmission systems.

Main Content
Current View