Determinantal point process

In mathematics, a determinantal point process is a stochastic point process, the probability distribution of which is characterized as a determinant of some function. They are suited for modelling global negative correlations, and for efficient algorithms of sampling, marginalization, conditioning, and other inference tasks. Such processes arise as important tools in random matrix theory, combinatorics, physics, machine learning, and wireless network modeling.

Consider some positively charged particles confined in a 1-dimensional box ${\displaystyle [-1,+1]}$. Due to electrostatic repulsion, the locations of the charged particles are negatively correlated. That is, if one particle is in a small segment ${\displaystyle [x,x+\delta x]}$, then that makes the other particles less likely to be in the same set. The strength of repulsion between two particles at locations ${\displaystyle x,x'}$can be characterized by a function ${\displaystyle K(x,x')}$.

Let ${\displaystyle \Lambda }$be a locally compact Polish space and ${\displaystyle \mu }$be a Radon measure on ${\displaystyle \Lambda }$. In most concrete applications, these are Euclidean space ${\displaystyle \mathbb {R} ^{n}}$with its Lebesgue measure. A kernel function is a measurable function ${\displaystyle K:\Lambda ^{2}\to \mathbb {C} }$.

We say that ${\displaystyle X}$is a determinantal point process on ${\displaystyle \Lambda }$with kernel ${\displaystyle K}$if it is a simple point process on ${\displaystyle \Lambda }$with a joint intensity or correlation function (which is the density of its factorial moment measure) given by

${\displaystyle \rho _{n}(x_{1},\ldots ,x_{n})=\det[K(x_{i},x_{j})]_{1\leq i,j\leq n}}$

for every n ≥ 1 and x₁, ..., x_n ∈ Λ.

The following two conditions are necessary and sufficient for the existence of a determinantal random point process with intensities ρ_k.

• Symmetry: ρ_k is invariant under action of the symmetric group S_k. Thus: $${\displaystyle \rho _{k}(x_{\sigma (1)},\ldots ,x_{\sigma (k)})=\rho _{k}(x_{1},\ldots ,x_{k})\quad \forall \sigma \in S_{k},k}$$
• Positivity: For any N, and any collection of measurable, bounded functions ${\displaystyle \varphi _{k}:\Lambda ^{k}\to \mathbb {R} }$, k = 1, ..., N with compact support:
  If $${\displaystyle \varphi _{0}+\sum _{k=1}^{N}\sum _{i_{1}\neq \cdots \neq i_{k}}\varphi _{k}(x_{i_{1}}\ldots x_{i_{k}})\geq 0{\text{ for all }}k,(x_{i})_{i=1}^{k}}$$Then $${\displaystyle \varphi _{0}+\sum _{k=1}^{N}\int _{\Lambda ^{k}}\varphi _{k}(x_{1},\ldots ,x_{k})\rho _{k}(x_{1},\ldots ,x_{k})\,{\textrm {d}}x_{1}\cdots {\textrm {d}}x_{k}\geq 0{\text{ for all }}k,(x_{i})_{i=1}^{k}}$$

A sufficient condition for the uniqueness of a determinantal random process with joint intensities ρ_k is $${\displaystyle \sum _{k=0}^{\infty }\left({\frac {1}{k!}}\int _{A^{k}}\rho _{k}(x_{1},\ldots ,x_{k})\,{\textrm {d}}x_{1}\cdots {\textrm {d}}x_{k}\right)^{-{\frac {1}{k}}}=\infty }$$for every bounded Borel A ⊆ Λ.

The eigenvalues of a random m × m Hermitian matrix drawn from the Gaussian unitary ensemble (GUE) form a determinantal point process on ${\displaystyle \mathbb {R} }$with kernel

${\displaystyle K_{m}(x,y)=\sum _{k=0}^{m-1}\psi _{k}(x)\psi _{k}(y)}$

where ${\displaystyle \psi _{k}(x)}$is the ${\displaystyle k}$th oscillator wave function defined by

$${\displaystyle \psi _{k}(x)={\frac {1}{\sqrt {{\sqrt {2n}}n!}}}H_{k}(x)e^{-x^{2}/4}}$$

and ${\displaystyle H_{k}(x)}$is the ${\displaystyle k}$th Hermite polynomial.

The Airy process is governed by the so called extended Airy kernel which is a generalization of the Airy kernel function$${\displaystyle K^{\mathrm {Ai} }(x,y)={\frac {\operatorname {Ai} (x)\operatorname {Ai} ^{\prime }(y)-\operatorname {Ai} (y)\operatorname {Ai} ^{\prime }(x)}{x-y}}}$$where ${\displaystyle \operatorname {Ai} }$is the Airy function. This process arises from rescaled eigenvalues near the spectral edge of the Gaussian Unitary Ensemble.

The poissonized Plancherel measure on integer partition (and therefore on Young diagrams) plays an important role in the study of the longest increasing subsequence of a random permutation. The point process corresponding to a random Young diagram, expressed in modified Frobenius coordinates, is a determinantal point process on ${\displaystyle \mathbb {Z} }$+

$${\displaystyle K(x,y)={\begin{cases}{\sqrt {\theta }}\,{\dfrac {k_{+}(|x|,|y|)}{|x|-|y|}}&{\text{if }}xy>0,\\[12pt]{\sqrt {\theta }}\,{\dfrac {k_{-}(|x|,|y|)}{x-y}}&{\text{if }}xy<0,\end{cases}}}$$where $${\displaystyle k_{+}(x,y)=J_{x-{\frac {1}{2}}}(2{\sqrt {\theta }})J_{y+{\frac {1}{2}}}(2{\sqrt {\theta }})-J_{x+{\frac {1}{2}}}(2{\sqrt {\theta }})J_{y-{\frac {1}{2}}}(2{\sqrt {\theta }}),}$$$${\displaystyle k_{-}(x,y)=J_{x-{\frac {1}{2}}}(2{\sqrt {\theta }})J_{y-{\frac {1}{2}}}(2{\sqrt {\theta }})+J_{x+{\frac {1}{2}}}(2{\sqrt {\theta }})J_{y+{\frac {1}{2}}}(2{\sqrt {\theta }})}$$For J the Bessel function of the first kind, and θ the mean used in poissonization.

This serves as an example of a well-defined determinantal point process with non-Hermitian kernel (although its restriction to the positive and negative semi-axis is Hermitian).

Let G be a finite, undirected, connected graph, with edge set E. Define I^e:E → ℓ²(E) as follows: first choose some arbitrary set of orientations for the edges E, and for each resulting, oriented edge e, define I^e to be the projection of a unit flow along e onto the subspace of ℓ²(E) spanned by star flows. Then the uniformly random spanning tree of G is a determinantal point process on E, with kernel

${\displaystyle K(e,f)=\langle I^{e},I^{f}\rangle ,\quad e,f\in E}$.

• Johansson, Kurt (2006). Course 1 - Random matrices and determinantal processes. Les Houches. Vol. 83. Elsevier. doi:10.1016/s0924-8099(06)80038-7. ISSN 0924-8099.