A DPP, call it P, is a random variable that take values on the powerset 2

^{X}of some set X, with a particular sort of distribution that encourages "variety" of the points of X that get selected to be in the set that is outcome of the random variable.

To define a DPP, you pick a kernel K, a symmetric positive semi-definite N x N matrix (whose eigenvalues are never any more than 1) where N is the cardinality of X, and then the marginal probability distribution of P is determined by

_{S})

for any S ⊆ X, where K

_{S}means the matrix K trimmed down to just the rows and columns that correspond to the elements of X that are actually in S.

To unpack some intuition about this, consider the singleton and doubleton cases of S.

Pr[x ∈ P] = Pr[P ⊇ {x}] = det(K

_{xx}) = K

_{xx}

so the diagonal of K tells us the marginal probabilities of each particular element of X belonging to P in isolation.

Pr[{x,y} ⊆ P] = det | ( | K_{xx} | K_{xy} | ) |

K_{yx} | K_{yy} |

= K

_{xx}K

_{yy}- K

_{xy}

^{2}

so all of the off-diagonal elements of K tell us how much potential elements of P "repel" each other, in the sense that the joint probability of having the two of them is less than they would be if they were independent.

Apparently this kind of distribution is good for (among other things) search result display, because you don't necessarily want to show the top results for a query --- they might all be very similar to each other. You want the similar ones to "repel" each other a bit, and prefer choosing different ones to better cover the space of what someone might want from a query.