Determinantal point process explained

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,^[1] machine learning,^[2] and wireless network modeling.^{[3] [4] [5]}

Introduction

Intuition

Consider some positively charged particles confined in a 1-dimensional box

. Due to electrostatic repulsion, the locations of the charged particles are negatively correlated. That is, if one particle is in a small segment , then that makes the other particles less likely to be in the same set. The strength of repulsion between two particles at locations can be characterized by a function .

Formal definition

Let

be a locally compact Polish space and be a Radon measure on . In most concrete applications, these are Euclidean space with its Lebesgue measure. A kernel function is a measurable function .

We say that

is a determinantal point process on with kernel if it is a simple point process on with a joint intensity or correlation function (which is the density of its factorial moment measure) given by

for every n ≥ 1 and x₁, ..., x_n ∈ Λ.^[6]

Properties

Existence

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: $$\backslash rho\_k(x\_,\; \backslash ldots,\; x\_)\; =\; \backslash rho\_k(x\_1,\; \backslash ldots,\; x\_k)\backslash quad\; \backslash forall\; \backslash sigma\; \backslash in\; S\_k,\; k$$
• Positivity: For any N, and any collection of measurable, bounded functions k = 1, ..., N with compact support: If $$\backslash varphi\_0\; +\; \backslash sum\_^N\; \backslash sum\_\; \backslash varphi\_k(x\_\; \backslash ldots\; x\_)\backslash ge\; 0\; \backslash textk,(x\_i)\_^k$$ Then ^[7] $$\backslash varphi\_0\; +\; \backslash sum\_^N\; \backslash int\_\; \backslash varphi\_k(x\_1,\; \backslash ldots,\; x\_k)\backslash rho\_k(x\_1,\backslash ldots,x\_k)\backslash ,\backslash textrmx\_1\backslash cdots\backslash textrmx\_k\; \backslash ge0\; \backslash text\; k,\; (x\_i)\_^k$$

Uniqueness

A sufficient condition for the uniqueness of a determinantal random process with joint intensities ρ_k is$$\backslash sum\_^\backslash infty\; \backslash left(\backslash frac\; \backslash int\_\; \backslash rho\_k(x\_1,\backslash ldots,x\_k)\; \backslash ,\; \backslash textrmx\_1\backslash cdots\backslash textrmx\_k\; \backslash right)^\; =\; \backslash infty$$for every bounded Borel ^[7]

Examples

Gaussian unitary ensemble

The eigenvalues of a random m × m Hermitian matrix drawn from the Gaussian unitary ensemble (GUE) form a determinantal point process on

with kernel

where

is the th oscillator wave function defined by

$$\backslash psi\_k(x)=\; \backslash fracH\_k(x)\; e^$$

and

is the th Hermite polynomial.^[8]

Airy process

The Airy process has kernel function$$K^(x,\; y)=\backslash frac$$where

is the Airy function. This process arises from rescaled eigenvalues near the spectral edge of the Gaussian Unitary Ensemble. It was introduced in 1992.^[9]

Poissonized Plancherel measure

The poissonized Plancherel measure on integer partition (and therefore on Young diagramss) 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

+ with the discrete Bessel kernel, given by:

$$K(x,y)\; =\backslash begin\backslash sqrt\; \backslash ,\; \backslash dfrac$$

-

y

& \text xy >0,\\[12pt]\sqrt \, \dfrac & \text xy <0,\end where$$k\_+(x,y)\; =\; J\_(2\backslash sqrt)J\_(2\backslash sqrt)\; -\; J\_(2\backslash sqrt)J\_(2\backslash sqrt),$$$$k\_-(x,y)\; =\; J\_(2\backslash sqrt)J\_(2\backslash sqrt)\; +\; J\_(2\backslash sqrt)J\_(2\backslash sqrt)$$For J the Bessel function of the first kind, and θ the mean used in poissonization.^[10]

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).^[7]

Uniform spanning trees

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.^[11] Then the uniformly random spanning tree of G is a determinantal point process on E, with kernel

.^[6]

References

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

Notes and References

1. Book: Vershik. Anatoly M.. Asymptotic combinatorics with applications to mathematical physics a European mathematical summer school held at the Euler Institute, St. Petersburg, Russia, July 9-20, 2001. 2003. Springer. Berlin [etc.]. 978-3-540-44890-7. 151.
2. Kulesza. Alex. Taskar. Ben. Determinantal Point Processes for Machine Learning. Foundations and Trends in Machine Learning. 5. 2–3. 2012. 123–286. 10.1561/2200000044. 1207.6083.
3. Miyoshi. Naoto. Shirai. Tomoyuki. A Cellular Network Model with Ginibre Configured Base Stations. Advances in Applied Probability. 46. 3. 2016. 832–845. 0001-8678. 10.1239/aap/1409319562. free.
4. Torrisi. Giovanni Luca. Leonardi. Emilio. Large Deviations of the Interference in the Ginibre Network Model. Stochastic Systems. 4. 1. 2014. 173–205. 1946-5238. 10.1287/13-SSY109. free.
5. N. Deng, W. Zhou, and M. Haenggi. The Ginibre point process as a model for wireless networks with repulsion. IEEE Transactions on Wireless Communications, vol. 14, pp. 107-121, Jan. 2015.
6. Hough, J. B., Krishnapur, M., Peres, Y., and Virág, B., Zeros of Gaussian analytic functions and determinantal point processes. University Lecture Series, 51. American Mathematical Society, Providence, RI, 2009.
7. A. Soshnikov, Determinantal random point fields. Russian Math. Surveys, 2000, 55 (5), 923–975.
8. B. Valko. Random matrices, lectures 14–15. Course lecture notes, University of Wisconsin-Madison.
9. Tracy . Craig A. . Widom . Harold . January 1994 . Level-spacing distributions and the Airy kernel . Communications in Mathematical Physics . en . 159 . 1 . 151–174 . 10.1007/BF02100489 . 0010-3616.
10. A. Borodin, A. Okounkov, and G. Olshanski, On asymptotics of Plancherel measures for symmetric groups, available via .
11. Lyons, R. with Peres, Y., Probability on Trees and Networks. Cambridge University Press, In preparation. Current version available at http://mypage.iu.edu/~rdlyons/