Maximum entropy as applied common sense

Some tools are quite nice substitutes for having a well-defined problem. Let’s suppose that someone has kidnapped your cat and will only return it if you can produce a probability distribution on $1\dots 6$ with mean $5$. There’s the obvious answer, of course, but that’s a bit of a special case and a bit boring. What’s the least special answer to the question?

Amazingly enough problems like this come up surprisingly often — although I’ve yet to see it in the stated context. In general, can you produce a probability distribution that satisfies some constraint but is otherwise underdetermined?

A sensible solution is surprisingly simple, but it does require a bit of numerics (or grinding one’s way through $tanh$). The trick is to remember entropy. Barring boring factors, the entropy of a probability distribution is

and is a measure of the fuzziness of a distribution.

The maximum entropy distribution — the distribution that maximizes the entropy — is of course the uniform. (Jensen’s inequality.) But if we maximize the entropy subject to constraints, we get the fuzziest distribution possible compatible with the constraints. In our case, we want to maximize

over ${𝑝}_{𝑖}$, $𝜇$, and $𝜈$. ($𝜇$ and $𝜈$ are Lagrange multipliers that enforce normalization and our mean constraint.) We find that

We’ve got to find $𝜈$ by enforcing the mean constraint, most conveniently done numerically.

softmax <- function(z) {
  z <- z - max(z)
  probs <- exp(z)
  probs / sum(probs)
}

cost <- function(x, s, target) {
    probs <- softmax(x * s) 
    m <- s %*% probs
    m - target
}

s <- seq(1, 6, by=1)

vals <- seq(-2, 2, by=0.05)
t <- vapply(vals, cost, 0, s, 5)

plot(vals, t, type='l')

crit <- uniroot(cost, c(-2, 2), s, 5)
cost(crit$root,s , 5)

p <- softmax(s * crit$root)
p

And, behold, the cat is free.

If our catnapper is a statistical physicist¹ and is shouting about ensembles and partition functions we can of course tell them that

where