Local time, upcrossing time and weak cutpoints of a spatially inhomogeneous random walk on the line

Hua-Ming WANG^†,§ and Lingyun WANG^†

²²footnotetext: School of Mathematics and Statistics, Anhui Normal University, Wuhu 241003, China ⁴⁴footnotetext: Email: [email protected]

Abstract

In this paper, we study a transient spatially inhomogeneous random walk with asymptotically zero drifts on the lattice of the positive half line. We give criteria for the finiteness of the number of points having exactly the same local time and/or upcrossing time and weak cutpoints (a point $x$ is called a weak cutpoint if the walk never returns to $x-1$ after its first upcrossing from $x$ to $x+1$ ). In addition, for the walk with some special local drifts, we also give the order of the expected number of these points in $[1,n].$ Finally, we show that, when properly scaled, the number of these points in $[1,n]$ converges in distribution to a random variable with the standard exponential distribution. Our results answer three conjectures related to the local time, the upcrossing time, and the weak cutpoints proposed by E. Csáki, A. Földes, P. Révész [J. Theoret. Probab. 23 (2) (2010) 624-638].

Keywords: Random walk; Local time; Upcrossing time; Cutpoints; Moment method

MSC 2020: 60J10, 60G50, 60J55

1 Introduction

In this paper, we study the local time, upcrossing time and weak cutpoints of a spatially inhomogeneous random walk on $\mathbb{Z}+:=\{0,1,2,...\}$ with asymptotically zero drifts. To introduce precisely the model, suppose that $p_{k},q_{k},k\geq 0$ are numbers such that $p_{0}=1,$ $q_{0}=0,$ $p_{k}>0,$ $q_{k}>0$ and $p_{k}+q_{k}=1$ for all $k\geq 1.$ Let $X=\{X_{k}\}_{k\geq 0}$ be a Markov chain on $\mathbb{Z}_{+}$ starting from $0$ with transition probabilities

	$\displaystyle\mathbb{P}(X_{k+1}=1\|X_{k}=0)=p_{0},$
	$\displaystyle\mathbb{P}(X_{k+1}=n+1\|X_{k}=n)=p_{n},$
	$\displaystyle\mathbb{P}(X_{k+1}=n-1\|X_{k}=n)=q_{n},$

for $n\geq 1$ and $k\geq 0.$ Since the transition probabilities are spatially inhomogeneous, we call the chain $X$ a spatially inhomogeneous random walk. We remark that the chain $X$ is also called a birth and death chain in the literature.

For $k\geq 1,$ let $\rho_{k}=\frac{q_{k}}{p_{k}}.$ Then we have the following criterion of recurrence or transience for the chain $X,$ which can be found, e.g., in Chung’s book [1, Part I. §12].

Proposition 1.

The chain $X$ is transient if and only if $\sum_{k=1}^{\infty}\rho_{1}\cdots\rho_{k}<\infty.$

Notice that the local drift of the walk at $n\geq 1$ is $2p_{n}-1.$ What we are concerned about are random walks with asymptotically zero drifts, that is, the case $p_{n}\rightarrow 1/2$ as $n\rightarrow\infty,$ whose limit behaviors are different in many aspects from those of simple random walks. Such random walks date back to a series of works of Lamperti. In [8, 10], Lamperti gave the criteria for recurrence or transience and the existence of the moments. Moreover, in [9], he proved an invariance principle which says that under certain conditions, $X_{[nt]}/\sqrt{n}$ converges weakly in $D[0,1]$ to a Bessel process. Such an invariance principle was further investigated and strengthened in Csáki et al. [3]. It is well known that a transient simple random walk grows linearly to infinity. But for a transient spatially inhomogeneous random walk, if the drifts are asymptotically zero, intuitively, the walk grows much slower than the simple random walk. The number of cutpoints on the path of the walk can reflect the speed of the walk. Roughly speaking, if the walk never returns to $[0,x]$ after its first entry into $[x+1,\infty),$ then $x$ is a cutpoint. By intuition, if the walk runs to infinity more quickly, there are more cutpoints. But for a spatially inhomogeneous random walk, things are very different. James et al. [6] gave an example of a transient random walk which has only finitely many cutpoints. Such a phenomenon never happens to the simple random walk since it is known that the number of cutpoints of the simple random walk is either 0 (recurrent case) or $\infty$ (transient case). Along this line, Csáki et al. [4] provided a criterion to determine the finiteness of the number of cutpoints, which we will quote below. We first give the following definition.

Definition 1.

For $x\in\mathbb{Z}_{+},$ we call $\xi(x):=\sum_{k=0}^{\infty}1_{\{X_{k}=x\}}$ the local time of the chain $X$ at $x$ and $\xi(x,\uparrow):=\sum_{k=0}^{\infty}1_{\{X_{k}=x,X_{k+1}=x+1\}}$ the upcrossing time of the chain $X$ from $x$ to $x+1,$ respectively. If $\xi(x,\uparrow)=1,$ we call $x$ a cutpoint of $X.$ If $\xi(x)=1,$ we call $x$ a strong cutpoint of $X.$

For $n\geq m\geq 0,$ write

\displaystyle D(m,n):=\left\{\begin{array}[]{ll}0,&\text{if }n=m,\\ 1,&\text{if }n=m+1,\\ 1+\sum_{j=1}^{n-m-1}\rho_{m+1}\cdots\rho_{m+j},&\text{if }n\geq m+2,\end{array}\right.

(4)

and denote

\displaystyle D(m):=\lim_{n\rightarrow\infty}D(m,n).

(5)

The theorem below gives a criterion for the finiteness of the number of cutpoints.

Theorem A(Csáki et al. [4]) Suppose $p_{i}\geq 1/2,\ i=1,2,...$ and let $D(n),\ n=1,2,...$ be as in (5). If

\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty,

then the chain $X$ has finitely many cutpoints almost surely. If $D(n)$ is increasing in $n,$ there exist $n_{0}>0$ and $\delta>0$ such that $D(n)\leq\delta n\log n$ for all $n\geq n_{0}$ and

\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}=\infty,

then $X$ has infinitely many strong cutpoints almost surely.

Remark 1.

We remark that the monotonicity condition of $D(n)$ is not contained in [4, Theorem 1.1]. But we knew from Professor A. Földes, one author of [4], that such a condition is indeed required for proving the last display on page 634 of [4].

Csáki et al. proposed in [4] four conjectures related to the weak cutpoints, local time and upcrossing time of the walk. We quote here the first three of them word for word.

Open Problems(Csáki et al. [4])

1.

It would be interesting to know whether Theorem A also holds for the number of sites with $\xi(R)=a$ or $\xi(R,\uparrow)=a$ for any fixed integer $a>1$ , i.e., whether we have the same criteria for $\{\xi(R)=a\}$ and $\{\xi(R,\uparrow)=a\}$ to occur infinitely often almost surely for any positive integer $a.$
2.

Call the site $R$ a weak cutpoint if, for some $k$ , we have $X_{k}=R,$ $X_{i}\leq R,\ i=0,1,...,k-1,$ and $X_{i}\geq R,\ i=k+1,k+2,....$ One would like to know whether Theorem A can be extended for the number of weak cutpoints.
3.

It would be interesting to know whether Theorem A holds for cutpoints with a given local time, i.e., for $\{\xi(R)=a,\xi(R,\uparrow)=1\}$ or, in general, $\{\xi(R)=a,\xi(R,\uparrow)=b\}$ infinitely often almost surely, with positive integers $a,b.$

The main task of the paper is to answer the above open problems.

Definition 2.

Let $A$ and $B$ be two subsets of $\{1,2,...\}.$ We denote by

\displaystyle C(A,B):=\{x\in\mathbb{Z}_{+}:\xi(x)\in A,\xi(x,\uparrow)\in B\}

the collection of nonnegative sites at which the local times and the upcrossing times of the walk belong to $A$ and $B,$ respectively. Moreover, consider the weak cutpoint defined in the above open problem 2. We denote by

\displaystyle C_{w}:=\{x\in\mathbb{Z}_{+}:x\text{ is a weak cutpoint}\}

the collection of all weak cutpoints.

In what follows, if $A=\{a\},$ instead of $C(\{a\},B),$ we write simply $C(a,B).$ The notations $C(A,a)$ and $C(a,b)$ can be understood similarly. Also, for simplicity, we write

\displaystyle C(*,a)=C(\{a,a+1,...\},a)\text{ and }C(a,*)=C(a,\{1,...,a\}).

(6)

Notice that $C(*,a)$ is the collection of sites at which the upcrossing times of the walk are exactly $a,$ while $C(a,*)$ is the collection of sites at which the local times of the walk are exactly $a.$ Finally, we use $|C|$ to denote the cardinality for a set $C.$

The theorem below provides criteria to tell whether $C(A,a),$ $C(a,B)$ or $C_{w}$ are finite or not, answering the above-mentioned open problems.

Theorem 1.

Let $D(n),\ n=1,2,...$ be as in (5). Suppose that $\rho_{k}$ is increasing in $k>N_{0}$ for some $N_{0}>0$ and $\rho_{k}\rightarrow 1$ as $k\rightarrow\infty.$ If

\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty,

then almost surely, we have

(i)

$|C(A,a)|<\infty$ for each $a\in\{1,2,...\}$ and $A\subseteq\{a,a+1,...\};$
(ii)

$|C(a,B)|<\infty$ for each $a\in\{1,2,...\}$ and $B\subseteq\{1,2,...,a\};$
(iii)

$|C_{w}|<\infty.$

If $D(n)\leq\delta n\log n,$ $n\geq n_{0}$ for some $n_{0}>0$ and $\delta>0$ and

\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}=\infty,

then almost surely, we have

(i)

$|C(A,a)|=\infty$ for each $a\in\{1,2,...\}$ and $\phi\neq A\subseteq\{a,a+1,...\};$
(ii)

$|C(a,B)|=\infty$ for each $a\in\{1,2,...\}$ and $\phi\neq B\subseteq\{1,2,...,a\};$
(iii)

$|C_{w}|=\infty.$

Remark 2.

We explain how Theorem 1 answers the above open problems. Noticing that $C(a,\{1,2,...,a\})=\{R\in\mathbb{Z}_{+}:\xi(R)=a\}$ and $C(\{a,a+1,...\},a)=\{R\in\mathbb{Z}_{+}:\xi(R,\uparrow)=a\},$ thus the criteria for $|C(a,\{1,2,...,a\})|<\infty$ and $|C(\{a,a+1,...\},a)|<\infty$ answer the above open problem 1. Clearly, the criterion for $|C_{w}|<\infty$ gives an answer to the above open problem 2 and the criterion for the finiteness of $C(a,b)$ provides an answer to the above open problem 3.

Fix $a\in\{1,2,...\},$ $A\subseteq\{a,a+1,...\}$ and $B\subseteq\{1,2,...,a\}.$ If $D(n)=\infty$ for some and hence all $n\geq 0,$ then it follows from Proposition 1 that the chain $X$ is recurrent. Thus, for any site $x\geq 0,$ we have $\xi(x)=\infty.$ As a consequence, we get $|C(A,a)|=|C(a,B)|=|C_{w}|=0,$ which coincides with the convergent part of Theorem 1 since in this case, we always have $\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}=0.$ The interesting phenomenon arises when $D(n)<\infty$ for all $n$ and $\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty.$ In this case, the walk is transient, but almost surely, we have $|C(A,a)|+|C(a,B)|+|C_{w}|<\infty.$

Finally, we mention that $C(*,1)$ and $C(1,1)$ are collections of the cutpoints and strong cutpoints, respectively. From this point of view, Theorem 1 is a generalization of Theorem A.

As pointed out in Csáki et al. [4], the condition “ $D(n)\leq\delta n\log n,$ $n\geq n_{0}$ for some $n_{0}>0$ and $\delta>0$ ” is a technical one. We now give a concrete example for which such a condition is satisfied naturally.

Fix $\beta\in\mathbb{R}.$ Clearly, there exists $n_{1}>0$ such that $\frac{1}{4}\left(\frac{1}{n}+\frac{1}{n(\log\log n)^{\beta}}\right)\in(0,1/2)$ for all $n>n_{1}.$ For $n\geq 1,$ set

\displaystyle r_{n}=\left\{\begin{array}[]{ll}\frac{1}{4}\left(\frac{1}{n}+\frac{1}{n(\log\log n)^{\beta}}\right),&\text{if }n\geq n_{1},\\ r_{n_{1}},&\text{if }n<n_{1},\end{array}\right.

(9)

which serves as perturbation that will be added to the transition probability of the simple recurrent random walk. We emphasize that the perturbation $r_{n}$ in (9) is taken from [4] without change.

Lemma 1.

For $n\geq 1,$ let $r_{n}$ be the one in (9) and set $p_{n}=\frac{1}{2}+r_{n}.$ Then $D(n)\sim n(\log\log n)^{\beta}\text{ as }n\rightarrow\infty.$

The proof of Lemma 1 is given in Section 7. It is easy to see from Lemma 1 that there is $n_{0}>0$ such that $D(n)<n\log n,$ $n\geq n_{0}.$ Thus, applying Theorem 1, we have the following corollary, which gives sharp criteria for the finiteness of the sets $C(A,a)$ , $C(a,B)$ and $C_{w}.$

Corollary 1.

Fix $a\in\{1,2,...\},$ $\phi\neq A\subseteq\{a,a+1,...\}$ and $\phi\neq B\subseteq\{1,2,...,a\}.$ For $n\geq 1,$ let $r_{n}$ be the one in (9) and set $p_{n}=\frac{1}{2}+r_{n}.$ If $\beta>1,$ we have $|C(A,a)|+|C(a,B)|+|C_{w}|<\infty$ almost surely. If $\beta\leq 1,$ we have $|C(A,a)|=|C(a,B)|=|C_{w}|=\infty$ almost surely.

Another interesting question is to estimate the cardinality of the set $C\cap[1,n]$ for $C=C_{w},$ $C(A,a)$ or $C(a,B)$ and $n$ large enough. We first compute the expectations of the cardinalities of these sets.

Proposition 2.

Suppose $a\geq b\geq 1$ are positive integers. For $n\geq 1,$ let $r_{n}$ be as in (9) and set $p_{n}=\frac{1}{2}+r_{n}.$ Then we have

\displaystyle\lim_{n\rightarrow\infty}\frac{(\log\log n)^{\beta}}{\log n}\mathbb{E}|C(a,b)\cap[1,n]|=\frac{1}{2^{a}}\binom{a-1}{b-1}

(10)

and

\displaystyle\lim_{n\rightarrow\infty}\frac{(\log\log n)^{\beta}}{\log n}\mathbb{E}|C_{w}\cap[1,n]|=2.

(11)

Remark 3.

Fix $a\in\{1,2,...\},$ $A\subseteq\{a,a+1,...\}$ and $B\subseteq\{1,2,...,a\}.$ By the linear property of the expectation, it follows immediately from (10) that

		$\displaystyle\lim_{n\rightarrow\infty}\frac{(\log\log n)^{\beta}}{\log n}\mathbb{E}\|C(A,a)\cap[1,n]\|=\sum_{x\in A}\frac{1}{2^{x}}\binom{x-1}{a-1},$		(12)
		$\displaystyle\lim_{n\rightarrow\infty}\frac{(\log\log n)^{\beta}}{\log n}\mathbb{E}\|C(a,B)\cap[1,n]\|=\frac{1}{2^{a}}\sum_{x\in B}\binom{a-1}{x-1}.$		(13)

Recall that $C(a,*)$ is the collection of sites at which the local times of the walk are exactly $a,$ while $C(*,a)$ is the collection of sites at which the upcrossing times of the walk are exactly $a.$ From (12) and(13), we get

	$\displaystyle\lim_{n\rightarrow\infty}\frac{(\log\log n)^{\beta}}{\log n}\mathbb{E}\|C(*,a)\cap[1,n]\|=1,$
	$\displaystyle\lim_{n\rightarrow\infty}\frac{(\log\log n)^{\beta}}{\log n}\mathbb{E}\|C(a,*)\cap[1,n]\|=1/2.$

Inspired by Proposition 2, one may expect that $\frac{(\log\log n)^{\beta}}{\log n}\left|C(a,b)\cap[1,n]\right|\rightarrow\frac{1}{2^{a}}\binom{a-1}{b-1}$ for $a\geq b\geq 1$ or $\frac{(\log\log n)^{\beta}}{\log n}\left|C_{w}\cap[1,n]\right|\rightarrow 2$ almost surely as $n\rightarrow\infty.$ However, this is not the case. The main reason is that the events $\{x\in C(a,b)\}(\text{or }x\in C_{w}),x=1,2,...,n$ are not independent. We have the following theorem.

Theorem 2.

Suppose $a\geq b\geq 1$ are positive integers. Let $r_{1}=1/4$ and $r_{n}=\frac{1}{2n}$ for $n\geq 2.$ Set $p_{n}=\frac{1}{2}+r_{n}$ for $n\geq 1.$ Then

\displaystyle\frac{\left|C(a,b)\cap[1,n]\right|}{2^{-a}\binom{a-1}{b-1}\log n}\overset{d}{\rightarrow}S,\ \frac{|C(*,a)\cap[1,n]|}{\log n}\overset{d}{\rightarrow}S\text{ and }\frac{\left|C_{w}\cap[1,n]\right|}{2\log n}\overset{d}{\rightarrow}S

as $n\rightarrow\infty,$ where (and in what follows) the notation $\overset{d}{\rightarrow}$ means the convergence in distribution and $S$ is an exponential random variable with $\mathbb{P}(S>t)=e^{-t},t>0.$

Remark 4.

Theorem 2 is proved by the standard moment method. The key step is to find the limits of the moments of $\frac{2^{a}\left|C(a,b)\cap[1,n]\right|}{\binom{a-1}{b-1}\log n},$ $\frac{\left|C(*,a)\cap[1,n]\right|}{\log n},$ or $\frac{\left|C_{w}\cap[1,n]\right|}{2\log n},$ which depend on the joint probability of $\{j_{1}\in C,...,j_{m}\in C\}$ for $C=C(a,b)$ , $C(*,a)$ or $C_{w},$ $0<j_{1}<j_{2}<...<j_{m}.$ Except for the special case $a\geq b=1,$ it is hard to give explicitly the formulae of such joint probabilities. But we can show that the events $\{j_{i}\in C\},$ $i=1,...,m$ satisfy certain Markov properties, that is, $\mathbb{P}(j_{s+1}\in C|j_{s}\in C,...,j_{1}\in C)=\mathbb{P}(j_{s+1}\in C|j_{s}\in C)$ for $1\leq s<m,$ $C=C(a,b)$ , $C(*,a)$ or $C_{w}.$ So it suffices to compute and estimate the two-dimensional joint probabilities of these events. Fix an integer $a>1.$ For general $A\subseteq\{a,a+1,...\}$ and $B\subseteq\{1,2,...,a\},$ we currently do not know how to get the limit distributions of $|C(A,a)\cap[1,n]|$ and $|C(a,B)\cap[1,n]|.$ For example, for $a>1,$ $C(a,*)\cap[1,n]$ is the collection of sites in $[1,n]$ at which the local times of the walk are exactly $a.$ But neither is $\{\xi(x)\}_{x\geq 0}$ a Markov chain nor is it possible for us to compute and estimate the joint probability of $\{\xi(j_{1})=a,...,\xi(j_{m})=a\}.$ Therefore, by our method, we can not find the limit distribution of $|C(a,*)\cap[1,n]|.$

Outline of the paper. The present paper is built up as follows. Firstly, besides introducing the exit probabilities of the walk, we prove some combinatorial results in Section 2, which play key roles in proving the main results. Then, by summarizing the proofs of Csáki et al. [4, Theorem 1.1] and James et al. [6, Theorem 3.1], we get a version of the Borel-Cantelli lemma in Section 3, which will be used to prove Theorem 1. In Section 4, we express the upcrossing times in terms of loops, moves and escapes. The probability of $\{x\in C\},$ and the joint probability and dependence of $\{x\in C\}$ and $\{y\in C\}$ for $C=C_{w},$ $C(*,a)$ or $C(a,b)$ are studied in Section 5. Section 6 is devoted to proving Theorem 1. Finally, Proposition 2 and Theorem 2 are proved in Section 7 and Section 8, respectively.

Notations: When writing $A(n)\sim B(n)$ , we mean $A(n)/B(n)\rightarrow 1$ as $n\rightarrow\infty$ . The notation $A(n)=O(B(n))$ means there is a constant $c>0$ such that $\lvert A(n)\rvert<cB(n)$ for all $n$ large enough. We also adopt the convention that an empty product equals identity and an empty sum equals $0.$ Finally, throughout the paper, $0<c<\infty$ is assumed to be a constant whose value may change from line to line.

2 Auxiliary results

In this section, we introduce first the exit probabilities of the walk from certain intervals and then give some combinatorial results that are helpful for the proofs of both Theorem 1 and Theorem 2.

2.1 Exit probabilities

For $n\geq k\geq m\geq 0$ set

	$\displaystyle P_{k}(m,n,-)$	$\displaystyle:=\mathbb{P}(X\text{ hits }m\text{ before it hits }n\|X_{0}=k),$		(14)
	$\displaystyle P_{k}(m,n,+)$	$\displaystyle:=\mathbb{P}(X\text{ hits }n\text{ before it hits }m\|X_{0}=k),$		(15)

which are the exit probabilities of the walk from $[m,n].$ Evidently, we have

P_{k}(m,n,-)+P_{k}(m,n,+)=1,\text{ for }n\geq k\geq m\geq 0.

Set also

P_{0}(-1,n,+)=\mathbb{P}(X\text{ hits }n\text{ before it hits }-1|X_{0}=0).

Since $q_{0}=0,$ we must have

\displaystyle P_{0}(-1,n,+)=1\text{ for }n\geq 0.

The following lemma is from Csáki et al. [2], see Lemma 2.2 therein, which provides formulae for the exit probabilities.

Lemma 2.

For $n\geq k\geq m\geq 0,$ we have

\displaystyle P_{k}(m,n,-)=1-\frac{D(m,k)}{D(m,n)}.

It is easily seen from Lemma 2 that for $0\leq x<y,$

\displaystyle P_{x+1}(x,y,+)=\frac{1}{D(x,y)},\ P_{x+1}(x,\infty,+)=\frac{1}{D(x)},\ P_{y-1}(x,y,+)=\frac{D(x,y-1)}{D(x,y)}.

(16)

Notice that these exit or escape probabilities are written in terms of $D(m)$ and $D(m,n)$ . By some direct computation, we see that

	$\displaystyle D(m)=1+\rho_{m+1}D(m+1),m\geq 0,$
	$\displaystyle D(m,n)=1+\rho_{m+1}D(m+1,n),n>m\geq 0,$
	$\displaystyle D(m,n)=D(m,n-1)+\rho_{m+1}\cdots\rho_{n-1},n>m\geq 0.$

Furthermore, it is shown in Csáki et al. [4] (see display (2.3) therein) that

\displaystyle\frac{D(m,n)}{D(m)}=1-\prod_{i=m}^{n-1}\left(1-\frac{1}{D(i)}\right),n>m\geq 0.

(17)

Finally, we give the following estimations.

Lemma 3.

Suppose that $\rho_{k}\rightarrow 1$ as $k\rightarrow\infty.$ Then, for each $\varepsilon>0$ there exists $N>0,$ which is independent of $x,$ such that for $x>N,\ y>x+N,$ we have

	$\displaystyle\frac{1}{D(x)}\leq\varepsilon,\ \frac{1}{D(x,y)}\leq\varepsilon,\ 1-\varepsilon\leq\frac{D(x-1)}{D(x)}\leq 1+\varepsilon,$
	$\displaystyle 1-\varepsilon\leq\frac{D(x-1,y)}{D(x,y)}\leq 1+\varepsilon,\ 1\leq\frac{D(x,y)}{D(x,y-1)}\leq 1+\varepsilon.$

Proof. Fix $0<\eta<1.$ Choose $M_{1}>0,$ which is independent of $x,$ such that $(1-\eta)^{y-x-1}<\eta$ for all $y-x\geq M_{1}.$ Since $\lim_{k\rightarrow\infty}\rho_{k}=1,$ there is a number $M_{2}>0$ such that for $k\geq M_{2},$ we have $1+\eta>\rho_{k}^{-1}\vee\rho_{k}\geq\rho_{k}^{-1}\wedge\rho_{k}>1-\eta.$ Let $N=M_{1}\vee M_{2}.$ Then, we have

	$\displaystyle D(x,y)$	$\displaystyle=1+\sum_{k=x+1}^{y-1}\rho_{x+1}\cdots\rho_{k}>1+\sum_{k=1}^{y-x-1}(1-\eta)^{k}$
		$\displaystyle=\frac{1-(1-\eta)^{y-x}}{\eta}\geq\frac{1-\eta}{\eta},\ x>N,\ y>x+N$

and

	$\displaystyle 1$	$\displaystyle\leq\frac{D(x,y)}{D(x,y-1)}=1+\frac{\rho_{x+1}\cdots\rho_{y-1}}{1+\sum_{k=x+1}^{y-2}\rho_{x+1}\cdots\rho_{k}}$
		$\displaystyle=1+\frac{1}{\sum_{k=x+1}^{y-1}\rho_{k}^{-1}\cdots\rho_{y-1}^{-1}}\leq 1+\frac{1}{\sum_{k=1}^{y-x-1}(1-\eta)^{k}}$
		$\displaystyle=1+\frac{\eta}{(1-\eta)(1-(1-\eta)^{y-x-1})}$
		$\displaystyle\leq 1+\frac{\eta}{(1-\eta)^{2}},\ x>N,\ y>x+N.$

Moreover, since $\frac{D(x-1,y)}{D(x,y)}=\rho_{x}+\frac{1}{D(x,y)},$ we have

\displaystyle 1-\eta<\frac{D(x-1,y)}{D(x,y)}<1+\eta+\frac{\eta}{1-\eta},\ x>N,\ y>x+N.

Therefore, fixing $\varepsilon>0,$ the lemma is proved by choosing $\eta$ small enough. $\Box$

2.2 Some combinatorial results

To begin with, we study the cardinality of certain simplexes. For positive integers $a\geq j\geq i\geq 1,$ set

		$\displaystyle S(a,j)=\left\{(v_{1},...,v_{j}):\ v_{k}\in\mathbb{Z}_{+}/\{0\},\ j\geq k\geq 1,\ \sum_{k=1}^{j}v_{k}=a\right\},$		(18)
		$\displaystyle\tilde{S}(a,j)=\left\{(v_{1},...,v_{j}):\ v_{k}\in\mathbb{Z}_{+},\ j\geq k\geq 1,\ v_{j}\geq 1,\ \sum_{k=1}^{j}v_{k}=a\right\},$
		$\displaystyle\tilde{S}_{i}(a,j)=\left\{(v_{1},...,v_{j})\in\tilde{S}(a,j):\ \sum_{k=1}^{j}1_{v_{k}\neq 0}=i\right\}.$

Lemma 4.

For $a\geq j\geq i\geq 1,$ we have $|S(a,j)|=\binom{a-1}{j-1}$ and $|\tilde{S}_{i}(a,j)|=\binom{j-1}{i-1}\binom{a-1}{i-1}.$

Proof. The first assertion is obvious. Indeed, arrange $a$ balls in a lineup. This lineup has $a-1$ spaces among the balls. Choose $j-1$ of those spaces and erect a wall at each of the selected places to get an arrangement of $j$ nonempty sets of balls. Obviously, this can be done by $\binom{a-1}{j-1}$ ways. Thus $|S(a,j)|=\binom{a-1}{j-1}.$

Next, we compute the cardinality of $\tilde{S}_{i}(a,j).$ Consider a vector $(v_{1},...,v_{j})\in\tilde{S}_{i}(a,j).$ There are exactly $i$ strictly positive coordinates. Since by definition, $v_{j}\geq 1,$ thus for some $k_{1},k_{2},...,k_{i-1},$ we have $v_{k_{l}}>0,l=1,...,i-1$ and $v_{k_{1}}+\cdots+v_{k_{i-1}}+v_{j}=a.$ But there are $\binom{j-1}{i-1}$ ways to choose $i-1$ coordinates from $j-1$ coordinates. Therefore, we must have

|\tilde{S}_{i}(a,j)|=\binom{j-1}{i-1}|S(a,i)|=\binom{j-1}{i-1}\binom{a-1}{i-1}.

The lemma is proved. $\Box$

The next lemma is crucial for proving Theorem 2.

Lemma 5.

Write $j_{0}=0$ and fix $k\geq 1,n_{2}\geq 1.$ We have

\displaystyle\lim_{n\rightarrow\infty}\frac{1}{(\log n)^{k}}\sum_{\begin{subarray}{c}0<j_{1}<...<j_{k}\leq n\\ j_{i}-j_{i-1}\geq n_{2},i=1,...,k\end{subarray}}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}=1.

(19)

Remark 5.

We have never seen formula (19) in the literature we are aware of, so we do not know whether it is actually new or not. If that is the case, such a formula may have an independent interest in mathematical analysis.

Proof. To start with, we prove (19) for $n_{2}=1.$ If $k=1,$ it is clear that

\lim_{n\rightarrow\infty}\frac{1}{\log n}\sum_{j_{1}=1}^{n}\frac{1}{j_{1}}=1.

Next, we fix $k\geq 2.$ Notice that

\displaystyle\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}=\prod_{i=1}^{k-1}\left(\frac{1}{j_{i}}+\frac{1}{j_{i+1}-j_{i}}\right)\frac{1}{j_{k}}.

We thus have

		$\displaystyle\sum_{0<j_{1}<...<j_{k}\leq n}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}$
		$\displaystyle\quad\quad=\sum_{j_{k}=k}^{n}\frac{1}{j_{k}}\sum_{j_{k-1}=k-1}^{j_{k}-1}\left(\frac{1}{j_{k-1}}+\frac{1}{j_{k}-j_{k-1}}\right)\cdots\sum_{j_{1}=1}^{j_{2}-1}\left(\frac{1}{j_{1}}+\frac{1}{j_{2}-j_{1}}\right).$		(20)

We claim that for $1\leq i\leq k-1,$

	$\displaystyle\sum_{j_{i}=i}^{j_{i+1}-1}$	$\displaystyle\left(\frac{1}{j_{i}}+\frac{1}{j_{i+1}-j_{i}}\right)i(i-1+\log j_{i})^{i-1}\leq(i+1)(i+\log j_{i+1})^{i},$		(21)
	$\displaystyle\sum_{j_{i}=i}^{j_{i+1}-1}$	$\displaystyle\left(\frac{1}{j_{i}}+\frac{1}{j_{i+1}-j_{i}}\right)i(\log j_{i}-\log(i-1))^{i-1}\geq(i+1)(\log j_{i+1}-\log i)^{i}.$		(22)

Indeed, (21) holds trivially for $i=1.$ For $2\leq i\leq k-1,$ since

	$\displaystyle\sum_{j_{i}=i}^{j_{i+1}-1}$	$\displaystyle\frac{i(i-1+\log j_{i})^{i-1}}{j_{i}}\leq i\int_{i-1}^{j_{i+1}-1}\frac{(i-1+\log(x+1))^{i-1}}{x}dx$
		$\displaystyle\leq i\int_{i-1}^{j_{i+1}-1}\frac{(i+\log x)^{i-1}}{x}dx\leq(i+\log j_{i+1})^{i}$

and

	$\displaystyle\sum_{j_{i}=i}^{j_{i+1}-1}$	$\displaystyle\frac{i(i-1+\log j_{i})^{i-1}}{j_{i+1}-j_{i}}=\sum_{j_{i}=1}^{j_{i+1}-i}\frac{i(i-1+\log(j_{i+1}-j_{i}))^{i-1}}{j_{i}}$
		$\displaystyle\leq\sum_{j_{i}=1}^{\left[j_{i+1}/2\right]}+\sum_{j_{i}=1+\left[j_{i+1}/2\right]}^{j_{i+1}-i}\frac{i(i-1+\log(j_{i+1}-j_{i}))^{i-1}}{j_{i}}$
		$\displaystyle\leq i(i+\log j_{i+1})^{i-1}\sum_{j_{i}=1}^{\left[j_{i+1}/2\right]}\frac{1}{j_{i}}+i(i+\log(j_{i+1}/2))^{i-1}\sum_{j_{i}=1+\left[j_{i+1}/2\right]}^{j_{i+1}-i}\frac{1}{j_{i}}$
		$\displaystyle\leq i(i+\log(j_{i+1}/2))^{i-1}(1+\log(j_{i+1}/2))+i\log 2(i+\log(j_{i+1}/2))^{i-1}$
		$\displaystyle\leq i(i+\log j_{i+1})^{i},$

then (21) is true. We now proceed to prove (22). To this end, note that

	$\displaystyle\sum_{j_{i}=i}^{j_{i+1}-1}$	$\displaystyle\frac{i(\log j_{i}-\log(i-1))^{i-1}}{j_{i}}\geq i\int_{i}^{j_{i+1}}\frac{(\log(x-1)-\log(i-1))^{i-1}}{x}dx$
		$\displaystyle\geq i\int_{i}^{j_{i+1}}\frac{(\log x-\log i)^{i-1}}{x}dx=(\log j_{i+1}-\log i)^{i}$

and

	$\displaystyle\sum_{j_{i}=i}^{j_{i+1}-1}$	$\displaystyle\frac{i(\log j_{i}-\log(i-1))^{i-1}}{j_{i+1}-j_{i}}=\sum_{j_{i}=1}^{j_{i+1}-i}\frac{i(\log(j_{i+1}-j_{i})-\log(i-1))^{i-1}}{j_{i}}$
		$\displaystyle\geq\sum_{j_{i}=1}^{\left[j_{i+1}/i\right]}\frac{i(\log(j_{i+1}-j_{i})-\log(i-1))^{i-1}}{j_{i}}$
		$\displaystyle\geq i\left(\log\frac{(i-1)j_{i+1}}{i}-\log(i-1)\right)^{i-1}\sum_{j_{i}=1}^{\left[j_{i+1}/i\right]}\frac{1}{j_{i}}$
		$\displaystyle\geq i(\log j_{i+1}-\log i)^{i-1}\log([j_{i+1}/i]+1)$
		$\displaystyle\geq i(\log j_{i+1}-\log i)^{i}.$

We thus get (22).

Using (21) and (22) time and again, from (2.2), we get

		$\displaystyle\sum_{0<j_{1}<...<j_{k}\leq n}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}$
		$\displaystyle\quad\leq\sum_{j_{k}=k}^{n}\frac{1}{j_{k}}k(k-1+\log j_{k})^{k-1}\leq\int_{k-1}^{n}\frac{k(k-1+\log(x+1))^{k-1}}{x}dx$
		$\displaystyle\quad\leq\int_{k-1}^{n}\frac{k(k+\log x)^{k-1}}{x}dx\leq(k+\log n)^{k}$		(23)

and

		$\displaystyle\sum_{0<j_{1}<...<j_{k}\leq n}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}$
		$\displaystyle\quad\geq\sum_{j_{k}=k}^{n}\frac{1}{j_{k}}k(\log j_{k}-\log(k-1))^{k-1}\geq\int_{k}^{n+1}\frac{k(\log(x-1)-\log(k-1))^{k-1}}{x}dx$
		$\displaystyle\quad\geq\int_{k}^{n}\frac{k(\log x-\log k)^{k-1}}{x}dx=(\log n-\log k)^{k}.$		(24)

Dividing (2.2) and (2.2) by $(\log n)^{k}$ and taking the upper and lower limits, we obtain

\displaystyle\lim_{n\rightarrow\infty}\frac{1}{(\log n)^{k}}\sum_{0<j_{1}<...<j_{k}\leq n}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}=1.

(25)

Applying (25), for any $l_{0}\geq 1$ and $1\leq i\leq k,$ we have

	$\displaystyle\lim_{n\rightarrow\infty}$	$\displaystyle\frac{1}{(\log n)^{k}}\sum_{\begin{subarray}{c}0<j_{1}<...<j_{k}\leq n,\\ j_{i}-j_{i-1}=l_{0}\end{subarray}}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}$
		$\displaystyle=\frac{1}{l_{0}}\lim_{n\rightarrow\infty}\frac{(\log(n-l_{0}))^{k-1}}{(\log n)^{k}}\frac{1}{(\log(n-l_{0}))^{k-1}}$
		$\displaystyle\quad\quad\quad\quad\times\sum_{0<j_{1}<...<j_{k-1}\leq n-l_{0}}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k-1}-j_{k-2})}$
		$\displaystyle=0.$

Consequently, we infer that for any $1\leq i\leq k,$

\displaystyle\lim_{n\rightarrow\infty}

\displaystyle\frac{1}{(\log n)^{k}}\sum_{\begin{subarray}{c}0<j_{1}<...<j_{k}\leq n,\\ j_{i}-j_{i-1}\leq n_{2}\end{subarray}}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{k}-j_{k-1})}=0.

(26)

Putting (25) and (26) together, we get (19). Lemma 5 is proved. $\Box$

3 A version of the Borel-Cantelli lemma

The following Theorem 3 can be seen as a version of the Borel-Cantelli lemma. Its proof is indeed a summary of Csáki et al. [4, Theorem 1.1] and James et al. [6, Theorem 3.1]. But some details are different. So we provide a complete proof here. We remark that to prove Theorem 1, we just need to check one-by-one that all conditions of Theorem 3 are fulfilled.

Theorem 3 ([4], [6]).

For $n>m\geq 0,$ let $D(m)\geq 1$ and $D(m,n)\geq 1$ be certain numbers. Assume that $(\Omega,\mathcal{F},\mathbb{P})$ is a probability space and $\Gamma_{n},n\geq 0$ are $\mathcal{F}$ -measurable events such that

\displaystyle\lim_{n\rightarrow\infty}D(n)\mathbb{P}(\Gamma_{n})=\sigma

(27)

for some $0<\sigma<\infty.$

(i) Suppose that $\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty,$

\displaystyle\mathbb{P}(\Gamma_{k+1}^{c}\cdots\Gamma_{n}^{c}|\Gamma_{i}\Gamma_{k})=\mathbb{P}(\Gamma_{k+1}^{c}\cdots\Gamma_{n}^{c}|\Gamma_{k}),\ 0\leq i\leq k<n,

(28)

and there exists a number $N_{1}>0$ such that

\displaystyle D(m,n)\leq c(n-m),\ \mathbb{P}(\Gamma_{m}|\Gamma_{n})>\frac{c}{D(m,n)},\ n>m>N_{1}.

(29)

Then we have $\mathbb{P}\left(\bigcap_{i=0}^{\infty}\bigcup_{j=i}^{\infty}\Gamma_{j}\right)=0.$

(ii) Suppose that $\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty,$ there exist $n_{0}>0$ and $\delta>0$ such that $D(n)\leq\delta n\log n,$ for all $n\geq n_{0}$ and

\displaystyle\frac{D(m,n)}{D(m)}=1-\prod_{i=m}^{n-1}\left(1-\frac{1}{D(i)}\right),\ n>m\geq 0.

(30)

In addition, assume that for each $\varepsilon>0,$ there exists $N>0$ such that $D(k),k\geq N$ is increasing in $k,$ and

\displaystyle\frac{D(m,n)}{D(m)}\frac{\mathbb{P}(\Gamma_{m}\Gamma_{n})}{\mathbb{P}(\Gamma_{m})\mathbb{P}(\Gamma_{n})}\leq 1+\varepsilon,\ m>N,\ n-m>N.

(31)

Then we have $\mathbb{P}\left(\bigcap_{i=0}^{\infty}\bigcup_{j=i}^{\infty}\Gamma_{j}\right)=1.$

Proof. We prove part (i) first. Suppose all conditions of part (i) are fulfilled. For $0\leq m<k,$ set $A_{m,k}:=\sum_{j=2^{m}+1}^{2^{k}}1_{\Gamma_{j}},$ $l_{m}=\max\left\{2^{m}+1<j\leq 2^{m+1}:\ 1_{\Gamma_{j}}=1\right\}$ and write

b_{m}:=\min_{k\in(2^{m},2^{m+1}]}\sum_{i=1}^{2^{m-1}}\frac{1}{D(k-i,k)}.

Let $N_{1}$ be as in (29). Taking (28) and (29) into consideration, for $m\geq 1+\frac{\log N_{1}}{\log 2}=:M_{1}$ (or equivalently $2^{m-1}>N_{1}$ ), $2^{m}<k\leq 2^{m+1}$ and $2^{m-1}<i<k$ we have

\displaystyle\mathbb{P}

\displaystyle(\Gamma_{i}|A_{m,m+1}>0,l_{m}=k)=\frac{\mathbb{P}\left(\Gamma_{i}\Gamma_{k}\Gamma_{k+1}^{c}\cdots\Gamma_{2^{m+1}}^{c}\right)}{\mathbb{P}\left(\Gamma_{k}\Gamma_{k+1}^{c}\cdots\Gamma_{2^{m+1}}^{c}\right)}=\mathbb{P}(\Gamma_{i}|\Gamma_{k})\geq\frac{c}{D(i,k)}.

Thus, for $m\geq M_{1},$

$\displaystyle\sum_{j=2^{m-1}+1}^{2^{m+1}}$	$\displaystyle\mathbb{P}(\Gamma_{j})=\mathbb{E}\left(A_{m-1,m+1}\right)$
	$\displaystyle\geq\sum_{k=2^{m}+1}^{2^{m+1}}\mathbb{P}(A_{m,m+1}>0,l_{m}=k)\mathbb{E}(A_{m-1,m+1}\|A_{m,m+1}>0,l_{m}=k)$
	$\displaystyle=\sum_{k=2^{m}+1}^{2^{m+1}}\mathbb{P}(A_{m,m+1}>0,l_{m}=k)\sum_{i={2^{m-1}+1}}^{k}P(\Gamma_{i}\|A_{m,m+1}>0,l_{m}=k)$
	$\displaystyle\geq c\mathbb{P}(A_{m,m+1}>0)\min_{2^{m}<k\leq 2^{m+1}}\sum_{i=1}^{2^{m-1}}\frac{1}{D(k-i,k)}$
	$\displaystyle=cb_{m}\mathbb{P}(A_{m,m+1}>0).$	(32)

Using (29), we get $b_{m}\geq c\sum_{i=1}^{2^{m-1}}\frac{1}{i}\geq cm$ for $m>M_{1}.$ Since $\mathbb{P}\left(\Gamma_{n}\right)\sim\sigma/D(n),$ as $n\rightarrow\infty,$ thus, from (32), we infer that

	$\displaystyle\sum_{m=M_{1}}^{\infty}$	$\displaystyle\mathbb{P}(A_{m,m+1}>0)\leq c\sum_{m=M_{1}}^{\infty}\frac{1}{b_{m}}\sum_{j=2^{m-1}+1}^{2^{m+1}}\mathbb{P}(j\in C)$
		$\displaystyle\leq c\sum_{m=M_{1}}^{\infty}\frac{1}{m}\sum_{j=2^{m-1}+1}^{2^{m+1}}\frac{1}{D(j)}\leq c\sum_{m=1}^{\infty}\sum_{j=2^{m-1}+1}^{2^{m+1}}\frac{1}{D(j)\log j}$
		$\displaystyle\leq c\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty.$

Applying the Borel-Cantelli lemma, we get $\mathbb{P}\left(\bigcap_{n=1}^{\infty}\bigcup_{m=n}^{\infty}\{A_{m,m+1}>0\}\right)=0.$ Thus, $\mathbb{P}\left(\bigcap_{i=0}^{\infty}\bigcup_{j=i}^{\infty}\Gamma_{j}\right)=0.$ Part (i) is proved.

Next, we prove part (ii). Suppose all conditions of part (ii) hold. For $k\geq 1,$ set $m_{k}=[k\log k].$ Since $\mathbb{P}\left(\Gamma_{n}\right)\sim\sigma/D(n),$ as $n\rightarrow\infty,$ there exists a number $M_{2}>0$ such that $\mathbb{P}(\Gamma_{m_{k}})>\sigma/2$ for $k\geq M_{2}.$ Notice that $D(n)$ is increasing in $n>N.$ It follows from Csáki et al. [4, Lemma 2.2] that $\sum_{k=M_{2}}^{\infty}\frac{1}{D([k\log k])}$ and $\sum_{k=M_{2}}^{\infty}\frac{1}{D(k)\log k}$ are equiconvergent. Therefore, we get

\displaystyle\sum_{k=M_{2}}^{\infty}\mathbb{P}(\Gamma_{m_{k}})\geq\frac{\sigma}{2}\sum_{k=M_{2}}^{\infty}\frac{1}{D([k\log k])}=\infty.

(33)

Now fix $\varepsilon>0.$ Obviously, for $l>k,$ $m_{l}-m_{k}\geq l\log l-k\log k\geq\log k.$ Then, there exists a number $M_{3}>0$ such that for all $k\geq M_{3},$ $m_{k}\geq N,m_{l}-m_{k}>N.$ Therefore, it follows from (30) and (31) that for $l>k>M_{3},$

$\displaystyle\mathbb{P}(\Gamma_{m_{k}}\Gamma_{m_{l}})$	$\displaystyle\leq(1+\varepsilon)\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})\left(\frac{D(m_{k},m_{l})}{D(m_{k})}\right)^{-1}$
	$\displaystyle=(1+\varepsilon)\left(1-\prod_{i=m_{k}}^{m_{l}-1}\left(1-\frac{1}{D(i)}\right)\right)^{-1}\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})$
	$\displaystyle\leq(1+\varepsilon)\left(1-\exp\left\{-\sum_{i=m_{k}}^{m_{l}-1}\frac{1}{D(i)}\right\}\right)^{-1}\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}}).$	(34)

Define

\displaystyle\ell_{1}=\min\left\{l\geq k:\sum_{i=m_{k}}^{m_{l}-1}\frac{1}{D(i)}\geq\log\frac{1+\varepsilon}{\varepsilon}\right\}.

Then for $l\geq\ell_{1},$ we have $\left(1-\exp\left\{-\sum_{i=m_{k}}^{m_{l}-1}\frac{1}{D(i)}\right\}\right)^{-1}\leq 1+\varepsilon.$ Therefore, it follows from (3) that

\displaystyle\mathbb{P}(\Gamma_{m_{k}}\Gamma_{m_{l}})\leq(1+\varepsilon)^{2}\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}}),\text{ for }l\geq\ell_{1}.

(35)

Next, we consider $k<l<\ell_{1}.$ Note that for $0\leq u\leq\log\frac{1+\varepsilon}{\varepsilon}$ , we have $1-e^{-u}\geq cu$ . Since $D(i),i\geq m_{k}$ is increasing in $i,$ thus, using again the fact $\mathbb{P}\left(\Gamma_{n}\right)\sim\sigma/D(n),$ as $n\rightarrow\infty,$ from (3) we deduce that

	$\displaystyle\mathbb{P}(\Gamma_{m_{k}}\Gamma_{m_{l}})$	$\displaystyle\leq(1+\varepsilon)\left(1-\exp\left\{-\sum_{i=m_{k}}^{m_{l}-1}\frac{1}{D(i)}\right\}\right)^{-1}\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})$
		$\displaystyle\leq\frac{cP(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})}{\sum_{i=m_{k}}^{m_{l}-1}\frac{1}{D(i)}}\leq\frac{cP(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})D(m_{l})}{m_{l}-m_{k}}\leq\frac{cP(\Gamma_{m_{k}})}{l\log l-k\log k}.$

Since $D(n)\leq\delta n\log n,$ for all $n\geq n_{0},$ it can be shown that $\frac{\log\ell_{1}}{\log k}\leq\gamma$ for some constant $\gamma$ depending only on $\varepsilon,$ see [4, p.635, display (4.2)]. Thus,

	$\displaystyle\sum_{l=k+1}^{\ell_{1}-1}$	$\displaystyle\mathbb{P}(\Gamma_{m_{k}}\Gamma_{m_{l}})\leq cP(\Gamma_{m_{k}})\sum_{l=k+1}^{\ell_{1}-1}\frac{1}{l\log l-k\log k}$
		$\displaystyle\leq cP(\Gamma_{m_{k}})\frac{1}{\log k}\sum_{l=k+1}^{\ell_{1}-1}\frac{1}{l-k}\leq cP(\Gamma_{m_{k}})\frac{\log\ell_{1}}{\log k}\leq cP(\Gamma_{m_{k}}).$		(36)

Taking (35) and (36) together, we have

\sum_{k=M_{3}}^{n}\sum_{l=k+1}^{n}\mathbb{P}(\Gamma_{m_{k}}\Gamma_{m_{l}})\leq\sum_{k=M_{3}}^{n}\sum_{l=k+1}^{n}(1+\varepsilon)^{2}\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})+c\sum_{k=M_{3}}^{n}\mathbb{P}(\Gamma_{m_{k}}).

Writing $H(\varepsilon)=(1+\varepsilon)^{2}$ , owing to (33) , we have

	$\displaystyle\alpha_{H(\varepsilon)}$	$\displaystyle:=\varliminf_{n\rightarrow\infty}\frac{\sum_{k=M_{3}}^{n}\sum_{l=k+1}^{n}\mathbb{P}(\Gamma_{m_{k}}\Gamma_{m_{l}})-\sum_{k=M_{3}}^{n}\sum_{l=k+1}^{n}H(\varepsilon)\mathbb{P}(\Gamma_{m_{k}})\mathbb{P}(\Gamma_{m_{l}})}{[\sum_{k=M_{3}}^{n}\mathbb{P}(\Gamma_{m_{k}})]^{2}}$
		$\displaystyle\leq\lim_{n\rightarrow\infty}\frac{c}{\sum_{k=M_{3}}^{n}\mathbb{P}(\Gamma_{m_{k}})}=0.$

An application of a generalized version of the Borel-Cantelli lemma (see Petrov [11, p. 235]) yields that $\mathbb{P}\left(\bigcap_{k=M_{3}}^{\infty}\bigcup_{j=k}^{\infty}\Gamma_{m_{j}}\right)\geq\frac{1}{H(\varepsilon)+2\alpha_{H(\varepsilon)}}\geq\frac{1}{(1+\varepsilon)^{2}}.$ As a consequence, we get $\mathbb{P}\left(\bigcap_{i=0}^{\infty}\bigcup_{j=i}^{\infty}\Gamma_{j}\right)\geq\mathbb{P}\left(\bigcap_{k=M_{3}}^{\infty}\bigcup_{j=k}^{\infty}\Gamma_{m_{j}}\right)\geq\frac{1}{(1+\varepsilon)^{2}}.$ Since $\varepsilon$ is arbitrary, letting $\varepsilon\rightarrow 0,$ we conclude that $\mathbb{P}\left(\bigcap_{i=0}^{\infty}\bigcup_{j=i}^{\infty}\Gamma_{j}\right)=1.$ Part (ii) is proved. $\Box$

4 Upcrossing times represented by loops, moves and escapes

In this section, by decomposing the path of the walk, we represent the upcrossing times $\xi(n,\uparrow),n\geq 0$ by certain loops, moves and escapes. Throughout this section, we assume $D(0)<\infty.$ As a consequence, we see from Proposition 1 that $\lim_{n\rightarrow\infty}X_{n}=\infty$ almost surely.

4.1 Loops, moves and escapes

Now, considering the random walk $X,$ we introduce the following events. For integers $0\leq x<y,$ define

	$\displaystyle FL_{x}$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x,\text{ the walk jumps upward to }x+1,\text{ and then, }\\ \text{after a number of steps, it returns to }x\text{ before going to }\infty\end{array}\right\},$
	$\displaystyle FL_{xy}$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x,\text{ the walk jumps upward to }x+1,\text{ and then, }\\ \text{after a number of steps, it returns to }x\text{ before it hits }y\end{array}\right\},$
	$\displaystyle F_{xy}$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x,\text{ the walk jumps upward to }x+1,\text{ and then, }\\ \text{after a number of steps, it hits }y\text{ before returning to }x\end{array}\right\},$
	$\displaystyle F_{x}$	$\displaystyle=\{\text{starting from }x,\text{ the walk jumps to }x+1\text{ and never returns to }x\},$

and

	$\displaystyle BL_{x}$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x,\text{ the walk jumps downward to }x-1,\\ \text{and then,}\text{ after a number of steps,}\text{ it returns to }x\end{array}\right\},$
	$\displaystyle BL_{yx}$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }y,\text{ the walk jumps downward to }y-1,\text{ and }\\ \text{then, after a number of steps, it returns to }y\text{ before hitting }x\end{array}\right\},$
	$\displaystyle B_{yx}$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }y,\text{ the walk jumps downward to }y-1,\text{ and }\\ \text{then, after a number of steps, it hits }x\text{ before returning to }y\end{array}\right\}.$

Refer to caption — Figure 1: The figure illustrates the sample paths of the loops, moves, and escapes defined in Definition 3. They all begin with a dashed arrow. Some special remarks should be added to $FL_{x}$ and $BL_{y}.$ Notice that the sample path of $FL_{x}$ in the figure has reached some site above $y.$ But by definition, for a forward loop $FL_{x},$ the walk may or may not visit the sites above $y.$ The path of $BL_{y}$ should be understood similarly.

Definition 3.

If the event $FL_{x},$ $FL_{xy},$ $F_{xy},$ or $F_{x}$ occurs, we say that a forward loop at $x,$ a forward loop at $x$ avoiding $y,$ a forward move from $x$ to $y,$ or an escape from $x$ to $\infty$ appears, respectively. Similarly, if the event $BL_{x},$ $BL_{yx},$ or $B_{yx}$ occurs, we say that a backward loop at $x,$ a backward loop at $y$ avoiding $x,$ or a backward move from $y$ to $x$ appears, respectively. When there is no danger of confusion, these notations of events are also used to represent the loop, move, or escape that they define. For example, if we say there is a forward loop $FL_{x},$ we mean that a forward loop appears at $x.$

The sample paths of these loops, moves and escapes are illustrated in Figure 1. Consulting (14), (15) and (16) time and again, we get

$\displaystyle\mathbb{P}(FL_{x})$	$\displaystyle=p_{x}P_{x+1}(x,\infty,-)=p_{x}\left(1-\frac{1}{D(x)}\right),$	(37)
$\displaystyle\mathbb{P}(FL_{xy})$	$\displaystyle=p_{x}P_{x+1}(x,y,-)=p_{x}\left(1-\frac{1}{D(x,y)}\right),$	(38)
$\displaystyle\mathbb{P}(F_{xy})$	$\displaystyle=p_{x}P_{x+1}(x,y,+)=\frac{p_{x}}{D(x,y)},$	(39)
$\displaystyle\mathbb{P}(F_{x})$	$\displaystyle=p_{x}P_{x+1}(x,\infty,+)=\frac{p_{x}}{D(x)},$	(40)

and

$\displaystyle\mathbb{P}(BL_{x})$	$\displaystyle=q_{x},$	(41)
$\displaystyle\mathbb{P}(BL_{yx})$	$\displaystyle=q_{y}P_{y-1}(x,y,+)=\frac{q_{y}D(x,y-1)}{D(x,y)},$	(42)
$\displaystyle\mathbb{P}(B_{yx})$	$\displaystyle=q_{y}P_{y-1}(x,y,-)=q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right).$	(43)

4.2 Upcrossing times and branching processes with immigration

Since the chain $X$ is transient, for each $x\in\mathbb{Z}_{+},$ there must be an escape $F_{x}$ at $x.$ For $x\geq 0,$ $k\geq 1,$ if $\xi(x,\uparrow)=k,$ then there must be $k-1$ forward loops $FL_{x}$ and one escape $F_{x}$ at $x.$

Fixing $x\geq 1$ and $k\geq 0,$ on the event $\{\xi(x-1,\uparrow)=k+1\},$ let

	$\displaystyle\eta(x,i)=$	$\displaystyle\text{ the number of forward loops }FL_{x}\text{ at }x\text{ contained}$
		$\displaystyle\text{ in the }i\text{-th forward loop }FL_{x-1}\text{ at }x-1,\text{ for }i\geq 1$		(44)

and

	$\displaystyle\zeta(x)=$	$\displaystyle\text{ the number of forward loops }FL_{x}\text{ at }x\text{ contained}$
		$\displaystyle\text{ in the escape }F_{x-1}\text{ at }x-1.$		(45)

Conditioned on the event $\{\xi(x-1,\uparrow)=k+1\},$ by strong Markov property, the paths contained in those $k$ forward loops $FL_{x-1}$ are i.i.d. and moreover, they are all independent of the path contained in the escape $F_{x-1}.$ Therefore, we conclude that

\displaystyle\xi(x,\uparrow)=\sum_{i=1}^{\xi(x-1,\uparrow)-1}\eta(x,i)+\zeta(x)+1,

(46)

where $\eta(x,i),i\geq 1$ are i.i.d. and they are all independent of $\zeta(x),$ the number $1$ represents the escape $F_{x}$ from $x$ to $\infty.$ Indeed, from the definition in (4.2) and (4.2), by the strong Markov property, $\eta(x,i),\zeta(x),x\geq 1,i\geq 1$ are mutually independent. Thus, (46) says indeed that

\displaystyle\{\xi(x,\uparrow)\}_{x=0}^{\infty}\text{ is a Markov chain (or a branching process with immigration).}

(47)

To study the weak cutpoints, we need to introduce a new chain related to the upcrossing times. Let $Y_{0}=0,$ and for $x\geq 1,$ let

	$\displaystyle Y_{x}=$	$\displaystyle\text{ number of forward loops }FL_{x}\text{ at }x\text{ contained}$
		$\displaystyle\text{ in all forward loops }FL_{x-1}\text{ at }x-1.$

Then, in view of (4.2), (4.2) and (46), we have

\displaystyle Y_{x}=\sum_{i=1}^{Y_{x-1}+\zeta(x-1)}\eta(x,i),\ x\geq 1.

(48)

Clearly, by the strong Markov property, $Y_{x-1}$ and $\zeta(x-1)$ are mutually independent. Thus, we come to the conclusion that

\displaystyle\{Y_{x}\}_{x=0}^{\infty}\text{ is a Markov chain (or a branching process with immigration).}

(49)

Now, we consider the sets $C(a,b),$ $C_{w}$ and $C(*,a)$ defined in Definition 2 and (6). Clearly,

	$\displaystyle\{x\in C(*,a)\}=\{\xi(x,\uparrow)=a\},$		(50)
	$\displaystyle\{x\in C(a,b)\}=\{\xi(x,\uparrow)=b,\ \xi(x-1,\uparrow)=a-b+1\},$		(51)
	$\displaystyle\{x\in C_{w}\}=\{Y_{x}=0\}.$		(52)

From (47) and (49) we see that both $\{\xi(x,\uparrow)\}_{x=0}^{\infty}$ and $\{Y_{x}\}_{x=0}^{\infty}$ are Markov chains. Thus, by the Markov property, we get directly the following lemma.

Lemma 6.

Suppose $D(1)<\infty.$ Then we have

\displaystyle\mathbb{P}(j\notin

\displaystyle C,k+1\leq j\leq n|i\in C,k\in C)=\mathbb{P}(j\notin C,k+1\leq j\leq n|k\in C),

for $0\leq i\leq k<n,$ $C=C(a,b),$ $C(*,a)$ or $C_{w}.$

What we really need is Lemma 6. Of course, we can say more about the Markov chain $\{\xi(x,\uparrow)\}_{x=0}^{\infty}$ and $\{Y_{x}\}_{x=0}^{\infty}.$ For $x\geq 0,$ write

	$\displaystyle f_{x}(s):=\frac{1}{P_{x}(x-1,\infty,-)}\frac{q_{x}}{1-sp_{x}P_{x+1}(x,\infty,-)},\ s\in[0,1],$		(53)
	$\displaystyle g_{x}(s):=\frac{1}{P_{x}(x-1,\infty,+)}\frac{p_{x}P_{x+1}(x,\infty,+)}{1-sp_{x}P_{x+1}(x,\infty,-)},\ s\in[0,1].$		(54)

By the Markov property, it follows that

	$\displaystyle P_{x}(x-1,\infty,-)$	$\displaystyle=p_{x}P_{x+1}(x,\infty,-)P_{x}(x-1,\infty,-)+q_{x},$
	$\displaystyle P_{x}(x-1,\infty,+)$	$\displaystyle=p_{x}P_{x+1}(x,\infty,+),$

from which we get $f_{x}(1)=g_{x}(1)=1.$ Thus, both $f_{x}(s)$ and $g_{x}(s)$ are candidates for probability generation functions. By checking carefully, we can show that $f_{x}(s)$ and $g_{x}(s)$ are indeed the probability generation functions of the random variables $\eta(x,i)$ and $\zeta(x)$ defined in (4.2) and (4.2), respectively. Consequently, from (46) and (48) we get the following proposition.

Proposition 3.

Let $\xi(-1,\uparrow)=1$ and $f_{x}(s),$ $g_{x}(s),$ $x\geq 0$ be as in (53) and (54). Then $\{\xi(x,\uparrow)\}_{x=-1}^{\infty}$ and $\{Y_{x}\}_{x=0}^{\infty}$ are branching processes with immigration such that

	$\displaystyle\mathbb{E}\left(s^{\xi(x,\uparrow)}\Big{\|}\xi(x-1,\uparrow)=k+1\right)=sg_{x}(s)\left(f_{x}(s)\right)^{k},\ k\geq 0,\ x\geq 0,$
	$\displaystyle\mathbb{E}\left(s^{Y_{x}}\big{\|}Y_{x-1}=k\right)=g_{x-1}(f_{x}(s))(f_{x}(s))^{k},\ k\geq 0,\ x\geq 1.$

Proposition 3 can be seen as a generalization of the classical Ray-Knight theorem (see Knight [7, Theorem 1.1]) on the local time of a recurrent simple random walk or the branching structure in the path of a transient simple random walk (see Dwass [5, Theorem 2]).

5 Probability, joint probability and dependence

As seen in (29) and (31), to apply Theorem 3, we need to compute the probability of $\{x\in C\}$ and characterize the dependence of $\{x\in C\}$ and $\{y\in C\}$ for $C=C(a,b),$ $C_{w}$ or $C(*,a).$ The following proposition is the main result of this section.

Proposition 4.

Suppose $\rho_{k}\rightarrow 1$ as $k\rightarrow\infty.$ Let $C=C(a,b),C(*,a)$ or $C_{w}.$ Then

\displaystyle\lim_{x\rightarrow\infty}\mathbb{P}(x\in C)D(x)=\lambda_{C}=\left\{\begin{array}[]{cl}2,&\text{if }C=C_{w},\\ \binom{a-1}{b-1}\frac{1}{2^{a}},&\text{if }C(a,b),\\ 1,&\text{if }C(*,a),\end{array}\right.

(58)

and

	$\displaystyle\mathbb{P}(y\in C\|x\in C)\leq\frac{cD(x)}{D(x,y)D(y)},\ y\geq x\geq 0,$		(59)
	$\displaystyle\mathbb{P}(x\in C\|y\in C)\geq\frac{c}{D(x,y)},\ y\geq x\geq 0,$		(60)
	$\displaystyle\mathbb{P}(j_{1}\in C,...,j_{k}\in C)\leq\frac{c}{\left(\prod_{i=1}^{k-1}D(j_{i},j_{i+1})\right)D(j_{k})},\ 0<j_{1}<...<j_{k}.$		(61)

Furthermore, there exists $N>0$ such that for all $x>N,y>x+N,$ we have

	$\displaystyle 1-\varepsilon\leq\frac{D(x,y)}{D(x)}\frac{\mathbb{P}(x\in C,y\in C)}{\mathbb{P}(x\in C)\mathbb{P}(y\in C)}\leq 1+\varepsilon,$		(62)
	$\displaystyle(\lambda_{C}-\varepsilon)\frac{D(x)}{D(x,y)D(y)}\leq\mathbb{P}(y\in C\|x\in C)\leq(\lambda_{C}+\varepsilon)\frac{D(x)}{D(x,y)D(y)},$		(63)

and for $0=j_{0}<j_{1}<...<j_{k},$ $j_{i}-j_{i-1}>N,$ $i=1,...,k$ we have

\displaystyle\frac{(\lambda_{C}-\varepsilon)^{k}}{D(j_{k})\prod_{i=1}^{k-1}D(j_{i},j_{i+1})}

\displaystyle\leq\mathbb{P}(j_{1}\in C,...,j_{k}\in C)\leq\frac{(\lambda_{C}+\varepsilon)^{k}}{D(j_{k})\prod_{i=1}^{k-1}D(j_{i},j_{i+1})}.

(64)

5.1 Weak cutpoints-Proof of Proposition 4 for $C=C_{w}$

To warm up, we consider first the weak cutpoints. The following lemma gives the probability of $\{x\in C_{w}\}$ and the joint probability of $\{x\in C_{w},y\in C_{w}\}.$

Lemma 7.

We have

		$\displaystyle\mathbb{P}(x\in C_{w})=\frac{1}{p_{x}D(x-1)},$		(65)
		$\displaystyle\mathbb{P}(x\in C_{w},y\in C_{w})=\frac{1}{p_{x}D(x-1,y)}\frac{1}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}\frac{1}{D(y-1)}.$		(66)

Proof. To begin with, we prove (65). Notice that the event $\{x\in C_{w}\}$ if and only if after hitting $x$ for the first time, the walk forms a number of (possibly $0$ ) backward loops $BL_{x}$ at $x$ one after another and then never visits $x-1.$ Thus, on accounting of (41), we get

\displaystyle\mathbb{P}(x\in C_{w})=\sum_{k=0}^{\infty}(\mathbb{P}(BL_{x}))^{k}P_{x}(x-1,\infty,+)=\sum_{k=0}^{\infty}\frac{q_{x}^{k}}{D(x-1)}=\frac{1}{p_{x}D(x-1)},

which proves (65).

Next, we show (66). Notice that the event $\{x\in C_{w},y\in C_{w}\}$ occurs if and only if the following events occur consecutively: after hitting $x$ for the first time, the walk forms a number of (possibly $0$ ) backward loops $BL_{x}$ at $x$ one after another; then, restarting from $x,$ it hits $y$ before it hits $x-1;$ restarting from $y,$ it forms a number of (possibly $0$ ) backward loops $BL_{y(x-1)}$ at $y$ avoiding $x-1$ one after another; finally, restarting from $y,$ it never hits $y-1.$

Therefore, it follows from the Markov property and (14)-(16) and (41)-(42) that

	$\displaystyle\mathbb{P}$	$\displaystyle(x\in C_{w},y\in C_{w})$
		$\displaystyle=\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}(\mathbb{P}(BL_{x}))^{k}P_{x}(x-1,y,+)\left(P(BL_{y(x-1)})\right)^{j}P_{y}(y-1,\infty,+)$
		$\displaystyle=\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}q_{x}^{k}\frac{1}{D(x-1,y)}\left(\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}\right)^{j}\frac{1}{D(y-1)}$
		$\displaystyle=\frac{1}{p_{x}D(x-1,y)}\frac{1}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}\frac{1}{D(y-1)},$

which finishes the proof of (66). $\Box$

Next, we give the proof of Proposition 4 for $C=C_{w}.$

Proof of Proposition 4 for $C=C_{w}.$ Let $C=C_{w}.$ Suppose $\rho_{k}\rightarrow 1$ as $k\rightarrow\infty.$ Then we have $p_{x}\rightarrow 1/2,$ $D(x)\rightarrow\infty$ as $x\rightarrow\infty$ and $p_{k}\vee p_{k}^{-1}<c,$ $\rho_{k}\vee\rho_{k}^{-1}\leq c,$ for all $k\geq 1.$ Thus, it follows from (65) that

\displaystyle\mathbb{P}(x\in C_{w})D(x)=\frac{D(x)}{p_{x}D(x-1)}=\frac{1}{p_{x}\left(\rho_{x}+\frac{1}{D(x)}\right)}\rightarrow 2,\text{ as }x\rightarrow\infty,

(67)

which proves (58).

Next, taking (65) and (66) together, for $y\geq x\geq 1,$ we get

$\displaystyle\mathbb{P}(y$	$\displaystyle\in C_{w}\|x\in C_{w})=\frac{D(x-1)}{D(x-1,y)D(y-1)}\frac{1}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}$
	$\displaystyle=\frac{D(x)}{D(x,y)D(y)}\frac{D(x-1)}{D(x)}\frac{D(x,y)}{D(x-1,y)}\frac{D(y)}{D(y-1)}\frac{1}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}$
	$\displaystyle=\frac{D(x)}{D(x,y)D(y)}\left(\rho_{x}+\frac{1}{D(x)}\right)\frac{1}{\rho_{x}+\frac{1}{D(x,y)}}\frac{1}{\rho_{y}+\frac{1}{D(y)}}\frac{1}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}},$	(68)

and

	$\displaystyle\mathbb{P}(x$	$\displaystyle\in C_{w}\|y\in C_{w})=\frac{1}{p_{x}D(x-1,y)}\frac{p_{y}}{1-q_{y}\frac{D(x-1,y-1)}{D(x-1,y)}}$
		$\displaystyle\geq\frac{p_{y}}{p_{x}D(x-1,y)}=\frac{p_{y}}{p_{x}D(x,y)}\frac{1}{\rho_{x}+\frac{1}{D(x,y)}}$
		$\displaystyle\geq\frac{p_{y}}{p_{x}D(x,y)}\frac{1}{1+\rho_{x}}=\frac{p_{y}}{D(x,y)}\geq\frac{c}{D(x,y)}.$

We thus get (60). Since $D(m)\geq D(m,n)\geq 1$ for $n>m\geq 0$ and $D(x-1,y)>D(x-1,y-1)$ for $y\geq x\geq 1,$ then from (68), we obtain

\displaystyle\mathbb{P}(y\in C_{w}|x\in C_{w})\leq\frac{D(x)}{D(x,y)D(y)}\frac{\rho_{x}+1}{\rho_{x}}\frac{\rho_{y}+1}{\rho_{y}}

from which we get (59). Notice that by (67) we have $\mathbb{P}(x\in C_{w})\leq\frac{c}{D(x)}.$ Thus, due to (49) and (52), (61) is a direct consequence of (59).

Now fix $\eta>0.$ By (67), there exists a number $M_{1}>0$ such that

\displaystyle(2-\eta)\frac{1}{D(x)}

\displaystyle\leq\mathbb{P}(x\in C_{w})\leq(2+\eta)\frac{1}{D(x)},\ x\geq M_{1}.

(69)

Using again (65) and (66), we get

	$\displaystyle\frac{\mathbb{P}(x\in C_{w},y\in C_{w})}{\mathbb{P}(x\in C_{w})\mathbb{P}(y\in C_{w})}=\frac{D(x-1)}{D(x-1,y)}\frac{p_{y}}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}$
	$\displaystyle=\frac{D(x)}{D(x,y)}\frac{D(x-1)}{D(x)}\frac{D(x,y)}{D(x-1,y)}\frac{p_{y}}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}.$

Applying Lemma 3, we can find a number $M_{2}>0$ such

\displaystyle 1-\eta\leq\frac{D(x-1)}{D(x)}\frac{D(x,y)}{D(x-1,y)}\frac{p_{y}}{1-\frac{q_{y}D(x-1,y-1)}{D(x-1,y)}}\leq 1+\eta,

for all $x>M_{2},\ y>x+M_{2}.$ Therefore, we get

\displaystyle 1-\eta\leq\frac{D(x,y)}{D(x)}\frac{\mathbb{P}(x\in C_{w},y\in C_{w})}{\mathbb{P}(x\in C_{w})\mathbb{P}(y\in C_{w})}\leq 1+\eta,\ x>M_{2},\ y>x+M_{2}.

(70)

Taking (69) and (70) together, we infer that

\displaystyle\frac{(2-\eta)(1-\eta)D(x)}{D(x,y)D(y)}\leq\mathbb{P}(y\in C|x\in C)\leq\frac{(2+\eta)(1+\eta)D(x)}{D(x,y)D(y)},

(71)

for $x>M_{1}\vee M_{2},\ y>x+M_{1}\vee M_{2}.$ Choosing $\eta$ small enough such that $(2+\eta)(1+\eta)<2+\varepsilon$ and $(2-\eta)(1-\eta)>2-\varepsilon$ and letting $N=M_{1}\vee M_{2},$ from (70) and (71), we get (62) and (63), respectively. Finally, putting (69) and (71) together, we get (64). Proposition 4 is proved for $C=C_{w}.$ $\Box$

5.2 Local times and upcrossing times-Proof of Proposition 4 for $C=C(a,b)$ or $C(*,a)$

Compared with the case $C=C_{w},$ it is much more involved to prove Proposition 4 for $C=C(a,b)$ or $C(*,a).$ The main difficulty is to compute the joint probability of $\{x\in C,y\in C\}$ for $C=C(a,b)$ or $C(*,a).$

5.2.1 Probabilities and joint probabilities

To begin with, we compute the probabilities of $\{x\in C(a,b)\}$ and $\{x\in C(*,b)\}.$

Lemma 8.

For $x\geq 1$ and $a\geq b\geq 1,$ we have

		$\displaystyle\mathbb{P}(\xi(x)=a,\xi(x,\uparrow)=b)=\binom{a-1}{b-1}\frac{p_{x}^{b}q_{x}^{a-b}}{D(x)}\left(1-\frac{1}{D(x)}\right)^{b-1},$		(72)
		$\displaystyle\mathbb{P}(\xi(x,\uparrow)=b)=\frac{1}{D(x)}\left(1-\frac{1}{D(x)}\right)^{b-1}.$		(73)

Proof. For $x\geq 1$ and $a\geq b\geq 1,$ $\{\xi(x)=a,\xi(x,\uparrow)=b\}$ if and only if the following events occur consecutively: starting from $0,$ the walk hits $x$ for the first time (with probability 1); restarting from $x,$ the walk forms $a-b$ backward loops $BL_{x}$ at $x,$ and $b-1$ forward loops $FL_{x}$ at $x;$ finally, the walk forms an escape $F_{x}$ from $x$ to $\infty.$

We next determine the possible orders of those $a-b$ backward loops $BL_{x},$ $b-1$ forward loops $FL_{x}$ and one escape $F_{x}.$ To this end, notice that there are $a$ jumps of the walk from $x$ to $x+1$ or $x-1.$ We know exactly that when standing at $x$ for the last time, the walk must take a jump from $x$ to $x+1,$ which forms the beginning of the escape $F_{x}$ at $x.$ But there are $\binom{a-1}{b-1}$ possible ways to choose $b-1$ jumps from the other $a-1$ jumps to jump from $x$ to $x+1,$ which are the beginnings of those $b-1$ forward loops $FL_{x}.$

To sum up the above discussion, owing to (37), (40) and (41), we get

	$\displaystyle\mathbb{P}(\xi$	$\displaystyle(x)=a,\xi(x,\uparrow)=b)=\binom{a-1}{b-1}(\mathbb{P}(BL_{x}))^{a-b}(\mathbb{P}(FL_{x}))^{b-1}\mathbb{P}(F_{x})$
		$\displaystyle=\binom{a-1}{b-1}q_{x}^{a-b}\left(p_{x}P_{x+1}(x,\infty,-)\right)^{b-1}p_{x}P_{x+1}(x,\infty,+)$
		$\displaystyle=\binom{a-1}{b-1}\frac{p_{x}^{b}q_{x}^{a-b}}{D(x)}\left(1-\frac{1}{D(x)}\right)^{b-1}.$

Finally, taking summation on both sides of (72) over $a$ from $b$ to $\infty,$ we obtain (73). The lemma is proved. $\Box$

The lemma below gives the joint probability of $\{x\in C(a,b),y\in C(n,m)\},$ or $\{x\in C(*,b),y\in C(*,m)\}.$

Lemma 9.

For integers $1\leq b\leq a,$ $1\leq m\leq n$ and $1\leq x<y,$ we have

$\displaystyle\mathbb{P}$	$\displaystyle(\xi(x)=a,\xi(x,\uparrow)=b,\xi(y)=n,\xi(y,\uparrow)=m)$
	$\displaystyle=\binom{a-1}{b-1}\sum_{i=1}^{b\wedge(n-m+1)}\binom{b-1}{i-1}\binom{n-i}{m-1}\binom{n-1}{i-1}q_{x}^{a-b}\frac{p_{y}}{D(y)}$
	$\displaystyle\times\left(p_{x}\left(1-\frac{1}{D(x,y)}\right)\right)^{b-i}\left(\frac{p_{x}}{D(x,y)}\right)^{i}\left(p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{m-1}$
	$\displaystyle\times\left(q_{y}\left(\frac{D(x,y-1)}{D(x,y)}\right)\right)^{n-m-(i-1)}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{i-1}$	(74)

and

$\displaystyle\mathbb{P}$	$\displaystyle(\xi(x,\uparrow)=b,\xi(y,\uparrow)=m)$
	$\displaystyle=\sum_{i=1}^{b}\binom{b-1}{i-1}\binom{m+i-2}{i-1}\left(\left(1-\frac{1}{D(x,y)}\right)\right)^{b-i}\left(\frac{1}{D(x,y)}\right)^{i}$
	$\displaystyle\times\left(\frac{p_{y}\left(1-\frac{1}{D(y)}\right)}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}\right)^{m-1}\left(\frac{q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}\right)^{i-1}\frac{\frac{p_{y}}{D(y)}}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}.$	(75)

Remark 6.

Setting $n=a$ and taking summation on both sides of (9) over $b$ and $m$ from $1$ to $a,$ by some tedious manipulation, we get

	$\displaystyle\mathbb{P}(\xi$	$\displaystyle(x)=a,\xi(y)=a)$
		$\displaystyle=\sum_{i=1}^{a}\binom{a-1}{i-1}^{2}\left(\frac{p_{x}}{D(x,y)}\right)^{i}\left(1-\frac{p_{x}}{D(x,y)}\right)^{a-i}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{i-1}$
		$\displaystyle\quad\quad\times\left(q_{y}\frac{D(x,y-1)}{D(x,y)}+p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{a-i}\frac{p_{y}}{D(y)}.$

But we do not need such a formula because $C(a,*)$ is finite if and only if $C(a,b)$ is finite for all $b\in\{1,...,a\},$ while $C(a,*)$ is infinite if and only if $C(a,b)$ is infinite for some $b\in\{1,...,a\}.$

The formula in (75) looks heavy. If we take summation on both sides of (75) over $m$ from $1$ to $\infty,$ then by some careful computation, we get $\mathbb{P}(\xi(x,\uparrow)=b)=\left(1-\frac{1}{D(x)}\right)^{b-1}\frac{1}{D(x)},b\geq 1,$ which coincides with (73).

We give two proofs of Lemma 9 from different scopes, i.e., the combinatorial one and the path decomposition one.

Proof of Lemma 9(Combinatorial scope). For simplicity, write

\displaystyle\mathcal{A}=\{\xi(x)=a,\xi(x,\uparrow)=b,\xi(y)=n,\xi(y,\uparrow)=m\}.

Let $FL_{xy},$ $F_{xy},$ $FL_{y},$ $F_{y}$ and $BL_{x},$ $BL_{yx},$ $B_{yx}$ be the loops, moves and escapes defined in Definition 3 whose probabilities are given in (37)-(43).

Notice that the event $\mathcal{A}$ occurs if and only if for some $i,$ there are $a-b$ backward loops $BL_{x}$ at $x,$ $b-i$ forward loops $FL_{xy}$ at $x$ avoiding $y,$ $i$ forward moves $F_{xy}$ from $x$ to $y$ , $m-1$ forward loops $FL_{y}$ at $y,$ $n-m-(i-1)$ backward loops $BL_{yx}$ at $y$ avoiding $x,$ $i-1$ backward moves $B_{yx}$ from $y$ to $x,$ and finally an escape $F_{y}$ from $y$ to $\infty.$ See Figure 3 for the case $a=9,$ $n=8,$ $b=5,$ $m=4$ and $i=3.$

Clearly,

\displaystyle 1\leq i\leq(n-m+1)\wedge b.

(76)

If the order of those events is determined, in view of (37)-(43), by the Marov property, the probability of these events occurring one by one is

		$\displaystyle q_{x}^{a-b}\left(p_{x}\left(1-\frac{1}{D(x,y)}\right)\right)^{b-i}\left(\frac{p_{x}}{D(x,y)}\right)^{i}\left(p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{m-1}$
		$\displaystyle\times\left(q_{y}\left(\frac{D(x,y-1)}{D(x,y)}\right)\right)^{n-(m-1)-i}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{i-1}\frac{p_{y}}{D(y)}$		(77)

which does not depend on the order of these events.

Next, fix such a number $i.$ We claim that

\begin{split}&\text{the possible number of the orders of these moves, loops,}\\ &\text{and the escape is}\binom{a-1}{b-1}\binom{b-1}{i-1}\binom{n-1}{i-1}\binom{n-i}{m-1}.\end{split}

(78)

Putting (76), (5.2.1) and (78) together, we get (9).

What is left for us to do is to prove (78). Indeed, fix $1\leq i\leq b\wedge(n-m+1).$ On one hand, since the local time at $x$ is $a,$ the walk should visit $x$ for $a$ times, or in other words, it must jump away from $x$ to $x+1$ or $x-1$ for $a$ times. On the other hand, since the upcrossing time at $x$ is $b,$ the walk should jump from $x$ to $x+1$ for $b$ times and jump from $x$ to $x-1$ for $a-b$ times. Those jumps from $x$ to $x-1$ form the beginnings of those $a-b$ backward loops $BL_{x},$ while those $b$ jumps from $x$ to $x+1$ form the beginnings of those $i$ forward moves $F_{xy}$ and $b-i$ forward loops $FL_{xy}.$ But we know exactly that when standing at $x$ for the last time, it jumps from $x$ to $x+1$ and never returns to $x.$ Except for such a jump, we do not know exactly which $a-b$ jumps of the other $a-1$ jumps are from $x$ to $x-1.$ There are $\binom{a-1}{b-1}$ ways to choose $a-b$ jumps from those $a-1$ jumps to jump from $x$ to $x-1$ and form the beginnings of those $a-b$ backward loops $BL_{x}.$

Up to now, we already know which $b$ jumps (out of $a$ jumps) of the walk are from $x$ to $x+1.$ They form the beginnings of those $b-i$ forward loops $FL_{xy}$ and $i$ forward moves $F_{xy}.$ As mentioned above, the last jump of those $b$ jumps is from $x$ to $x+1,$ which forms the beginning of an upward move $F_{xy}.$ There are $\binom{b-1}{i-1}$ ways to choose $b-i$ jumps from the left $b-1$ jumps to form the beginning of those $b-i$ forward loops $FL_{xy}$ and the other $i-1$ jumps to form the beginnings of the other $i-1$ forward moves $F_{xy}.$

We now know there are $b$ jumps that the walk takes from $x$ to $x+1$ and already know which $b-i$ jumps of them form the beginnings of the forward loops $FL_{xy}$ (which end with a jump from $x+1$ to $x$ ) and which $i$ jumps of them form the beginnings of the forward moves $F_{xy}.$ But since the upcrossing time at $x$ is $b,$ except for the last time, every time the walk jumps forward from $x$ to $x+1,$ after a number of steps, it must return to $x.$ Thus, except for the last forward move $F_{xy}$ from $x$ to $y,$ the other $i-1$ forward moves $F_{xy}$ from $x$ to $y$ must be followed by a number (possibly $0$ ) of forward loops $FL_{y}$ and/or a number(possibly $0$ ) of backward loops $BL_{yx},$ and then, with probability $1$ a backward move $F_{yx}$ from $y$ to $x.$ The walk jumps from $y$ to $y+1$ or $y-1$ for $n$ times. We also know that when the last time the walk standing at $y,$ it jumps from $y$ to $y+1$ and never returns to $y.$ There are $\binom{n-1}{i-1}$ possible ways to choose $i-1$ jumps from the other $n-1$ jumps to form the beginning of those backward moves $B_{yx}$ from $y$ to $x.$

Until now, we have fixed $i-1$ jumps from $y$ to $y-1,$ which are the beginnings of those $i-1$ backward moves $F_{yx}$ from $y$ to $x$ and one jump from $y$ to $y+1,$ which is the beginning of the escape $F_{y}$ from $y$ to $\infty.$ But the walk will leave $y$ for $n$ times. Therefore, except for the above already fixed $i$ jumps, the other $n-i$ jumps that the walk jumps away from $y$ should be the beginnings of those $m-1$ forward loops $FL_{y}$ and $n-i-(m-1)$ backward loops at $y.$ There are $\binom{n-i}{m-1}$ ways to choose $m-1$ jumps from those $n-i$ jumps to serve as the beginnings of those forward loops $FL_{y}$ at $y.$ So far, we have already determined the order of that escape and those loops and moves.

Summing up the above discussion, we get (78). Thus, (9) is proved.

Finally, taking summation on both sides of (9) over $a$ and $n$ from $b$ to $\infty$ and $m$ to $\infty,$ respectively, and using the formula $\sum_{j=0}^{\infty}\binom{k+j}{j}t^{j}=\frac{1}{(1-t)^{k+1}},$ by some tedious but elementary computation, we get (75). The lemma is proved. $\Box$

Remark 7.

The above combinatorial proof of Lemma 9 related to loops, moves and escapes is relatively short and easy to understand. The idea of such a proof comes from an anonymous referee of an early unpublished version of our manuscript [13], which contains only criterion for the finiteness of $C(a,*),$ and the limit distribution of $C(1,1).$ But we worry that some of the readers may doubt the rigorousness of such a combinatorial proof. So we also provide a path decomposition proof here, which is much longer.

Proof of Lemma 9(Path decomposition scope). In this proof, for a $j$ -dimensional vector $\vec{\mathbf{v}},$ we stipulate that its $k$ th coordinate is $v_{k},$ $1\leq k\leq j.$ For two $j$ -dimensional vectors $\vec{\mathbf{w}}$ and $\vec{\mathbf{u}}$ we write $\vec{\mathbf{w}}\prec\vec{\mathbf{u}}$ if $w_{j}<u_{j}$ and $w_{k}\leq u_{k},$ $1\leq k\leq j-1.$

We show only (9), since (75) can be derived from (9). Denote again $\mathcal{A}=\{\xi(x)=a,\xi(x,\uparrow)=b,\xi(y)=n,\xi(y,\uparrow)=m\}.$ Let $\tau_{0}=0,$ and for $k\geq 1,$ let

\tau_{k}=\inf\{n>\tau_{k-1}:X_{n-1}=x,X_{n}=x+1\}.

Then we have

0=\tau_{0}\leq\tau_{1}\leq\tau_{2}\leq...\leq\tau_{b}\leq\tau_{b+1}\leq\infty,

where for $k\geq 1,$ $\tau_{k}<\tau_{k+1}$ if $\tau_{k+1}<\infty.$ Notice that on $\mathcal{A},$ $\tau_{b}<\tau_{b+1}=\infty.$ For $1\leq k\leq b,$ let

	$\displaystyle V_{k}$	$\displaystyle=\#\{\tau_{k-1}\leq n<\tau_{k}:X_{n}=x\},$		(79)
	$\displaystyle U_{k}$	$\displaystyle=\#\{\tau_{k}\leq n<\tau_{k+1}:X_{n}=y\}.$		(80)

Furthermore, let

\displaystyle W_{b}+1=\#\{\tau_{b}\leq n<\tau_{b+1}:X_{n-1}=y,X_{n}=y+1\}

(81)

and for $1\leq k\leq b-1,$ set

\displaystyle W_{k}=\#\{\tau_{k}\leq n<\tau_{k+1}:X_{n-1}=y,X_{n}=y+1\}.

(82)

Clearly, $\mathcal{A}$ occurs if and only if

	$\displaystyle V_{k}\geq 1,\ k=1,...,b,\ V_{1}+...+V_{b}=a,$
	$\displaystyle U_{b}\geq 1,\ U_{k}\geq 0,\ k=1,...,b-1,\ U_{1}+...+U_{b}=n,$
	$\displaystyle 0\leq W_{b}<U_{b},\ 0\leq W_{k}\leq U_{k},\ k=0,...,b-1,\ W_{1}+...+W_{b}=m-1,$

or equivalently,

\vec{\mathbf{V}}\in S(a,b),\ \vec{\mathbf{U}}\in\tilde{S}(n,b),\ \vec{\mathbf{W}}\in S(m-1,b)\text{ and }\vec{\mathbf{W}}\prec\vec{\mathbf{U}}.

Now fix $\vec{\mathbf{v}}\in S(a,b),$ $\vec{\mathbf{u}}\in\tilde{S}(n,b)$ and $\vec{\mathbf{w}}\in S(m-1,b).$ Denote

\displaystyle\mathcal{A}(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}})=\{\vec{\mathbf{V}}=\vec{\mathbf{v}},\vec{\mathbf{U}}=\vec{\mathbf{u}},\vec{\mathbf{W}}=\vec{\mathbf{w}},\vec{\mathbf{w}}\prec\vec{\mathbf{u}}\}.

(83)

In order to compute the probability of the event $\mathcal{A}(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}}),$ for $v,u,w\geq 0,$ we define

	$\displaystyle\mathcal{B}(x,v)$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x,\text{ before it hits }x+1,\text{ the }\\ \text{walk visits }x\ v\text{ times and then hits }x+1\end{array}\right\};$
	$\displaystyle\mathcal{C}(x,y,u,w)$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x+1,\text{ before it hits }x,\text{ the walk }\\ \text{visits }y\ u\text{ times, jumps from }y\text{ to }y+1\ w\text{ times}\\ \text{and then, after a number of steps, it hits }x\end{array}\right\};$
	$\displaystyle\tilde{\mathcal{C}}(x,y,u,w)$	$\displaystyle=\left\{\begin{array}[]{l}\text{starting from }x+1,\text{ the walk never returns back}\text{ to }x\\ \text{and visits }y\ u\text{ times, jumps from }y\text{ to }y+1\ w\text{ times}\end{array}\right\}.$

It is easily seen that

\displaystyle\mathbb{P}(\mathcal{B}(x,v))=q_{x}^{v-1}p_{x},\ v\geq 1.

(84)

Furthermore, we claim that

\displaystyle\mathbb{P}(\mathcal{C}(x,y,0,0))

\displaystyle=P_{x+1}(x,y,-)

(85)

and

	$\displaystyle\mathbb{P}(\mathcal{C}(x,y,u,w))$	$\displaystyle=\binom{u-1}{w}P_{x+1}(x,y,+)(q_{y}P_{y-1}(x,y,+))^{u-w-1}$
		$\displaystyle\times(p_{y}P_{y+1}(y,\infty,-))^{w}q_{y}P_{y-1}(x,y,-)\text{ for }0\leq w<u.$		(86)

Indeed, the event $\mathcal{C}(x,y,0,0)$ occurs if and only if starting from $x+1,$ the walk hits $x$ before it hits $y,$ which occurs with probability $P_{x+1}(x,y,-).$ Thus, we get (85). Next, fixing $u>w\geq 0,$ we show (5.2.1). Notice that the event $\mathcal{C}(x,y,u,w)$ occurs if and only if the following events occur:

(i) starting from $x+1,$ the walk hits $y$ before it hits $x;$

(ii) restarting from $y,$ before it hits $x,$ it has $u$ jumps away from $y,$ of which the last one is from $y$ to $y-1$ , and $w$ jumps are from $y$ to $y+1,$ and the other $u-w-1$ jumps are from $y$ to $y-1$ .

Clearly, the probability of the first event equals $P_{x+1}(x,y,+)$ ). To see the probability of the second event, notice that standing at $y$ for the last time, the walk jumps to $y-1,$ and restarting from $y-1,$ it hits $x$ before it hits $y,$ with probability $q_{y}P_{y-1}(x,y,-).$ Next, we see what happens after the other $u-1$ times that the walk stands at $y.$ For $w$ times, it moves from $y$ to $y+1$ and returns back to $y,$ with probability $p_{y}P_{y+1}(y,\infty,-).$ And for $u-w-1$ times, it moves from $y$ to $y-1,$ and restarting from $y-1,$ it returns back to $y$ before it hits $x,$ with probability $q_{y}P_{y-1}(x,y,+).$ But there are $\binom{u-1}{w}$ possible ways to choose $w$ jumps from those $u-1$ jumps to move forward from $y$ to $y+1.$ Consequently, the probability of the second event equals

\displaystyle\binom{u-1}{w}(q_{y}P_{y-1}(x,y,+))^{u-w-1}(p_{y}P_{y+1}(y,\infty,-))^{w}q_{y}P_{y-1}(x,y,-).

Therefore, (5.2.1) is true.

Putting (85) and (5.2.1) together, we get

$\displaystyle\mathbb{P}(\mathcal{C}(x,y,u,w))$	$\displaystyle=1_{\{u=w=0\}}P_{x+1}(x,y,-)$
	$\displaystyle\quad\quad+1_{\{0\leq w<u\}}\binom{u-1}{w}P_{x+1}(x,y,+)(q_{y}P_{y-1}(x,y,+))^{u-w-1}$
	$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\times(p_{y}P_{y+1}(y,\infty,-))^{w}q_{y}P_{y-1}(x,y,-)$	(87)

Notice that if $\tilde{\mathcal{C}}(x,y,u,w)$ occur, when standing at $y$ for the last time, the walk moves forward from $y$ to $y+1$ and never returns back to $y,$ with probability $p_{y}P_{y+1}(y,\infty,+).$ Thus similar to (5.2.1), we obtain

	$\displaystyle\mathbb{P}(\tilde{\mathcal{C}}(x,y,u,w))=$	$\displaystyle\binom{u-1}{w}P_{x+1}(x,y,+)(q_{y}P_{y-1}(x,y,+))^{u-w-1}$
		$\displaystyle\times(p_{y}P_{y+1}(y,\infty,-))^{w}p_{y}P_{y+1}(y,\infty,+)\text{ for }0\leq w<u.$		(88)

We are now ready to compute the probability of the event $\mathcal{A}(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}})$ defined in (83). Notice that $\vec{\mathbf{w}}\prec\vec{\mathbf{u}}.$ Thus, if $u_{i}=0,$ then $w_{i}=0,$ for $1\leq i\leq b-1.$

In view of (79)-(82), $\mathcal{A}(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}})$ occurs if and only if the event

\bigcap_{k=1}^{b-1}\mathcal{B}(x,v_{k})\mathcal{C}(x,y,u_{k},w_{k})\mathcal{B}(x,v_{b})\tilde{\mathcal{C}}(x,y,u_{b},w_{b})

occurs. Thus, by the Markov property, on accounting of (84), (5.2.1) and (5.2.1), we have

	$\displaystyle\mathbb{P}(\mathcal{A}$	$\displaystyle(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}}))=\mathbb{P}\left(\bigcap_{k=1}^{b-1}\mathcal{B}(x,v_{k})\mathcal{C}(x,y,u_{k},w_{k})\mathcal{B}(x,v_{b})\tilde{\mathcal{C}}(x,y,u_{b},w_{b})\right)$
		$\displaystyle=\left(\prod_{k=1}^{b-1}P(\mathcal{B}(x,v_{k}))\mathbb{P}(C(x,y,u_{k},w_{k}))\right)P(\mathcal{B}(x,v_{b}))\mathbb{P}(\tilde{\mathcal{C}}(x,y,u_{b},w_{b}))$
		$\displaystyle=\bigg{(}\prod_{k=1}^{b-1}q_{x}^{v_{k}-1}p_{x}\bigg{(}1_{\{u_{k}=0\}}P_{x+1}(x,y,-)$
		$\displaystyle\quad\quad\quad\quad\quad\quad+1_{\{u_{k}\neq 0\}}\binom{u_{k}-1}{w_{k}}P_{x+1}(x,y,+)(p_{y}P_{y+1}(y,\infty,-))^{w_{k}}$
		$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\times(q_{y}P_{y-1}(x,y,+))^{u_{k}-w_{k}-1}q_{y}p_{y-1}(x,y,-)\bigg{)}\bigg{)}$
		$\displaystyle\quad\quad\times\bigg{(}q_{x}^{v_{b}-1}p_{x}\binom{u_{b}-1}{w_{b}}P_{x+1}(x,y,+)$
		$\displaystyle\quad\quad\times(p_{y}P_{y+1}(y,\infty,-))^{w_{b}}(q_{y}P_{y-1}(x,y,+))^{u_{b}-w_{b}-1}p_{y}p_{y+1}(y,\infty,+)\bigg{)}$
		$\displaystyle=q_{x}^{a-b}p_{x}^{b}\left(\prod_{k=1}^{b}\binom{u_{k}-1}{w_{k}}\right)(P_{x+1}(x,y,-))^{\sum_{k=1}^{b-1}1_{u_{k}=0}}$
		$\displaystyle\quad\quad\times(P_{x+1}(x,y,+))^{\sum_{k=1}^{b}1_{u_{k}\neq 0}}\left(p_{y}P_{y+1}(y,\infty,-)\right)^{\sum_{k=1}^{b-1}w_{k}1_{u_{k}\neq 0}}$
		$\displaystyle\quad\quad\times\left(q_{y}P_{y-1}(x,y,+)\right)^{\sum_{k=1}^{b-1}(u_{k}-w_{k}-1)1_{u_{k}\neq 0}}(q_{y}P_{y-1}(x,y,-))^{\sum_{k=1}^{b-1}1_{u_{k}\neq 0}}$
		$\displaystyle\quad\quad\times(p_{y}P_{y+1}(y,\infty,-))^{w_{b}}(q_{y}P_{y-1}(x,y,+))^{u_{b}-w_{b}-1}p_{y}p_{y+1}(y,\infty,+),$

where and in what follows, we use the convention that $\binom{u_{k}-1}{w_{k}}=1$ if $w_{k}\geq u_{k}-1,$ $k=1,...,b.$

Since $\vec{\mathbf{v}}\in S(a,b),$ $\vec{\mathbf{u}}\in\tilde{S}(n,b),$ $\vec{\mathbf{w}}\in S(m-1,b),$ and $w_{k}\leq u_{k}$ for all $1\leq k\leq b,$ thus, we have $u_{b}\geq 1,$ $w_{b}+\sum_{k=1}^{b-1}w_{k}1_{u_{k}\neq 0}=\sum_{k=1}^{b}w_{b}=m-1$ and $u_{b}+\sum_{k=1}^{b-1}u_{b}1_{u_{b}\neq 0}=n.$ Therefore, we get

	$\displaystyle\mathbb{P}(\mathcal{A}$	$\displaystyle(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}}))$
		$\displaystyle=q_{x}^{a-b}p_{x}^{b}\left(\prod_{k=1}^{b}\binom{u_{k}-1}{w_{k}}\right)(P_{x+1}(x,y,-))^{\sum_{k=1}^{b}1_{u_{k}=0}}$
		$\displaystyle\quad\quad\times(P_{x+1}(x,y,+))^{\sum_{k=1}^{b}1_{u_{k}\neq 0}}\left(p_{y}P_{y+1}(y,\infty,-)\right)^{m-1}$
		$\displaystyle\quad\quad\times\left(q_{y}P_{y-1}(x,y,+)\right)^{n-(m-1)-\sum_{k=1}^{b}1_{u_{k}\neq 0}}(q_{y}P_{y-1}(x,y,-))^{\sum_{k=1}^{b}1_{u_{k}\neq 0}-1}$
		$\displaystyle\quad\quad\times p_{y}p_{y+1}(y,\infty,+).$

Consequently, taking (16) and Lemma 4 into account, we conclude that

	$\displaystyle\mathbb{P}(\xi$	$\displaystyle(x)=a,\xi(x,\uparrow)=b,\xi(y)=n,\xi(y,\uparrow)=m)$
		$\displaystyle=\sum_{\vec{\mathbf{v}}\in S(a,b),\vec{\mathbf{u}}\in\tilde{S}(n,b),\vec{\mathbf{w}}\in S(m-1,b),\vec{\mathbf{w}}\prec\vec{\mathbf{u}}}\mathbb{P}(\mathcal{A}(\vec{\mathbf{v}},\vec{\mathbf{u}},\vec{\mathbf{w}}))$
		$\displaystyle=\sum_{\vec{\mathbf{v}}\in S(a,b),\vec{\mathbf{u}}\in\tilde{S}(n,b),\vec{\mathbf{w}}\in S(m-1,b),\vec{\mathbf{w}}\prec\vec{\mathbf{u}}}q_{x}^{a-b}p_{x}^{b}\left(\prod_{k=1}^{b}\binom{u_{k}-1}{w_{k}}\right)\frac{p_{y}}{D(y)}$
		$\displaystyle\times\left(1-\frac{1}{D(x,y)}\right)^{\sum_{k=1}^{b}1_{u_{k}=0}}\left(\frac{1}{D(x,y)}\right)^{\sum_{k=1}^{b}1_{u_{k}\neq 0}}\left(p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{m-1}$
		$\displaystyle\times\left(q_{y}\frac{D(x,y-1)}{D(x,y)}\right)^{n-(m-1)-\sum_{k=1}^{b}1_{u_{k}\neq 0}}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{\sum_{k=1}^{b}1_{u_{k}\neq 0}-1}$
		$\displaystyle=\sum_{i=1}^{b\wedge(n-m+1)}\binom{a-1}{b-1}\sum_{\vec{\mathbf{u}}\in\tilde{S}_{i}(n,b),\vec{\mathbf{w}}\in S(m-1,b),\vec{\mathbf{w}}\prec\vec{\mathbf{u}}}q_{x}^{a-b}p_{x}^{b}\left(\prod_{k=1}^{b}\binom{u_{k}-1}{w_{k}}\right)\frac{p_{y}}{D(y)}$
		$\displaystyle\times\left(1-\frac{1}{D(x,y)}\right)^{b-i}\left(\frac{1}{D(x,y)}\right)^{i}\left(p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{m-1}$
		$\displaystyle\times\left(q_{y}\frac{D(x,y-1)}{D(x,y)}\right)^{n-(m-1)-i}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{i-1}$
		$\displaystyle=\sum_{i=1}^{b\wedge(n-m+1)}\binom{a-1}{b-1}\binom{b-1}{i-1}\sum_{\vec{\mathbf{u}}\in S(n,i),\vec{\mathbf{w}}\in S(m-1,i),\vec{\mathbf{w}}\prec\vec{\mathbf{u}}}q_{x}^{a-b}p_{x}^{b}\left(\prod_{k=1}^{i}\binom{u_{k}-1}{w_{k}}\right)$
		$\displaystyle\times\frac{p_{y}}{D(y)}\left(1-\frac{1}{D(x,y)}\right)^{b-i}\left(\frac{1}{D(x,y)}\right)^{i}\left(p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{m-1}$
		$\displaystyle\times\left(q_{y}\frac{D(x,y-1)}{D(x,y)}\right)^{n-(m-1)-i}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{i-1}$
		$\displaystyle=\binom{a-1}{b-1}\sum_{i=1}^{b\wedge(n-m+1)}\binom{b-1}{i-1}\binom{n-1}{i-1}\binom{n-i}{m-1}q_{x}^{a-b}p_{x}^{b}\frac{p_{y}}{D(y)}$
		$\displaystyle\times\left(1-\frac{1}{D(x,y)}\right)^{b-i}\left(\frac{1}{D(x,y)}\right)^{i}\left(p_{y}\left(1-\frac{1}{D(y)}\right)\right)^{b-1}$
		$\displaystyle\times\left(q_{y}\frac{D(x,y-1)}{D(x,y)}\right)^{a-(b-1)-i}\left(q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)\right)^{i-1},$

where for the last equality we use the fact that

\sum_{\vec{\mathbf{w}}\in S(m-1,i),\vec{\bf w}\prec\vec{\bf u}}\prod_{k=1}^{i}\binom{u_{k}-1}{w_{k}}=\binom{n-i}{m-1},\text{ for each }\vec{\bf u}\in S(n,i).

The lemma is proved. $\Box$

5.2.2 Proof of Proposition 4 for $C=C(a,b)$ or $C(*,a)$

Proof. Fix $a\geq b\geq 1.$ Suppose $\rho_{k}\rightarrow 1$ as $k\rightarrow\infty.$ Then we have $p_{x}\rightarrow 1/2,$ $q_{x}\rightarrow 1/2,$ $D(x)\rightarrow\infty$ as $x\rightarrow\infty$ and $p_{k}\vee p_{k}^{-1}\vee q_{k}\vee q_{k}^{-1}<c,$ $\rho_{k}\vee\rho_{k}^{-1}\leq c,$ for all $k\geq 1.$ Firstly, it follows directly from (72) and (73) that

\displaystyle\mathbb{P}(x\in C(a,b))<\binom{a-1}{b-1}\frac{1}{D(x)},\ \mathbb{P}(x\in C(*,a))<\frac{1}{D(x)}

(89)

and

\displaystyle\lim_{x\rightarrow\infty}\mathbb{P}(x\in C(a,b))D(x)=\frac{1}{2^{a}}\binom{a-1}{b-1},\ \lim_{x\rightarrow\infty}\mathbb{P}(x\in C(*,a))D(x)=1.

We thus get (58) for $C=C(a,b)$ or $C(*,a).$

Furthermore, it is straightforward to see from (72), (9) and (73), (75) that

\displaystyle\mathbb{P}(y\in C|x\in C)<\frac{cD(x)}{D(x,y)D(y)},\text{ for }y\geq x\geq 0,\ C=C(a,b)\text{ or }C(*,a),

which proves (59). Putting (59) and (89) together, on accounting of (47) and (50)-(51), we get (61).

Next, we show (62). For this purpose, on one hand, from (72) and (9), we get

	$\displaystyle\frac{\mathbb{P}(x\in C(a,b),y\in C(a,b))}{\mathbb{P}(x\in C(a,b))\mathbb{P}(y\in C(a,b))}$
	$\displaystyle=\frac{D(x)}{D(x,y)}\left(1-\frac{1}{D(x,y)}\right)^{b-1}\left(\frac{D(x,y-1)}{D(x,y)}\right)^{a-b}\left(1-\frac{1}{D(x)}\right)^{1-b}$
	$\displaystyle+\frac{D(x)}{D(x,y)}\binom{a-1}{b-1}^{-1}\sum_{i=2}^{b\wedge(a-b+1)}\binom{b-1}{i-1}\binom{a-i}{b-1}\binom{a-1}{i-1}$
	$\displaystyle\quad\quad\times\left(\frac{1}{D(x,y)}\right)^{i-1}\left(1-\frac{1}{D(x,y)}\right)^{b-i}\left(\frac{D(x,y-1)}{D(x,y)}\right)^{a-b+1-i}$
	$\displaystyle\quad\quad\times\left(1-\frac{D(x,y-1)}{D(x,y)}\right)^{i-1}\left(1-\frac{1}{D(x)}\right)^{1-b}$
	$\displaystyle=:(A)+(B).$		(90)

On the other hand, taking (73) and (75) together, we infer that

	$\displaystyle\frac{\mathbb{P}(x\in C(,a),y\in C(,a))}{\mathbb{P}(x\in C(,a))\mathbb{P}(y\in C(,a))}$
	$\displaystyle=\frac{D(x)}{D(x,y)}\left(1-\frac{1}{D(x,y)}\right)^{a-1}\left(\frac{p_{y}}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}\right)^{a}\left(1-\frac{1}{D(x)}\right)^{1-a}$
	$\displaystyle+\frac{D(x)}{D(x,y)}\sum_{i=2}^{a}\binom{a-1}{i-1}\binom{a+i-2}{i-1}\left(1-\frac{1}{D(x,y)}\right)^{a-i}\left(\frac{1}{D(x,y)}\right)^{i-1}$
	$\displaystyle\quad\quad\times\left(\frac{p_{y}}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}\right)^{a}\left(\frac{q_{y}\left(1-\frac{D(x,y-1)}{D(x,y)}\right)}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}\right)^{i-1}\left(1-\frac{1}{D(x)}\right)^{1-a}$
	$\displaystyle=:(D)+(E).$		(91)

Fix $\varepsilon>0$ and $\delta>0$ . We claim that there exists $M_{1}>0$ such that $(A)$ , $(B)$ in (90) and $(D),$ $(E)$ in (91) satisfy

	$\displaystyle\frac{D(x,y)}{D(x)}\times\max\{(B),(E)\}\leq\delta/2,\ x>M_{1},\ y>x+M_{1},$		(92)
	$\displaystyle 1-\delta/2\leq\frac{D(x,y)}{D(x)}\times(A)\leq 1+\delta/2,\ x>M_{1},\ y>x+M_{1},$		(93)

and

\displaystyle 1-\delta/2\leq\frac{D(x,y)}{D(x)}\times(D)\leq 1+\delta/2,\ x>M_{1},\ y>x+M_{1}.

(94)

Indeed, choose $\eta>0$ such that

	$\displaystyle\binom{a-1}{b-1}^{-1}\sum_{i=2}^{b\wedge(a-b+1)}\binom{b-1}{i-1}\binom{a-i}{b-1}\binom{a-1}{i-1}\eta(1+\eta)^{b-1}<\delta/2,$		(95)
	$\displaystyle\sum_{i=2}^{a}\binom{a-1}{i-1}\binom{a+i-2}{i-1}\eta\left(1+\eta\right)^{2a-2}<\delta/2,$		(96)
	$\displaystyle(1+\eta)^{a-1}<1+\delta/2,\ (1-\eta)^{2a-1}>1-\delta/2.$		(97)

Since $\lim_{k\rightarrow\infty}\rho_{k}=1,$ by Lemma 3, there exists $M_{1}>0$ such that

	$\displaystyle\left(1-\frac{1}{D(x)}\right)^{-1}<1+\eta,\ \left(1-\frac{1}{D(y)}\right)^{-1}<1+\eta,$		(98)
	$\displaystyle\frac{1}{D(x,y)}<\eta,\ 1-\frac{D(x,y-1)}{D(x,y)}<\eta,\ \frac{q_{y}}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}<1+\eta,$		(99)
	$\displaystyle\frac{p_{y}}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}>1-\eta,\ x>M_{1},\ y>x+M_{1}.$		(100)

Thus, on accounting of (95) and (96), we have

	$\displaystyle\frac{D(x,y)}{D(x)}\times(B)$
	$\displaystyle\quad\quad\leq\binom{a-1}{b-1}^{-1}\sum_{i=2}^{b\wedge(a-b+1)}\binom{b-1}{i-1}\binom{a-i}{b-1}\binom{a-1}{i-1}\eta^{2i-2}(1+\eta)^{b-1}<\frac{\delta}{2},$
	$\displaystyle\frac{D(x,y)}{D(x)}\times(E)\leq\sum_{i=2}^{a}\binom{a-1}{i-1}\binom{a+i-2}{i-1}\eta^{2i-2}\left(1+\eta\right)^{2a-2}<\frac{\delta}{2},$

for all $x>M_{1},y>x+M_{1}.$ We thus get (92). To prove (93) and (94), it is easy to see from (98)-(100) that

	$\displaystyle(1-\eta)^{a-1}\leq\frac{D(x,y)}{D(x)}\times(A)\leq(1+\eta)^{b-1},\ x>M_{1},\ y>x+M_{1},$		(101)
	$\displaystyle(1-\eta)^{2a-1}\leq\frac{D(x,y)}{D(x)}\times(D)\leq(1+\eta)^{a-1},\ x>M_{1},\ y>x+M_{1}.$		(102)

Consequently, putting (97), (101) and (102) together, we get (93) and (94). Finally, substituting (92)-(93) into (90) and (91), we get

\displaystyle 1-\delta\leq\frac{D(x,y)}{D(x)}\frac{\mathbb{P}(x\in C,y\in C)}{\mathbb{P}(x\in C)\mathbb{P}(y\in C)}\leq 1+\delta,

(103)

for $x>M_{1},y>x+M_{1},$ $C=C(a,b)$ or $C(*,a).$ But by (58), there exists a number $M_{2}>0$ such that

\displaystyle(\lambda_{C}-\delta)/D(k)\leq\mathbb{P}(k\in C)\leq(\lambda_{C}+\delta)/D(k),

(104)

for $k>M_{2},$ $C=C(a,b)$ or $C(*,a).$ Therefore, letting $N=M_{1}\vee M_{2},$ from (103), we obtain

\displaystyle\frac{(\lambda_{C}-\delta)(1-\delta)D(x)}{D(x,y)D(y)}\leq\mathbb{P}(y\in C|x\in C)\leq\frac{(\lambda_{C}+\delta)(1+\delta)D(x)}{D(x,y)D(y)},

(105)

for $x>N,$ $y>x+N,$ $C=C(a,b)$ or $C(*,a).$ Taking (104) and (105) together, thanks to (47) and (50)-(51), we conclude that

\displaystyle\frac{((\lambda_{C}-\delta)(1-\delta))^{k}}{D(j_{k})\prod_{i=1}^{k-1}D(j_{i},j_{i+1})}

\displaystyle\leq\mathbb{P}(j_{1}\in C,...,j_{k}\in C)\leq\frac{((\lambda_{C}+\delta)(1+\delta))^{k}}{D(j_{k})\prod_{i=1}^{k-1}D(j_{i},j_{i+1})},

(106)

for $0=j_{0}<j_{1}<...<j_{k},\ j_{i}-j_{i-1}>N,\ i=1,...,k,$ $C=C(a,b)$ or $C(*,a).$ Choosing $\delta$ small enough such that $(\lambda_{C}-\delta)(1-\delta)>\lambda_{C}-\varepsilon$ and $(\lambda_{C}+\delta)(1+\delta)<\lambda_{C}+\varepsilon,$ from (103), (105) and (106), we get (62), (63) and (64).

Finally, by multiplying $\mathbb{P}(x\in C),$ $C=C(a,b)$ or $C(*,a)$ on both sides of (90) or (91), respectively, and discarding the second term on the righthand side, owing to Lemma 8, we have

	$\displaystyle\mathbb{P}(x$	$\displaystyle\in C(a,b)\|y\in C(a,b))\geq(A)\times\mathbb{P}(x\in C(a,b))$
		$\displaystyle=\binom{a-1}{b-1}p_{x}^{b}q_{x}^{a-b}\frac{1}{D(x,y)}\left(1-\frac{1}{D(x,y)}\right)^{b-1}\left(\frac{D(x,y-1)}{D(x,y)}\right)^{a-b}$
		$\displaystyle\geq\binom{a-1}{b-1}\frac{c}{D(x,y)}\left(1-\frac{1}{1+\rho_{x+1}}\right)^{b-1}\left(\frac{1}{1+\rho_{y-1}}\right)^{a-b}$
		$\displaystyle\geq\frac{c}{D(x,y)},\ y\geq x\geq 0,$

and

	$\displaystyle\mathbb{P}(x$	$\displaystyle\in C(,a)\|y\in C(,a))\geq(D)\times\mathbb{P}(x\in C(*,a))$
		$\displaystyle=\frac{1}{D(x,y)}\left(1-\frac{1}{D(x,y)}\right)^{a-1}\left(\frac{p_{y}}{1-q_{y}\frac{D(x,y-1)}{D(x,y)}}\right)^{a}$
		$\displaystyle\geq\frac{1}{D(x,y)}\left(1-\frac{1}{1+\rho_{x+1}}\right)^{a-1}p_{y}^{a}\geq\frac{c}{D(x,y)},\ y\geq x\geq 0.$

That is, (60) is true for $C=C(a,b)$ or $C(*,a).$ We thus finish the proof of Proposition 4 for $C=C(a,b)$ or $C(*,a).$ $\Box$

6 Proof of Theorem 1

Based on Lemma 6 and Proposition 4, we give the proof of Theorem 1 in this section.

Proof. Let $\Gamma_{n}=\{n\in C(a,b)\},$ or $\{n\in C_{w}\},$ or $\{n\in C(*,a)\},n\geq 1.$ Let $D(m)$ and $D(m,n)$ be as in (4) and (5). Suppose that $\rho_{k}$ is increasing in $k>N_{0}$ for some $N_{0}>0$ and $\rho_{k}\rightarrow 1$ as $k\rightarrow\infty.$ Then clearly, we have

	$\displaystyle D(n)\geq D(m),\ n>m>N_{0},$		(107)
	$\displaystyle D(m,n)\leq c(n-m),\ n>m\geq 0,$		(108)

and from (58), we see that (27) holds.

Suppose now $\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}<\infty.$ If $D(0)=\infty,$ then by Proposition 1, the chain $X$ is recurrent almost surely. Therefore, $|C(a,b)|=|C(*,a)|=|C_{w}|=0$ almost surely, for $a\geq b\geq 1.$ Assume next $D(0)<\infty.$ From Lemma 6, we see that (28) is fulfilled. Putting (60) and (108) together, we deduce that (29) is fulfilled. Therefore, applying part (i) of Theorem 3, we conclude that

\displaystyle|C(a,b)|\vee|C(*,a)|\vee|C_{w}|<\infty,\ a\geq b\geq 1,

(109)

almost surely. Notice that for each $A\subseteq\{a,a+1,...\},$ $B\subset\{1,2,...,a\},$ we must have $|C(A,a)|<C(*,a)$ and $|C(a,B)|=\sum_{b\in B}|C(a,b)|.$ Consequently, we infer from (109) that $|C(A,a)|<\infty$ and $|C(a,B)|<\infty$ almost surely for each $a\in\{1,2,...\}$ $A\subseteq\{a,a+1,...\},$ and $B\subset\{1,2,...,a\}.$ The convergent part of Theorem 1 is proved.

Next, we prove the divergent part. To this end, suppose that there exist $n_{0}>0$ and $\delta>0$ such that $D(n)\leq\delta n\log n$ for all $n\geq n_{0},$ and $\sum_{n=2}^{\infty}\frac{1}{D(n)\log n}=\infty.$ From (17), we see that (30) is fulfilled. Moreover, from (107), we know that $D(n)$ is increasing in $n>N_{0}.$ Finally, from (62), we infer that (31) holds. Thus, it follows from part (ii) of Theorem 3 that

\displaystyle|C(a,b)|=\infty,\ |C_{w}|=\infty,\text{ for }a\geq b\geq 1,

(110)

almost surely. Now, consider $a\geq 1,$ $\phi\neq A\subseteq\{a,a+1,...\}$ and $\phi\neq B\subseteq\{1,2,...,a\}.$ Obviously, from (110), we obtain $|C(A,a)|=\sum_{x\in A}|C(x,a)|=\infty$ and $|C(a,B)|=\sum_{b\in B}|C(a,b)|=\infty,$ almost surely. The divergent part of Theorem 1 is proved. $\Box$

7 Expectations-Proof of Proposition 2

In this section, letting the perturbations $r_{n},n\geq 1$ be as in (9), we estimate the expectations of the cardinalities of the sets $C(a,b)\cap[1,n]$ and $C_{w}\cap[1,n].$ For this purpose, we first give the proof of Lemma 1.

7.1 Proof of Lemma 1

Proof. It is shown in Csáki et al. [4] (see page 637 therein) that $c_{1}n(\log\log n)^{\beta}<D(n)<c_{2}n(\log\log n)^{\beta}$ for some constants $0<c_{1}<c_{2}<\infty.$ The proof of Lemma 1 is a refinement of such a result. We need the following lemma.

Lemma 10.

Suppose that $f(x),x\geq 0$ is a nonnegative function, $f(x)$ is decreasing in $x>M$ for some $M>0,$ and $\sum_{k=1}^{\infty}(f(k))^{2}<\infty.$ Set $\rho_{n}=1-f(n)+O((f(n))^{2}).$ Then,

\displaystyle\rho_{1}\cdots\rho_{n}\sim c\exp\left\{-\int_{1}^{n}f(x)dx\right\}\text{ as }n\rightarrow\infty.

(111)

Proof. Under the given conditions, by checking carefully, we can show that the series

\sum_{j=1}^{\infty}\left(\log\rho_{j}+\int_{j-1}^{j}f(x)dx\right)

is convergent. Thus, (111) is true. $\Box$

Now we are ready to finish the proof of Lemma 1. Notice that $\rho_{n}=1-4r_{n}+O(r_{n}^{2})$ as $n\rightarrow\infty.$ Letting $f(x)=\frac{1}{x}+\frac{1}{x(\log\log x)^{\beta}},\ x\geq 3,$ then we have $\rho_{n}=1-f(n)+O((f(n))^{2}),$ as $n\rightarrow\infty.$ Thus, applying Lemma 10 we get

\displaystyle\rho_{1}\cdots\rho_{n}\sim\frac{c}{n}\exp\left\{-\int_{3}^{n}\frac{1}{x(\log\log x)^{\beta}}dx\right\}\text{ as }n\rightarrow\infty.

(112)

Set $B_{n}=:\sum_{i=n}^{\infty}\rho_{1}\cdots\rho_{i}$ for $n\geq 1.$ Fix $\varepsilon>0.$ By (112) there exists $M_{1}>0$ such that

	$\displaystyle(c-\varepsilon)$	$\displaystyle\frac{1}{n}\exp\left\{-\int_{3}^{n}\frac{1}{x(\log\log x)^{\beta}}dx\right\}$
		$\displaystyle\leq\rho_{1}\cdots\rho_{n}\leq(c+\varepsilon)\frac{1}{n}\exp\left\{-\int_{3}^{n}\frac{1}{x(\log\log x)^{\beta}}dx\right\},n>M_{1}.$		(113)

Thus, we have

	$\displaystyle(c-\varepsilon)$	$\displaystyle\sum_{i=n}^{\infty}\frac{1}{i}\exp\left\{-\int_{3}^{i}\frac{1}{x(\log\log x)^{\beta}}dx\right\}$
		$\displaystyle\leq B_{n}\leq(c+\varepsilon)\sum_{i=n}^{\infty}\frac{1}{i}\exp\left\{-\int_{3}^{i}\frac{1}{x(\log\log x)^{\beta}}dx\right\},n>M_{1}.$		(114)

Let $g(y)=\frac{1}{y}\exp\left\{-\int_{3}^{y}\frac{1}{x(\log\log x)^{\beta}}dx\right\},\ y\geq 3.$ Since $g(y)$ is decreasing in $y\geq 3,$ then we have $0<g(l)\leq\sum_{j=n}^{l}g(j)-\int_{n}^{l}g(y)dy\leq g(n)$ for $l>n\geq 3.$ Thus, we deduce that

\displaystyle 1\leq\frac{\sum_{j=n}^{\infty}g(j)}{\int_{n}^{\infty}g(y)dy}\leq 1+\frac{g(n)}{\int_{n}^{\infty}g(y)dy},\ n\geq 3.

But by L’Hospital’s rule, $\lim_{n\rightarrow\infty}\frac{g(n)}{\int_{n}^{\infty}g(y)dy}=0.$ Therefore, there exists a number $M_{2}>0$ such that

\displaystyle 1\leq\frac{\sum_{j=n}^{\infty}g(j)}{\int_{n}^{\infty}g(y)dy}\leq 1+\varepsilon,\ n>M_{2}.

(115)

Substituting (115) into (7.1), we infer that for $n>M_{1}\vee M_{2},$

	$\displaystyle(c-\varepsilon)$	$\displaystyle\int_{n}^{\infty}\frac{1}{y}\exp\left\{-\int_{3}^{y}\frac{1}{x(\log\log x)^{\beta}}dx\right\}dy$
		$\displaystyle\leq B_{n}\leq(c+\varepsilon)(1+\varepsilon)\int_{n}^{\infty}\frac{1}{y}\exp\left\{-\int_{3}^{y}\frac{1}{x(\log\log x)^{\beta}}dx\right\}dy.$

Since

\displaystyle\int_{n}^{\infty}\frac{1}{y}\exp\left\{-\int_{3}^{y}\frac{1}{x(\log\log x)^{\beta}}dx\right\}dy\sim(\log\log n)^{\beta}\exp\left\{\int_{3}^{n}\frac{1}{x(\log\log x)^{\beta}}dx\right\}

as $n\rightarrow\infty$ (see Csáki et al. [4], page 637), there is $M_{3}>M_{1}\vee M_{2}$ such that for $n>M_{3}$

	$\displaystyle(c-\varepsilon)(1-\varepsilon)$	$\displaystyle(\log\log n)^{\beta}\exp\left\{\int_{3}^{n}\frac{1}{x(\log\log x)^{\beta}}dx\right\}$
		$\displaystyle\leq B_{n}\leq(c+\varepsilon)(1+\varepsilon)^{2}(\log\log n)^{\beta}\exp\left\{\int_{3}^{n}\frac{1}{x(\log\log x)^{\beta}}dx\right\}.$		(116)

Noticing that $D(n)=\frac{B_{n}}{\rho_{1}\cdots\rho_{n},}$ then from (7.1) and (7.1), we get

\displaystyle\frac{(c-\varepsilon)(1-\varepsilon)}{c+\varepsilon}n(\log\log n)^{\beta}<D(n)<\frac{(c+\varepsilon)(1+\varepsilon)^{2}}{c-\varepsilon}n(\log\log n)^{\beta},\ n>M_{3}.

We thus come to the conclusion that

\displaystyle D(n)\sim n(\log\log n)^{\beta}\text{ as }n\rightarrow\infty.

Lemma 1 is proved. $\Box$

7.2 Proof of Proposition 2

Proof. Fix integers $a\geq b\geq 1.$ For $k\geq 1,$ we set $\eta_{k}=1_{\{k\in C(a,b)\}},$ $\varphi_{k}=1_{\{k\in C_{w}\}}.$ Then we have

|C(a,b)\cap[1,n]|=\sum_{k=1}^{n}\eta_{k}\text{ and }|C_{w}\cap[1,n]|=\sum_{k=1}^{n}\varphi_{k}.

It follows from Lemma 8 that

	$\displaystyle\mathbb{P}(\eta_{k}=1)$	$\displaystyle=\mathbb{P}(k\in C(a,b))=\mathbb{P}(\xi(k)=a,\xi(k,\uparrow)=b)$
		$\displaystyle=\binom{a-1}{b-1}\frac{p_{k}^{b}q_{k}^{a-b}}{D(k)}\left(1-\frac{1}{D(k)}\right)^{b-1},$
	$\displaystyle\mathbb{P}(\varphi_{k}=1)$	$\displaystyle=\mathbb{P}(k\in C_{w})=\frac{1}{p_{k}D(k-1)}.$

Noting that $p_{k}\rightarrow 1/2,$ as $k\rightarrow\infty,$ thus applying Lemma 1, we see that

	$\displaystyle\mathbb{P}(\eta_{k}=1)\sim\binom{a-1}{b-1}\frac{1}{2^{a}k(\log\log k)^{\beta}}\text{ as }k\rightarrow\infty,$
	$\displaystyle\mathbb{P}(\varphi_{k}=1)\sim\frac{2}{k(\log\log k)^{\beta}}\text{ as }k\rightarrow\infty.$

Consequently, for $\varepsilon>0,$ there exists a number $M_{1}>0$ such that

	$\displaystyle\binom{a-1}{b-1}\frac{1-\varepsilon}{2^{a}k(\log\log k)^{\beta}}\leq$	$\displaystyle\mathbb{P}(\eta_{k}=1)\leq\binom{a-1}{b-1}\frac{1+\varepsilon}{2^{a}k(\log\log k)^{\beta}},\ k\geq M_{1},$
	$\displaystyle\frac{2(1-\varepsilon)}{k(\log\log k)^{\beta}}\leq$	$\displaystyle\mathbb{P}(\varphi_{k}=1)\leq\frac{2(1+\varepsilon)}{k(\log\log k)^{\beta}},\ k\geq M_{1}.$

But

\displaystyle\sum_{k=M_{1}}^{n}

\displaystyle\frac{1}{k(\log\log k)^{\beta}}\sim\int_{M_{1}}^{n}\frac{dx}{x(\log\log x)^{\beta}}\sim\frac{\log n}{(\log\log n)^{\beta}},\ n\rightarrow\infty.

Therefore, there exists a number $M_{2}>M_{1}$ such that for $n>M_{2},$

	$\displaystyle\binom{a-1}{b-1}\frac{(1-\varepsilon)^{2}\log n}{2^{a}(\log\log n)^{\beta}}\leq$	$\displaystyle\sum_{k=M_{2}}^{n}\mathbb{P}(\eta_{k}=1)\leq\binom{a-1}{b-1}\frac{(1+\varepsilon)^{2}\log n}{2^{a}(\log\log n)^{\beta}},$		(117)
	$\displaystyle\frac{2(1-\varepsilon)^{2}\log n}{(\log\log n)^{\beta}}\leq$	$\displaystyle\sum_{k=M_{2}}^{n}\mathbb{P}(\varphi_{k}=1)\leq\frac{2(1+\varepsilon)^{2}\log n}{(\log\log n)^{\beta}}.$		(118)

As a result, we deduce from (117) that

	$\displaystyle(1-\varepsilon)^{2}$	$\displaystyle\leq\varliminf_{n\rightarrow\infty}\frac{2^{a}(\log\log n)^{\beta}}{\binom{a-1}{b-1}\log n}\mathbb{E}\|C(a,b)\cap[1,n]\|$
		$\displaystyle\leq\varlimsup_{n\rightarrow\infty}\frac{2^{a}(\log\log n)^{\beta}}{\binom{a-1}{b-1}\log n}\mathbb{E}\|C(a,b)\cap[1,n]\|\leq(1+\varepsilon)^{2}.$

Since $\varepsilon$ is arbitrary, letting $\varepsilon\rightarrow 0,$ we get (10). Similarly, from (118) we get (11). Proposition 2 is proved. $\Box$

8 Limit distributions-Proof of Theorem 2

This section is devoted to proving Theorem 2. The proof is based on the moment method. To start with, we give an auxiliary lemma to estimate $D(i)$ and $D(i,j).$

8.1 An auxiliary lemma

Lemma 11.

Set $r_{1}=1/4,$ and for $n\geq 2,$ let $r_{n}=\frac{1}{2n}.$ Suppose that $p_{n}=1/2+r_{n},\ n\geq 1.$ Then there exists a number $i_{0}>0$ such that

	$\displaystyle(1-\varepsilon)\frac{i(j-i)}{j}\leq D(i$	$\displaystyle,j)\leq(1+\varepsilon)\frac{i(j-i)}{j},\ j>i\geq i_{0},$		(119)
	$\displaystyle(1-\varepsilon)i\leq D($	$\displaystyle i)\leq(1+\varepsilon)i,\ i\geq i_{0}.$		(120)

Proof. Notice that

\rho_{n}\sim 1-4r_{n}+O(r_{n}^{2})=1-\frac{2}{n}+O(n^{-2}),\ n\rightarrow\infty.

Then for $j>i\geq 1,$ choosing $\theta_{n}\in(0\wedge(\rho_{n}-1),0\vee(\rho_{n}-1)),\ i\leq n\leq j$ properly, we have

	$\displaystyle\rho_{i}\cdots\rho_{j}$	$\displaystyle=e^{\sum_{n=i}^{j}\log\rho_{n}}=e^{-\sum_{n=i}^{j}\frac{(\rho_{n}-1)^{2}}{2(1+\theta_{n})^{2}}}e^{\sum_{n=i}^{j}(\rho_{n}-1)}$
		$\displaystyle\geq e^{-\sum_{n=i}^{\infty}\frac{cn^{-2}}{2(1+\theta_{n})2}}e^{-2\sum_{n=i}^{j}\frac{1}{n}}e^{-\sum_{n=i}^{\infty}cn^{-2}}$
		$\displaystyle\geq e^{-\sum_{n=i}^{\infty}\frac{cn^{-2}}{2(1+\theta_{n})2}}e^{-2\int_{i}^{j+1}\frac{1}{x}dx}e^{-\sum_{n=i}^{\infty}cn^{-2}}$
		$\displaystyle=\left(\frac{i}{j+1}\right)^{2}e^{-\sum_{n=i}^{\infty}\frac{cn^{-2}}{2(1+\theta_{n})2}}e^{-\sum_{n=i}^{\infty}cn^{-2}}.$

Fix $\varepsilon>0.$ We can find a number $i_{1}$ such that $\frac{i}{i-1}\frac{j}{j+1}e^{-\sum_{n=i}^{\infty}\frac{cn^{-2}}{2(1+\theta_{n})2}}e^{-\sum_{n=i}^{\infty}cn^{-2}}>(1-\varepsilon)^{1/2}$ for all $i\geq i_{1}.$ Thus we have

\displaystyle\rho_{i}\cdots\rho_{j}\geq(1-\varepsilon)^{1/2}\left(\frac{i-1}{j}\right)^{2},\text{ for all }j\geq i\geq i_{1}.

Similarly, we can find a number $i_{2}>i_{1}$ such that

\displaystyle\rho_{i}\cdots\rho_{j}\leq(1+\varepsilon)^{1/2}\left(\frac{i-1}{j}\right)^{2},\text{ for all }j\geq i\geq i_{2}.

Consequently, we get

\displaystyle(1-\varepsilon)^{1/2}\left(\frac{i-1}{j}\right)^{2}\leq\rho_{i}\cdots\rho_{j}\leq(1+\varepsilon)^{1/2}\left(\frac{i-1}{j}\right)^{2},\text{ for all }j\geq i\geq i_{2}.

As a result, we obtain

\displaystyle(1-\varepsilon)^{1/2}\sum_{n=i}^{j-1}\left(\frac{i}{n}\right)^{2}\leq D(i,j)\leq(1+\varepsilon)^{1/2}\sum_{n=i}^{j-1}\left(\frac{i}{n}\right)^{2},\ j>i\geq i_{2}.

Notice that for some number $i_{0}>i_{2},$ we have

\displaystyle(1-\varepsilon)^{1/2}\frac{i(j-i)}{j}\leq\sum_{n=i}^{j-1}\left(\frac{i}{n}\right)^{2}\leq(1+\varepsilon)^{1/2}\frac{i(j-i)}{j},\ j>i\geq i_{0}.

Therefore, we get

\displaystyle(1-\varepsilon)\frac{i(j-i)}{j}\leq D(i,j)\leq(1+\varepsilon)\frac{i(j-i)}{j},\ j>i\geq i_{0}

which proves (119). Letting $j\rightarrow\infty$ in (119), we get (120). Lemma 11 is proved. $\Box$

8.2 Convergence of the moments

An important step to prove Theorem 2 is to show the convergence of $\frac{\mathbb{E}(|C\cap[1,n]|^{k})}{(\log n)^{k}},$ for $k\geq 1,$ $C=C(a,b),$ $C(*,a)$ or $C_{w},$ as $n\rightarrow\infty.$ We have the following lemma.

Lemma 12.

Fix integers $a\geq b\geq 1.$ Let $r_{1}=1/4$ and $r_{n}=\frac{1}{2n}$ for $n\geq 2.$ Set $p_{n}=\frac{1}{2}+r_{n}$ for $n\geq 1.$ Then we have

\displaystyle\lim_{n\rightarrow\infty}\frac{\mathbb{E}(|C\cap[1,n]|^{k})}{(\log n)^{k}}=\left\{\begin{array}[]{cl}\frac{k!}{2^{ak}}\binom{a-1}{b-1}^{k}&\text{if }\ C=C(a,b),\\ k!&\text{if }\ C=C(*,a),\\ 2^{k}k!&\text{if }\ C=C_{w},\end{array}\right.\text{ for }\ k\geq 1.

Proof. Consider $C=C(a,b),C_{w}$ or $C(*,a).$ Let $\lambda_{C}$ be the one in (58). For $k\geq 1,$ set $\eta_{k}=1_{\{k\in C\}},$ clearly we have $|C\cap[1,n]|=\sum_{k=1}^{n}\eta_{k}.$

Let $S(a,j)$ be the one defined in (18). Then

	$\displaystyle\mathbb{\mathbb{missing}}E\|C\cap[1,n]\|^{k}$	$\displaystyle=\mathbb{E}\left(\left(\sum_{j=1}^{n}\eta_{j}\right)^{k}\right)=\sum_{0<j_{1},j_{2},...,j_{k}\leq n}\mathbb{E}\left(\eta_{j_{1}}\eta_{j_{2}}\cdots\eta_{j_{k}}\right)$
		$\displaystyle=\sum_{m=1}^{k}\sum_{\begin{subarray}{c}l_{1}+\dots+l_{m}=k,\\ l_{i}\geq 1,i=1,...,m\end{subarray}}m!\binom{k}{m}\sum_{0<j_{1}<...<j_{m}\leq n}\mathbb{E}\left(\eta_{j_{1}}^{l_{1}}\cdots\eta_{j_{m}}^{l_{m}}\right)$
		$\displaystyle=\sum_{m=1}^{k}\sum_{(l_{1},...,l_{m})\in S(k,m)}m!\binom{k}{m}\sum_{0<j_{1}<...<j_{m}\leq n}\mathbb{E}\left(\eta_{j_{1}}^{l_{1}}\cdots\eta_{j_{m}}^{l_{m}}\right).$

Since the values of $\eta_{j},j=1,...,n$ are either $0$ or $1,$ then taking Lemma 4 into account, we have

	$\displaystyle\mathbb{E}\|C\cap[1,n]\|^{k}=\sum_{m=1}^{k}\binom{k-1}{m-1}m!\binom{k}{m}\sum_{0<j_{1}<...<j_{m}\leq n}\mathbb{E}(\eta_{j_{1}}\cdots\eta_{j_{m}})$
	$\displaystyle=\sum_{m=1}^{k}\binom{k-1}{m-1}m!\binom{k}{m}\sum_{0<j_{1}<...<j_{m}\leq n}\mathbb{P}(j_{1}\in C,..,j_{m}\in C)$
	$\displaystyle=:\sum_{m=1}^{k}\binom{k-1}{m-1}m!\binom{k}{m}G(n,m).$		(121)

Fix $\varepsilon>0.$ Let $N$ and $i_{0}$ be as in Proposition 4 and Lemma 11, respectively. Set $n_{2}=N\vee i_{0}$ and denote temporarily

	$\displaystyle A=\{(j_{1},...,j_{m})\mid 0<j_{1}<....<j_{m}\leq n,j_{i+1}-j_{i}>n_{2},\forall 0\leq i\leq m-1\},$
	$\displaystyle B=\{(j_{1},...,j_{m})\mid 0<j_{1}<....<j_{m}\leq n,(j_{1},...,j_{m})\notin A\},$
	$\displaystyle B_{i}=\{(j_{1},...,j_{m})\mid j_{1}<...<j_{i}\leq n_{2}<j_{i+1}<...<j_{m}\leq n\},i=1,...,m-1,$
	$\displaystyle B_{m}=\{(j_{1},...,j_{m})\|n_{2}<j_{1}<..<j_{m},\{1\leq s\leq m-1\|j_{s+1}-j_{s}<n_{2}\}\neq\phi\},$

where and in the remainder of this proof we set $j_{0}=0.$ Obviously, we have $B=\bigcup_{i=1}^{m}B_{i}.$ Therefore, we can write

	$\displaystyle G(n,m)$	$\displaystyle=\sum_{(j_{1},...,j_{m})\in A}+\sum_{i=1}^{m}\sum_{(j_{1},...,j_{m})\in B_{i}}\mathbb{P}(j_{1}\in C,..,j_{m}\in C)$
		$\displaystyle=:G_{A}(n,m)+\sum_{i=1}^{m}G_{B_{i}}(n,m).$		(122)

Consider first the term $G_{A}(n,m).$ From (64), (119) and (120), we get

	$\displaystyle G_{A}(n,m)$	$\displaystyle=\sum_{(j_{1},...,j_{m})\in A}\mathbb{P}(j_{1}\in C,...,j_{m}\in C)$
		$\displaystyle\leq(\lambda_{C}+\varepsilon)^{m}(1+\varepsilon)^{m}\sum_{(j_{1},...,j_{m})\in A}\frac{1}{\left(\prod_{i=1}^{m-1}D(j_{i},j_{i+1})\right)D(j_{m})}$
		$\displaystyle\leq(\lambda_{C}+\varepsilon)^{m}(1+\varepsilon)^{m}\sum_{(j_{1},...,j_{m})\in A}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{m}-j_{m-1})}.$

Applying Lemma 5, we obtain

\displaystyle\varlimsup_{n\rightarrow\infty}\frac{G_{A}(n,m)}{(\log n)^{m}}\leq(\lambda_{C}+\varepsilon)^{m}(1+\varepsilon)^{m}.

(123)

Similarly, we have

\displaystyle\varliminf_{n\rightarrow\infty}\frac{G_{A}(n,m)}{(\log n)^{m}}\geq(\lambda_{C}-\varepsilon)^{m}(1-\varepsilon)^{m}.

(124)

Next, we claim that

\displaystyle\lim_{n\rightarrow\infty}\frac{G_{B_{i}}(n,m)}{(\log n)^{m}}=0,i=1,...,m.

(125)

Indeed, for each $1\leq i\leq m,$ from (61), we see that

\displaystyle G_{B_{i}}(n,m)\leq\sum_{(j_{1},...,j_{m})\in B_{i}}\frac{c}{\left(\prod_{i=1}^{m-1}D(j_{i},j_{i+1})\right)D(j_{m})}.

(126)

Then, in view of (26), (119) and (120), we have

\displaystyle\varlimsup_{n\rightarrow\infty}\frac{G_{B_{m}}(n,m)}{(\log n)^{m}}\leq\varlimsup_{n\rightarrow\infty}\frac{c}{(\log n)^{m}}\sum_{(j_{1},...,j_{m})\in B_{m}}\frac{1}{j_{1}(j_{2}-j_{1})\cdots(j_{m}-j_{m-1})}=0.

For $1\leq i\leq m-1,$ from (119), (120) and (126), we deduce that

	$\displaystyle G_{B_{i}}(n,m)$	$\displaystyle\leq c\sum_{\begin{subarray}{c}0\leq j_{1}<...<j_{i}\leq n_{2},\\ n\geq j_{m}>...>j_{i+1}>n_{2}\end{subarray}}\frac{1}{\left(\prod_{s=1}^{m-1}D(j_{s},j_{s+1})\right)D(j_{m})},$
		$\displaystyle\leq c\sum_{0<j_{1}<...<j_{i}\leq n_{2}}\frac{1}{\prod_{s=1}^{i}D(j_{s},j_{s+1})}$
		$\displaystyle\quad\quad\quad\quad\times\sum_{n\geq j_{m}>...>j_{i+1}>n_{2}}\frac{1}{j_{m}\prod_{s=i+1}^{m-1}(j_{s+1}-j_{s})}$
		$\displaystyle\leq c\binom{n_{2}}{i}\max_{0<j_{1}<...<j_{i}\leq n_{2}}\frac{1}{\prod_{s=1}^{i}D(j_{s},j_{s+1})}$
		$\displaystyle\quad\quad\quad\quad\times\sum_{n\geq j_{m-i}>...>j_{1}>n_{2}}\frac{1}{j_{m-i}\prod_{s=1}^{m-i-1}(j_{s+1}-j_{s})}.$

But it follows from Lemma 5 that

\displaystyle\lim_{n\rightarrow\infty}\frac{1}{(\log n)^{m-i}}\sum_{n\geq j_{m-i}>...>j_{1}>n_{2}}\frac{1}{j_{m-i}\prod_{s=1}^{m-i-1}(j_{s+1}-j_{s})}=1.

Therefore, we obtain

\displaystyle\varlimsup_{n\rightarrow\infty}\frac{G_{B_{i}}(n,m)}{(\log n)^{m}}=0,1\leq i\leq m-1.

We thus finish the proof of (125).

Now, putting (123), (124) and (125) together, we infer from (8.2) that

\displaystyle(\lambda_{C}-\varepsilon)^{m}(1-\varepsilon)^{m}\leq\varliminf\frac{G(n,m)}{(\log n)^{m}}\leq\varlimsup\frac{G(n,m)}{(\log n)^{m}}\leq(\lambda_{C}+\varepsilon)^{m}(1+\varepsilon)^{m}.

Since $\varepsilon$ is arbitrary, letting $\varepsilon\rightarrow 0,$ we get

\displaystyle\lim_{n\rightarrow\infty}\frac{G(n,m)}{(\log n)^{m}}=\lambda_{C}^{m}.

Consequently, dividing by $(\log n)^{k}$ on both sides of (121) and taking the limit, we conclude that

\displaystyle\lim_{n\rightarrow\infty}\frac{\mathbb{E}|C\cap[1,n]|^{k}}{(\log n)^{k}}=k!\lambda_{C}^{k}.

Lemma 12 is proved. $\Box$

8.3 Proof of Theorem 2

Proof. We have shown in Lemma 12 that for $k\geq 1,$ $\mathbb{E}\left(\frac{|C(a,b)\cap[1,n]|}{2^{-a}\binom{a-1}{b-1}\log n}\right)^{k}\rightarrow k!$ , $\mathbb{E}\left(\frac{|C(*,a)\cap[1,n]|}{\log n}\right)^{k}\rightarrow k!$ and $\mathbb{E}\left(\frac{|C_{w}\cap[1,n]|}{2\log n}\right)^{k}\rightarrow k!$ as $n\rightarrow\infty.$ Since $((2n)!)^{-\frac{1}{2n}}\sim\frac{e}{2n},$ as $n\rightarrow\infty,$ we thus have

\displaystyle\sum_{k=1}^{\infty}((2k)!)^{-\frac{1}{2k}}=\infty.

Consequently, using Carleman’s test for the uniqueness of the moment problem (see e.g., [12, Chap.II, §12]), we conclude that

\displaystyle\frac{\left|C(a,b)\cap[1,n]\right|}{2^{-a}\binom{a-1}{b-1}\log n}\overset{d}{\rightarrow}S,\ \frac{|C(*,a)\cap[1,n]|}{\log n}\overset{d}{\rightarrow}S\text{ and }\frac{\left|C_{w}\cap[1,n]\right|}{2\log n}\overset{d}{\rightarrow}S

as $n\rightarrow\infty,$ where $S$ is an exponential random variable with $\mathbb{P}(S>t)=e^{-t},t>0.$ Theorem 2 is proved. $\Box$

Acknowledgements: The authors are in debt to two anonymous referees who read carefully an earlier unpublished version of our manuscript [13], provided us with very useful suggestions and comments, and especially helped us to improve the proofs of Lemma 5 and Lemma 9 in the current manuscript, respectively. We also thank Professor A. Földes for confirming to us that an additional monotonicity condition of $D(n)$ is required for [4, Theorem 1.1]. This project is partially supported by the National Natural Science Foundation of China (Grant No. 11501008) and the Nature Science Foundation of Anhui Educational Committee (Grant No. 2023AH040025).

References

[1] K.L. Chung, Markov chains with stationary transition probabilities, 2nd ed. Springer, New York, 1967.
[2] E. Csáki, A. Földes, P. Révész, Transient nearest neighbor random walk on the line, J. Theoret. Probab. 22 (1) (2009) 100-122.
[3] E. Csáki, A. Földes, P. Révész, Transient nearest neighbor random walk and Bessel process, J. Theoret. Probab. 22 (4) (2009) 992-1009.
[4] E. Csáki, A. Földes, P. Révész, On the number of cutpoints of transient nearest neighbor random walk on the line, J. Theoret. Probab. 23 (2) (2010) 624-638.
[5] M. Dwass, Branching processes in simple random walk, Proc. Amer. Math. Soc. 51 (2) (1975) 270-274.
[6] N. James, R. Lyons, Y. Peres, A transient Markov chain with finitely many cutpoints, In: IMS Collections Probability and Statistics: Essays in Honor of David A. Freedman, 2 (2008) 24-29, Institute of Mathematical Statistics.
[7] F.B. Knight, Random walks and a sojourn density process of Brownian motion, Trans. Amer. Math. Soc. 109 (1963) 56-86.
[8] J. Lamperti, Criteria for the recurrence or transience of stochastic processes. I, J. Math. Anal. Appl. 1 (3-4) (1960) 314-330.
[9] J. Lamperti, A new class of probability limit theorems, J. Math. Mech. 11 (5) (1962) 749-772.
[10] J. Lamperti, Criteria for stochastic processes II: Passage-time moments, J. Math. Anal. Appl. 7 (1) (1963) 127-145.
[11] V.V. Petrov, A generalization of the Borel-Cantelli lemma, Statist. Probab. Lett. 67 (3) (2004) 233-239.
[12] A.N. Shiryaev, Probability, 2nd ed. Springer-Verlag, Berlin/Heidelberg/New York, 1996.
[13] H.-M. Wang, Local time of transient random walk on the lattice of positive half line. Preprint, (2023) arXiv: 2306.14376.