CounterexampleConstruction: 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.

Coordinatewise posterior modes need not be a sequence MAP

Statement refuted

For every finite HMM with positive observation evidence, choosing a posterior-most-probable hidden state separately at each time always produces a sequence MAP path.

Facts & Assumptions

Given: A finite discrete HMM, an observation sequence $y$ , and $p (y) > 0$ . The time- $t$ posterior marginal at state $s$ is $\sum_{z : z_{t} = s} p (z ∣ y)$ .

[F1]

Finite hidden Markov models for sequence decoding: For positive evidence, $p (z ∣ y) = p (z, y) / p (y)$ ; a sequence MAP path maximizes this whole-path conditional mass.

Counterexample

Let $S = {u, v}$ and $Y = {x}$ . Set $π (u) = 7 / 20$ and $π (v) = 13 / 20$ . The transition rows are $u \to (u, v) = (1, 0)$ and $v \to (u, v) = (34 / 65, 31 / 65)$ . Both states emit $x$ with probability $1$ . Observe $y = (x, x)$ . The four hidden-path masses are $p (u u, y) = 7 / 20, p (u v, y) = 0, p (v u, y) = 17 / 50, p (v v, y) = 31 / 100.$ They sum to $1$ , so these are also the posterior path masses.

1.1givenF1algebra

The initial weights sum to $1$ , each transition row sums to $1$ , and each emission row has its single entry equal to $1$ , so this is a valid HMM. The path masses follow by multiplying the initial and transition factors: $u u = (7 / 20) \cdot 1 = 7 / 20$ , $u v = (7 / 20) \cdot 0 = 0$ , $v u = (13 / 20) (34 / 65) = 17 / 50$ , and $v v = (13 / 20) (31 / 65) = 31 / 100$ . Their sum is $35 / 100 + 0 + 34 / 100 + 31 / 100 = 1$ .

2.1givenF1step 1.1algebra∎

The time-1 marginal masses are $P (Z_{1} = u ∣ y) = 35 / 100$ and $P (Z_{1} = v ∣ y) = 65 / 100$ , so the unique time-1 mode is $v$ . The time-2 marginal masses are $P (Z_{2} = u ∣ y) = 35 / 100 + 34 / 100 = 69 / 100$ and $P (Z_{2} = v ∣ y) = 31 / 100$ , so the unique time-2 mode is $u$ . Their coordinatewise mode is $v u$ , whose mass $17 / 50 = 34 / 100$ is strictly below $p (u u ∣ y) = 7 / 20 = 35 / 100$ . Hence $v u$ is not a sequence MAP path, refuting the Statement.

Depends on

Finite hidden Markov models for sequence decoding

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

1 result within one dependency step 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)