Irreducible and aperiodic Markov chain : $P^t(x,y)>0$ Consider a Markov chain $X$ with transition probability $P$ and finite state space $\Omega$.
Which of the following statement is true?


*

*If $X$ is irreducible then $\exists t>0 \ni P^t(x,y)>0, \forall x,y\in\Omega$.

*If $X$ is irreducible and aperiodic then $\exists t>0 \ni P^t(x,y)>0, \forall x,y\in\Omega$.
I think it's (2.), and (1.) is false, but I can't find how to prove it.
 A: HINT You are correct that (1.) is false and (2.) is true. (1.) has a very simple counter-example, which I will leave you to figure out. Here I give a proof sketch for (2.).
[Added:] This is a roundabout proof compared to Byron's elegant one, but this is the proof that first came to my mind. :)
For each $x \in \Omega$, let $C(x)$ be the set of lengths of walks from $x$ to $x$ with positive probability. The aperiodicity condition says that the set $C(x)$ has gcd $1$. Therefore, there exist $a_1, a_2, \ldots, a_m \in C(x)$ such that $\gcd(a_1, a_2, \ldots, a_m)=1$. 
The proof then proceeds in the following stages:


*

*(This is the crucial step of the proof.) For any collection of numbers $\{ a_1, a_2, \ldots, a_m \}$ with gcd equal to $d$, show that there exists a number $T \in \mathbb Z_{\geq 0}$, such that the following holds: if $t \geq T$ and $t$ is a multiple of $d$, then $t$ can be expressed a nonnegative integer combination of $a_1, \ldots, a_m$. This means that there exist $q_1, q_2, \ldots, q_m \in \mathbb Z_{\geq 0}$ such that
$$
t = q_1 a_1 + q_2 a_2 + \ldots + q_m a_m.
$$
HINT One way to prove this statement will be via mathematical induction and Bézout's identity. (See below for some more details on this problem.)

*For $x \in \Omega$, there exists a number $T_x \in \mathbb N$, such that for all $t \geq T_x$, there exists a walk from $x$ to $x$ (of positive probability) of length exactly $t$. 

*For all $y \in \Omega$ and all $t \geq T_x+n$, there exists a walk from $x$ to $y$ (of positive probability) of length exactly $t$.

*Show how to conclude the claim in the question from the above statement. 



More details on Step 1. 
Step 1 is related to the so-called Frobenius coin problem. In the coin problem, we are given a number of denominations $a_1, a_2, \ldots, a_m$ (that do not have any nontrivial common factor), and are asked to compute the largest denomination $g$ such that $g$ cannot be expressed as an integer linear combination of these denominations. The proof that I have left as exercise essentially asks you to show that such a $g$ exists (i.e., it is finite). Moreover, in our notation, $T$ is at least $g+1$. 
A: For an irreducible, aperiodic Markov chain on 
a finite state space, we have 
$P^t(x,y)\to\pi(y)>0$
where $\pi$ is the unique invariant probability
distribution of the chain. Since the values $\pi(y)$ are all strictly positive, the  result follows.       
