Answer:
Overview of proof (by contradiction):
- Assume by contradiction it takes more than
steps to reach
from
. - By assumption, the shortest path from
to
should includes more than
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
to
. 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
to
.
Step-by-step explanation:
Since state
is accessible from state
, there exists a path
where
and
. For
to be a valid path,
must be a neighbor of
for each integer
. Notice that there are
states in path
, meaning that it would take
steps to go from
to
following this path.
Assume by contradiction it takes strictly more than
steps to go from state
to state
. In other words, any path that goes from state
to state
should include at least
states.
Let
be the shortest path from state
to state
. Under the assumption,
.
Note that the number of states visited in
exceeds the total number of states in this Markov chain:
. By the pigeonhole principle, it is not possible to define an injective map from
to the set of states
because
. In simpler words, at least one state in this Markov chain is repeated in the list of states visited along path
.
Assume that the
th state
in path
is repeated. There would exist an integer
(
) such that
:
.
Notice that
is a neighbor of
. However, because
,
is also a neighbor of
. The following would also be a valid path between
and
.:
.
However, path
contains
fewer steps than path
. This observation is a contradiction of the previous assumption that path
is the shortest path from state
to state
.
In simpler words, between step
and step
, the original path
went through a loop of
steps (
) that eventually goes back to
. Skipping this loop creates a new path
, which is also a valid path between
and
. However, the new path would be strictly shorter than the original path, which leads to a contradiction.