# Maximizing entropy under constraints

This question is about an extension of the variational principle in thermodynamical formalism when one adds linear constraints to the measures.

Consider the one-sided shift $\sigma:\mathcal{A}^\mathbb{N}$ where $\mathcal{A}$ is a finite alphabet ($\{0,1\}$ say). Consider a test function $\varphi:\mathcal{A}^\mathbb{N}\to \mathbb{R}$, of Hölder regularity with respect to a usual metric, $d(x,y) = 2^{-\min\{i,x_i\neq y_i\}}$ say, and assume that $0$ is in the interior of the interval of values taken by $\int\varphi \,d\mu$ when $\mu$ runs over shift-invariant probability measures.

Consider the following question:

How to find a shift invariant probability measure $\mu$ such that $\int\varphi \,d\mu=0$ and which maximizes the metric entropy $h(\sigma,\mu)$ under this constraint?

Together with collaborators we developed tools about the thermodynamical formalism which allow us to answer such a question. What I would like to know is whether this should be considered a mere illustration of our methods or a true application.

My question: Is the answer to the above question known? If yes, could you give a reference? How difficult is it? If no, do you know a reference where this kind of question is explicitly asked?

In fact, we can deal with multiple constraints of the same form, and optimize pressure $h(\sigma,\mu) + \int A \,d\mu$ of yet another function $A$, and we can deal with more general dynamical systems (we mostly need a spectral gap for the Ruelle operator).

Just to examplify the above, let me give the answer in two cases, using $\mathcal{A}=\{0,1\}$ in denoting by $w*$ the cylinder defined by a finite word $w$.

Example 1: among shift-invariant measures $\mu$ such that $\mu(0*) = .9$, the Bernoulli measure of parameter .9 (i.e. the law of the word $\alpha_1\alpha_2\dots$ where the $\alpha_j$ are i.i.d. random variables taking the value $0$ with probability .9) maximizes entropy.

Example 2: Among shift-invariant measures $\mu$ such that $\mu(01*) = 2\mu(11*)$, the Markov measure associated to the transition probabilities \begin{align*} \mathbb{P}(0\to 0) &= 1-a & \mathbb{P}(0\to1) &= a \\ \mathbb{P}(1\to0) &= \frac23 & \mathbb{P}(1\to1) &= \frac13 \end{align*} where $a$ is the only real solution to $$(1-a)^5=\frac{4}{27} a^2 \qquad (a\simeq 0.487803)$$ maximizes entropy.

The first example feels quite obvious (but I do not know if there is a really easy way to prove it) while the second surprised me quite a bot (hoping that I did not messed up the computations).

• I think the first is obvious using the relationship $H(\mathcal P^n)\le nH(\mathcal P)$ with equality iff $T^{-i}\mathcal P$ are independent for $i=0,\ldots,n-1$. Some very closely related work is due to Christian Wolf and Tamara Kucherenko. – Anthony Quas May 25 '15 at 19:52
• @AnthonyQuas: the pointer to Christian Wolf and Tamara Kucherenko is so good that it could be made an answer; it seems after a quick look that their work does contain this application of our work. Thanks! – Benoît Kloeckner May 25 '15 at 20:14

The question you ask has been extensively studied in multifractal analysis under the name "conditional variational principle". A quick search for that phrase on MathSciNet turns up an article by Barreira and Saussol in Trans. AMS from 2001. The article by Barreira, Saussol, and Schmeling mentioned in John B's answer also gives a pretty complete account. As Anthony Quas mentions, Kucherenko and Wolf consider similar questions; indeed, there is actually quite a large literature on multifractal analysis (or multifractal formalism) which addresses various questions related to this one.

It may be worth noting that even in multifractal papers which do not explicitly formulate a result on maximizing entropy subject to a constraint on $\mu$, such a result is often still implicit. Broadly speaking the story is like this: in multifractal analysis one considers a local asymptotic quantity like the limit of Birkhoff averages $\lim \frac 1n S_n \phi(x)$, puts $K_\alpha$ equal to the set where this quantity exists and is equal to $\alpha$, and then tries to find $h_{\mathrm{top}}(K_\alpha)$ as a function of $\alpha$, where $h_{\mathrm{top}}$ is topological entropy is the sense of Bowen. Often topological entropy is replaced with Hausdorff dimension and the Birkhoff limit is replaced with a pointwise dimension, a local entropy, or a Lyapunov exponent. In any case one often finds that $\alpha \mapsto h_{\mathrm{top}}(K_\alpha)$ is the Legendre transform of the pressure function $t\mapsto P(t\phi)$, and in particular is an analytic function of $\alpha$ in some standard situations where the topological pressure has nice analytic properties.

There are basically two approaches to proving that the dependence on $\alpha$ is the Legendre transform of pressure. One approach is to assume some version of the specification property (or some similar uniform mixing condition, such as being a mixing SFT) and then use some orbit-gluing techniques to estimate the size of the sets $K_\alpha$ almost by hand. Another approach is to use thermodynamic results to produce unique equilibrium states $\mu_t$ for $t\phi$ and then argue that each $\mu_t$ is the measure of maximal entropy for some $K_\alpha$ where $\alpha$ depends on $t$, and in particular is the measure you described in your original question.

It's entirely possible that the procedure I just described is well known to you; my point is just that such procedures were done even before the 2001 paper of Barreira and Saussol, so this is quite a well-established idea. I believe I've seen the conditional variational principle discussed explicitly in papers by Gelfert and Rams, also by Johannson, Jordan, Öberg, and Pollicott. At some point I wrote a survey of multifractal analysis that discusses this issue in Section 2.3; it also appears in Proposition 2.9 and Theorem C of another paper of mine.

Perhaps I've gotten long-winded and just told you some things you already knew. To more specifically address your main questions... "Is the answer to the above question known?" Yes, it is pretty well-known and studied, the keywords being "multifractal formalism" and "conditional variational principle". "If yes, could you give a reference?" The references given by others to Kucherenko-Wolf and Barreira-Saussol-Schmeling will do -- my preference would be Barreira-Saussol 2001 since it is earlier -- but I would point out that the techniques used are pretty standard in multifractal work going even further back (Pesin-Weiss 1997, probably earlier as well). "How difficult is it?" In the generality you formulated I do not believe it is particularly dialfficult; one can consider the unique equilibrium states $\mu_t$ for $t\phi$ as $t$ ranges over $\mathbb{R}$ and then make some general arguments (if this is what you do then I apologize for telling you things you know). The same technique works more generally as long as you can say enough about the uniqueness of the equilibrium states, but this can be a challenging question in general.

Edit: As pointed out in the comments the references I gave above do not really answer the question directly. For the sake of notation let me write $K_\alpha$ for the level set above, and $T(\alpha) = \sup \{ h(\mu) \mid \int\phi\,d\mu=\alpha\}$. Then many of the main results in the references are of the form "$h(K_\alpha) = T(\alpha)$ under certain conditions". Which is not quite the same as describing how to compute the measure maximizing $T(\alpha)$, which is what you asked. The result in my Nonlinearity paper that I linked to describes a proof that $T(\alpha)$ is the Legendre transform of the pressure function $t\mapsto P(t\phi)$, which comes a little closer to the mark; the proof there contains a proof that there is some equilibrium state $\mu$ for some potential that achieves the maximum in $T(\alpha)$. But the way that it is written is opaque enough that I can't really claim it answers your question.

So let me extract the relevant bits in the case when $\phi$ is Hölder. Then the function $S(t) := P(t\phi)$ is differentiable in $t$, and $S'(t) = \int\phi\,d\mu_t$, where $\mu_t$ is the unique equilibrium state for $t\phi$. Using convexity properties of $S$ one can argue that $S'(t)$ takes all values in the interior of $\{ \int\phi\,d\nu \mid \nu \text{ is invariant}\}$. In particular, there is $t$ such that $S'(t)=\alpha$, and then one can show that $h(\mu_t) = T(\alpha)$, so that $\mu_t$ is the measure you want. As long as your system is such that you can write down $S'(t)$ explicitly, solve for $t$, and then describe $\mu_t$, then this gives you a pretty concrete algorithm for finding the conditionally maximizing measure.

My understanding is that the argument in the previous paragraph is implicit in a lot of work on multifractal formalism. But as illustrated by my earlier attempt at giving references, it's not always stated in a form that is readily useful for answering your specific question.

• Thanks for your detailed answer; I must say that a quick look at the references you mention did not enable me to find what I looked for: I found interpretation in terms of multifractal spectra of such maximization problems, but not the description of how a maximizing (Gibbs) measure can be found. But you warned about the fact that these are implicit, so I guess I just need to take a more careful look. – Benoît Kloeckner May 26 '15 at 18:29
• Gibbs measures do not always exist. Here, Vaughn Climenhaga explains that you just need to consider the (unique in good cases) equilibrium state of certain potentials. If the question is how to find such an equilibrium state, look at the LNM book of Bowen "Equilibrium states..." or more recently the book of Walters on ergodic theory (the last edition has one or two chapters on equilibrium states). If you want a reference with the difference beween Gibbs and equilibrium states look at the book of Gerhard Keller. – Barbara Schapira May 26 '15 at 19:55
• @BenoîtKloeckner: The more I look through the references I mentioned (instead of just relying on my memory) the more I agree with you; the exact question you asked is not really addressed explicitly. I still believe that the techniques are there lying in the background, but it's not clear they're well-explained anywhere. I'll edit my answer to say a little more. – Vaughn Climenhaga May 27 '15 at 15:07
• @BarbaraSchapira: note that I chose a context (shift with Hölder potentials) where the existence of Gibbs measures and coincidence with equilibrium states is not an issue (unless we mean different things by Gibbs measure, which might be the case). Note also that I am asking about a constrained case, i.e. we restrict to measure satisfying a certain equality $\int \varphi \,d\mu=0$; I do not see how this is addressed by the usual equilibrium states. – Benoît Kloeckner May 27 '15 at 15:32
• @VaughnClimenhaga: thanks for the clarification; in fact one of the nice point is that we are able to consider several constraints $\int \varphi_k \,d\mu=0$, which complicate things a bit as one needs more than the intermediate value theorem to get surjectivity. At the moment, it seems that the reference given by Anthony Quas is closest to what I asked, but the Barreira-Saussol thread will have to be mentioned. – Benoît Kloeckner May 27 '15 at 15:36

This type of question was considered by Barreira, Saussol and Schmeling in 2002. See their paper in http://www.sciencedirect.com/science/article/pii/S0021782401012284. Details and applications to number theory are included in the book "Dimension and Recurrence in Hyperbolic Dynamics", by Barreira, see chapters 9 and 10. In particular, Theorem B in the work of Kucherenko and Wolf is a particular case of results proved there.

PS: Indeed, chapter 9 details the earlier work of Barreira and Saussol in TAMS. The techniques most certainly do not depend on former work of Pesin and Weiss.

This is a question that we have been working on since a long time in the community of computational neuroscience. Arise naturally when dealing with spike trains and parametrical potentials with spatio-temporal constraints. Please have a look at my paper http://journals.aps.org/pre/abstract/10.1103/PhysRevE.89.052117 (arXiv version). There you will find the answer to your question: if your constraints are average values, the maximum entropy measure is reached for the parameter found using the derivative of the log of the maximum eigenvalue (pressure).

• I took the liberty to add a link to the arXiv version of your paper. It seems to me that your statement, "the maximum entropy measure is reached for the parameter found using the derivative of the pressure" is also what Kurechenko-Wolf obtain (but it is not surprising that this is found independently in such different areas). My concerns is that computing somewhat explicitly this parameter from pressure is a daunting task. Do you succeed at getting exact, simple characterizations of these parameters? – Benoît Kloeckner Jun 15 '16 at 16:01
• I think that your answer would get more attention if it where somewhat more detailed, but it already gives a pointer to an area where these question are addressed, so +1. – Benoît Kloeckner Jun 15 '16 at 16:01