Practicable shuffles

Haskell commentary on the implementation of Tractable and Practicable Inducers/Practicable shuffles

The application, $I_{z,\mathrm{p}}^{ * }(A)$, of a substrate histogram $A \in \mathcal{A}_z$ in a practicable inducer $I_{z,\mathrm{p}} \in \mathrm{inducers}(z)$ requires that the histogram be practicably representable. For example, substrate histogram, $A$, may have a binary map histogram representation such that $I_{z,\mathrm{p}}^{\mathrm{s}}(A) \leq \mathrm{smax}$ where the maximum space limit is $\mathrm{smax} \in \mathbf{N}_{>0}$. In this case the representation space depends on the effective volume, $|A^{\mathrm{F}}|$.

In some cases the computation of the independent histogram, $A^{\mathrm{X}}$, may be impracticable because the effective volume, $|A^{\mathrm{XF}}| = v = |V_A^{\mathrm{C}}|$, is too large for available resources, for example, if $v > \mathrm{smax}$. If this is the case, the computation of the alignment of the histogram, $\mathrm{algn}(A)$, is also impracticable, for example $I_{\mathrm{a}}^{\mathrm{s}}(A) > \mathrm{smax}$. Consider the case where any subset of the cartesian, $A^{\mathrm{C}}$, of cardinality equal to the size, $\{B : B \subseteq A^{\mathrm{C}},~\mathrm{size}(B)=z\}$, is practicably representable. In this case of practicable size, a practicable inducer may use a shuffled histogram as a proxy for the independent histogram. For example, given some substrate transform $T \in \mathcal{T}_{U_A,V_A}$, the computation of the content alignment, $\mathrm{algn}(A * T) - \mathrm{algn}(A^{\mathrm{X}} * T)$, may be approximated by the computation of $\mathrm{algn}(A * T) - \mathrm{algn}(B * T)$, where the shuffled histogram, $B$, approximates to the independent, $B \approx A^{\mathrm{X}}$, and the effective volume is practicable, $|B^{\mathrm{F}}| \leq z$.

Section ‘Shuffled history’ P262 defines the function $\mathrm{shuffles} \in \mathcal{H} \to \mathrm{P}(\mathcal{H})$. Let the set of shuffled histories of the substrate histogram $A \in \mathcal{A}_{z}$ be $Q = \mathrm{shuffles}(\mathrm{history}(A)) \subset \mathcal{H}$. The independent of each of the shuffled histories is equal to that of the independent histogram, $\forall G \in Q~\lozenge B=\mathrm{his}(G)~(B^{\mathrm{X}} \equiv A^{\mathrm{X}})$, where $\mathrm{his} = \mathrm{histogram}$. If the independent is integral, $A \in \mathcal{A}_{z,\mathrm{xi}}$, there must exist independent shuffles, $\exists G \in Q~\lozenge B=\mathrm{his}(G)~(B = A^{\mathrm{X}})$. In this case, there exist shuffles having zero alignment, $\exists G \in Q~\lozenge B=\mathrm{his}(G)~(\mathrm{algn}(B)=0)$.

As shown above in section ‘Minimum alignment’ P427, the logarithm expected exponential alignment given distribution histogram of $A^{\mathrm{X}}$ is \[ \begin{eqnarray} &&\ln \mathrm{expected}(\hat{Q}_{\mathrm{m},U_A}(A^{\mathrm{X}},z))(\{(B,\mathrm{exp}(\mathrm{algn}(B))) : B \in \mathcal{A}_{U_A,\mathrm{i},V_A,z}\}) = \\ &&\hspace{15em}\ln \sum_{B \in \mathcal{A}_{U_A,\mathrm{i},V_A,z}} \mathrm{mpdf}(U_A)(A^{\mathrm{X}},z)(B^{\mathrm{X}}) \end{eqnarray} \] and that the expected alignment in the case where the independent is cartesian, $A^{\mathrm{X}} = \mathrm{scalar}(z/v) * V_A^{\mathrm{C}}$, is such that \[ \begin{eqnarray} &&\mathrm{expected}(\hat{Q}_{\mathrm{m},U_A}(V^{\mathrm{C}},z))(\{(B,\mathrm{algn}(B)) : B \in \mathcal{A}_{U_A,\mathrm{i},V_A,z}\}) \\ &\leq& \ln (z+v-1)! - \ln (v-1)! - v \ln (z/v)! - z \ln v \end{eqnarray} \] where $v = |V_A^{\mathrm{CS}}|$. So conjecture that the expected alignment of the shuffled histories is also approximately subject to the same inequality, \[ \begin{eqnarray} &&\mathrm{average}(\{(G,\mathrm{algn}(B)) : G \in Q,~B=\mathrm{his}(G)\})\\ &\leq& \ln (z+v-1)! - \ln (v-1)! - v \ln (z/v)! - z \ln v \end{eqnarray} \] If $z \ll v$ then the expression above approximates to $z \ln (v/z)$. In the case of a regular volume of dimension $n$ and valency $d$, the expected alignment approximates to $zn \ln (d/z^{1/n})$. This may be compared to the maximum alignment which approximates to $z(n-1) \ln (d)$. So in this case, the inequality imposes little or no constraint. That is, if the volume, $v$, is impracticable, but the size, $z$, is practicable, the inequality above is not a practicable test of a randomly chosen shuffle histogram that ensures that its alignment does not exceed the expected alignment. In any case the computation of the alignment of the shuffle histogram is impracticable.

Even so, a practicable inducer may be implemented without guarantee that a randomly chosen shuffle histogram has an alignment that is small. Choose a shuffle histogram at random, $L_r$, where $X \in \mathrm{enums}(\mathrm{shuffles}(\mathrm{history}(A)))$, $L = \mathrm{map}(\mathrm{his},\mathrm{flip}(X))$, $r \in \{1 \ldots z!^n\}$ and $n = |V_A|$. The randomly chosen shuffle histogram, $L_r$, is expected to have alignment that is near zero with respect to maximum alignment, $\mathrm{algn}(L_r) \approx \mathrm{expected}(\hat{Q}_{\mathrm{m},U_A}(A^{\mathrm{X}},z))(\{(B,\mathrm{algn}(B)) : B \in \mathcal{A}_{U_A,\mathrm{i},V_A,z}\}) \approx 0 = \mathrm{algn}(A^{\mathrm{X}})$. As the size, $z$, increases, the alignment, $\mathrm{algn}(L_r)$, decreases. Note that the computation of the alignment of the shuffle histogram, $\mathrm{algn}(L_r)$, is impracticable.

The confidence in the shuffle histogram may be increased in a practicable inducer, $I_{z,\mathrm{p}}$, by scaling the sum of shuffle histograms, $B = \mathrm{scalar}(1/|R|) * \sum_{r \in R} L_r$, where $R \subset \{1 \ldots z!^n\}$ and $R \neq \emptyset$. Note that the scaled shuffle histogram, $B$, is not necessarily integral. The effective volume of the scaled shuffle histogram is greater than or equal to the effective volume of the contributing shuffle histograms, $\forall r \in R~(|B^{\mathrm{F}}| \geq |L_r^{\mathrm{F}}|)$. If all possible shuffle histograms are used the resultant scaled shuffle histogram is the independent, $\mathrm{scalar}(1/z!^n) * \sum_{r \in \{1 \ldots z!^n\}} L_r = A^{\mathrm{X}}$.

In addition, the alignment of the scaled shuffle histogram, $B$, may be tested for practicable subsets of the substrate. Choose the largest substrate subset cardinality $k \leq n$ such that the computation of the combinations, $\sum_{i \in \{1 \ldots k\}} n^{\underline{i}}/i! = |\{K : K \subseteq V,~|K| \leq k\}|$, of reduced alignments is practicable. Then the highest reduced alignment is $\mathrm{maxr}(\{(K, \mathrm{algn}(B\%K)) : K \subseteq V,~|K| \leq k\})$.