Return to Answer

Define (the starting times of the walks) $S_1,S_2,\dots$ and (the finishing times of the walks) $F_0,F_1,F_2,\dots$ by the following recursion: \begin{equation*} F_0:=0 \end{equation*} and, for $k\in\N$, \begin{equation*} S_k:=F_{k-1}+T_k,\quad F_k:=\inf\{n\in\N\colon n>S_k,W^{(k)}_n=0\}, \tag{3} \end{equation*} where \begin{equation*} W^{(k)}_n:=\sum_{i\in\N}R_i\,1(S_k<i\le n). \tag{3a} \end{equation*} Note that $F_k=\min\{n\in\N\colon n>S_k,W^{(k)}_n=0\}<\infty$ for all $k\in\N_0:=\{0\}\cup\N$ almost surely (a.s.), because the simple random walk is recurrent. So, $S_k<\infty$ for all $k\in\N$ a.s.

Showing that $((Y_n,\F_n))_{n\in\N}$ is a martingale: Abusing notation as is commonly done, for a r.v. $X$ let us write $X\in\F_n$ to mean that $X$ is $\F$-measurable. Then obviously $1(F_0\le n)=1(0\le n)\in\F_0:=\{\Om,\emptyset\}\subseteq\F_1$ for all $n\in\N$. Using now the relations \begin{equation*} 1(S_k\le n)=\sum_{j=1}^{n-1}1(T_k=j)1(F_{k-1}\le n-j), \end{equation*} $1(T_k=j)=1(T_k\le j)-1(T_k\le j-1)$, and \begin{equation*} \{F_k\not\le n\}= \bigcap_{m=1}^n\Big(\{S_k\not\le m-1\}\cup\Big\{\sum_{i=1}^m R_i\,1(S_k\le i-1)\ne0\Big\}\Big) \end{equation*} for natural $k,j$ (which follow by (3) and (3a)), we conclude by induction on $k$ that \begin{equation*} \{S_k\le n\}\in\F_n,\quad \{F_k\le n\}\in\F_n \tag{5} \end{equation*} for all natural $k,n$.

Define (the starting times of the walks) $S_1,S_2,\dots$ and (the finishing times of the walks) $F_0,F_1,F_2,\dots$ by the following recursion: \begin{equation*} F_0:=0 \end{equation*} and, for $k\in\N$, \begin{equation*} S_k:=F_{k-1}+T_k,\quad F_k:=\inf\{n\in\N\colon n>S_k,W^{(k)}_n=0\}, \tag{3} \end{equation*} where \begin{equation*} W^{(k)}_n:=\sum_{i\in\N}R_i\,1(S_k<i\le n). \tag{3a} \end{equation*} Note that $F_0=0<\infty$ and $F_k=\min\{n\in\N\colon n>S_k,W^{(k)}_n=0\}<\infty$ for all $k\in\N$ almost surely (a.s.), because the simple random walk is recurrent. So, $S_k<\infty$ for all $k\in\N$ a.s.

Showing that $((Y_n,\F_n))_{n\in\N}$ is a martingale: Abusing notation as is commonly done, for a r.v. $X$ let us write $X\in\F_n$ to mean that $X$ is $\F_n$-measurable. Then obviously $1(F_0\le n)=1(0\le n)\in\F_0:=\{\Om,\emptyset\}\subseteq\F_1$ for all $n\in\N$. Using now the relations \begin{equation*} 1(S_k\le n)=\sum_{j=1}^{n-1}1(T_k=j)1(F_{k-1}\le n-j), \end{equation*} $1(T_k=j)=1(T_k\le j)-1(T_k\le j-1)$, and \begin{equation*} \{F_k\not\le n\}= \bigcap_{m=1}^n\Big(\{S_k\not\le m-1\}\cup\Big\{\sum_{i=1}^m R_i\,1(S_k\le i-1)\ne0\Big\}\Big) \end{equation*} for natural $k,j$ (which follow by (3) and (3a)), we conclude by induction on $k$ that \begin{equation*} \{S_k\le n\}\in\F_n,\quad \{F_k\le n\}\in\F_n \tag{5} \end{equation*} for all natural $k,n$.

Construction: Let $T_1,T_2,\dots$ be independent geometrically distributed random variables (r.v.'s) (defined on some measurable space $(\Om,\F)$) with means $ET_i=1/p_i$, where $0<p_i<1/2$ and \begin{equation*} \sum_{i\in\N}p_i^{1/2}<\infty. \tag{1} \end{equation*} So, \begin{equation*} P(T_i=t)=p_i q_i^{t-1}\,1(t\in\N) \tag{2} \end{equation*} for real $t$, where $q_i:=1-p_i$.

Let $R_1,R_2,\dots$ be independent Rademacher r.v.'s (defined on the same measurable space $(\Om,\F)$) that are independent of the $T_i$'s; so, $P(R_i=1|(T_j))=1/2=P(R_i=-1|(T_j))$ for all $i\in\N$.

Construction: Let $T_1,T_2,\dots$ be independent geometrically distributed random variables (r.v.'s) (defined on some probability space $(\Om,\F,P)$) with means $ET_i=1/p_i$, where $0<p_i<1/2$ and \begin{equation*} \sum_{i\in\N}p_i^{1/2}<\infty. \tag{1} \end{equation*} So, \begin{equation*} P(T_i=t)=p_i q_i^{t-1}\,1(t\in\N) \tag{2} \end{equation*} for real $t$, where $q_i:=1-p_i$.

Let $R_1,R_2,\dots$ be independent Rademacher r.v.'s (defined on the same probability space $(\Om,\F,P)$) that are independent of the $T_i$'s; so, $P(R_i=1|(T_j))=1/2=P(R_i=-1|(T_j))$ for all $i\in\N$.

Showing that $Y_n\to0$ in probability (as $n\to\infty$): By (4), \begin{equation*} 1(Y_n\ne0\}=\sum_{k\in\N}1(S_k<n\le F_k) \tag{6} \end{equation*} and hence \begin{equation*} P(Y_n\ne0\}=\sum_{k\in\N}P(S_k<n\le F_k). \tag{7} \end{equation*} Here and in what follows, $n$ and $k$ are natural numbers. Next, consider the duration \begin{equation*} D_k:=F_k-S_k \end{equation*} of the $k$th walk. Since the $R_i$'s are independent and independent of the $T_j$'s, the r.v.'s $D_1,D_2,\dots$ are independent and independent of the $T_j$'s, and the $T_j$'s are also independent. So, the r.v.'s $T_1,D_1,T_2,D_2,\dots$ are independent. Also, \begin{equation*} S_k=T_1+\sum_{j=2}^k(D_{j-1}+T_j). \tag{8} \end{equation*} So, $S_k$ and $D_k$ are independent and hence
\begin{equation*} P(S_k<n\le F_k)=\sum_{d\in\N}P(D_k=d)P(S_k<n\le S_k+d). \end{equation*} Using (8) and the independence of $T_1,D_1,T_2,D_2,\dots$, for all $d\in\N$ we have \begin{equation*} P(S_k<n\le S_k+d)\le\sup_{m\in\Z}P(T_k<n\le T_k+d)=\sum_{t=1}^d p_kq_k^{t-1}. \end{equation*} So, \begin{equation*} \begin{aligned} P(S_k<n\le F_k)&\le\sum_{d\in\N}P(D_k=d)\sum_{t=1}^d p_kq_k^{t-1} \\ &=\sum_{t\in\N}^d p_kq_k^{t-1}\sum_{d=t}^\infty P(D_k=d) \\ &=\sum_{t\in\N}^d p_kq_k^{t-1}P(D_k\ge t) \\ &=\sum_{t\in\N}^d p_kq_k^{t-1}P(D_1\ge t) \\ &\le\sum_{t\in\N} p_kq_k^{t-1}ct^{-1/2}, \end{aligned} \end{equation*} since, by (say) the reflection principle, $P(D_1\ge t)\le ct^{-1/2}$ for $t\in\N$. Here and in what follows, $c$ denotes various universal positive real constants. Therefore and because $0<p_k<1/2$, \begin{equation*} \begin{aligned} P(S_k<n\le F_k)&\le 2c\sum_{t\in\N} p_k(1-p_k)^t t^{-1/2} \\ &\le 2cp_k \sum_{t\in\N} e^{-p_k t}t^{-1/2} \\ &\le 2cp_k \int_0^\infty e^{-p_k t}t^{-1/2}\,dt =cp_k^{1/2}. \end{aligned} \tag{9} \end{equation*}

Showing that $Y_n\to0$ in probability (as $n\to\infty$): By (4), \begin{equation*} 1(Y_n\ne0\}=\sum_{k\in\N}1(S_k<n\le F_k) \tag{6} \end{equation*} and hence \begin{equation*} P(Y_n\ne0\}=\sum_{k\in\N}P(S_k<n\le F_k). \tag{7} \end{equation*} Here and in what follows, $n$ and $k$ are natural numbers. Next, consider the duration \begin{equation*} D_k:=F_k-S_k \end{equation*} of the $k$th walk. Since the $R_i$'s are independent and independent of the $T_j$'s, the r.v.'s $D_1,D_2,\dots$ are independent and independent of the $T_j$'s, and the $T_j$'s are also independent. So, the r.v.'s $T_1,D_1,T_2,D_2,\dots$ are independent. Also, \begin{equation*} S_k=T_1+\sum_{j=2}^k(D_{j-1}+T_j). \tag{8} \end{equation*} So, $S_k$ and $D_k$ are independent and hence
\begin{equation*} P(S_k<n\le F_k)=\sum_{d\in\N}P(D_k=d)P(S_k<n\le S_k+d). \end{equation*} Using (8) and the independence of $T_1,D_1,T_2,D_2,\dots$, for all $d\in\N$ we have \begin{equation*} P(S_k<n\le S_k+d)= P(n-d\le S_k<n)\le\sup_{m\in\Z} P(m-d\le T_k<m) =\sum_{t=1}^d p_kq_k^{t-1}. \end{equation*} So, \begin{equation*} \begin{aligned} P(S_k<n\le F_k)&\le\sum_{d\in\N}P(D_k=d)\sum_{t=1}^d p_kq_k^{t-1} \\ &=\sum_{t\in\N}^d p_kq_k^{t-1}\sum_{d=t}^\infty P(D_k=d) \\ &=\sum_{t\in\N}^d p_kq_k^{t-1}P(D_k\ge t) \\ &=\sum_{t\in\N}^d p_kq_k^{t-1}P(D_1\ge t) \\ &\le\sum_{t\in\N} p_kq_k^{t-1}ct^{-1/2}, \end{aligned} \end{equation*} since, by (say) the reflection principle, $P(D_1\ge t)\le ct^{-1/2}$ for $t\in\N$. Here and in what follows, $c$ denotes various universal positive real constants. Therefore and because $0<p_k<1/2$, \begin{equation*} \begin{aligned} P(S_k<n\le F_k)&\le 2c\sum_{t\in\N} p_k(1-p_k)^t t^{-1/2} \\ &\le 2cp_k \sum_{t\in\N} e^{-p_k t}t^{-1/2} \\ &\le 2cp_k \int_0^\infty e^{-p_k t}t^{-1/2}\,dt =cp_k^{1/2}. \end{aligned} \tag{9} \end{equation*}