ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

An exact two-state HMM sequence-MAP calculation

Example

Let $S = {u, v}$ , $Y = {0, 1}$ , and $π (u) = 3 / 4$ , $π (v) = 1 / 4$ . The transition rows are $u \to (u, v) = (3 / 4, 1 / 4)$ and $v \to (u, v) = (1 / 4, 3 / 4)$ . The emissions are $B (u, 0) = 3 / 4$ , $B (u, 1) = 1 / 4$ , $B (v, 0) = 1 / 4$ , and $B (v, 1) = 3 / 4$ . For observations $(0, 1, 1)$ , use the state order $u ≺ v$ . The eight joint path masses are:

Hidden path	Joint mass
$u u u$	$81 / 4096$
$u u v$	$81 / 4096$
$u v u$	$27 / 4096$
$u v v$	$243 / 4096$
$v u u$	$3 / 4096$
$v u v$	$3 / 4096$
$v v u$	$9 / 4096$
$v v v$	$81 / 4096$

The observation evidence is $528 / 4096 = 33 / 256$ .

The diagram uses arrows for transition probabilities and initial weights. Emission probabilities are listed in the prose above each state.

\begin{tikzpicture}[>=stealth]
\node[draw] (start) at (-2,0) {start};
\node[circle,draw] (u) at (0,1) {$u$};
\node[circle,draw] (v) at (0,-1) {$v$};
\draw[->] (start) -- node[above] {$3/4$} (u);
\draw[->] (start) -- node[below] {$1/4$} (v);
\draw[->] (u) edge[loop above] node {$3/4$} (u);
\draw[->] (v) edge[loop below] node {$3/4$} (v);
\draw[->] (u) to[bend left=15] node[right] {$1/4$} (v);
\draw[->] (v) to[bend left=15] node[left] {$1/4$} (u);
\end{tikzpicture}

Facts & Assumptions

Given: The HMM parameters and observation sequence specified in the Example.

[F1]

Finite hidden Markov models for sequence decoding: A hidden path and observation sequence have joint mass equal to the initial, emission, transition, and later emission factors multiplied in order; positive evidence defines the conditional path mass by division by that evidence, and a sequence MAP path maximizes this conditional mass.

[F2]

Viterbi sequence decoding for a finite hidden Markov model: The induced trellis starts with $π (s) B (s, y_{1})$ , uses edge weights $A (r, s) B (s, y_{t})$ for positive factors, and has terminal weights $1$ .

[F3]

Finite-HMM Viterbi decoding is exact sequence MAP: With positive observation evidence, the algorithm returns a hidden-state sequence maximizing the posterior mass of the entire sequence.

Verification

1.1givenF1algebra

The common denominator in each joint path mass is $4^{6} = 4096$ . The numerator factor products, in the order initial, first emission, first transition, second emission, second transition, third emission, are $u u u : 3 \cdot 3 \cdot 3 \cdot 1 \cdot 3 \cdot 1 = 81$ , $u u v : 3 \cdot 3 \cdot 3 \cdot 1 \cdot 1 \cdot 3 = 81$ , $u v u : 3 \cdot 3 \cdot 1 \cdot 3 \cdot 1 \cdot 1 = 27$ , $u v v : 3 \cdot 3 \cdot 1 \cdot 3 \cdot 3 \cdot 3 = 243$ , $v u u : 1 \cdot 1 \cdot 1 \cdot 1 \cdot 3 \cdot 1 = 3$ , $v u v : 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 3 = 3$ , $v v u : 1 \cdot 1 \cdot 3 \cdot 3 \cdot 1 \cdot 1 = 9$ , and $v v v : 1 \cdot 1 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = 81$ . Their sum is $528$ , so the evidence is positive and $u v v$ is the unique maximum-mass path.

2.1givenF2F3step 1.1algebra∎

The max-product table starts with $D_{1} (u) = 9 / 16$ and $D_{1} (v) = 1 / 16$ . At time $2$ , the best incoming products give $D_{2} (u) = (1 / 4) \max {27 / 64, 1 / 64} = 27 / 256$ and $D_{2} (v) = (3 / 4) \max {9 / 64, 3 / 64} = 27 / 256$ . At time $3$ , $D_{3} (u) = (1 / 4) \max {81 / 1024, 27 / 1024} = 81 / 4096$ and $D_{3} (v) = (3 / 4) \max {27 / 1024, 81 / 1024} = 243 / 4096$ . The last pointer is from $v$ to $v$ , and the preceding pointer for $v$ is from $u$ to $v$ , so traceback gives $u v v$ . This agrees with the exhaustive maximum in step 1.1; by [F3] it is a sequence MAP path. Its posterior mass is $(243 / 4096) / (528 / 4096) = 81 / 176$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Manolis Kellis, 6.096 Algorithms for Computational Biology, Lecture 7: Gene Finding and HMMs, MIT OpenCourseWare (Spring 2005) (standard reference, not scraped)
Stanford CS262, Lecture 7: Hidden Markov Models (standard reference, not scraped)