betaFeedback

WorksMathematics

Characterisation of first passage locations for two-dimensional lattice random walks

Abstract

Consider a diagonal random walk (Xn,Yn)(X_n,Y_n) on Z2\mathbb{Z}^2 with transition probabilities depending only on the second coordinate. We characterise the distributions of first passage locations, X(τa)X(τ_a), where τaτ_a is the first time YnY_n reaches level aa. We obtain a necessary and sufficient condition for a given distribution to be realised as a rescaled first passage location from some starting level. The proof extends Bondesson's method for one-dimensional first passage times. It combines a transformation of generating functions based on Pick functions with a construction using barriers. We also study maximal representations of generating functions of first passage locations and show that analogous converse results for standard and honeycomb random walks require additional restrictions.

Introduction

Main results

Let (Xn)(X_n) be a discrete-time random walk on Z\mathbb{Z} with jumps ±1\pm1. Assume that the probabilities of jumps depend only on the current position of the walk. By τ0=min⁡{n≥0:Xn=0}\tau_0 = \min\{n \ge0 : X_n = 0\} we denote the first passage time to 0. The classical result of Bondesson [1] states that if the random walk starts from x∈Nx \in\mathbb{N}, then τ0\tau_0 has the same distribution as x+2(X+Y)x + 2(X+Y), where XX has a distribution given by a mixture of geometric distributions and YY, independent of XX, is a sum of at most ⌊(x−1)/2⌋\lfloor(x-1)/2\rfloor geometrically distributed random variables. Bondesson also proved the converse: for every distribution described above, there is a random walk such that τ0\tau_0 restricted to {τ0<∞}\{\tau_0 < \infty\} has the same distribution as x+2(X+Y)x + 2(X+Y).

In this paper we study the two-dimensional variant of this setting. We consider a two-dimensional random walk (Xn,Yn)(X_n,Y_n) on Z2\mathbb{Z}^2. Our process moves diagonally, with jumps (±1,±1)(\pm1,\pm1). We additionally assume that the transition probabilities depend only on the current level YnY_n of the process. If τ0=min⁡{n≥0:Yn=0}\tau_0 = \min\{n \ge0 : Y_n = 0\} is the first passage time to a level 0, the random variable X(τ0)X(\tau_0) is called the first passage location. Note that if the walk moves only to the right and X0=0X_0 = 0, then X(τ0)=τ0X(\tau_0)=\tau_0 and Bondesson’s setting is recovered.

In [9], a convolution representation of the first passage location distribution was obtained. More precisely, it was proved that if the random walk starts from (0,y)(0,y) and y≥0y \ge0, then (X(τa)−y)/2(X(\tau_a)-y)/2 restricted to {τ0<∞}\{\tau_0 < \infty\} has a distribution given by a convolution of geometric sequences, reflected geometric sequences, reflected two-point sequences and an AM-CM\mathcal{AM\text{-}CM} (absolutely monotone-then-completely monotone) sequence (see Theorem 1.1 in [9]). The class of AM-CM\mathcal{AM\text{-}CM} sequences can be considered as a two-sided analogue of mixtures of geometric distributions (for details, see § 3). This raises the converse question of which distributions with this convolution structure can be realised by a diagonal random walk.

In this paper, we extend Bondesson’s method to the two-dimensional setting and prove the following characterisation theorem.

Theorem 1.1. Let

F(x)=G(x)∏k=1A1−qk1−qkx∏k=1B1−rk1−rkx−1∏k=1C(1−βk+βkx−1).(1)F(x)=G(x)\prod_{k=1}^{A}\frac{1-q_k}{1-q_kx}\prod_{k=1}^{B}\frac{1-r_k}{1-r_kx^{-1}}\prod_{k=1}^{C}(1-\beta_k+\beta_kx^{-1}). \tag*{(1)}

where

  • GG is a generating function of an AM\mathcal{AM}-CM\mathcal{CM} sequence with G(1)≤1G(1)\le1;

  • qk,rk∈(0,1), βk∈(0,1]q_k,r_k\in(0,1),\ \beta_k\in(0,1];

  • A,B,CA,B,C are nonnegative integers.

If B≤CB\le C, then there is y∈Ny\in\mathbb{N} and a diagonal random walk (Xn,Yn)(X_n,Y_n) starting from (0,y)(0,y) such that

F(x)=E(0,y)[x(X(τ0)−y)/21τ0<∞](2)F(x)=\mathbb{E}^{(0,y)}\left[x^{(X(\tau_0)-y)/2}\mathbb{1}_{\tau_0<\infty}\right] \tag*{(2)}

for ∣x∣=1|x|=1. One can take y=2A+B+C+1y=2A+B+C+1.

Conversely, every nonzero generating function of the form (1.2) admits a representation of the form (1.1) with B≤CB\le C.

In the proof of the first part of the theorem we construct an appropriate random walk. Following Bondesson’s approach, we introduce a barrier at level y−1y-1, preventing the walk from returning to level yy after its first visit to level y−1y-1. This allows us to construct the upper and lower parts of the walk separately. On levels n≥yn\ge y, we realise the AM\mathcal{AM}-CM\mathcal{CM} factor by iterating a transformation of AM\mathcal{AM}-CM\mathcal{CM} generating functions. On levels n<yn<y, we realise all geometric factors using two-level blocks separated by further barriers. Condition B≤CB\le C reflects the use of the two-point factors in this construction. The remaining C−BC-B two-point factors can be realised with simple one-level blocks.

Bondesson’s theorem for one-dimensional random walks can be recovered from our result. If FF is given by (1.1) with GG being the generating function a one sided AM\mathcal{AM}-CM\mathcal{CM} sequence (hence, a completely monotone sequence) and B=C=0B=C=0, then the condition B≤CB\le C is satisfied automatically. Our construction gives pn,2=pn,3=0p_{n,2}=p_{n,3}=0 for every n∈Nn\in\mathbb{N}. Hence, one can find a random walk (Xn,Yn)(X_n,Y_n) which starts from some (0,2A+1)(0,2A+1) and moves only to the right (with NE and SE jumps). Consequently, we have X(τ0)=τ0X(\tau_0)=\tau_0 and Theorem 2 in [1] is recovered.

In the proof of the second part of Theorem 1.1 (see (47)), we actually prove sharper bounds on the number of geometric factors in Theorem 1.1 in [9]. We state this result below.

Theorem 1.2 (Extension of Theorem 1.1 in [9]). Let (Xn,Yn)(X_n,Y_n) be a diagonal starting from (0,y)(0,y), where y≥1y\ge1, such that P(τ0<∞)>0\mathbb{P}(\tau_0<\infty)>0. The distribution of (X(τ0)−y)/2(X(\tau_0)-y)/2 restricted to {τ0<∞}\{\tau_0<\infty\} is given by a convolution of

  • AA geometric sequences,

  • BB reflected geometric sequences,

  • at most yy reflected two-point sequences,

  • an AM\mathcal{AM}-CM\mathcal{CM} sequence,

where Ky=⌊(y−1)/2⌋K_y=\lfloor(y-1)/2\rfloor and A,BA,B are nonnegative integers such that

A≤min⁡{Ky,∑k=2y−11pk,4>0},A\le\min\left\{K_y,\sum_{k=2}^{y-1}\mathbb{1}_{p_{k,4}>0}\right\},
B≤min⁡{Ky,∑k=2y−11pk,3>0}.B\le\min\left\{K_y,\sum_{k=2}^{y-1}\mathbb{1}_{p_{k,3}>0}\right\}.

Remark 1.3. Theorems 1.1 and 1.2 have a symmetric counterpart. If we consider the reflected random walk (X~n,Y~n)=(−Xn,Yn)(\widetilde{X}_n,\widetilde{Y}_n)=(-X_n,Y_n) and normalise (X~(τ0)+y)/2(\widetilde{X}(\tau_0)+y)/2, then the corresponding characteristic function is F~(x)=F(x−1)\widetilde{F}(x)=F(x^{-1}). Since G(x−1)G(x^{-1}) is again a generating function of an AM\mathcal{AM}-CM\mathcal{CM} sequence, (1.1) reads

F~(x)=G~(x)∏k=1A1−qk1−qkx−1∏k=1B1−rk1−rkx∏k=1C(1−βk+βkx).\widetilde{F}(x)=\widetilde{G}(x)\prod_{k=1}^{A}\frac{1-q_k}{1-q_kx^{-1}}\prod_{k=1}^{B}\frac{1-r_k}{1-r_kx}\prod_{k=1}^{C}(1-\beta_k+\beta_kx).

With the notation above, the sufficient condition remains B≤CB \le C, and one can still take y=2A+B+C+1y = 2A + B + C + 1. After relabelling the numbers of geometric and reflected geometric factors as AA and BB, respectively, these become A≤CA \le C and y=A+2B+C+1y = A + 2B + C + 1. In the reflected version of Theorem 1.2, the reflected two-point sequences are replaced by two-point sequences supported on {0,1}\{0,1\}. The bounds on the relabelled numbers AA and BB remain in their original form when expressed in terms of the reflected transition probabilities.

References

  1. [1]L. Bondesson. A characterization of first passage time distributions for random walks. Stochastic Processes and their Applications, 39(1):81–88, 1991.DOI
  2. [2]W. F. j. Donoghue. Monotone matrix functions and analytic continuation, volume 207 of Grundlehren Math. Wiss. Springer, Cham, 1974.
  3. [3]M. Kwaśnicki. A new class of bell-shaped functions. Trans. Am. Math. Soc., 373(4):2255–2280, 2020.
  4. [4]M. Kwaśnicki and T. Simon. Characterisation of the class of bell-shaped functions. Math. Z., 301(3):2659–2683, 2022.
  5. [5]M. Kwaśnicki and J. Wszoła. Two-sided bell-shaped sequences. Math. Z., 311(3), 2025.arxiv.org/abs/2404.11274
  6. [6]M. Kwaśnicki and J. Wszoła. Generalised eigenvector expansion of infinite Toeplitz matrices with absolutely/completely monotone entries, 2026. arXiv:2606.01986.arxiv.org/abs/2606.01986
  7. [7]R. Remmert. Classical topics in complex function theory. Transl. by Leslie Kay, volume 172 of Grad. Texts Math. New York, NY: Springer, 1998.
  8. [8]J. Wszoła. Eigenvalues of Hermitian Toeplitz matrices with Fisher–Hartwig symbols, 2026. arXiv:2610.01498.
  9. [9]J. Wszoła. First passage locations for two-dimensional lattice random walks and the bell-shape. Electron. J. Probab., 31:28, 2026. Id/No 44.arxiv.org/abs/2501.14393

Paper details

vlnc:W_6r6v64rd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex

View statement
Looking for related papers…
Contents