Discrete-Time Discrete-Markov Process

A Discrete-Time Discrete-Markov Process is a discrete Markov process that is a discrete time process.

• AKA: Markov Chain.
• Context:
  • It can range from being a Small Markov Chain to being a Large Markov Chain.
  • It can be represented by a Markov Chain Diagram (or a Transition Matrix).
  • It can be a component of a Markov Blanket.
  • …
• Example(s):
  • a Two-State Markov Chain (with four process transitions).
  • a PageRank Algorithm.
  • …
• Counter-Example(s):
  • a Continuous Time Process.
• See: Markov Chain Algorithm, Markov Model, Stochastic Matrix, Markov Random Field, Stationary Distribution.

---

---

References

2016

• http://setosa.io/ev/markov-chains/ Markov Chains - Explained Visually

2011

• (Wikipedia, 2011) ⇒ http://en.wikipedia.org/wiki/Markov_chain
  • A 'Markov chain, named for Andrey Markov, is a mathematical system that undergoes transitions from one state to another (from a finite or countable number of possible states) in a chainlike manner. It is a random process characterized as memoryless: the next state depends only on the current state and not on the entire past. This specific kind of "memorylessness" is called the Markov property. Markov chains have many applications as statistical models of real-world processes.

    Formally, a Markov chain is a discrete (discrete-time) random process with the Markov property. Often, the term "Markov chain" is used to mean a Markov process which has a discrete (finite or countable) state-space. Usually a Markov chain would be defined for a discrete set of times (i.e. a discrete-time Markov chain) although some authors use the same terminology where "time" can take continuous values. The use of the term in Markov chain Monte Carlo methodology covers cases where the process is in discrete-time (discrete algorithm steps) with a continuous state space. The following concentrates on the discrete-time discrete-state-space case.

    A "discrete-time" random process involves a system which is in a certain state at each "step", with the state changing randomly between steps. The steps are often thought of as time, but they can equally well refer to physical distance or any other discrete measurement; formally, the steps are just the integers or natural numbers, and the random process is a mapping of these to states. The Markov property states that the conditional probability distribution for the system at the next step (and in fact at all future steps) given its current state depends only on the current state of the system, and not additionally on the state of the system at previous steps.

    Since the system changes randomly, it is generally impossible to predict the exact state of the system in the future. However, the statistical properties of the system's future can be predicted. In many applications it is these statistical properties that are important.

    The changes of state of the system are called transitions, and the probabilities associated with various state-changes are called transition probabilities. The set of all states and transition probabilities completely characterizes a Markov chain. By convention, we assume all possible states and transitions have been included in the definition of the processes, so there is always a next-state and the process goes on forever.

    A famous Markov chain is the so-called "drunkard's walk", a random walk on the number line where, at each step, the position may change by +1 or −1 with equal probability. From any position there are two possible transitions, to the next or previous integer. The transition probabilities depend only on the current position, not on the way the position was reached. For example, the transition probabilities from 5 to 4 and 5 to 6 are both 0.5, and all other transition probabilities from 5 are 0. These probabilities are independent of whether the system was previously in 4 or 6.

2009

• (WordNet, 2009) ⇒ http://wordnetweb.princeton.edu/perl/webwn?s=markov%20chain
  • S: (n) Markov chain, Markoff chain (a Markov process for which the parameter is discrete time values)
• http://www.scipy.org/Cookbook/Solving_Large_Markov_Chains
  • This page shows how to compute the stationary distribution pi of a large Markov chain. The example is a tandem of two M/M/1 queues. Generally the transition matrix P of the Markov chain is sparse, so that we can either use scipy.sparse or Pysparse. Here we demonstrate how to use both of these tools.

2003

• (Davison, 2003) ⇒ Anthony C. Davison. (2003). “Statistical Models." Cambridge University Press. ISBN:0521773393

---