You are currently browsing the tag archive for the ‘spectral theorem’ tag.
The prime number theorem can be expressed as the assertion
as , where
is the von Mangoldt function. It is a basic result in analytic number theory, but requires a bit of effort to prove. One “elementary” proof of this theorem proceeds through the Selberg symmetry formula
(We are avoiding the use of the symbol here to denote Dirichlet convolution, as we will need this symbol to denote ordinary convolution shortly.) For the convenience of the reader, we give a proof of the Selberg symmetry formula below the fold. Actually, for the purposes of proving the prime number theorem, the weaker estimate
In this post I would like to record a somewhat “soft analysis” reformulation of the elementary proof of the prime number theorem in terms of Banach algebras, and specifically in Banach algebra structures on (completions of) the space of compactly supported continuous functions equipped with the convolution operation
This soft argument does not easily give any quantitative decay rate in the prime number theorem, but by the same token it avoids many of the quantitative calculations in the traditional proofs of this theorem. Ultimately, the key “soft analysis” fact used is the spectral radius formula
for any element of a unital commutative Banach algebra , where is the space of characters (i.e., continuous unital algebra homomorphisms from to ) of . This formula is due to Gelfand and may be found in any text on Banach algebras; for sake of completeness we prove it below the fold.
The connection between prime numbers and Banach algebras is given by the following consequence of the Selberg symmetry formula.
for all .
We prove this theorem below the fold. The prime number theorem then follows from Theorem 1 and the following two assertions. The first is an application of the spectral radius formula (6) and some basic Fourier analysis (in particular, the observation that contains a plentiful supply of local units:
for all . In particular, by (7), one has
whenever is a non-negative function.
The second is a consequence of the Selberg symmetry formula and the fact that is real (as well as Mertens’ theorem, in the case), and is closely related to the non-vanishing of the Riemann zeta function on the line :
as for any Schwartz function (the decay rate in may depend on ). Specialising to functions of the form for some smooth compactly supported on , we conclude that
as ; by the smooth Urysohn lemma this implies that
as for any fixed , and the prime number theorem then follows by a telescoping series argument.
The same argument also yields the prime number theorem in arithmetic progressions, or equivalently that
for any fixed Dirichlet character ; the one difference is that the use of Mertens’ theorem is replaced by the basic fact that the quantity is non-vanishing.
In the traditional foundations of probability theory, one selects a probability space , and makes a distinction between deterministic mathematical objects, which do not depend on the sampled state , and stochastic (or random) mathematical objects, which do depend (but in a measurable fashion) on the sampled state . For instance, a deterministic real number would just be an element , whereas a stochastic real number (or real random variable) would be a measurable function , where in this post will always be endowed with the Borel -algebra. (For readers familiar with nonstandard analysis, the adjectives “deterministic” and “stochastic” will be used here in a manner analogous to the uses of the adjectives “standard” and “nonstandard” in nonstandard analysis. The analogy is particularly close when comparing with the “cheap nonstandard analysis” discussed in this previous blog post. We will also use “relative to ” as a synonym for “stochastic”.)
Actually, for our purposes we will adopt the philosophy of identifying stochastic objects that agree almost surely, so if one was to be completely precise, we should define a stochastic real number to be an equivalence class of measurable functions , up to almost sure equivalence. However, we shall often abuse notation and write simply as .
More generally, given any measurable space , we can talk either about deterministic elements , or about stochastic elements of , that is to say equivalence classes of measurable maps up to almost sure equivalence. We will use to denote the set of all stochastic elements of . (For readers familiar with sheaves, it may helpful for the purposes of this post to think of as the space of measurable global sections of the trivial –bundle over .) Of course every deterministic element of can also be viewed as a stochastic element given by (the equivalence class of) the constant function , thus giving an embedding of into . We do not attempt here to give an interpretation of for sets that are not equipped with a -algebra .
Remark 1 In my previous post on the foundations of probability theory, I emphasised the freedom to extend the sample space to a larger sample space whenever one wished to inject additional sources of randomness. This is of course an important freedom to possess (and in the current formalism, is the analogue of the important operation of base change in algebraic geometry), but in this post we will focus on a single fixed sample space , and not consider extensions of this space, so that one only has to consider two types of mathematical objects (deterministic and stochastic), as opposed to having many more such types, one for each potential choice of sample space (with the deterministic objects corresponding to the case when the sample space collapses to a point).
Any (measurable) -ary operation on deterministic mathematical objects then extends to their stochastic counterparts by applying the operation pointwise. For instance, the addition operation on deterministic real numbers extends to an addition operation , by defining the class for to be the equivalence class of the function ; this operation is easily seen to be well-defined. More generally, any measurable -ary deterministic operation between measurable spaces extends to an stochastic operation in the obvious manner.
There is a similar story for -ary relations , although here one has to make a distinction between a deterministic reading of the relation and a stochastic one. Namely, if we are given stochastic objects for , the relation does not necessarily take values in the deterministic Boolean algebra , but only in the stochastic Boolean algebra – thus may be true with some positive probability and also false with some positive probability (with the event that being stochastically true being determined up to null events). Of course, the deterministic Boolean algebra embeds in the stochastic one, so we can talk about a relation being determinstically true or deterministically false, which (due to our identification of stochastic objects that agree almost surely) means that is almost surely true or almost surely false respectively. For instance given two stochastic objects , one can view their equality relation as having a stochastic truth value. This is distinct from the way the equality symbol is used in mathematical logic, which we will now call “equality in the deterministic sense” to reduce confusion. Thus, in the deterministic sense if and only if the stochastic truth value of is equal to , that is to say that for almost all .
Any universal identity for deterministic operations (or universal implication between identities) extends to their stochastic counterparts: for instance, addition is commutative, associative, and cancellative on the space of deterministic reals , and is therefore commutative, associative, and cancellative on stochastic reals as well. However, one has to be more careful when working with mathematical laws that are not expressible as universal identities, or implications between identities. For instance, is an integral domain: if are deterministic reals such that , then one must have or . However, if are stochastic reals such that (in the deterministic sense), then it is no longer necessarily the case that (in the deterministic sense) or that (in the deterministic sense); however, it is still true that “ or ” is true in the deterministic sense if one interprets the boolean operator “or” stochastically, thus “ or ” is true for almost all . Another way to properly obtain a stochastic interpretation of the integral domain property of is to rewrite it as
and then make all sets stochastic to obtain the true statement
thus we have to allow the index for which vanishing occurs to also be stochastic, rather than deterministic. (A technical note: when one proves this statement, one has to select in a measurable fashion; for instance, one can choose to equal when , and otherwise (so that in the “tie-breaking” case when and both vanish, one always selects to equal ).)
Similarly, the law of the excluded middle fails when interpreted deterministically, but remains true when interpreted stochastically: if is a stochastic statement, then it is not necessarily the case that is either deterministically true or deterministically false; however the sentence “ or not-” is still deterministically true if the boolean operator “or” is interpreted stochastically rather than deterministically.
To avoid having to keep pointing out which operations are interpreted stochastically and which ones are interpreted deterministically, we will use the following convention: if we assert that a mathematical sentence involving stochastic objects is true, then (unless otherwise specified) we mean that is deterministically true, assuming that all relations used inside are interpreted stochastically. For instance, if are stochastic reals, when we assert that “Exactly one of , , or is true”, then by default it is understood that the relations , , and the boolean operator “exactly one of” are interpreted stochastically, and the assertion is that the sentence is deterministically true.
In the above discussion, the stochastic objects being considered were elements of a deterministic space , such as the reals . However, it can often be convenient to generalise this situation by allowing the ambient space to also be stochastic. For instance, one might wish to consider a stochastic vector inside a stochastic vector space , or a stochastic edge of a stochastic graph . In order to formally describe this situation within the classical framework of measure theory, one needs to place all the ambient spaces inside a measurable space. This can certainly be done in many contexts (e.g. when considering random graphs on a deterministic set of vertices, or if one is willing to work up to equivalence and place the ambient spaces inside a suitable moduli space), but is not completely natural in other contexts. For instance, if one wishes to consider stochastic vector spaces of potentially unbounded dimension (in particular, potentially larger than any given cardinal that one might specify in advance), then the class of all possible vector spaces is so large that it becomes a proper class rather than a set (even if one works up to equivalence), making it problematic to give this class the structure of a measurable space; furthermore, even once one does so, one needs to take additional care to pin down what it would mean for a random vector lying in a random vector space to depend “measurably” on .
Of course, in any reasonable application one can avoid the set theoretic issues at least by various ad hoc means, for instance by restricting the dimension of all spaces involved to some fixed cardinal such as . However, the measure-theoretic issues can require some additional effort to resolve properly.
In this post I would like to describe a different way to formalise stochastic spaces, and stochastic elements of these spaces, by viewing the spaces as measure-theoretic analogue of a sheaf, but being over the probability space rather than over a topological space; stochastic objects are then sections of such sheaves. Actually, for minor technical reasons it is convenient to work in the slightly more general setting in which the base space is a finite measure space rather than a probability space, thus can take any value in rather than being normalised to equal . This will allow us to easily localise to subevents of without the need for normalisation, even when is a null event (though we caution that the map from deterministic objects ceases to be injective in this latter case). We will however still continue to use probabilistic terminology. despite the lack of normalisation; thus for instance, sets in will be referred to as events, the measure of such a set will be referred to as the probability (which is now permitted to exceed in some cases), and an event whose complement is a null event shall be said to hold almost surely. It is in fact likely that almost all of the theory below extends to base spaces which are -finite rather than finite (for instance, by damping the measure to become finite, without introducing any further null events), although we will not pursue this further generalisation here.
The approach taken in this post is “topos-theoretic” in nature (although we will not use the language of topoi explicitly here), and is well suited to a “pointless” or “point-free” approach to probability theory, in which the role of the stochastic state is suppressed as much as possible; instead, one strives to always adopt a “relative point of view”, with all objects under consideration being viewed as stochastic objects relative to the underlying base space . In this perspective, the stochastic version of a set is as follows.
Definition 1 (Stochastic set) Unless otherwise specified, we assume that we are given a fixed finite measure space (which we refer to as the base space). A stochastic set (relative to ) is a tuple consisting of the following objects:
- A set assigned to each event ; and
- A restriction map from to to each pair of nested events . (Strictly speaking, one should indicate the dependence on in the notation for the restriction map, e.g. using instead of , but we will abuse notation by omitting the dependence.)
We refer to elements of as local stochastic elements of the stochastic set , localised to the event , and elements of as global stochastic elements (or simply elements) of the stochastic set. (In the language of sheaves, one would use “sections” instead of “elements” here, but I prefer to use the latter terminology here, for compatibility with conventional probabilistic notation, where for instance measurable maps from to are referred to as real random variables, rather than sections of the reals.)
Furthermore, we impose the following axioms:
- (Category) The map from to is the identity map, and if are events in , then for all .
- (Null events trivial) If is a null event, then the set is a singleton set. (In particular, is always a singleton set; this is analogous to the convention that for any number .)
- (Countable gluing) Suppose that for each natural number , one has an event and an element such that for all . Then there exists a unique such that for all .
If is an event in , we define the localisation of the stochastic set to to be the stochastic set
relative to . (Note that there is no need to renormalise the measure on , as we are not demanding that our base space have total measure .)
The following fact is useful for actually verifying that a given object indeed has the structure of a stochastic set:
Exercise 1 Show that to verify the countable gluing axiom of a stochastic set, it suffices to do so under the additional hypothesis that the events are disjoint. (Note that this is quite different from the situation with sheaves over a topological space, in which the analogous gluing axiom is often trivial in the disjoint case but has non-trivial content in the overlapping case. This is ultimately because a -algebra is closed under all Boolean operations, whereas a topology is only closed under union and intersection.)
Let us illustrate the concept of a stochastic set with some examples.
Example 1 (Discrete case) A simple case arises when is a discrete space which is at most countable. If we assign a set to each , with a singleton if . One then sets , with the obvious restriction maps, giving rise to a stochastic set . (Thus, a local element of can be viewed as a map on that takes values in for each .) Conversely, it is not difficult to see that any stochastic set over an at most countable discrete probability space is of this form up to isomorphism. In this case, one can think of as a bundle of sets over each point (of positive probability) in the base space . One can extend this bundle interpretation of stochastic sets to reasonably nice sample spaces (such as standard Borel spaces) and similarly reasonable ; however, I would like to avoid this interpretation in the formalism below in order to be able to easily work in settings in which and are very “large” (e.g. not separable in any reasonable sense). Note that we permit some of the to be empty, thus it can be possible for to be empty whilst for some strict subevents of to be non-empty. (This is analogous to how it is possible for a sheaf to have local sections but no global sections.) As such, the space of global elements does not completely determine the stochastic set ; one sometimes needs to localise to an event in order to see the full structure of such a set. Thus it is important to distinguish between a stochastic set and its space of global elements. (As such, it is a slight abuse of the axiom of extensionality to refer to global elements of simply as “elements”, but hopefully this should not cause too much confusion.)
Example 2 (Measurable spaces as stochastic sets) Returning now to a general base space , any (deterministic) measurable space gives rise to a stochastic set , with being defined as in previous discussion as the measurable functions from to modulo almost everywhere equivalence (in particular, a singleton set when is null), with the usual restriction maps. The constraint of measurability on the maps , together with the quotienting by almost sure equivalence, means that is now more complicated than a plain Cartesian product of fibres, but this still serves as a useful first approximation to what is for the purposes of developing intuition. Indeed, the measurability constraint is so weak (as compared for instance to topological or smooth constraints in other contexts, such as sheaves of continuous or smooth sections of bundles) that the intuition of essentially independent fibres is quite an accurate one, at least if one avoids consideration of an uncountable number of objects simultaneously.
Example 3 (Extended Hilbert modules) This example is the one that motivated this post for me. Suppose that one has an extension of the base space , thus we have a measurable factor map such that the pushforward of the measure by is equal to . Then we have a conditional expectation operator , defined as the adjoint of the pullback map . As is well known, the conditional expectation operator also extends to a contraction ; by monotone convergence we may also extend to a map from measurable functions from to the extended non-negative reals , to measurable functions from to . We then define the “extended Hilbert module” to be the space of functions with finite almost everywhere. This is an extended version of the Hilbert module , which is defined similarly except that is required to lie in ; this is a Hilbert module over which is of particular importance in the Furstenberg-Zimmer structure theory of measure-preserving systems. We can then define the stochastic set by setting
with the obvious restriction maps. In the case that are standard Borel spaces, one can disintegrate as an integral of probability measures (supported in the fibre ), in which case this stochastic set can be viewed as having fibres (though if is not discrete, there are still some measurability conditions in on the local and global elements that need to be imposed). However, I am interested in the case when are not standard Borel spaces (in fact, I will take them to be algebraic probability spaces, as defined in this previous post), in which case disintegrations are not available. However, it appears that the stochastic analysis developed in this blog post can serve as a substitute for the tool of disintegration in this context.
We make the remark that if is a stochastic set and are events that are equivalent up to null events, then one can identify with (through their common restriction to , with the restriction maps now being bijections). As such, the notion of a stochastic set does not require the full structure of a concrete probability space ; one could also have defined the notion using only the abstract -algebra consisting of modulo null events as the base space, or equivalently one could define stochastic sets over the algebraic probability spaces defined in this previous post. However, we will stick with the classical formalism of concrete probability spaces here so as to keep the notation reasonably familiar.
As a corollary of the above observation, we see that if the base space has total measure , then all stochastic sets are trivial (they are just points).
Exercise 2 If is a stochastic set, show that there exists an event with the property that for any event , is non-empty if and only if is contained in modulo null events. (In particular, is unique up to null events.) Hint: consider the numbers for ranging over all events with non-empty, and form a maximising sequence for these numbers. Then use all three axioms of a stochastic set.
One can now start take many of the fundamental objects, operations, and results in set theory (and, hence, in most other categories of mathematics) and establish analogues relative to a finite measure space. Implicitly, what we will be doing in the next few paragraphs is endowing the category of stochastic sets with the structure of an elementary topos. However, to keep things reasonably concrete, we will not explicitly emphasise the topos-theoretic formalism here, although it is certainly lurking in the background.
Firstly, we define a stochastic function between two stochastic sets to be a collection of maps for each which form a natural transformation in the sense that for all and nested events . In the case when is discrete and at most countable (and after deleting all null points), a stochastic function is nothing more than a collection of functions for each , with the function then being a direct sum of the factor functions :
Thus (in the discrete, at most countable setting, at least) stochastic functions do not mix together information from different states in a sample space; the value of at depends only on the value of at . The situation is a bit more subtle for continuous probability spaces, due to the identification of stochastic objects that agree almost surely, nevertheness it is still good intuition to think of stochastic functions as essentially being “pointwise” or “local” in nature.
One can now form the stochastic set of functions from to , by setting for any event to be the set of local stochastic functions of the localisations of to ; this is a stochastic set if we use the obvious restriction maps. In the case when is discrete and at most countable, the fibre at a point of positive measure is simply the set of functions from to .
In a similar spirit, we say that one stochastic set is a (stochastic) subset of another , and write , if we have a stochastic inclusion map, thus for all events , with the restriction maps being compatible. We can then define the power set of a stochastic set by setting for any event to be the set of all stochastic subsets of relative to ; it is easy to see that is a stochastic set with the obvious restriction maps (one can also identify with in the obvious fashion). Again, when is discrete and at most countable, the fibre of at a point of positive measure is simply the deterministic power set .
Note that if is a stochastic function and is a stochastic subset of , then the inverse image , defined by setting for any event to be the set of those with , is a stochastic subset of . In particular, given a -ary relation , the inverse image is a stochastic subset of , which by abuse of notation we denote as
In a similar spirit, if is a stochastic subset of and is a stochastic function, we can define the image by setting to be the set of those with ; one easily verifies that this is a stochastic subset of .
Remark 2 One should caution that in the definition of the subset relation , it is important that for all events , not just the global event ; in particular, just because a stochastic set has no global sections, does not mean that it is contained in the stochastic empty set .
Now we discuss Boolean operations on stochastic subsets of a given stochastic set . Given two stochastic subsets of , the stochastic intersection is defined by setting to be the set of that lie in both and :
This is easily verified to again be a stochastic subset of . More generally one may define stochastic countable intersections for any sequence of stochastic subsets of . One could extend this definition to uncountable families if one wished, but I would advise against it, because some of the usual laws of Boolean algebra (e.g. the de Morgan laws) may break down in this setting.
Stochastic unions are a bit more subtle. The set should not be defined to simply be the union of and , as this would not respect the gluing axiom. Instead, we define to be the set of all such that one can cover by measurable subevents such that for ; then may be verified to be a stochastic subset of . Thus for instance is the stochastic union of and . Similarly for countable unions of stochastic subsets of , although for uncountable unions are extremely problematic (they are disliked by both the measure theory and the countable gluing axiom) and will not be defined here. Finally, the stochastic difference set is defined as the set of all in such that for any subevent of of positive probability. One may verify that in the case when is discrete and at most countable, these Boolean operations correspond to the classical Boolean operations applied separately to each fibre of the relevant sets . We also leave as an exercise to the reader to verify the usual laws of Boolean arithmetic, e.g. the de Morgan laws, provided that one works with at most countable unions and intersections.
One can also consider a stochastic finite union in which the number of sets in the union is itself stochastic. More precisely, let be a stochastic set, let be a stochastic natural number, and let be a stochastic function from the stochastic set (defined by setting )) to the stochastic power set . Here we are considering to be a natural number, to allow for unions that are possibly empty, with used for the positive natural numbers. We also write for the stochastic function . Then we can define the stochastic union by setting for an event to be the set of local elements with the property that there exists a covering of by measurable subevents for , such that one has and . One can verify that is a stochastic set (with the obvious restriction maps). Again, in the model case when is discrete and at most countable, the fibre is what one would expect it to be, namely .
The Cartesian product of two stochastic sets may be defined by setting for all events , with the obvious restriction maps; this is easily seen to be another stochastic set. This lets one define the concept of a -ary operation from stochastic sets to another stochastic set , or a -ary relation . In particular, given for , the relation may be deterministically true, deterministically false, or have some other stochastic truth value.
Remark 3 In the degenerate case when is null, stochastic logic becomes a bit weird: all stochastic statements are deterministically true, as are their stochastic negations, since every event in (even the empty set) now holds with full probability. Among other pathologies, the empty set now has a global element over (this is analogous to the notorious convention ), and any two deterministic objects become equal over : .
The following simple observation is crucial to subsequent discussion. If is a sequence taking values in the global elements of a stochastic space , then we may also define global elements for stochastic indices as well, by appealing to the countable gluing axiom to glue together restricted to the set for each deterministic natural number to form . With this definition, the map is a stochastic function from to ; indeed, this creates a one-to-one correspondence between external sequences (maps from to ) and stochastic sequences (stochastic functions from to ). Similarly with replaced by any other at most countable set. This observation will be important in allowing many deterministic arguments involving sequences will be able to be carried over to the stochastic setting.
We now specialise from the extremely broad discipline of set theory to the more focused discipline of real analysis. There are two fundamental axioms that underlie real analysis (and in particular distinguishes it from real algebra). The first is the Archimedean property, which we phrase in the “no infinitesimal” formulation as follows:
Proposition 2 (Archimedean property) Let be such that for all positive natural numbers . Then .
The other is the least upper bound axiom:
- for all .
- For any real , there exists such that .
Furthermore, does not depend on the choice of .
The Archimedean property extends easily to the stochastic setting:
Remark 4 Here, incidentally, is one place in which this stochastic formalism deviates from the nonstandard analysis formalism, as the latter certainly permits the existence of infinitesimal elements. On the other hand, we caution that stochastic real numbers are permitted to be unbounded, so that formulation of Archimedean property is not valid in the stochastic setting.
The proof is easy and is left to the reader. The least upper bound axiom also extends nicely to the stochastic setting, but the proof requires more work (in particular, our argument uses the monotone convergence theorem):
Theorem 5 (Stochastic least upper bound axiom) Let be a stochastic subset of which has a global upper bound , thus for all , and is globally non-empty in the sense that there is at least one global element . Then there exists a unique stochastic real number with the following properties:
- for all .
- For any stochastic real , there exists such that .
Furthermore, does not depend on the choice of .
For future reference, we note that the same result holds with replaced by throughout, since the latter may be embedded in the former, for instance by mapping to and to . In applications, the above theorem serves as a reasonable substitute for the countable axiom of choice, which does not appear to hold in unrestricted generality relative to a measure space; in particular, it can be used to generate various extremising sequences for stochastic functionals on various stochastic function spaces.
Proof: Uniqueness is clear (using the Archimedean property), as well as the independence on , so we turn to existence. By using an order-preserving map from to (e.g. ) we may assume that is a subset of , and that .
We observe that is a lattice: if , then and also lie in . Indeed, may be formed by appealing to the countable gluing axiom to glue (restricted the set ) with (restricted to the set ), and similarly for . (Here we use the fact that relations such as are Borel measurable on .)
Let denote the deterministic quantity
then (by Proposition 3!) is well-defined; here we use the hypothesis that is finite. Thus we may find a sequence of elements of such that
Using the lattice property, we may assume that the are non-decreasing: whenever . If we then define (after choosing measurable representatives of each equivalence class ), then is a stochastic real with .
If , then , and so
From this and (1) we conclude that
From monotone convergence, we conclude that
and so , as required.
Now let be a stochastic real. After choosing measurable representatives of each relevant equivalence class, we see that for almost every , we can find a natural number with . If we choose to be the first such positive natural number when it exists, and (say) otherwise, then is a stochastic positive natural number and . The claim follows.
Remark 5 One can abstract away the role of the measure here, leaving only the ideal of null sets. The property that the measure is finite is then replaced by the more general property that given any non-empty family of measurable sets, there is an at most countable union of sets in that family that is an upper bound modulo null sets for all elements in that faily.
Using Proposition 4 and Theorem 5, one can then revisit many of the other foundational results of deterministic real analysis, and develop stochastic analogues; we give some examples of this below the fold (focusing on the Heine-Borel theorem and a case of the spectral theorem). As an application of this formalism, we revisit some of the Furstenberg-Zimmer structural theory of measure-preserving systems, particularly that of relatively compact and relatively weakly mixing systems, and interpret them in this framework, basically as stochastic versions of compact and weakly mixing systems (though with the caveat that the shift map is allowed to act non-trivially on the underlying probability space). As this formalism is “point-free”, in that it avoids explicit use of fibres and disintegrations, it will be well suited for generalising this structure theory to settings in which the underlying probability spaces are not standard Borel, and the underlying groups are uncountable; I hope to discuss such generalisations in future blog posts.
Remark 6 Roughly speaking, stochastic real analysis can be viewed as a restricted subset of classical real analysis in which all operations have to be “measurable” with respect to the base space. In particular, indiscriminate application of the axiom of choice is not permitted, and one should largely restrict oneself to performing countable unions and intersections rather than arbitrary unions or intersections. Presumably one can formalise this intuition with a suitable “countable transfer principle”, but I was not able to formulate a clean and general principle of this sort, instead verifying various assertions about stochastic objects by hand rather than by direct transfer from the deterministic setting. However, it would be desirable to have such a principle, since otherwise one is faced with the tedious task of redoing all the foundations of real analysis (or whatever other base theory of mathematics one is going to be working in) in the stochastic setting by carefully repeating all the arguments.
More generally, topos theory is a good formalism for capturing precisely the informal idea of performing mathematics with certain operations, such as the axiom of choice, the law of the excluded middle, or arbitrary unions and intersections, being somehow “prohibited” or otherwise “restricted”.
Let be a self-adjoint operator on a finite-dimensional Hilbert space . The behaviour of this operator can be completely described by the spectral theorem for finite-dimensional self-adjoint operators (i.e. Hermitian matrices, when viewed in coordinates), which provides a sequence of eigenvalues and an orthonormal basis of eigenfunctions such that for all . In particular, given any function on the spectrum of , one can then define the linear operator by the formula
which then gives a functional calculus, in the sense that the map is a -algebra isometric homomorphism from the algebra of bounded continuous functions from to , to the algebra of bounded linear operators on . Thus, for instance, one can define heat operators for , Schrödinger operators for , resolvents for , and (if is positive) wave operators for . These will be bounded operators (and, in the case of the Schrödinger and wave operators, unitary operators, and in the case of the heat operators with positive, they will be contractions). Among other things, this functional calculus can then be used to solve differential equations such as the heat equation
The functional calculus can also be associated to a spectral measure. Indeed, for any vectors , there is a complex measure on with the property that
indeed, one can set to be the discrete measure on defined by the formula
One can also view this complex measure as a coefficient
of a projection-valued measure on , defined by setting
Finally, one can view as unitarily equivalent to a multiplication operator on , where is the real-valued function , and the intertwining map is given by
so that .
It is an important fact in analysis that many of these above assertions extend to operators on an infinite-dimensional Hilbert space , so long as one one is careful about what “self-adjoint operator” means; these facts are collectively referred to as the spectral theorem. For instance, it turns out that most of the above claims have analogues for bounded self-adjoint operators . However, in the theory of partial differential equations, one often needs to apply the spectral theorem to unbounded, densely defined linear operators , which (initially, at least), are only defined on a dense subspace of the Hilbert space . A very typical situation arises when is the square-integrable functions on some domain or manifold (which may have a boundary or be otherwise “incomplete”), and are the smooth compactly supported functions on , and is some linear differential operator. It is then of interest to obtain the spectral theorem for such operators, so that one build operators such as or to solve equations such as (1), (2), (3), (4).
for all . These hypotheses are sufficient in the case when is bounded, and in particular when is finite dimensional. However, as it turns out, for unbounded operators these conditions are not, by themselves, enough to obtain a good spectral theory. For instance, one consequence of the spectral theorem should be that the resolvents are well-defined for any strictly complex , which by duality implies that the image of should be dense in . However, this can fail if one just assumes symmetry, or symmetry and positive definiteness. A well-known example occurs when is the Hilbert space , is the space of test functions, and is the one-dimensional Laplacian . Then is symmetric and positive, but the operator does not have dense image for any complex , since
for all test functions , as can be seen from a routine integration by parts. As such, the resolvent map is not everywhere uniquely defined. There is also a lack of uniqueness for the wave, heat, and Schrödinger equations for this operator (note that there are no spatial boundary conditions specified in these equations).
Another example occurs when , , is the momentum operator . Then the resolvent can be uniquely defined for in the upper half-plane, but not in the lower half-plane, due to the obstruction
for all test functions (note that the function lies in when is in the lower half-plane). For related reasons, the translation operators have a problem with either uniqueness or existence (depending on whether is positive or negative), due to the unspecified boundary behaviour at the origin.
The key property that lets one avoid this bad behaviour is that of essential self-adjointness. Once is essentially self-adjoint, then spectral theorem becomes applicable again, leading to all the expected behaviour (e.g. existence and uniqueness for the various PDE given above).
Unfortunately, the concept of essential self-adjointness is defined rather abstractly, and is difficult to verify directly; unlike the symmetry condition (5) or the positive condition (6), it is not a “local” condition that can be easily verified just by testing on various inputs, but is instead a more “global” condition. In practice, to verify this property, one needs to invoke one of a number of a partial converses to the spectral theorem, which roughly speaking asserts that if at least one of the expected consequences of the spectral theorem is true for some symmetric densely defined operator , then is self-adjoint. Examples of “expected consequences” include:
- Existence of resolvents (or equivalently, dense image for );
- Existence of a contractive heat propagator semigroup (in the positive case);
- Existence of a unitary Schrödinger propagator group ;
- Existence of a unitary wave propagator group (in the positive case);
- Existence of a “reasonable” functional calculus.
- Unitary equivalence with a multiplication operator.
Thus, to actually verify essential self-adjointness of a differential operator, one typically has to first solve a PDE (such as the wave, Schrödinger, heat, or Helmholtz equation) by some non-spectral method (e.g. by a contraction mapping argument, or a perturbation argument based on an operator already known to be essentially self-adjoint). Once one can solve one of the PDEs, then one can apply one of the known converse spectral theorems to obtain essential self-adjointness, and then by the forward spectral theorem one can then solve all the other PDEs as well. But there is no getting out of that first step, which requires some input (typically of an ODE, PDE, or geometric nature) that is external to what abstract spectral theory can provide. For instance, if one wants to establish essential self-adjointness of the Laplace-Beltrami operator on a smooth Riemannian manifold (using as the domain space), it turns out (under reasonable regularity hypotheses) that essential self-adjointness is equivalent to geodesic completeness of the manifold, which is a global ODE condition rather than a local one: one needs geodesics to continue indefinitely in order to be able to (unitarily) solve PDEs such as the wave equation, which in turn leads to essential self-adjointness. (Note that the domains and in the previous examples were not geodesically complete.) For this reason, essential self-adjointness of a differential operator is sometimes referred to as quantum completeness (with the completeness of the associated Hamilton-Jacobi flow then being the analogous classical completeness).
In these notes, I wanted to record (mostly for my own benefit) the forward and converse spectral theorems, and to verify essential self-adjointness of the Laplace-Beltrami operator on geodesically complete manifolds. This is extremely standard analysis (covered, for instance, in the texts of Reed and Simon), but I wanted to write it down myself to make sure that I really understood this foundational material properly.
In the foundations of modern probability, as laid out by Kolmogorov, the basic objects of study are constructed in the following order:
- Firstly, one selects a sample space , whose elements represent all the possible states that one’s stochastic system could be in.
- Then, one selects a -algebra of events (modeled by subsets of ), and assigns each of these events a probability in a countably additive manner, so that the entire sample space has probability .
- Finally, one builds (commutative) algebras of random variables (such as complex-valued random variables, modeled by measurable functions from to ), and (assuming suitable integrability or moment conditions) one can assign expectations to each such random variable.
In measure theory, the underlying measure space plays a prominent foundational role, with the measurable sets and measurable functions (the analogues of the events and the random variables) always being viewed as somehow being attached to that space. In probability theory, in contrast, it is the events and their probabilities that are viewed as being fundamental, with the sample space being abstracted away as much as possible, and with the random variables and expectations being viewed as derived concepts. See Notes 0 for further discussion of this philosophy.
However, it is possible to take the abstraction process one step further, and view the algebra of random variables and their expectations as being the foundational concept, and ignoring both the presence of the original sample space, the algebra of events, or the probability measure.
There are two reasons for wanting to shed (or abstract away) these previously foundational structures. Firstly, it allows one to more easily take certain types of limits, such as the large limit when considering random matrices, because quantities built from the algebra of random variables and their expectations, such as the normalised moments of random matrices tend to be quite stable in the large limit (as we have seen in previous notes), even as the sample space and event space varies with . (This theme of using abstraction to facilitate the taking of the large limit also shows up in the application of ergodic theory to combinatorics via the correspondence principle; see this previous blog post for further discussion.)
Secondly, this abstract formalism allows one to generalise the classical, commutative theory of probability to the more general theory of non-commutative probability theory, which does not have a classical underlying sample space or event space, but is instead built upon a (possibly) non-commutative algebra of random variables (or “observables”) and their expectations (or “traces”). This more general formalism not only encompasses classical probability, but also spectral theory (with matrices or operators taking the role of random variables, and the trace taking the role of expectation), random matrix theory (which can be viewed as a natural blend of classical probability and spectral theory), and quantum mechanics (with physical observables taking the role of random variables, and their expected value on a given quantum state being the expectation). It is also part of a more general “non-commutative way of thinking” (of which non-commutative geometry is the most prominent example), in which a space is understood primarily in terms of the ring or algebra of functions (or function-like objects, such as sections of bundles) placed on top of that space, and then the space itself is largely abstracted away in order to allow the algebraic structures to become less commutative. In short, the idea is to make algebra the foundation of the theory, as opposed to other possible choices of foundations such as sets, measures, categories, etc..
[Note that this foundational preference is to some extent a metamathematical one rather than a mathematical one; in many cases it is possible to rewrite the theory in a mathematically equivalent form so that some other mathematical structure becomes designated as the foundational one, much as probability theory can be equivalently formulated as the measure theory of probability measures. However, this does not negate the fact that a different choice of foundations can lead to a different way of thinking about the subject, and thus to ask a different set of questions and to discover a different set of proofs and solutions. Thus it is often of value to understand multiple foundational perspectives at once, to get a truly stereoscopic view of the subject.]
It turns out that non-commutative probability can be modeled using operator algebras such as -algebras, von Neumann algebras, or algebras of bounded operators on a Hilbert space, with the latter being accomplished via the Gelfand-Naimark-Segal construction. We will discuss some of these models here, but just as probability theory seeks to abstract away its measure-theoretic models, the philosophy of non-commutative probability is also to downplay these operator algebraic models once some foundational issues are settled.
When one generalises the set of structures in one’s theory, for instance from the commutative setting to the non-commutative setting, the notion of what it means for a structure to be “universal”, “free”, or “independent” can change. The most familiar example of this comes from group theory. If one restricts attention to the category of abelian groups, then the “freest” object one can generate from two generators is the free abelian group of commutative words with , which is isomorphic to the group . If however one generalises to the non-commutative setting of arbitrary groups, then the “freest” object that can now be generated from two generators is the free group of non-commutative words with , which is a significantly larger extension of the free abelian group .
Similarly, when generalising classical probability theory to non-commutative probability theory, the notion of what it means for two or more random variables to be independent changes. In the classical (commutative) setting, two (bounded, real-valued) random variables are independent if one has
whenever are well-behaved functions (such as polynomials) such that all of , vanishes. In the non-commutative setting, one can generalise the above definition to two commuting bounded self-adjoint variables; this concept is useful for instance in quantum probability, which is an abstraction of the theory of observables in quantum mechanics. But for two (bounded, self-adjoint) non-commutative random variables , the notion of classical independence no longer applies. As a substitute, one can instead consider the notion of being freely independent (or free for short), which means that
whenever are well-behaved functions such that all of vanish.
The concept of free independence was introduced by Voiculescu, and its study is now known as the subject of free probability. We will not attempt a systematic survey of this subject here; for this, we refer the reader to the surveys of Speicher and of Biane. Instead, we shall just discuss a small number of topics in this area to give the flavour of the subject only.
The significance of free probability to random matrix theory lies in the fundamental observation that random matrices which are independent in the classical sense, also tend to be independent in the free probability sense, in the large limit . (This is only possible because of the highly non-commutative nature of these matrices; as we shall see, it is not possible for non-trivial commuting independent random variables to be freely independent.) Because of this, many tedious computations in random matrix theory, particularly those of an algebraic or enumerative combinatorial nature, can be done more quickly and systematically by using the framework of free probability, which by design is optimised for algebraic tasks rather than analytical ones.
Much as free groups are in some sense “maximally non-commutative”, freely independent random variables are about as far from being commuting as possible. For instance, if are freely independent and of expectation zero, then vanishes, but instead factors as . As a consequence, the behaviour of freely independent random variables can be quite different from the behaviour of their classically independent commuting counterparts. Nevertheless there is a remarkably strong analogy between the two types of independence, in that results which are true in the classically independent case often have an interesting analogue in the freely independent setting. For instance, the central limit theorem (Notes 2) for averages of classically independent random variables, which roughly speaking asserts that such averages become gaussian in the large limit, has an analogue for averages of freely independent variables, the free central limit theorem, which roughly speaking asserts that such averages become semicircular in the large limit. One can then use this theorem to provide yet another proof of Wigner’s semicircle law (Notes 4).
Another important (and closely related) analogy is that while the distribution of sums of independent commutative random variables can be quickly computed via the characteristic function (i.e. the Fourier transform of the distribution), the distribution of sums of freely independent non-commutative random variables can be quickly computed using the Stieltjes transform instead (or with closely related objects, such as the -transform of Voiculescu). This is strongly reminiscent of the appearance of the Stieltjes transform in random matrix theory, and indeed we will see many parallels between the use of the Stieltjes transform here and in Notes 4.
As mentioned earlier, free probability is an excellent tool for computing various expressions of interest in random matrix theory, such as asymptotic values of normalised moments in the large limit . Nevertheless, as it only covers the asymptotic regime in which is sent to infinity while holding all other parameters fixed, there are some aspects of random matrix theory to which the tools of free probability are not sufficient by themselves to resolve (although it can be possible to combine free probability theory with other tools to then answer these questions). For instance, questions regarding the rate of convergence of normalised moments as are not directly answered by free probability, though if free probability is combined with tools such as concentration of measure (Notes 1) then such rate information can often be recovered. For similar reasons, free probability lets one understand the behaviour of moments as for fixed , but has more difficulty dealing with the situation in which is allowed to grow slowly in (e.g. ). Because of this, free probability methods are effective at controlling the bulk of the spectrum of a random matrix, but have more difficulty with the edges of that spectrum (as well as with related concepts such as the operator norm, Notes 3) as well as with fine-scale structure of the spectrum. Finally, free probability methods are most effective when dealing with matrices that are Hermitian with bounded operator norm, largely because the spectral theory of bounded self-adjoint operators in the infinite-dimensional setting of the large limit is non-pathological. (This is ultimately due to the stable nature of eigenvalues in the self-adjoint setting; see this previous blog post for discussion.) For non-self-adjoint operators, free probability needs to be augmented with additional tools, most notably by bounds on least singular values, in order to recover the required stability for the various spectral data of random matrices to behave continuously with respect to the large limit. We will discuss this latter point in a later set of notes.
I was asked recently (in relation to my recent work with Van Vu on the spectral theory of random matrices) to explain some standard heuristics regarding how the eigenvalues of an matrix A behave under small perturbations. These heuristics can be summarised as follows:
- For normal matrices (and in particular, unitary or self-adjoint matrices), eigenvalues are very stable under small perturbations. For more general matrices, eigenvalues can become unstable if there is pseudospectrum present.
- For self-adjoint (Hermitian) matrices, eigenvalues that are too close together tend to repel quickly from each other under such perturbations. For more general matrices, eigenvalues can either be repelled or be attracted to each other, depending on the type of perturbation.
In this post I would like to briefly explain why these heuristics are plausible.
We now begin our study of measure-preserving systems , i.e. a probability space together with a probability space isomorphism (thus is invertible, with T and both being measurable, and for all and all n). For various technical reasons it is convenient to restrict to the case when the -algebra is separable, i.e. countably generated. One reason for this is as follows:
Exercise 1. Let be a probability space with separable. Then the Banach spaces are separable (i.e. have a countable dense subset) for every ; in particular, the Hilbert space is separable. Show that the claim can fail for . (We allow the spaces to be either real or complex valued, unless otherwise specified.)
Remark 1. In practice, the requirement that be separable is not particularly onerous. For instance, if one is studying the recurrence properties of a function on a non-separable measure-preserving system , one can restrict to the separable sub--algebra generated by the level sets for integer n and rational q, thus passing to a separable measure-preserving system on which f is still measurable. Thus we see that in many cases of interest, we can immediately reduce to the separable case. (In particular, for many of the theorems in this course, the hypothesis of separability can be dropped, though we won’t bother to specify for which ones this is the case.)
We are interested in the recurrence properties of sets or functions . The simplest such recurrence theorem is
Theorem 1. (Poincaré recurrence theorem) Let be a measure-preserving system, and let be a set of positive measure. Then . In particular, has positive measure (and is thus non-empty) for infinitely many n.
(Compare with Theorem 1 of Lecture 3.)
Proof. For any integer , observe that , and thus by Cauchy-Schwarz
The left-hand side of (1) can be rearranged as
On the other hand, . From this one easily obtains the asymptotic
where o(1) denotes an expression which goes to zero as N goes to infinity. Combining (1), (2), (3) and taking limits as we obtain
Remark 2. In classical physics, the evolution of a physical system in a compact phase space is given by a (continuous-time) measure-preserving system (this is Hamilton’s equations of motion combined with Liouville’s theorem). The Poincaré recurrence theorem then has the following unintuitive consequence: every collection E of states of positive measure, no matter how small, must eventually return to overlap itself given sufficient time. For instance, if one were to burn a piece of paper in a closed system, then there exist arbitrarily small perturbations of the initial conditions such that, if one waits long enough, the piece of paper will eventually reassemble (modulo arbitrarily small error)! This seems to contradict the second law of thermodynamics, but the reason for the discrepancy is because the time required for the recurrence theorem to take effect is inversely proportional to the measure of the set E, which in physical situations is exponentially small in the number of degrees of freedom (which is already typically quite large, e.g. of the order of the Avogadro constant). This gives more than enough opportunity for Maxwell’s demon to come into play to reverse the increase of entropy. (This can be viewed as a manifestation of the curse of dimensionality.) The more sophisticated recurrence theorems we will see later have much poorer quantitative bounds still, so much so that they basically have no direct significance for any physical dynamical system with many relevant degrees of freedom.
Exercise 2. Prove the following generalisation of the Poincaré recurrence theorem: if is a measure-preserving system and is non-negative, then .
Exercise 3. Give examples to show that the quantity in the conclusion of Theorem 1 cannot be replaced by any smaller quantity in general, regardless of the actual value of . (Hint: use a Bernoulli system example.)
Exercise 4. Using the pigeonhole principle instead of the Cauchy-Schwarz inequality (and in particular, the statement that if , then the sets cannot all be disjoint), prove the weaker statement that for any set E of positive measure in a measure-preserving system, the set is non-empty for infinitely many n. (This exercise illustrates the general point that the Cauchy-Schwarz inequality can be viewed as a quantitative strengthening of the pigeonhole principle.)
For this lecture and the next we shall study several variants of the Poincaré recurrence theorem. We begin by looking at the mean ergodic theorem, which studies the limiting behaviour of the ergodic averages in various spaces, and in particular in .