Tag Archives: probability

Determinantal point processes 2

So, to try to understand these determinantal processes better, let’s take a look at the case when the set \(E\) contains only two points, say \(E=\{x,y\}\).  Then the kernel \(K\) that defines the process is a symmetric \(2\times 2\) matrix, say

\[ K = \left(\begin{array}{cc} a & b \\ b& d \end{array}\right) , \]

and the definition of a determinantal process gives us

\[ {\mathbb P}( x \in {\mathfrak S}) = a, \quad {\mathbb P}( y \in {\mathfrak S}) = d, \quad {\mathbb P}( x,y \in {\mathfrak S}) = ad-b^2 \]

for a random subset \(\mathfrak S\).   From these we can obtain by the inclusion-exclusion principle the exact probabilities of all four subsets of \(E\): the probability of \(E=\{x,y\}\) is \(ad-b^2\), that of \(\{x\}\) is \( a – (ad-b^2)\), that of \(\{y\}\) is \(d-(ad-b^2) \), and finally that of \(\emptyset\) is \( 1-a-d+(ad-b^2) = (1-a)(1-d)-b^2 \).

By construction these four quantities add up to 1, but in order to have a valid probability measure we also require that they all be  non-negative.  What condition will bring this about?

Lemma If the matrix \(K\) is positive and contractive (which is to say that its eigenvalues are \(\le 1\), or equivalently that \(\|K\|\le 1\) then the four quantities above are non-negative (and thus we have a determinantal probability measure).

Proof Let the eigenvalues be \(\lambda,\mu \in [0,1]\).  The probabilities defined above are, respectively, \(\lambda \mu, a-\lambda\mu, d-\lambda\mu, (1-\lambda)(1-\mu)\).  The first and fourth quantities are obviously non-negative, and the second and third are as well since \(a,d\) lie in the closed interval whose endpoints are \(\lambda\) and \(\mu\).

Conversely suppose that all the named quantities are strictly positive.  Since \(a,d>0\) are convex combinations of \(\lambda,\mu\), at least one eigenvalue is positive.  The determinant is positive, so they have the same sign, hence they are both positive.  Since also \((1-\lambda)(1-\mu)> 0 \) the eigenvalues are either both less than 1 or both greater than 1.  They can’t both be greater than one or else their sum \(a+d\) would be greater than 2 and therefore one of \(a,d\) would be greater than 1.

Thus at least in the \(2\times 2\) case we have established that determinantal measures are defined by positive contractions.  Of course this is very ad hoc.  To proceed more generally we need to use exterior algebra – topic for the next post.

 

Determinantal point processes

I went to a talk by Russ Lyons of Indiana this morning.  The subject, an intriguing one to me, was the relationship between costs and \(\ell^2\) Betti numbers in the context of discrete groups.  In the course of the discussion, though, the notion of determinantal process showed up, and I wanted to get acquainted with that.  Russ has an article about the generalities of this idea (referenced below) and there is also a nice blog post by Terry Tao.

Let \(E\) be a set (at most countable for now).  We’re interested in probability measures on the set of all subsets of \(E\) – in the jargon of probability theory, such a measure is called a point process on \(E\).  For example, one such measure is given by fixing a probability \(p\) and then determining independently, with probability \(p\), whether each \(e\in E\) is or is not a member of a random subset.  This is called the Bernoulli process with the given probability.

Suppose a point process is given, and let \(\mathfrak S\) denote a random subset of \(E\) for that process. We are interested in the finite marginals of the process: these are the probabilities

\[ {\mathbb P}( e_1,\ldots,e_k \in {\mathfrak S}) \]

for finite subsets \( \{e_1,\ldots,e_k\} \) of \(E\).  (In terms of measure theory, these are the measures of the cylinder subsets of the power set of \(E\).)  For example, the marginals of the Bernoulli process are just \(p^k\).

Definition: We say that the process is determinantal if there is a symmetric positive kernel \(K\) on \(E\) such that the finite marginals are given by determinants, as follows,

\[ {\mathbb P}( e_1,\ldots,e_k \in {\mathfrak S}) = \det \bigl( K(e_i,e_j)_{i,j=1,\ldots,k} \bigr) \]

For example, the Bernoulli process is determinantal.  The corresponding \(K\) just has entries \(p\) down the diagonal, and zeroes elsewhere.

Lyons establishes a correspondence between determinantal processes on \(E\) and positive contractions on the Hilbert space \(\ell^2(E)\).   Taking contractions related to the combinatorial Laplacian of a graph then produces processes related to random spanning trees.

“Determinantal Processes.”   Accessed October 24. http://terrytao.wordpress.com/2009/08/23/determinantal-processes/.

Lyons, Russell. 2003. “Determinantal Probability Measures.” Publications Mathématiques De l’Institut Des Hautes Études Scientifiques 98 (1): 167–212. doi:10.1007/s10240-003-0016-0.