Markov chain

A Markov process is a mathematical way to describe a sequence of events. These events are called a stochastic process. In this specific type of process, the future depends only on the current state. This concept is known as the Markov property. It is also frequently described as "memorylessness." This means that knowing the entire history of the system does not help you predict the future better than simply knowing where the system is right now.

In a Markovian system, the future and the past are independent once the present state is known.

To understand how these processes function, we must look at transitions. A transition is a change from one state to another. Each of these changes has an associated transition probability. These numbers tell us the likelihood of moving between specific states. A Markov process is defined by its state space and its transition matrix. The matrix organizes all the possible probabilities for every transition. Most models also begin with an initial state, which is the starting point of the sequence.

Because the system changes randomly, we cannot predict the exact next state with total certainty. However, we can use mathematics to predict the statistical properties of the system over time.

There are different ways to categorize these processes based on time and state. A discrete-time Markov chain (DTMC) moves in separate, countable steps. These steps might represent moments in time or even physical distances. On the other hand, a continuous-time Markov chain (CTMC) moves through a continuous flow of time. These are also called Markov jump processes. We can also classify them by their state space. Some processes have a countable state space, meaning the possible states can be listed. Other processes exist on a measurable or continuous state space.

While definitions can vary among mathematicians, these distinctions are essential for analysis.

History shows that many thinkers contributed to these ideas. The Russian mathematician Andrey Markov published his first paper on the subject in 1906. He wanted to prove that certain mathematical laws could work without assuming total independence. Markov even applied his theories to literature. He studied the distribution of vowels in the poem "Eugene Onegin" by Alexander Pushkin. Other researchers also explored related concepts earlier. For example, the branching process was introduced by Francis Galton and Henry William Watson in 1873. In 1912, Henri Poincaré studied how Markov chains could explain card shuffling.

In the 20th century, the theory became much more complex. Andrey Kolmogorov developed much of the early theory for continuous-time processes in 1931. He was inspired by studies of the stock market and Brownian movement. He introduced diffusion processes, which use differential equations to describe movement. Around the same time, Sydney Chapman derived the Chapman–Kolmogorov equation. This equation is vital for understanding how these processes evolve. Later, mathematicians like William Feller and Eugene Dynkin helped build the modern foundations of the field.

We can see Markov chains in many famous examples. One is the "drunkard's walk." This is a random walk on a number line. At each step, the walker moves either +1 or -1 with a probability of 0.5. The direction depends only on the current position, not on how the walker arrived there. Another example is the Wiener process, also called Brownian motion. The Poisson process is another central continuous-time process. In computer science, the Mark V. Shaney program uses a third-order Markov chain to generate text. It looks at sequences of three words to predict what word should come next.

Markov chains are incredibly significant in modern science and technology. They serve as the foundation for Markov chain Monte Carlo methods. These methods allow scientists to sample from very complex probability distributions. Because of this, they are used in Bayesian statistics and biology. They are also essential in chemistry, physics, and economics. In the world of digital technology, they are used in signal processing and speech processing. Even the way we navigate the internet relies on these ideas. The PageRank algorithm uses state diagrams to represent how users move between web pages.