Markov Chain Ontology

FLOW ALGEBRA
TITLE: Markov Chain Ontology
DOMAIN: Discrete Mathematics / Discrete Probability
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-probability/markov-chain-ontology-2.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Represent discrete-time Markov chains as typed stochastic transition systems, enabling mathematically valid reasoning about state evolution, transition probabilities, communicating classes, stationary distributions and long-run behaviour.

2. TYPED ENTITIES
StateSpace S: finite or countable nonempty set.
State i,j,k: elements of S.
TimeIndex t: nonnegative integer.
RandomState X_t: S-valued random variable.
TransitionMatrix P: S x S -> [0,1], row-stochastic.
TransitionProbability p_ij: P(X_(t+1)=j | X_t=i).
InitialDistribution mu_0: probability mass function on S.
Distribution mu_t: probability mass function on S at time t.
NstepTransition P^n: n-step transition kernel.
StationaryDistribution pi: probability distribution satisfying pi P = pi.
CommunicatingClass C: equivalence class under mutual reachability.
AbsorbingState a: state satisfying p_aa=1.

3. CORE RELATIONSHIPS
HAS_STATE(chain, state)
HAS_TRANSITION(chain, i, j, p_ij)
HAS_INITIAL_DISTRIBUTION(chain, mu_0)
REACHABLE(i,j) iff exists n>=0 with (P^n)_ij>0
COMMUNICATES(i,j) iff REACHABLE(i,j) and REACHABLE(j,i)
IS_ABSORBING(i) iff p_ii=1
IS_STATIONARY(pi,P) iff pi P=pi

4. FORMAL AXIOMS
A1: for every i,j in S, 0 <= p_ij <= 1.
A2: for every i in S, sum_(j in S) p_ij = 1.
A3 (Markov property): P(X_(t+1)=j | X_t=i, X_(t-1),...,X_0) = p_ij for histories with positive probability.
A4 (time homogeneity): p_ij does not depend on t; this file models homogeneous discrete-time chains.
A5: mu_0(i)>=0 and sum_i mu_0(i)=1.

5. FLOW OPERATIONS
INITIALISE(S,P,mu_0) -> MarkovChain after validation.
ADVANCE(mu_t,P) -> mu_(t+1)=mu_t P.
EVOLVE(mu_0,P,n) -> mu_n=mu_0 P^n.
N_STEP(P,n) -> P^n, with P^0=I.
CLASSIFY_COMMUNICATION(P) -> communicating classes.
CHECK_IRREDUCIBLE(P) -> all states communicate.
CHECK_ABSORBING(P,i) -> p_ii=1.
SOLVE_STATIONARY(P) -> pi with pi P=pi, pi>=0, sum pi=1.
CHECK_PERIOD(P,i) -> gcd{n>=1 : (P^n)_ii>0}, when returns exist.

6. ALGEBRAIC LAWS
Chapman-Kolmogorov: (P^(m+n))_ij = sum_k (P^m)_ik (P^n)_kj.
Semigroup: P^(m+n)=P^m P^n.
Identity: P^0=I.
Mass conservation: sum_j mu_t(j)=1 for every t>=0.
Stationarity: if mu_0=pi and pi P=pi, then mu_t=pi for all t.
Finite irreducible chains have a unique stationary distribution with strictly positive entries.
Finite irreducible aperiodic chains converge to their stationary distribution from any initial distribution.
Irreducibility alone does not guarantee pointwise convergence: periodic chains can oscillate.
Countably infinite chains require additional conditions for existence, uniqueness and convergence of stationary distributions.

7. INFERENCE RULES
R1: ROW_STOCHASTIC(P) and DISTRIBUTION(mu) => DISTRIBUTION(mu P).
R2: STATIONARY(pi,P) => STATIONARY(pi,P^n) for n>=0.
R3: REACHABLE(i,j) and REACHABLE(j,k) => REACHABLE(i,k).
R4: COMMUNICATES(i,j) and COMMUNICATES(j,k) => COMMUNICATES(i,k).
R5: ABSORBING(a) and X_t=a => P(X_(t+n)=a | X_t=a)=1 for n>=0.
R6: FINITE(S) and IRREDUCIBLE(P) => UNIQUE_STATIONARY(P).
R7: FINITE(S) and IRREDUCIBLE(P) and APERIODIC(P) => CONVERGES_TO_STATIONARY(P).

8. VALIDATION
V1: S nonempty; every transition endpoint belongs to S.
V2: probabilities are numeric, finite, nonnegative and at most one.
V3: each transition row sums to 1 within declared numerical tolerance.
V4: initial and stationary distributions are nonnegative and normalised.
V5: stationary residual ||pi P-pi|| within numerical tolerance.
V6: label convergence claims with assumptions on finiteness, irreducibility and aperiodicity.
V7: do not infer independence of successive states from the Markov property.
V8: distinguish absorbing, recurrent, transient and periodic states.

9. WORKED EXAMPLE
S={A,B}
P=[[0.8,0.2],[0.3,0.7]]
mu_0=[1,0]
mu_1=mu_0 P=[0.8,0.2]
pi=[0.6,0.4]
CHECK: pi P=[0.6,0.4]=pi.
Both states communicate; positive self-transition probabilities imply aperiodicity. The finite chain is irreducible and converges to pi.

10. SEMANTIC_EQUIVALENCE
"Markov chain" ~= "discrete-time Markov process" only where discrete-time, Markov and time-homogeneous assumptions match.
"Transition probability matrix" == "row-stochastic transition matrix" under row-vector distribution convention.
"Stationary distribution" != "initial distribution" unless explicitly equal.
"Markov property" != "independence of states".

11. CONFIDENCE
Mathematical definitions and standard finite-chain results: HIGH, subject to explicit assumptions.
Numerical computations: confidence depends on precision, conditioning and validation tolerance.
Empirically estimated transition probabilities: report estimation method, sample size and uncertainty; do not treat as exact.

12. FLOW_HASH
MODEL: SHA-256 over canonical UTF-8 serialisation of ontology identifier, version, entities, axioms, operations and inference rules.
STATUS: NOT_COMPUTED; compute after canonicalisation and deployment. Never represent a placeholder as a verified digest.

13. UPDATE_MODEL
Trigger on changes to state space, transition kernel, initial distribution, modelling assumptions or validation rules.
On update: increment version; rerun stochasticity checks; recompute communicating classes, stationary solutions and applicable convergence claims; regenerate FLOW_HASH.
Preserve source URL, revision history and provenance.

14. AI_CONSUMPTION
Inputs: typed state space, transition matrix, optional initial distribution and query.
Processing: validate -> select operation -> compute -> verify assumptions -> return result.
Outputs: distributions, n-step probabilities, classifications, stationary candidates, proof conditions and provenance.
Constraints: do not assert convergence without conditions; distinguish exact algebra from numerical approximation; report undefined or unverified results.

END FLOW ALGEBRA