Formal Computer Science / Mathematical structures

Kenton Labs / Mathematical structures

Finite probability

Propagate a probability distribution through an explicitly finite stochastic model with exact fractions.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

DTMC
A discrete-time Markov chain whose row probabilities determine the next-state distribution.
Stochastic matrix
A nonnegative matrix with every row summing to one.
Absorbing state
A state that transitions to itself with probability one.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Validate the initial distribution and each matrix row.
  2. Multiply the row distribution by the transition matrix.
  3. Repeat for the exact declared horizon.
  4. Compare every trajectory row and the final rational distribution.

Cost and scope

A dense n-state chain over h steps costs O(hn²) arithmetic operations, with fraction sizes growing over time.

A common failure

A finite-horizon probability is not automatically an eventual-reachability answer.

Explore the mechanics.

Change a local input or follow the steps. The stored result and its scope remain attached to the downloadable record.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-058
Finite probabilitySuccess and failure after four stepsExact rational trajectory · 4 transitions

The problem

Compute the exact distribution at each step of a finite Markov chain.

The checked result

Final probability distribution: ["1/16", "15/32", "15/32"].

Each step distributes the current mass across outgoing transitions. Absorbing rows retain their mass, and every row of the artifact preserves total probability one.

Why the checker accepts it

  1. Validate the initial distribution and each matrix row.
  2. Multiply the row distribution by the transition matrix.
  3. Repeat for the exact declared horizon.
  4. Compare every trajectory row and the final rational distribution.

Formal specification

{
  "transition": [
    [
      "1/2",
      "1/4",
      "1/4"
    ],
    [
      "0",
      "1",
      "0"
    ],
    [
      "0",
      "0",
      "1"
    ]
  ],
  "initial": [
    "1",
    "0",
    "0"
  ],
  "steps": 4,
  "semantics": "Discrete time, row-stochastic transition matrix, no nondeterministic scheduler."
}

Claim and evidence

{
  "claim": {
    "distribution": [
      "1/16",
      "15/32",
      "15/32"
    ]
  },
  "witness": {
    "trajectory": [
      [
        "1",
        "0",
        "0"
      ],
      [
        "1/2",
        "1/4",
        "1/4"
      ],
      [
        "1/4",
        "3/8",
        "3/8"
      ],
      [
        "1/8",
        "7/16",
        "7/16"
      ],
      [
        "1/16",
        "15/32",
        "15/32"
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 4 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A dense n-state chain over h steps costs O(hn²) arithmetic operations, with fraction sizes growing over time.

The result is for the declared horizon. The browser chart uses floating-point display; Python fractions establish the exact certificate.

A boundary to investigate

A finite-horizon probability is not automatically an eventual-reachability answer. Add absorbing-state equations, expected hitting time, and nondeterministic MDP choices.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-059 ↘Related KL-FCS-060 ↘
KL-FCS-059
Finite probabilityA reversible two-state distributionExact rational trajectory · 6 transitions

The problem

Compute the exact distribution at each step of a finite Markov chain.

The checked result

Final probability distribution: ["2731/4096", "1365/4096"].

Each step distributes the current mass across outgoing transitions. Absorbing rows retain their mass, and every row of the artifact preserves total probability one.

Why the checker accepts it

  1. Validate the initial distribution and each matrix row.
  2. Multiply the row distribution by the transition matrix.
  3. Repeat for the exact declared horizon.
  4. Compare every trajectory row and the final rational distribution.

Formal specification

{
  "transition": [
    [
      "3/4",
      "1/4"
    ],
    [
      "1/2",
      "1/2"
    ]
  ],
  "initial": [
    "1",
    "0"
  ],
  "steps": 6,
  "semantics": "Discrete time, row-stochastic transition matrix, no nondeterministic scheduler."
}

Claim and evidence

{
  "claim": {
    "distribution": [
      "2731/4096",
      "1365/4096"
    ]
  },
  "witness": {
    "trajectory": [
      [
        "1",
        "0"
      ],
      [
        "3/4",
        "1/4"
      ],
      [
        "11/16",
        "5/16"
      ],
      [
        "43/64",
        "21/64"
      ],
      [
        "171/256",
        "85/256"
      ],
      [
        "683/1024",
        "341/1024"
      ],
      [
        "2731/4096",
        "1365/4096"
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 6 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A dense n-state chain over h steps costs O(hn²) arithmetic operations, with fraction sizes growing over time.

The result is for the declared horizon. The browser chart uses floating-point display; Python fractions establish the exact certificate.

A boundary to investigate

A finite-horizon probability is not automatically an eventual-reachability answer. Add absorbing-state equations, expected hitting time, and nondeterministic MDP choices.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-058 ↘Related KL-FCS-060 ↘
KL-FCS-060
Finite probabilityProgress through two transient statesExact rational trajectory · 8 transitions

The problem

Compute the exact distribution at each step of a finite Markov chain.

The checked result

Final probability distribution: ["1/256", "1/32", "247/256"].

Each step distributes the current mass across outgoing transitions. Absorbing rows retain their mass, and every row of the artifact preserves total probability one.

Why the checker accepts it

  1. Validate the initial distribution and each matrix row.
  2. Multiply the row distribution by the transition matrix.
  3. Repeat for the exact declared horizon.
  4. Compare every trajectory row and the final rational distribution.

Formal specification

{
  "transition": [
    [
      "1/2",
      "1/2",
      "0"
    ],
    [
      "0",
      "1/2",
      "1/2"
    ],
    [
      "0",
      "0",
      "1"
    ]
  ],
  "initial": [
    "1",
    "0",
    "0"
  ],
  "steps": 8,
  "semantics": "Discrete time, row-stochastic transition matrix, no nondeterministic scheduler."
}

Claim and evidence

{
  "claim": {
    "distribution": [
      "1/256",
      "1/32",
      "247/256"
    ]
  },
  "witness": {
    "trajectory": [
      [
        "1",
        "0",
        "0"
      ],
      [
        "1/2",
        "1/2",
        "0"
      ],
      [
        "1/4",
        "1/2",
        "1/4"
      ],
      [
        "1/8",
        "3/8",
        "1/2"
      ],
      [
        "1/16",
        "1/4",
        "11/16"
      ],
      [
        "1/32",
        "5/32",
        "13/16"
      ],
      [
        "1/64",
        "3/32",
        "57/64"
      ],
      [
        "1/128",
        "7/128",
        "15/16"
      ],
      [
        "1/256",
        "1/32",
        "247/256"
      ]
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 8 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A dense n-state chain over h steps costs O(hn²) arithmetic operations, with fraction sizes growing over time.

The result is for the declared horizon. The browser chart uses floating-point display; Python fractions establish the exact certificate.

A boundary to investigate

A finite-horizon probability is not automatically an eventual-reachability answer. Add absorbing-state equations, expected hitting time, and nondeterministic MDP choices.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-058 ↘Related KL-FCS-059 ↘

Go further.

Add absorbing-state equations, expected hitting time, and nondeterministic MDP choices.

Questions to investigate

  1. A finite-horizon probability is not automatically an eventual-reachability answer.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add absorbing-state equations, expected hitting time, and nondeterministic MDP choices.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

Information theoryLinear algebra over GF(2)