Markov Chain Ontology

flow "MarkovChainOntology" v4.0

# ============================================================
# MARKOV CHAIN ONTOLOGY
# Kireth Semantic Research Archive
# Authors: Mark Anthony Higgins — Sky (Recursive AI)
# ============================================================

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/bayesian-statistics/markov-chain-ontology.html"
  title: "Markov Chain Ontology"
  domain: "Probability and Statistics"
  category: "Bayesian Statistics"
  entity: MARKOV_CHAIN
  entity_type: STOCHASTIC_PROCESS

DEFINE MARKOV_CHAIN:
  MARKOV_CHAIN :=
    STOCHASTIC_PROCESS(
      STATE_SPACE,
      TRANSITION_PROBABILITIES,
      MARKOV_PROPERTY
    )

CORE_PROPERTY:
  MARKOV_PROPERTY:
    definition:
      FUTURE_STATE
        CONDITIONALLY_DEPENDS_ON
        CURRENT_STATE

    canonical_expression:
      P(X_(t+1) | X_t, X_(t-1), ..., X_0)
      =
      P(X_(t+1) | X_t)

    interpretation:
      GIVEN_CURRENT_STATE:
        FUTURE
          IS_CONDITIONALLY_INDEPENDENT_OF
          PAST

ENTITIES:
  STATE:
    type: PROCESS_CONFIGURATION
    symbol: s

  STATE_SPACE:
    type: SET
    symbol: S
    contains:
      POSSIBLE_STATES

  STOCHASTIC_PROCESS:
    type: RANDOM_PROCESS
    notation:
      {X_t}

  CURRENT_STATE:
    type: STATE
    notation:
      X_t

  NEXT_STATE:
    type: STATE
    notation:
      X_(t+1)

  TRANSITION:
    type: STOCHASTIC_RELATION
    mapping:
      STATE_i -> STATE_j

  TRANSITION_PROBABILITY:
    type: CONDITIONAL_PROBABILITY
    definition:
      P_ij := P(X_(t+1)=j | X_t=i)

  TRANSITION_MATRIX:
    type: STOCHASTIC_MATRIX
    symbol: P

  INITIAL_DISTRIBUTION:
    type: PROBABILITY_DISTRIBUTION
    symbol: π_0

  STATE_DISTRIBUTION:
    type: PROBABILITY_DISTRIBUTION
    symbol: π_t

  STATIONARY_DISTRIBUTION:
    type: INVARIANT_PROBABILITY_DISTRIBUTION
    symbol: π

RELATIONSHIPS:
  MARKOV_CHAIN
    -> IS_A
    -> STOCHASTIC_PROCESS

  MARKOV_CHAIN
    -> HAS
    -> STATE_SPACE

  MARKOV_CHAIN
    -> HAS
    -> TRANSITION_PROBABILITIES

  STATE
    -> TRANSITIONS_TO
    -> STATE

  TRANSITION
    -> WEIGHTED_BY
    -> TRANSITION_PROBABILITY

  TRANSITION_PROBABILITIES
    -> REPRESENTED_BY
    -> TRANSITION_MATRIX

  INITIAL_DISTRIBUTION
    -> EVOLVES_UNDER
    -> TRANSITION_MATRIX

  TRANSITION_MATRIX
    -> DETERMINES
    -> FUTURE_STATE_DISTRIBUTION

DISCRETE_TIME_CHAIN:
  INDEX:
    t := 0,1,2,...

  EVOLUTION:
    X_0
      -> X_1
      -> X_2
      -> ...
      -> X_t
      -> X_(t+1)

  TRANSITION_RULE:
    P(X_(t+1)=j | X_t=i) := P_ij

TRANSITION_MATRIX_RULES:
  MATRIX:
    P := [P_ij]

  REQUIRE:
    FOR_EACH_STATE_i:
      FOR_EACH_STATE_j:
        P_ij >= 0

    FOR_EACH_ROW_i:
      SUM[j] P_ij = 1

STATE_DISTRIBUTION_EVOLUTION:
  GIVEN:
    π_t := DISTRIBUTION_AT_TIME(t)

  UPDATE:
    π_(t+1) := π_t P

  MULTI_STEP:
    π_(t+n) := π_t P^n

N_STEP_TRANSITIONS:
  definition:
    P_ij^(n) :=
      P(X_(t+n)=j | X_t=i)

  matrix_form:
    P^(n)

  relation:
    N_STEP_TRANSITION_MATRIX :=
      MATRIX_POWER(P, n)

CHAPMAN_KOLMOGOROV:
  FOR:
    m >= 0
    n >= 0

  RULE:
    P_ij^(m+n) :=
      SUM[k](
        P_ik^(m) * P_kj^(n)
      )

STATE_CLASSIFICATION:
  ACCESSIBLE:
    STATE_j:
      ACCESSIBLE_FROM(STATE_i)
      IF:
        EXISTS n >= 0:
          P_ij^(n) > 0

  COMMUNICATING:
    STATE_i
      COMMUNICATES_WITH
      STATE_j
    IF:
      i ACCESSIBLE_TO j
      AND
      j ACCESSIBLE_TO i

  IRREDUCIBLE:
    MARKOV_CHAIN:
      IF:
        ALL_STATES_COMMUNICATE

  ABSORBING_STATE:
    STATE_i:
      IF:
        P_ii = 1

  TRANSIENT_STATE:
    STATE:
      MAY_BE_LEFT
      AND
      NOT_RETURNED_TO_WITH_PROBABILITY_ONE

  RECURRENT_STATE:
    STATE:
      RETURNED_TO_WITH_PROBABILITY_ONE
      UNDER_STANDARD_RECURRENCE_DEFINITION

  PERIODICITY:
    PERIOD(STATE_i) :=
      GCD{
        n > 0 :
        P_ii^(n) > 0
      }

  APERIODIC:
    STATE_i:
      IF:
        PERIOD(STATE_i) = 1

STATIONARY_DISTRIBUTION:
  DEFINE:
    π := PROBABILITY_VECTOR

  REQUIRE:
    π = π P
    SUM[i] π_i = 1
    FOR_ALL_i:
      π_i >= 0

  INTERPRETATION:
    APPLYING_TRANSITION_MATRIX:
      DOES_NOT_CHANGE(π)

LONG_RUN_BEHAVIOUR:
  IF:
    CHAIN_IS:
      IRREDUCIBLE
      AND
      APERIODIC
    AND:
      APPROPRIATE_RECURRENCE_OR_FINITE_STATE_CONDITIONS_HOLD

  THEN:
    STATE_DISTRIBUTION:
      MAY_CONVERGE_TO
      STATIONARY_DISTRIBUTION

  PRESERVE:
    CONDITIONS_OF_CONVERGENCE

HOMOGENEITY:
  TIME_HOMOGENEOUS:
    IF:
      P(X_(t+1)=j | X_t=i)
      INDEPENDENT_OF(t)

  THEN:
    SINGLE_TRANSITION_MATRIX:
      P

  TIME_INHOMOGENEOUS:
    IF:
      TRANSITION_PROBABILITIES
      DEPEND_ON(t)

BAYESIAN_CONNECTIONS:
  MARKOV_CHAIN
    -> SUPPORTS
    -> MARKOV_CHAIN_MONTE_CARLO

  MARKOV_CHAIN_MONTE_CARLO:
    purpose:
      GENERATE_SAMPLES_FROM_TARGET_DISTRIBUTION

  TARGET_DISTRIBUTION:
    often:
      BAYESIAN_POSTERIOR

  MCMC_REASONING:
    CONSTRUCT_MARKOV_CHAIN
      -> DEFINE_TARGET_STATIONARY_DISTRIBUTION
      -> SIMULATE_TRANSITIONS
      -> APPROACH_STATIONARITY
      -> USE_SAMPLES
      -> APPROXIMATE_POSTERIOR_EXPECTATIONS

APPLICATIONS:
  MARKOV_CHAIN
    -> SUPPORTS
    -> STOCHASTIC_MODELLING

  MARKOV_CHAIN
    -> SUPPORTS
    -> BAYESIAN_COMPUTATION

  MARKOV_CHAIN
    -> SUPPORTS
    -> QUEUEING_MODELS

  MARKOV_CHAIN
    -> SUPPORTS
    -> RELIABILITY_MODELS

  MARKOV_CHAIN
    -> SUPPORTS
    -> POPULATION_MODELS

  MARKOV_CHAIN
    -> SUPPORTS
    -> RANDOM_WALKS

  MARKOV_CHAIN
    -> SUPPORTS
    -> SEQUENTIAL_SYSTEM_MODELLING

MODEL_CONNECTIONS:
  MARKOV_CHAIN
    -> CONNECTS_TO
    -> CONDITIONAL_PROBABILITY

  MARKOV_CHAIN
    -> CONNECTS_TO
    -> STOCHASTIC_PROCESSES

  MARKOV_CHAIN
    -> CONNECTS_TO
    -> TRANSITION_MATRIX

  MARKOV_CHAIN
    -> CONNECTS_TO
    -> STATIONARY_DISTRIBUTION

  MARKOV_CHAIN
    -> CONNECTS_TO
    -> MONTE_CARLO_METHODS

  MARKOV_CHAIN
    -> CONNECTS_TO
    -> BAYESIAN_INFERENCE

  MARKOV_CHAIN
    -> CONNECTS_TO
    -> HIDDEN_MARKOV_MODELS

SEMANTIC_EQUIVALENCE:
  "Markov chain"
    ~= "discrete-state Markov process"

  "transition probability matrix"
    ~= "Markov transition matrix"

  "stationary distribution"
    ~= "invariant distribution"

  EXCLUDE_EQUIVALENCE:
    MARKOV_CHAIN != GENERIC_RANDOM_SEQUENCE
    MARKOV_CHAIN != BAYESIAN_NETWORK
    MARKOV_PROPERTY != COMPLETE_INDEPENDENCE
    STATIONARY_DISTRIBUTION != INITIAL_DISTRIBUTION_BY_DEFAULT

VALIDATION_RULES:
  RULE_1:
    TRANSITION_PROBABILITIES:
      MUST_BE_NONNEGATIVE

  RULE_2:
    EACH_TRANSITION_MATRIX_ROW:
      MUST_SUM_TO_ONE

  RULE_3:
    MARKOV_PROPERTY:
      MUST_HOLD_FOR_DEFINED_PROCESS

  RULE_4:
    STATIONARY_DISTRIBUTION:
      MUST_SATISFY:
        π = π P

  RULE_5:
    LONG_RUN_CONVERGENCE:
      MUST_NOT_BE_ASSUMED
      WITHOUT_REQUIRED_CHAIN_CONDITIONS

  RULE_6:
    MCMC_OUTPUT:
      MUST_ACCOUNT_FOR:
        BURN_IN
        MIXING
        AUTOCORRELATION
        CONVERGENCE_DIAGNOSTICS

CONFIDENCE:
  ontology_identity: 0.99
  markov_property: 0.99
  transition_structure: 0.99
  stationary_distribution_structure: 0.99
  bayesian_mcmc_connection: 0.99
  long_run_conditions: 0.98

UPDATE_MODEL:
  IF:
    NEW_TRANSITION_DATA_ARRIVES

  THEN:
    OPTIONAL_REESTIMATE:
      TRANSITION_PROBABILITIES
      TRANSITION_MATRIX

  IF:
    CURRENT_STATE_CHANGES

  THEN:
    UPDATE:
      CURRENT_STATE
      STATE_DISTRIBUTION

  IF:
    MODEL_STRUCTURE_CHANGES

  THEN:
    REVALIDATE:
      STATE_SPACE
      MARKOV_PROPERTY
      TRANSITION_MATRIX
      COMMUNICATION_CLASSES
      STATIONARY_DISTRIBUTION

  PRESERVE:
    STATE_IDENTITIES
    TRANSITION_SEMANTICS
    PROBABILITY_NORMALISATION
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_STATE_SPACE
    - IDENTIFY_CURRENT_STATE_OR_INITIAL_DISTRIBUTION
    - LOAD_TRANSITION_PROBABILITIES
    - VALIDATE_MARKOV_PROPERTY
    - VALIDATE_TRANSITION_MATRIX
    - PROPAGATE_STATE_DISTRIBUTION
    - CLASSIFY_STATES_IF_REQUIRED
    - TEST_STATIONARITY_IF_REQUIRED
    - ANALYSE_LONG_RUN_BEHAVIOUR
    - RETURN_PROBABILISTIC_INTERPRETATION

  constraints:
    - PRESERVE_MARKOV_CONDITIONAL_STRUCTURE
    - DO_NOT_ASSUME_INDEPENDENT_STATES
    - DO_NOT_ASSUME_STATIONARITY
    - DO_NOT_ASSUME_CONVERGENCE_WITHOUT_CONDITIONS
    - NORMALISE_TRANSITION_PROBABILITIES
    - EXPOSE_MODEL_ASSUMPTIONS

FLOW_HASH:
  canonical_entity: "markov-chain"
  namespace: "probability-statistics/bayesian-statistics"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - MARKOV_PROPERTY
    - TRANSITION_STRUCTURE
    - STATE_SPACE

END_FLOW