document_title: Markov chain

question_text: markov chains with finite and countable state space

question_tokens: markov chains with finite and countable state space

text: Markov chain

text: Introduction[edit]

text: A Markov chain is a stochastic process with the Markov property. The term "Markov chain" refers to the sequence of random variables such a process moves through, with the Markov property defining serial dependence only between adjacent periods (as in a "chain"). It can thus be used for describing systems that follow a chain of linked events, where what happens next depends only on the current state of the system.

text: The system's state space and time parameter index need to be specified. The following table gives an overview of the different instances of Markov processes for different levels of state space generality and for discrete time v. continuous time:

text:
Countable state space

Continuous or general state space

Discrete-time

(discrete-time) Markov chain on a countable or finite state space

Harris chain (Markov chain on a general state space)

Continuous-time

Continuous-time Markov process or Markov jump process

Any continuous stochastic process with the Markov property, e.g., the Wiener process

text: Note that there is no definitive agreement in the literature on the use of some of the terms that signify special cases of Markov processes. Usually the term "Markov chain" is reserved for a process with a discrete set of times, i.e. a discrete-time Markov chain (DTMC),[31][31] but a few authors use the term "Markov process" to refer to a continuous-time Markov chain (CTMC) without explicit mention.[32][33][34] In addition, there are other extensions of Markov processes that are referred to as such but do not necessarily fall within any of these four categories (see Markov model). Moreover, the time index need not necessarily be real-valued; like with the state space, there are conceivable processes that move through index sets with other mathematical constructs. Notice that the general state space continuous-time Markov chain is general to such a degree that it has no designated term.

text: While the time parameter is usually discrete, the state space of a Markov chain does not have any generally agreed-on restrictions: the term may refer to a process on an arbitrary state space.[35] However, many applications of Markov chains employ finite or countably infinite state spaces, which have a more straightforward statistical analysis. Besides time-index and state-space parameters, there are many other variations, extensions and generalizations (see Variations). For simplicity, most of this article concentrates on the discrete-time, discrete state-space case, unless mentioned otherwise.

text: The changes of state of the system are called transitions. The probabilities associated with various state changes are called transition probabilities. The process is characterized by a state space, a transition matrix describing the probabilities of particular transitions, and an initial state (or initial distribution) across the state space.  By convention, we assume all possible states and transitions have been included in the definition of the process, so there is always a next state, and the process does not terminate.

text: 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 moments in time, but they can equally well refer to physical distance or any other discrete measurement.  Formally, the steps are 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) depends only on the current state of the system, and not additionally on the state of the system at previous steps.

text: Since the system changes randomly, it is generally impossible to predict with certainty the state of a Markov chain at a given point 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.

text: 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 manner in which 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.

text: Another example is the dietary habits of a creature who eats only grapes, cheese, or lettuce, and whose dietary habits conform to the following rules:

text:
It eats exactly once a day.
If it ate cheese today, tomorrow it will eat lettuce or grapes with equal probability.
If it ate grapes today, tomorrow it will eat grapes with probability 1/10, cheese with probability 4/10 and lettuce with probability 5/10.
If it ate lettuce today, tomorrow it will eat grapes with probability 4/10 or cheese with probability 6/10. It will not eat lettuce again tomorrow.

text: This creature's eating habits can be modeled with a Markov chain since its choice tomorrow depends solely on what it ate today, not what it ate yesterday or any other time in the past. One statistical property that could be calculated is the expected percentage, over a long period, of the days on which the creature will eat grapes.

text: A series of independent events (for example, a series of coin flips) satisfies the formal definition of a Markov chain. However, the theory is usually applied only when the probability distribution of the next step depends non-trivially on the current state.

text: History[edit]

text: Andrey Markov studied Markov chains in the early 20th century.  Markov was interested in studying an extension of independent random sequences, motivated by a disagreement with Pavel Nekrasov who claimed independence was necessary for the weak law of large numbers to hold.[36] In his first paper on Markov chains, published in 1906, Markov showed that under certain conditions the average outcomes of the Markov chain would converge to a fixed vector of values, so proving a weak law of large numbers without the independence assumption,[9][10][11] which had been commonly regarded as a requirement for such mathematical laws to hold.[11] Markov later used Markov chains to study the distribution of vowels in Eugene Onegin, written by Alexander Pushkin, and proved a central limit theorem for such chains.[9]

text: In 1912 Poincaré studied Markov chains on finite groups with an aim to study card shuffling.  Other early uses of Markov chains include a diffusion model, introduced by Paul and Tatyana Ehrenfest in 1907, and a branching process, introduced by Francis Galton and Henry William Watson in 1873, preceding the work of Markov.[9][10] After the work of Galton and Watson, it was later revealed that their branching process had been independently discovered and studied around three decades earlier by Irénée-Jules Bienaymé.[37] Starting in 1928, Maurice Fréchet became interested in Markov chains, eventually resulting in him publishing in 1938 a detailed study on Markov chains.[9][38]

text: Andrei Kolmogorov developed in a 1931 paper a large part of the early theory of continuous-time Markov processes.[39][40] Kolmogorov was partly inspired by Louis Bachelier's 1900 work on fluctuations in the stock market as well as Norbert Wiener's work on Einstein's model of Brownian movement.[39][41] He introduced and studied a particular set of Markov processes known as diffusion processes, where he derived a set of differential equations describing the processes.[39][42] Independent of Kolmogorov's work, Sydney Chapman derived in a 1928 paper an equation, now called the Chapman–Kolmogorov equation, in a less mathematically rigorous way than Kolmogorov, while studying Brownian movement.[43] The differential equations are now called the Kolmogorov equations[44] or the Kolmogorov–Chapman equations.[45] Other mathematicians who contributed significantly to the foundations of Markov processes include William Feller, starting in 1930s, and then later Eugene Dynkin, starting in the 1950s.[40]

text: Examples[edit]

text: Gambling[edit]

text:
Suppose that you start with $10, and you wager $1 on an unending, fair, coin toss indefinitely, or until you lose all of your money. If

X

n

{\displaystyle X_{n}}

 represents the number of dollars you have after n tosses, with

X

0

=
10

{\displaystyle X_{0}=10}

, then the sequence

{

X

n

:
n
∈

N

}

{\displaystyle \{X_{n}:n\in \mathbb {N} \}}

 is a Markov process. If I know that you have $12 now, then it would be expected that with even odds, you will either have $11 or $13 after the next toss. This guess is not improved by the added knowledge that you started with $10, then went up to $11, down to $10, up to $11, and then to $12.

text: The process described here is a Markov chain on a countable state space that follows a random walk.

text: A birth-death process[edit]

text:
If one pops one hundred kernels of popcorn in an oven, each kernel popping at an independent exponentially-distributed time, then this would be a continuous-time Markov process. If

X

t

{\displaystyle X_{t}}

 denotes the number of kernels which have popped up to time t, the problem can be defined as finding the number of kernels that will pop in some later time. The only thing one needs to know is the number of kernels that have popped prior to the time "t". It is not necessary to know when they popped, so knowing

X

t

{\displaystyle X_{t}}

 for previous times "t" is not relevant.

text: The process described here is an approximation of a Poisson point process - Poisson processes are also Markov processes.

text: A non-Markov example[edit]

text:
Suppose that there is a coin purse containing five quarters (each worth 25¢), five dimes (each worth 10¢), and five nickels (each worth 5¢), and one-by-one, coins are randomly drawn from the purse and are set on a table. If

X

n

{\displaystyle X_{n}}

 represents the total value of the coins set on the table after n draws, with

X

0

=
0

{\displaystyle X_{0}=0}

, then the sequence

{

X

n

:
n
∈

N

}

{\displaystyle \{X_{n}:n\in \mathbb {N} \}}

 is not a Markov process.

text:
To see why this is the case, suppose that in the first six draws, all five nickels and a quarter are drawn. Thus

X

6

=
$
0.50

{\displaystyle X_{6}=\$0.50}

. If we know not just

X

6

{\displaystyle X_{6}}

, but the earlier values as well, then we can determine which coins have been drawn, and we know that the next coin will not be a nickel; so we can determine that

X

7

≥
$
0.60

{\displaystyle X_{7}\geq \$0.60}

 with probability 1. But if we do not know the earlier values, then based only on the value

X

6

{\displaystyle X_{6}}

 we might guess that we had drawn four dimes and two nickels, in which case it would certainly be possible to draw another nickel next. Thus, our guesses about

X

7

{\displaystyle X_{7}}

 are impacted by our knowledge of values prior to

X

6

{\displaystyle X_{6}}

.

text:
However, it is possible to model this scenario as a Markov process.  Instead of defining

X

n

{\displaystyle X_{n}}

 to represent the total value of the coins on the table, one could define

X

n

{\displaystyle X_{n}}

 to represent the count of the various coin types on the table.  For instance,

X

6

=
1
,
0
,
5

{\displaystyle X_{6}=1,0,5}

 could be defined to represent the state where there is one quarter, zero dimes, and five nickels on the table.  This new model would be represented by 216 possible states (that is, 6x6x6 states, since each of the three coin types could have zero to five coins on the table), and is more complex than the previous (total value) model which has 41 possible states (that is, the values ranging from 0¢ to 200¢, counting by 5¢).

text: Markov property[edit]

text: Formal definition[edit]

text: Discrete-time Markov chain[edit]

text: A discrete-time Markov chain is a sequence of random variables X1, X2, X3, ... with the Markov property, namely that the probability of moving to the next state depends only on the present state and not on the previous states

text: The possible values of Xi form a countable set S called the state space of the chain.

text:
Markov chains are often described by a sequence of directed graphs, where the edges of graph n are labeled by the probabilities of going from one state at time n to the other states at time n + 1,

Pr
(

X

n
+
1

=
x
∣

X

n

=

x

n

)

{\displaystyle \Pr(X_{n+1}=x\mid X_{n}=x_{n})}

. The same information is represented by the transition matrix from time n to time n + 1. However, Markov chains are frequently assumed to be time-homogeneous (see variations below), in which case the graph and matrix are independent of n and are thus not presented as sequences.

text:
These descriptions highlight the structure of the Markov chain that is independent of the initial distribution

Pr
(

X

1

=

x

1

)

{\displaystyle \Pr(X_{1}=x_{1})}

. When time-homogeneous, the chain can be interpreted as a state machine assigning a probability of hopping from each vertex or state to an adjacent one. The probability

Pr
(

X

n

=
x
∣

X

1

=

x

1

)

{\displaystyle \Pr(X_{n}=x\mid X_{1}=x_{1})}

 of the machine's state can be analyzed as the statistical behavior of the machine with an element

x

1

{\displaystyle x_{1}}

 of the state space as input, or as the behavior of the machine with the initial distribution

Pr
(

X

1

=
y
)
=
[

x

1

=
y
]

{\displaystyle \Pr(X_{1}=y)=[x_{1}=y]}

 of states as input, where

[
P
]

{\displaystyle [P]}

 is the Iverson bracket.

text:
The fact that some sequences of states might have zero probability of occurring corresponds to a graph with multiple connected components, where we omit edges that would carry a zero transition probability. For example, if a has a nonzero probability of going to b, but a and x lie in different connected components of the graph, then

Pr
(

X

n
+
1

=
b
∣

X

n

=
a
)

{\displaystyle \Pr(X_{n+1}=b\mid X_{n}=a)}

 is defined, while

Pr
(

X

n
+
1

=
b
∣

X

1

=
x
,
…
,

X

n

=
a
)

{\displaystyle \Pr(X_{n+1}=b\mid X_{1}=x,\ldots ,X_{n}=a)}

 is not.

text: Variations[edit]

text: Time-homogeneous Markov chains (or stationary Markov chains) are processes where

text: A Markov chain with memory (or a Markov chain of order m)

text: where m is finite, is a process satisfying

text: Example[edit]

text: A state diagram for a simple example is shown in the figure on the right, using a directed graph to picture the state transitions. The states represent whether a hypothetical stock market is exhibiting a bull market, bear market, or stagnant market trend during a given week.  According to the figure, a bull week is followed by another bull week 90% of the time, a bear week 7.5% of the time, and a stagnant week the other 2.5% of the time. Labelling the state space {1 = bull, 2 = bear, 3 = stagnant} the transition matrix for this example is

text: The distribution over states can be written as a stochastic row vector x with the relation x(n + 1) = x(n)P. So if at time n the system is in state x(n), then three time periods later, at time n + 3 the distribution is

text: In particular, if at time n the system is in state 2 (bear), then at time n + 3 the distribution is

text: Using the transition matrix it is possible to calculate, for example, the long-term fraction of weeks during which the market is stagnant, or the average number of weeks it will take to go from a stagnant to a bull market. Using the transition probabilities, the steady-state probabilities indicate that 62.5% of weeks will be in a bull market, 31.25% of weeks will be in a bear market and 6.25% of weeks will be stagnant, since:

text:
A thorough development and many examples can be found in the on-line monograph
Meyn & Tweedie 2005.[46]

text: A finite state machine can be used as a representation of a Markov chain. Assuming a sequence of independent and identically distributed input signals (for example, symbols from a binary alphabet chosen by coin tosses), if the machine is in state y at time n, then the probability that it moves to state x at time n + 1 depends only on the current state.

text: Continuous-time Markov chain[edit]

text: A continuous-time Markov chain (Xt)t ≥ 0 is defined by a finite or countable state space S, a transition rate matrix Q with dimensions equal to that of the state space and initial probability distribution defined on the state space. For i ≠ j, the elements qij are non-negative and describe the rate of the process transitions from state i to state j. The elements qii are chosen such that each row of the transition rate matrix sums to zero, while the row-sums of a probability transition matrix in a (discrete) Markov chain are all equal to one.

text: There are three equivalent definitions of the process.[47]

text: Infinitesimal definition[edit]

text: Let Xt be the random variable describing the state of the process at time t, and assume that the process is in a state i at time t.

text: Then, knowing Xt = i,   Xt + h is independent of previous values (Xs : s< t), and as h → 0 for all j and for all t:

text:
using the little-o notation.
The qij can be seen as measuring how quickly the transition from i to j happens

text: Jump chain/holding time definition[edit]

text: Define a discrete-time Markov chain Yn to describe the nth jump of the process and variables S1, S2, S3, ... to describe holding times in each of the states where Si follows the exponential distribution with rate parameter −qYiYi.

text: Transition probability definition[edit]

text: For any value n = 0, 1, 2, 3, ... and times indexed up to this value of n: t0, t1, t2, ... and all states recorded at these times i0, i1, i2, i3, ... it holds that

text: where pij is the solution of the forward equation (a first-order differential equation)

text: with initial condition P(0) is the identity matrix.

text: Transient evolution[edit]

text: The probability of going from state i to state j in n time steps is

text: and the single-step transition is

text: For a time-homogeneous Markov chain:

text: and

text: The n-step transition probabilities satisfy the Chapman–Kolmogorov equation, that for any k such that 0 < k < n,

text: where S is the state space of the Markov chain.

text: The marginal distribution Pr(Xn = x) is the distribution over states at time n. The initial distribution is Pr(X0 = x). The evolution of the process through one time step is described by

text: Note: The superscript (n) is an index and not an exponent.

text: Properties[edit]

text: Reducibility[edit]

text: A Markov chain is said to be irreducible if it is possible to get to any state from any state. The following explains this definition more formally.

text: A state j is said to be accessible from a state i (written i → j) if a system started in state i has a non-zero probability of transitioning into state j at some point. Formally, state j is accessible from state i if there exists an integer nij ≥ 0 such that

text:
This integer is allowed to be different for each pair of states, hence the subscripts in nij.
Allowing n to be zero means that every state is accessible from itself by definition. The accessibility relation is reflexive and transitive, but not necessarily symmetric.

text: A state i is said to communicate with state j (written i ↔ j) if both i → j and j → i. A communicating class is a maximal set of states C such that every pair of states in C communicates with each other. Communication is an equivalence relation, and communicating classes are the equivalence classes of this relation.

text: A communicating class is closed if the probability of leaving the class is zero, namely if i is in C but j is not, then j is not accessible from i. The set of communicating classes forms a directed, acyclic graph by inheriting the arrows from the original state space. A communicating class is closed if and only if it has no outgoing arrows in this graph.

text: A state i is said to be essential or final if for all j such that i → j it is also true that j → i. A state i is inessential if it is not essential.[48] A state is final if and only if its communicating class is closed.

text: A Markov chain is said to be irreducible if its state space is a single communicating class; in other words, if it is possible to get to any state from any state.

text: Periodicity[edit]

text: A state i has period k if any return to state i must occur in multiples of k time steps. Formally, the period of a state is defined as

text: (where "gcd" is the greatest common divisor) provided that this set is not empty. Otherwise the period is not defined.  Note that even though a state has period k, it may not be possible to reach the state in k steps. For example, suppose it is possible to return to the state in {6, 8, 10, 12, ...} time steps; k would be 2, even though 2 does not appear in this list.

text:
If k = 1, then the state is said to be aperiodic.
Otherwise (k > 1), the state is said to be periodic with period k.  A Markov chain is aperiodic if every state is aperiodic. An irreducible Markov chain only needs one aperiodic state to imply all states are aperiodic.

text: Every state of a bipartite graph has an even period.

text: Transience and recurrence[edit]

text: A state i is said to be transient if, given that we start in state i, there is a non-zero probability that we will never return to i. Formally, let the random variable Ti be the first return time to state i (the "hitting time"):

text: The number

text:
is the probability that we return to state i for the first time after n steps.
Therefore, state i is transient if

text:
State i is recurrent (or persistent) if it is not transient.
Recurrent states are guaranteed (with probability 1) to have a finite hitting time.
Recurrence and transience are class properties, that is, they either hold or do not hold equally for all members of a communicating class.

text: Mean recurrence time[edit]

text:
Even if the hitting time is finite with probability 1, it need not have a finite expectation.
The mean recurrence time at state i is the expected return time Mi:

text: State i is positive recurrent (or non-null persistent) if Mi is finite; otherwise, state i is null recurrent (or null persistent).

text: Expected number of visits[edit]

text: It can be shown that a state i is recurrent if and only if the expected number of visits to this state is infinite, i.e.,

text: Absorbing states[edit]

text: A state i is called absorbing if it is impossible to leave this state. Therefore, the state i is absorbing if and only if

text: If every state can reach an absorbing state, then the Markov chain is an absorbing Markov chain.

text: Ergodicity[edit]

text: A state i is said to be ergodic if it is aperiodic and positive recurrent. In other words, a state i is ergodic if it is recurrent, has a period of 1, and has finite mean recurrence time. If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.

text: It can be shown that a finite state irreducible Markov chain is ergodic if it has an aperiodic state.  More generally, a Markov chain is ergodic if there is a number N such that any state can be reached from any other state in any number of steps greater than or equal to a number N. In case of a fully connected transition matrix, where all transitions have a non-zero probability, this condition is fulfilled with N = 1.

text: A Markov chain with more than one state and just one out-going transition per state is either not irreducible or not aperiodic, hence cannot be ergodic.

text: Steady-state analysis and limiting distributions[edit]

text:
If the Markov chain is a time-homogeneous Markov chain, so that the process is described by a single, time-independent matrix

p

i
j

{\displaystyle p_{ij}}

, then the vector

π

{\displaystyle {\boldsymbol {\pi }}}

 is called a stationary distribution (or invariant measure) if

∀
j
∈
S

{\displaystyle \forall j\in S}

 it satisfies

text:
An irreducible chain has a positive stationary distribution (a stationary distribution such that

∀
i
,

π

i

>
0

{\displaystyle \forall i,\pi _{i}>0}

) if and only if all of its states are positive recurrent.[49] In that case, π is unique and is related to the expected return time:

text:
where

C

{\displaystyle C}

 is the normalizing constant. Further, if the positive recurrent chain is both irreducible and aperiodic, it is said to have a limiting distribution; for any i and j,

text:
Note that there is no assumption on the starting distribution; the chain converges to the stationary distribution regardless of where it begins. Such

π

{\displaystyle \pi }

 is called the equilibrium distribution of the chain.

text:
If a chain has more than one closed communicating class, its stationary distributions will not be unique (consider any closed communicating class

C

i

{\displaystyle C_{i}}

 in the chain; each one will have its own unique stationary distribution

π

i

{\displaystyle \pi _{i}}

. Extending these distributions to the overall chain, setting all values to zero outside the communication class, yields that the set of invariant measures of the original chain is the set of all convex combinations of the

π

i

{\displaystyle \pi _{i}}

's). However, if a state j is aperiodic, then

text: and for any other state i, let fij be the probability that the chain ever visits state j if it starts at i,

text: If a state i is periodic with period k > 1 then the limit

text: does not exist, although the limit

text: does exist for every integer r.

text: Steady-state analysis and the time-inhomogeneous Markov chain[edit]

text:
A Markov chain need not necessarily be time-homogeneous to have an equilibrium distribution.  If there is a probability distribution over states

π

{\displaystyle {\boldsymbol {\pi }}}

 such that

text:
for every state j and every time n then

π

{\displaystyle {\boldsymbol {\pi }}}

 is an equilibrium distribution of the Markov chain.  Such can occur in Markov chain Monte Carlo (MCMC) methods in situations where a number of different transition matrices are used, because each is efficient for a particular kind of mixing, but each matrix respects a shared equilibrium distribution.

text: Finite state space[edit]

text: If the state space is finite, the transition probability distribution can be represented by a matrix, called the transition matrix, with the (i, j)th element of P equal to

text: Since each row of P sums to one and all elements are non-negative, P is a right stochastic matrix.

text: Stationary distribution relation to eigenvectors and simplices[edit]

text: A stationary distribution π is a (row) vector, whose entries are non-negative and sum to 1, is unchanged by the operation of transition matrix P on it and so is defined by

text: By comparing this definition with that of an eigenvector we see that the two concepts are related and that

text:
is a normalized (

∑

i

π

i

=
1

{\displaystyle \textstyle \sum _{i}\pi _{i}=1}

) multiple of a left eigenvector  e of the transition matrix PT with an eigenvalue of 1. If there is more than one unit eigenvector then a weighted sum of the corresponding stationary states is also a stationary state. But for a Markov chain one is usually more interested in a stationary state that is the limit of the sequence of distributions for some initial distribution.

text:
The values of a stationary distribution

π

i

{\displaystyle \textstyle \pi _{i}}

 are associated with the state space of P and its eigenvectors have their relative proportions preserved. Since the components of π are positive and the constraint that their sum is unity can be rewritten as

∑

i

1
⋅

π

i

=
1

{\displaystyle \textstyle \sum _{i}1\cdot \pi _{i}=1}

 we see that the dot product of π with a vector whose components are all 1 is unity and that π lies on a simplex.

text: Time-homogeneous Markov chain with a finite state space[edit]

text: This section includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this section by introducing more precise citations. (February 2012) (Learn how and when to remove this template message)

text: If the Markov chain is time-homogeneous, then the transition matrix P is the same after each step, so the k-step transition probability can be computed as the k-th power of the transition matrix, Pk.

text: If the Markov chain is irreducible and aperiodic, then there is a unique stationary distribution π. Additionally, in this case Pk converges to a rank-one matrix in which each row is the stationary distribution π, that is,

text:
where 1 is the column vector with all entries equal to 1. This is stated by the Perron–Frobenius theorem. If, by whatever means,

lim

k
→
∞

P

k

{\displaystyle \scriptstyle \lim _{k\to \infty }\mathbf {P} ^{k}}

 is found, then the stationary distribution of the Markov chain in question can be easily determined for any starting distribution, as will be explained below.

text:
For some stochastic matrices P, the limit

lim

k
→
∞

P

k

{\displaystyle \scriptstyle \lim \limits _{k\to \infty }\mathbf {P} ^{k}}

 does not exist while the stationary distribution does, as shown by this example:

text: Note that this example illustrates a periodic Markov chain.

text:
Because there are a number of different special cases to consider, the process of finding this limit if it exists can be a lengthy task. However, there are many techniques that can assist in finding this limit. Let P be an n×n matrix, and define

Q

=

lim

k
→
∞

P

k

.

{\displaystyle \scriptstyle \mathbf {Q} =\lim _{k\to \infty }\mathbf {P} ^{k}.}

text: It is always true that

text: Subtracting Q from both sides and factoring then yields

text: where In is the identity matrix of size n, and 0n,n is the zero matrix of size n×n. Multiplying together stochastic matrices always yields another stochastic matrix, so Q must be a stochastic matrix (see the definition above). It is sometimes sufficient to use the matrix equation above and the fact that Q is a stochastic matrix to solve for Q. Including the fact that the sum of each the rows in P is 1, there are n+1 equations for determining n unknowns, so it is computationally easier if on the one hand one selects one row in Q and substitute each of its elements by one, and on the other one substitute the corresponding element (the one in the same column) in the vector 0, and next left-multiply this latter vector by the inverse of transformed former matrix to find Q.

text: Here is one method for doing so: first, define the function f(A) to return the matrix A with its right-most column replaced with all 1's. If [f(P − In)]−1 exists then[50][citation needed]

text: One thing to notice is that if P has an element Pi,i on its main diagonal that is equal to 1 and the ith row or column is otherwise filled with 0's, then that row or column will remain unchanged in all of the subsequent powers Pk. Hence, the ith row or column of Q will have the 1 and the 0's in the same positions as in P.

text: Convergence speed to the stationary distribution[edit]

text:
As stated earlier, from the equation

π

=

π

P

,

{\displaystyle {\boldsymbol {\pi }}={\boldsymbol {\pi }}\mathbf {P} ,}

 (if exists) the stationary (or steady state) distribution π is a left eigenvector of row stochastic matrix P. Then assuming that P is diagonalizable or equivalently that P has n linearly independent eigenvectors, speed of convergence is elaborated as follows. (For non-diagonalizable, i.e. defective matrices, one may start with the Jordan normal form of P and proceed with a bit more involved set of arguments in a similar way.[51])

text: Let U be the matrix of eigenvectors (each normalized to having an L2 norm equal to 1) where each column is a left eigenvector of P and let Σ be the diagonal matrix of left eigenvalues of P, i.e. Σ = diag(λ1,λ2,λ3,...,λn). Then by eigendecomposition

text: Let the eigenvalues be enumerated such that:

text:
Since P is a row stochastic matrix, its largest left eigenvalue is 1. If there is a unique stationary distribution, then the largest eigenvalue and the corresponding eigenvector is unique too (because there is no other π which solves the stationary distribution equation above). Let ui be the i-th column of U matrix, i.e. ui is the left eigenvector of P corresponding to λi. Also let x be a length n row vector that represents a valid probability distribution; since the eigenvectors ui span

R

n

,

{\displaystyle \mathbb {R} ^{n},}

 we can write

text: If we multiply x with P from right and continue this operation with the results, in the end we get the stationary distribution π. In other words, π = ui ← xPP...P = xPk as k → ∞. That means

text:
Since π = u1, π(k) approaches to π as k → ∞ with a speed in the order of λ2/λ1 exponentially. This follows because

|

λ

2

|

⩾
⋯
⩾

|

λ

n

|

,

{\displaystyle |\lambda _{2}|\geqslant \cdots \geqslant |\lambda _{n}|,}

 hence λ2/λ1 is the dominant term. Random noise in the state distribution π can also speed up this convergence to the stationary distribution.[52]

text: Reversible Markov chain[edit]

text: A Markov chain is said to be reversible if there is a probability distribution π over its states such that

text: for all times n and all states i and j. This condition is known as the detailed balance condition (some books call it the local balance equation).

text: Considering a fixed arbitrary time n and using the shorthand

text: the detailed balance equation can be written more compactly as

text: The single time-step from n to n + 1 can be thought of as each person i having πi dollars initially and paying each person j a fraction pij of it. The detailed balance condition states that upon each payment, the other person pays exactly the same amount of money back.[53] Clearly the total amount of money π each person has remains the same after the time-step, since every dollar spent is balanced by a corresponding dollar received. This can be shown more formally by the equality

text: which essentially states that the total amount of money person j receives (including from himself) during the time-step equals the amount of money he pays others, which equals all the money he initially had because it was assumed that all money is spent (i.e. pji sums to 1 over i). The assumption is a technical one, because the money not really used is simply thought of as being paid from person j to himself (i.e. pjj is not necessarily zero).

text: As n was arbitrary, this reasoning holds for any n, and therefore for reversible Markov chains π is always a steady-state distribution of Pr(Xn+1 = j | Xn = i) for every n.

text: If the Markov chain begins in the steady-state distribution, i.e., if Pr(X0 = i) = πi, then Pr(Xn = i) = πi for all n and the detailed balance equation can be written as

text: The left- and right-hand sides of this last equation are identical except for a reversing of the time indices n and n + 1.

text: Kolmogorov's criterion gives a necessary and sufficient condition for a Markov chain to be reversible directly from the transition matrix probabilities. The criterion requires that the products of probabilities around every closed loop are the same in both directions around the loop.

text: Reversible Markov chains are common in Markov chain Monte Carlo (MCMC) approaches because the detailed balance equation for a desired distribution π necessarily implies that the Markov chain has been constructed so that π is a steady-state distribution.  Even with time-inhomogeneous Markov chains, where multiple transition matrices are used, if each such transition matrix exhibits detailed balance with the desired π distribution, this necessarily implies that π is a steady-state distribution of the Markov chain.

text: Closest reversible Markov chain[edit]

text:
For any time-homogeneous Markov chain given by a transition matrix

P
∈

R

n
×
n

{\displaystyle P\in \mathbb {R} ^{n\times n}}

, any norm

|

|

⋅

|

|

{\displaystyle ||\cdot ||}

 on

R

n
×
n

{\displaystyle \mathbb {R} ^{n\times n}}

 which is induced by a scalar product, and any probability vector

π

{\displaystyle \pi }

, there exists a unique transition matrix

P

∗

{\displaystyle P^{*}}

 which is reversible according to

π

{\displaystyle \pi }

and which is closest to

P

{\displaystyle P}

 according to the norm

|

|

⋅

|

|

.

{\displaystyle ||\cdot ||.}

 The matrix

P

∗

{\displaystyle P^{*}}

 can be computed by solving a quadratic-convex optimization problem.[54] A GNU licensed Matlab script that computes the nearest reversible Markov chain can be found here.

text: For example, consider the following Markov chain:

text:
This Markov chain is not reversible. According to the Frobenius Norm the closest reversible Markov chain according to

π
=

(

1
3

,

1
3

,

1
3

)

{\displaystyle \pi =\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}

 can be computed as

text:
If we choose the probability vector randomly as

π
=

(

1
4

,

1
4

,

1
2

)

{\displaystyle \pi =\left({\frac {1}{4}},{\frac {1}{4}},{\frac {1}{2}}\right)}

, then the closest reversible Markov chain according to the Frobenius norm is approximately given by

text: Bernoulli scheme[edit]

text: A Bernoulli scheme is a special case of a Markov chain where the transition probability matrix has identical rows, which means that the next state is even independent of the current state (in addition to being independent of the past states). A Bernoulli scheme with only two possible states is known as a Bernoulli process.

text: General state space[edit]

text: For an overview of Markov chains on a general state space, see the article Markov chains on a measurable state space.

text: Harris chains[edit]

text:
Many results for Markov chains with finite state space can be generalized to chains with uncountable state space through Harris chains. The main idea is to see if there is a point in the state space that the chain hits with probability one. Generally, it is not true for continuous state space, however, we can define sets A and B along with a positive number ε and a probability
measure ρ, such that

text: Then we could collapse the sets into an auxiliary point α, and a recurrent Harris chain can be modified to contain α. Lastly, the collection of Harris chains is a comfortable level of generality, which is broad enough to contain a large number of interesting examples, yet restrictive enough to allow for a rich theory.

text: The use of Markov chains in Markov chain Monte Carlo methods covers cases where the process follows a continuous state space.

text: Locally interacting Markov chains[edit]

text:
Considering a collection of Markov chains whose evolution takes in account the state of other Markov chains, is related to the notion
of locally interacting Markov chains. This corresponds to the situation when the state space has a (Cartesian-) product form.
See interacting particle system and stochastic cellular automata (probabilistic cellular automata).
See for instance Interaction of Markov Processes[55]
or[56]

text: Markovian representations[edit]

text: In some cases, apparently non-Markovian processes may still have Markovian representations, constructed by expanding the concept of the 'current' and 'future' states. For example, let X be a non-Markovian process. Then define a process Y, such that each state of Y represents a time-interval of states of X. Mathematically, this takes the form:

text: If Y has the Markov property, then it is a Markovian representation of X.

text: An example of a non-Markovian process with a Markovian representation is an autoregressive time series of order greater than one.[57]

text: Transient behaviour[edit]

text: Write P(t) for the matrix with entries pij = P(Xt = j | X0 = i). Then the matrix P(t) satisfies the forward equation, a first-order differential equation

text: where the prime denotes differentiation with respect to t. The solution to this equation is given by a matrix exponential

text: In a simple case such as a CTMC on the state space {1,2}. The general Q matrix for such a process is the following 2 × 2 matrix with α,β > 0

text: The above relation for forward matrix can be solved explicitly in this case to give

text: However, direct solutions are complicated to compute for larger matrices. The fact that Q is the generator for a semigroup of matrices

text: is used.

text: Stationary distribution[edit]

text: The stationary distribution for an irreducible recurrent CTMC is the probability distribution to which the process converges for large values of t. Observe that for the two-state process considered earlier with P(t) given by

text: as t → ∞ the distribution tends to

text: Observe that each row has the same distribution as this does not depend on starting state. The row vector π may be found by solving[58]

text: with the additional constraint that

text: Example 1[edit]

text: The image to the right describes a continuous-time Markov chain with state-space {Bull market, Bear market, Stagnant market} and transition rate matrix

text: The stationary distribution of this chain can be found by solving π Q = 0 subject to the constraint that elements must sum to 1 to obtain

text: Example 2[edit]

text: The image to the right describes a discrete-time Markov chain with state-space {1,2,3,4,5,6,7,8,9}. The player controls Pac-Man through a maze, eating pac-dots. Meanwhile, he is being hunted by ghosts. For convenience, the maze shall be a small 3x3-grid and the monsters move randomly in horizontal and vertical directions. A secret passageway between states 2 and 8 can be used in both directions. Entries with probability zero are removed in the following transition matrix:

text:
Q
=

(

1
2

1
2

1
4

1
4

1
4

1
4

1
2

1
2

1
3

1
3

1
3

1
4

1
4

1
4

1
4

1
3

1
3

1
3

1
2

1
2

1
4

1
4

1
4

1
4

1
2

1
2

)

{\displaystyle Q={\begin{pmatrix}&{\frac {1}{2}}&&{\frac {1}{2}}\\{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}&&&{\frac {1}{4}}\\&{\frac {1}{2}}&&&&{\frac {1}{2}}\\{\frac {1}{3}}&&&&{\frac {1}{3}}&&{\frac {1}{3}}\\&{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}\\&&{\frac {1}{3}}&&{\frac {1}{3}}&&&&{\frac {1}{3}}\\&&&{\frac {1}{2}}&&&&{\frac {1}{2}}\\&{\frac {1}{4}}&&&{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}\\&&&&&{\frac {1}{2}}&&{\frac {1}{2}}\end{pmatrix}}}

text:
This Markov chain is irreducible, because the ghosts can fly from every state to every state in a finite amount of time. Due to the secret passageway, the Markov chain is also aperiodic, because the monsters can move from any state to any state both in an even and in an uneven number of state transitions. Therefore, a unique stationary distribution exists and can be found by solving π Q = 0 subject to the constraint that elements must sum to 1. The solution of this linear equation subject to the constraint is

π
=
(
7.7
,
15.4
,
7.7
,
11.5
,
15.4
,
11.5
,
7.7
,
15.4
,
7.7
)
%
.

{\displaystyle \pi =(7.7,15.4,7.7,11.5,15.4,11.5,7.7,15.4,7.7)\%.}

The central state and the border states 2 and 8 of the adjacent secret passageway are visited most and the corner states are visited least.

text: Hitting times[edit]

text: The hitting time is the time, starting in a given set of states until the chain arrives in a given state or set of states. The distribution of such a time period has a phase type distribution. The simplest such distribution is that of a single exponentially distributed transition.

text: Expected hitting times[edit]

text:
For a subset of states A ⊆ S, the vector kA of hitting times (where element

k

i

A

{\displaystyle k_{i}^{A}}

 represents the expected value, starting in state i that the chain enters one of the states in the set A) is the minimal non-negative solution to[58]

text: Time reversal[edit]

text:
For a CTMC Xt, the time-reversed process is defined to be

X
^

t

=

X

T
−
t

{\displaystyle \scriptstyle {\hat {X}}_{t}=X_{T-t}}

. By Kelly's lemma this process has the same stationary distribution as the forward process.

text: A chain is said to be reversible if the reversed process is the same as the forward process. Kolmogorov's criterion states that the necessary and sufficient condition for a process to be reversible is that the product of transition rates around a closed loop must be the same in both directions.

text: Embedded Markov chain[edit]

text: One method of finding the stationary probability distribution, π, of an ergodic continuous-time Markov chain, Q, is by first finding its embedded Markov chain (EMC).  Strictly speaking, the EMC is a regular discrete-time Markov chain, sometimes referred to as a jump process.  Each element of the one-step transition probability matrix of the EMC, S, is denoted by sij, and represents the conditional probability of transitioning from state i into state j.  These conditional probabilities may be found by

text: From this, S may be written as

text: where I is the identity matrix and diag(Q) is the diagonal matrix formed by selecting the main diagonal from the matrix Q and setting all other elements to zero.

text:
To find the stationary probability distribution vector, we must next find

ϕ

{\displaystyle \phi }

 such that

text:
with

ϕ

{\displaystyle \phi }

 being a row vector, such that all elements in

ϕ

{\displaystyle \phi }

 are greater than 0 and

|

|

ϕ

|

|

1

{\displaystyle ||\phi ||_{1}}

 = 1. From this, π may be found as

text: Note that S may be periodic, even if Q is not.  Once π is found, it must be normalized to a unit vector.

text: Another discrete-time process that may be derived from a continuous-time Markov chain is a δ-skeleton—the (discrete-time) Markov chain formed by observing X(t) at intervals of δ units of time.  The random variables X(0), X(δ), X(2δ), ... give the sequence of states visited by the δ-skeleton.

text: Applications[edit]

text: Research has reported the application and usefulness of Markov chains in a wide range of topics such as physics, chemistry, medicine, music, game theory and sports.

text: Physics[edit]

text: Markovian systems appear extensively in thermodynamics and statistical mechanics, whenever probabilities are used to represent unknown or unmodelled details of the system, if it can be assumed that the dynamics are time-invariant, and that no relevant history need be considered which is not already included in the state description.[59][citation needed]

text: The paths, in the path integral formulation of quantum mechanics, are Markov chains.[60]

text: Markov chains are used in lattice QCD simulations.[61]

text: Chemistry[edit]

text: Markov chains and continuous-time Markov processes are useful in chemistry when physical systems closely approximate the Markov property. For example, imagine a large number n of molecules in solution in state A, each of which can undergo a chemical reaction to state B with a certain average rate. Perhaps the molecule is an enzyme, and the states refer to how it is folded. The state of any single enzyme follows a Markov chain, and since the molecules are essentially independent of each other, the number of molecules in state A or B at a time is n times the probability a given molecule is in that state.

text: The classical model of enzyme activity, Michaelis–Menten kinetics, can be viewed as a Markov chain, where at each time step the reaction proceeds in some direction. While Michaelis-Menten is fairly straightforward, far more complicated reaction networks can also be modeled with Markov chains.

text: An algorithm based on a Markov chain was also used to focus the fragment-based growth of chemicals in silico towards a desired class of compounds such as drugs or natural products.[62] As a molecule is grown, a fragment is selected from the nascent molecule as the "current" state. It is not aware of its past (i.e., it is not aware of what is already bonded to it). It then transitions to the next state when a fragment is attached to it. The transition probabilities are trained on databases of authentic classes of compounds.

text: Also, the growth (and composition) of copolymers may be modeled using Markov chains. Based on the reactivity ratios of the monomers that make up the growing polymer chain, the chain's composition may be calculated (e.g., whether monomers tend to add in alternating fashion or in long runs of the same monomer). Due to steric effects, second-order Markov effects may also play a role in the growth of some polymer chains.

text: Similarly, it has been suggested that the crystallization and growth of some epitaxial superlattice oxide materials can be accurately described by Markov chains.[63]

text: Testing[edit]

text: Several theorists have proposed the idea of the Markov chain statistical test (MCST), a method of conjoining Markov chains to form a "Markov blanket", arranging these chains in several recursive layers ("wafering") and producing more efficient test sets—samples—as a replacement for exhaustive testing. MCSTs also have uses in temporal state-based networks; Chilukuri et al.'s paper entitled "Temporal Uncertainty Reasoning Networks for Evidence Fusion with Applications to Object Detection and Tracking" (ScienceDirect) gives a background and case study for applying MCSTs to a wider range of applications.

text: Speech recognition[edit]

text: Hidden Markov models are the basis for most modern automatic speech recognition systems.

text: Information and computer science[edit]

text: Markov chains are used throughout information processing. Claude Shannon's famous 1948 paper A Mathematical Theory of Communication, which in a single step created the field of information theory, opens by introducing the concept of entropy through Markov modeling of the English language. Such idealized models can capture many of the statistical regularities of systems. Even without describing the full structure of the system perfectly, such signal models can make possible very effective data compression through entropy encoding techniques such as arithmetic coding. They also allow effective state estimation and pattern recognition. Markov chains also play an important role in reinforcement learning.

text: Markov chains are also the basis for hidden Markov models, which are an important tool in such diverse fields as telephone networks (which use the Viterbi algorithm for error correction), speech recognition and bioinformatics (such as in rearrangements detection[64]).

text: The LZMA lossless data compression algorithm combines Markov chains with Lempel-Ziv compression to achieve very high compression ratios.

text: Queueing theory[edit]

text: Markov chains are the basis for the analytical treatment of queues (queueing theory). Agner Krarup Erlang initiated the subject in 1917.[65] This makes them critical for optimizing the performance of telecommunications networks, where messages must often compete for limited resources (such as bandwidth).[66]

text: Numerous queueing models use continuous-time Markov chains. For example, an M/M/1 queue is a CTMC on the non-negative integers where upward transitions from i to i + 1 occur at rate λ according to a Poisson process and describe job arrivals, while transitions from i to i – 1 (for i > 1) occur at rate μ (job service times are exponentially distributed) and describe completed services (departures) from the queue.

text: Internet applications[edit]

text:
The PageRank of a webpage as used by Google is defined by a Markov chain.[67] It is the probability to be at page

i

{\displaystyle i}

 in the stationary distribution on the following Markov chain on all (known) webpages. If

N

{\displaystyle N}

 is the number of known webpages, and a page

i

{\displaystyle i}

 has

k

i

{\displaystyle k_{i}}

 links to it then it has transition probability

α

k

i

+

1
−
α

N

{\displaystyle {\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}}

 for all pages that are linked to and

1
−
α

N

{\displaystyle {\frac {1-\alpha }{N}}}

 for all pages that are not linked to. The parameter

α

{\displaystyle \alpha }

 is taken to be about 0.85.[68]

text: Markov models have also been used to analyze web navigation behavior of users. A user's web link transition on a particular website can be modeled using first- or second-order Markov models and can be used to make predictions regarding future navigation and to personalize the web page for an individual user.

text: Statistics[edit]

text: Markov chain methods have also become very important for generating sequences of random numbers to accurately reflect very complicated desired probability distributions, via a process called Markov chain Monte Carlo (MCMC). In recent years this has revolutionized the practicability of Bayesian inference methods, allowing a wide range of posterior distributions to be simulated and their parameters found numerically.

text: Economics and finance[edit]

text: Markov chains are used in finance and economics to model a variety of different phenomena, including asset prices and market crashes. The first financial model to use a Markov chain was from Prasad et al. in 1974.[dubious  – discuss][69] Another was the regime-switching model of James D. Hamilton (1989), in which a Markov chain is used to model switches between periods high and low GDP growth (or alternatively, economic expansions and recessions).[70] A more recent example is the Markov Switching Multifractal model of Laurent E. Calvet and Adlai J. Fisher, which builds upon the convenience of earlier regime-switching models.[71][72] It uses an arbitrarily large Markov chain to drive the level of volatility of asset returns.

text: Dynamic macroeconomics heavily uses Markov chains.  An example is using Markov chains to exogenously model prices of equity (stock) in a general equilibrium setting.[73]

text: Credit rating agencies produce annual tables of the transition probabilities for bonds of different credit ratings.[74]

text: Social sciences[edit]

text: Markov chains are generally used in describing path-dependent arguments, where current structural configurations condition future outcomes. An example is the reformulation of the idea, originally due to Karl Marx's Das Kapital, tying economic development to the rise of capitalism. In current research, it is common to use a Markov chain  to model how once a country reaches a specific level of economic development, the configuration of structural factors, such as size of the middle class, the ratio of urban to rural residence, the rate of political mobilization, etc., will generate a higher probability of transitioning from authoritarian to democratic regime.[75]

text: Mathematical biology[edit]

text:
Markov chains also have many applications in biological modelling, particularly population processes, which are useful in modelling processes that are (at least) analogous to biological populations. The Leslie matrix, is one such example used to describe the population dynamics of many species, though some of its entries
are not probabilities (they may be greater than 1). Another example is the modeling of cell shape in dividing sheets of epithelial cells.[76] Yet another example is the state of ion channels in cell membranes.

text: Markov chains are also used in simulations of brain function, such as the simulation of the mammalian neocortex.[77] Markov chains have also been used to model viral infection of single cells.[78]

text: Genetics[edit]

text: Markov chains have been used in population genetics in order to describe the change in gene frequencies in small populations affected by genetic drift, for example in diffusion equation method described by Motoo Kimura.[79]

text: Games[edit]

text: Markov chains can be used to model many games of chance. The children's games Snakes and Ladders and "Hi Ho! Cherry-O", for example, are represented exactly by Markov chains. At each turn, the player starts in a given state (on a given square) and from there has fixed odds of moving to certain other states (squares).

text: Music[edit]

text: Markov chains are employed in algorithmic music composition, particularly in software such as CSound, Max and SuperCollider. In a first-order chain, the states of the system become note or pitch values, and a probability vector for each note is constructed, completing a transition probability matrix (see below). An algorithm is constructed to produce output note values based on the transition matrix weightings, which could be MIDI note values, frequency (Hz), or any other desirable metric.[80]

text:
1st-order matrix

Note
A
C♯
E♭

A

0.1
0.6
0.3

C♯

0.25
0.05
0.7

E♭

0.7
0.3
0

text:
2nd-order matrix

Notes
A
D
G

AA

0.18
0.6
0.22

AD

0.5
0.5
0

AG

0.15
0.75
0.1

DD

0
0
1

DA

0.25
0
0.75

DG

0.9
0.1
0

GG

0.4
0.4
0.2

GA

0.5
0.25
0.25

GD

1
0
0

text: A second-order Markov chain can be introduced by considering the current state and also the previous state, as indicated in the second table. Higher, nth-order chains tend to "group" particular notes together, while 'breaking off' into other patterns and sequences occasionally. These higher-order chains tend to generate results with a sense of phrasal structure, rather than the 'aimless wandering' produced by a first-order system.[81]

text: Markov chains can be used structurally, as in Xenakis's Analogique A and B.[82]  Markov chains are also used in systems which use a Markov model to react interactively to music input.[83]

text: Usually musical systems need to enforce specific control constraints on the finite-length sequences they generate, but control constraints are not compatible with Markov models, since they induce long-range dependencies that violate the Markov hypothesis of limited memory. In order to overcome this limitation, a new approach has been proposed.[84]

text: Baseball[edit]

text:
Markov chain models have been used in advanced baseball analysis since 1960, although their use is still rare. Each half-inning of a baseball game fits the Markov chain state when the number of runners and outs are considered. During any at-bat, there are 24 possible combinations of number of outs and position of the runners. Mark Pankin shows that Markov chain models can be used to evaluate runs created for both individual players as well as a team.[85]
He also discusses various kinds of strategies and play conditions: how Markov chain models have been used to analyze statistics for game situations such as bunting and base stealing and differences when playing on grass vs. astroturf.[86]

text: Markov text generators[edit]

text: Markov processes can also be used to generate superficially real-looking text given a sample document.  Markov processes are used in a variety of recreational "parody generator" software (see dissociated press, Jeff Harrison,[87] Mark V Shaney[88][89])

text: Bioinformatics[edit]

text: In the bioinformatics field, they can be used to simulate DNA sequences.[90]


document_title: List of Twenty20 cricket records

question_text: highest score in t20 match by a player

question_tokens: highest score in t20 match by a player

root

text: List of Twenty20 cricket records

text: Listing criteria[edit]

text: In general the top five are listed in each category (except when there is a tie for the last place among the five, when all the tied record holders are noted). Currently active players are indicated with a . Teams playing at home are indicated by , where appropriate.

tag: p

text: Team records[edit]

text: Highest innings totals[edit]

text:
Rank
Score
Team
Opponent
Venue
Date

1
263/5 (20 overs)
Royal Challengers Bangalore
Pune Warriors India
Bangalore
23 April 2013

263/3 (20 overs)
 Australia
 Sri Lanka
Kandy
6 September 2016

3
260/6 (20 overs)
 Sri Lanka
 Kenya
Johannesburg
14 September 2007

260/4 (20 overs)
Yorkshire
Northants
Headingley
17 August 2017

260/5 (20 overs)
 India
 Sri Lanka
Indore
22 December 2017

Source: ESPNcricinfo (updated 1 March 2018).

tag: table

text: Lowest innings totals[edit]

text: Completed innings only.

text:
Rank
Score
Team
Opponent
Venue
Date

1
30 (11.4 overs)
Tripura
Jharkhand
Dhanbad
20 September 2009

2
39 (10.3 overs)
 Netherlands
 Sri Lanka
Chittagong
24 March 2014

3
44 (14.4 overs)
Boland
North West
Potchefstroom
16 November 2014

44 (12.5 overs)
Leeward Islands
Trinidad and Tobago
North Sound
11 January 2012

44 (12.1 overs)
Assam
Delhi
Vadodara
6 January 2016

44 (10.4 overs)
Khulna Titans
Rangpur Riders
Mirpur
10 November 2016

Source: ESPNcricinfo (updated 1 March 2018).

text: Highest victory margin (by runs)[edit]

text:
Rank
Winner
Margin
Target
Opponent
Venue
Date

1
 Sri Lanka
172 runs
261
 Kenya
Johannesburg
14 September 2007

2
Trinidad and Tobago
167 runs
212
Leeward Islands
North Sound
11 January 2012

3
Prime Bank
159 runs
205
Mohammedan
Sylhet
26 December 2013

4
Northerns
158 runs
228
Southerns
Harare
19 March 2008

5
Mumbai Indians
146 runs
213
Delhi Daredevils
New Delhi
6 May 2017

Source: ESPNcricinfo (updated 16 May 2016).

text: Highest match aggregate[edit]

text:
Rank
Score
Teams
Venue
Date

1
497/7 (40 overs)
Otago (249–3) v Central Districts (248–4)
New Plymouth, Taranaki
21 December 2016

2
489/10 (40 overs)
 West Indies (245–6) v  India (244–4)
Lauderhill, Florida
27 August 2016

3
488/11 (38.5 overs)
 New Zealand (243-6)  v  Australia (245-5)
Auckland
16 February 2018

4
469/10 (40 overs)
Chennai Super Kings (246–5)  v Rajasthan Royals (223–5)
Chennai
3 April 2010

5
467/13 (39.2 overs)
 South Africa (231/7)  v  West Indies (236/6)
Johannesburg
11 January 2015

Source: ESPNcricinfo (Updated 1 March 2018)

text: Individual records[edit]

text: Individual records (batting)[edit]

text: Highest individual score[edit]

text:
Rank
Runs
Player
Team
Opponents
Venue
Date

1
175*
Chris Gayle
Royal Challengers Bangalore
Pune Warriors India
Bangalore
23 April 2013

2
162*
Hamilton Masakadza
Mountaineers
Eagles
Bulawayo
11 February 2016

3
161
Adam Lyth
Yorkshire Vikings
Northants Steelbacks
Headingley
17 August 2017

4
158*
Brendon McCullum
Kolkata Knight Riders
Royal Challengers Bangalore
Bangalore
18 April 2008

Birmingham Bears
Derbyshire
Edgbaston
3 July 2015

Source: ESPNcricinfo (updated 1 March 2018).

text: Most career runs[edit]

text:
Rank
Runs
Innings)
Player
National Team
Period

1
11068
316
Chris Gayle
 West Indies
2005–present

2
8848
317
Brendon McCullum
 New Zealand
2005–present

3
7932
366
Kieron Pollard
 West Indies
2006–present

4
7668
242
David Warner
 Australia
2007–present

5
7575
279
Shoaib Malik
 Pakistan
2005–present

Source: ESPNcricinfo.com, last updated 1 March 2018

text: Most centuries in a career[edit]

text: Chris Gayle is the clear leader in the list of the most career centuries in T20s with 21; no other player has scored more than seven.[1]

text: Fastest 100[edit]

text:
Rank
Balls
Player
Team
Opposition
Venue
Date

1
30
Chris Gayle
Royal Challengers Bangalore
Pune Warriors India
Bangalore
23 April 2013

2
32
Rishabh Pant
Delhi
Himachal Pradesh
Delhi
14 January 2018

3
34
Andrew Symonds
Kent
Middlesex
Maidstone
2 July 2004

4
35
Louis van der Westhuizen
 Namibia
 Kenya
Windhoek
7 November 2011

David Miller
 South Africa
 Bangladesh
Potchefstroom
29 October 2017

Rohit Sharma
 India
 Sri Lanka
Indore
22 December 2017

Source: ESPNcricinfo.com, last updated 1 March 2018

text: Fastest 50[edit]

text:
Rank
Balls
Player
Team
Opposition
Venue
Date

1
12
Yuvraj Singh
 India
 England
Durban
19 September 2007

12
Chris Gayle
Melbourne Renegades
Adelaide Strikers
Docklands Stadium
18 January 2016

3
13
Marcus Trescothick
Somerset
Hampshire
Taunton
9 July 2010

4
14
Colin Munro
 New Zealand
 Sri Lanka
Auckland
10 January 2016

14
Gerard Brophy
Yorkshire
Derbyshire
Derby
10 July 2006

14
Imran Nazir
Sialkot Stallions
Lahore Eagles
Lahore
26 April 2005

14
Kieran Noema-Barnett
Central Districts
Otago
Invercargill
12 December 2010

14
Kieron Pollard
Trinidad and Tobago
Leeward Islands
North Sound
11 January 2012

14
Farhaan Behardien
Titans
Warriors
East London
11 December 2016

14
KL Rahul
Kings XI Punjab
Delhi Daredevils
Punjab Cricket Association Stadium
8 April 2018

Source: ESPNcricinfo.com, last updated 1 March 2018

text: Highest career strike rate[edit]

text: Qualification: 1,000 balls.

text:
Rank
Strike Rate
Balls faced
Player
National Team
Period

1
167.80
1,379
Colin de Grandhomme
 New Zealand
2007–present

2
164.60
2,114
Andre Russell
 West Indies
2010–present

3
157.47
2,714
Glenn Maxwell
 Australia
2010–present

4
156.40
2,469
Shahid Afridi
 Pakistan
2004–present

5
153.77
1,664
Luke Ronchi
 New Zealand,  Australia
2006–present

Source: ESPNcricinfo.com, last updated: 1 March 2018

text: Highest career average[edit]

text: Qualification: 50 innings.

text:
Rank
Average
Innings
Player
National Team
Period

1
41.15
316
Chris Gayle
 West Indies
2005–present

2
40.54
215
Virat Kohli
 India
2007–present

3
39.60
161
Shaun Marsh
 Australia
2006–present

4
37.72
55
H. D. Ackerman
 South Africa
2004–2009

5
37.68
216
JP Duminy
 South Africa
2004–present

Source: ESPNcricinfo.com, Last updated: 1 March 2018

text: Most career sixes[edit]

text:
Rank
Sixes
Player
National Team
Period

1
819
Chris Gayle
 West Indies
2005–present

2
512
Kieron Pollard
 West Indies
2006–present

3
430
Brendon McCullum
 New Zealand
2005–present

5
359
Dwayne Smith
 West Indies
2006–present

4
320
Shane Watson
 Australia
2007–present

Source: Cricinfo.com, Last updated: 1 March 2018

text: Most sixes in an innings[edit]

text:
Rank
Sixes
Player
Team
Opponent
Venue
Date

1
18
Chris Gayle
Rangpur Riders
Dhaka Dynamites
Dhaka
12 December 2017

2
17
Chris Gayle
Royal Challengers Bangalore
Pune Warriors India
Bangalore
23 April 2013

3
16
Graham Napier
Essex
Sussex
Chelmsford
24 June 2008

16
Dasun Shanaka
Sinhalese
Saracens
Colombo
12 January 2016

5
15
Chris Gayle
Somerset
Kent
Taunton
31 May 2015

Source: Cricinfo.com, Last updated: 1 March 2018

text: Individual records (bowling)[edit]

text: Best figures in a match[edit]

text:
Rank
Bowling
Player
Team
Opponent
Venue
Date

1
6/5
Arul Suppiah
Somerset
Glamorgan
Cardiff
5 July 2011

2
6/6
Shakib Al Hasan
Barbados Tridents
Trinidad and Tobago Red Steel
Bridgetown
3 August 2013

3
6/7
Lasith Malinga
Melbourne Stars
Perth Scorchers
Perth
12 December 2012

4
6/8
Ajantha Mendis
 Sri Lanka
 Zimbabwe
Hambantota
18 September 2012

5
6/9
Phaphama Fojela
Border
Easterns
East London
14 December 2014

Source: ESPNcricinfo, last updated 1 March 2018

text: Most career wickets[edit]

text:
Rank
Wickets
Matches
Player
National Team
Period

1
413
375
Dwayne Bravo
 West Indies
2006–present

2
339
251
Lasith Malinga
 Sri Lanka
2004–present

3
310
265
Sunil Narine
 West Indies
2011–present

4
293
268
Shahid Afridi
 Pakistan
2006–present

5
292
252
Shakib Al Hasan
 Bangladesh
2006–present

Source:ESPNcricinfo , last updated 1 March 2018

text: Individual records (wicket keeping)[edit]

text: Most dismissals in career[edit]

text: Only dismissals and innings played as wicketkeeper counted, some of the players have also taken catches as fielders.

text:
Rank
Dismissals
Innings
Player
National Team
Period
Catches
Stumpings

1
209
206
Kamran Akmal
 Pakistan
2005–present
117
92

2
205
264
Mahendra Singh Dhoni
 India
2006–present
135
70

3
195
197
Kumar Sangakkara
 Sri Lanka
2004–present
136
59

4
171
196
Dinesh Karthik
 India
2006–present
123
48

5
152
167
Denesh Ramdin
 West Indies
2006–present
108
44

Source:ESPNcricinfo.com, last updated 1 March 2018

text: Individual records (other)[edit]

text: Most matches played[edit]

text:
Rank
Matches
Player
National Team
Period

1
406
Kieron Pollard
 West Indies
2006–present

2
375
Dwayne Bravo
 West Indies
2006–present

3
323
Chris Gayle
 West Indies
2005–present

4
322
Brendan McCullum
 New Zealand
2005–present

5
311
Dwayne Smith
 West Indies
2006–present

Source: ESPNcricinfo.com, last updated 1 March 2018

text: Partnership records[edit]

text: Record wicket partnerships[edit]

text:
Partnership
Runs
Players
Team
Opponent
Venue
Date

1st wicket
209
 Kamran Akmal &  Salman Butt
Lahore Whites
Islamabad Region
Rawalpindi Cricket Stadium
24 November 2017

2nd wicket
229
 AB de Villiers &  Virat Kohli
Royal Challengers Bangalore
Gujarat Lions
Bengaluru
14 May 2016

3rd wicket
162
 Abdul Razzaq &  Nasir Jamshed
Lahore Lions
Quetta Bears
Lahore
26 May 2009

4th wicket
202*
 Manpreet Juneja &  Abdulahad Malek
Gujarat
Kerala
Indore
30 March 2013

5th wicket
150
 Hashim Amla &  Dwayne Bravo
Trinbago Knight Riders
Barbados Tridents
Port of Spain
1 Jul 2016

6th wicket
126*
 Calum MacLeod &  John Hastings
Durham
Northamptonshire
Chester-le-Street
25 July 2014

7th wicket
107*
 Lasith Abeyratne &  Roshan Anurudda
Colombo Cricket Club
Chilaw Marians Cricket Club
Colombo
12 January 2016

8th wicket
120
 Azhar Mahmood &  Isuru Udana
Wayamba United
Uva Next
Colombo
28 August 2012

9th wicket
69
 Corey Anderson &  Josh Davey
Somerset
Surrey
The Oval
9 Jul 2017

10th wicket
63
 Grant Elliott &  Zulfiqar Babar
Quetta Gladiators
Peshawar Zalmi
Sharjah
14 February 2016

Source: Cricinfo.com, last updated 9 December 2017

text: Note: An asterisk (*) signifies an unbroken partnership (i.e. neither of the batsmen were dismissed before either the end of the allotted overs or they reached the required score).

tag: ul


document_title: Disaster recovery plan

question_text: list 4 important issues you must consider when developing a comprehensive disaster recovery plan

text: Disaster recovery plan

text: Objectives[edit]

text: Organizations cannot always avoid disasters, but with careful planning the effects of a disaster can be minimized. The objective of a disaster recovery plan is to minimize downtime and data loss.[3] The primary objective is to protect the organization in the event that all or part of its operations and/or computer services are rendered unusable. The plan minimizes the disruption of operations and ensures that some level of organizational stability and an orderly recovery after a disaster will prevail.[2]  Minimizing downtime and data loss is measured in terms of two concepts: the recovery time objective (RTO) and the recovery point objective (RPO).

text: The recovery time objective is the time within which a business process must be restored, after a major incident (MI) has occurred, in order to avoid unacceptable consequences associated with a break in business continuity. The recovery point objective (RPO) is the age of files that must be recovered from backup storage for normal operations to resume if a computer, system, or network goes down as a result of a MI. The RPO is expressed backwards in time (that is, into the past) starting from the instant at which the MI occurs, and can be specified in seconds, minutes, hours, or days.[4] The recovery point objective (RPO) is thus the maximum acceptable amount of data loss measured in time. It is the age of the files or data in backup storage required to resume normal operations after the MI.[5]

text: Relationship to the Business Continuity Plan[edit]

text: According to the SANS institute, the Business Continuity Plan (BCP) is a comprehensive organizational plan that includes the disaster recovery plan. The Institute further states that a Business Continuity Plan (BCP) consists of the five component plans:[6]

text:
Business Resumption Plan
Occupant Emergency Plan
Continuity of Operations Plan
Incident Management Plan
Disaster Recovery Plan

text: The Institute states that the first three plans (Business Resumption, Occupant Emergency, and Continuity of Operations Plans) do not deal with the IT infrastructure. They further state that the Incident Management Plan (IMP) does deal with the IT infrastructure, but since it establishes structure and procedures to address cyber attacks against an organization’s IT systems, it generally does not represent an agent for activating the Disaster Recovery Plan, leaving The Disaster Recovery Plan as the only BCP component of interest to IT.[6]

text: Disaster Recovery Institute International states that disaster recovery is the area of business continuity that deals with technology recovery as opposed to the recovery of business operations.[7]

text: Benefits[edit]

text: Like every insurance plan, there are benefits that can be obtained from the drafting of a disaster recovery plan. Some of these benefits are:[2]

text:
Providing a sense of security
Minimizing risk of delays
Guaranteeing the reliability of standby systems
Providing a standard for testing the plan
Minimizing decision-making during a disaster
Reducing potential legal liabilities
Lowering unnecessarily stressful work environment

text: Types of plans[edit]

text: There is no one right type of disaster recovery plan,[8] nor is there a one-size-fits-all disaster recovery plan.[1][8] However, there are three basic strategies that feature in all disaster recovery plans: (1) preventive measures, (2) detective measures, and (3) corrective measures.[9] Preventive measures will try to prevent a disaster from occurring. These measures seek to identify and reduce risks. They are designed to mitigate or prevent an event from happening. These measures may include keeping data backed up and off site, using surge protectors, installing generators and conducting routine inspections. Detective measures are taken to discover the presence of any unwanted events within the IT infrastructure.  Their aim is to uncover new potential threats. They may detect or uncover unwanted events. These measures include installing fire alarms, using up-to-date antivirus software, holding employee training sessions, and installing server and network monitoring software.  Corrective measures are aimed to restore a system after a disaster or otherwise unwanted event takes place. These measures focus on fixing or restoring the systems after a disaster. Corrective measures may include keeping critical documents in the Disaster Recovery Plan or securing proper insurance policies, after a "lessons learned" brainstorming session.[1][10]

text: A disaster recovery plan must answer at least three basic questions: (1) what is its objective and purpose, (2) who will be the people or teams who will be responsible in case any disruptions happen, and (3) what will these people do (the procedures to be followed) when the disaster strikes.[11]

text: Types of disasters[edit]

text: Disasters can be natural or man-made. Man-made disasters could be intentional (for example, sabotage or an act of terrorism) or unintentional (that is, accidental, such as the breakage of a man-made dam).  Disasters may encompass more than weather. They may involve Internet threats or take on other man-made manifestations such as theft.[1]

text: Natural disaster[edit]

text: A natural disaster is a major adverse event resulting from the earth's natural hazards. Examples of natural disasters are floods, tsunamis, tornadoes, hurricanes/cyclones, volcanic eruptions, earthquakes, heat waves, and landslides.  Other types of disasters include the more cosmic scenario of an asteroid hitting the Earth.

text: Man-made disasters[edit]

text: Man-made disasters are the consequence of technological or human hazards. Examples include stampedes, urban fires, industrial accidents, oil spills, nuclear explosions/nuclear radiation and acts of war.  Other types of man-made disasters include the more cosmic scenarios of catastrophic global warming, nuclear war, and bioterrorism.

text: The following table categorizes some disasters and notes first response initiatives. Note that whereas the sources of a disaster may be natural (for example, heavy rains) or man-made (for example, a broken dam), the results may be similar (flooding).[12]

text:
Natural

Disaster

Example
Profile
First Response

Avalanche
The sudden, drastic flow of snow down a slope, occurring when either natural triggers, such as loading from new snow or rain, or artificial triggers, such as explosives or backcountry skiers, overload the snowpack
Shut off utilities; Evacuate building if necessary; Determine impact on the equipment and facilities and any disruption

Blizzard
A severe snowstorm characterized by very strong winds and low temperatures
Power off all equipment; listen to blizzard advisories; Evacuate area, if unsafe; Assess damage

Earthquake
The shaking of the earth’s crust, caused by underground volcanic forces of breaking and shifting rock beneath the earth’s surface
Shut off utilities; Evacuate building if necessary; Determine impact on the equipment and facilities and any disruption

Fire (wild)
Fires that originate in uninhabited areas and which pose the risk to spread to inhabited areas
Attempt to suppress fire in early stages; Evacuate personnel on alarm, as necessary; Notify fire department; Shut off utilities; Monitor weather advisories

Flood
Flash flooding: Small creeks, gullies, dry streambeds, ravines, culverts or even low-lying areas flood quickly
Monitor flood advisories; Determine flood potential to facilities; Pre-stage emergency power generating equipment; Assess damage

Freezing Rain
Rain occurring when outside surface temperature is below freezing
Monitor weather advisories; Notify employees of business closure; home; Arrange for snow and ice removal

Heat wave
A prolonged period of excessively hot weather relative to the usual weather pattern of an area and relative to normal temperatures for the season
Listen to weather advisories; Power-off all servers after a graceful shutdown if there is imminent potential of power failure; Shut down main electric circuit usually located in the basement or the first floor

Hurricane
Heavy rains and high winds
Power off all equipment; listen to hurricane advisories; Evacuate area, if flooding is possible; Check gas, water and electrical lines for damage; Do not use telephones, in the event of severe lightning; Assess damage

Landslide
Geological phenomenon which includes a range of ground movement, such as rock falls, deep failure of slopes and shallow debris flows
Shut off utilities; Evacuate building if necessary; Determine impact on the equipment and facilities and any disruption

Lightning strike
An electrical discharge caused by lightning, typically during thunderstorms
Power off all equipment; listen to hurricane advisories; Evacuate area, if flooding is possible; Check gas, water and electrical lines for damage; Do not use telephones, in the event of severe lightning; Assess damage

Limnic eruption
The sudden eruption of carbon dioxide from deep lake water
Shut off utilities; Evacuate building if necessary; Determine impact on the equipment and facilities and any disruption

Tornado
Violent rotating columns of air which descent from severe thunderstorm cloud systems
Monitor tornado advisories; Power off equipment; Shut off utilities (power and gas); Assess damage once storm passes

Tsunami
A series of water waves caused by the displacement of a large volume of a body of water, typically an ocean or a large lake, usually caused by earthquakes, volcanic eruptions, underwater explosions, landslides, glacier calvings, meteorite impacts and other disturbances above or below water
Power off all equipment; listen to tsunami advisories; Evacuate area, if flooding is possible; Check gas, water and electrical lines for damage; Assess damage

Volcanic eruption
The release of hot magma, volcanic ash and/or gases from a volcano
Shut off utilities; Evacuate building if necessary; Determine impact on the equipment and facilities and any disruption

Man-made

Bioterrorism
The intentional release or dissemination of biological agents as a means of coercion
Get information immediately from your Public Health officials via the news media as to the right course of action; If you think you have been exposed, quickly remove your clothing and wash off your skin; Also put on a HEPA to help prevent inhalation of the agent[13]

Civil unrest
A disturbance caused by a group of people that may include sit-ins and other forms of obstructions, riots, sabotage and other forms of crime, and which is intended to be a demonstration to the public and the government, but can escalate into general chaos
Contact local police or law enforcement[14][15]

Fire (urban)
Even with strict building fire codes, people still perish needlessly in fires
Attempt to suppress fire in early stages; Evacuate personnel on alarm, as necessary; Notify fire department; Shut off utilities; Monitor weather advisories

Hazardous material spills
The escape of solids, liquids, or gases that can harm people, other living organisms, property or the environment, from their intended controlled environment such as a container.
Leave the area and call the local fire department for help.[16] If anyone was affected by the spill, call the your local Emergency Medical Services line[17]

Nuclear and Radiation Accidents
An event involving significant release of radioactivity to the environment or a reactor core meltdown and which leads to major undesirable consequences to people, the environment, or the facility
Recognize that a CBRN incident has or may occur. Gather, assess and disseminate all available information to first responders. Establish an overview of the affected area. Provide and obtain regular updates to and from first responders.[18]

Power Failure
Caused by summer or winter storms, lightning or construction equipment digging in the wrong location
Wait 5–10 minutes; Power-off all Servers after a graceful shutdown; Do not use telephones, in the event of severe lightning; Shut down main electric circuit usually located in the basement or the first floor

text: In the realm of information technology per se, disasters may also be the result of a computer security exploit. Some of these are: computer viruses, cyberattacks, denial-of-service attacks, hacking, and malware exploits. These are ordinarily attended to by information security experts.

text: Planning methodology[edit]

text: According to Geoffrey H. Wold of the Disaster Recovery Journal, the entire process involved in developing a Disaster Recovery Plan consists of 10 steps:[2]

text: Obtaining top management commitment[edit]

text: For a disaster recovery plan to be successful, the central responsibility for the plan must reside on top management. Management is responsible for coordinating the disaster recovery plan and ensuring its effectiveness within the organization. It is also responsible for allocating adequate time and resources required in the development of an effective plan. Resources that management must allocate include both financial considerations and the effort of all personnel involved.

text: Establishing a planning committee[edit]

text: A planning committee is appointed to oversee the development and implementation of the plan. The planning committee includes representatives from all functional areas of the organization. Key committee members customarily include the operations manager and the data processing manager. The committee also defines the scope of the plan.

text: Performing a risk assessment[edit]

text: The planning committee prepares a risk analysis and a business impact analysis (BIA) that includes a range of possible disasters, including natural, technical and human threats. Each functional area of the organization is analyzed to determine the potential consequence and impact associated with several disaster scenarios. The risk assessment process also evaluates the safety of critical documents and vital records. Traditionally, fire has posed the greatest threat to an organization. Intentional human destruction, however, should also be considered. A thorough plan provides for the “worst case” situation: destruction of the main building. It is important to assess the impacts and consequences resulting from loss of information and services. The planning committee also analyzes the costs related to minimizing the potential exposures.

text: Establishing priorities for processing and operations[edit]

text: At this point, the critical needs of each department within the organization are evaluated in order to prioritize them. Establishing priorities is important because no organization possesses infinite resources and criteria must be set as to where to allocate resources first. Some of the areas often reviewed during the prioritization process are functional operations, key personnel and their functions, information flow, processing systems used, services provided, existing documentation, historical records, and the department's policies and procedures.

text: Processing and operations are analyzed to determine the maximum amount of time that the department and organization can operate without each critical system. This will later get mapped into the Recovery Time Objective. A critical system is defined as that which is part of a system or procedure necessary to continue operations should a department, computer center, main facility or a combination of these be destroyed or become inaccessible. A method used to determine the critical needs of a department is to document all the functions performed by each department. Once the primary functions have been identified, the operations and processes are then ranked in order of priority: essential, important and non-essential.

text: Determining recovery strategies[edit]

text: During this phase, the most practical alternatives for processing in case of a disaster are researched and evaluated. All aspects of the organization are considered, including physical facilities, computer hardware and software, communications links, data files and databases, customer services provided, user operations, the overall management information systems (MIS) structure, end-user systems, and any other processing operations.

text: Alternatives, dependent upon the evaluation of the computer function, may include: hot sites, warm sites, cold sites, reciprocal agreements, the provision of more than one data center, the installation and deployment of multiple computer system, duplication of service center, consortium arrangements, lease of equipment, and any combinations of the above.

text: Written agreements for the specific recovery alternatives selected are prepared, specifying contract duration, termination conditions, system testing, cost, any special security procedures, procedure for the notification of system changes, hours of operation, the specific hardware and other equipment required for processing, personnel requirements, definition of the circumstances constituting an emergency, process to negotiate service extensions, guarantee of compatibility, availability, non-mainframe resource requirements, priorities, and other contractual issues.

text: Collecting data[edit]

text:
In this phase, data collection takes place. Among the recommended data gathering materials and documentation often included are
various lists (employee backup position listing, critical telephone numbers list, master call list, master vendor list, notification checklist), inventories (communications equipment, documentation, office equipment, forms, insurance policies, workgroup and data center computer hardware, microcomputer hardware and software, office supply, off-site storage location equipment, telephones, etc.), distribution register, software and data files backup/retention schedules, temporary location specifications, any other such other lists, materials, inventories and documentation. Pre-formatted forms are often used to facilitate the data gathering process.

text: Organizing and documenting a written plan[edit]

text: Next, an outline of the plan’s contents is prepared to guide the development of the detailed procedures. Top management reviews and approves the proposed plan. The outline can ultimately be used for the table of contents after final revision. Other four benefits of this approach are that (1) it helps to organize the detailed procedures, (2) identifies all major steps before the actual writing process begins, (3) identifies redundant procedures that only need to be written once, and (4) provides a road map for developing the procedures.

text: It is often considered best practice to develop a standard format for the disaster recovery plan so as to facilitate the writing of detailed procedures and the documentation of other information to be included in the plan later. This helps ensure that the disaster plan follows a consistent format and allows for its ongoing future maintenance. Standardization is also important if more than one person is involved in writing the procedures.

text: It is during this phase that the actual written plan is developed in its entirety, including all detailed procedures to be used before, during, and after a disaster. The procedures include methods for maintaining and updating the plan to reflect any significant internal, external or systems changes. The procedures allow for a regular review of the plan by key personnel within the organization. The disaster recovery plan is structured using a team approach. Specific responsibilities are assigned to the appropriate team for each functional area of the organization. Teams responsible for administrative functions, facilities, logistics, user support, computer backup, restoration and other important areas in the organization are identified.

text: The structure of the contingency organization may not be the same as the existing organization chart. The contingency organization is usually structured with teams responsible for major functional areas such as administrative functions, facilities, logistics, user support, computer backup, restoration, and any other important area.

text: The management team is especially important because it coordinates the recovery process. The team assesses the disaster, activates the recovery plan, and contacts team managers. The management team also oversees, documents and monitors the recovery process. It is helpful when management team members are the final decision-makers in setting priorities, policies and procedures. Each team has specific responsibilities that are completed to ensure successful execution of the plan. The teams have an assigned manager and an alternate in case the team manager is not available. Other team members may also have specific assignments where possible.

text: Developing testing criteria and procedures[edit]

text: Best practices dictate that DR plans be thoroughly tested and evaluated on a regular basis (at least annually). Thorough DR plans include documentation with the procedures for testing the plan. The tests will provide the organization with the assurance that all necessary steps are included in the plan. Other reasons for testing include:

text:
Determining the feasibility and compatibility of backup facilities and procedures.
Identifying areas in the plan that need modification.
Providing training to the team managers and team members.
Demonstrating the ability of the organization to recover.
Providing motivation for maintaining and updating the disaster recovery plan.

text: Testing the plan[edit]

text: After testing procedures have been completed, an initial "dry run" of the plan is performed by conducting a structured walk-through test. The test will provide additional information regarding any further steps that may need to be included, changes in procedures that are not effective, and other appropriate adjustments. These may not become evident unless an actual dry-run test is performed. The plan is subsequently updated to correct any problems identified during the test. Initially, testing of the plan is done in sections and after normal business hours to minimize disruptions to the overall operations of the organization. As the plan is further polished, future tests occur during normal business hours.

text: Types of tests include: checklist tests, simulation tests, parallel tests, and full interruption tests.

text: Obtaining plan approval[edit]

text: Once the disaster recovery plan has been written and tested, the plan is then submitted to management for approval. It is top management’s ultimate responsibility that the organization has a documented and tested plan. Management is responsible for (1) establishing the policies, procedures and responsibilities for comprehensive contingency planning, and (2) reviewing and approving the contingency plan annually, documenting such reviews in writing.

text: Organizations that receive information processing from service bureaus will, in addition, also need to (1) evaluate the adequacy of contingency plans for its service bureau, and (2)ensure that its contingency plan is compatible with its service bureau’s plan.

text: Caveats/controversies[edit]

text: Due to its high cost, disaster recovery plans are not without critics. Cormac Foster has identified five "common mistakes" organizations often make related to disaster recovery planning:[19]

text: Lack of buy-in[edit]

text: One factor is the perception by executive management that DR planning is "just another fake earthquake drill" or CEOs that fail to make DR planning and preparation a priority, are often significant contributors to the failure of a DR plan.

text: Incomplete RTOs and RPOs[edit]

text: Another critical point is failure to include each and every important business process or a block of data. "Every item in your DR plan requires a Recovery Time Objective (RTO) defining maximum process downtime or a Recovery Point Objective (RPO) noting an acceptable restore point. Anything less creates ripples that can extend the disaster's impact." As an example, "payroll, accounting and the weekly customer newsletter may not be mission-critical in the first 24 hours, but left alone for several days, they can become more important than any of your initial problems."

text: Systems myopia[edit]

text: A third point of failure involves focusing only on DR without considering the larger business continuity needs: "Data and systems restoration after a disaster are essential, but every business process in your organization will need IT support, and that support requires planning and resources." As an example, corporate office space lost to a disaster can result in an instant pool of teleworkers which, in turn, can overload a company's VPN overnight, overwork the IT support staff at the blink of an eye and cause serious bottlenecks and monopolies with the dial-in PBX system.

text: Lax security[edit]

text: When there is a disaster, an organization's data and business processes become vulnerable. As such, security can be more important than the raw speed involved in a disaster recovery plan's RTO. The most critical consideration then becomes securing the new data pipelines: from new VPNs to the connection from offsite backup services. Another security concern includes documenting every step of the recovery process—something that is especially important in highly regulated industries, government agencies, or in disasters requiring post-mortem forensics. Locking down or remotely wiping lost handheld devices is also an area that may require addressing.

text: Outdated plans[edit]

text: Another important aspect that is often overlooked involves the frequency with which DR Plans are updated. Yearly updates are recommended but some industries or organizations require more frequent updates because business processes evolve or because of quicker data growth. To stay relevant, disaster recovery plans should be an integral part of all business analysis processes, and should be revisited at every major corporate acquisition, at every new product launch and at every new system development milestone.