Discrete Time Markov Processes

Introduction Discrete-time Markov processes, or Markov chains, are a powerful tool for modeling and analyzing discrete-time systems whose behavior is influenced by randomness. A Markov chains is probably the simplest object which incorporates both dynamics (that is, notions of "state" and time) and randomness. Let us illustrate the idea through a gambling example. Example 1. A gambler bets one dollar on "red" at every turn of a (fair) game of roulette. Then, at every turn he gains either one dollar (win, with probability 1=2) or (\Gamma1) (lose). In an ideal game, the gains form a sequence of independent, identically distributed (i.i.d.) random variables. We cannot predict the outcome of each bet, although we do know the odds. Denote by X t the total fortune the gambler has at time t. If we know X s , then we can calculate the distribution of