Tutorials › Stochastic Processes › Periodicity and the Timing of Returns

Home  /  Tutorials  /  Recurrence and Transience

Recurrence and Transience · Tutorial 174 of 994

Periodicity and the Timing of Returns

Use return-time supports and their greatest common divisor to identify periodicity, while assessing recurrence from the total probability of ever returning.

Advanced 10 min read

What You'll Learn

  • Define a state’s period from the possible positive return times.
  • Relate first-return times to return probabilities at fixed times.
  • Prove that possible first-return times have the same greatest common divisor as possible return times.
  • Compute the return-time law in a recurrent bipartite chain.
  • Identify the period and recurrence type of a deterministic cycle.
  • See why a transient chain can still have period two.

Return times have a rhythm

A chain can be certain to return to a state eventually while being unable to return at many particular times. In a bipartite chain, for example, every step switches sides, so a return to the starting state can occur only after an even number of steps. This timing constraint is described by the state’s period. Period is about which return times are possible; recurrence is about whether a return eventually occurs with probability one. Those are different questions.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Write \(\mathbb{P}_i\) for probabilities when \(X_0=i\). For a state \(i\), the first return time is \(T_i^+=\inf\{n\ge1:X_n=i\}\), with \(\inf\varnothing=\infty\). The return probability at time \(n\) is \(p_{ii}^{(n)}=\mathbb{P}_i(X_n=i)\).

Definition: For a state \(i\) that can return to itself in a positive number of steps, its period is \(d(i)=\gcd\{n\ge1:p_{ii}^{(n)}>0\}\). A state is recurrent if \(\mathbb{P}_i(T_i^+<\infty)=1\), and transient if \(\mathbb{P}_i(T_i^+<\infty)<1\). The period records the common timing constraint on returns; it does not, on its own, specify which of these two recurrence classifications applies.

Here \(p_{ii}^{(n)}>0\) means that there is positive probability of being back at \(i\) at time \(n\), not necessarily that the first return occurs at time \(n\). The distinction matters: a path that is at \(i\) at time \(n\) may have visited \(i\) earlier. The first-return probabilities are \(f_n=\mathbb{P}_i(T_i^+=n)\), for \(n\ge1\). Their sum is the probability of ever returning because the events \(\{T_i^+=n\}\) are disjoint.

What the period says about return times

Theorem: For a state \(i\) with at least one possible positive return, the greatest common divisor of the possible first-return times is \(d(i)\). In particular, every possible first-return time is a multiple of \(d(i)\), and \(p_{ii}^{(n)}=0\) whenever \(n\) is not a multiple of \(d(i)\). The recurrence classification is instead determined by \(\sum_{n\ge1} f_n\): the state is recurrent exactly when this sum is \(1\), and transient exactly when it is less than \(1\).

Proof. Let \(R=\{n\ge1:p_{ii}^{(n)}>0\}\), and let \(F=\{n\ge1:f_n>0\}\). If \(n\in F\), the chain returns for the first time at \(n\), so \(n\in R\). Thus every common divisor of \(R\) divides every element of \(F\). In the other direction, for any \(n\in R\), there is positive probability of a return at time \(n\). Such a return path has a first return at some time \(r_1\in F\); if the path returns again before time \(n\), it has further first-return segments of lengths \(r_2,\ldots,r_k\in F\). The lengths add to \(n\). Hence every common divisor of \(F\) divides \(n\), and so divides every element of \(R\). The two sets therefore have the same greatest common divisor. In particular, each element of \(F\) is divisible by \(d(i)\), and each possible return time in \(R\) is divisible by \(d(i)\), proving the timing statements. Finally, \(\{T_i^+=n\}\), \(n\ge1\), are disjoint and their union is \(\{T_i^+<\infty\}\). Countable additivity gives \(\mathbb{P}_i(T_i^+<\infty)=\sum_{n\ge1}f_n\), which proves the recurrence statements by the definitions. \(\square\)

The theorem does not assert that every multiple of the period is a possible return time. A greatest common divisor describes a common divisibility constraint, not the whole support of a return-time distribution. In particular, zeros in the return probabilities at some times are not evidence by themselves of transience. The examples show how the same timing restriction can coexist with different recurrence classifications.

Worked Example: A Recurrent Bipartite Chain

Let \(S=\{a,b,c,d\}\), with the two sides \(\{a,b\}\) and \(\{c,d\}\). From either state on one side, the chain moves to each state on the other side with probability \(\tfrac12\). In the order \(a,b,c,d\), the transition matrix is

$$ P= \begin{bmatrix} 0&0&\tfrac12&\tfrac12\\ 0&0&\tfrac12&\tfrac12\\ \tfrac12&\tfrac12&0&0\\ \tfrac12&\tfrac12&0&0 \end{bmatrix}. $$

Each row sums to \(\tfrac12+\tfrac12=1\), so this is a transition matrix. Every step switches sides. Starting at \(a\), the chain therefore cannot return at an odd time, while a return in two steps has positive probability. At every even time \(2k\), \(k\ge1\), the chain is on the \(\{a,b\}\) side, and its location is equally likely to be \(a\) or \(b\). Thus \(p_{aa}^{(2k)}=\tfrac12\), all odd-time return probabilities are zero, and \(d(a)=2\).

To find the first-return law, group steps into pairs. At each positive even time, conditional on being on the \(\{a,b\}\) side, the chain is at \(a\) with probability \(\tfrac12\) and at \(b\) with probability \(\tfrac12\). Consequently, the probability that the first return occurs at time \(2k\) is the probability of missing \(a\) at the first \(k-1\) such checks and then being at \(a\) at the \(k\)th check:

$$ \mathbb{P}_a(T_a^+=2k)=\left(\tfrac12\right)^{k-1}\tfrac12=2^{-k},\qquad k\ge1. $$

The total return probability is \(\sum_{k\ge1}2^{-k}=1\), so \(a\) is recurrent, despite the impossibility of returning at any odd time. The mean return time is also finite: using \(\sum_{k\ge1}k x^k=x/(1-x)^2\) for \(0\le x<1\), obtained by differentiating the geometric series, gives \(\mathbb{E}_a[T_a^+]=2\sum_{k\ge1}k2^{-k}=2\cdot2=4\).

Check: The first-return probabilities sum to \(\sum_{k\ge1}2^{-k}=1\), as required for recurrence. At time \(2\), direct multiplication gives \(p_{aa}^{(2)}=p_{ac}p_{ca}+p_{ad}p_{da}=\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12=\tfrac12\), consistent with the return probability computed above.

Worked Example: A Deterministic Cycle

Consider the chain on \(S=\{0,1,2\}\) that moves from \(0\) to \(1\), from \(1\) to \(2\), and from \(2\) to \(0\), each with probability \(1\). Its transition matrix is

$$ P= \begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}. $$

Every row sums to \(1\). Starting from \(0\), the chain is at \(1\) after one step, at \(2\) after two steps, and back at \(0\) after three steps. The same cycle then repeats. Therefore \(T_0^+=3\) with probability \(1\), and all possible return times are \(3,6,9,\ldots\). Their greatest common divisor is \(3\), so \(d(0)=3\). Since the return occurs with probability one, state \(0\) is recurrent. Its mean return time is \(3\).

Check: The first-return probabilities are \(f_3=1\) and \(f_n=0\) for \(n\ne3\). Their sum is \(1\), and their support has greatest common divisor \(3\). This verifies both recurrence and the claimed period directly from the return-time law.

Periodicity does not determine recurrence

The bipartite example is recurrent with period two, and the deterministic cycle is recurrent with period three. A periodic chain can also be transient. The next example uses an irreducible chain on the integers: from every integer it steps right with probability \(\tfrac23\) and left with probability \(\tfrac13\). Each row of its transition matrix has exactly these two nonzero entries, whose sum is \(\tfrac23+\tfrac13=1\). A step changes the parity of the integer, so any return to the starting integer must take an even number of steps. A two-step return has positive probability, making the period two. We compute the return probability to see why the chain is nevertheless transient.

Worked Example: A Transient Chain of Period Two

Write \(p=\tfrac23\) for the probability of a step right and \(q=\tfrac13\) for the probability of a step left. Starting at \(0\), the first step is to \(1\) with probability \(p\) or to \(-1\) with probability \(q\). We first compute the probability of hitting \(0\) from \(1\).

For an integer \(N>1\), let \(h_i\) be the probability, starting at \(i\in\{0,\ldots,N\}\), of hitting \(0\) before \(N\). The boundary values are \(h_0=1\) and \(h_N=0\), and first-step conditioning gives \(h_i=qh_{i-1}+ph_{i+1}\) for \(1\le i<N\). Put \(r=q/p=\tfrac12\). The values \(h_i=(r^i-r^N)/(1-r^N)\) satisfy both boundary conditions. They satisfy the interior equation because \(qr^{i-1}+pr^{i+1}=r^i(q/r+pr)=r^i(p+q)=r^i\), and the constant term is also preserved since \(p+q=1\). These boundary equations have a unique solution: if two solutions differ, their difference has boundary values zero, and a positive maximum or negative minimum at an interior state contradicts its expression as a weighted average of its neighbors. Thus, from state \(1\), the probability of hitting \(0\) before \(N\) is

$$ h_1=\frac{\tfrac12-2^{-N}}{1-2^{-N}}. $$

As \(N\) increases, these events increase to the event of ever hitting \(0\) from \(1\): any path that hits \(0\) does so after finitely many steps and has a finite maximum before that hit. Taking the limit gives \(\mathbb{P}_1(T_{\{0\}}<\infty)=\tfrac12\). From \(-1\), the probability of hitting \(0\) is \(1\). Indeed, in the interval \(\{-M,\ldots,0\}\), the probability from \(-1\) of hitting \(0\) before \(-M\) is \((1-r^{M-1})/(1-r^M)\), which tends to \(1\) as \(M\) tends to infinity. The events increase to eventual hitting of \(0\), since any finite path that reaches \(0\) has a finite minimum.

Conditioning on the first step from \(0\), the probability of ever returning is therefore \(p\cdot\tfrac12+q\cdot1=\tfrac23\cdot\tfrac12+\tfrac13=\tfrac23\). This is less than \(1\), so \(0\) is transient. Returns can only occur at even times by parity, and a return in two steps has probability \(pq+qp=2\cdot\tfrac23\cdot\tfrac13=\tfrac49>0\); hence the period is two.

Check: The two possible first-step routes contribute \(\tfrac13\) from the step left and \(\tfrac13\) from the step right followed by eventual hitting from \(1\). Their sum is \(\tfrac23\), confirming the return probability and the transient classification.

A common misreading

A common mistake is to see \(p_{ii}^{(n)}=0\) at some times and conclude that \(i\) is transient. For the bipartite chain, this would treat the zero probability of an odd-time return as evidence that the chain might never return. That confuses a timing restriction with the probability of eventual return.

Wrong calculation: “Since \(p_{aa}^{(1)}=0\), the chain has probability zero of returning, so \(a\) is transient.” This uses the probability of return at one particular time as though it were the probability of ever returning. Correction: sum the first-return probabilities over all possible return times. In the bipartite example, \(\sum_{k\ge1}\mathbb{P}_a(T_a^+=2k)=\sum_{k\ge1}2^{-k}=1\), so \(a\) is recurrent. The zeros at odd times describe the period, not a failure to return.

Keep the two questions separate: the period is the greatest common divisor of possible return times; recurrence is determined by the total probability of a finite return. In particular, neither a period greater than one nor a gap in the return-time support is, by itself, a recurrence classification.

Check Your Understanding

Use the return-time support and total return probability as separate checks.

  1. If a state can return only at times \(4,8,12,\ldots\), what is its period? Does this information alone determine whether the state is recurrent?
  2. In the bipartite example, why does \(p_{aa}^{(2k)}=\tfrac12\) for every \(k\ge1\) not mean that the first return occurs at each even time with probability \(\tfrac12\)?
  3. A deterministic cycle has length \(5\). Starting at one of its states, give the first-return time, the period, and the recurrence classification.
  4. For a state with first-return probabilities \(f_2=\tfrac14\), \(f_4=\tfrac14\), and \(f_n=0\) at all other times, identify its period and recurrence classification.
  5. Why can a return probability at one fixed time not be substituted for \(\mathbb{P}_i(T_i^+<\infty)\)?

Previous

Next

Back to Tutorials