Random Walk Ontology

flow "RandomWalkOntology" v4.0

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

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/stochastic-mathematics/random-walk-ontology.html"
  title: "Random Walk Ontology"
  domain: "Probability and Statistics"
  category: "Stochastic Mathematics"
  entity: RANDOM_WALK
  entity_type: DISCRETE_STOCHASTIC_PROCESS

DEFINE_RANDOM_WALK:
  RANDOM_WALK :=
    STOCHASTIC_PROCESS(
      INITIAL_STATE,
      RANDOM_INCREMENTS,
      CUMULATIVE_STATE_EVOLUTION
    )

CORE_STRUCTURE:
  INITIAL_STATE:
    S_0 := s_0

  INCREMENTS:
    X_1, X_2, ..., X_n

  PROCESS:
    S_n :=
      S_0
      + SUM[k=1..n] X_k

  RECURSION:
    S_(n+1) :=
      S_n
      + X_(n+1)

ENTITIES:
  RANDOM_WALK:
    type: STOCHASTIC_PROCESS

  POSITION:
    type: PROCESS_STATE

  STEP:
    type: RANDOM_INCREMENT

  TIME_INDEX:
    type: DISCRETE_INDEX

  STATE_SPACE:
    type: SET_OF_REACHABLE_STATES

  PATH:
    type: SEQUENCE_OF_STATES

  HITTING_TIME:
    type: RANDOM_TIME

  RETURN_TIME:
    type: RANDOM_TIME

  BOUNDARY:
    type: STATE_SPACE_CONSTRAINT

RELATIONSHIPS:
  RANDOM_WALK
    -> IS_A
    -> STOCHASTIC_PROCESS

  RANDOM_WALK
    -> HAS
    -> RANDOM_INCREMENTS

  RANDOM_INCREMENTS
    -> ACCUMULATE_TO
    -> POSITION

  POSITION_AT_n
    + NEXT_INCREMENT
    -> DETERMINES
    -> POSITION_AT_n_PLUS_1

  RANDOM_WALK
    -> GENERATES
    -> SAMPLE_PATH

  SAMPLE_PATH
    -> MAY_REACH
    -> BOUNDARY

GENERAL_RANDOM_WALK:
  process:
    S_n :=
      S_0
      + SUM[k=1..n] X_k

  increments:
    X_k:
      RANDOM_VARIABLES

  common_assumption:
    X_k:
      IID

  but:
    GENERAL_RANDOM_WALK_MODELS:
      MAY_USE:
        NON_IDENTICAL
        OR:
        DEPENDENT_INCREMENTS

SIMPLE_RANDOM_WALK:
  state_space:
    INTEGERS

  increments:
    X_k IN {-1,+1}

  probabilities:
    P(X_k=+1) := p
    P(X_k=-1) := q

  require:
    p + q = 1

  process:
    S_n :=
      S_0
      + SUM[k=1..n] X_k

SIMPLE_SYMMETRIC_RANDOM_WALK:
  parameters:
    p := 1/2
    q := 1/2

  expectation:
    E[X_k] := 0

  variance:
    Var(X_k) := 1

  if:
    S_0 = 0

  then:
    E[S_n] := 0
    Var(S_n) := n

BIASED_RANDOM_WALK:
  condition:
    p != q

  step_expectation:
    E[X_k] :=
      p - q

  position_expectation:
    E[S_n] :=
      S_0
      + n*(p-q)

  step_variance:
    Var(X_k) :=
      4*p*q

  position_variance:
    Var(S_n) :=
      4*n*p*q
    UNDER:
      IID_STEPS

DISTRIBUTION:
  SIMPLE_RANDOM_WALK:
    NUMBER_OF_UP_STEPS:
      U_n ~ BINOMIAL(n,p)

    relation:
      S_n :=
        S_0
        + 2*U_n
        - n

  probability:
    P(S_n = S_0 + 2k - n)
      =
    COMBINATION(n,k)
    * p^k
    * q^(n-k)

  for:
    k = 0,...,n

PARITY:
  SIMPLE_RANDOM_WALK:
    reachable_states_at_time_n:
      HAVE_PARITY_CONSISTENT_WITH:
        S_0 + n

  implication:
    NOT_EVERY_INTEGER_STATE:
      REACHABLE_AT_EVERY_TIME

MARKOV_PROPERTY:
  IF:
    INCREMENTS:
      INDEPENDENT_OF_PAST
    AND:
      TRANSITION_DISTRIBUTION_DEPENDS_ONLY_ON_CURRENT_STATE

  THEN:
    RANDOM_WALK:
      IS:
        MARKOV_CHAIN

  transition:
    P(S_(n+1)=j | S_n=i)

TIME_HOMOGENEITY:
  IF:
    INCREMENT_DISTRIBUTION:
      DOES_NOT_DEPEND_ON_n

  THEN:
    TRANSITION_PROBABILITIES:
      TIME_HOMOGENEOUS

MARTINGALE_PROPERTY:
  IF:
    E[X_(n+1) | F_n] := 0

  THEN:
    S_n:
      MARTINGALE
    WITH_RESPECT_TO:
      FILTRATION F_n

  SIMPLE_SYMMETRIC_CASE:
    S_n:
      MARTINGALE

DRIFT:
  DEFINE:
    mu :=
      E[X_k]
    FOR:
      IDENTICALLY_DISTRIBUTED_STEPS

  interpretation:
    mu > 0:
      POSITIVE_DRIFT

    mu = 0:
      ZERO_DRIFT

    mu < 0:
      NEGATIVE_DRIFT

VARIANCE_GROWTH:
  IID_INCREMENTS:
    Var(S_n) :=
      n * Var(X_1)
    IF:
      S_0_CONSTANT

  implication:
    STANDARD_DEVIATION:
      GROWS_AS:
        sqrt(n)

RECURRENCE:
  STATE_i:
    recurrent_if:
      RETURN_TO_i_WITH_PROBABILITY_ONE

  transient_if:
    RETURN_PROBABILITY_LESS_THAN_ONE

ONE_DIMENSIONAL_SYMMETRIC_RANDOM_WALK:
  property:
    RECURRENT = TRUE

  implication:
    RETURNS_TO_START:
      WITH_PROBABILITY_ONE

TWO_DIMENSIONAL_SIMPLE_SYMMETRIC_RANDOM_WALK:
  property:
    RECURRENT = TRUE

THREE_OR_MORE_DIMENSIONAL_SIMPLE_SYMMETRIC_RANDOM_WALK:
  property:
    TRANSIENT = TRUE

  theorem_connection:
    POLYA_RECURRENCE_THEOREM

RETURN_TIME:
  tau_return :=
    inf{
      n > 0 :
      S_n = S_0
    }

  type:
    STOPPING_TIME
    UNDER:
      NATURAL_FILTRATION

HITTING_TIME:
  FOR_STATE_OR_SET:
    A

  tau_A :=
    inf{
      n >= 0 :
      S_n IN A
    }

  role:
    MEASURE:
      FIRST_TIME_WALK_REACHES_TARGET

FIRST_PASSAGE_PROBABILITY:
  quantity:
    P(tau_A = n)

  applications:
    - BOUNDARY_CROSSING
    - RELIABILITY
    - FINANCE
    - QUEUEING

GAMBLERS_RUIN:
  state_space:
    {0,1,...,N}

  absorbing_boundaries:
    0
    N

  initial_state:
    i

  question:
    PROBABILITY_OF_HITTING_N_BEFORE_0

  symmetric_case:
    P_i(hit_N_before_0) :=
      i / N

  biased_case:
    IF:
      p != q

    THEN:
      P_i(hit_N_before_0) :=
        [
          1 - (q/p)^i
        ]
        /
        [
          1 - (q/p)^N
        ]

ABSORBING_RANDOM_WALK:
  boundary_state:
    once_reached:
      PROCESS_REMAINS_AT_BOUNDARY

REFLECTING_RANDOM_WALK:
  boundary:
    STEP_BEHAVIOUR_MODIFIED
    TO:
      PREVENT_EXIT_FROM_STATE_SPACE

RANDOM_WALK_ON_GRAPH:
  state_space:
    GRAPH_VERTICES

  transition:
    CURRENT_VERTEX
      -> RANDOMLY_SELECT
      -> NEIGHBOURING_VERTEX

  simple_graph_walk:
    probability:
      1 / DEGREE(current_vertex)
    FOR:
      EACH_NEIGHBOUR

  applications:
    - NETWORK_ANALYSIS
    - PAGERANK
    - MARKOV_CHAIN_METHODS
    - GRAPH_SAMPLING

MULTIDIMENSIONAL_RANDOM_WALK:
  state:
    S_n IN R^d
    OR:
    Z^d

  process:
    S_n :=
      S_0
      + SUM[k=1..n] X_k

  increments:
    X_k:
      VECTOR_VALUED_RANDOM_VARIABLES

CONTINUOUS_STATE_RANDOM_WALK:
  increments:
    MAY_HAVE:
      NORMAL
      UNIFORM
      HEAVY_TAILED
      OR_OTHER_DISTRIBUTIONS

  state_space:
    OFTEN:
      REAL_NUMBERS
      OR:
      VECTOR_SPACE

LAW_OF_LARGE_NUMBERS:
  IID_INCREMENTS_WITH_FINITE_MEAN:
    S_n / n
      -> E[X_1]
    ALMOST_SURELY
    UNDER:
      STRONG_LAW_CONDITIONS

CENTRAL_LIMIT_THEOREM:
  IID_INCREMENTS:
    mean := mu
    variance := sigma^2

  normalised:
    (
      S_n - S_0 - n*mu
    )
    /
    (
      sigma*sqrt(n)
    )
      -> N(0,1)
    IN_DISTRIBUTION

BROWNIAN_MOTION_CONNECTION:
  DIFFUSIVE_SCALING:
    RANDOM_WALK
      -> BROWNIAN_MOTION
    IN:
      FUNCTIONAL_LIMIT

  Donsker_theorem:
    APPROPRIATELY_CENTERED_AND_SCALED_RANDOM_WALK
      CONVERGES_IN_DISTRIBUTION_TO:
        BROWNIAN_MOTION

  distinction:
    RANDOM_WALK:
      DISCRETE_TIME

    BROWNIAN_MOTION:
      CONTINUOUS_TIME
      CONTINUOUS_PATH

RANDOM_WALK_WITH_DRIFT:
  process:
    S_n :=
      S_0
      + n*mu
      + CENTERED_RANDOM_COMPONENT

  long_run:
    DRIFT_TERM:
      DOMINATES_MEAN_POSITION

HEAVY_TAILED_RANDOM_WALK:
  increments:
    HEAVY_TAILED

  consequence:
    EXTREME_STEPS:
      MORE_PROBABLE
    THAN:
      LIGHT_TAILED_INCREMENT_MODELS

  possible_limit:
    STABLE_LEVY_PROCESS
    UNDER:
      APPROPRIATE_SCALING_AND_DOMAIN_OF_ATTRACTION

SIMULATION:
  INPUT:
    INITIAL_STATE
    STEP_DISTRIBUTION
    NUMBER_OF_STEPS

  PROCESS:
    SET S_0
      -> FOR n=1..N:
           DRAW X_n
           SET S_n := S_(n-1) + X_n
           RECORD S_n

  OUTPUT:
    SAMPLE_PATH

MONTE_CARLO_CONNECTION:
  RANDOM_WALKS:
    USED_IN:
      - MARKOV_CHAIN_MONTE_CARLO
      - RANDOM_WALK_METROPOLIS
      - STOCHASTIC_SIMULATION

RANDOM_WALK_METROPOLIS:
  proposal:
    theta_star :=
      theta_current
      + epsilon

  where:
    epsilon:
      SYMMETRIC_RANDOM_INCREMENT

  acceptance:
    DETERMINED_BY:
      METROPOLIS_RULE

APPLICATIONS:
  RANDOM_WALK
    -> SUPPORTS
    -> STOCHASTIC_MODELLING

  RANDOM_WALK
    -> SUPPORTS
    -> FINANCIAL_MODELLING

  RANDOM_WALK
    -> SUPPORTS
    -> PHYSICS

  RANDOM_WALK
    -> SUPPORTS
    -> ECOLOGY

  RANDOM_WALK
    -> SUPPORTS
    -> NETWORK_ANALYSIS

  RANDOM_WALK
    -> SUPPORTS
    -> MONTE_CARLO_METHODS

  RANDOM_WALK
    -> SUPPORTS
    -> QUEUEING_AND_RELIABILITY

MODEL_CONNECTIONS:
  RANDOM_WALK
    -> CONNECTS_TO
    -> STOCHASTIC_PROCESS

  RANDOM_WALK
    -> CONNECTS_TO
    -> MARKOV_CHAIN

  RANDOM_WALK
    -> CONNECTS_TO
    -> MARTINGALE

  RANDOM_WALK
    -> CONNECTS_TO
    -> BROWNIAN_MOTION

  RANDOM_WALK
    -> CONNECTS_TO
    -> CENTRAL_LIMIT_THEOREM

  RANDOM_WALK
    -> CONNECTS_TO
    -> FIRST_PASSAGE_TIME

SEMANTIC_EQUIVALENCE:
  "random walk"
    ~= "cumulative stochastic process generated by random increments"

  "simple random walk"
    ~= "random walk with unit positive or negative steps"

  "symmetric random walk"
    ~= "zero-drift equal-probability simple random walk"
    IN:
      STANDARD_ONE_DIMENSIONAL_CONTEXT

  EXCLUDE_EQUIVALENCE:
    RANDOM_WALK != BROWNIAN_MOTION
    RANDOM_WALK != GENERIC_MARKOV_CHAIN
    RANDOM_WALK != INDEPENDENT_SEQUENCE
    RECURRENCE != STATIONARITY
    ZERO_DRIFT != ZERO_VARIANCE
    INDEPENDENT_INCREMENTS != INDEPENDENT_POSITIONS

VALIDATION_RULES:
  RULE_1:
    INITIAL_STATE:
      MUST_BE:
        DEFINED

  RULE_2:
    INCREMENT_DISTRIBUTION:
      MUST_BE:
        DEFINED

  RULE_3:
    DEPENDENCE_BETWEEN_INCREMENTS:
      MUST_BE:
        EXPLICIT

  RULE_4:
    SIMPLE_RANDOM_WALK:
      MUST_SATISFY:
        p + q = 1

  RULE_5:
    REACHABLE_STATES:
      MUST_RESPECT:
        STEP_STRUCTURE
        PARITY
        BOUNDARIES

  RULE_6:
    MARKOV_PROPERTY:
      MUST_NOT_BE_ASSUMED:
        IF_INCREMENT_DEPENDENCE_INVALIDATES_IT

  RULE_7:
    BOUNDARY_BEHAVIOUR:
      MUST_BE:
        EXPLICITLY_DEFINED

  RULE_8:
    RANDOM_WALK:
      MUST_NOT_BE_CONFUSED_WITH:
        CONTINUOUS_BROWNIAN_MOTION

CONFIDENCE:
  ontology_identity: 0.99
  random_walk_definition: 0.99
  simple_walk_structure: 0.99
  markov_relationship: 0.99
  recurrence_structure: 0.99
  brownian_limit_relationship: 0.99
  first_passage_structure: 0.98

UPDATE_MODEL:
  IF:
    NEW_STEP_OCCURS

  THEN:
    DRAW_OR_OBSERVE:
      NEW_INCREMENT

    UPDATE:
      CURRENT_POSITION
      PATH_HISTORY
      TIME_INDEX

  IF:
    STEP_DISTRIBUTION_CHANGES

  THEN:
    UPDATE:
      DRIFT
      VARIANCE
      TRANSITION_STRUCTURE

    REVALIDATE:
      MARKOV_PROPERTY
      RECURRENCE_PROPERTIES

  IF:
    BOUNDARY_ADDED_OR_CHANGED

  THEN:
    UPDATE:
      STATE_SPACE
      TRANSITION_RULES
      HITTING_PROBABILITIES

  PRESERVE:
    INITIAL_STATE
    STEP_HISTORY
    TIME_ORDER
    INCREMENT_DISTRIBUTION
    BOUNDARY_RULES
    RANDOM_SEED_WHEN_RECORDED
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_INITIAL_STATE
    - IDENTIFY_TIME_INDEX
    - IDENTIFY_STATE_SPACE
    - IDENTIFY_INCREMENT_DISTRIBUTION
    - IDENTIFY_INCREMENT_DEPENDENCE
    - IDENTIFY_BOUNDARY_CONDITIONS
    - COMPUTE_DRIFT_AND_VARIANCE
    - TEST_MARKOV_OR_MARTINGALE_PROPERTIES_IF_REQUIRED
    - COMPUTE_HITTING_OR_RETURN_QUANTITIES_IF_REQUIRED
    - APPLY_LIMIT_THEOREMS_IF_REQUIRED
    - SIMULATE_PATH_IF_REQUIRED
    - RETURN_RANDOM_WALK_INTERPRETATION

  constraints:
    - PRESERVE_INCREMENT_STRUCTURE
    - PRESERVE_TIME_ORDER
    - DO_NOT_EQUATE_INDEPENDENT_INCREMENTS_WITH_INDEPENDENT_POSITIONS
    - DISTINGUISH_RANDOM_WALK_FROM_BROWNIAN_MOTION
    - RESPECT_STATE_SPACE_AND_BOUNDARIES
    - EXPOSE_DRIFT_AND_STEP_DISTRIBUTION
    - PRESERVE_DATA_PROVENANCE

FLOW_HASH:
  canonical_entity: "random-walk"
  namespace: "probability-statistics/stochastic-mathematics"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - RANDOM_INCREMENTS
    - CUMULATIVE_STATE_EVOLUTION
    - DISCRETE_TIME_STRUCTURE

END_FLOW