Consider the Markov chain shown in Figure 11.35.

This is known as the simple random walk. Show that

Using Stirling's formula, it can be shown that

is finite if and only if p ≠ 1/2. Thus, we conclude that the simple random walk is recurrent if p = 1/2 and is transient if p ≠ 1/2.

Transcribed Image Text:

1-p P 1-p 1-pi Figure 11.35 - Simple random walk. 1-p 1-p 1-p