Question

Prove that if the number of states in a Markov chain is M, and if state j can be reached from state i, i.e. j is accessible from i, then it can be reached in M steps or less.

Answer 1

Overview of proof (by contradiction):

• Assume by contradiction it takes more than
  `M` steps to reach
  `j` from
  `i`.
• By assumption, the shortest path from
  `i` to
  `j` should includes more than
  `M` steps.
• Apply the pigeonhole principle to demonstrate that at least one state will be repeated along this path, forming a loop.
• Define a new path from the original path, bypassing the loop.
• Notice that this new path still goes from
  `i` to
  `j`. However, unlike the original path, this new path is strictly shorter because it skipped the loop.
• Arrive at a contradiction with the previous assumption: the original path isn't the shortest from
  `i` to
  `j`.

Step-by-step explanation:

Since state
`j` is accessible from state
`i`, there exists a path
`P = \lbrace s_(1),\, \dots,\, s_(n)\rbrace` where
`s_(1) = i` and
`s_(n) = j`. For
`P` to be a valid path,
`s_(x+1)` must be a neighbor of
`s_(x)` for each integer
`1 \le x \le m-1`. Notice that there are
`n` states in path
`P`, meaning that it would take
`(n - 1)` steps to go from
`i\!` to
`j` following this path.

Assume by contradiction it takes strictly more than
`M` steps to go from state
`i` to state
`j`. In other words, any path that goes from state
`i\!` to state
`j\!` should include at least
`(M + 1)` states.

Let
`P = \lbrace s_(1),\, \dots,\, s_(n)\rbrace` be the shortest path from state
`s_(1) = i` to state
`s_(n) = j`. Under the assumption,
`n > (M + 1)`.

Note that the number of states visited in
`P` exceeds the total number of states in this Markov chain:
`n > M`. By the pigeonhole principle, it is not possible to define an injective map from
`P` to the set of states
`S` because
`|P| > |S|`. In simpler words, at least one state in this Markov chain is repeated in the list of states visited along path
`P`.

Assume that the
`k`th state
`s_(k)` in path
`P` is repeated. There would exist an integer
`r` (
`r > 0`) such that
`s_(k) = s_(k+r)`:

`P = \lbrace s_(1),\, s_(2),\, \dots,\, s_(k),\, s_(k+1),\, \dots,\, \underbrace{s_(k+r)}_{=s_(k)},\,s_(k+r+1),\, \dots,\, s_(n)\rbrace`.

Notice that
`s_(k+r+1)` is a neighbor of
`s_(k+r)`. However, because
`s_(k) = s_(k+r)`,
`s_(k+r+1)\!` is also a neighbor of
`s_(k)`. The following would also be a valid path between
`s_(1) = i` and
`s_(n) = j`.:

`P^(\prime) = \lbrace s_(1),\, s_(2),\, \dots,\, s_(k),\, s_(k+r+1),\, \dots,\, s_(n)\rbrace`.

However, path
`P^(\prime)` contains
`r` fewer steps than path
`P`. This observation is a contradiction of the previous assumption that path
`P\!` is the shortest path from state
`i` to state
`j`.

In simpler words, between step
`k` and step
`(k+r-1)`, the original path
`P` went through a loop of
`r` steps (
`r > 0`) that eventually goes back to
`s_(k)`. Skipping this loop creates a new path
`P^(\prime)`, which is also a valid path between
`s_(1) = i` and
`s_(n) = j`. However, the new path would be strictly shorter than the original path, which leads to a contradiction.