0
$\begingroup$

I am reading these university notes (https://web.stanford.edu/class/cs265/Lectures/Lecture14/l14.pdf) on Page 3.

The following statement is written:

Theorem 1 (The Fundamental Theorem of Markov Chains): Let $X_0, X_1, \ldots$ be a Markov chain over a finite state space, with transition matrix $P$. Suppose that the chain is irreducible and aperiodic. Then the following hold:

  1. There exists a unique stationary distribution, $\pi = (\pi_1, \pi_2, \ldots)$ over the states such that: for any states $i$ and $j$, $$\lim_{{t \to \infty}} Pr[X_t = i|X_0 = j] = \pi_i.$$
  1. For each state $i$, $\pi_i = \frac{1}{E[\min(t:X_t=i)|X_0=i]}$, namely $\pi_i$ is the inverse of the expected return time of state $i$.
  1. $\pi$ is a left eigenvector of matrix $P$, with eigenvalue 1, namely the vector-matrix product $\pi P = \pi$.

My Question: I am trying to find a proof for 2:

For each state $i$, $\pi_i = \frac{1}{E[\min(t:X_t=i)|X_0=i]}$, namely $\pi_i$ is the inverse of the expected return time of state $i$.

I found some corresponding videos (i.e. same author as the notes, Dr. Wootters) to these notes in which a proof for 1 is provided (https://www.youtube.com/watch?v=U3nJFDs7fUc&list=PLkvhuSoxwjI_JL7GYcJHK7-EK55t0KYGO&index=30), but I have not been able to find a proof for 2.

Can someone please help me understand how this proof can be done?

Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

One reference which has this proof is Introduction to Probability for Computing by Harchol-Balter, specifically Theorem 25.12 [PDF link].

$\endgroup$
1
  • 1
    $\begingroup$ @ Ziv: Wow, this is a very good link. thank you! $\endgroup$
    – stats_noob
    Commented Apr 14 at 3:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .