43. A finite certificate with a positive lift
On this page · Permalink · Source line 1748
Let \(V=[v_1\ \cdots\ v_m]\in\mathbb R^{r\times m}\) have full row rank and satisfy
Its columns generate \(C=V\mathbb R_+^m\) and its normalized base is \(K=\operatorname{conv}\{v_1,\ldots,v_m\}\). Finite generation makes the cone closed. Its normalized generators and full row rank make it pointed and generating, with a strictly positive mass functional.
Proposition 39: Finite positive-lift certificate
This cone is invariant under \(B_s\) if and only if there is an entrywise nonnegative matrix \(A_s\in\mathbb R^{m\times m}\) such that
If these identities hold for every symbol and \(z_0=V\alpha_0\) for \(\alpha_0\geq0\) with \(\mathbf1^\top\alpha_0=1\), then
Thus the finite witness defines a nonnegative probability instrument whose image under \(V\) is the predictive model. It certifies all word probabilities without enumerating them.
Read proof · Recorded Lean scope · Visual guide: Probability meaning is geometric · Permalink · Source line 1758
Proof
Invariance places each \(B_sv_j\) in the conical hull of the columns of \(V\). Choose its nonnegative coefficients as column \(j\) of \(A_s\). Conversely, \(B_sV\alpha=VA_s\alpha\in C\) for every \(\alpha\geq0\). Multiplying the intertwining identity by \(\lambda\) and summing over observations gives
Iterating \(B_sV=VA_s\) gives \(B_wV=VA_w\). Applying the mass row and the initial coefficients proves the word identity. Strict positivity of \(\lambda\) follows because a nonzero conical combination has positive total coefficient mass. \(\square\)
The \(m\) nonnegative coordinates need not be physical hidden states, and \(m\) need not equal the minimal predictive dimension \(r\). They are one finite realization witnessing validity. When \(V\) has dependent columns, the lift can be nonunique. Those redundant coordinates do not change the predictive state after synthesis.
There is a dual finite test. If a complete inequality description of the same cone is \(C=\{z:Gz\geq0\}\), then \(GB_sv_j\geq0\) for every generator \(j\) is equivalent to invariance. One may also certify \(GB_s=H_sG\) with \(H_s\geq0\). The latter certificate is sufficient by direct multiplication and necessary by the polyhedral cone form of Farkas' lemma [R13]. The reference calculation uses the direct generator test, not an unreported numerical optimization certificate.