Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional -algebra . 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.
Positivity and Hankel determinants
Consider the -algebra with involution given by extending ; in other words, the free complex -algebra on a self-adjoint element. A state is uniquely determined by the moments which are real since the are all self-adjoint and which satisfy . Positivity is equivalent to the condition that for any we have
and this condition characterizes states on . That this condition actually characterizes Borel measures on the real line is the content of the solution to the Hamburger moment problem, although we will not use this fact. In discussing examples, we will make implicit use of the fact that various kinds of Borel measures on are uniquely determined by their moments thanks to results like Carleman’s condition, but only in order to identify these measures from their moments.
Note that by the universal property, if is any random algebra and any self-adjoint element, then there is a unique morphism of -algebras sending to , and pulling back the state on gives a state on . Consequently, everything we are about to say about states on places restrictions on states on any random algebra (more precisely, on moment sequences of self-adjoint elements of any random algebra).
The states which are not faithful are straightforward to describe.
Proposition: Let be a state on which is not faithful. If is a nonzero self-adjoint element of minimal degree such that , then is a finite sum of Dirac measures supported at the roots of , all of which are real.
Proof. Note that “self-adjoint” here is equivalent to having real coefficients. We first show that the roots of are all real. Suppose by contradiction that has a complex root with . Then it is divisible by . Writing where is self-adjoint, we have
.
By positivity of , it follows that , and since , it follows that , which contradicts the assumption that has minimal degree. Hence all of the roots of are real.
By the division algorithm, we can write any in the form where . By Cauchy-Schwarz we have , hence
.
Let be the real roots of . Since , by Lagrange interpolation we know that can be written
where
are the Lagrange interpolation polynomials, which do not depend on . Consequently,
which is a finite sum of Dirac measures supported at the points as desired.
The corresponding universal statement is the following: if is a self-adjoint element of any random algebra which has a minimal polynomial, then the state on restricted to is a finite sum of Dirac measures supported on the spectrum of (which is finite).
As for the faithful states, we can say the following. Faithfulness is equivalent to the condition that for every the Hankel matrix
with entries is positive-definite. This is because is the symmetric matrix describing the restriction of the inner product to the subspace of polynomials of degree less than . In particular, if is faithful, the Hankel determinants are positive. For example, is the variance .
Proposition (Sylvester’s criterion): is positive-definite if and only if for all .
Corollary: A moment sequence determines a faithful state if and only if for all .
Proof. We observed one direction above. In the other direction, we prove the contrapositive. Note that is always positive-definite. We proceed by induction. Assume that is positive-definite. By the spectral theorem, has an orthonormal basis of eigenvectors, which we may take to be self-adjoint elements of . Since , it follows that has an even number of eigenvectors with negative eigenvalues. Suppose by contradiction that it has at least one, hence at least two, such eigenvectors with negative eigenvalues . Then
with strict inequality if either or is nonzero. On the other hand, there exists some choice of such that , from which it follows that is not positive-definite; contradiction.
Hence has only positive eigenvalues, so is positive-definite.
So we have reduced the problem of determining whether a moment sequence describes a state on to the problem of determining whether its Hankel determinants are non-negative. Unfortunately, it is not at all obvious how to compute Hankel determinants. We give without proof several evaluations of Hankel determinants below; the proofs will be subsumed in a more general result later in the post.
Example. Consider the moment sequence . The corresponding Hankel matrices are the Hilbert matrices
and the corresponding Hankel determinants are
.
The corresponding state on describes the uniform distribution on .
Example. Consider the moment sequence , the Bell numbers. The corresponding Hankel determinants are
.
The corresponding state on describes the Poisson distribution with parameter .
Example. Consider the moment sequence with odd terms and even terms
.
The corresponding Hankel determinants are again
.
The corresponding state on describes the Gaussian distribution with mean and variance . As a corollary, the Hankel determinants of a moment sequence do not uniquely determine it.
Example. Consider the moment sequence . The corresponding Hankel determinants are
.
The corresponding state on describes the exponential distribution with mean .
Example. Consider the moment sequence with odd terms and even terms , the Catalan numbers. The corresponding Hankel determinants are
.
The corresponding state on describes the Wigner semicircle distribution with radius . The semicircle distribution is important in free probability, where it takes on a role analogous to the Gaussian distribution in a noncommutative version of the central limit theorem. It also appears in number theory as the Sato-Tate distribution, where it comes from the distribution of traces of a random element of .
Example. Consider the moment sequence . The corresponding Hankel determinants are again
.
The corresponding state on describes a random variable which is the square of a Wigner semicircularly distributed random variable.
Non-example. This example occurred a few years ago at the Secret Blogging Seminar. Consider the moment sequence with odd terms and even terms
.
The third Hankel determinant is
.
Hence this moment sequence does not define a state (and consequently cannot describe a random variable).
Orthogonal polynomials and Motzkin paths
Faithful states on are closely related to the classical theory of orthogonal polynomials. The starting point is that is a faithful state on if and only if defines an inner product on . Applying the Gram-Schmidt process with a slightly different normalization to the basis , we obtain a sequence of monic self-adjoint polynomials of degree , uniquely determined by the moment sequence , such that
whenever . (In addition, by faithfulness.) These are the orthogonal polynomials associated to (equivalently, to the moment sequence ).
Example. For a state describing a Wigner semicircular distribution with radius , the corresponding polynomials are (up to normalization) the Chebyshev polynomials of the second kind.
Example. For a state describing a Gaussian distribution with mean and variance , the corresponding polynomials are the probabilist’s Hermite polynomials.
Example. For a state describing the uniform distribution on , the corresponding polynomials are (up to normalization) the Legendre polynomials.
Example. For a state describing the exponential distribution with mean , the corresponding polynomials are (up to normalization) the Laguerre polynomials.
The moments can be evaluated in terms of the orthogonal polynomials as follows. First, by construction is orthogonal to all polynomials of degree at most . Since is self-adjoint with respect to the inner product above, is orthogonal to all polynomials of degree at most . It follows that the polynomials are orthogonal to all polynomials of degree at most but have degree at most , hence lie in a -dimensional subspace of . Moreover, by orthogonality are linearly independent. Hence there exists a nontrivial linear dependence of the form
where the coefficient of is determined by comparing leading coefficients. Thus the matrix of the linear operator given by multiplication by with respect to the basis is tridiagonal: it begins
.
Corollary: is the characteristic polynomial of the matrix
.
Proof. Multiplication by has characteristic polynomial on , which has basis , and the above is the matrix by which acts in this basis. Alternately, this can be proven by induction on using the recurrence relation above.
It will be convenient to think of the above matrix as the weighted adjacency matrix of a weighted graph with vertex set the non-negative integers and, for every , three edges: an edge to with weight , an edge to with weight , and an edge to with weight .
The power of this matrix describes the sums of weights of paths of length in this graph, and these weights describe the action of multiplication by with respect to the basis . The corresponding paths (disregarding weights) are Motzkin paths, and they are counted by the Motzkin numbers .
In particular, is equal to the sum of the weights of all closed walks in from to itself of length ; this sum contains terms, one for each Motzkin path, and may be thought of as a weighted Motzkin number. The first few such sums are as follows:
.
Example. For the Wigner semicircular distribution with , we have for all . The above expression for moments then reduces to a sum over Motzkin paths which never stay at a given vertex, hence over Dyck paths, which are counted by the Catalan numbers. There are no paths of odd length, and a path of length has weight . This gives and as expected.
The combinatorial description of moments in terms of Motzkin paths leads to the following beautiful continued fraction expansion.
Theorem: We have an equality of formal power series
.
Proof. This is more difficult to formalize than to understand. Consider the weighted graph described above. Let be the graph obtained from by deleting the vertices (and all corresponding edges), and let be the set of all paths from to in . The combinatorial content of the above theorem is that a path in has a unique decomposition into a sequence of paths of the following two forms:
- A loop (weight , length ), or
- A step (weight , length ), a path in , and a step (weight , length ).
Let denote the sum of all weights of all paths in , weighted in addition by . Then , and the above argument shows that
.
Applying this identity times verifies the desired equality , and taking gives the result by the universal property of formal power series.
A converse result
We saw above that we can associate to a faithful state on a sequence of monic polynomials of degree such that and
for some pair of sequences of real numbers uniquely determined by . This pair of sequences in turn uniquely determines the sequence of polynomials , hence uniquely determines the state via the conditions and .
Given an arbitrary such pair of real sequences, it is natural to ask when the corresponding linear functional determines a faithful state.
Proposition: If , then , and .
Proof. If , assume WLOG that . Write and apply the recurrence above to
to write it in the basis . Then does not appear as a term. One way to see this is to use the combinatorial interpretation; the coefficients in count paths on the weighted graph starting at of length , and such a path cannot return to the origin. Hence by construction .
If , then applying the recurrence to we see that the only contribution to the coefficient of comes from the unique path from to of length , which has weight as desired.
Corollary (Favard’s theorem): The linear functional on associated to a pair of real sequences as above is a faithful state if and only if for all .
Proof. Since the are orthogonal, is faithful if and only if for all .
This gives us a method to construct faithful states on without computing Hankel determinants: we can instead write down a sequence of real numbers and another sequence of positive real numbers, then compute the corresponding orthogonal polynomials. The corresponding moment sequence can be computed using Motzkin paths or using the continued fraction. Alternatively, given a moment sequence which we suspect determines a faithful state, we can write down what we suspect the corresponding orthogonal polynomials are and compute the sequences and to verify that for all .
Example. Taking for all gives the Wigner semicircular distribution with .
Computing Hankel determinants
We now give the promised result which explains the Hankel determinants given without proof above.
Theorem: With notation as above, we have
Proof 1. First, observe that the change of basis matrix from the basis to the basis is by construction triangular with s on the diagonal. Such a change of basis changes the Hankel matrices by a congruence where has determinant , and consequently does not affect the value of the Hankel determinants. We can therefore compute the Hankel determinants with respect to the basis of orthogonal polynomials. By construction, the Hankel matrices with respect to are diagonal:
.
It follows that
as desired.
Proof 2. We will give a combinatorial proof using the Lindström-Gessel-Viennot lemma. Consider the following locally finite directed acyclic graph : the vertices are the set of pairs with . The edges take the following forms:
- edges with weights ,
- edges with weight , and
- edges with weights .
For a fixed positive integer , take the sources in the statement of the LGV lemma to be the vertices and take the sinks to be the vertices . Then the paths from to may be identified with closed walks of length on the weighted Motzkin graph (in the sense that there is a weight-preserving bijection between them), so the matrix appearing in the statement of the LGV lemma is precisely the Hankel matrix (with respect to the basis ).
On the other hand, there is a unique non-intersecting -path in : the source is taken to the sink by diagonal steps up and to the right, then diagonal steps down and to the right, and this is the unique possibility by induction on . This path has weight , from which the conclusion follows by the LGV lemma.
Example. For the Wigner semicircular distribution with , we know that for all , which gives for all as desired.
Dear Qiaochu,
Thanks for sharing your valuable information. I have a question. Here what I understand was that we have a set of moments and then we use the Hankel determinants to determines a faithful state of the moments (let us say the moments are realizable if they grantee the Hankel determinants to be positive). Now my main question is that is there a reverse algorithm for this problem? What I mean is that we find a moments space where the hankel determinants are absolutely positive and then choose our moment set from that range? Thanks in advance for your valuable comment . Best, Ehsan
Can you rephrase the question? I’m not sure I understand what you’re asking for.
Faithfulness is equivalent to the condition that for every n the Hankel matrix
\displaystyle H_n = \left[ \begin{array}{cccc} m_0 & m_1 & \hdots & m_{n-1} \\ m_1 & m_2 & \hdots & m_n \\ \vdots & \vdots & \ddots & \vdots \\ m_{n-1} & m_n & \hdots & m_{2n-2} \end{array} \right]
with entries (H_n)_{i, j} = m_{i+j} is positive-definite. This is what I copy paste from your note.
Let us say we work in the range between \left[ 0,1\right]. What I am asking is that is there any way that for example we find the root of the Hankel determinants. Then for example the positivity of the Hankel determinant be grantee between \left[0, x \right] where x is the root we found in the previous step and then define the moments which have the hankel determinants at that range?
No idea. The closest I can get you is that the positivity of the Hankel determinants is equivalent to the positivity of the in the above notation, and these determine the moments, so you get a nice map whose image consists of faithful states.
What’s the reference for this approach of Hankel determinants and Orthogonal Polynomials?
I don’t have a reference.