Determinantal point process

Short description: Stochastic point process in mathematics

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]

## Contents

* 1 Introduction
* 1.1 Intuition
* 1.2 Formal definition
* 2 Properties
* 2.1 Existence
* 2.2 Uniqueness
* 3 Examples
* 3.1 Gaussian unitary ensemble
* 3.2 Airy process
* 3.3 Poissonized Plancherel measure
* 3.4 Uniform spanning trees
* 4 References

## Introduction

### Intuition

Consider some positively charged particles confined in a 1-dimensional box [−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 [x,x+δx], then that makes the other particles less likely to be in the same set. The strength of repulsion between two particles at locations x,x′ can be characterized by a function K(x,x′).

### Formal definition

Let Λ be a locally compact Polish space and μ be a Radon measure on Λ. In most concrete applications, these are Euclidean space ℝn with its Lebesgue measure. A kernel function is a measurable function K:Λ2->ℂ.

We say that X is a determinantal point process on Λ with kernel K 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

ρn(x1,…,xn)=det⁡[K(xi,xj)]1≤i,j≤n

for every n ≥ 1 and x1, ..., xn ∈ Λ.[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 Sk. Thus: ρk(xσ(1),…,xσ(k))=ρk(x1,…,xk)∀σ∈Sk,k
* Positivity: For any N, and any collection of measurable, bounded functions φk:Λk->ℝ, k = 1, ..., N with compact support:

If φ0+∑k=1N∑i1≠⋯≠ikφk(xi1…xik)≥0 for all k,(xi)i=1k Then [7] φ0+∑k=1N∫Λkφk(x1,…,xk)ρk(x1,…,xk)dx1⋯dxk≥0 for all k,(xi)i=1k

### Uniqueness

A sufficient condition for the uniqueness of a determinantal random process with joint intensities ρk is ∑k=0∞(1k!∫Akρk(x1,…,xk)dx1⋯dxk)−1k=∞ for every bounded Borel A ⊆ Λ.[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

Km(x,y)=∑k=0m−1ψk(x)ψk(y)

where ψk(x) is the kth oscillator wave function defined by

ψk(x)=12nn!Hk(x)e−x2/4

and Hk(x) is the kth Hermite polynomial. [8]

### Airy process

Main article: Airy process

The Airy process is governed by the so called extended Airy kernel which is a generalization of the Airy kernel functionKAi(x,y)=Ai⁡(x)Ai′(y)−Ai⁡(y)Ai′(x)x−ywhere Ai is the Airy function. This process arises from rescaled eigenvalues near the spectral edge of the Gaussian Unitary Ensemble.[9]

### Poissonized Plancherel measure

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 ℤ \+ ​1⁄2 with the discrete Bessel kernel, given by:

K(x,y)={θk+(|x|,|y|)|x|−|y|if xy>0,θk−(|x|,|y|)x−yif xy<0, where k+(x,y)=Jx−12(2θ)Jy+12(2θ)−Jx+12(2θ)Jy−12(2θ), k−(x,y)=Jx−12(2θ)Jy−12(2θ)+Jx+12(2θ)Jy+12(2θ) 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 Ie:E → ℓ2(E) as follows: first choose some arbitrary set of orientations for the edges E, and for each resulting, oriented edge e, define Ie to be the projection of a unit flow along e onto the subspace of ℓ2(E) spanned by star flows.[11] Then the uniformly random spanning tree of G is a determinantal point process on E, with kernel

K(e,f)=⟨Ie,If⟩,e,f∈E.[6]

## References

1. ↑ Vershik, Anatoly M. (2003). Asymptotic combinatorics with applications to mathematical physics a European mathematical summer school held at the Euler Institute, St. Petersburg, Russia, July 9-20, 2001. Berlin [etc.]: Springer. p. 151. ISBN 978-3-540-44890-7.
2. ↑ Kulesza, Alex; Taskar, Ben (2012). "Determinantal Point Processes for Machine Learning". Foundations and Trends in Machine Learning 5 (2–3): 123–286. doi:10.1561/2200000044.
3. ↑ Miyoshi, Naoto; Shirai, Tomoyuki (2016). "A Cellular Network Model with Ginibre Configured Base Stations". Advances in Applied Probability 46 (3): 832–845. doi:10.1239/aap/1409319562. ISSN 0001-8678.
4. ↑ Torrisi, Giovanni Luca; Leonardi, Emilio (2014). "Large Deviations of the Interference in the Ginibre Network Model". Stochastic Systems 4 (1): 173–205. doi:10.1287/13-SSY109. ISSN 1946-5238. https://iris.polito.it/bitstream/11583/2525885/2/SSY-2013-109.pdf.
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. ↑ 6.0 6.1 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. ↑ 7.0 7.1 7.2 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" (in en). Communications in Mathematical Physics 159 (1): 151–174. doi:10.1007/BF02100489. ISSN 0010-3616. http://link.springer.com/10.1007/BF02100489.
10. ↑ A. Borodin, A. Okounkov, and G. Olshanski, On asymptotics of Plancherel measures for symmetric groups, available via arXiv:math/9905032.
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/

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

* v
* t
* e

Stochastic processes

Discrete time|

* Bernoulli process
* Branching process
* Chinese restaurant process
* Galton–Watson process
* Independent and identically distributed random variables
* Markov chain
* Moran process
* Random walk
* Loop-erased
* Self-avoiding
* Biased
* Maximal entropy

Continuous time|

* Bessel process
* Birth–death process
* Brownian motion
* Bridge
* Excursion
* Fractional
* Geometric
* Meander
* Cauchy process
* Contact process
* Continuous-time random walk
* Cox process
* Diffusion process
* Empirical process
* Feller process
* Fleming–Viot process
* Gamma process
* Geometric process
* Hunt process
* Interacting particle systems
* Itô diffusion
* Itô process
* Jump diffusion
* Jump process
* Lévy process
* Local time
* Markov additive process
* McKean–Vlasov process
* Ornstein–Uhlenbeck process
* Poisson process
* Compound
* Non-homogeneous
* Point process
* Schramm–Loewner evolution
* Semimartingale
* Sigma-martingale
* Stable process
* Superprocess
* Telegraph process
* Variance gamma process
* Wiener process
* Wiener sausage

Both|

* Branching process
* Galves–Löcherbach model
* Gaussian process
* Hidden Markov model (HMM)
* Markov process
* Martingale
* Differences
* Local
* Sub-
* Super-
* Random dynamical system
* Regenerative process
* Renewal process
* Stochastic chains with memory of variable length
* White noise

Fields and other|

* Dirichlet process
* Gaussian random field
* Gibbs measure
* Hopfield model
* Ising model
* Potts model
* Boolean network
* Markov random field
* Percolation
* Pitman–Yor process
* Point process
* Cox
* Poisson
* Random field
* Random graph

Time series models|

* Autoregressive conditional heteroskedasticity (ARCH) model
* Autoregressive integrated moving average (ARIMA) model
* Autoregressive (AR) model
* Autoregressive–moving-average (ARMA) model
* Generalized autoregressive conditional heteroskedasticity (GARCH) model
* Moving-average (MA) model

Financial models|

* Black–Derman–Toy
* Black–Karasinski
* Black–Scholes
* Chen
* Constant elasticity of variance (CEV)
* Cox–Ingersoll–Ross (CIR)
* Garman–Kohlhagen
* Heath–Jarrow–Morton (HJM)
* Heston
* Ho–Lee
* Hull–White
* LIBOR market
* Rendleman–Bartter
* SABR volatility
* Vašíček
* Wilkie

Actuarial models|

* Bühlmann
* Cramér–Lundberg
* Risk process
* Sparre–Anderson

Queueing models|

* Bulk
* Fluid
* Generalized queueing network
* M/G/1
* M/M/1
* M/M/c

Properties|

* Càdlàg paths
* Continuous
* Continuous paths
* Ergodic
* Exchangeable
* Feller-continuous
* Gauss–Markov
* Markov
* Mixing
* Piecewise deterministic
* Predictable
* Progressively measurable
* Self-similar
* Stationary
* Time-reversible

Limit theorems|

* Central limit theorem
* Donsker's theorem
* Doob's martingale convergence theorems
* Ergodic theorem
* Fisher–Tippett–Gnedenko theorem
* Large deviation principle
* Law of large numbers (weak/strong)
* Law of the iterated logarithm
* Maximal ergodic theorem
* Sanov's theorem

Inequalities|

* Burkholder–Davis–Gundy
* Doob's martingale
* Kunita–Watanabe

Tools|

* Cameron–Martin formula
* Convergence of random variables
* Doléans-Dade exponential
* Doob decomposition theorem
* Doob–Meyer decomposition theorem
* Doob's optional stopping theorem
* Dynkin's formula
* Feynman–Kac formula
* Filtration
* Girsanov theorem
* Infinitesimal generator
* Itô integral
* Itô's lemma
* Karhunen–Loève_theorem
* Kolmogorov continuity theorem
* Kolmogorov extension theorem
* Lévy–Prokhorov metric
* Malliavin calculus
* Martingale representation theorem
* Optional stopping theorem
* Prokhorov's theorem
* Quadratic variation
* Reflection principle
* Skorokhod integral
* Skorokhod's representation theorem
* Skorokhod space
* Snell envelope
* Stochastic differential equation
* Tanaka
* Stopping time
* Stratonovich integral
* Uniform integrability
* Usual hypotheses
* Wiener space
* Classical
* Abstract

Disciplines|

* Actuarial mathematics
* Econometrics
* Ergodic theory
* Extreme value theory (EVT)
* Large deviations theory
* Mathematical finance
* Mathematical statistics
* Probability theory
* Queueing theory
* Renewal theory
* Ruin theory
* Statistics
* System on Chip design
* Stochastic analysis
* Time series analysis
* Machine learning

* List of topics
* Category

Template:Random matrix theory

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Determinantal point process. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Determinantal_point_process&oldid=3982831"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template