The Julia Language

April 18th, 2014 2 comments

The Julia Language

I played a bit this spring with Julia (the software, not the girl next door ;-). For Debian : apt-get install julia julia-doc. This was the source of great enthusiasm! Julia is a promising software for scientific computing. Yet another interpreter around Lapack? Yes and no. Some people believe that Julia is a revolution in scientific computing. For most of my daily needs, Julia is already almost preferable to Matlab/Octave/Scilab/R/C++/Python/… due to multiple bleeding edge technical features, including a high performance just-in-time compiler. Julia is flexible like Matlab, is fast like C, is free software like Octave/Scilab/R (MIT license), is text friendly like Python, and much more. Julia is also good for its competitors: it will help them to evolve. The reading of «Why we created Julia» by the creators of Julia is informative. An impressive summary of Julia features is given on julialang.org, which provides many resources, including videos featuring the great Alan Edelman (MIT group leader, co-creator of Julia).

Learning Julia is a pretty easy task. Here is one of my first Julia program:

Pkg.add("Winston") # Pkg.add("Winston") is needed once for all.
using Winston # for simple graphics à la Matlab
n = 1000;
(D,U) = eig((randn(n,n)+im*randn(n,n))/sqrt(2*n));
I = [-1:.01:1]; J = sqrt(1-I.^2);
hold(true)
plot(real(D),imag(D),"b.",I,J,"r--",I,-J,"r--")
title(@sprintf("Complex Ginibre Ensemble %dx%d",n,n))
file("circ.png")

(this is my standard test: Ginibre ensemble!) which produces the following image: Ginibre with JuliaJulia is still young – born in 2012, version 0.2 – and needs time to gain maturity, notably for plotting support among other things. One can regret the lack of a graphical user interface, but one can use Emacs+ESS, or the wonderful IPython notebooks in web browser via the Julia package IJulia. For Debian: apt-get install ess ipython-notebook. Give it a try!

 

Share
Categories: Computers

Random walks on regular graphs

April 5th, 2014 No comments

Cayley graph of the free group F2

We will see in this post how the arcsine law appears naturally in the combinatorics of paths of the simple random walk on \( {\mathbb{Z}} \), while the Wigner semicircle law appears naturally in the asymptotic analysis (over the degree) of the combinatorics of paths in regular trees, in relation with free groups. The link with free probability and random matrices might be the subject of further posts.

Counting paths on graphs. Let \( {G=(V,E)} \) be a graph with set of vertices \( {V} \), and set of edges \( {E\subset\{\{v,w\}:v\neq w\in V\}} \). We assume that \( {V} \) is at most countable, that \( {E} \) is non empty, and that each vertex has positive and finite degree: for any \( {v\in V} \),

\[ d_v=\sum_{w\in V}\mathbf{1}_{\{v,w\}\in E}\in(0,\infty). \]

We may consider the Hilbert space

\[ \ell^2_{\mathbb{C}}(V) =\left\{x:V\rightarrow\mathbb{C}\mbox{ with }\sum_{v\in V}|x_v|^2<\infty\right\}. \]

To any \( {x\in\ell^2_{\mathbb{C}}(V)} \) we associate a complex measure \( {\sum_{v\in V}x_v\delta_v} \). We have \( {\langle\delta_v,\delta_w\rangle=\mathbf{1}_{v=w}} \) and we say that \( {{(\delta_v)}_{v\in V}} \) is the canonical basis of \( {\ell^2_{\mathbb{C}}(V)} \). The scalar product is

\[ \langle x,y\rangle =\sum_{v,w\in V}x_v\overline{y_w}\langle\delta_v,\delta_w\rangle =\sum_{v\in V}x_v\overline{y_v}. \]

The adjacency operator of \( {G} \) is \( {A:\ell^2_{\mathbb{C}}(V)\rightarrow \ell^2_{\mathbb{C}}(V)} \) defined for every \( {v,w\in V} \) by

\[ \langle A\delta_w,\delta_v\rangle=\mathbf{1}_{\{v,w\}\in E}. \]

Note that \( {A} \) is well defined since \( {\|A\delta_v\|^2=\langle A\delta_v,\delta_v\rangle=d_v<\infty} \) for any \( {v\in V} \). For any \( {m\in\mathbb{N}} \), we denote by \( {A^m=A\circ\cdots\circ A} \) the \( {m} \)-th power of \( {A} \). For every vertices \( {v,w\in V} \) the number of paths in \( {G} \) of length \( {m} \) starting at \( {v} \) and ending at \( {w} \) is

\[ \langle A^m\delta_v,\delta_w\rangle =\sum_{\substack{u_0,\ldots,u_m\in V\\v=u_0,u_m=w}} \mathbf{1}_{\{u_0,u_1\}\in E}\cdots\mathbf{1}_{\{u_{m-1},u_m\}\in E}. \]

Simple random walk on graphs. Let \( {G=(V,E)} \) be as above. The simple random walk \( {X={(X_t)}_{t\in\mathbb{N}}} \) on \( {G} \) is the Markov chain with state space \( {V} \) and transition kernel \( {P:V\times V\mapsto[0,1]} \) given for any \( {v,w\in V} \) by

\[ P(v,w) =\mathbb{P}(X_{n+1}=w|X_n=v) =\frac{\mathbf{1}_{\{v,w\}\in E}}{d_v}. \]

The measure \( {\mu} \) on \( {V} \) associated to the degree sequence \( {{(d_v)}_{v\in V}} \) of \( {G} \), defined by \( {\mu(v)=d_v} \) for every \( {v\in V} \), is symmetric with respect to the kernel \( {P} \): for every \( {v,w\in V} \),

\[ \mu(v)P(v,w)=\mu(w)P(w,v). \]

Suppose now that \( {G} \) is regular, meaning that \( {{(d_v)}_{v\in V}} \) is constant and say equal to some \( {d>1} \). Then \( {\mu} \) is proportional to the counting measure, and \( {P} \) is doubly stochastic. Conditional on \( {\{X_0=v\}} \), for every \( {m\in\mathbb{N}} \), the law of the random path \( {(X_0=v,X_1,\ldots,X_m)} \) is uniform on the set of paths of length \( {m} \) starting at \( {v} \). It follows that for every \( {v\in V} \) and every \( {m\in\mathbb{N}} \),

\[ \mathbb{P}(X_m=v|X_0=v) =P^m(v,v) =\frac{\langle A^m\delta_v,\delta_v\rangle}{d^m}, \]

and it follows then from Markov chains theory that the random walk \( {X} \), which is irreducible, is recurrent (null recurrent if \( {V} \) is infinite) if and only if for some (thus every) \( {v\in V} \)

\[ \sum_{m\in\mathbb{N}} \frac{\langle A^m\delta_v,\delta_v\rangle}{d^m} =\infty. \]

One can compute \( {\langle A^m\delta_v,\delta_v\rangle} \) with some combinatorics for certain nice regular graphs.

Counting paths on square lattices. Let us compute \( {\langle A^m\delta_v,\delta_v\rangle} \) when \( {G} \) is the usual square lattice of dimension \( {n\geq1} \), which is the Cayley graph of the commutative group \( {(\mathbb{Z}^n,+)} \). In this case \( {G} \) is regular of even degree \( {d=2n} \). In this graph \( {G} \), the quantity \( {\langle A^m\delta_v,\delta_v\rangle} \) does not depend on \( {v} \) and is equal to zero if \( {m} \) is odd. When \( {m} \) is even, we may replace \( {m} \) by \( {2m} \) for convenience. Thanks to the commutativity, one can, for each path, group the increments by type. This makes the combinatorics multinomial (encodes the outcomes of a dice of \( {2n} \) faces thrown \( {2m} \) times): place \( {2m} \) balls in \( {2n} \) boxes labeled \( {+e_1,-e_1,\ldots,+e_n,-e_n} \) in such a way that the boxes \( {+e_i} \) and \( {-e_i} \) contain the same number of balls, for each \( {1\leq i\leq n} \):

\[ \langle A^{2m}\delta_0,\delta_0\rangle =\sum_{\substack{0\leq m_1,\ldots,m_n\leq m\\m_1+\cdots+m_n=m}}\binom{2m}{m_1,m_1,\ldots,m_n,m_n} =\sum_{\substack{0\leq m_1,\ldots,m_n\leq m\\m_1+\cdots+m_n=m}}\frac{(2m)!}{m_1!^2\cdots m_n!^2}. \]

When \( {n=1} \) then the formula boils down to the central binomial coefficient

\[ \langle A^{2m}\delta_0,\delta_0\rangle\overset{n=1}{=}\binom{2m}{m}. \]

When \( {n=2} \) then by the Vandermonde convolution formula for binomial coefficients,

\[ \langle A^{2m}\delta_0,\delta_0\rangle\overset{n=2}{=}\frac{(2m)!}{m!^2}\sum_{0\leq k\leq m} \binom{m}{k}\binom{m}{m-k}=\frac{(2m)!}{m!^2}\binom{2m}{m}=\frac{(2m)!^2}{m!^4}. \]

More generally, one may seek for compact formulas for any \( {n\geq1} \) in the same spirit. Beyond the example of square lattices, it turns out that one can compute \( {\langle A^m\delta_v,\delta_v\rangle} \) for other examples of regular graphs, such as for instance regular trees.

Counting paths on regular trees. For any integer \( {d\geq2} \), the regular tree \( {T_d=(V,E)} \) is the graph with infinite countable number of vertices, without cycles, and in which each vertex has exactly \( {d} \) neighbors. If \( {d} \) is even with \( {d=2n} \) then \( {T_d=T_{2n}} \) is the Cayley graph of the free group \( {\mathbb{F}_n} \) (see below), in particular \( {T_2} \) is the Cayley graph of \( {\mathbb{Z}} \). Let us pick a vertex \( {\varnothing} \) in \( {T_d} \), and call it the root. In the case \( {d=2n} \) it is customary to identify \( {\varnothing} \) with the neutral element of the free group \( {\mathbb{F}_n} \) (which is \( {0} \) if \( {n=1} \), and the empty string if \( {n>1} \), see below for details).

Let us denote by \( {A_d} \) the adjacency operator of our regular tree \( {T_d} \). Recall that \( {\langle A_d^m\delta_v,\delta_v\rangle} \) is the number of paths in the graph \( {T_d} \), of length \( {m} \), starting and ending at \( {\varnothing} \). As for square lattices, the quantity \( {\langle A_d^m\delta_v,\delta_v\rangle} \) does not depend on \( {v\in V} \), and is equal in particular to \( {\langle A_d^m \delta_\varnothing,\delta_\varnothing\rangle} \), and is equal to zero if \( {m} \) is odd. We have

\[ \langle A_d^m\delta_\varnothing,\delta_\varnothing\rangle =\int\!x^m\,\mu_{d}(dx) \]

for any \( {m\in\mathbb{N}} \), where \( {\mu_{d}} \) is the Kesten-McKay distribution given by

\[ \mu_{d}(dx) =\frac{d\sqrt{4(d-1)-x^2}}{2\pi(d^2-x^2)} \mathbf{1}_{[-2\sqrt{d-1},2\sqrt{d-1}]}(x)dx. \]

In other words, the number of paths of length \( {m} \) in \( {T_d} \), starting and ending at \( {\varnothing} \), is given by the \( {m} \)-th moment of the probability distribution \( {\mu_{d}} \). A proof relies on the Carleman moments condition for the existence of the probability measure, and on the inversion of the Cauchy-Stieltjes transform to get the formula for the density. Experts may note by the way that the probability distribution \( {\mu_{d}} \) is nothing else but the so-called spectral distribution with respect to vector \( {\delta_\varnothing} \) of the symmetric operator \( {A_d} \) (actually with respect to any canonical vector \( {\delta_v} \), \( {v\in V} \), thanks to symmetries!).

When \( {d=2} \) then \( {T_2} \) is the Cayley graph of \( {F_1=\mathbb{Z}} \) and the corresponding Kesten-McKay distribution \( {\mu_{2}} \) is the arcsine distribution on \( {[-2,2]} \): for every integer \( {m\geq1} \),

\[ \langle A_d^{2m}\delta_\varnothing,\delta_\varnothing\rangle =\int\!x^{2m}\,\mu_{2}(dx) =\int_{-2}^2\frac{x^{2m}}{\pi\sqrt{4-x^2}}dx =\binom{2m}{m} \]

and we recover that the number of paths of length \( {2m} \) in \( {\mathbb{Z}} \) starting and ending at the root \( {\varnothing} \) (which is the origin \( {0} \)) is given by the central binomial coefficient:

\[ \langle A_d^{2m}\delta_\varnothing,\delta_\varnothing\rangle =\binom{2m}{m}. \]

At the opposite side of degree, when \( {d\rightarrow\infty} \) then \( {\mu_{d}} \), scaled by \( {(d-1)^{-1/2}} \), tends to the semicircle distribution on \( {[-2,2]} \) (also known as the Wigner or the Sato-Tate distribution): for every integer \( {m\geq1} \),

\[ \begin{array}{rcl} \lim_{d\rightarrow\infty} \frac{\langle A_d^{2m}\delta_\varnothing,\delta_\varnothing\rangle}{(d-1)^m} &=&\lim_{d\rightarrow\infty}\int\!\left(\frac{x}{\sqrt{d-1}}\right)^{2m}\,\mu_{d}(dx)\\ &=&\lim_{d\rightarrow\infty}\frac{d}{2\pi}\int_{-2\sqrt{d-1}}^{2\sqrt{d-1}}\! \left(\frac{x}{\sqrt{d-1}}\right)^{2m} \frac{\sqrt{4(d-1)-x^2}}{d^2-x^2}\,dx\\ &=&\lim_{d\rightarrow\infty}\frac{d}{2\pi}\int_{-2}^2\!y^{2m}\frac{\sqrt{4(d-1)-(d-1)y^2}}{d^2-(d-1)y^2}\,\sqrt{d-1}dy\\ &=&\int_{-2}^2 y^{2m}\frac{\sqrt{4-y^2}}{2\pi}dy\\ &=&\frac{1}{1+m}\binom{2m}{m}. \end{array} \]

This quantity \( {C_m=\frac{1}{1+m}\binom{2m}{m}} \) is nothing else but the \( {m} \)-th Catalan number. Taking \( {d=2n} \), this says that the number of paths of length \( {2m} \) in the free group \( {\mathbb{F}_n} \) starting and ending at the root \( {\varnothing} \) is equivalent, as \( {n\rightarrow\infty} \), to \( {(2n-1)^mC_m} \):

\[ \langle A_{2n}^{2m}\delta_\varnothing,\delta_\varnothing\rangle \sim_{n\rightarrow\infty}(2n)^m\frac{1}{m+1}\binom{2m}{m}. \]

Tensor products versus free products. There are two natural multivariate generalizations of the group \( {(\mathbb{Z},+)} \). The first one is the commutative group \( {(\mathbb{Z}^n,+)=(\mathbb{Z},+)^{\otimes n}} \), obtained by tensor product, for which the Cayley graph is the usual square lattice. The second one is the less known free group \( {\mathbb{F}_n=(\mathbb{Z},+)^{\boxplus n}} \) which is non commutative if \( {n>1} \), but for which the Cayley graph is a tree like for \( {\mathbb{Z}} \) and unlike for \( {\mathbb{Z}^n} \) with \( {n>1} \). The Cayley graphs of \( {\mathbb{Z}^n} \) and \( {\mathbb{F}_n} \) are both infinite and \( {(2n)} \)-regular. One should not confuse the free group \( {\mathbb{F}_n} \) with the finite field \( {\mathbf{F}_q} \).

  • Commutative universe: \( {\mathbb{Z}^n} \), tensor product of \( {n} \) copies of \( {\mathbb{Z}} \)
    • Regular square lattice, presence of cycles
    • Central binomial coefficients and arcsine distribution
  • Non commutative universe: \( {\mathbb{F}_n} \), free product of \( {n>1} \) copies of \( {\mathbb{Z}} \)
    • Regular tree, absence of cycles
    • Catalan numbers and semicircle distribution (only as \( {n\rightarrow\infty} \)).

Free product and free group. If \( {G_1,\ldots,G_n} \) are at most countable groups, then their free product \( {G} \) is the group of finite strings (words) written using as letters the element of the disjoint union of \( {G_1,\ldots,G_n} \). The sole simplifications in these strings are the ones coming from the group operation in each \( {G_1,\ldots,G_n} \). The group operation in \( {G} \) is the concatenation of strings, and the neutral element is the empty string \( {\varnothing} \). If \( {G_1,\ldots,G_n} \) are finitely generated then \( {G} \) is also finitely generated and one may use the generators of \( {G_1,\ldots,G_n} \) as letters to construct the elements of \( {G} \). The free group \( {\mathbb{F}_n} \) is the free product of \( {n} \) copies of \( {(\mathbb{Z},+)} \). It is customary to use the multiplicative notation. Namely, let \( {n\geq1} \) be an integer and let

\[ S=\{e_1,\ldots,e_n,e_1^{-1},\ldots,e_n^{-1}\} \]

be a set of \( {2n} \) distinct letters. The notation will make sense in the sequel. The free group \( {\mathbb{F}_n} \) with \( {n} \) generators is constituted by all the finite words (strings of letters) written with the letters of \( {S} \), with the simplification rules

\[ e_i e_i^{-1} = e_i^{-1} e_i = \varnothing \]

for every \( {1\leq i\leq d} \), where \( {\varnothing} \) denotes the empty string. For any \( {a_1\cdots a_p} \) and \( {b_1\cdots b_q} \) in \( {\mathbb{F}_n} \), with \( {a_1,\ldots,a_p,b_1,\ldots,b_q} \) in \( {S} \), the group operation consists first to concatenate the strings into \( {a_1\cdots a_p b_1\cdots b_q} \), and then to simplify using the simplification rules. This operation is not commutative if \( {n>1} \). The empty word \( {\varnothing} \) is the neutral element. With multiplicative notation, we have \( {(e_i)^{-1}=e_i^{-1}} \) and \( {(e_i^{-1})^{-1}=e_i} \) and \( {(a_1\cdots a_p)^{-1}=a_p^{-1}\cdots a_1^{-1}} \). We say that \( {S} \) is a generating set of \( {\mathbb{F}_n} \), and that the element of \( {S} \) are generators. Every element \( {a} \) of \( {\mathbb{F}_n} \) with \( {a\neq\varnothing} \) can be written as

\[ a=a_1\cdots a_p \]

with \( {p\geq1} \) and \( {a_1,\ldots,a_p\in S} \) and \( {a_{i+1}\neq a_i^{-1}} \) for every \( {1\leq i\leq p-1} \). The term free comes from the fact that the sole relations are due to the group structure. There are no extra relations. The free group is infinite and non commutative if \( {n>1} \). Every finitely generated group is isomorphic to the quotient of a free group by extra relations. Note that \( {F_1} \) is isomorphic to \( {(\mathbb{Z},+)} \) and \( {S=\{\pm e_1\}} \), while for \( {d>1} \) the group \( {(\mathbb{Z}^d,+)} \) is isomorphic to the quotient of \( {F_d} \) with the extra relations which are the commutation relations between the generators \( {S=\{\pm e_i:1\leq i\leq d\}} \). The group \( {(\mathbb{Z}^d,+)} \) can be seen from this perspective as the free commutative group. The notation \( {e_i} \) matches the standard notation for the canonical basis of \( {\mathbb{Z}^d} \).

Cayley graph. The (left) Cayley graph of \( {\mathbb{F}_n} \) has vertices \( {V=\mathbb{F}_n} \) and edges

\[ E=\{\{h,k\}\subset V:kh^{-1}\in S\}=\{\{h,sh\}:h\in V,s\in S\}. \]

We say left since we multiply from the left by elements of \( {S} \) in order to produce edges. This graph is actually a rooted infinite \( {2n} \)-regular tree, in which the root \( {\varnothing} \) has \( {2n} \) children while each other vertex has exactly \( {1} \) parent and \( {2n-1} \) children. Note that \( {F_1} \) is isomorphic to \( {\mathbb{Z}} \), and its Cayley graph is a doubly infinite chain. In \( {\mathbb{Z}^n} \), \( {n>1} \), the commutation relations produce cycles, which are not present in \( {\mathbb{F}_n} \).

The set \( {\mathbb{F}_n} \) is a metric space for the natural distance \( {\mathrm{dist}} \) on its Cayley graph: \( {\mathrm{dist}(a,b)} \) is the length of the shortest path from \( {a} \) to \( {b} \) in the graph, for any \( {a,b\in \mathbb{F}_n} \). Let us denote by \( {|a|} \) the length of the word \( {a} \) after simplification, in other words we have \( {a=c_1\cdots c_{|a|}} \) where \( {c_1,\ldots,c_{|a|}\in S} \) and \( {c_i\neq c_i^{-1}} \) for any \( {1\leq i<|a|} \). Then \( {\mathrm{dist}(\varnothing,a)=|a|} \) and \( {\mathrm{dist}(a,b)=|a^{-1}b|} \). The distance is invariant by translation in the sense that \( {\mathrm{dist}(ac,bc)=\mathrm{dist}(a,b)} \) for any \( {a,b,c\in \mathbb{F}_n} \).

Random walk again. The random walk on \( {\mathbb{F}_n} \) is the random walk on the Cayley graph of \( {\mathbb{F}_n} \). At each step, it multiplies its position in \( {\mathbb{F}_n} \), from the left, by a random letter chosen uniformly in \( {S} \). For any \( {t\geq0} \) and \( {h,k\in \mathbb{F}_n} \),

\[ P(h,k) :=\mathbb{P}(X_{t+1}=k\,|\,X_t=h) =\frac{\mathbf{1}_{\{h,k\}\in E}}{|S|} =\frac{\mathbf{1}_{kh^{-1}\in S}}{2n} \]

where \( {E} \) is the set of edges of the Cayley graph of \( {\mathbb{F}_n} \). For any \( {m\geq1} \), let us consider

\[ P^m(h,k):=\mathbb{P}(X_m=k\,|\,X_0=h), \]

The law of the random walk is translation invariant: for every \( {h,k\in \mathbb{F}_n} \),

\[ P^m(h,k)=p^m(\varnothing,kh^{-1}). \]

In particular the diagonal of \( {P^m} \) is constant: \( {P^m(h,h)} \) does not depend on \( {h} \). Let \( {A_{2n}} \) be the adjacency operator of the Cayley graph of \( {\mathbb{F}_n} \) which is the regular tree of degree \( {d=2n} \) (see above). For every \( {m\geq0} \), we get from our preceding analysis that

\[ P^{m}(\varnothing,\varnothing) =\frac{\langle A_{2n}^m\delta_\varnothing,\delta_\varnothing\rangle}{(2n)^{m}}. \]

We know that \( {P^{m}(\varnothing,\varnothing)=0} \) if \( {m} \) is odd. If \( {m} \) is even, we may replace \( {m} \) by \( {2m} \) for convenience. If \( {n=1} \) then \( {F_1=\mathbb{Z}} \) is commutative and

\[ P^{2m}(\varnothing,\varnothing) \overset{n=1}{=}\frac{1}{2^{2m}}\binom{2m}{m}. \]

In contrast, if \( {n>1} \) then \( {\mathbb{F}_n} \) is no longer commutative, and by the Kesten-McKay formula,

\[ P^{2m}(\varnothing,\varnothing) \sim_{n\rightarrow\infty} \frac{(2n)^m}{(2n)^{2m}}C_m=\frac{C_m}{(2n)^m} \]

where \( {C_m=\frac{1}{1+m}\binom{2m}{m}} \) is the \( {m} \)-th Catalan number.

Notes. The Kesten-McKay distribution was obtained by Harry Kesten (1931 – ) in his doctoral thesis (35p., entitled Symmetric random walks on groups, published in 1959 in Transactions of the AMS), in the special case of the random walk on the Cayley graph of the free group. A modern presentation lifted to regular trees can be found in the book by Hora and Obata (theorem 4.4). The cumulative distribution of the Kesten-McKay distribution \( {\mu_d} \) has a nice expression: for any \( {u\in(-2\sqrt{d-1},2\sqrt{d-1})} \),

\[ \begin{array}{rcl} \mu_d((-\infty,u)) &=&\int_{-2\sqrt{d-1}}^u\!\frac{d\sqrt{4(d-1)-x^2}}{2\pi(d^2-x^2)}\,dx \\ &=&\frac{1}{2}+\frac{d}{2\pi} \left[\arcsin\frac{u}{2\sqrt{d-1}}-\frac{d-2}{d}\arctan\frac{(d-2)u}{d\sqrt{4(d-1)-u^2}} \right]. \end{array} \]

It has been shown by Brendan McKay (1951 – ) in his 1981 paper The Expected Eigenvalue Distribution of Large Regular Graphs that if \( {{(G_n)}_{n\geq1}} \) is a sequence of finite regular graphs with fixed degree \( {d\geq2} \) such that

  • the number of vertices \( {|G_n|} \) satisfies \( {\lim_{n\rightarrow\infty}|G_n|=\infty} \);
  • the number \( {k} \)-cycles \( {C_k(G_n)} \) in \( {G_n} \) satisfies \( {\lim_{n\rightarrow\infty}\frac{C_k(G_n)}{|G_n|}=0} \) for any \( {k\geq3} \);

then the empirical distribution of the eigenvalues of the adjacency matrix of \( {G_n} \) tends weakly to \( {\mu_d} \) as \( {n\rightarrow\infty} \). Moreover if \( {G} \) is a random regular graph drawn from the uniform distribution on regular graphs with degree \( {d} \) and \( {n} \) vertices, then the expected spectral distribution of the adjacency matrix of \( {G} \) tends weakly as \( {n\rightarrow\infty} \) to \( {\mu_d} \). The proof of McKay is based on the method of moments. At the very end of his paper, McKay says that his work can be connected to the statistical theory of random walks but does not cite explicitly the work of Kesten.

Share

De la Vallée Poussin on Uniform Integrability

March 9th, 2014 No comments
Charles Jean de la Vallée-Poussin

Charles de la Vallée-Poussin.

« La Belgique, victime de cruelles violences, a rencontré, dans ses épreuves, de grands et de nombreux témoignages de sympathie. L’Université de Louvain en a recueilli sa part. Ses professeurs, dispersés après le désastre de la ville, ont été invités dans des Universités étrangères. Beaucoup y ont trouvé un asile, quelques-uns même la possibilité de poursuivre leur enseignement. Ainsi, j’ai été appelé a faire des conférences à l’Université Harvard en Amérique l’année dernière, puis cette année au Collège de France. Le présent volume contient la matière des Leçons que j’ai faites au Collège de France entre décembre 1915 et mars 1916. Il est, après bien d’autres, un modeste souvenir de ces événements. … Une partie des résultats établis dans cet article se trouvaient dans la troisième édition du Tome II de mon Cours d’Analyse, qui était sous presse lors de l’incendie de Louvain. Les Allemands ont brulé cet ouvrage : toutes les installations de mon éditeur ont, en effet, partagé le sort de la bibliothèque de l’Université. … » Charles de la Vallée Poussin in Intégrales de Lebesgue, fonctions d’ensemble, classes de Baire, Leçons professées au Collège de France (1916). Excerpt from the introduction.

This post is devoted to some probabilistic aspects of uniform integrability, a basic concept that I like very much. Let \( {\Phi} \) be the class of non-decreasing functions \( {\varphi:\mathbb{R}_+\rightarrow\mathbb{R}_+} \) such that

\[ \lim_{x\rightarrow+\infty}\frac{\varphi(x)}{x}=+\infty. \]

This class contains for instance the convex functions \( {x\mapsto x^p} \) with \( {p>1} \) and \( {x\mapsto x\log(x)} \). Let us fix a probability space \( {(\Omega,\mathcal{A},\mathbb{P})} \), and denote by \( {L^\varphi} \) the set of random variables \( {X} \) such that \( {\varphi(|X|)\in L^1=L^1((\Omega,\mathcal{F},\mathbb{P}),\mathbb{R})} \). We have \( {L^\varphi\subsetneq L^1} \). Clearly, if \( {{(X_i)}_{i\in I}\subset L^1} \) is bounded in \( {L^\varphi} \) with \( {\varphi\in\Phi} \) then \( {{(X_i)}_{i\in I}} \) is bounded in \( {L^1} \).

Uniform integrability. For any family \( {{(X_i)}_{i\in I}\subsetneq L^1} \), the following three properties are equivalent. When one (and thus all) of these properties holds true, we say that the family \( {{(X_i)}_{i\in I}} \) is uniformly integrable (UI). The first property can be seen as a natural definition of uniform integrability.

  1. (definition of UI) \( {\lim_{x\rightarrow+\infty}\sup_{i\in I}\mathbb{E}(|X_i|\mathbf{1}_{|X_i|\geq x})=0} \);
  2. (epsilon-delta) \( {\forall\varepsilon>0} \), \( {\exists\delta>0} \), \( {\forall A\in\mathcal{F}} \), \( {\mathbb{P}(A)\leq\delta\Rightarrow\sup_{i\in I}\mathbb{E}(|X_i|\mathbf{1}_A)\leq\varepsilon} \);
  3. (de la Vallée Poussin) there exists \( {\varphi\in\Phi} \) such that \( {\sup_{i\in I}\mathbb{E}(\varphi(|X_i|))<\infty} \).

The second property is often referred to as the “epsilon-delta” criterion. The third and last property is a boundedness in \( {L^\varphi\subsetneq L^{1}} \) and is due to Charles-Jean Étienne Gustave Nicolas de la Vallée Poussin (1866 – 1962), a famous Belgian mathematician, also well known for his proof of the prime number theorem.

Proof of \( {1\Rightarrow2} \). By assumption, for any \( {\varepsilon>0} \), there exists \( {x_\varepsilon} \) such that \( {\sup_{i\in I}\mathbb{E}(|X_i|\mathbf{1}_{|X_i|\geq x})\leq\varepsilon} \) for any \( {x\geq x_\varepsilon} \). If \( {\mathbb{P}(A)\leq \delta_\varepsilon:=\varepsilon/x_\varepsilon} \) then for any \( {i\in I} \),

\[ \mathbb{E}(|X_i|\mathbf{1}_A) =\mathbb{E}(|X_i|\mathbf{1}_{|X_i|<x_\varepsilon}\mathbf{1}_A) +\mathbb{E}(|X_i|\mathbf{1}_{|X_i|\geq x_\varepsilon}\mathbf{1}_A) \leq x_\varepsilon\mathbb{P}(A)+\varepsilon\leq 2\varepsilon. \]

Proof of \( {2\Rightarrow1} \). By assumption, for any \( {\varepsilon>0} \) there exist \( {\delta>0} \) such that if \( {\Omega=B_1\cup\cdots\cup B_n} \) is a covering of \( {\Omega} \) such that \( {\max_{1\leq k\leq n}\mathbb{P}(B_k)\leq\delta} \), then

\[ \sup_{i\in I}\mathbb{E}(|X_i|)\leq\sup_{i\in I}\sum_{k=1}^n\mathbb{E}(|X_i|\mathbf{1}_{B_k})\leq n\varepsilon<\infty \]

i.e. \( {{(X_i)}_{i\in I}} \) is bounded in \( {L^1} \). Thus, for every \( {j\in I} \), if \( {A:=A_j:=\{|X_j|\geq x\}} \), then, by the Markov inequality, \( {\mathbb{P}(A)\leq x^{-1}\sup_{i\in I}\mathbb{E}(|X_i|)\leq \delta} \) for \( {x} \) large enough, uniformly in \( {j\in I} \), and the assumption gives \( {\lim_{x\rightarrow+\infty}\sup_{i,j\in I}\mathbb{E}(|X_i|\mathbf{1}_{|X_j|\geq x})=0} \).

Proof of \( {3\Rightarrow1} \). For any \( {\varepsilon>0} \), since \( {\varphi\in\Phi} \), by definition of \( {\Phi} \) there exists \( {x_\varepsilon\geq0} \) such that \( {x\leq\varepsilon \varphi(x)} \) for every \( {x\geq x_\varepsilon} \), and therefore

\[ \sup_{i\in I}\mathbb{E}(|X_i|\mathbf{1}_{|X_i|\geq x_\varepsilon}) \leq \varepsilon\sup_{i\in I}\mathbb{E}(\varphi(|X_i|)\mathbf{1}_{|X_i|\geq x_\varepsilon}) \leq \varepsilon\sup_{i\in I}\mathbb{E}(\varphi(|X_i|)). \]

Proof of \( {1\Rightarrow 3} \). Let us seek for a piecewise linear function \( {\varphi} \) of the form

\[ \varphi(x)=\int_0^x\varphi'(t)dt \quad\mbox{with}\quad \varphi'=\sum_{n=1}^\infty u_n\mathbf{1}_{[n,n+1[} \quad\mbox{and}\quad u_n=\sum_{m\geq1}\mathbf{1}_{x_m\leq n} \]

for a sequence \( {{(x_m)}_{m\geq1}\nearrow+\infty} \) to be constructed. We have \( {\varphi\in\Phi} \) since \( {\lim_{n\rightarrow\infty}u_n=+\infty} \). Moreover, since \( {\varphi\leq\sum_{n=1}^\infty(u_1+\cdots+u_n)\mathbf{1}_{[n,n+1[}} \), we get, for any \( {i\in I} \),

\[ \begin{array}{rcl} \mathbb{E}(\varphi(|X_i|)) &\leq& \sum_{n=1}^\infty (u_1+\cdots+u_n)\mathbb{P}(n\leq |X_i|<n+1) \\ &=& \sum_{n=1}^\infty u_n\mathbb{P}(|X_i|\geq n)\\ &=& \sum_{m\geq1}\sum_{n\geq x_m}\mathbb{P}(|X_i|\geq n)\\ &=& \sum_{m\geq1}\sum_{n\geq x_m}n\mathbb{P}(n\leq |X_i|<n+1)\\ &\leq & \sum_{m\geq1}\mathbb{E}(|X_i|\mathbf{1}_{|X_i|\geq x_m})\\ &\overset{*}{\leq} & \sum_{m\geq1}2^{-m}<\infty \end{array} \]

where \( {\overset{*}{\leq}} \) holds if for every \( {m} \) we select \( {x_m} \) such that \( {\sup_{i\in I}\mathbb{E}(|X_i|\mathbf{1}_{|X_i|\geq x_m})\leq 2^{-m}} \), which is allowed by assumption (we may replace \( {2^{-m}} \) by anything sumable in \( {m} \)).

This achieves the proof of the equivalence of the three properties: \( {1\Leftrightarrow 2\Leftrightarrow 3} \).

Convexity and moderate growth. In the de la Vallée Poussin criterion, one can always assume that the function \( {\varphi} \) is convex (in particular continuous), with moderate growth in the sense that for every \( {x\geq0} \),

\[ \varphi(x)\leq x^2. \]

Indeed, the construction of \( {\varphi} \) that we gave above provides a function \( {\varphi} \) with piecewise constant and \( {\geq0} \) derivative, thus the function is convex (it is a Young function). Following Paul-André Meyer, to derive the moderate growth property, we may first observe that thanks to the way we constructed \( {\varphi} \), for every \( {x\geq0} \),

\[ \varphi'(2x)\leq c\varphi'(x) \]

where one can take \( {c=2} \). This follows from the fact that we have the freedom to take the \( {x_m} \)’s as large as we want, for instance in such a way that for every \( {n\geq1} \),

\[ u_{2n}\leq u_n+\sum_{m\geq1}\mathbf{1}_{n<x_m\leq 2n}\leq 2u_n. \]

Consequently, the function \( {\varphi} \) itself has also moderate growth since, denoting \( {C:=2c} \),

\[ \varphi(2x)=\int_0^{2x}\!g(u)\,du=\int_0^x\!g(2t)\,2dt\leq 2c\varphi(x)=C\varphi(x). \]

Now \( {\varphi(x)\leq C^{1+k}\varphi(2^{-k}x)} \) for any \( {k\geq1} \), and taking \( {k=k_x=\lceil\log_2(x)\rceil} \) we obtain

\[ \varphi(x)\leq C^2C^{\log_2(x)}\varphi(1)=C^2\varphi(1)2^{\log_2(C)\log_2(x)}=C^2\varphi(1)x^{\log_2(C)}. \]

Since one can take \( {c=2} \) we get \( {C=4} \), which allows \( {\varphi(x)\leq x^2} \) by scaling.

Examples of UI families.

  • Any finite subset of \( {L^1} \) is UI;
  • More generally, if \( {\sup_{i\in I}|X_i|\in L^1} \) (domination: \( {|X_i|\leq X} \) for every \( {i\in I} \), with \( {X\in L^1} \)) then \( {{(X_i)}_{i\in I}} \) is UI. To see it, we may first observe that the singleton family \( {\{\sup_{i\in I}|X_i|\}} \) is UI, and thus, by the de la Vallée Poussin criterion, there exists \( {\varphi\in\Phi} \) such that \( {\varphi(\sup_{i\in I}|X_i|)\in L^1} \), and therefore

    \[ \sup_{i\in I}\mathbb{E}(\varphi(|X_i|))\leq\mathbb{E}(\sup_{i\in I}\varphi(|X_i|))\leq\mathbb{E}(\varphi(\sup_{i\in I}|X_i|))<\infty, \]

    which implies, by the de la Vallée Poussin criterion again, that \( {{(X_i)}_{i\in I}} \) is UI;

  • If \( {\mathcal{U}_1\subset L^1,\ldots,\mathcal{U}_n\subset L^1} \) is a finite collection of UI families then the union \( {\mathcal{U}_1\cup\cdots\cup\mathcal{U}_n} \) is UI, and also the vector span \( {\mathrm{span}(\mathcal{U}_1\cup\cdots\cup\mathcal{U}_n)} \) is UI.
  • If \( {{(X_n)}_{n\geq1},X\in L^1} \) and \( {X_n\overset{L^1}{\rightarrow} X} \) then \( {{(X_n)}_{n\geq1}\cup\{X\}} \) is UI and \( {{(X_n-X)}_{n\geq1}} \) is UI. To see it, for any \( {\varepsilon>0} \), we first select \( {n} \) large enough such that \( {\sup_{k\geq n}\mathbb{E}(|X_k-X|)\leq\varepsilon} \), and then \( {\delta>0} \) with the epsilon-delta criterion for the finite family \( {\{X_1,\ldots,X_n\}} \), which gives, for any \( {A\in\mathcal{F}} \) such that \( {\mathbb{P}(A)\leq\delta} \),

    \[ \sup_{n\geq1}\mathbf{E}(|X_n-X|\mathbf{1}_A) \leq \max\left(\max_{1\leq k\leq n}\mathbf{E}(|X_k-X|\mathbf{1}_A) ; \sup_{k\geq n}\mathbf{E}(|X_k-X|) \right) \leq \varepsilon. \]

  • The de la Vallée Poussin criterion is often used with \( {\varphi(x)=x^2} \), and means in this case that every bounded subset of \( {L^2} \) is UI.

Integrability. The de la Vallée Poussin criterion, when used with a singleton UI family \( {\{X\}} \), states that \( {X\in L^1} \) implies that \( {\varphi(|X|)\in L^1} \) for some \( {\varphi\in\Phi} \). In other words, for every random variable, integrability can always be improved in a sense. There is not any paradox here since \( {\varphi} \) depends actually on \( {X} \). Topologically, integrability is in a sense an open statement rather than a closed statement. An elementary instance of this phenomenon is visible for Riemann series, in the sense that if \( {\sum_{n\geq1}n^{-s}<\infty} \) for some \( {s>0} \) then \( {\sum_{n\geq1}n^{-s’}<\infty} \) for some \( {s’<s} \), because the convergence condition of the series is “\( {s>1} \)”, which is an open condition.

Dominated convergence. For any \( {{(X_n)}_{n\geq1},X\in L^1} \), we have

\[ X_n\overset{ L^1}{\rightarrow}X \quad\text{if and only if}\quad X_n\overset{\mathbb{P}}{\rightarrow}X \text{ and } {(X_n)}_{n\geq1}\text{ is UI}. \]

This can be seen as an improved dominated convergence theorem (since \( {{(X_n)}_{n\geq1}} \) is UI when \( {\sup_n|X_n|\in L^1} \)). The proof may go as follows. We already know that if \( {X_n\rightarrow X} \) in \( {L^1} \) then \( {X_n\rightarrow X} \) in probability (Markov inequality) and \( {{(X_n)}_{n\geq1}\cup\{X\}} \) is UI (see above). Conversely, if \( {X_n\rightarrow X} \) in probability and \( {{(X_n)}_{n\geq1}} \) is UI, then \( {{(X_n-X)}_{n\geq1}} \) is UI since \( {X\in L^1} \), and thus, using the convergence in probability and the epsilon-delta criterion, we obtain that for any \( {\varepsilon>0} \) and large enough \( {n} \),

\[ \mathbb{E}(|X_n-X|) =\mathbb{E}(|X_n-X|\mathbf{1}_{|X_n-X|\geq\varepsilon}) +\mathbb{E}(|X_n-X|\mathbf{1}_{|X_n-X|<\varepsilon}) \leq 2\varepsilon. \]

Martingales. The American mathematician Joseph Leo Doob (1910 – 2004) has shown that if a sub-martingale \( {{(M_n)}_{n\geq1}} \) is bounded in \( {L^1} \) then there exists \( {M_\infty\in L^1} \) such that \( {M_n\rightarrow M_\infty} \) almost surely. Moreover, in the case of martingales, this convergence holds also in \( {L^1} \) if and only if \( {{(M_n)}_{n\geq1}} \) is UI. In the same spirit, and a bit more precisely, if \( {{(M_n)}_{n\geq1}} \) is a martingale for a filtration \( {{(\mathcal{F}_n)}_{n\geq1}} \), then the following two properties are equivalent:

  • \( {{(M_n)}_{n\geq1}} \) is UI;
  • \( {{(M_n)}_{n\geq1}} \) is closed, meaning that there exists \( {M_\infty\in L^1} \) such that \( {M_n=\mathbb{E}(M_\infty|\mathcal{F}_n)} \) for all \( {n\geq1} \), and moreover \( {M_n\rightarrow M_\infty} \) almost surely and in \( {L^1} \).

Are there non UI martingales? Yes, but they are necessarily unbounded: \( {\sup_{n\geq0}|M_n|\not\in L^1} \), otherwise we may apply dominated convergence. A nice counter example is given by critical Galton-Watson branching process, defined recursively by \( {M_0=1} \) and

\[ M_{n+1}=X_{n+1,1}+\cdots+X_{n+1,M_n}, \]

where \( {X_{n+1,j}} \) is the number of offspring of individual \( {j} \) in generation \( {n} \), and \( {{(X_{j,k})}_{j,k\geq1}} \) are i.i.d. random variables on \( {\mathbb{N}} \) with law \( {\mu} \) of mean \( {1} \) and such that \( {\mu(0)>0} \). The sequence \( {{(M_n)}_{n\geq1}} \) is a non-negative martingale, and thus it converges almost surely to some \( {M_\infty\in L^1} \). It is also a Markov chain with state space \( {\mathbb{N}} \). The state \( {0} \) is absorbing and all the remaining states can lead to \( {0} \) and are thus transient. It follows then that almost surely, either \( {{(M_n)}_{n\geq0}} \) converges to \( {0} \) or to \( {+\infty} \), and since \( {M_\infty \in L^1} \), it follows that \( {M_\infty=0} \). However, the convergence cannot hold in \( {L^1} \) since this leads to the contradiction \( {1=\mathbb{E}(M_n)\rightarrow\mathbb{E}(M_\infty)=0} \) (note that \( {{(M_n)}_{n\geq1}} \) is bounded in \( {L^1} \)).

Topology. The Dunford-Pettis theorem, due to the American mathematicians Nelson James Dunford (1906 – 1986) and Billy James Pettis (1913 – 1979), states that for every family \( {{(X_i)}_{i\in I}\in L^1} \), the following propositions are equivalent.

  • \( {{(X_i)}_{i\in I}} \) is UI;
  • \( {{(X_i)}_{i\in I}} \) is relatively compact for the weak \( {\sigma(L^1,L^\infty)} \) topology;
  • \( {{(X_i)}_{i\in I}} \) is relatively sequentially compact for the weak \( {\sigma(L^1,L^\infty)} \) topology.

The proof, which is not given in this post, can be found for instance in Delacherie and Meyer or in Diestel. We just recall that a sequence \( {{(X_n)}_{n\geq1}} \) in \( {L^1} \) converges to \( {X\in L^1} \) for the weak \( {\sigma(L^1,L^\infty)} \) topology when \( {\lim_{n\rightarrow\infty}\ell(X_n)=\ell(X)} \) for every \( {\ell\in (L^1)’=L^\infty} \), in other words when \( {\lim_{n\rightarrow\infty}\mathbb{E}(YX_n)=\mathbb{E}(YX)} \) for every \( {Y\in L^\infty} \).

The Dunford-Pettis theorem opens the door for the fine analysis of closed (possibly linear) subsets of \( {L^1} \), a deep subject in functional analysis and Banach spaces.

Tightness. If \( {{(X_i)}_{i\in I}\subset L^1} \) is bounded in \( {L^\varphi} \) for \( {\varphi:\mathbb{R}_+\rightarrow\mathbb{R}_+} \) non-decreasing and such that \( {\lim_{x\rightarrow\infty}\varphi(x)=+\infty} \), then the Markov inequality gives

\[ \sup_{i\in I}\mathbb{P}(|X_i|\geq R)\leq \frac{\sup_{i\in I}\mathbb{E}(\varphi(|X_i|))}{\varphi(R)}\underset{R\rightarrow\infty}{\longrightarrow0} \]

and thus the family of distributions \( {{(\mathbb{P}_{X_i})}_{i \in I}} \) is tight, in the sense that for every \( {\varepsilon>0} \), there exists a compact subset \( {K_\varepsilon} \) of \( {\mathbb{R}} \) such that \( {\sup_{i\in I}\mathbb{P}(|X_i|\in K_\varepsilon)\geq 1-\varepsilon} \). The Prohorov theorem states that tightness is equivalent to being relatively compact for the narrow topology (which is by the way metrizable by the bounded-Lipschitz Fortet-Mourier distance). The Prohorov and the Dunford-Pettis theorems correspond to different topologies on different objects (distributions or random variables). The tightness of \( {{(\mathbb{P}_{X_i})}_{i\in I}} \) is strictly weaker than the UI of \( {{(X_i)}_{i\in I}} \).

UI functions with respect to a family of laws. The UI property for a family \( {{(X_i)}_{i\in I}\subset L^1} \) depends actually only on the marginal distributions \( {{(\mathbb{P}_{X_i})}_{i\in I}} \) and does not feel the dependence between the \( {X_i} \)’s. In this spirit, if \( {(\eta_i)_{i\in I}} \) is a family of probability measures on a Borel space \( {(E,\mathcal{E})} \) and if \( {f:E\rightarrow\mathbb{R}} \) is a Borel function then we say that \( {f} \) is UI for \( {(\eta_i)_{i\in I}} \) on \( {E} \) when

\[ \lim_{t\rightarrow\infty}\sup_{i\in I}\int_{\{|f|>t\}}\!|f|\,d\eta_i=0. \]

This means that \( {{(f(X_i))}_{i\in I}} \) is UI, where \( {X_i\sim\eta_i} \) for every \( {i\in I} \). This property is often used in applications as follows: if \( {\eta_n\rightarrow\eta} \) narrowly as \( {n\rightarrow\infty} \) for some probability measures \( {{(\eta_n)}_{n\geq1}} \) and \( {\eta} \) and if \( {f} \) is continuous and UI for \( {(\eta_n)_{n\geq1}} \) then

\[ \int\!|f|\,d\eta<\infty \quad\text{and}\quad \lim_{n\rightarrow\infty}\int\!f\,d\eta_n=\int\!f\,d\eta. \]

Logarithmic potential. What follows is extracted from the survey Around the circular law (random matrices). We have already devoted a previous post to the logarithmic potential. Let \( {\mathcal{P}(\mathbb{C})} \) be the set of probability measures on \( {\mathbb{C}} \) which integrate \( {\log\left|\cdot\right|} \) in a neighborhood of infinity. The logarithmic potential \( {U_\mu} \) of \( {\mu\in\mathcal{P}(\mathbb{C})} \) is the function \( {U_\mu:\mathbb{C}\rightarrow(-\infty,+\infty]} \) defined for all \( {z\in\mathbb{C}} \) by

\[ U_\mu(z)=-\int_{\mathbb{C}}\!\log|z-w|\,d\mu(w) =-(\log\left|\cdot\right|*\mu)(z). \]

Let \( {\mathcal{D}’(\mathbb{C})} \) be the set of Schwartz-Sobolev distributions on \( {\mathbb{C}} \). We have \( {\mathcal{P}(\mathbb{C})\subset\mathcal{D}’(\mathbb{C})} \). Since \( {\log\left|\cdot\right|} \) is Lebesgue locally integrable on \( {\mathbb{C}} \), the Fubini-Tonelli theorem implies that \( {U_\mu} \) is a Lebesgue locally integrable function on \( {\mathbb{C}} \). In particular, we have \( {U_\mu<\infty} \) almost everywhere and \( {U_\mu\in\mathcal{D}’(\mathbb{C})} \). By using Green’s or Stockes’ theorems, one may show, for instance via the Cauchy-Pompeiu formula, that for any smooth and compactly supported function \( {\varphi:\mathbb{C}\rightarrow\mathbb{R}} \),

\[ -\int_{\mathbb{C}}\!\Delta\varphi(z)\log|z|\,dxdy=2\pi\varphi(0) \]

where \( {z=x+iy} \). Now can be written, in \( {\mathcal{D}’(\mathbb{C})} \),

\[ \Delta\log\left|\cdot\right| = 2\pi\delta_0 \]

In other words, \( {\frac{1}{2\pi}\log\left|\cdot\right|} \) is the fundamental solution of the Laplace equation on \( {\mathbb{R}^2} \). Note that \( {\log\left|\cdot\right|} \) is harmonic on \( {\mathbb{C}\setminus\{0\}} \). It follows that in \( {\mathcal{D}’(\mathbb{C})} \),

\[ \Delta U_\mu=-2\pi\mu, \]

i.e. for every smooth and compactly supported “test function” \( {\varphi:\mathbb{C}\rightarrow\mathbb{R}} \),

\[ \langle\Delta U_\mu,\varphi\rangle_{\mathcal{D}'} =-\!\int_{\mathbb{C}}\!\Delta\varphi(z)U_\mu(z)\,dxdy =-2\pi\int_{\mathbb{C}}\!\varphi(z)\,d\mu(z) =-\langle2\pi\mu,\varphi\rangle_{\mathcal{D}'} \]

where \( {z=x+iy} \). Also \( {-\frac{1}{2\pi}U_\cdot} \) is the Green operator on \( {\mathbb{R}^2} \) (Laplacian inverse). For every \( {\mu,\nu\in\mathcal{P}(\mathbb{C})} \), we have

\[ U_\mu=U_\nu\text{ almost everywhere }\Rightarrow \mu=\nu. \]

To see it, since \( {U_\mu=U_\nu} \) in \( {\mathcal{D}’(\mathbb{C})} \), we get \( {\Delta U_\mu=\Delta U_\nu} \) in \( {\mathcal{D}’(\mathbb{C})} \), and thus \( {\mu=\nu} \) in \( {\mathcal{D}’(\mathbb{C})} \), and finally \( {\mu=\nu} \) as measures since \( {\mu} \) and \( {\nu} \) are Radon measures. (Note that this remains valid if \( {U_\mu=U_\nu+h} \) for some harmonic \( {h\in\mathcal{D}’(\mathbb{C})} \)). As for the Fourier transform, the pointwise convergence of logarithmic potentials along a sequence of probability measures implies the narrow convergence of the sequence to a probability measure. We need however some strong tightness. More precisely, if \( {{(\mu_n)}_{n\geq1}} \) is a sequence in \( {\mathcal{P}(\mathbb{C})} \) and if \( {U:\mathbb{C}\rightarrow(-\infty,+\infty]} \) is such that

  • (i) for a.a. \( {z\in\mathbb{C}} \), \( { \lim_{n\rightarrow\infty}U_{\mu_n}(z)=U(z)} \);
  • (ii) \( {\log(1+\left|\cdot\right|)} \) is UI for \( {(\mu_n)_{n \geq 1}} \);

then there exists \( {\mu \in \mathcal{P}(\mathbb{C})} \) such that

  • (j) \( {U_\mu=U} \) almost everywhere;
  • (jj) \( {\mu = -\frac{1}{2\pi}\Delta U} \) in \( {\mathcal{D}’(\mathbb{C})} \);
  • (jjj) \( {\mu_n\rightarrow\mu} \) narrowly.

Let us give a proof inspired from an article by Goldsheid and Khoruzhenko on random tridiagonal matrices. From the de la Vallée Poussin criterion, assumption (ii) implies that for every real number \( {r\geq1} \), there exists \( {\varphi\in\Phi} \), which may depend on \( {r} \), which is moreover convex and has moderate growth \( {\varphi(x)\leq 1+x^2} \), and

\[ \sup_n \int\!\varphi(\log(r+|w|))\,d\mu_{n}(w)<\infty. \]

Let \( {K\subset \mathbb{C}} \) be an arbitrary compact set. Take \( {r = r(K) \geq 1} \) large enough so that the ball of radius \( {r-1 } \) contains \( {K} \). Therefore for every \( {z\in K} \) and \( {w\in\mathbb{C}} \),

\[ \varphi(|\log|z-w||) \leq (1 + |\log|z-w||^2)\mathbf{1}_{\{|w|\leq r\}} +\varphi(\log(r+|w|))\mathbf{1}_{\{|w|>r\}}. \]

The couple of inequalities above, together with the local Lebesgue integrability of \( {(\log\left|\cdot\right|)^2} \) on \( {\mathbb{C}} \), imply, by using Jensen and Fubini-Tonelli theorems,

\[ \sup_n\int_K\!\varphi(|U_n(z)|)\,dxdy \leq \sup_n\iint\!\mathbf{1}_K(z)\varphi(|\log|z-w||)\,d\mu_n(w)\,dxdy<\infty, \]

where \( {z=x+iy} \) as usual. Since the de la Vallée Poussin criterion is necessary and sufficient for UI, this means that the sequence \( {{(U_{\mu_n})}_{n\geq1}} \) is locally Lebesgue UI. Consequently, from (i) it follows that \( {U} \) is locally Lebesgue integrable and that \( {U_{\mu_n}\rightarrow U} \) in \( {\mathcal{D}’(\mathbb{C})} \). Since the differential operator \( {\Delta} \) is continuous in \( {\mathcal{D}’(\mathbb{C})} \), we find that \( {\Delta U_{\mu_n}\rightarrow\Delta U} \) in \( {\mathcal{D}’(\mathbb{C})} \). Since \( {\Delta U\leq0} \), it follows that \( {\mu:=-\frac{1}{2\pi}\Delta U} \) is a measure (see e.g. Hormander). Since for a sequence of measures, convergence in \( {\mathcal{D}’(\mathbb{C})} \) implies narrow convergence, we get \( {\mu_n=-\frac{1}{2\pi}\Delta U_{\mu_n}\rightarrow\mu=-\frac{1}{2\pi}\Delta U} \) narrowly, which is (jj) and (jjj). Moreover, by assumptions (ii) we get additionally that \( {\mu\in\mathcal{P}(\mathbb{C})} \). It remains to show that \( {U_\mu=U} \) almost everywhere Indeed, for any smooth and compactly supported \( {\varphi:\mathbb{C}\rightarrow\mathbb{R}} \), since the function \( {\log\left|\cdot\right|} \) is locally Lebesgue integrable, the Fubini-Tonelli theorem gives

\[ \int\!\varphi(z)U_{\mu_n}(z)\,dz =-\int\!\left(\int\!\varphi(z)\log|z-w|\,dz\right)\,d\mu_n(w). \]

Now \( {\varphi*\log\left|\cdot\right|:w\in\mathbb{C}\mapsto\int\!\varphi(z)\log|z-w|\,dz} \) is continuous and is \( {\mathcal{O}(\log|1+\cdot|)} \). Therefore, by (i-ii), \( {U_{\mu_n}\rightarrow U_\mu} \) in \( {\mathcal{D}’(\mathbb{C})} \), thus \( {U_\mu=U} \) in \( {\mathcal{D}’(\mathbb{C})} \) and then almost everywhere, giving (j).

Share
Categories: Analysis, Probability

Octave 3.8 in Debian with GUI and JIT

March 6th, 2014 2 comments
GNU Octave 3.8 GUI

GNU Octave 3.8 QT GUI in Gnome 3.8 (Debian)

 

Which software do you use for your numerical experiments? I am used to use GNU Octave for pure numerics, even if I play sometimes with Scilab, Python, GNU R, and Maxima for algebraics. Many people do not like Octave because it is command line oriented. Regarding these aspects, I was delighted to discover the quite exciting message below when updating my Debian distribution today. At long last, GNU Octave 3.8 comes with native QT GUI and JIT compiler. Give it a try!

octave (3.8.0~rc1-1) experimental; urgency=medium

* Starting with this version, the octave package now contains an
experimental graphical user interface (GUI) based on the Qt toolkit.
That GUI can be started by running the `octave-gui’ executable, or by
giving the `–force-gui’ option to the octave binary.

* For those who want to keep the lower memory footprint of a pure text
interface, there is the `octave-cli’ executable which is not linked
against Qt.

* Starting with this version, Octave incorporates a just-in-time (JIT)
compiler, which can offer performance improvements in some situations.
Since it is still experimental, the JIT is disabled by default, but
you can activate it with the `jit_enable’ command.

Share
Categories: Computers