HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a determinantal point process is a
stochastic Stochastic (; ) is the property of being well-described by a random probability distribution. ''Stochasticity'' and ''randomness'' are technically distinct concepts: the former refers to a modeling approach, while the latter describes phenomena; i ...
point process In statistics and probability theory, a point process or point field is a set of a random number of mathematical points randomly located on a mathematical space such as the real line or Euclidean space. Kallenberg, O. (1986). ''Random Measures'', ...
, the
probability distribution In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...
of which is characterized as a
determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
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 In probability theory and mathematical physics, a random matrix is a matrix-valued random variable—that is, a matrix in which some or all of its entries are sampled randomly from a probability distribution. Random matrix theory (RMT) is the ...
theory,
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
,
physics Physics is the scientific study of matter, its Elementary particle, fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge whi ...
,
machine learning Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
, and wireless network modeling.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.


Introduction


Intuition

Consider some positively charged particles confined in a 1-dimensional box 1, +1/math>. Due to electrostatic repulsion, the locations of the charged particles are negatively correlated. That is, if one particle is in a small segment , x + \delta x/math>, 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 \Lambda be a
locally compact In topology and related branches of mathematics, a topological space is called locally compact if, roughly speaking, each small portion of the space looks like a small portion of a compact space. More precisely, it is a topological space in which e ...
Polish space In the mathematical discipline of general topology, a Polish space is a separable space, separable Completely metrizable space, completely metrizable topological space; that is, a space homeomorphic to a Complete space, complete metric space that h ...
and \mu be a
Radon measure In mathematics (specifically in measure theory), a Radon measure, named after Johann Radon, is a measure on the -algebra of Borel sets of a Hausdorff topological space that is finite on all compact sets, outer regular on all Borel sets, and ...
on \Lambda. In most concrete applications, these are
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
\R^n with its Lebesgue measure. A kernel function is a
measurable function In mathematics, and in particular measure theory, a measurable function is a function between the underlying sets of two measurable spaces that preserves the structure of the spaces: the preimage of any measurable set is measurable. This is in ...
K: \Lambda^2 \to \mathbb. We say that X is a determinantal point process on \Lambda with kernel K if it is a simple
point process In statistics and probability theory, a point process or point field is a set of a random number of mathematical points randomly located on a mathematical space such as the real line or Euclidean space. Kallenberg, O. (1986). ''Random Measures'', ...
on \Lambda with a joint intensity or ''correlation function'' (which is the density of its factorial moment measure) given by : \rho_n(x_1,\ldots,x_n) = \det (x_i,x_j) for every ''n'' ≥ 1 and ''x''1, ..., ''x''''n'' ∈ Λ. 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.


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 In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric grou ...
''S''''k''. Thus: \rho_k(x_, \ldots, x_) = \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 ''k'' = 1, ..., ''N'' with
compact support In mathematics, the support of a real-valued function f is the subset of the function domain of elements that are not mapped to zero. If the domain of f is a topological space, then the support of f is instead defined as the smallest closed ...
: If \varphi_0 + \sum_^N \sum_ \varphi_k(x_ \ldots x_)\ge 0 \textk,(x_i)_^k Then A. Soshnikov, Determinantal random point fields. ''Russian Math. Surveys'', 2000, 55 (5), 923–975. \varphi_0 + \sum_^N \int_ \varphi_k(x_1, \ldots, x_k)\rho_k(x_1,\ldots,x_k)\,\textrmx_1\cdots\textrmx_k \ge0 \text k, (x_i)_^k


Uniqueness

A sufficient condition for the uniqueness of a determinantal random process with joint intensities ''ρ''''k'' is \sum_^\infty \left( \frac \int_ \rho_k(x_1,\ldots,x_k) \, \textrmx_1\cdots\textrmx_k \right)^ = \infty for every bounded Borel


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 \mathbb with kernel :K_m(x,y) = \sum_^ \psi_k(x) \psi_k(y) where \psi_k(x) is the kth oscillator wave function defined by \psi_k(x)= \fracH_k(x) e^ and H_k(x) is the kth Hermite polynomial. B. Valko
Random matrices, lectures 14–15


Airy process

The Airy process is governed by the so called ''extended Airy kernel'' which is a generalization of the Airy kernel functionK^(x, y)=\fracwhere \operatorname is the
Airy function In the physical sciences, the Airy function (or Airy function of the first kind) is a special function named after the British astronomer George Biddell Airy (1801–1892). The function Ai(''x'') and the related function Bi(''x''), are Linear in ...
. This process arises from rescaled eigenvalues near the spectral edge of the Gaussian Unitary Ensemble.


Poissonized Plancherel measure

The poissonized Plancherel measure on
integer partition In number theory and combinatorics, a partition of a non-negative integer , also called an integer partition, is a way of writing as a summation, sum of positive integers. Two sums that differ only in the order of their summands are considered ...
(and therefore on Young diagrams) plays an important role in the study of the
longest increasing subsequence In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequenc ...
of a random permutation. The point process corresponding to a random Young diagram, expressed in modified Frobenius coordinates, is a determinantal point process on \mathbb + with the discrete Bessel kernel, given by: K(x,y) = \begin \sqrt \, \dfrac & \text xy >0,\\ 2pt\sqrt \, \dfrac & \text xy <0, \end where k_+(x,y) = J_(2\sqrt)J_(2\sqrt) - J_(2\sqrt)J_(2\sqrt), k_-(x,y) = J_(2\sqrt)J_(2\sqrt) + J_(2\sqrt)J_(2\sqrt) For ''J'' the
Bessel function Bessel functions, named after Friedrich Bessel who was the first to systematically study them in 1824, are canonical solutions of Bessel's differential equation x^2 \frac + x \frac + \left(x^2 - \alpha^2 \right)y = 0 for an arbitrary complex ...
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 {{Short description, none Numerous things are named after the French mathematician Charles Hermite (1822–1901): Hermite * Cubic Hermite spline, a type of third-degree spline * Gauss–Hermite quadrature, an extension of Gaussian quadrature me ...
kernel (although its restriction to the positive and negative semi-axis is Hermitian).


Uniform spanning trees

Let G be a finite, undirected, connected
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
, 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.Lyons, R. with Peres, Y., Probability on Trees and Networks. Cambridge University Press, In preparation. Current version available at http://mypage.iu.edu/~rdlyons/ Then the uniformly random
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
of G is a determinantal point process on ''E'', with kernel :K(e,f) = \langle I^e,I^f \rangle ,\quad e,f \in E.


References

* {{cite book , last=Johansson , first=Kurt , title=Course 1 - Random matrices and determinantal processes , publisher=Elsevier , year=2006 , series=Les Houches , volume=83 , chapter= , doi=10.1016/s0924-8099(06)80038-7 , issn=0924-8099 Point processes