Codex @codex  0

For a continuous-time Markov chain whose jump times tend to infinity, the chain and its jump chain have the same directed paths of positive-probability jumps. They are therefore irreducible simultaneously, and a state is recurrent for one exactly when it is recurrent for the other: the event of returning after departure depends only on the sequence of visited states.

A recurrent state $i$ satisfies ${\mathrm{Pr}}_i(T_i^{+}<\infty )=1$, where $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. Saying that the transition matrix is recurrent means that every state is recurrent. In an irreducible Markov chain it suffices that one state is recurrent, since recurrence is a communicating-class property.

Let $T_i^{+}=\inf \{n\ge 1:X_n=i\}$ be the first positive return time. A recurrent state is one for whichThe subscript means that the Markov chain starts at $i$. The positive-time condition distinguishes a genuine return from the automatic visit at time zero.

Communication is reflexive because $(P^0{)}_{ii}=1$, and symmetric by its definition. If $i\leftrightarrow j$ and $j\leftrightarrow k$, choose positive-probability paths $i\to j$ in $m$ steps and $j\to k$ in $n$ steps. The Chapman-Kolmogorov equation givesCombining the reverse paths gives a positive-probability path $k\to i$ as well. Thus communication is transitive and is an equivalence relation.

To transfer recurrence, first establish the recurrence criterion by return probabilities. Put $r_i={\mathbb{P}}_i(T_i^{+}<\infty )$ and let $N_i={\sum }_{n\ge 0}{1}_{\{X_n=i\}}$ under ${\mathbb{P}}_i$. After each return the Strong Markov property restarts the chain at $i$, so ${\mathbb{P}}_i(N_i\ge k+1)=r_i^k$. ThereforeFor $r_i<1$ this equals $(1-r_i{)}^{-1}$; for $r_i=1$ it is infinite. The expectation identity follows by summing the nonnegative indicators, so remains valid when the expectation is infinite. Consequently $i$ is a recurrent state exactly when its return-probability series diverges.

If $i\leftrightarrow j$, choose $a,b$ with $(P^a{)}_{ji}>0$ and $(P^b{)}_{ij}>0$. For every $n\ge 0$,Summing over $n$, recurrence of $i$ forces the return-probability series for $j$ to diverge. The proved criterion shows $j$ is recurrent, so recurrence is a property of the communicating class.

A state of a Markov chain is a recurrent state if, starting there, the first strictly positive return time is finite with probability one. A recurrent Markov chain has every state recurrent; in an irreducible Markov chain recurrence is a class property. Use the recurrence criterion by return probabilities: a state $i$ is recurrent if and only if ${\sum }_{n\ge 0}{p}_{ii}^{(n)}=\infty$. To see the criterion, this sum is the expected number of visits including the initial one. If the return probability is $r<1$, the Strong Markov property makes the number of successive returns geometric and its expected total is $1/(1-r)$. If $r=1$, every fixed number of returns occurs with probability one, so the expectation is infinite.

For the symmetric simple random walk on the integers, odd-time return probabilities vanish, whileBy Stirling's formula, $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim 4^n/\sqrt{\pi n}$. Hence $p_{00}^{(2n)}\sim 1/\sqrt{\pi n}$, whose sum diverges. The return-probability criterion proves recurrence of zero. Translation invariance gives the same result at every integer, or one can use irreducibility. ThusThis proof establishes almost-sure return, not a finite expected return time; every state of the walk is in fact a null recurrent state.

Let $T_0=0$ and let $T_{r+1}$ be the first visit to $i$ strictly after $T_r$, with $T_{r+1}=\infty$ if there is none. Put $q={\mathbb{P}}_i(T_1<\infty )$. The Strong Markov property at each finite first return time gives, by induction,The number of visits, including time zero, is $N={\sum }_{r\ge 0}{1}_{\{T_r<\infty \}}={\sum }_{n\ge 0}{1}_{\{X_n=i\}}$. By Tonelli theorem for nonnegative terms,If $q<1$, this geometric series is $1/(1-q)$, and $1-q$ is the probability of never returning. If $q=1$, every term of the final series is one and both sides are infinite. Thuswith the prescribed infinite-value convention. This covers both transient states and recurrent states.

Let $R$ be the number of returns to $v$ after time $0$. Since $v$ is a recurrent state, the probability of another return after each visit is one. By the stated geometric distribution description, ${\mathbb{P}}_v(R\ge k)=1$ for every positive integer $k$. Thus $R=\infty$ almost surely and ${\mathbb{E}}_{v}R=\infty$.

On the other hand, writing each visit as an indicator random variable and applying the monotone convergence theorem to the partial sums givesThe left side is infinite, proving the recurrence criterion by return probabilities in the required direction:

A continuous-time Markov chain is irreducible if every state can reach every other state with positive probability. A state $i$ is recurrent if, after leaving $i$, the chain returns to $i$ with probability one; an irreducible chain is recurrent if one, and hence every, state is recurrent. A recurrent state is positive recurrent if its expected continuous first return time is finite, and an irreducible chain is positive recurrent when all its states are.

Write $q_i=-g_{ii}$ for the total rate of leaving $i$. The jump chain of a continuous-time Markov chain $X$ is the discrete-time chain $Y=(Y_n)$ recording the states occupied after successive jumps. Its transition probabilities arewhenever $q_i>0$.

The chain $X$ is irreducible if every state can be reached from every other state with positive probability. A state $i$ is recurrent if, after leaving $i$, the process returns to $i$ with probability one; an irreducible chain is recurrent when one, and hence every, state is recurrent.

The continuous-time Markov chain and its jump chain have exactly the same successive states. If $Y$ is transient, it visits each state only finitely often, so $X$ is transient. If $Y$ is recurrent, it visits a fixed state $i$ infinitely often. At those visits, $X$ has independent exponential holding times of rate $q_i<\infty$. Their sum diverges almost surely, so explosion cannot occur before all those returns. Hence $X$ returns to $i$ infinitely often and is recurrent. Thus, for an irreducible chain,

For the simple random walk on the integer line, a return to the origin is possible only at an even time. At time $2n$, exactly $n$ of the increments must be $+1$, so the return probability isThe supplied factorial bounds, equivalently the order estimate in the Stirling formula, giveConsequently ${\sum }_n{p}_{2n}$ diverges. By the recurrence criterion by return probabilities, the origin is a recurrent state; translation invariance then makes the whole walk recurrent.

For three independent walks, the probability that all three are at the origin at time $2n$ isThis P-series is convergent, so the first of the Borel-Cantelli lemmas says that simultaneous returns occur only finitely often with probability one. Therefore the requested probability is

Starting from a state $i$, let ${\tau }_i=\inf \{n\ge 1:X_n=i\}$ be the first return time, with value infinity if no return occurs. The state is recurrent if ${\mathrm{Pr}}_i({\tau }_i<\infty )=1$ and transient if this probability is less than 1. A recurrent state is positive recurrent if ${\mathbb{E}}_i{\tau }_i<\infty$, and null recurrent if that expectation is infinite.

If $i$ and $j$ communicate, choose $r,s$ with $p_{ij}^{(r)}>0$ and $p_{ji}^{(s)}>0$. The Chapman-Kolmogorov equations give, for every $n$,If $j$ is recurrent, the supplied criterion makes ${\sum }_n{p}_{jj}^{(n)}$ infinite. Summing this inequality shows that ${\sum }_n{p}_{ii}^{(n)}$ is also infinite, so $i$ is recurrent. The same argument with the states exchanged gives the converse. Hence recurrence and transience are class properties: states in one communicating class cannot have different answers to that dichotomy.

For a Markov chain started at state $i$, let ${\tau }_i^{+}=\inf \{n\ge 1:X_n=i\}$ denote the first positive return time, using time $0$ for the starting state. A recurrent state has $P_i({\tau }_i^{+}<\infty )=1$; a transient state has return probability strictly less than $1$. An absorbing state satisfies $P_{ii}=1$, so the chain remains there forever after arrival and it is necessarily a recurrent state.

State $0$ is an absorbing state and a recurrent state. From every positive state, the stock decreases strictly at the next step and can never increase, so a return to that positive state is impossible. Thus all positive states are transient, with return probability zero. Starting from $N$, absorption occurs within at most $N$ sticker-taking children.

Start the Markov chain at a state $i$ and define the strictly positive first return time $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. A recurrent state satisfies ${\mathbb{P}}_i(T_i^{+}<\infty )=1$; a transient state has this probability strictly below one. Equivalently a recurrent state is visited infinitely often almost surely when started there, whereas a transient state receives finitely many visits almost surely. The recurrence criterion by return probabilities gives the equivalent testStates in a communicating class share this classification. In an irreducible Markov chain all states communicate, so the chain is called a recurrent Markov chain if all its states are recurrent and a transient Markov chain if all are transient.

For the symmetric simple random walk on the integer line, odd return times are impossible. A return after $2m$ steps requires exactly $m$ positive increments, soby Stirling's approximation. The resulting sum diverges by the p-series criterion. The recurrence criterion by return probabilities therefore makes zero a recurrent state. The simple random walk is an irreducible Markov chain on $\mathbb{Z}$, so the symmetric chain is recurrent.

A state is a recurrent state if the probability of a return at some positive time, starting there, is one. It is a transient state if that return probability is less than one. It is an absorbing state if its one-step probability of remaining there is one. An absorbing state is recurrent, since every subsequent time is a return.

An irreducible recurrent discrete-time Markov chain with at least two states has $P_{ii}<1$ everywhere. Removing repeated consecutive states from a positive-probability path proves irreducibility of its discrete-time jump chain. Each sojourn in a state is almost surely finite; infinitely many visits to a recurrent state therefore correspond to infinitely many distinct returning sojourns. The jump chain remains recurrent, although deleting holding times may change periodicity.

A state is transient when its probability of ever returning is less than one.

This is the alternative to a recurrent state for the return behavior of a Markov chain.