A Markov chain whose state space is given by the integers i = 0,±1,±2, . . . is said to be a random walk if, for some number 0 < p < 1, Pi,i+1 = p = 1 − Pi,i−1, i = 0,±1, . . .

The preceding Markov chain is called a random walk for we may think of it as being a model for an individual walking on a straight line who at each point of time either takes one step to the right with probability p or one step to the left with probability 1 − p.