Markov chain

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

A stochastic model representing a sequence of states in which each transition probability depends only on the current state.

A Markov chain is a stochastic model for moving through possible states when the next transition depends only on the fully observable current state, not earlier events. section 5.2.2

State transitions

From state A, the process may move to neighboring state B according to transition probability pAB; related probabilities describe moves among A, B, and C. section 5.2.2

Markov chains support several practical uses:

• Model random search in simulated annealing, where improving solutions are accepted and some non-improving moves are accepted probabilistically. section 5.2.2
• Represent processes in stochastic optimization, economics, speech recognition, weather prediction, control systems, and web navigation through PageRank. 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.

Use the state diagram to inspect how transition probabilities connect neighboring states. section 5.2.2

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

How deep it goes

Defines the memoryless property and illustrates transitions, but does not develop formal probability theory.

Examples

Illustrates transitions among states A, B, and C and probabilistic acceptance of neighboring solutions during simulated annealing.

What you can do after

Apply it via SymPy's DiscreteMarkovChain for finite discrete-time homogeneous models.

How it connects

Connects Markov chains to simulated annealing, stochastic optimization, PageRank, control systems, and transition probabilities.

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
  Statistics Every Programmer NeedsMarkov analysis is a technique for modeling transitions among a finite set of states using transition probabilities to predict future states.
• 

  liveBookmanning.com
  Fabulous Adventures in Data Structures and AlgorithmsA Markov process is a stochastic process in which the conditional distribution of the next state depends only on the current state.
• 

  liveBookmanning.com
  Machine Learning Algorithms in DepthA Markov model is a stochastic model in which the conditional distribution of future states depends on the present state rather than the full history.

Compare how 4 books explain Markov chain →

Related concepts

• Markov decision processcontrasts with · A Markov decision process is a mathematical model of sequential decision-making defined by states, actions, probabilistic transitions, and rewards, with future dynamics depending on the current state and action.
• transition probabilityuses · 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.
• diffusion modelused by · A diffusion model is a generative model that learns to produce data by reversing a process that progressively adds noise to data.
• statehas part · State is information or a configuration describing the condition of a system, entity, or computation at a particular time and potentially influencing subsequent behavior or decisions.
• transition matrixuses · A transition matrix is a matrix whose entries represent the probabilities of moving between states in a stochastic process.

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.