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, 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
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, N-1\}\) 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 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
-
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 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
-
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) –
-
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
[Kam18], Sec ??
Todo
ask @kammmoun to complete the docsting and Section in see also
-