# 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.