49.8k views
4 votes
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.

1 Answer

7 votes

Answer:

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
kth 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.

User Yansigner
by
8.1k points