API¶
Implementation of exotic DPP objects:
Uniform spanning trees
UST
Descent procresses
Descent
:PoissonizedPlancherel
measure

class
dppy.exotic_dpps.
CarriesProcess
(base=10)[source]¶ Bases:
dppy.exotic_dpps.Descent
DPP on \(\{1, \dots, N1\}\) (with a non symmetric kernel) derived from the cumulative sum of \(N\) i.i.d. digits in \(\{0, \dots, b1\}\).
 Parameters
base (int, default 10) – Base/radix
See also

flush_samples
()¶ Empty the
list_of_samples
attribute.

plot
(vs_bernoullis=True, random_state=None)¶ Display the last realization of the process. If
vs_bernoullis=True
compare it to a sequence of i.i.d. Bernoullis with parameter_bernoulli_param
See also

class
dppy.exotic_dpps.
DescentProcess
[source]¶ Bases:
dppy.exotic_dpps.Descent
DPP on \(\{1, \dots, N1\}\) associated to the descent process on the symmetric group \(\mathfrak{S}_N\).
See also

flush_samples
()¶ Empty the
list_of_samples
attribute.

plot
(vs_bernoullis=True, random_state=None)¶ Display the last realization of the process. If
vs_bernoullis=True
compare it to a sequence of i.i.d. Bernoullis with parameter_bernoulli_param
See also


class
dppy.exotic_dpps.
PoissonizedPlancherel
(theta=10)[source]¶ Bases:
object
DPP on partitions associated to the Poissonized Plancherel measure
 Parameters
theta (int, default 10) – Poisson parameter i.e. expected length of permutation
See also
[Bor09] Section 6

plot
(title='')[source]¶ Display the process on the real line
 Parameters
title (string) – Plot title
See also

plot_diagram
(normalization=False)[source]¶ Display the Young diagram (russian convention), the associated sample and potentially rescale the two to visualize the limitshape theorem [Ker96]. The sample corresponds to the projection onto the real line of the descending surface edges.
 Parameters
normalization (bool, default False) – If
normalization=True
, the Young diagram and the corresponding sample are scaled by a factor \(\sqrt{\theta}\) and the limiting

class
dppy.exotic_dpps.
UST
(graph)[source]¶ Bases:
object
DPP on edges of a connected graph \(G\) with correlation kernel the projection kernel onto the span of the rows of the incidence matrix \(\text{Inc}\) of \(G\).
This DPP corresponds to the uniform measure on spanning trees (UST) of \(G\).
 Parameters
graph (networkx graph) – Connected undirected graph
See also

compute_kernel
()[source]¶ Compute the orthogonal projection kernel \(\mathbf{K} = \text{Inc}^+ \text{Inc}\) i.e. onto the span of the rows of the vertexedge incidence matrix \(\text{Inc}\) of size \(V \times E\).
In fact, for a connected graph, \(\text{Inc}\) has rank \(V1\) and any row can be discarded to get an basis of row space. If we note \(A\) the amputated version of \(\text{Inc}\), then \(\text{Inc}^+ = A^{\top}[AA^{\top}]^{1}\).
In practice, we orthogonalize the rows of \(A\) to get the eigenvectors \(U\) of \(\mathbf{K}=UU^{\top}\).
See also

compute_kernel_eig_vecs
()[source]¶ See explaination in
compute_kernel

plot
(title='')[source]¶ Display the last realization (spanning tree) of the corresponding
UST
object. Parameters
title (string) – Plot title
See also

plot_graph
(title='')[source]¶ Display the original graph defining the
UST
object Parameters
title (string) – Plot title
See also

plot_kernel
(title='')[source]¶ Display a heatmap of the underlying orthogonal projection kernel \(\mathbf{K}\) associated to the DPP underlying the
UST
object Parameters
title (string) – Plot title
See also

sample
(mode='Wilson', root=None, random_state=None)[source]¶ Sample a spanning of the underlying graph uniformly at random. It generates a networkx graph object.
 Parameters
mode (string, default
'Wilson'
) –Markovchainbased samplers:
'Wilson'
,'AldousBroder'
Chainrulebased samplers:
'GS'
,'GS_bis'
,'KuTa12'
from eigenvectors'Schur'
,'Chol'
, from \(\mathbf{K}\) correlation kernel
root (int) – Starting node of the random walk when using Markovchainbased samplers
random_state (None, np.random, int, np.random.RandomState) –

class
dppy.exotic_dpps.
VirtualDescentProcess
(x_0=0.5)[source]¶ Bases:
dppy.exotic_dpps.Descent
This is a DPP on \(\{1, \dots, N1\}\) with a non symmetric kernel appearing in (or as a limit of) the descent process on the symmetric group \(\mathfrak{S}_N\).

flush_samples
()¶ Empty the
list_of_samples
attribute.

plot
(vs_bernoullis=True, random_state=None)¶ Display the last realization of the process. If
vs_bernoullis=True
compare it to a sequence of i.i.d. Bernoullis with parameter_bernoulli_param
See also

sample
(size=100, random_state=None)[source]¶ Draw a permutation uniformly at random and record the descents i.e. indices where \(\sigma(i+1) < \sigma(i)\) and something else…
 Parameters
size (int) – size of the permutation i.e. degree \(N\) of \(\mathfrak{S}_N\).
See also
[Kam18], Sec ??
Todo
ask @kammmoun to complete the docsting and Section in see also
