Determinantal point process

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a determinantal point process is a stochastic point process, the probability distribution of which is characterized as a determinant of some function. Such processes arise as important tools in random matrix theory, combinatorics, and physics.[citation needed]

Definition[edit]

Let \Lambda be a locally compact Polish space and \mu be a Radon measure on \Lambda. Also, consider a measurable function K2 → ℂ.

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

 \rho_n(x_1,\ldots,x_n) = \det(K(x_i,x_j)_{1 \le i,j \le n})

for every n ≥ 1 and x1, . . . , xn ∈ Λ.[1]

Properties[edit]

Existence[edit]

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

\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 φk:Λk → ℝ, k = 1,. . . ,N with compact support:
If
\quad \varphi_0 + \sum_{k=1}^N \sum_{i_1 \neq \cdots \neq i_k } \varphi_k(x_{i_1} \ldots x_{i_k})\ge 0 \text{ for all }k,(x_i)_{i = 1}^k
Then
\quad \varphi_0 + \sum_{i=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 \ge0 \text{ for all } k, (x_i)_{i = 1}^k [2]

Uniqueness[edit]

A sufficient condition for the uniqueness of a determinantal random process with joint intensities ρk is

\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 ⊆ Λ.[2]

Examples[edit]

Gaussian unitary ensemble[edit]

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

K_m(x,y) = \sum_{k=0}^{m-1} \psi_k(x) \psi_k(y)

where \psi_k(x) is the kth oscillator wave function defined by


\psi_k(x)= \frac{1}{\sqrt{\sqrt{2n}n!}}H_k(x) e^{-x^2/4}

and H_k(x) is the kth Hermite polynomial. [3]

Poissonized Plancherel measure[edit]

The poissonized Plancherel measure on partitions of integers (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 ℤ[clarification needed] + 12 with the discrete Bessel kernel, given by:

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

 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}),
 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.[4]

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

Uniform spanning trees[edit]

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.[5] Then the uniformly random spanning tree 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.[1]

References[edit]

  1. ^ a b 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.
  2. ^ a b c A. Soshnikov, Determinantal random point fields. Russian Math. Surveys, 2000, 55 (5), 923–975.
  3. ^ B. Valko. Random matrices, lectures 14–15. Course lecture notes, University of Wisconsin-Madison.
  4. ^ A. Borodin, A. Okounkov, and G. Olshanski, On asymptotics of Plancherel measures for symmetric groups, available via http://xxx.lanl.gov/abs/math/9905032.
  5. ^ Lyons, R. with Peres, Y., Probability on Trees and Networks. Cambridge University Press, In preparation. Current version available at http://mypage.iu.edu/~rdlyons/