# Large and moderate deviations in Poisson navigations

Partha Pratim Ghosh, Benedikt Jahnel, Sanjoy Kumar Jhawar

► To cite this version:

Partha Pratim Ghosh, Benedikt Jahnel, Sanjoy Kumar Jhawar. Large and moderate deviations in Poisson navigations. 2024. hal-05051110

HAL Id: hal-05051110

https://inria.hal.science/hal-05051110v1

Preprint submitted on 29 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
LARGE AND MODERATE DEVIATIONS IN POISSON NAVIGATIONS

PARTHA PRATIM GHOSH, BENEDIKT JAHNEL, AND SANJOY KUMAR JHAWAR

ABSTRACT. We derive large- and moderate-deviation results in random networks given as planar directed navigations on homogeneous Poisson point processes. In this non-Markovian routing scheme, starting from the origin, at each consecutive step a Poisson point is joined by an edge to its nearest Poisson point to the right within a cone. We establish precise exponential rates of decay for the probability that the vertical displacement of the random path is unexpectedly large. The proofs rest on controlling the dependencies of the individual steps and the randomness in the horizontal displacement as well as renewal-process arguments.

*Key words and phrases.* traffic network; directed-navigation; Poisson point process; renewal process; moderate-deviation principle; large-deviation principle.

*AMS 2020 Subject Classifications.* Primary: 60D05, 60G70. Secondary: 60G55, 05C80.

# 1. INTRODUCTION

We consider decentralized traffic-flow networks or drainage networks, where nodes transmit data individually to dedicated neighboring nodes according to local rules, or respectively liquid flows towards a certain direction. For this, directed navigations on homogeneous Poisson point processes in the Euclidean plane can be used as an underlying network model [3,5]. The traffic generated at each node is forwarded iteratively to the nearest node for example to the right in horizontal direction. While analyzing such models, it has been observed in [9], that the spatial traffic-flow density at a given location in the domain, i.e., the spatial average of accumulated traffic at a microscopic area around that point, follows a law of large numbers in the high-density limit. Here, the asymptotic traffic density can be captured as an integral in terms of the spatial intensity of the point process along with their rate of traffic generation. The bulk contribution in the limit in this asymptotics comes from the traffic generated within a thin horizontal strip at that given point due to sub-ballisticity of the trajectory of the navigation. This sub-ballistic behavior is nothing but a version of the straightness condition studied in [11].

Going beyond sub-ballisticity and the law of large numbers, questions about the deviation behavior of paths in the traffic network arise. In a stationary setting, is it rare to have a path originating from the origin to deviate much away from the horizontal axis? For this, we denoted by $Y_t$ the vertical position of the path measured as a function of horizontal position $t$. If the answer to the question is no, then essentially these paths are not so unlikely to miss the microscopic region around a given location and the traffic accumulated along the path may not contribute to the aggregated traffic at the location of interest. This in turn would lead to deviations in the throughput at the target location and it is an indication of unexpected network performance. On the other hand, if the answer is yes, that means that the paths do not deviate too much and contribute to the bulk of the throughput. But how rare is the deviation event? In other words, at what scale does the probability of such an event live on and what are the rates? To answer this sort of questions, in this article, we investigate the large- and moderate-deviation behavior of the deviation of these paths away from the horizontal axis in a Poisson navigation model where the consecutive successors are defined as the closest neighbor within a cone to the right of the current point in the Euclidean plane.

Date: March 26, 2024.
Large- and moderate-deviation principles constitute a corner stone in the analysis of random geometric models and in general in stochastic processes in the last four to five decades, well-documented for example in [7, 10, 16]. These principles essentially capture rare events by quantifying their asymptotic unlikelihood. The small probability of the events is expressed in terms of an exponential rate and a rate function. In the context of telecommunication networks, large-deviation principles can be used to point out how badly the network is performing and what the most prominent reasons for this behavior are. The large-deviation principle has been studied for many different telecommunication network models, mainly identifying poor service indicator, see for example [12, Chapter 6] and references therein. On the other hand, moderate deviations are nothing but large deviations with a slower scaling. The moderate-deviation principle for a sequence of iid centered random variables has been studied for example in [8] as a much cleaner and shorter version of [1] and for sequences of random variables from Banach space in the classic work by [13]. In case of moderate deviations, the rate function turns out to be of Gaussian type irrespective of the model under consideration, whereas in large deviations the rate function depends on characteristics of the random variables.

The model we study in this article is the underlying setup for the traffic-flow network mentioned above. It is known as a *navigation* on Poisson point processes in Euclidean space and specifically the directed and radial navigation where introduced in [5]. However, we introduce an additional parameter $0 < \theta < \pi/2$ that controls the angle of the cone in which the navigation searches for the next neighbor. By definition, if the navigation starts at multiple points, this type of navigation gives rise to a tree structure. In application to telecommunication networks, the root of the spanning trees can be seen as a network head where all the information is gathered along the edges of the tree and processed. Hence, it is worthwhile to know the local and global structural properties of the tree. In the work [3], the quantities of interest were the local tree functionals around a vertex, for example, the degree, properties of the path in the tree from a vertex to the root, namely the total length or properties of the tree structure and its shape. In a somewhat more geometric and analytical work, the convergence of the tree to a Brownian web under the appropriate scaling limit has been studied in [6] and in [15] for the Poisson setting and in a recent work [14] for a discrete setting on perturbed lattice. In this manuscript, we in particular improve the polynomial-decay properties in [3, Lemma 4.11] to stretched-exponential decay of moderate-deviation type as well as go beyond the associated central limit theorem [3, Theorem 4.7]. Let us also mention the work [4] where navigation characteristics are investigated in a high-density regime for not necessarily homogeneous Poisson point processes.

When $\pi/4 < \theta < \pi/2$, the model of navigation possesses a challenging dependence structure along its path, since each step of the navigation carries an extra piece of information from the previous steps via non-trivial regions that have been observed as void spaces for the underlying Poisson point process. We call this piece of information the *history set* and identify the steps where the history set is empty. This is only possible since $\theta < \pi/2$ and gives rise to a renewal structure that is essential for our analysis. However, the tail properties of the step variables of the renewal process are challenging to analyse, which makes up for the bulk of the technical part of the manuscript. For this, we control the exponential decay of the inter-stopping time gaps via bounds on the dynamics of the width of the history set, using Markov-chain comparison ideas from [6, Proposition 3.1]. However, this control fails to be sufficiently detailed in order to establish the large deviations in the whole parameter regime. Indeed, the model becomes substantially simpler for $\theta \in (0, \pi/4]$ as the steps become iid and we can then provide the full large- and moderate-deviation analysis with rather explicit rate functions.

Organization of the article: In the following Section 2, we describe the model in detail, state the main results about large and moderate-deviation principles and the scaling property of the rate functions with respect to the intensity of the Poisson point process. In Section 3, we first uncover the hidden independence structure in the model and state the key supporting results that enables us to prove the main result for the moderate deviations as well as the large-deviation
result in the restricted parameter setting. Section 4 contains the proofs of all the supporting results that are stated in Section 3 and the large-deviation principle for $0 < \theta \le \pi/4$. The large-deviation principle in the dependent case, i.e., $\pi/4 < \theta < \pi/2$, is presented in Appendix 5 and proved under a key assumption for the tail behavior of the renewal-step variables.

## 2. SETTING AND MAIN RESULTS

Let $\mathcal{P}_\lambda$ denote the homogeneous Poisson point process with intensity $\lambda > 0$ on $\mathbb{R}^2$ and consider an additional point $o$ at the origin such that $\mathcal{P}_\lambda \cup \{o\}$ is the Poisson point process under its Palm distribution $\mathbb{P}$. We are interested in the large and moderate deviations of a dependent sequence of waypoints, starting at $o$, that are defined iteratively by choosing a successor point, which is the closest Poisson point towards the right within a cone. More precisely, for any $v \in \mathbb{R}^2$, let $(r_v, \varphi_v) \in \mathbb{R} \times [-\pi, \pi)$ denote its polar coordinates, with the first unit vector $e_1$ corresponding to the polar coordinates $(1, 0)$, and consider

$$C_{\theta} := \{v = (r_v, \varphi_v) : r_v > 0, |\varphi_v| \le \theta\},$$

the cone with angle $2\theta$ centered at the origin. For $0 \le \theta \le \pi/2$, we might say that the cone is facing towards the right. For any $v \in \mathbb{R}^2$ we write $C_{\theta}(v) := v + C_{\theta}$ and $C_{\theta}^{o}(v)$ for the interior of $C_{\theta}(v)$. Then, we consider the following family of navigations based on the usual Euclidean metric $|\cdot|$ in $\mathbb{R}^2$.

**Definition 1 (Navigations).** Let $V_0 = o$. Then, we call $\mathcal{V} := \{V_n\}_{n \ge 0} \subset \mathcal{P}_\lambda$, iteratively defined as

$$V_{i+1} := \underset{i \in \mathcal{P}_\lambda \cap C_{\theta}(V_i)}{\operatorname{argmin}} \{|v - V_i| : v \in \mathcal{P}_\lambda \cap C_{\theta}(V_i)\},$$

a *directed-$\theta$-navigation*. $V_{i+1}$ is denoted the *successor* of $V_i \in \mathcal{P}_\lambda$ and $U_i := V_i - V_{i-1}$ the $i$-th *progress* of the navigation.

Note that, under $\mathbb{P}$, the argmin is uniquely defined almost surely. We are interested in a continuous-time process based on the navigation $\mathcal{V}$. For this, consider $\bar{\mathcal{V}} := \bigcup_{k \ge 0} [V_k, V_{k+1}]$, the *interpolated trajectory* for the navigation, where $[V_k, V_{k+1}] \subset \mathbb{R}^2$ should be understood as the one-dimensional line segment that connects $V_k$ and $V_{k+1}$. Then, we can see the interpolated trajectory $\bar{\mathcal{V}}$ as a piece-wise affine and continuous path, parametrized with respect to time $t$ as, $\{(t, \mathcal{Y}_t)\}_{t \ge 0}$, where the parameter $t$ denotes the progress along the $x$-axis and $\mathcal{Y}_t \in \mathbb{R}$ is the corresponding $y$-coordinate or *vertical displacement* at time $t$. In particular, for $t = \pi_1(V_k)$, where $\pi_1$ denotes the projection to the first Cartesian coordinate, we have that $\mathcal{Y}_t = \pi_2(V_k)$, for every $k \ge 0$, where $\pi_2$ denotes the projection to the second Cartesian coordinate, see Figure 1 for an illustration. Our first main result is the *moderate-deviation principle* for $\mathcal{Y} = \{\mathcal{Y}_t\}_{t \ge 0}$.

**Theorem 1.** For any $0 < \lambda, 0 < \theta < \pi/2$ and $0 < \varepsilon < 1/2$, $\{t^{-1/2-\varepsilon}\mathcal{Y}_t\}_{t \ge 0}$ obeys the moderate-deviation principle with rate $t^{2\varepsilon}$ and rate function $I_{\lambda,\theta}(x) := \rho(\lambda, \theta)x^2$ where $\rho(\lambda, \theta) > 0$ satisfies the scaling relation $\rho(\lambda, \theta) = \sqrt{\lambda}\rho(1, \theta)$.

The constant $\rho(\lambda, \theta)$ can be generally expressed in a semi-explicit way, see (5) in Section 3. In case $0 < \theta \le \pi/4$, it is given by

$$\rho(\lambda, \theta) := \frac{\int_{0}^{\infty} dr r^2 \exp(-\lambda \theta r^2) \int_{-\theta}^{\theta} d\varphi \cos \varphi}{2 \int_{0}^{\infty} dr r^3 \exp(-\lambda \theta r^2) \int_{-\theta}^{\theta} d\varphi \sin^2 \varphi} = \frac{\sqrt{\pi \lambda \theta} \sin \theta}{2\theta - \sin(2\theta)}. \quad (1)$$

For all sufficiently small angles, we show that $\mathcal{Y}$ also satisfies the *large-deviation principle*. The rate function is given in terms of the multivariate rate function of iid progress variables defined in terms of the usual scalar product $\langle \cdot, \cdot \rangle$ in $\mathbb{R}^2$.
<figure><img src="image_2.png" /><figcaption>FIGURE 1. Simulated sample path of $\bar{V}$ for $\theta = \arctan(5)$.</figcaption></figure>

**Lemma 1.** Consider iid copies $\{\tilde{U}_i\}_{i \ge 1}$ of the progress variable $U_1 \in \mathbb{R}^2$ in the directed-$\theta$-navigation. Then, $\{n^{-1} \sum_{i=1}^n \tilde{U}_i\}_{n \ge 1}$ satisfies the large-deviation principle with rate $n$ and rate function

$$ \mathcal{I}_{\lambda, \theta}(u) := \sup\{\langle \gamma, u \rangle - J_{\lambda, \theta}(\gamma) : \gamma \in \mathbb{R}^2\}, $$

where, for all $\gamma \in \mathbb{R}^2$,

$$ J_{\lambda, \theta}(\gamma) := \log \left( \lambda \int_{0}^{\infty} dr r \exp(-\lambda \theta r^2) \int_{-\theta}^{\theta} d\varphi \exp(\gamma_1 r \cos \varphi + \gamma_2 r \sin \varphi) \right) < \infty. $$

Further, $u \mapsto \mathcal{I}_{\lambda, \theta}(u)$ is continuous on $\{u \in \mathbb{R}^2 : \mathcal{I}_{\lambda, \theta}(u) < \infty\} = C_{\theta}^o$.

We are now in the position to state our second main theorem.

**Theorem 2.** For any $0 < \lambda$ and $0 < \theta \le \pi/4$, $\{t^{-1}\mathcal{Y}_t\}_{t \ge 0}$ obeys the large-deviation principle with rate $t$ and rate function $I_{\lambda, \theta}(x) := \inf\{\beta\mathcal{I}_{\lambda, \theta}(1/\beta, x/\beta) : \beta > 0\}$ that satisfies the scaling relation $I_{\lambda, \theta} = \sqrt{\lambda}I_{1, \theta}$.

We believe that $\mathcal{Y}$ also satisfies the large-deviation principle for all $\pi/4 < \theta < \pi/2$, but with a substantially more involved rate function $I'_{\lambda, \theta}$. We establish this under some assumptions in Appendix 5.

### 3. STRATEGY OF PROOF

The proof of Theorem 2 is a consequence of Lemma 1 and step-wise independence in case of $\theta \le \pi/4$. We present the arguments in Section 4. Let us now focus on the moderate deviations. In general, the setting of Theorem 1 is more challenging since for $\theta > \pi/4$ we
do not see independence in every step. Indeed, in the case where $\theta = \pi/2$ we almost surely never see independence of a step from the previous steps. This is the reason, why we only consider the case where $\theta < \pi/2$. In this case, the navigation will occasionally make a step that is independent of the past. Conceiving the in-between steps as one segment, we re-enter a regime of independent segments for which we derive the moderate-deviation result. However, the distribution of the segments is hard to trace and has exponential tails. This is the main reason why we restrict ourselves to moderate deviations and only establish the large deviations under some assumptions on the segment distribution in Appendix 5.

To make this precise, we iteratively define a sequence of history sets. We set $H_0 = \emptyset$ and define

$$H_1 := C_{\theta}(U_1) \cap B(o, |U_1|),$$

where we recall that our navigation starts at the origin $o$. Here, $B(x, r)$ denotes the open ball with radius $r$ centered at $x \in \mathbb{R}^2$. In words, the history set at step 1 is given by the region that lies both, in the (potential) future of the first waypoint $V_1 = U_1$ and in the void space that is responsible for finding the first waypoint. Note that $H_1 = \emptyset$ whenever $0 \le \theta \le \pi/4$. For all larger $n$, we define

$$H_n := C_{\theta}(V_{n-1} + U_n) \cap \{H_{n-1} \cup B(V_{n-1}, |U_n|)\},$$

the region in the future of the $n$-th waypoint that intersects the joint history. One way to look at the history set $H_n$ is to realize that this is the region where, for the next step, we already know that a certain part of space is already empty of points since we already searched for points there in the previous steps.

Based on our history sets, we define $\tau_0^\theta = 0$ and

$$\tau_1^\theta := \inf\{n > 0: H_n = \emptyset\},$$

to be the first step where there is no history. For $k > 1$,

$$\tau_k^\theta := \inf\{n > \tau_{k-1}^\theta: H_n = \emptyset\},$$

is the $k$-th step where the history set is empty. Note that the inter-stopping time gaps $\{\tau_k^\theta - \tau_{k-1}^\theta\}_{k \ge 1}$ are iid random variables due to the total independence of the underlying Poisson point process. In particular, $\tau_k^\theta = k$ almost surely, whenever $0 < \theta \le \pi/4$. We will later verify that $\tau_1^\theta$ is almost-surely finite and has exponential tails. As anticipated, we now build segments

$$U'_i := \sum_{j=\tau_{i-1}^\theta+1}^{\tau_i^\theta} U_j$$

and note that the sequence $\{U'_i\}_{i \ge 1}$ is iid, again due to the total independence of the underlying Poisson point process. Further, let us denote the number of steps before hitting time $t$ by

$$K_t := \sup \{n > 0: \sum_{i=1}^{n} X_i < t\}.$$

Based on our hitting times, we now define

$$K'_t := \sup\{n > 0: \tau_n^\theta \le K_t\}, \qquad (2)$$

as the index of the largest stopping time before $K_t$. In particular, we can also consider the vertical displacement there as

$$\mathcal{Y}'_t := \sum_{i=1}^{K'_t} Y'_i,$$

where $U'_i = (X'_i, Y'_i)$. Let us start by noting that $U'_1$ possesses some exponential moments.

**Lemma 2.** For some $\gamma = (\gamma_1, \gamma_2)$ with $\gamma_1, \gamma_2 > 0$, we have that $\mathbb{E}[\exp(\langle \gamma, U'_1 \rangle)] < \infty$.
We present the proof and all other proofs in this section later in Section 4. In the Appendix 5, roughly speaking, we will make the assumption that $U'_1$ obeys a large-deviation principle, which is the critical input in order to establish the large-deviation principle for $\mathcal{Y}_t$ with $\pi/4 < \theta < \pi/2$.

For the moderate deviations, the difference between $\mathcal{Y}_t$ and $\mathcal{Y}'_t$ is irrelevant in the following sense.

**Proposition 1.** For any $0 < \lambda, 0 < \theta < \pi/2$ and $0 < \varepsilon < 1/2$, $\{t^{-1/2-\varepsilon}\mathcal{Y}_t\}_{t\ge0}$ and $\{t^{-1/2-\varepsilon}\mathcal{Y}'_t\}_{t\ge0}$ are exponentially equivalent, i.e., for any $\delta > 0$,

$$ \limsup_{t \uparrow \infty} t^{-2\varepsilon} \log \mathbb{P} \left( |\mathcal{Y}_t - \mathcal{Y}'_t| \ge \delta t^{1/2+\varepsilon} \right) = -\infty. \quad (3) $$

Now, we want to deal with the randomness in the number of steps $K'_t$ in the definition of $\mathcal{Y}'_t$. For this, we define for $w > 0$ the process

$$ \mathcal{Y}_t^w := \sum_{i=1}^{[tw]} Y'_i $$

and establish in the following statement that it obeys a moderate-deviation principle.

**Proposition 2.** For any $0 < \lambda, 0 < \theta < \pi/2$, $0 < w$ and $0 < \varepsilon < 1/2$, $\{t^{-1/2-\varepsilon}\mathcal{Y}_t^w\}_{t\ge0}$ obeys the moderate-deviation principle with rate function $I_{\lambda,\theta}^w(x) := x^2/(2w\mathbb{E}[Y_1^{w'}])$.

Now let $\kappa := \mathbb{E}[X_1^{w'}]^{-1}$ denote the inverse expected horizontal progress. By Lemma 2, we have that $\kappa > 0$ and by Lemma 6 below also $\kappa < \infty$. The following result now presents the final ingredient for the proof of Theorem 1.

**Proposition 3.** For any $0 < \lambda, 0 < \theta < \pi/2$ and $0 < \varepsilon < 1/2$, $\{t^{-1/2-\varepsilon}\mathcal{Y}_t^\kappa\}_{t\ge0}$ and $\{t^{-1/2-\varepsilon}\mathcal{Y}'_t\}_{t\ge0}$ are exponentially equivalent, i.e., for any $\delta > 0$,

$$ \limsup_{t \uparrow \infty} t^{-2\varepsilon} \log \mathbb{P} \left( |\mathcal{Y}_t^\kappa - \mathcal{Y}'_t| \ge \delta t^{1/2+\varepsilon} \right) = -\infty. \quad (4) $$

*Proof of Theorem 1.* By Propositions 1 and 3, we have the exponential equivalence of $\mathcal{Y}_t$ and $\mathcal{Y}'_t$ and by Proposition 2 we have that $\mathcal{Y}_t^\kappa$ obeys the moderate-deviation principle with rate function

$$ I_{\lambda,\theta}(x) := x^2 \frac{\mathbb{E}[X_1']}{2\mathbb{E}[Y_1^{w'}]}, \quad (5) $$

as desired. For the scale invariance, if we denote by $U'_{\lambda,1} = (X'_{\lambda,1}, Y'_{\lambda,1})$ the progress of the first independent segment in the navigation based on a Poisson point process with intensity $\lambda > 0$, then, by scaling both the coordinates by $\sqrt{\lambda}$, we get that $(\sqrt{\lambda}X'_{\lambda,1}, \sqrt{\lambda}Y'_{\lambda,1})$ and $(X'_{1,1}, Y'_{1,1})$ have the same distribution. Therefore, we obtain

$$ 2\rho(\lambda, \theta) = \mathbb{E}[X'_{\lambda,1}]/\mathbb{E}[Y'_{\lambda,1}^2] = \sqrt{\lambda}\mathbb{E}[X'_{1,1}]/\mathbb{E}[Y'_{1,1}^2] = 2\sqrt{\lambda}\rho(1, \theta), $$

which finishes the proof. $\square$

Note that, when $0 < \theta \le \pi/4$, we have that $U'_1 = U_1$ and the Expression (1) for $\rho$ follows from a simple computation, see for example the proof of Lemma 1 below.
4. PROOFS

4.1. **Exponential tails of the stopping times.** Let us start by establishing exponential-decay properties of the inter-stopping time gaps.

**Proposition 4.** Let $0 < \lambda$ and $0 < \theta < \pi/2$. Then, for all $n, k \in \mathbb{N}$, there exist constants $c, C > 0$ depending only on $\theta$ such that

$$ \mathbb{P}(\tau_k^\theta - \tau_{k-1}^\theta \ge n) \le C e^{-cn}. \qquad (6) $$

In particular, for all $n, k \in \mathbb{N}$, $\mathbb{P}(\tau_k^\theta \ge n) \le kC e^{-cn/k}$.

First note that it suffices to prove that $\mathbb{P}(\tau_1^\theta \ge n) \le C e^{-cn}$ since the remaining statements then follow from the fact that $\{\tau_k^\theta - \tau_{k-1}^\theta\}_{k \ge 1}$ are iid. We write $\tau := \tau_1^\theta$ for the rest of the proof. It is worth noting that $\tau$ is invariant under scaling both the coordinates by $\sqrt{\lambda}$, and therefore, $\mathbb{P}(\tau \ge n)$ does not depend on $\lambda$. Note also that we can focus on the case $\pi/4 < \theta < \pi/2$ since for $\theta \le \pi/4$, we have almost surely that $\tau = 1$ as mentioned before, see the first paragraph in the proof of Theorem 2 below.

Our arguments rest on ideas developed in [6], more precisely the proof of [6, Proposition 3.1], where however a slightly different situation is analyzed. Let us define for all $n \ge 0$,

$$ L_n := \sup \left\{ x - \sum_{i=1}^{n} X_i : (x, y) \in H_n \right\}, $$

the width of the history set and write $U_n = (X_n, Y_n) = (R_n, \Phi_n)$ for the progress variables first in Cartesian and alternatively in polar coordinates. In particular, $L_0 = 0$ and $\mathbb{P}(\tau \ge n) = \mathbb{P}(H_m \neq \emptyset)$ for all $m < n$.

Note that, if $\Phi_n \in [-\pi/2 + \theta, \pi/2 - \theta] =: T_\theta$, then the $n$-th step escapes its immediate history, i.e., $H_n = C_\theta(V_n) \cap H_{n-1}$. Therefore, for all $n \ge 1$, we have

$$ L_n \le (L_{n-1} - X_n)_+ \mathbb{1}\{\Phi_n \in T_\theta\} + \max\{(L_{n-1} - X_n)_+, (R_n - X_n)\} \mathbb{1}\{\Phi_n \notin T_\theta\}, $$

where $x_+ := \max\{x, 0\}$. The key ingredient for the proof is the following (random) monotone coupling of the progress variables with respect to an iid sequence, which is also used on multiple occasions throughout the proof section.

**Lemma 3.** There exists a sequence of iid quadruplets of random variables $\{(\underline{R}_n, \underline{\Phi}_n, \overline{R}_n, \overline{\Phi}_n)\}_{n \ge 1}$, defined on an extended probability space, such that for all $n \ge 1$,

(i) $\underline{R}_n \le R_n \le \overline{R}_n$ a.s.,

(ii) if $\underline{\Phi}_n \in T_\theta$ then $\underline{\Phi}_n = \overline{\Phi}_n$ a.s., and

(iii) $(\underline{R}_n, \underline{\Phi}_n, \overline{R}_n, \overline{\Phi}_n) \stackrel{d}{=} (\underline{R}, \underline{\Phi}, \overline{R}, \overline{\Phi})$, where

$$ (\underline{R}, \underline{\Phi}) := \operatorname{argmin}\{|v|: v \in C_\theta \cap \mathcal{P}_\lambda\} \text{ and } (\overline{R}, \overline{\Phi}) := \operatorname{argmin}\{|v|: v \in C_{\pi/2-\theta} \cap \mathcal{P}_\lambda\}. $$

We present to the proof of the lemma later in this section. Now, observe that, almost surely,

$$ \begin{aligned} L_n &\le (L_{n-1} - R_n \cos \theta)_+ \mathbb{1}\{\Phi_n \in T_\theta\} + \max\{(L_{n-1} - R_n \cos \theta)_+, R_n(1 - \cos \theta)\} \mathbb{1}\{\Phi_n \notin T_\theta\} \\ &\le (L_{n-1} - \underline{R}_n \cos \theta)_+ \mathbb{1}\{\Phi_n \in T_\theta\} + \max\{L_{n-1}, \overline{R}_n\} \mathbb{1}\{\Phi_n \notin T_\theta\} \\ &\le (L_{n-1} - \underline{R}_n \cos \theta)_+ \mathbb{1}\{\underline{\Phi}_n \in T_\theta\} + \max\{L_{n-1}, \overline{R}_n\} \mathbb{1}\{\overline{\Phi}_n \notin T_\theta\}, \end{aligned} $$

and we can make a comparison with a Markov chain $\{M_n\}_{n \ge 0}$ on $\mathbb{N}_0$, defined as $M_0 := 0$ and

$$ M_n := (M_{n-1} - |\underline{R}_n \cos \theta|)_+ \mathbb{1}\{\underline{\Phi}_n \in T_\theta\} + \max\{M_{n-1}, \lceil \overline{R}_n \rceil\} \mathbb{1}\{\overline{\Phi}_n \notin T_\theta\}, \quad n > 0. $$

The following result establishes that the stopping time $\tau^M := \inf\{n > 0: M_n = 0\}$ of the Markov chain to hit 0 has an exponential tail.
**Lemma 4.** For any $n > 0$, $\mathbb{P}(\tau^M \ge n) \le Ce^{-cn}$, for some $C, c > 0$.

*Proof of Proposition 4.* The reason for constructing the Markov chain is to dominate the sequence of widths $\{L_n\}_{n \ge 0}$. More precisely, by construction, $M_n \ge L_n$ for all $n \ge 0$ and, in particular, when $M_n = 0$, we have $L_n = 0$. Therefore, almost surely, $\tau^M \ge \tau$, which completes the proof. $\square$

*Proof of Lemma 4.* Note that the Markov chain $\{M_n\}_{n \ge 0}$ is irreducible since, for any $m > 0$,

$$ \begin{aligned} \mathbb{P}(M_1 = m | M_0 = 0) &\ge \mathbb{P}(\lceil \bar{R}_1 \rceil = m \text{ and } \underline{\Phi}_1 \notin T_\theta) > 0 \quad \text{and} \\ \mathbb{P}(M_1 = 0 | M_0 = m) &\ge \mathbb{P}(\lfloor \bar{R}_1 \cos \theta \rfloor > m \text{ and } \underline{\Phi}_1 \in T_\theta) > 0. \end{aligned} \quad (7) $$

Now, we demonstrate the recurrence of $\{M_n\}_{n \ge 0}$ by establishing that 0 is a recurrent state. From Lemma 3, we know that for all $h \ge 2$,

$$ \mathbb{P}(\lceil \bar{R}_1 \rceil > h) \le \mathbb{P}(\bar{R}_1 > h/2) = \exp(-\lambda(\pi/2 - \theta)h^2/4). $$

Let us define the sequence $\{a_n\}_{n \ge 1}$ as

$$ a_n := \left\lceil \left( \frac{8}{\lambda(\pi/2 - \theta)} \log n \right)^{1/2} \right\rceil. $$

Then, for all sufficiently large $n$, we have $\mathbb{P}(\lceil \bar{R}_1 \rceil > a_n) \le n^{-2}$. This implies that, for all sufficiently large $n$,

$$ \mathbb{P}\left(\max_{i=1}^{n} \lceil \bar{R}_i \rceil \le a_n\right) \ge (1 - n^{-2})^n $$

and therefore,

$$ \lim_{n \uparrow \infty} \mathbb{P} \left( \max_{i=1}^{n} \lceil \bar{R}_i \rceil \le a_n \right) = 1. \quad (8) $$

Now, let $G_n := \mathbb{1}\{\underline{\Phi}_n \in T_\theta$ and $\bar{R}_n \cos \theta \ge 1\}$ and $q := \mathbb{P}(G_1 = 1) > 0$. From the definition of $M_n$, it follows that, whenever $G_n = 1$, we have $M_n \le (M_{n-1} - 1)_+$. We define $A_n$ to be the event that the finite sequence $\{G_i\}_{i=1}^n$ has a run of 1's of length at least $a_n$. Since $\{G_i\}_{i=1}^n$ are iid, we have

$$ \mathbb{P}(A_n^c) \le (1 - q^{a_n})^{\lfloor n/a_n \rfloor}. $$

Further, since, for all sufficiently large $n$,

$$ a_n \le \frac{1}{2(-\log q)} \log n, $$

we have that, for all sufficiently large $n$,

$$ \mathbb{P}(A_n^c) \le (1 - n^{-1/2})^{\lfloor 2(-\log q)n/\log n \rfloor}, $$

which tends to zero as $n \to \infty$. Therefore, we obtain

$$ \lim_{n \uparrow \infty} \mathbb{P}(A_n) = 1. \quad (9) $$

Now, by construction, we have

$$ \begin{aligned} \mathbb{P}(M_i = 0 \text{ for some } 1 \le i \le n | M_0 = 0) & \\ & \ge \mathbb{P}\left(\max_{i=1}^{n} M_i \le a_n \text{ and } \{G_i\}_{i=1}^n \text{ has } a_n \text{ consecutive 1's } \middle| M_0 = 0\right) \\ & \ge \mathbb{P}\left(\max_{i=1}^{n} \lceil \bar{R}_i \rceil \le a_n \text{ and } \{G_i\}_{i=1}^n \text{ has } a_n \text{ consecutive 1's } \middle| M_0 = 0\right) \\ & = \mathbb{P}\left(\max_{i=1}^{n} \lceil \bar{R}_i \rceil \le a_n \text{ and } \{G_i\}_{i=1}^n \text{ has } a_n \text{ consecutive 1's }\right). \end{aligned} $$

But, this tends to one as $n \to \infty$ by (8) and (9). As a result, we established that 0 is a recurrent state, and therefore, in view of (7), the Markov chain $\{M_n\}_{n \ge 0}$ is recurrent.
The rest of the proof is similar to the proof of [2, Proposition 5.5], but we include some details for the convenience of the reader. Observe that

$$ 
\begin{aligned}
\mathbb{E}[e^{M_1} | M_0 = k] &= \mathbb{E}[\exp((k - \lfloor \underline{R}_1 \cos \theta \rfloor)_+ \mathbf{1}\{\underline{\Phi}_1 \in T_\theta\} + \max\{k, \lceil \overline{R}_1 \rceil\} \mathbf{1}\{\underline{\Phi}_1 \notin T_\theta\})] \\
&= e^k \mathbb{E}[\exp(-\min\{k, \lfloor \underline{R}_1 \cos \theta \rfloor\} \mathbf{1}\{\underline{\Phi}_1 \in T_\theta\} + \max\{0, \lceil \overline{R}_1 \rceil - k\} \mathbf{1}\{\underline{\Phi}_1 \notin T_\theta\})]
\end{aligned}
\quad (10) $$

and note that

$$ \exp(-\min\{k, \lfloor \underline{R}_1 \cos \theta \rfloor\} \mathbf{1}\{\underline{\Phi}_1 \in T_\theta\} + \max\{0, \lceil \overline{R}_1 \rceil - k\} \mathbf{1}\{\underline{\Phi}_1 \notin T_\theta\}) \le \exp(\lceil \overline{R}_1 \rceil), $$

which has finite expectation. Therefore, for all $k \ge 0$,

$$ \mathbb{E}[\exp(M_1) | M_0 = k] < \infty. \quad (11) $$

Moreover, by the dominated-convergence theorem, we get that

$$ 
\begin{aligned}
\lim_{k \uparrow \infty} \mathbb{E}[\exp(-\min\{k, \lfloor \underline{R}_1 \cos \theta \rfloor\} \mathbf{1}\{\underline{\Phi}_1 \in T_\theta\} + \max\{0, \lceil \overline{R}_1 \rceil - k\} \mathbf{1}\{\underline{\Phi}_1 \notin T_\theta\})] \\
&= \mathbb{E}[\exp(-\lfloor \underline{R}_1 \cos \theta \rfloor \mathbf{1}\{\underline{\Phi}_1 \in T_\theta\})] < 1
\end{aligned}
$$

and thus, there exists $r > 1$ and $k_0 \ge 0$ such that for all $k > k_0$,

$$ \mathbb{E}[\exp(-\min\{k, \lfloor \underline{R}_1 \cos \theta \rfloor\} \mathbf{1}\{\underline{\Phi}_1 \in T_\theta\} + \max\{0, \lceil \overline{R}_1 \rceil - k\} \mathbf{1}\{\underline{\Phi}_1 \notin T_\theta\})] < r^{-1}. $$

But this, together with (10), implies that, for all $k > k_0$,

$$ \mathbb{E}[\exp(M_1) | M_0 = k] < r^{-1} \exp(k). \quad (12) $$

Let $\sigma := \inf\{n > 0: M_n \le k_0\}$ denote the first time that $M_n$ is below $k_0$ and fix any $l > k_0$. In view of (12), note that, for $M_0 = l$, the process $\{Y_n\}_{n \ge 0}$ defined as $Y_n := r^{n \wedge \sigma} \exp(M_{n \wedge \sigma})$ is a non-negative super-martingale. Therefore, by the recurrence of the Markov chain $\{M_n\}_{n \ge 0}$, almost surely,

$$ Y_n \to_{\infty} Y_\infty := r^\sigma \exp(M_\sigma) \ge r^\sigma. $$

This, together with Fatou's lemma, implies that,

$$ \mathbb{E}[r^\sigma | M_0 = l] \le \mathbb{E}[Y_\infty | M_0 = l] \le \liminf_{n \uparrow \infty} \mathbb{E}[Y_n | M_0 = l] \le \mathbb{E}[Y_0 | M_0 = l] = \exp(l). $$

Since $l > k_0$ is arbitrary, we have that for all $l > k_0$,

$$ \mathbb{E}[r^\sigma | M_0 = l] \le \exp(l). $$

Therefore, for any $z \le k_0$,

$$ 
\begin{aligned}
\mathbb{E}[r^\sigma | M_0 = z] &\le r + r \sum_{l > k_0} \mathbb{P}(M_1 = l | M_0 = z) \mathbb{E}[r^\sigma | M_0 = l] \\
&\le r + r \sum_{l > k_0} \mathbb{P}(M_1 = l | M_0 = z) \exp(l) \\
&\le r + r \mathbb{E}[\exp(M_1) | M_0 = z] < \infty.
\end{aligned}
$$

Note that, for any $z \le k_0$ and $l > k_0$,

$$ \mathbb{P}(M_1 = l | M_0 = z) = \mathbb{P}(\underline{\Phi}_1 \notin T_\theta, \lceil \overline{R}_1 \rceil = l) = \mathbb{P}(M_1 = l | M_0 \le k_0), $$

which does not depend on $z$. Therefore, if we define $\{\sigma_i\}_{i \ge 0}$ as $\sigma_0 := 0$ and for all $i \ge 1$,

$$ \sigma_i := \inf\{n > \sigma_{i-1}: M_n \le k_0\}, $$

then $\{\sigma_i - \sigma_{i-1}\}_{i \ge 1}$ are iid copies of $\sigma$. Moreover, for all $z \le k_0$,

$$ c_1 := \mathbb{E}[r^\sigma | M_0 \le k_0] = \mathbb{E}[r^\sigma | M_0 = z] < \infty. $$

We choose $c_2 > 0$ such that $c_1^{c_2} < r$. Then, by Markov's inequality,

$$ \mathbb{P}(\sigma_{\lfloor c_2 n \rfloor} \ge n | M_0 = 0) \le r^{-n} \mathbb{E}[r^{\sigma_{\lfloor c_2 n \rfloor}} | M_0 = 0] = r^{-n} \mathbb{E}[r^{\sigma_1} | M_0 = 0]^{\lfloor c_2 n \rfloor} \le (r^{-1} c_1^{c_2})^n. $$
and thus

$$
\begin{align*}
\mathbb{P}(\tau^M > n | M_0 = 0) &\le \mathbb{P}(\tau^M > n, \sigma_{\lfloor c_2 n \rfloor} < n | M_0 = 0) + \mathbb{P}(\sigma_{\lfloor c_2 n \rfloor} \ge n | M_0 = 0) \\
&\le \mathbb{P}\left( \bigcap_{i=1}^{\lfloor c_2 n \rfloor} \{ \underline{\Phi}_{\sigma_{i+1}} \notin T_{\theta} \text{ or } \lfloor \underline{R}_{\sigma_{i+1}} \cos \theta \rfloor < k_0 \} \right) + \mathbb{P}(\sigma_{\lfloor c_2 n \rfloor} \ge n | M_0 = 0) \\
&\le \mathbb{P}(\underline{\Phi}_1 \notin T_{\theta} \text{ or } \lfloor \underline{R}_1 \cos \theta \rfloor < k_0)^{\lfloor c_2 n \rfloor} + (r^{-1} c_1^{c_2})^n \\
&\le C_1 e^{-cn},
\end{align*}
$$

for some $C_1, c > 0$. This proves the result.

□

Now, the only thing that remains to be proven is Lemma 3. For this, let us first verify the
following statement.

**Lemma 5.** For any $n \ge 0$, we have that $C_{\pi/2-\theta}(V_n) \cap H_n = \emptyset$.

*Proof of Lemma 5.* From the definition of $H_n$, we see that, for any $n \ge 0$,

$$
H_n \subseteq \bigcup_{m=0}^{n-1} B(V_m, R_{m+1}).
$$

Now, since, for any $0 \le m \le n - 1$, $V_n \in C_{\theta}(V_m)$, it follows that $R_{m+1} \le |V_n - V_m|$. Therefore,

$$
H_n \subseteq \bigcup_{m=0}^{n-1} B(V_m, |V_n - V_m|).
$$

Hence, it suffices to show that, for any $0 \le m \le n - 1$, $C_{\pi/2-\theta}(V_n) \cap B(V_m, |V_n - V_m|) = \emptyset$. For this, note that the lines

$$
\begin{align*}
L_n(\pi/2 - \theta) &:= V_n + \{(r, \varphi) : r > 0, \varphi = \pi/2 - \theta\} \quad \text{and} \\
L_n(-\pi/2 + \theta) &:= V_n + \{(r, \varphi) : r > 0, \varphi = -\pi/2 + \theta\}
\end{align*}
$$

are the two boundary lines of $C_{\pi/2-\theta}(V_n)$. Hence, it is also adequate to prove that for any $0 \le m \le n-1$, $(L_n(\pi/2-\theta) \cup L_n(-\pi/2+\theta)) \cap B(V_m, |V_n-V_m|) = \emptyset$.

We now fix $m < n$ and write $V_m$ and $V_n$ in Cartesian coordinates as $V_m = (V_{m,1}, V_{m,2})$ and $V_n = (V_{n,1}, V_{n,2})$. If $V_{m,2} = V_{n,2}$, then $|V_n - V_m| = V_{n,1} - V_{m,1}$ and since, for any $x = (x_1, x_2) \in L_n(\pi/2 - \theta) \cup L_n(-\pi/2 + \theta)$, we have $x_1 > V_{n,1} > V_{m,1}$, it follows that

$$
|x - V_m| \geq x_1 - V_{m,1} > V_{n,1} - V_{m,1} = |V_n - V_m|.
$$

$$
\text{Therefore, } (L_n(\pi/2 - \theta) \cup L_n(-\pi/2 + \theta)) \cap B(V_m, |V_n - V_m|) = \emptyset.
$$

Now, suppose $V_{m,2} \neq V_{n,2}$. Without loss of generality, we assume $V_{m,2} < V_{n,2}$. Then, for any $x = (x_1, x_2) \in L_n(\pi/2 - \theta)$, we have $x_1 > V_{n,1} > V_{m,1}$ and $x_2 > V_{n,2} > V_{m,2}$, which implies that

$$
|x - V_m| = \sqrt{(x_1 - V_{m,1})^2 + (x_2 - V_{m,2})^2} > \sqrt{(V_{n,1} - V_{m,1})^2 + (V_{n,2} - V_{m,2})^2} = |V_n - V_m|.
$$

Therefore, $L_n(\pi/2 - \theta) \cap B(V_m, |V_n - V_m|) = \emptyset$. Now, we draw two horizontal line segments $\overline{V_m A}$ and $\overline{V_n B}$ passing through $V_m$ and $V_n$, respectively, such that $\overline{V_m A}$ intersects $L_n(-\pi/2 + \theta)$ at the point $C$, see Figure 2 for an illustration. From the definition of $L_n(-\pi/2 + \theta)$, we know that $\angle BV_n C = \pi/2 - \theta$. Since $\overline{V_m A}$ and $\overline{V_n B}$ are parallel, we also have $\angle V_n C V_m = \pi/2 - \theta$. Furthermore, as $V_n \in C_{\theta}(V_m)$, it follows that $\angle V_n V_m C \le \theta$. Now, focusing on the triangle $\triangle V_n V_m C$, we observe the relationship

$$
\angle V_n C V_m + \angle V_n V_m C + \angle V_m V_n C = \pi,
$$

which implies $\angle V_m V_n C \ge \pi/2$, and this, in turn, implies that $\cos \angle V_m V_n C \le 0$. Therefore, for any $x \in L_n(-\pi/2 + \theta)$, by the law of cosines,

$$
|x - V_m| = \sqrt{|V_n - V_m|^2 + |x - V_n|^2 - 2 \cos \angle V_m V_n C \cdot |V_n - V_m| \cdot |x - V_n|} > |V_n - V_m|,
$$
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Illustration for the proof of Lemma 5.</figcaption></figure>

which means $L_n(\pi/2 - \theta) \cap B(V_m, |V_n - V_m|) = \emptyset$. This proves that, for any $0 \le m \le n - 1$, $C_{\pi/2-\theta}(V_n) \cap B(V_m, |V_n - V_m|) = \emptyset$, thereby completing the proof. $\square$

*Proof of Lemma 3.* We define a sequence of sets $\{D_n\}_{n \ge 1}$ as

$$D_n := C_{\theta}(V_{n-1}) \cap \overline{B(V_{n-1}, R_n)} \cap H_{n-1}^c.$$

Essentially, $D_n$ is the previously unexplored set where we have explored at the n-th step to find $V_n$. Clearly, $\{D_n\}_{n \ge 1}$ are pairwise disjoint. Let $\{P_{\lambda}^{(n)}\}_{n \ge 1}$ be iid copies of the Poisson point process $P_{\lambda}$. We define $\{Q_{\lambda}^{(n)}\}_{n \ge 1}$ as

$$Q_{\lambda}^{(n)} := (P_{\lambda} \cap D_n) \cup (P_{\lambda}^{(n)} \cap D_n^c).$$

Since the $D_n$ are disjoint, $\{Q_{\lambda}^{(n)}\}_{n \ge 1}$ is a sequence of iid Poisson point processes with intensity $\lambda$. We write

$$\underline{W}_n := \operatorname{argmin}\{|v - V_{n-1}|: v \in C_{\theta}(V_{n-1}) \cap Q_{\lambda}^{(n)}\},$$

and define $(\underline{R}_n, \underline{\Phi}_n)$ to be the polar coordinates of $\underline{W}_n - V_{n-1}$. Similarly, we write

$$\overline{W}_n := \operatorname{argmin}\{|v - V_{n-1}|: v \in C_{\pi/2-\theta}(V_{n-1}) \cap Q_{\lambda}^{(n)}\},$$

and define $(\overline{R}_n, \overline{\Phi}_n)$ to be the polar coordinates of $\overline{W}_n - V_{n-1}$. From the definition, it follows that $(\underline{R}_n, \underline{\Phi}_n, \overline{R}_n, \overline{\Phi}_n)$ and $(\underline{R}, \underline{\Phi}, \overline{R}, \overline{\Phi})$ are equal in distribution. Furthermore, note that, since $\{Q_{\lambda}^{(n)}\}_{n \ge 1}$ are iid, $\{(\underline{R}_n, \underline{\Phi}_n, \overline{R}_n, \overline{\Phi}_n)\}_{n \ge 1}$ are also iid. We know that $(R_n, \Phi_n)$ are the polar coordinates of $V_n - V_{n-1}$, where

$$
\begin{align*}
V_n &= \operatorname{argmin}\{|v - V_{n-1}|: v \in C_{\theta}(V_{n-1}) \cap P_{\lambda}\} \\
&= \operatorname{argmin}\{|v - V_{n-1}|: v \in C_{\theta}(V_{n-1}) \cap \overline{B(V_{n-1}, R_n)} \cap H_{n-1}^c \cap P_{\lambda}\} \\
&= \operatorname{argmin}\{|v - V_{n-1}|: v \in D_n \cap P_{\lambda}\} \\
&= \operatorname{argmin}\{|v - V_{n-1}|: v \in D_n \cap Q_{\lambda}^{(n)}\} \\
&= \operatorname{argmin}\{|v - V_{n-1}|: v \in C_{\theta}(V_{n-1}) \cap \overline{B(V_{n-1}, R_n)} \cap H_{n-1}^c \cap Q_{\lambda}^{(n)}\} \\
&= \operatorname{argmin}\{|v - V_{n-1}|: v \in C_{\theta}(V_{n-1}) \cap H_{n-1}^c \cap Q_{\lambda}^{(n)}\}.
\end{align*}
$$
Now, from Lemma 5, we obtain that $C_{\pi/2-\theta}(V_{n-1}) \subseteq C_{\theta}(V_{n-1}) \cap H_{n-1}^c \subseteq C_{\theta}(V_{n-1})$, which implies $\overline{R}_n \ge R_n \ge \overline{R}_n$. Additionally, if $\underline{\Phi}_n \in T_{\theta}$, then we have $(\underline{R}_n, \underline{\Phi}_n) = (R_n, \Phi_n) = (\overline{R}_n, \overline{\Phi}_n)$. This concludes the proof. □

## 4.2. Proof of Lemma 2 and Proposition 2.

*Proof of Lemma 2.* Using Proposition 4, Lemma 3 and the Cauchy-Schwarz inequality,

$$ \mathbb{E}[e^{\langle \gamma, U_1' \rangle}] \le \sum_{n \ge 1} \mathbb{E}[e^{2\langle \gamma, \sum_{j=1}^n U_j \rangle}]^{1/2} \mathbb{P}(\tau_1^\theta \ge n)^{1/2} \le \sum_{n \ge 1} \mathbb{E}[e^{2(\gamma_1+\gamma_2)\overline{R}}]^{n/2} \sqrt{C} e^{-cn/2}. $$

Since $\overline{R}$ has all exponential moments finite, for all sufficiently small $\gamma_1, \gamma_2 > 0$, the above sum is also finite. □

*Proof of Proposition 2.* Note that, by symmetry, we have that $\mathbb{E}[Y_1'] = 0$ and by Lemma 2 that

$$ \limsup_{n \uparrow \infty} n^{-2\epsilon} \log \mathbb{P}(|Y_1'| \ge n^{1/2+\epsilon}) = -\infty. $$

Indeed, by symmetry and the exponential Markov inequality, for sufficiently small $s > 0$,

$$ \mathbb{P}(|Y_1'| \ge n^{1/2+\epsilon}) \le 2e^{-sn^{1/2+\epsilon}} \mathbb{E}[e^{sY_1'}] < \infty, $$

and thus

$$ \limsup_{n \uparrow \infty} n^{-2\epsilon} \log \mathbb{P}(|Y_1'| \ge n^{1/2+\epsilon}) \le -s \limsup_{n \uparrow \infty} n^{1/2-\epsilon} = -\infty. $$

Hence, $\{\mathcal{Y}_{[t]}^w\}_{t \ge 0}$ satisfies the conditions of [8, Theorem 2.2] and thus obeys the moderate-deviation principle with rate $x^2/(2w\mathbb{E}[Y_1'^2])$. But $\{\mathcal{Y}_{[t]}^w\}_{t \ge 0}$ and $\{\mathcal{Y}_t^w\}_{t \ge 0}$ are exponentially equivalent since, for all $\delta > 0$,

$$ \limsup_{t \uparrow \infty} t^{-2\epsilon} \log \mathbb{P}(|\mathcal{Y}_{[t]}^w - \mathcal{Y}_t^w| \ge \delta t^{1/2+\epsilon}) \le \limsup_{t \uparrow \infty} t^{-2\epsilon} \log \mathbb{P}\left(\sum_{i=1}^{[w+1]} |Y_i'| \ge \delta t^{1/2+\epsilon}\right), $$

as $[tw] - \lfloor |t|w \rfloor \le [w+1]$. Hence, again using symmetry, independence and the exponential Markov inequality, for sufficiently small $s > 0$,

$$ \mathbb{P}\left(\sum_{i=1}^{[w+1]} |Y_i'| \ge \delta t^{1/2+\epsilon}\right) \le 2e^{-s\delta t^{1/2+\epsilon}} \mathbb{E}[e^{sY_1'}]^{[w+1]} < \infty $$

and thus

$$ \limsup_{t \uparrow \infty} t^{-2\epsilon} \log \mathbb{P}(|\mathcal{Y}_{[t]}^w - \mathcal{Y}_t^w| \ge \delta t^{1/2+\epsilon}) \le -s\delta \limsup_{t \uparrow \infty} t^{1/2-\epsilon} = -\infty, $$

as desired. □

## 4.3. Proof of Propositions 1.

*Proof of Proposition 1.* First note that we have $\mathcal{Y}_t = \sum_{i=1}^{K_t} Y_i + Y_{K_t+1}(t - \sum_{i=1}^{K_t} X_i)/X_{K_t+1}$ with $(t - \sum_{i=1}^{K_t} X_i)/X_{K_t+1} \le 1$, and hence, by Lemma 3,

$$ \begin{aligned} \mathbb{P}(|\mathcal{Y}_t - \mathcal{Y}_t'| \ge \delta t^{1/2+\epsilon}) &\le \mathbb{P}\left(\sum_{i=\tau_1^\theta+1}^{K_t+1} |Y_i| \ge \delta t^{1/2+\epsilon}\right) \\ &\le \mathbb{P}\left(\sum_{i=1}^{\tau_1^\theta} \overline{R}_i \ge \delta t^{1/2+\epsilon}\right) \le \mathbb{P}\left(\sum_{i=1}^{\lfloor t^{\epsilon'} \rfloor} \overline{R}_i \ge \delta t^{1/2+\epsilon}\right) + \mathbb{P}(\tau_1^\theta \ge \lfloor t^{\epsilon'} \rfloor), \end{aligned} $$
for some $\varepsilon' \in (2\varepsilon, 1/2 + \varepsilon)$. This, together with Proposition 4 and the exponential Markov inequality, implies that

$$ \mathbb{P}(|Y_t - Y'_t| \ge \delta t^{1/2+\varepsilon}) \le e^{-\delta t^{1/2+\varepsilon}} \mathbb{E}[e^{\overline{R}t}]^{\lfloor t^{\varepsilon'} \rfloor} + C e^{-c \lfloor t^{\varepsilon'} \rfloor}, $$

and therefore,

$$ \limsup_{t \uparrow \infty} t^{-2\varepsilon} \log \mathbb{P}(|Y_t - Y'_t| \ge \delta t^{1/2+\varepsilon}) \\ \le \max \left\{ - \liminf_{t \uparrow \infty} t^{-2\varepsilon} (\delta t^{1/2+\varepsilon} - \lfloor t^{\varepsilon'} \rfloor \log \mathbb{E}[e^{\overline{R}t}]), - \liminf_{t \uparrow \infty} c \lfloor t^{\varepsilon'} \rfloor t^{-2\varepsilon} \right\} = -\infty, $$

as desired.

□

**4.4. Proof of Proposition 3.** Before we prove Proposition 3, let us collect concentration properties of the horizontal displacement.

**Lemma 6.** We have that $\kappa < \infty$ and for all $\varepsilon > 0$ there exist constants $c_1, c_2 > 0$ such that for all $t > 0$

$$ \mathbb{P}(K'_t/t \notin B_{\varepsilon}(\kappa)) \le c_1 e^{-c_2 t}. \quad (13) $$

*Proof of Lemma 6.* First, note that

$$ \kappa^{-1} = \mathbb{E}[X'_1] \ge \mathbb{E}[X_1 \mathbf{1}\{\tau_1^\theta = 1\}] = \lambda \int_0^\infty dr r^2 e^{-\theta r^2} \int d\varphi \cos \varphi \mathbf{1}\{\theta - \pi/2 \le \varphi \le \pi/2 - \theta\} > 0, $$

since independence after one step is achieved precisely if the angle is in the interval $[\theta-\pi/2, \pi/2-\theta]$. For the second part of the statement, note that we can bound

$$ \begin{aligned} \mathbb{P}(K'_t/t \notin B_{\varepsilon}(\kappa)) &\le \mathbb{P}(K'_t \le t(\kappa - \varepsilon)) + \mathbb{P}(K'_t \ge t(\kappa + \varepsilon)) \\ &\le \mathbb{P}\left(\sum_{i=1}^{\lfloor t(\kappa - \varepsilon) \rfloor} X'_i \ge t\right) + \mathbb{P}\left(\sum_{i=1}^{\lfloor t(\kappa + \varepsilon) \rfloor} X'_i < t\right), \end{aligned} $$

where we used that $K'_t$, as defined in (2), can also be represented as

$$ K'_t = \sup \left\{ n > 0 : \sum_{i=1}^{n} X'_i < t \right\}. $$

Now, by the exponential Markov inequality, for any $s > 0$,

$$ \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P} \left( \sum_{i=1}^{\lfloor t(\kappa - \varepsilon) \rfloor} X'_i \ge t \right) \le -s \left( 1 - (\kappa - \varepsilon) s^{-1} \log \mathbb{E} \left[ e^{s X'_1} \right] \right), $$

where, $s^{-1} \log \mathbb{E}[e^{sX'_1}]$ converges to $\kappa^{-1}$ for $s$ tending to zero. In particular, there exists $c > 0$, such that $\limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P} \left( \sum_{i=1}^{\lfloor t(\kappa - \varepsilon) \rfloor} X'_i \ge t \right) < -c$. The same argument holds also for the other term, as for all $s > 0$,

$$ \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P} \left( \sum_{i=1}^{\lfloor t(\kappa + \varepsilon) \rfloor} -X'_i > -t \right) \le s \left( 1 + (\kappa + \varepsilon) s^{-1} \log \mathbb{E} \left[ e^{-sX'_1} \right] \right), $$

where $s^{-1} \log \mathbb{E}[e^{-sX'_1}]$ converges to $-\kappa^{-1}$, as desired.

□
Proof of Proposition 3. Let us fix $\varepsilon' > 0$ and note that

$$
\begin{align}
\mathbb{P}(|\mathcal{Y}_t^\kappa - \mathcal{Y}_t'| \ge \delta t^{1/2+\varepsilon}) &\le \mathbb{P}\left(\left\{\left|\sum_{i=\lfloor t\kappa \rfloor+1}^{K'_t} Y_i'\right| \ge \delta t^{1/2+\varepsilon}\right\} \cap \{\kappa \le K'_t/t \le \kappa + \varepsilon'\}\right) \nonumber \\
&\quad + \mathbb{P}\left(\left\{\left|\sum_{i=K'_t+1}^{\lfloor t\kappa \rfloor} Y_i'\right| \ge \delta t^{1/2+\varepsilon}\right\} \cap \{\kappa - \varepsilon' \le K'_t/t \le \kappa\}\right) \nonumber \\
&\quad + \mathbb{P}(K'_t/t \notin B_{\varepsilon'}(\kappa)), \tag{14}
\end{align}
$$

where, by Lemma 6, $\limsup_{t\uparrow\infty} t^{-2\varepsilon} \log \mathbb{P}(K'_t/t \notin B_{\varepsilon'}(\kappa)) = -\infty$ and hence the third summand plays no role, by logarithmic equivalence. For the first summand in (14), since the $Y'_i$ are iid, we have the bound

$$
\sum_{m=\lfloor t\kappa \rfloor+1}^{\lfloor t(\kappa+\varepsilon')\rfloor} \mathbb{P}\left(\left\{\left|\sum_{i=\lfloor t\kappa \rfloor+1}^{K'_t} Y_i'\right| \ge \delta t^{1/2+\varepsilon}\right\} \cap \{K'_t = m\}\right) \le \sum_{m=1}^{r_1(t,\varepsilon')} \mathbb{P}\left(\left|\sum_{i=1}^{m} Y_i'\right| \ge \delta t^{1/2+\varepsilon}\right), \quad (15)
$$

where the number of summands in the above sum is $r_1(t, \varepsilon') := \lfloor t(\kappa + \varepsilon') \rfloor - \lfloor t\kappa \rfloor$. Note that the corresponding upper bound is valid also for the second summand in (14) with $r_1(r, \varepsilon')$ replaced by $r_2(t, \varepsilon') := \lfloor t\kappa \rfloor - \lfloor t(\kappa - \varepsilon') \rfloor$. Further, since $\limsup_{t\uparrow\infty} t^{-2\varepsilon} \log r(t, \varepsilon') = 0$, where $r(t, \varepsilon') = r_1(t, \varepsilon') \lor r_2(t, \varepsilon')$, we have that

$$
\begin{align*}
\limsup_{t \uparrow \infty} t^{-2\varepsilon} \log \mathbb{P}(|\mathcal{Y}_t^\kappa - \mathcal{Y}_t'| \ge \delta t^{1/2+\varepsilon}) &\le \limsup_{t \uparrow \infty} t^{-2\varepsilon} \sup_{0 \le \alpha \le \varepsilon'} \log \mathbb{P}\left(\left|\sum_{i=1}^{\lfloor t\alpha \rfloor} Y_i'\right| \ge \delta t^{1/2+\varepsilon}\right) \\
&\le \limsup_{t \uparrow \infty} t^{-2\varepsilon} \log \mathbb{P}\left(\left|\sum_{i=1}^{\lfloor t\varepsilon' \rfloor} Y_i'\right| \ge \delta t^{1/2+\varepsilon}\right),
\end{align*}
$$

where we used that, by symmetry and independence,

$$
\mathbb{P}\left(\sum_{i=1}^{\lfloor t\alpha \rfloor} Y_i' \ge \delta t^{1/2+\varepsilon}\right) = 2\mathbb{P}\left(\sum_{i=1}^{\lfloor t\alpha \rfloor} Y_i' \ge \delta t^{1/2+\varepsilon}, \sum_{i=\lfloor t\alpha \rfloor+1}^{\lfloor t\varepsilon' \rfloor} Y_i' \ge 0\right) \le 2\mathbb{P}\left(\sum_{i=1}^{\lfloor t\varepsilon' \rfloor} Y_i' \ge \delta t^{1/2+\varepsilon}\right),
$$

and similar for $\mathbb{P}\left(\sum_{i=1}^{\lfloor t\alpha \rfloor} Y_i' < -\delta t^{1/2+\varepsilon}\right)$. Hence, using the moderate-deviation principle, Proposition 2, we have that

$$
\limsup_{t \uparrow \infty} t^{-2\varepsilon} \log \mathbb{P}(|\mathcal{Y}_t^\kappa - \mathcal{Y}_t'| \ge \delta t^{1/2+\varepsilon}) \le -I^{\varepsilon'}(\delta),
$$

which tends to $-\infty$ as $\varepsilon'$ tends to zero, as desired. $\square$

4.5. **Proof of Theorem 2.** Let us now present the proof for our large-deviation statement.

*Proof of Lemma 1.* The statement follows from an application of the multivariate Cramér theorem for empirical means of sequences of iid random variables that possess exponential moments, see [7, Corollary 6.1.6]. In order to compute the exponential moments, we use polar coordinates, i.e., consider $U_1 = (R, \Phi) \in \mathbb{R}_+ \times [-\pi, \pi]$. As used already earlier, the radius follows a Rayleigh distribution, i.e.,

$$
\mathbb{P}(R > r) = \exp(-\lambda \theta r^2)
$$

and we note that, due to the isotopy of the model, $\Phi$ is uniformly distributed in $[-\theta, \theta]$. Hence,

$$
\begin{align*}
\mathbb{E}[\exp(\langle \gamma, U_1 \rangle)] &= \int_0^\infty dr \frac{1}{2\theta} \int_{-\theta}^\theta d\varphi \exp(\gamma_1 r \cos \varphi + \gamma_2 r \sin \varphi - \lambda \theta r^2) \lambda 2\theta r \\
&= \lambda \int_0^\infty dr r \exp(-\lambda \theta r^2) \int_{-\theta}^\theta d\varphi \exp(\gamma_1 r \cos \varphi + \gamma_2 r \sin \varphi),
\end{align*}
$$
as desired. In particular,

$$J_{\lambda,\theta}(\gamma) \leq 2\pi\lambda \int_{0}^{\infty} dr r \exp(-\lambda\theta r^2) \exp(r(\gamma_1 + \gamma_2)) < \infty.$$

The continuity follows from the fact, that the Legendre transform of strictly convex and continuously differentiable functions is differentiable and $J_{\lambda,\theta}$ is strictly convex and differentiable.

Further note that, writing $u = (r_u, \varphi_u)$ in polar coordinates,

$$e^{-\mathcal{I}_{\lambda,\theta}(u)} = \inf_{q \ge 0, \alpha \in [-\pi, \pi]} \int_{0}^{\infty} dr \int_{-\theta}^{\theta} d\varphi \lambda r \exp(-\lambda\theta r^2 + q[r\cos(\varphi - \alpha) - r_u \cos(\varphi_u - \alpha)])$$

and, if $\varphi_u \notin (-\theta, \theta)$, then we can always choose $\alpha_0 \in [-\pi, \pi]$ such that for all $\varphi \in [-\theta, \theta]$, we have $r \cos(\varphi - \alpha_0) - r_u \cos(\varphi_u - \alpha_0) \le 0$. One choice of $\alpha_0$ for example is given by

$$\alpha_0 = \begin{cases} \pi/2 + \theta & \text{if } \varphi_u \in [\theta, \pi], \\ -\pi/2 - \theta & \text{if } \varphi_u \in [-\pi, -\theta]. \end{cases}$$

Then, since

$$\int_{0}^{\infty} dr \int_{-\theta}^{\theta} d\varphi \lambda r \exp(-\lambda\theta r^2) < \infty,$$

by the dominated-convergence theorem, we obtain

$$e^{-\mathcal{I}_{\lambda,\theta}(u)} \le \lim_{q \to \infty} \int_0^\infty dr \int_{-\theta}^\theta d\varphi \lambda r \exp(-\lambda\theta r^2 + q[r\cos(\varphi - \alpha_0) - r_u \cos(\varphi_u - \alpha_0)]) \\ = \int_0^\infty dr \int_{-\theta}^\theta d\varphi \lim_{q \to \infty} \lambda r \exp(-\lambda\theta r^2 + q[r\cos(\varphi - \alpha_0) - r_u \cos(\varphi_u - \alpha_0)]) = 0.$$

Therefore, we get that $\mathcal{I}_{\lambda,\theta}(u) = \infty$ whenever $\varphi_u \notin (-\theta, \theta)$. A similar calculation also gives that $\mathcal{I}_{\lambda,\theta}(u) = \infty$ for $r_u = 0$. This implies that $\mathcal{I}_{\lambda,\theta}(u) = \infty$ for $u \notin C_\theta^o$.

Now, we show that $\mathcal{I}_{\lambda,\theta}(u) < \infty$ for $u \in C_\theta^o$. In that case, $r_u > 0$ and $\varphi_u \in (-\theta, \theta)$. For this, we pick $0 < \eta < \pi/16$ small enough such that $[\varphi_u - 4\eta, \varphi_u + 4\eta] \in (-\theta, \theta)$ and define two sets $A_\alpha$, $B_\alpha$ as

$$A_\alpha := \begin{cases} (r_u/(\sin \eta), \infty) & \text{if } |\alpha - \varphi_u| \le \pi/2 + \eta, \\ (0, r_u \sin \eta) & \text{if } |\alpha - \varphi_u| > \pi/2 + \eta, \end{cases}$$

and

$$B_\alpha := \begin{cases} [\varphi_u + 2\eta, \varphi_u + 3\eta] & \text{if } \alpha \in [\varphi_u, \varphi_u + \pi], \\ [\varphi_u - 3\eta, \varphi_u - 2\eta] & \text{if } \alpha \in [\varphi_u - \pi, \varphi_u). \end{cases}$$

Here, we consider the range of $\alpha$ as $[\varphi_u - \pi, \varphi_u + \pi]$ instead of $[-\pi, \pi]$ for simplicity. Now, for any $\alpha \in [\varphi_u - \pi, \varphi_u + \pi]$, $r \in A_\alpha$ and $\varphi \in B_\alpha$, we have $r \cos(\varphi - \alpha) - r_u \cos(\varphi_u - \alpha) \ge 0$. Therefore,

$$e^{-\mathcal{I}_{\lambda,\theta}(u)} \ge \inf_{\alpha \in [\varphi_u - \pi, \varphi_u + \pi]} \int_{A_\alpha} dr \int_{B_\alpha} d\varphi \lambda r \exp(-\lambda\theta r^2) > 0 \\ = \eta\lambda \min \left\{ \int_{0}^{r_u \sin \eta} dr r \exp(-\lambda\theta r^2), \int_{r_u/(\sin \eta)}^{\infty} dr r \exp(-\lambda\theta r^2) \right\} > 0,$$

which implies that for all $u \in C_\theta^o$ we have $\mathcal{I}_{\lambda,\theta}(u) < \infty$. This finishes the proof. $\square$

In order to establish certain bounds, it will be convenient to also have a large-deviation result for iid sequences of progress variables $\overline{U}_i = (X_i, |Y_i|)$ to our disposal.

**Lemma 7.** The sequence of iid copies $\{\overline{U}_i\}_{i \ge 1}$ of the progress variable $\overline{U}_1 \in \mathbb{R} \times \mathbb{R}_+$ satisfies the large-deviation principle with rate n and rate function

$$\overline{\mathcal{I}}_{\lambda,\theta}(u) := \sup\{\langle\gamma, u\rangle - \overline{\mathcal{J}}_{\lambda,\theta}(\gamma) : \gamma \in \mathbb{R}^2\},$$

where $\overline{\mathcal{J}}_{\lambda,\theta}(\gamma) < \infty$ for all $\gamma \in \mathbb{R}^2$.
Proof of Lemma 7. Using the same arguments as in the proof of Lemma 1, we have that

$$ \mathbb{E}[\exp(\langle \gamma, \bar{U}_1 \rangle)] = 2\lambda \int_0^\infty dr r \exp(-\lambda\theta r^2) \int_0^\theta d\varphi \exp(\gamma_1 r \cos \varphi + \gamma_2 r \sin \varphi) < \infty, $$

which, together with Cramér's theorem, gives the result. □

Proof of Theorem 2. The key observation is that the sequence of progress variables {$U_i$}$_{i \ge 1}$ is iid for $\theta < \pi/4$. Indeed, note that for all $i \ge 1$, $(C_\theta(V_i) \cap B(V_i, |U_{i+1}|)) \cap C_\theta(V_{i+1}) = \emptyset$. Hence, in every step, the navigation discovers a previous undiscovered region in space and the corresponding Poisson point clouds are stochastically independent.

**Step 1:** (Large deviations for iid steps.) Even though the progress steps are iid, the statement is not a direct application of, e.g., Cramér's theorem, since {$Y_t$}$_{t \ge 0}$ only tracks the vertical displacement, however there is also a random horizontal displacement. Let us write $U_i = (X_i, Y_i)$ where $X_i$ is the first and $Y_i$ the second Cartesian coordinate of $U_i$ and recall that $K_t := \sup \{n > 0: \sum_{i=1}^n X_i < t\}$ denotes the number of steps the navigation takes before reaching $t$ along the x-axis.

**Step 2:** (Lower bound for upper tail.) Let us start with the lower bound for the upper tail. It suffices to consider $a > 0$. Then, for all $1 > b > 0$, $c > 0$ and $\alpha > \beta > 0$,

$$ \begin{aligned} \mathbb{P}(\mathcal{Y}_t > at) &\ge \mathbb{P}(\mathcal{Y}_t > at, \lfloor \beta t \rfloor \le K_t < \lfloor \alpha t \rfloor) \\ &\ge \mathbb{P}\left(\sum_{i=1}^{\lfloor \beta t \rfloor} Y_i > at + \sum_{j=\lfloor \beta t \rfloor+1}^{\lfloor \alpha t \rfloor} |Y_j|, bt < \sum_{i=1}^{\lfloor \beta t \rfloor} X_i < t, \sum_{j=\lfloor \beta t \rfloor+1}^{\lfloor \alpha t \rfloor} X_j > (1-b)t\right) \\ &\ge \mathbb{P}\left(\sum_{j=\lfloor \beta t \rfloor+1}^{\lfloor \alpha t \rfloor} |Y_j| < ct, \sum_{j=\lfloor \beta t \rfloor+1}^{\lfloor \alpha t \rfloor} X_j > (1-b)t\right) \mathbb{P}\left(\sum_{i=1}^{\lfloor \beta t \rfloor} Y_i > (a+c)t, bt < \sum_{i=1}^{\lfloor \beta t \rfloor} X_i < t\right) \end{aligned} $$

by independence. Consequently, for $\delta = \alpha - \beta$,

$$ \begin{aligned} & \liminf_{t \uparrow \infty} t^{-1} \log \mathbb{P}(\mathcal{Y}_t > at) \\ & \ge -\delta \inf\{\overline{\mathcal{I}}_{\theta,\lambda}(x,y): x > (1-b)/\delta, y < c/\delta\} - \beta \inf\{\mathcal{I}_{\theta,\lambda}(x,y): b/\beta < x < 1/\beta, y > (a+c)/\beta\}. \end{aligned} $$

Sending $b$ to one and fixing $\delta = \delta(c)$ such that $c/\delta > \mathbb{E}[|Y_1|]$, the first summand vanishes and we have that

$$ \liminf_{t \uparrow \infty} t^{-1} \log \mathbb{P}(\mathcal{Y}_t > at) \ge -\beta \mathcal{I}_{\theta,\lambda}(1/\beta, (a+c)/\beta). $$

Sending $c$ to zero, we arrive at

$$ \liminf_{t \uparrow \infty} t^{-1} \log \mathbb{P}(\mathcal{Y}_t > at) \ge -\inf\{\beta \mathcal{I}_{\theta,\lambda}(1/\beta, a/\beta): \beta > 0\}. $$

This expression reflects that the process has to find the optimal compromise between making the right number of steps for the displacement along the y axis to be not too unlikely as well as hitting the time $t$ along the x axis.
**Step 3:** (Upper bound for upper tail.) For the upper bound, we can proceed similarly. For all $\alpha > 0$ we can bound,

$$
\begin{align*}
\mathbb{P}(\mathcal{Y}_t \ge at) &\le \mathbb{P}\left(\sum_{i=1}^{K_t} Y_i \ge at - |Y_{K_t+1}|, K_t \le \lfloor \alpha t \rfloor\right) + \mathbb{P}(K_t > \lfloor \alpha t \rfloor) \\
&= \sum_{m=0}^{\lfloor \alpha t \rfloor} \mathbb{P}\left(\sum_{i=1}^{m} Y_i \ge at - |Y_{m+1}|, K_t = m\right) + \mathbb{P}(K_t > \lfloor \alpha t \rfloor) \\
&\le \sum_{m=0}^{\lfloor \alpha t \rfloor} \mathbb{P}\left(\sum_{i=1}^{m} Y_i \ge t(a - \varepsilon), t(1 - \varepsilon) \le \sum_{i=1}^{m} X_i < t\right) + \mathbb{P}(B_{\varepsilon}^c(t)) + \mathbb{P}(K_t > \lfloor \alpha t \rfloor),
\end{align*}
$$

where $B_{\varepsilon}(t) = \{X_{m+1} \le \varepsilon t, |Y_{m+1}| \le \varepsilon t\}$ with $\varepsilon > 0$. Note that

$$
\limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}(B_{\varepsilon}^{c}(t)) = -\infty,
$$

since the upper tails of $|U_i|$ are of order $O(-t^2)$ on the exponential level. Further,

$$
\limsup_{\alpha \uparrow \infty} \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}(K_t > \lfloor \alpha t \rfloor) = \limsup_{\alpha \uparrow \infty} \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}\left(\sum_{i=1}^{\lfloor \alpha t \rfloor} X_i < t\right) = -\infty,
$$

and hence the error terms play no role on the exponential scale with rate $t$. Now, let $(t_n)_{n \ge 0}$ be a subsequence such that

$$
\limsup_{t \uparrow \infty} t^{-1} \log \sum_{m=0}^{\lfloor \alpha t \rfloor} \mathbb{P} \left( \sum_{i=1}^{m} Y_i \ge t(a-\varepsilon), t(1-\varepsilon) \le \sum_{i=1}^{m} X_i < t \right) \\
= \lim_{n \uparrow \infty} t_n^{-1} \log \sum_{m=0}^{\lfloor \alpha t_n \rfloor} \mathbb{P} \left( \sum_{i=1}^{m} Y_i \ge t_n(a-\varepsilon), t_n(1-\varepsilon) \le \sum_{i=1}^{m} X_i < t_n \right)
$$

and define

$$
\beta_{n,\varepsilon} := \underset{\alpha \uparrow \infty}{\operatorname{argmax}} \left\{ \mathbb{P} \left( \sum_{i=1}^{\lfloor \beta t_n \rfloor} Y_i \ge t_n(a-\varepsilon), t_n(1-\varepsilon) \le \sum_{i=1}^{\lfloor \beta t_n \rfloor} X_i < t_n \right) : 0 \le \beta \le \alpha \right\},
$$

where we simply take $\beta_{n,\varepsilon}$ to be the smallest solution in case of ambiguity. Then, for a suitable further sub-sequence $(t_{n_k})_{k \ge 0}$, we have that

$$
\begin{align*}
\lim_{n \uparrow \infty} t_n^{-1} \log \sum_{m=0}^{\lfloor \alpha t_n \rfloor} \mathbb{P} \left( \sum_{i=1}^{m} Y_i \ge t_n(a-\varepsilon), t_n(1-\varepsilon) \le \sum_{i=1}^{m} X_i < t_n \right) \\
&\le \limsup_{n \uparrow \infty} t_n^{-1} \log \mathbb{P} \left( \sum_{i=1}^{\lfloor \beta_{n,\varepsilon} t_n \rfloor} Y_i \ge t_n(a-\varepsilon), t_n(1-\varepsilon) \le \sum_{i=1}^{\lfloor \beta_{n,\varepsilon} t_n \rfloor} X_i < t_n \right) \\
&= \lim_{k \uparrow \infty} t_{n_k}^{-1} \log \mathbb{P} \left( \sum_{i=1}^{\lfloor \beta_{n_k,\varepsilon} t_{n_k} \rfloor} Y_i \ge t_{n_k}(a-\varepsilon), t_{n_k}(1-\varepsilon) \le \sum_{i=1}^{\lfloor \beta_{n_k,\varepsilon} t_{n_k} \rfloor} X_i < t_{n_k} \right)
\end{align*}
$$

and we note that $(\beta_{n_k, \varepsilon})_{k \ge 0}$ must contain a convergent sub-sequence $(\beta_{n_{k_l}, \varepsilon})_{l \ge 0}$ with limit $0 \le \beta_{\varepsilon}^* \le \alpha$. Hence,

$$
\lim_{l \uparrow \infty} t_{n_{k_l}}^{-1} \log \mathbb{P} \left( \sum_{i=1}^{\lfloor \beta_{n_{k_l}, \varepsilon} t_{n_{k_l}} \rfloor} Y_i \ge t_{n_{k_l}}(a-\varepsilon), t_{n_{k_l}}(1-\varepsilon) \le \sum_{i=1}^{\lfloor \beta_{n_{k_l}, \varepsilon} t_{n_{k_l}} \rfloor} X_i < t_{n_{k_l}} \right) \\
\le -\inf \{ \beta \mathcal{I}_{\theta, \lambda}(1/\beta, a/\beta) : \beta > 0 \},
$$

since $\limsup_{t \uparrow \infty} t^{-1} \log \lfloor \alpha t \rfloor = 0$ and we could use continuity.
**Step 4:** (General sets.) Note that, by symmetry, $\mathbb{P}(\mathcal{Y}_t \ge at) = \mathbb{P}(\mathcal{Y}_t \le -at)$ and hence, for $O \subset \mathbb{R}^2$ open, we have that for all $z = (x, y) \in O$, there exists $\varepsilon_z > 0$ such that $\bar{B}_{\varepsilon_z}(z) \subset O$. In particular, for all $z \in O$,

$$ \mathbb{P}(t^{-1}\mathcal{Y}_t \in O) \ge \mathbb{P}(z - \varepsilon_z < t^{-1}\mathcal{Y}_t < z + \varepsilon_z) = \mathbb{P}(t^{-1}\mathcal{Y}_t > -z - \varepsilon_z) - \mathbb{P}(t^{-1}\mathcal{Y}_t \ge -z + \varepsilon_z), $$

where the rate to zero is dominated by the first summand. Taking an infimum over $z \in O$ gives the desired result. The upper bound can be proved similarly.

**Step 5:** (Scaling.) If we denote by $\mathcal{Y}_{\lambda,t}$ the vertical displacement at time $t$ in the navigation based on a Poisson point process with intensity $\lambda > 0$, then, by scaling both the coordinates by $\sqrt{\lambda}$, we get that $\mathcal{Y}_{\lambda,t}$ and $\mathcal{Y}_{1,\sqrt{\lambda}t}/\sqrt{\lambda}$ are equal in distribution. Therefore, for any $x > 0$,

$$ \begin{aligned} I_{\lambda,\theta}(x) &= -\lim_{t\uparrow\infty} t^{-1} \log \mathbb{P}(t^{-1}\mathcal{Y}_{\lambda,t} > x) \\ &= -\lim_{t\uparrow\infty} \sqrt{\lambda}(\sqrt{\lambda}t)^{-1} \log \mathbb{P}((\sqrt{\lambda}t)^{-1}\mathcal{Y}_{1,\sqrt{\lambda}t} > x) = \sqrt{\lambda}I_{1,\theta}(x). \end{aligned} $$

By a similar calculation, we also get that for any $x < 0$, $I_{\lambda,\theta}(x) = \sqrt{\lambda}I_{1,\theta}(x)$. This proves the theorem. $\square$

# 5. APPENDIX

In this section, we study the large-deviation behavior of the model in the dependent case, where $\pi/4 < \theta < \pi/2$.

## 5.1. Large deviations for the dependent case.
First note that for all $\delta > 0$,

$$ \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P} \left( |\mathcal{Y}_t - \sum_{i=1}^{K_t} Y_i| \ge \delta t \right) = -\infty, $$

since

$$ \mathbb{P}\left(\left|\mathcal{Y}_t - \sum_{i=1}^{K_t} Y_i\right| \ge \delta t\right) \le 2\mathbb{P}(\tilde{Y}_1 \ge \delta t) \le C e^{-c(\delta t)^2}, $$

and hence, for the large deviations, we can focus on $\sum_{i=1}^{K_t} Y_i$. For this, note that we can split

$$ \sum_{i=1}^{K_t} Y_i = \sum_{i=1}^{K'_t} Y'_i + \sum_{j=\tau_{K'_t}^{\theta}+1}^{K_t} Y_j := \hat{\mathcal{Y}}'_t + \hat{Y}_t := \mathcal{Y}'_t. $$

The first summand is a sum of iid segments, but the second summand is a sum of dependent random variables. The challenge comes from the fact that all the involved random variable $Y'_i$, $\hat{Y}_t$ have exponential tails and therefore contribute on the large-deviation scale $t$. Let us start with the large deviations for the empirical average.

**Lemma 8.** For any $0 < \lambda$ and $\pi/4 < \theta < \pi/2$, $\{n^{-1}\sum_{i=1}^n U'_i\}_{n \ge 1}$ satisfies the large-deviation principle with rate $n$ and rate function

$$ \mathcal{I}'_{\lambda,\theta}(u) := \sup\{\langle\gamma, u\rangle - J'_{\lambda,\theta}(\gamma) : \gamma \in \mathbb{R}^2\}, $$

where, for all $\gamma \in \mathbb{R}^2$, $J'_{\lambda,\theta}(\gamma) := \log \mathbb{E}[\exp(\langle\gamma, U'_1\rangle)]$.

We present the proof of this lemma and the following statements in the next section. One would like to establish now a large-deviation principle for $\mathcal{Y}'_t$ similar to the one provided in Theorem 2. However, the situation is more complicated. The key reason for this is that the upper tails of $|U_1|$ are of order $O(-t^2)$ (this is crucially used in Step 3 in the proof of Theorem 2), however, the upper tails of $|U'_1|$ are only of order $O(-t)$, as can be seen from the following statement.
**Lemma 9.** Let $\pi/4 < \theta < \pi/2$, then, for all $n \ge 0$, $\mathbb{P}(\tau_1^\theta > n) \ge ((4\theta - \pi)/(4\theta))^n$.

We present the proof further below. As a consequence, for example for $X'_1$, we have for all $n$ and $s > 0$ that

$$ \mathbb{P}(X'_1 > t) \ge \mathbb{P}\left(\sum_{i=1}^{\tau_1^\theta} X_i > t, \tau_1^\theta > n\right) \ge \mathbb{P}(\tau_1^\theta > n) - \mathbb{P}\left(\sum_{i=1}^n \hat{X}_i \le t\right) \ge e^{an} - e^{st+n \log \mathbb{E}[\exp(-sX_1)]}, $$

where $a := \log((4\theta - \pi)/(4\theta))$ and the $\hat{X}_i$ are iid copies of $X_1$. Hence we have at least exponential decay if, for $n$ coupled to $t$ as $n = bt$ with $b > 0$, we have $s/b + \log \mathbb{E}[\exp(-sX_1)] < a$. But this is the case by first picking $s$ large and then picking $b$ large. We can proceed similarly for $Y'_1$.

Hence, it is reasonable to assume that we have the following tail behavior within a segment.

**Assumption 1.** Let $0 < \lambda$ and $\pi/4 < \theta < \pi/2$. Then, for all $a, b > 0$, we have that

$$ \lim_{t \uparrow \infty} t^{-1} \log \mathbb{P} \left( \sum_{i=1}^{[t]} X_i \ge at, \sum_{i=1}^{[t]} Y_i \ge bt, \tau_1^\theta > t \right) = -H_{\lambda, \theta}(a, b) \in (0, \infty). $$

Note that it is clear that the rate function must obey our usual scaling relation $H_{\lambda,\theta} = \sqrt{\lambda}H_{1,\theta}$. With this in mind, we can prove the large-deviation principle for $Y'_t$.

**Theorem 3.** Let Assumption 1 hold. Then, for any $0 < \lambda$ and $\pi/4 < \theta < \pi/2$, $\{t^{-1}\mathcal{Y}_t\}_{t \ge 0}$ obeys the large-deviation principle with rate $t$ and rate function

$$ I'_{\lambda, \theta}(x) := \inf_{b \in \mathbb{R}, c \in (0,1)} \left\{ \inf\{\beta \mathcal{I}'_{\lambda, \theta}(c/\beta, b/\beta) : \beta > 0\} + \inf\{dH_{\lambda, \theta}((1-c)/d, (a-b)/d) : d > 0\} \right\}. $$

Moreover, $I'_{\lambda, \theta}(x)$ satisfies the scaling relation $I'_{\lambda, \theta}(x) = \sqrt{\lambda}I'_{1, \theta}(x)$.

Let us try to explain the rate function in words. In the dependent case, the rate function is given by an optimization between the unlikely vertical displacement (up to level $b$, represented by the term involving $\mathcal{I}'_{\lambda, \theta}$), which is cheaper to achieve if the navigation performs fewer steps (up to level $c < 1$) and the, then necessary, cost produced by having an unlikely large last horizontal step (of length of order $(1-c)t$ that covers the remaining vertical displacement, represented by the term involving $H_{\lambda, \theta}$).

**Proof of Theorem 3.** We proceed again via several steps. First, by the initial observation in this section, it suffices to consider $\mathcal{Y}'_t$.

**Step 1:** (Upper bound for upper tail.) For all $\alpha > 0$ we can bound,

$$ \begin{aligned} \mathbb{P}(\mathcal{Y}'_t \ge at) & \le \mathbb{P}\left(\sum_{i=1}^{K'_t} Y'_i + \hat{Y}_t \ge at, K'_t \le \lfloor \alpha t \rfloor\right) + \mathbb{P}(K'_t > \lfloor \alpha t \rfloor) \\ & \le \sup_{0 < \beta \le \alpha} \alpha t \mathbb{P}\left(\sum_{i=1}^{[\beta t]} Y'_i + \hat{Y}_t \ge at, K'_t = \lfloor \beta t \rfloor\right) + \mathbb{P}(K'_t > \lfloor \alpha t \rfloor), \end{aligned} $$

where the second summand plays no role on the exponential scale with rate $t$ since

$$ \limsup_{\alpha \uparrow \infty} \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}(K'_t > \lfloor \alpha t \rfloor) = \limsup_{\alpha \uparrow \infty} \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}\left(\sum_{i=1}^{\lfloor \alpha t \rfloor} X'_i < t\right) = -\infty. $$

Similarly, for all $0 < \beta \le \alpha$,

$$ \limsup_{\gamma \uparrow \infty} \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}\left(\sum_{i=1}^{\lfloor \beta t \rfloor} Y'_i > \gamma t\right) = -\infty $$
and

$$ \limsup_{\delta \uparrow \infty} \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}(\tau_1^\theta > \delta t) = -\infty $$

and hence, it suffices to further bound as

$$ \begin{aligned} \mathbb{P}\left(\sum_{i=1}^{\lfloor\beta t\rfloor} Y'_i + \hat{Y}_t \ge at, K'_t = \lfloor\beta t\rfloor\right) &\le \sup_{|b|<\gamma, c<1} \gamma t^2 \mathbb{P}\left(\sum_{i=1}^{\lfloor\beta t\rfloor} Y'_i \hat{=} bt, \sum_{i=1}^{\lfloor\beta t\rfloor} X'_i \hat{=} ct\right) \times \\ &\quad \sup_{d \le \delta} \delta t \mathbb{P}\left(\sum_{i=1}^{\lfloor dt \rfloor} Y_i \ge (a-b)t, \sum_{i=1}^{\lfloor dt \rfloor} X_i \ge (1-c)t, \tau_1^\theta > dt\right) \\ &\quad + \mathbb{P}\left(\sum_{i=1}^{\lfloor\beta t\rfloor} Y'_i > \gamma t\right) + \mathbb{P}(\tau_1^\theta > \delta t), \end{aligned} $$

where we write $x \hat{=} y$ iff $\lfloor x \rfloor = \lfloor y \rfloor$ and used independence. Now, we can combine Assumption 1 and Lemma 8 to get

$$ \begin{aligned} & \limsup_{t \uparrow \infty} t^{-1} \log \mathbb{P}(\mathcal{Y}'_t \ge at) \\ &\le - \inf_{b \in \mathbb{R}, c \in (0,1)} \left\{ \inf\{\beta \mathcal{I}'_{\lambda,\theta}(c/\beta, b/\beta) : \beta > 0\} + \inf\{dH_{\lambda,\theta}((1-c)/d, (a-b)/d) : d > 0\} \right\} \end{aligned} $$

as desired.

**Step 2:** (Lower bound for upper tail.) Next, we consider the lower bound for the upper tail with $a > 0$. Then, for $b \in \mathbb{R}, 0 < c < 1$ and $\beta, d > 0$,

$$ \begin{aligned} \mathbb{P}(\mathcal{Y}'_t > at) &\ge \mathbb{P}\left(\sum_{i=0}^{K'_t} Y'_i > bt, K'_t = \lfloor\beta t\rfloor, \hat{Y}_t > (a-b)t\right) \\ &\ge \mathbb{P}\left(\sum_{i=0}^{\lfloor\beta t\rfloor} Y'_i > bt, \sum_{i=0}^{\lfloor\beta t\rfloor} X'_i \hat{=} ct\right) \mathbb{P}\left(\sum_{i=0}^{\lfloor dt \rfloor} Y_i > (a-b)t, \sum_{i=0}^{\lfloor dt \rfloor} X_i > (1-c)t, \tau_1^\theta > \lfloor dt \rfloor\right), \end{aligned} $$

where we used independence. Consequently,

$$ \liminf_{t \uparrow \infty} t^{-1} \log \mathbb{P}(\mathcal{Y}'_t > at) \ge -\beta \mathcal{I}'_{\lambda,\theta}(c/\beta, b/\beta) - dH_{\lambda,\theta}((1-c)/d, (a-b)/d). $$

Optimizing first with respect to $\beta$ and $d$ in the individual summands and then with respect to $b, c$ in the joint expression, we arrive at the desired lower bound which matches the upper bound.

**Step 3:** (General sets.) Using symmetry and the previous steps, we can follow the exact same arguments as in the independent case, Step 4 in the proof of Theorem 2, to arrive at the large-deviation principle.

**Step 4:** (Scaling.) A scaling argument similar to that in the proof of Theorem 2 implies that $I'_{\lambda,\theta}(x) = \sqrt{\lambda} I'_{1,\theta}(x)$ for all $x \in \mathbb{R}$. $\square$

## 5.2. Proofs of the supporting statements.

*Proof of Lemma 8.* The proof follows again from an application of the multivariate Cramér theorem for empirical means of sequences of iid random variables, see [7, Corollary 6.1.6]. We need to show existence of $\gamma = (\gamma_1, \gamma_2) \in \mathbb{R}^2 \setminus \{0\}$, such that $J'_{\lambda,\theta}(\gamma) < \infty$, but this is an immediate consequence of Lemma 2. $\square$
Proof of Lemma 9. Observe that, if for all $1 \le m \le n$, $\Phi_m \in (\pi/2-\theta, \theta]$, then, for all $1 \le m \le n$, $H_m \ne \emptyset$, which then ensures $\tau_1^\theta > n$. Therefore,

$$ \mathbb{P}(\tau_1^\theta > n) \ge \mathbb{P}(\Phi_m \in (\pi/2 - \theta, \theta] \text{ for all } 1 \le m \le n). $$

Note that, conditioned on $V_{m-1}$, $R_m$ and $H_{m-1}$, $\Phi_m$ is uniformly distributed on the set

$$ \{\varphi \in [-\theta, \theta] : V_{m-1} + (R_m, \varphi) \notin H_{m-1}\}. $$

Hence, with $\ell$ denoting the Lebesgue measure,

$$ \mathbb{P}(\Phi_m \in (\pi/2 - \theta, \theta] | V_{m-1}, R_m, H_{m-1}) = \frac{\ell(\{\varphi \in (\pi/2 - \theta, \theta] : V_{m-1} + (R_m, \varphi) \notin H_{m-1}\})}{\ell(\{\varphi \in [-\theta, \theta] : V_{m-1} + (R_m, \varphi) \notin H_{m-1}\})}. $$

Also, note that, if for all $1 \le i < m$, $\Phi_i > 0$, then $C_\theta^u(V_{m-1}) \cap H_{m-1} = \emptyset$. Therefore, in that case,

$$ \frac{\ell(\{\varphi \in (\pi/2 - \theta, \theta] : V_{m-1} + (R_m, \varphi) \notin H_{m-1}\})}{\ell(\{\varphi \in [-\theta, \theta] : V_{m-1} + (R_m, \varphi) \notin H_{m-1}\})} \ge \frac{\ell((\pi/2 - \theta, \theta])}{\ell([-\theta, \theta])} = \frac{2\theta - \pi/2}{2\theta} = \frac{4\theta - \pi}{4\theta}. $$

As a result, we get that

$$ \mathbb{P}(\Phi_m \in (\pi/2 - \theta, \theta] | \Phi_i \in (\pi/2 - \theta, \theta] \text{ for all } 1 \le i < m) \ge (4\theta - \pi)/(4\theta) $$

and thus,

$$ \begin{aligned} \mathbb{P}(\tau > n) &\ge \mathbb{P}(\Phi_m \in (\pi/2 - \theta, \theta] \text{ for all } 1 \le m \le n) \\ &= \prod_{m=1}^{n} \mathbb{P}(\Phi_m \in (\pi/2 - \theta, \theta] | \Phi_i \in (\pi/2 - \theta, \theta] \text{ for all } 1 \le i < m) \\ &\ge ((4\theta - \pi)/(4\theta))^n, \end{aligned} $$

which completes the proof. $\square$

## 6. ACKNOWLEDGEMENT

The authors would like to thank Christian Hirsch for many fruitful discussions about the topic and for mentioning important references. This work is supported by the Leibniz Association within the Leibniz Junior Research Group on *Probabilistic Methods for Dynamic Communication Networks* as part of the Leibniz Competition (grant no. J105/2020). The third author would also like to thank the grant *ERC NEMO* (grant no. 788851) of the research group DYOGENE at INRIA Paris.

## REFERENCES

[1] M. A. Arcones. Large Deviations of Empirical Processes. High Dimensional Probability III, Birkhäuser Basel, 205-223, 2003.

[2] S. Asmussen. Applied Probability and Queues: Stochastic Modelling and Applied Probability, 2nd ed. Applications of Mathematics (New York) 51, Springer, New York., 2003.

[3] F. Baccelli and C. Bordenave. The radial spanning tree of a Poisson point process. Ann. Appl. Probab., 17:305-359, 2007.

[4] N. Bonichon and J.-F. Marckert. Asymptotics of geometrical navigation on a random set of points in the plane. Adv. Appl. Probab., 43(4):899-942, 2011.

[5] C. Bordenave. Navigation on a Poisson point process. Ann. Appl. Probab., 18(2):708-746, 2008.

[6] D. Coupier, K. Saha, A. Sarkar and V. C. Tran. The 2d-directed spanning forest converges to the Brownian web. Ann. Probab., 49(1):435-484, 2021.

[7] A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability 38, Springer-Verlag Berlin Heidelberg, 1998.

[8] P. Eichelsbacher and M. Löwe. Moderate deviations for iid random variables. ESAIM: Probab. Stat., 7:209-218, 2003.

[9] C. Hirsch, B. Jahnel, P. Keeler and R. I. A. Patterson. Traffic flow densities in large transport networks. Adv. App. Probab., 49(4):1091-1115, 2017.

[10] F. den Hollander. Large Deviations. American Mathematical Soc., 2000.
[11] C. D. Howard and C. M. Newman. Euclidean models of first-passage percolation. *Prob. Theory Relat. Fields*, 108:153-170, 1997.

[12] B. Jahnel and W. König. Probabilistic Methods for Telecommunications. Birkhäuser Compact Textbooks in Mathematics, 2020.

[13] M. Ledoux. On moderate deviations of sums of iid vector random variables. *Ann. Inst. H. Poincaré Probab. Stat.*, 28:267-280, 1992.

[14] R. Roy, K. Saha and A. Sarkar. Scaling limit of a drainage network model on perturbed lattice. *arXiv:2302.09489*, 2023.

[15] R. Roy, K. Saha, A. Sarkar and V. C. Tran. Random directed forest and the Brownian web. *Ann. Inst. H. Poincaré Probab. Stat.*, 52(3):1106-1143, 2016.

[16] S. R. S. Varadhan. Large Deviations and Applications. *SIAM*, Philadelphia, 1984.

(Partha Pratim Ghosh) TECHNISCHE UNIVERSITÄT BRAUNSCHWEIG, UNIVERSITÄTSPLATZ 2, 38106 BRAUNSCHWEIG, GERMANY

Email address: p.pratim.10.93@gmail.com; partha.ghosh@tu-braunschweig.de

(Benedikt Jahnel) TECHNISCHE UNIVERSITÄT BRAUNSCHWEIG, UNIVERSITÄTSPLATZ 2, 38106 BRAUNSCHWEIG, GERMANY & WEIERSTRASS INSTITUTE BERLIN, MOHRENSTR. 39, 10117 BERLIN, GERMANY

Email address: benedikt.jahnel@tu-braunschweig.de

(Sanjoy Kumar Jhawar) INRIA PARIS, 2 RUE SIMONE IFF, 75012, PARIS, FRANCE

Email address: sanjoy-kumar.jhawar@inria.fr