Discrete Markov Chain
Definition
A discrete stochastic process $\left\{ X_{n} \right\}$ whose state space is a countable set and which satisfies the following is called a discrete Markov chain (DTMC), or simply a Markov chain (MC). $$ p \left( X_{n+1} = j \mid X_{n} = i , X_{n-1} = k , \cdots , X_{0} = l \right) = p \left( X_{n+1} = j \mid X_{n} = i \right) $$
See Also
Explanation
$p_{ij}:= p \left( X_{n+1} = j \mid X_{n} = i \right)$ is called the transition probability, and $i$, which denotes the current state, is called the source state, while $j$, which denotes the target state, is called the target state. The transition probability after $k$ steps is denoted as $p_{ij}^{(k)}: = p \left( X_{n+k} = j \mid X_{n} = i \right)$.
A Markov chain is a stochastic process in which the probability of the next step given the entire history so far is the same as the probability of the next step given only the present. Simply put, it is a stochastic process in which, as long as the current state is known exactly, the past has no influence on the future. This property is commonly called memorylessness. Naturally, with such an assumption, calculations and everything else become extremely convenient.
For example, suppose we model the probability of precipitation with a Markov chain. Assume that regardless of whether it rained yesterday or not, tomorrow’s probability of rain depends only on whether it rained today. Let the state where it rained be $0$ and the state where it did not rain be $1$, and let $$\begin{matrix} p_{00} = 0.7 & p_{01} = 0.3 \\ p_{10} = 0.4 & p_{11} = 0.6 \end{matrix}$$ This means that if it rained today, the probability that it also rains tomorrow is $70 %$ and the probability that it does not rain is $30 %$; if it did not rain today, the probability that it also does not rain tomorrow is $60 %$ and the probability that it rains is $40 %$.
Now, let us simplify such probability calculations by means of a matrix like $$P:= \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{bmatrix} = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} $$ Such a matrix is called a transition probability matrix, and the transition probability matrix after $k$ steps is denoted as $P^{(k)}:= \left( p_{ij}^{ ( k ) } \right)$. As a useful property of the transition probability matrix, $P^{(n)} = P^{n}$ can be proven via the Chapman-Kolmogorov equation.
If it rained today, the probability of rain two days later is $$ \begin{align*} P^{ (2) } =& P^{2} \\ =& \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \\ =& \begin{bmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{bmatrix} \end{align*} $$ and this matches exactly with $p_{00}^{(2)} = (0.7)^2 + (0.3) (0.4) = 0.61$. Since the problems we are usually interested in are more complicated than this and concern the relatively distant future, we can see that handling such matrices is essential.
Mathematical Definition of the Transition Probability Matrix
For reference, summing all the entries in the same row of a transition probability matrix always yields $1$, which is obvious since summing the probabilities of all next steps gives $1$. Expressed as a formula, this is $\displaystyle \sum_{j} p_{ij} = 1$. Depending on where one studies stochastic process theory, this property may even be taken as a definition outright.