Feeds:
Posts

Maximum entropy from Bayes’ theorem

The principle of maximum entropy asserts that when trying to determine an unknown probability distribution (for example, the distribution of possible results that occur when you toss a possibly unfair die), you should pick the distribution with maximum entropy consistent with your knowledge.

The goal of this post is to derive the principle of maximum entropy in the special case of probability distributions over finite sets from

• Bayes’ theorem and
• the principle of indifference: assign probability $\frac{1}{n}$ to each of $n$ possible outcomes if you have no additional knowledge. (The slogan in statistical mechanics is “all microstates are equally likely.”)

We’ll do this by deriving an arguably more fundamental principle of maximum relative entropy using only Bayes’ theorem.

Small factors in random polynomials over a finite field

Previously I mentioned very briefly Granville’s The Anatomy of Integers and Permutations, which explores an analogy between prime factorizations of integers and cycle decompositions of permutations. Today’s post is a record of the observation that this analogy factors through an analogy to prime factorizations of polynomials over finite fields in the following sense.

Theorem: Let $q$ be a prime power, let $n$ be a positive integer, and consider the distribution of irreducible factors of degree $1, 2, ... k$ in a random monic polynomial of degree $n$ over $\mathbb{F}_q$. Then, as $q \to \infty$, this distribution is asymptotically the distribution of cycles of length $1, 2, ... k$ in a random permutation of $n$ elements.

One can even name what this random permutation ought to be: namely, it is the Frobenius map $x \mapsto x^q$ acting on the roots of a random polynomial $f$, whose cycles of length $k$ are precisely the factors of degree $k$ of $f$.

Combined with our previous result, we conclude that as $q, n \to \infty$ (with $q$ tending to infinity sufficiently quickly relative to $n$), the distribution of irreducible factors of degree $1, 2, ... k$ is asymptotically independent Poisson with parameters $1, \frac{1}{2}, ... \frac{1}{k}$.

Short cycles in random permutations

Previously we showed that the distribution of fixed points of a random permutation of $n$ elements behaves asymptotically (in the limit as $n \to \infty$) like a Poisson random variable with parameter $\lambda = 1$. As it turns out, this generalizes to the following.

Theorem: As $n \to \infty$, the number of cycles of length $1, 2, ... k$ of a random permutation of $n$ elements are asymptotically independent Poisson with parameters $1, \frac{1}{2}, ... \frac{1}{k}$.

This is a fairly strong statement which essentially settles the asymptotic description of short cycles in random permutations.

Fixed points of random permutations

The following two results are straightforward and reasonably well-known exercises in combinatorics:

1. The number of permutations on $n$ elements with no fixed points (derangements) is approximately $\frac{n!}{e}$.
2. The expected number of fixed points of a random permutation on $n$ elements is $1$.

As it turns out, it is possible to say substantially more about the distribution of fixed points of a random permutation. In fact, the following is true.

Theorem: As $n \to \infty$, the distribution of the number of fixed points of a random permutation on $n$ elements is asymptotically Poisson with rate $\lambda = 1$.

Noncommutative probability and group theory

There are, roughly speaking, two kinds of algebras that can be functorially constructed from a group $G$. The kind which is covariantly functorial is some variation on the group algebra $k[G]$, which is the free $k$-module on $G$ with multiplication inherited from the multiplication on $G$. The kind which is contravariantly functorial is some variation on the algebra $k^G$ of functions $G \to k$ with pointwise multiplication.

When $k = \mathbb{C}$ and when $G$ is respectively either a discrete group or a compact (Hausdorff) group, both of these algebras can naturally be endowed with the structure of a random algebra. In the case of $\mathbb{C}[G]$, the corresponding state is a noncommutative refinement of Plancherel measure on the irreducible representations of $G$, while in the case of $\mathbb{C}^G$, the corresponding state is by definition integration with respect to normalized Haar measure on $G$.

In general, some nontrivial analysis is necessary to show that the normalized Haar measure exists, but for compact groups equipped with a faithful finite-dimensional unitary representation $V$ it is possible to at least describe integration against Haar measure for a dense subalgebra of the algebra of class functions on $G$ using representation theory. This construction will in some sense explain why the category $\text{Rep}(G)$ of (finite-dimensional continuous unitary) representations of $G$ behaves like an inner product space (with $\text{Hom}(V, W)$ being analogous to the inner product); what it actually behaves like is a random algebra, namely the random algebra of class functions on $G$.

Moments, Hankel determinants, orthogonal polynomials, Motzkin paths, and continued fractions

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional $^{\dagger}$-algebra $\mathbb{C}[x]$. Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.