Markov property

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

The property of a stochastic process whereby the distribution of the next state depends only on the current state and not on earlier states.

The Markov property describes a memoryless random process: the next state depends only on the current fully observable state, not on earlier events. A Markov chain models these possible moves with transition probabilities between states. section 5.2.2

State transitions

For states A, B, and C, moving from A to B is governed by a transition probability such as pAB. Earlier states do not affect that probability once the current state is known. Simulated annealing uses this idea to move between candidate solutions, always accepting improvements while sometimes accepting non-improvements to avoid local minima. section 5.2.2

Markov chain—p_AB, p_BA, p_BC, and p_CB are transition probabilities between the states A, B, and C.

A state-transition diagram makes memorylessness concrete by showing probabilities between neighboring states. section 5.2.2

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Defines memorylessness, illustrates transition probabilities, and connects the idea to implementation without developing a formal proof.

Examples

Uses transitions among states A, B, and C plus improving and non-improving candidate solutions in simulated annealing.

What you can do after

Evaluate/understand whether a stochastic state transition depends only on the currently observed state.

How it connects

Connects Markov chains with stochastic optimization, simulated annealing, transition probability, PageRank, and greedy algorithms.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Causal AIA Markov assumption is the assumption that each variable in an ordered chain depends only on the variable immediately preceding it, conditional on that predecessor.
• 

  liveBookmanning.com
  Build a Robo-Advisor with Python (From Scratch)The Markov property is the condition that the probabilities of future states depend on the current state and action but not on earlier history.

Compare how 3 books explain Markov property →

Related concepts

• causal Markov propertyequivalent to · The causal Markov property states that each variable is conditionally independent of its nondescendants given its causal parents in a directed acyclic graph.
• dynamic programminguses · Dynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions.
• Markov chainconfigures · A Markov chain is a stochastic process of states whose transition probabilities depend on the current state rather than the full preceding history.
• transition probabilityconfigures · A transition probability is the conditional probability that a stochastic process moves to a specified next state, possibly given its current state and an action.
• statistical modelingconfigures · Statistical modeling is the use of mathematical or probabilistic models to represent patterns, relationships, or variability in data for description, inference, or prediction.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.