API

Implementation of exotic DPP objects:

class dppy.exotic_dpps.CarriesProcess(base=10)[source]

Bases: dppy.exotic_dpps.Descent

DPP on \(\{1, \dots, N-1\}\) (with a non symmetric kernel) derived from the cumulative sum of \(N\) i.i.d. digits in \(\{0, \dots, b-1\}\).

Parameters

base (int, default 10) – Base/radix

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]

Compute the cumulative sum (in base \(b\)) of a sequence of i.i.d. digits and record the position of carries.

Parameters

size (int) – size of the sequence of i.i.d. digits in \(\{0, \dots, b-1\}\)

class dppy.exotic_dpps.DescentProcess[source]

Bases: dppy.exotic_dpps.Descent

DPP on \(\{1, \dots, N-1\}\) associated to 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 \(\sigma \in \mathfrak{S}_N\) uniformly at random and record the descents i.e. \(\{ i ~;~ \sigma_i > \sigma_{i+1} \}\).

Parameters

size (int) – size of the permutation i.e. degree \(N\) of \(\mathfrak{S}_N\).

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

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 limit-shape 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

sample(random_state=None)[source]

Sample from the Poissonized Plancherel measure.

Parameters

random_state (None, np.random, int, np.random.RandomState) –

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

compute_kernel()[source]

Compute the orthogonal projection kernel \(\mathbf{K} = \text{Inc}^+ \text{Inc}\) i.e. onto the span of the rows of the vertex-edge incidence matrix \(\text{Inc}\) of size \(|V| \times |E|\).

In fact, for a connected graph, \(\text{Inc}\) has rank \(|V|-1\) 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

flush_samples()[source]

Empty the list_of_samples attribute.

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') –

    Markov-chain-based samplers:

    • 'Wilson', 'Aldous-Broder'

    Chain-rule-based samplers:

    • 'GS', 'GS_bis', 'KuTa12' from eigenvectors

    • 'Schur', 'Chol', from \(\mathbf{K}\) correlation kernel

  • root (int) – Starting node of the random walk when using Markov-chain-based samplers

  • random_state (None, np.random, int, np.random.RandomState) –

See also

class dppy.exotic_dpps.VirtualDescentProcess(x_0=0.5)[source]

Bases: dppy.exotic_dpps.Descent

This is a DPP on \(\{1, \dots, N-1\}\) 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

Todo

ask @kammmoun to complete the docsting and Section in see also