In many applications, some variables evolve over time in a random (stochastic) way in that even if you know

everything up to time t, it is still impossible to know for sure which values the variables take in the future.

Stochastic processes are mathematical models that describe these phenomena when the randomness is driven

by something out of the control of the relevant decision makers. For example, the stock prices can be (and

usually are) modeled as stochastic processes, since it is difficult for an investor to affect them. However, in a

chess game, the uncertainty in your opponents' future moves are not modeled as stochastic processes as they

are made by a decision maker with the goal to defeat you and they may be adjusted based on your moves.

One simple and widely used class of stochastic processes are Markov chains. In this question, we study

Markov chains on a finite state space. There is a sequence of random variables x0, x1, ..., xt, ..., each taking

value in a finite set S called the state space. The subscripts have the interpretation of time. Therefore given

an integer time t, x0, ..., xt are assumed to be known at the time, while xt+1, xt+2, ... remain random. For

convenience, we label states with positive integers: S = {1, ..., n}, where n is the number of possible states.