Our concern is the maxima of certain excursions of (2,1) and (1,2) random walks with asymptotically zero drift, which exhibit limit behaviors quite different from those of simple random walks. To study maxima of random walks, we need to develop some limit theories for both the product of nonnegative 2-by-2 matrices and continued fractions, which have their own interests. Now let us introduce precisely the model. Suppose that q k , p k , k ≥ 2 are numbers such that ∀k ≥ 2, q k , p k > 0, p k + q k = 1.
Let Y = {Y k } k≥0 be a Markov chain on Z + := {0, 1, 2, ...} starting from some y 0 ∈ Z + and with transition probabilities P (Y k+1 = 1|Y k = 0) = P (Y k+1 = 2|Y k = 1) = 1, P (Y k+1 = n + 1|Y k = n) = q n , P (Y k+1 = n − 2|Y k = n) = p n , n ≥ 2, k ≥ 0.
Introduce also another Markov chain Y ′ = {Y ′ k } k≥0 on Z + , starting from some y ′ 0 ∈ Z + and with transition probabilities
Unless otherwise stated, we always assume that both Y and Y ′ start from y 0 = y ′ 0 = 2. We call the chain Y a (2,1) random walk and Y ′ a (1,2) random walk. In literatures, Y ′ is called the adjoint chain of Y and vice versa.
Next, we define the so-called maxima we concern for the chains Y and Y ′ above. For X ∈ {Y, Y ′ }, we denote D(X) := inf{k ≥ 1 : X k < X 0 }, M(X) := sup{X k : 0 ≤ k ≤ D(X)}, (1) where and throughout, we use the convention inf φ = ∞. Clearly, D(X) is the time that the chain X hits some point below X 0 for the first time and M(X) is the maximum of the excursion {X 0 , X 1 , ..., X D }. When no danger of making confusion, we write D(X) and M(X) as D and M respectively for simplicity.
To begin with, let us consider (2,1) random walk Y. We aim to study the distribution of M(Y ) and its asymptotics as well. To this end, for k ≥ 2, introduce matrix
which we will work with. Throughout the paper, for a matrix A, we denote by ̺(A) its spectral radius. The proposition below gives the distribution of M(Y ) on the event {D(Y ) < ∞} in terms of N k , k ≥ 2. Proposition 1. Consider (2,1) random walk Y. For n ≥ 2, we have P (M = n, D < ∞) = 1 1 + n−1 s=2 e 1 N s · · · N 2 e t 1 e 1 N n · · · N 2 e t 1 1 + n s=2 e 1 N s · · · N 2 e t 1 .
Noticing that for simple random walk, N k ≡ N for some matrix N, thus it is easy to compute P (M = n, D < ∞) explicitly in terms of eigenvalues of N. However, for random walk with non-homogeneous transition probabilities, the righthand side of (3) involves the product of non-homogeneous matrices, which can not be computed implicitly any longer. So, it is even hard to see its asymptotics in general.
Firstly, let us see what happens to simple random walk. For k ≥ 2, set q k ≡ q ∈ (0, 1), p k ≡ p = 1 − q and N k ≡ N := p/q p/q 1 0 .
In this case, the chain Y is positive recurrent, null recurrent or transient according as q < 2/3, = 2/3 or > 2/3(or equivalently, ̺(N) > 1, = 1 or < 1), respectively. Some direct computation from (3) Here and in the rest of the paper, unless otherwise specified, 0 < c < ∞ is some constant, whose value may change from line to line. We can conclude that P (M(Y ) = n, D(Y ) < ∞) decays either exponentially if the walk is transient or positive recurrent, or polynomially with speed c/n 2 if the walk is null recurrent.
We next study the (2, 1) and (1, 2) random walks with asymptotically zero drifts, for which, P (M = n, D < ∞) decays with various speeds quite different from those of simple random walk. Adding some perturbations on the transition probabilities of a null recurrent simple random walk, we get a nearrecurrent random walk, known also as Lamperti random walk which dates back to Harris [9] and Lamperti [15] and has been extensively studied in literatures, refer for example, to [3, 4, 10, 12, 16, 23] etc. To introduce Lamperti random walk, we take the perturbations from [3] . For K = 1, 2, ... and B ∈ R, set
where log 0 i = i and for k ≥ 1, log k i = log log k−1 i. For K and B fixed, set
and let
which will serve as perturbations added on a null recurrent simple random walk. (5), we get (6) and vice versa.
(b) Fixing K = 1 and letting q i = 2/3 + r i , i ≥ 1, we shed some light on the null recurrent case to illustrate the difference between Lamperti random walk and simple random walk. If −1 ≤ B ≤ 1, then by Corollary 2 below, the chain Y is null recurrent and thus P (D < ∞) = 1. By (5), we have
So, even for null recurrent case, the decay speeds are quite sensitive to B. But, for null recurrent simple random walk, P (M = n) always decays polynomially with speed cn −2 .
(c) The difficulty for (2,1) random walk arises from the fact that the escape probabilities are functionals of the product of matrices, e 1 N k · · · N 2 e t 1 , which cannot be estimated directly. To overcome this, if we can show
then instead of estimating e 1 N k · · · N 2 e t 1 directly, it suffices to work with ̺(N k ) · · · ̺(N 2 ), which is able to be estimated. However, it is not an easy task to prove (7). In Theorem 3 below, we prove (7) for a sequence of more general 2-by-2 nonnegative matrices.
(d) It is shown in [22] that similar result holds for the nearest neighbor random walk. For the nearest-neighbor setting, if we denote by p ′ k the probability that the walk jumps from k to k + 1 in the next step whenever it is currently located at k, then with ρ k :=
, the escape probabilities are written in terms of ρ 1 · · · ρ n , which can be directly estimated. Therefore for this setting, things are much easier.
Next, we consider (1,2) random walk Y ′ . To derive similar result, besides the asymptotics of product of nonnegative matrices mentioned above, we need to develop some other techniques related to the limit periodic continued fractions and the hitting probabilities of the walk.
We now explain the idea and difficulty to prove Theorem 2.
. Then by Markov property, we can get P (M = n, D < ∞) = P n 2 (1, n, +)(1 − P n (1, n + 1, +)).
Similar to Lemma 6 below, by some computation, it can be shown that 1 − P n (1, n + 1, +) = 1 1 + n s=2 e 1 N s · · · N n e t 1 , P n 2 (1, n, +) = e 1 N 2 · · · N n−1
which are hard to estimate even though we have (7) in hands, since every summand there depends on n. The good news is that, in [17] , the escape probability P 2 (1, n, +) (NOT P n 2 (1, n, +) ) can be written in terms of the tail ξ n := θ −1
of a continued fraction, whose estimation has been given in [23] . However, to study the asymptotics of P (M = n, D < ∞), we need to know exactly what P n 2 (1, n, +) is, or at least, to find out its asymptotics. By constructing a new Markov chain related to Y ′ and analyzing the hitting probabilities of the new chain, Lemma 10 below shows that P n 2 (1,n,+) P n+1 2 (1,n,+) → 2, so that the term P n 2 (1, n, +) in (8) can be estimated. The formula for 1 − P n (1, n + 1, +) in (9) looks somewhat simple, but some special techniques are required to give its estimation. In Lemma 11 below, with the help of (7), by a delicate analysis of the product N s · · · N n and the continued fraction, we show that 1−P n (1, n+1, +) ∼ c ξ 2 ···ξn n+1 s=2 ξ 2 ···ξ s−1 , as n → ∞. So Theorem 2 can finally be proved.
Remark 2. Our results for both (2,1) and (1,2) random walks rely heavily on the asymptotics of continued fractions, which are related to the product of 2-by-2 nonnegative matrices. So our methods do not work for any other more general models, for example, (1, 3) or (3,1) random walks.
As explained above, product of nonnegative matrices are very useful when studying the limit behaviors of Markov chains and has been extensively studied in literatures, see for example [2, 5, 7, 8, 13, 14, 20] , etc. We also refer the readers to [21] for more general application of the product of nonnegative matrices in studies of Markov chains.
We consider some matrices more general than N k in (2). Let a k , b k , d k , k ≥ 1 be certain positive numbers and for k ≥ 1, set
Next, we introduce some conditions on the numbers a k , b k and d k , k ≥ 1.
Notice that under condition (B1), there are some constants 0 < c 1 < c 2 < ∞ and c 1 ≤ a, b, d ≤ c 2 such that
Thus under condition (B1), A k is convergent. Suppose now condition (B1) holds. Introduce further the follow conditions.
exists as an extending number.
exists as an extending number.
exists as an extending number. In addition, if τ is finite, assume further lim k→∞
exists as an extending number. Otherwise, if τ = ∞, assume further lim k→∞
exists as an extending number. 
for some λ 1 , λ 2 > 0, and (13) holds trivially.
(ii) If we replace condition (B1) by a new condition "(B1) ′ : for some numbers a, b, d > 0, lim k→∞ a k = a, lim k→∞ b k = b, lim k→∞ d k = d and in addition, 
exist and are finite, then the limit in (B2) a exists. Roughly speaking, it requires that a k , b k and d k may fluctuate in different orders, but should fluctuate in some common manner.
Let us explain the main idea to prove Theorem 3. For k ≥ 1, let x k :=
. As the first step, under condition (B1), in Lemma 1 below, we show that x k , k ≥ 1 is uniformly bounded from 0 and infinity. For this purpose, owing to [13] , we show first in Lemma 2 below that ζ ≤ ̺(A k ···A 1 ) ̺(A k )···̺(A 1 ) ≤ γ, ∀k ≥ 1 for some ζ, γ ∈ (0, ∞). Then using the ergodiciy theorem of product of nonnegative matrices( [21] ) and the theory of limit periodic continued fractions, we show in Lemma 3 that e 1 A k · · · A 1 e t 1 ∼ c̺(A k · · · A 1 ). Therefore for some
As the second step, we need to show that x k − x k−1 converges to 0 either exponentially fast or in an alternating manner. To this end, we first develop some fluctuation theory of the critical tail sequence of a limit periodic continued fraction, where one of conditions (B2) a , (B2) b and (B2) c is required, see Lemmas 4 and 5 below. Then, the fluctuation of x k − x k−1 can be studied with the help of that of the critical tail sequence of the continued fraction. Consequently, by the above two steps, x k is convergent, so that Theorem 3 can be proved.
The rest of the paper is organized as follows. Section 2 is devoted to proving Theorem 3. In Section 3, we study the (2,1) random walk Y to give the proof of Theorem 1. The maximum for (1,2) random walk Y ′ are studied in Section 4. Finally, the criteria for transience, null recurrence and positive recurrence of both the chains Y and Y ′ are presented in an appendix section.
The main task of this section is to prove Theorem 3. To begin with, we introduce some notations of continued fraction which will be used time and time again.
Let β k , α k , k ≥ 1 be certain numbers. We denote by
a continued fraction, and by
its n-th tail and its critical tail sequence respectively.
For k ≥ 1, let A k be the one in (10) . We have
In this subsection, we show that
, k ≥ 1 are uniformly bounded away from 0 and infinity.
Proof. The lemma is a direct consequence of Lemmas 2 and 3 below.
for some constants 0 < ζ < γ < ∞ independent of k.
Let v n be a right eigenvector of A n corresponding to the largest eigenvalue ̺(A n ). Then we can choose v n to be
For k ≥ 1, write
Applying [13, Theorem 1, page 228], for k ≥ 1, we have
It remains to show that both ζ −1 k , k ≥ 1 and γ k , k ≥ 1 are uniformly bounded away from ∞. To this end, set
Then by (11),
Therefore, by condition (B1),
, an similar argument also yields that lim k→∞ ζ −1 k < ∞. Lemma 2 is proved. Remark 4. If condition (B1) is replaced by (B1) ′ defined in Remark 3, then we may choose a right eigenvector corresponding to ̺(A n ) as
Let γ k and ζ k be those defined in (16) and (17). Under condition (B1) ′ ,
Since lim k→∞ γ k = lim k→∞ ζ −1 k = c for some 0 < c < ∞, then both γ k , k ≥ 1 and ζ k , k ≥ 1 are uniformly bounded away from 0 and infinity. Otherwise, if ̺(A n )/d n is decreasing in n, things can be done by a similar approach.
where a, b, d are those numbers in (12) . Then we have 0 < g < ∞ and
Proof. For k ≥ 1, write
We claim that
Indeed, an application of the ergodicity theorem of the product of nonnegative matrices(see [21, Theorem 3.3] ) yields the existence of the limits and the second equality in both (19) and (20) . To compute f and g, noticing that
where (21) follows by forward induction and (22) by backward induction. It follows from (21) that
By the theory of convergence of limit periodic continued fractions(see [19, Theorem 4.13 , page 188]), from (22), we have
Thus the claim is true and 0 < g < ∞.
By some easy computation, we obtain
Consequently, it follows from (19) and (20) that
The lemma is proved.
In this subsection, we study the tail sequence of a limit periodic continued fraction, which is helpful to prove Theorem 3.
Set
Let q be a fixed number. We have
Remark 5. Similar results hold for the tail f (n) of a limit periodic continued fraction, see [11] and [18] . But for the critical tail sequence, up to our knowledge, there is no such observation yet.
Proof. To prove the lemma, we follow [18, Theorem 6.1, page 91]. It follows from (25) that for k ≥ 2, f k (α k + f k−1 ) = β k and thus
Therefore we get
We first suppose that lim k→∞ ε k ε k+1 = q. By (19) , (21) and (24), we have
= ω, implying that lim k→∞ ε k = 0. Therefore |q| ≥ 1.
If we write η k+1 := ε k ε k+1 ω k+1 , k ≥ 1 and for k ≥ 2,
and lim k→∞β k = βq, lim k→∞α k = α + ω − qω.
Applying [19, Theorem 4.13, page 188], the limit η := lim k→∞ η k exists. Letting k → ∞ in (28), we get η = βq α+ω−ωq+η whose solutions are η = ωq or η = −(α + ω).
The lemma is proved.
The lemma below ensures the existence of the limit of δ k δ k+1 , so that the fluctuation of f k − ω k , k ≥ 1 can be studied. 
Then the limit lim k→∞ δ k δ k+1 exists as an extending number.
Proof. By condition (B1), we have β k → d/b =: β, α k → a/b =: α and
For simplicity, write temporarily S k := α 2 k + 4β k − α k , k ≥ 1. Then we have lim k→∞ S k = α 2 + 4β − α. Some direct computation yields that
Suppose now condition (B2) a holds. Then for some
exists as an extending number. Therefore
exists as an extending number. Consequently, by (29), lim k→∞ δ k δ k+1 exists as an extending number.
If condition (B2) b holds, then an similar argument also yields that lim k→∞ δ k δ k+1 exists.
Suppose condition (B2) c holds. Then ∃k 0 > 0 such that α k = α k+1 , β k = β k+1 , ∀k ≥ k 0 and
exists as an extending number. Furthermore if τ is finite, by assumption, we also have that
exists as an extending number. In this situation, taking (30) into account, we have
. Therefore, by (30), (31) and (32),
exists as an extending number. Consequently, we conclude from (29) that
exists as an extending number. Finally, if τ = ∞, then we must have lim k→∞ α k −α k+1 β k −β k+1 = 0 and by assumption,
exists as an extending number. Thus,
exists as an extending number. As a result, by (29), lim k→∞ δ k δ k+1 exists as an extending number. The lemma is proved.
We are now ready to prove Theorem 3. To begin with, for k ≥ 1 we write
for simplicity. In view of (19) and (20), it suffices to show that x k → c as k → ∞ for some 0 < c < ∞. It follows from Lemma 1 that there exist some constants 0 < c 3 < c 4 < ∞ independent of k such that
Let f k , k ≥ 1 be the one in (25) with β k = d k /b k , α k = a k /b k , k ≥ 1 and set
, k ≥ 1. Then
as k → ∞. Let δ k , k ≥ 1 and ε k , k ≥ 2 be those in (26).
By (19) , (21) and (24), we have lim k→∞ f k = √ a 2 +4bd−a 2b
= ω, implying that lim k→∞ ε k = 0.
An application of Lemma 5 yields that the limit lim k→∞ δ k δ k+1 exists as an extending number. Assume
Since lim k→∞ δ k = 0, we must have |q| ≥ 1. Applying Lemma 4, we have
Case 1: Suppose |q| > 1. Then λ 0 := min{|q|, a/b+ω ω } > 1. Fix some 1 < λ < λ 0 . By (34), there exists some k 0 > 0 such that ε k ε k+1 ≥ λ, for all k > k 0 .
Taking (14) and (21) into account, for k ≥ 1 we have
Since ̺(A k ), k ≥ 1 is uniformly bounded away from 0 and ∞, then by (33), we have for some constant 0 < c 5 < ∞,
Taking (33), (35) and (37) together, we conclude that for some constant 0 < c < ∞, lim k→∞ x k = c. Case 2: Suppose q = 1 and lim k→∞ ε k ε k+1 = − a/b+ω ω . Since a/b+ω ω > 1, the proof goes exactly the same as Case 1.
Case 3: Suppose q = 1 and lim k→∞ ε k ε k+1 = q. Then there exists some number k 1 > 0 such that ε k = f k − ω k , k ≥ k 1 are all strictly positive or strictly negative, and consequently
But
Thus, by (38), x k+1 x k < 1(or > 1) for all k ≥ k 1 , that is, x k , k ≥ k 1 is monotone. As a consequence, it follows from (33) that for some constant 0 < c < ∞ lim k→∞ x k = c.
Case 4. Suppose that q = −1 and lim k→∞ ε k ε k+1 = − a/b+ω ω . In this case, the proof is the same as Case 2.
Case 5. Suppose that q = −1 and lim k→∞ ε k ε k+1 = −1. Combining (36) with (39), we have
as k → ∞. So there exists some number k 2 > 0 such that
Since ε k = f k − ω k → 0 as k → ∞, then by (36), we have x k+1 − x k → 0 as k → ∞. We thus come to the conclusion that x k+1 − x k converges to 0 in an alternating manner as k → ∞. Therefore,
exists and by (33), we must have 0 < c < ∞. Theorem 3 is proved.
3 Maximum of (2,1) random walk
We consider firstly the escape probability of (2,1) random walk Y from certain interval. For 0 < a ≤ k ≤ b, let
The above escape probabilities can be written as functionals of product of nonnegative matrices.
Proof. The proof of the lemma is very standard and can be find in [1] . Here we sketch its proof for convenience of the readers. For j ∈ {a, a − 1}, let
which we will write as P j k for simplicity. Then by Markov property,
which leads to
with the boundary condition
Taking (42) and the fact P a k (a, b, −) + P a−1 k (a, b, −) = P k (a, b, −) into account, solving (44) with initial condition (43), we get (40).
With Lemma 6 in hands, we next prove Proposition 1. Proof of Proposition 1. Note that the event {M = n, D < ∞} occurs if and only if the following two events occur successively: i) starting from 2, the walk hits n before the set {0, 1} and then ii) restarting from n, it hits the set {0, 1} before n + 1. Thus, it follows from Markov property that P (M = n, D < ∞) = (1 − P 2 (1, n, −))P n (1, n + 1, −).
Consequently, an application of Lemma 6 finishes the proof of (3).
Our aim is to prove Theorem 1. For this purpose, since by Proposition 1, the distribution of M is written in terms of e 1 N k · · · N 2 e t 1 , k ≥ 2, which is hard to estimate directly. But by Theorem 3, it is sufficient to work with ̺(N k ) · · · ̺(N 1 ).
The proposition below yields the asymptotics of ̺(N k ) · · · ̺(N 1 ).
Fix K ≥ 1 and B ∈ R. Let r i be the one in (4) . Suppose that σ i , i ≥ 2 is a sequence of numbers such that
Then we have σ 2 · · · σ n ∼ c n log n · · · log K−2 n(log K−1 n) B ±1 (47)
and
For a rigorous proof of (47), we refer readers to [22, Lemma 2] . Here, we only sketch its proof. For some M > 0 sufficiently large, we have
∼ c n log n... log K−2 n(log K−1 n) B ±1 , as n → ∞, which leads to (47). Finally, (48) is a direct consequence of (47).
For the product N k · · · N 2 , k ≥ 2, requirements of Theorem 3 are fulfilled by the following lemma.
Here and in the rest of the paper, we use the convention that empty product equals identity. Obviously, we have
and for 0 ≤ i ≤ K − 1,
Clearly we have I 0 = 1 n(n + 1) log n × · · · × log i n = o 1 n 2 , n → ∞, and for 1 ≤ k ≤ i, by the mean value theorem,
with some θ n ∈ (n, n + 1). It is easy to see that
Thus,
Notice that Γ 0 = 1 n − 1 n+1 ∼ 1 n 2 as n → ∞. Thus we conclude that
To prove the second part, noting that
Since r n − r n+1 ∼ 1 3n 2 as n → ∞ by the first part, then we have lim k→∞ θ k+1 −θ k θ k+2 −θ k+1 = 1. The lemma is proved
To conclude Section 3, we give the proof of Theorem 1. Recall that by Proposition 1, we have P (M = n, D < ∞) = 1 1 + n−1 s=2 e 1 N s · · · N 2 e t 1 e 1 N n · · · N 2 e t 1 1 + n s=2 e 1 N s · · · N 2 e t 1 .
Consider the product of matrices N k · · · N 2 . Lemma 7 ensures that conditions (B1) and (B2) a are fulfilled. Thus, applying Theorem 3, we get that
Applying Proposition 2, we get ̺(N 2 ) · · · ̺(N n ) ∼ c n log n · · · log K−2 n(log K−1 n) B ∓1 as n → ∞. Thus e 1 N k · · · N 2 e t 1 ∼ c n log n · · · log K−2 n(log K−1 n) B ∓1 , as k → ∞. Consequently, the proof of Theorem 1 is an almost verbatim repetition of [22, Theorem 1] . We do not repeat it here.
In this section, we consider (1,2) random walk Y ′ , whose escape probabilities can be written in terms of the tails of a continued fraction. By analyzing the escape probabilities and tails of the continued fraction delicately, we can study the asymptotics of M(Y ′ ).
Let θ k , k ≥ 2 be those defined in (2) . Consider the continued fraction
whose n-th tail is denoted by
It would be convenient to write
The lemma below presents several limit behaviors related to ξ n , n ≥ 2.
Lemma 8. If p i = 1/3 ± r i , i ≥ 2, then we have
and consequently, ξ 2 · · · ξ n ∼ c n log n · · · log K−2 n(log K−1 n) B ∓1 , (52)
as n → ∞.
Proof. Since r i , i ≥ n 0 is monotone for some n 0 > 0 large enough and by Lemma 7, (r n − r n+1 ) ∼ 3r 2 n ∼ 1 3n 2 as n → ∞, then the proof of (51) goes step by step as that of [23, Lemma 1] .
By (51), the condition of Proposition 2 is satisfied. Thus, apply Proposition 2 to the sequence ξ i , i ≥ 2, we obtain (52) and (53). a, b, +) .
Clearly, we have P k (a, b, +) = P b k (a, b, +)+P b+1 k (a, b, +) . We have the following estimations of the escape probabilities.
The lemma can be proved by a space reversal argument of the proof of [17, Lemma 1 on page 230].
It is easily seen that P (M = n, D < ∞) = P n 2 (1, n, +)P n (1, n + 1, −), n ≥ 2.
From (54), we can get ξ 2 · · · ξ n 1 + n i=2 ξ 2 · · · ξ i ≤ P n (1, n + 1, −) ≤ ξ 2 · · · ξ n + ξ 2 · · · ξ n+1 1 + n+1 i=2 ξ 2 · · · ξ i ,
But it is impossible to compute or estimate P n 2 (1, n, +) directly from (54). The following lemma shows that the ratio of P n 2 (1, n, +) over P n+1
(1, n, +) has a limit.
Proof. Fix n ≥ 3. Let
Define a measureP byP (·) = P (·|E n ).
Let T n = inf{k ≥ 0 : Y ′ k ∈ [n, ∞)}, n ≥ 3. Then T n < ∞ almost surely.
Step 1. We claim that Y ′ is a Markov chain underP with transition probabilities
We first show the Markov property. Indeed, for y j ∈ [2, n + 1], 1 ≤ j ≤ T n ,
where the third equality follows from the fact that Y ′ is a Markov chain under the measure P. Therefore, Y ′ is also a Markov chain under the measureP .
Next we compute the transition probabilities. Since (58) is trivial, we need only to prove (59). It is easy to see that
which proves (59).
Step 2. We show that lim i→∞pi = 1/3. Indeed, by (54), we have 1 + i+1 j=2 ξ 2 · · · ξ i 1 + i−1 j=2 ξ 2 · · · ξ i 1 + n−1 j=2 ξ 2 · · · ξ i 1 + n j=2 ξ 2 · · · ξ i ≤ P i+2 (1, n, +) P i (1, n, +) ≤ 1 + i+1 j=2 ξ 2 · · · ξ i 1 + i−1 j=2 ξ 2 · · · ξ i 1 + n j=2 ξ 2 · · · ξ i 1 + n−1 j=2 ξ 2 · · · ξ i .
Thus, since i < n, it follows from (53) that both the leftmost-hand side and the rightmost-hand side of (60) converge to 1 as i → ∞. Therefore, lim i→∞pi = lim i→∞ p i = 1/3.
Step 3. For 2 ≤ k ≤ n, define
To this end, using Markov property, we have
Write Γ k :=q k+1 p k+1 η k (2) and β k :=q k p k . Since η 2 (2) = 1, iterating (62), we get
Since by Step 2, lim k→∞ β k = 2, applying again the convergence of limit periodic continued fractions(see [19, Theorem 4.13 , page 188]), we have that the limit lim k→∞ Γ k exists. So η := lim k→∞ η k (2) exists. Let k → ∞ in (62), we get η = 1 1 + 2η whose positive solution is η = 1/2. Thus (61) is proved.
Step 4. For 2 ≤ k ≤ n, let
Clearly, we have h k (1) + h k (2) = 1. We claim that lim k→∞ h k (2) = 1 3 . In fact, using Markov property, for k ≥ 3, we have
Iterating (63) and using that fact h 2 (2) = 0, we obtain
Since by (61), lim i→∞ η i (2) = 1/2, then for any 1/2 > ǫ > 0, there exists a number k 3 > 0 such that 1/2 − ǫ < η i < 1/2 + ǫ, ∀i ≥ k 3 . It follows from (64) that
It is easy to see that
Since ǫ is arbitrary, the second term in the righthand side of (65) converges to 1/3. Consequently, lim k→∞ h k (2) = 1/3.
Step 5. At last, let us prove lim n→∞ P n 2 (1,n,+) P n+1 2 (1,n,+) = 2. For n ≥ 3, we have
As a result, it follows from Step 4 that lim n→∞ 
Connection between e 1 N 2 · · · N n e 1 and ξ 2 · · · ξ n We can now deduce from (53), (56) and (57) that if p i = 1/3 ± r i , i ≥ 2, then P n 2 (1, n, +) ∼ 2 3
With (66) in hands, to characterize the asymptotics of P (M = n, D < ∞), we need to estimate further P n (1, n + 1, −), whose lower and upper bounds are given in (55). But the upper bound in (55) is approximately twice as much as the lower bound, so that (55) is not enough for us to get the accurate limit behavior of P n (1, n + 1, −). To deal with this difficulty, we come back to the product of nonnegative matrices. By an argument similar to Lemma 6, we have
from which, we get for n ≥ 2,
P 2 (1, n, +) = e 1 N 2 · · · N n−1 e t 1 1 + n−1 s=2 e 1 N s · · · N n−1 e t 1 = e 1 N 2 · · · N n−1 e t 1 n s=2 e 1 N s · · · N n−1 e t 1 .
(68)
Although the rightmost-hand side of (67) is written in terms of the product of nonnegative matrices N k , k ≥ 2, we can not use Theorem 3 to give an estimate because the summand in denominator involves n. Thus we turn back to the continued fraction.
Lemma 11. If p i = 1/3 ± r i , i ≥ 2, then (ξ 2 · · · ξ n ) −1 ∼ ce 1 N 2 · · · N n e t 1 , as n → ∞,
Proof. For 2 ≤ s ≤ n + 1, set y s,n := e 1 N s · · · N n e t 1 and ξ s,n := y s+1,n y s,n .
Noting that the empty product equals identity, thus y n+1,n = e 1 Ie 1 = 1. Therefore, we have ξ −1 s,n · · · ξ −1 n,n = y s,n = e 1 N s · · · N n e t 1 .
Substituting (71) into (67), we obtain P n (1, n + 1, −) = 1 n+1 s=2 ξ −1 s,n · · · ξ −1 n,n = ξ 2,n · · · ξ n,n n+1 s=2 ξ 2,n · · · ξ s−1,n .
If we can show ξ 2,n · · · ξ n,n ∼ cξ 2 · · · ξ n ,
as n → ∞, then (70) is a consequence of (72). We prove first (73). To this end, note that for 2 ≤ s ≤ n, ξ s,n = y s+1,n y s,n = e 1 N s+1 · · · N n e t 1 e 1 N s · · · N n e t 1 = e 1 N s+1 · · · N n e t 1 θ s (e 1 + e 2 )N s+1 · · · N n e t
A backward induction shows that e 2 N s+1 · · · N n e t 1 e 1 N s+1 · · · N n e t
Therefore we have
Comparing (75) with (49) and (50), by theory of convergence of limit periodic continued fractions, we have lim n→∞ ξ s,n = ξ s . By Lemma 7, the matrices N t k , k ≥ 2 satisfies Condition (B2) c . Thus, applying Theorem 3, we get e 1 N s · · · N n e t 1 = e 1 N t n · · · N t s e t 1 ∼ c̺(N 2 ) · · · ̺(N n ).
Assume now p i = 1/3 ± r i , i ≥ 2. Then by (45), (46) and (47), we have ̺(N 2 ) · · · ̺(N n ) ∼ c n log n · · · log K−2 n(log K−1 n) B ±1 , and consequently e 1 N 2 · · · N n e t 1 ∼ c n log n · · · log K−2 n(log K−1 n) B ±1 as n → ∞.
On the other hand, it follows from (51) and (52) that ξ 2 · · · ξ n ∼ c n log n · · · log K−2 n(log K−1 n) B ∓1 as n → ∞.
Therefore, we have (ξ 2 · · · ξ n ) −1 ∼ ce 1 N 2 · · · N n e t 1 , as n → ∞, which proves (69). Taking (69) and (71) together, we get (73). Next, we proceed to prove (74). For this purpose, noticing that by (68) and (71), P 2 (1, n + 1, +) = e 1 N 2 · · · N n e t 1 n+1 s=2 e 1 N s · · · N n e t 1 = ξ −1 2,n · · · ξ −1 n,n n+1 s=2 ξ −1 s,n · · · ξ −1 n,n = 1 n+1 s=2 ξ 2,n · · · ξ s−1,n which together with (56) yields that 1 1 + n+1 s=2 ξ 2 · · · ξ s ≤ 1 n+1 s=2 ξ 2,n · · · ξ s−1,n ≤ 1 1 + n s=2 ξ 2 · · · ξ s . As a consequence, 1 − ξ 2 · · · ξ n+1 1 + n+1 s=2 ξ 2 · · · ξ s ≤ n+1 s=2 ξ 2 · · · ξ s−1 n+1 s=2 ξ 2,n · · · ξ s−1,n ≤ 1.
Therefore, using (53) we get lim n→∞ n+1 s=2 ξ 2 · · · ξ s−1 n+1 s=2 ξ 2,n · · · ξ s−1,n = 1.
Then (74) is proved and so is the lemma.
We now give the proof of Theorem 2. Suppose that p i = 1/3 ± r i , i ≥ 1. Then by (66) and (70), we have P (M = n, D < ∞) = P n 2 (1, n, +)P n (1, n + 1, −) ∼ c 1 n s=2 ξ 2 · · · ξ s−1 × ξ 2 · · · ξ n n+1 s=2 ξ 2 · · · ξ s−1 , as n → ∞.
Furthermore, it follows from Lemma 8 that ξ 2 · · · ξ n ∼ c n log n · · · log K−2 n(log K−1 n) B ∓1 , as n → ∞.
With the above facts in hands, once again, the proof of Theorem 2 is just a step-by-step repetition of that of [22, Theorem 1] .
We present here the criteria of recurrence, positive recurrence and transience for both the chain Y and its adjoint chain Y ′ , since they are helpful to understand the various decay speeds in Theorem 1 and Theorem 2. Let θ k , N k , k ≥ 1 be those defined in (2) and ξ k , k ≥ 1 be the one in (50). Then as a direct consequence of Lemma 6 and Lemma 9, we get the transience criteria of both Y and Y ′ . Corollary 1. (i) The (2,1) random walk Y is transient or recurrent according as ∞ s=2 e 1 N s · · · N 2 e t 1 < ∞ or = ∞. (ii) The (1,2) random walk Y ′ is transient or recurrent according as ∞ s=2 ξ 2 · · · ξ s < ∞ or = ∞.
The following recurrence criteria of Y and its adjoint chain Y ′ can be found in [6, page 204 ]. Let r i be the one in (4). If p i = 1/3 ± r i , i ≥ 2, then by Lemma 8 and Lemma 11, we have (ξ 2 · · · ξ n ) −1 ∼ ce 1 N 2 · · · N n e t 1 ∼ c n log n · · · log K−2 n(log K−1 n) B ±1 as n → ∞.
Combining Corollary 1 and Lemma 12 with (76), we have the following result. Proof. Here, we give only the proof of part (iii), since the others can be proved similarly. Fix K ≥ 2 and let q i = 2 3 − r i , i ≥ 1. Then, by (76), ξ 2 · · · ξ n ∼ 1 e 1 N n · · · N 2 e t 1 ∼ c 1 n log n · · · log K−2 n(log K−1 n) B
as n → ∞. If B > 1, then ∞ s=2 ξ 2 · · · ξ s < ∞. Consequently, it follows from Corollary 1 that Y ′ is transient. Therefore, by Lemma 12, Y must be positive recurrent.
If B ≤ 1, then ∞ s=2 ξ 2 · · · ξ s = ∞. Thus, by Corollary 1, Y ′ is recurrent. We claim that Y ′ must be null recurrent. Indeed, if we suppose conversely Y ′ is positive recurrent, then by Lemma 12, its adjoint chain Y must be transient. So it follows from Corollary 1 that ∞ s=2 e 1 N s · · · N 2 e t 1 < ∞ which contradicts (77). Therefore we can conclude that Y ′ is null recurrent and so is its adjoint chain Y. The proof of part (iii) is finished.