Two-dimensional Rademacher walk

Satyaki Bhattacharya, Stanislav Volkov · 2025

Read Two-dimensional Rademacher walk by Satyaki Bhattacharya, Stanislav Volkov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16259.txt.

Introduction

Satyaki Bhattacharya and Stanislav Volkov set a random walk loose on the two-dimensional grid and ask when it keeps coming home. The Rademacher walk takes steps in the four compass directions with equal chance, but the size of the nth step is fixed in advance by a chosen sequence of whole numbers. Their 2025 paper generalizes a one-dimensional walk the pair introduced earlier.

Whether such a walk is recurrent, returning to its start endlessly, or transient, wandering off for good, depends on the step-size sequence. The authors establish general conditions deciding between the two fates. A footnote carries real weight: in three dimensions and above, the same walk is always transient, a fact they cite from related work, which makes the two-dimensional case the true borderland. The paper maps parts of that border with conditions other walk theorists can apply.

Catalog record

CREATORSatyaki Bhattacharya, Stanislav Volkov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16259

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Two-dimensional Rademacher walk Satyaki Bhattacharya, Stanislav Volkov Abstract We study a generalisation of the one-dimensional Rademacher random walk introduced in [ 2 ] to ℤ 2 \mathbb{Z}^{2} (for d ≥ 3 d\geq 3 , the Rademacher random walk is always transient, as follows from Theorem 8.8 in [ 4 ] ). This walk is defined as the sum of a sequence of independent steps, where each step goes in one of the four possible directions with equal probability, and the size of the n n th step is a n a_{n} where { a n } \{a_{n}\} is a given sequence of positive integers. We establish some general conditions under which the walk is recurrent, respectively, transient. Keywords : recurrence, transience, Rademacher distribution, non-homogeneous Markov chains. AMS subject classification : 60G50, 60J10. 1 Introduction A one-dimensional Rademacher walk was introduced in [ 2 ] , as a generalisation of a simple symmetric random walk on \mathbb{Z} with step sizes following some pre-determined sequence of integers a_{1},a_{2},\dots (as opposed to all step sizes being one). It was shown that this walk is recurrent for some very slowly growing sequences, and transient, for example, if a_{k}=\lfloor k^{\gamma}\rfloor for all \gamma>0 . Some further generalisations of the Rademacher walk with non-integer step sizes were also considered, and they were studied further in [ 1 ] . This paper studies the extension of the walk to higher dimensions. We say that \xi has a two-dimensional Rademacher distribution , if \xi takes one of the values \{\mathrm{e}_{1},\mathrm{e}_{2},-\mathrm{e}_{1},-\mathrm{e}_{2}\} where \mathrm{e}_{1}=(0,1) , \mathrm{e}_{2}=(1,0) are the unit vectors in \mathbb{R}^{2} with equal probability 1/4 . Let \xi_{n} , n=1,2,\dots be a sequence of i.i.d. two-dimensional Rademacher random variables. Let a_{n} be a deterministic sequence of positive real numbers. The two-dimensional Rademacher walk is defined as S_{n}=Z_{1}+Z_{2}+\dots+Z_{n} where Z_{i}=a_{i}\xi_{i} . Definition 1 . We say that the walk S_{n} is transient if \|S_{n}\|\to\infty a.s. We say that the walk S_{n} is recurrent, if S_{n}=z for infinitely many n s a.s., for each z\in\mathbb{Z}^{2} . Note that the transience and recurrence are zero-one events. Also, in general, we do not have the dichotomy between recurrence vs. transience; for example, if all a_{n}\equiv 2 then the walk is neither recurrent nor transient according to our definition, as it returns to the origin (further denoted by \mathbf{0}=(0,0) ) infinitely often and yet never visits points with odd coordinates. We study the conditions for transience in Section 2 and for recurrence in Section 3 . 2 Transience 2.1 Non-decreasing steps Theorem 1 . Suppose that a_{n} is a non-decreasing sequence of integers converging to infinity (i.e. a_{n}\uparrow\infty ). Then S_{n} is transient. First, we prove a necessary technical result. Lemma 1 . Let d_{1},d_{2},d_{3}\dots be a sequence of distinct positive integers, and let T_{k}=d_{1}\varepsilon_{1}+\dots+d_{k}\varepsilon_{k} where \varepsilon_{i} are i.i.d. Rademacher. Then for every integer \displaystyle m\geq\max_{1\leq i\leq k}d_{i} and M\in\{0,1,\dots,m-1\} we have \mathbb{P}(T_{k}=M\,\mathrm{mod}\ m)\leq\frac{C\log k}{k} for some universal constant C>0 . Proof. By the result of [ 6 ] , for each z\in\mathbb{Z} we have \mathbb{P}(T_{k}=z)\leq\frac{C_{1}}{k^{3/2}} . On the other hand, by Hoeffding’s inequality \mathbb{P}(|T_{k}|\geq m\sqrt{2k\log k})\leq 2\exp\left(-\frac{4\,m^{2}\,k\,\log k}{4d_{1}^{2}+\dots+4d_{k}^{2}}\right)\leq 2\exp(-\log k)=\frac{2}{k}. Consequently, \displaystyle\mathbb{P}(T_{k}=M\,\mathrm{mod}\ m) \displaystyle\leq\mathbb{P}(T_{k}=M\,\mathrm{mod}\ m,|T_{k}|<m\sqrt{2k\log k})+\mathbb{P}(|T_{k}|\geq m\sqrt{2k\log k}) \displaystyle\leq\mathbb{P}(T_{k}=M+\ell d_{k+1}\text{ for some $\ell\in\mathbb{Z}$ s.t. }|M+m\ell|<m\sqrt{2k\log k})+\frac{2}{k} \displaystyle\leq\frac{1+2m\sqrt{2k\log k}}{m}\sup_{z\in\mathbb{Z}}\mathbb{P}(T_{k}=z)+\frac{2}{k}\leq\frac{3m\sqrt{k\log k}}{m}\times\frac{C_{1}}{k^{3/2}}+\frac{2}{k} \displaystyle=\frac{3C_{1}\sqrt{\log k}}{k}+\frac{2}{k}\leq\frac{C\log k}{k} for C=3C_{1}+2>0 . ∎ Proof of Theorem 1 . Let b_{1}=a_{1}\geq 1 , b_{2}=\min\{a_{n}:a_{n}>b_{1}\}\geq a_{1}+1 , b_{3}=\min\{a_{n}:a_{n}>b_{2}\}\geq a_{2}+1 , etc. Denote by m_{i}=\card\{n:\ a_{n}=b_{i}\} , i=1,2,\dots . Then the sequence \{a_{n}\} can be represented as \underbrace{b_{1},b_{1},\dots b_{1},}_{m_{1}}\underbrace{b_{2},b_{2},\dots b_{2},}_{m_{2}}\underbrace{b_{3},b_{3},\dots b_{3},}_{m_{3}}\dots\underbrace{b_{j},b_{j},\dots b_{j},}_{m_{j}}b_{j+1},\dots. Let k_{j+1}=m_{1}+m_{2}+\dots+m_{j}+1=\inf\{n:\ a_{n}=b_{j+1}\} be the first index of the sequence \{a_{n}\} equal to b_{j+1} . Let \kappa_{i}=1 if \xi_{i}\in\{\mathrm{e}_{1},-\mathrm{e}_{1}\} and =0 otherwise. Let \varepsilon_{i}=\pm 1 equal to the non-zero coordinate of \xi_{i} , Then \{\kappa_{i}\} are i.i.d. Bernoulli and \{\varepsilon_{i}\} are i.i.d. Rademacher; moreover, these two sequences are independent. The values of i\in\{1,2,\dots,n\} for which \kappa_{i}=1 ( =0 resp.) correspond to horizontal (vertical, resp.) steps. Formally, let H_{n}=\{1\leq i<n:\ \kappa_{i}=1\},\quad V_{n}=\{1\leq i<n:\ \kappa_{i}=0\} be the indices corresponding to horizontal (resp. vertical) steps. Note that Z_{i}=X_{i}\mathrm{e}_{1}+Y_{i}\mathrm{e}_{2} where X_{i}=\begin{cases}a_{i}\varepsilon_{i},&\text{if }\kappa_{i}=1;\\ 0,&\text{if }\kappa_{i}=0\end{cases}\qquad Y_{i}=\begin{cases}0,&\text{if }\kappa_{i}=1;\\ a_{i}\varepsilon_{i},&\text{if }\kappa_{i}=0,\end{cases} and denote S_{n}=S^{X}_{n}\mathrm{e}_{1}+S^{Y}_{n}\mathrm{e}_{2}\quad\text{ where }S_{n}^{X}=X_{1}+\dots+X_{n},\quad S_{n}^{Y}=Y_{1}+\dots+Y_{n}. Fix a large integer j and let A_{j}=\left\{\card\{b_{i},i\in H_{k_{j}}\}<\frac{j}{3}\text{ \ or \ }\card\{b_{i},i\in V_{k_{j}}\}<\frac{j}{3}\right\}. For each 1\leq i<k_{j} , \kappa_{i} equals 0 or 1 with equal probability \frac{1}{2} . Hence, by Hoeffding’s inequality, there exists a constant c_{0} such that \mathbb{P}(A_{j})\leq 2e^{-c_{0}j}, i.e., there are at least j/3 horizontal and j/3 vertical steps with probability very close to one. As a result, on A_{j}^{c} , we can write S^{X}_{k_{j}-1}=\sum_{i=1}^{h_{j}}b^{\prime}_{i}\varepsilon^{\prime}_{i},\quad S^{Y}_{k_{j}-1}=\sum_{i=1}^{v_{j}}b^{\prime\prime}_{i}\varepsilon^{\prime\prime}_{i} where h_{j}=\card\{H_{k_{j}-1}\} , v_{j}=\card\{V_{k_{j}-1}\} , the positive integer sequences \{b_{i}^{\prime}\}_{i=1}^{h_{j}} and \{b_{i}^{\prime\prime}\}_{i=1}^{v_{j}} are non-decreasing and each has at least j/3 distinct elements, while \varepsilon_{i}^{\prime},\varepsilon_{i}^{\prime\prime} are i.i.d. Rademacher. Now, by Lemma 1 , \displaystyle\mathbb{P}(S^{X}_{k_{j}-1}=0\,\mathrm{mod}\ b_{j+1}\mid A_{j}^{c})\leq\frac{C\log(j/3)}{j/3},\qquad\mathbb{P}(S^{Y}_{k_{j}-1}=0\,\mathrm{mod}\ b_{j+1}\mid A_{j}^{c})\leq\frac{C\log(j/3)}{j/3} and, moreover, conditioned on the sequence \kappa_{i} and A_{j}^{c} , the events above are independent. Since for the walk to hit \mathbf{0} at time n , k_{j+1}\leq n\leq k_{j+2}-1 , we need that both its coordinates are divisible by b_{j} at time k_{j}-1 , we have \displaystyle\mathbb{P}(S_{n}=\mathbf{0}\text{ for some }n\in[k_{j+1},k_{j+2}))\leq\mathbb{P}(A_{j})+\left(\frac{C\log(j/3)}{j/3}\right)^{2}=O\left(\frac{\log^{2}j}{j^{2}}\right). (1) Since the quantity in ( 1 ) is summable in j , by the Borel-Cantelli lemma we conclude that the event \{S_{n}=\mathbf{0}\} occurs finitely often. By the same token, we get that \{S_{n}={\bf w}\} occurs finitely often for each {\bf w}\in\mathbb{Z}^{2} . Hence the transience follows. ∎ 2.2 Transience for non-integerer sequences \{a_{n}\} In this section, we allow a_{n} to take any positive real values (not only integers). We will use the same Definition 1 for the transience of the walk. Definition 2 . Let a_{n}\in\mathbb{R}_{+} , n=1,2,\dots . We call the sequence \{a_{n}\} good, if for each large n there is a positive integer K_{n} such that \frac{K_{n}}{\log_{2}a_{n}}\to 1\text{ as }n\to\infty, and a subset of \{1,2,\dots,n\} with K_{n} distinct elements, say \{i_{1},i_{2},\dots,i_{K_{n}}\} , such that i_{K_{n}}\equiv n and a_{i_{k+1}}\geq 2a_{i_{k}} for every k=1,2,\dots,K_{n}-1 . Later in the Section, in Proposition 1 , we present a sufficient condition for a sequence to be good. Definition 3 . Let r,s\geq 1 be some constants. We call the sequence \{a_{n}\} (r,s) -monotone, if for all large n we have a_{n}\leq sa_{m} whenevever m\geq rn . Remark 1 . Note that the case r=s=1 corresponds in the above definition to the monotonicity in the usual sense. Theorem 2 . Assume that the sequence a_{n} is good and (r,s) -monotone, and for some \epsilon>0 we have a_{n}\geq(\log n)^{1/2+\epsilon} for all sufficiently large n . Then the two-dimensional Rademacher walk is transient. Proof. To show transience, it suffices to show that for each (x,y)\in R^{2} we have S_{n}\in(x,x+1)\times(y,y+1) for at most finitely many n s a.s. W.l.o.g. we can assume that a_{n}>1 for all n (this is, of course, true for all large n due to the assumption of the theorem, and a few initial values of the sequence \{a_{n}\} do not affect transience). The proof will follow an argument involving anti-concentration inequalities on two different scales, similarly to the method used in [ 1 ] . Define the event \displaystyle A_{n}=\{ The walk makes at least n/5 horizontal and n/5 vertical steps \displaystyle\text{among the last $n/2$ steps of the $n$--step walk}\} By Hoeffding’s inequality, it is easy to check that \mathbb{P}(A_{n}^{c})\leq 2e^{-0.01n} . Let T_{m} be a

Read the complete text