Kevin Feeney

The Dacura Data Curation System

Keywords: Linked Data Quality Metrics, Data Curation, Visualization, Semantic Web

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.

Introduction

Consistency and accuracy of data is a very real concern in scaling datasets which leverage the web of data [START_REF] Zaveri | Quality assessment methodologies for linked open data[END_REF]. Harvesting and analyzing linked data can prove to be challenging due to schematic differences, incomplete and inaccurate information, entropy and the rapid pace of change [START_REF] Millard | Consuming multiple linked data sources: Challenges and Experiences[END_REF]. If the data collected is to be used to support real-world analysis and decision making, the quality of the data is a critical factor in determining confidence in the analytic results. Furthermore, if we are to build applications which are based upon such linked datasets, data-quality assurance guarantees (for example about property completeness and schematic conformance) facilitate software development and the construction of robust applications.

Collecting linked datasets which leverage the web of data and other big-data sources is, in general, an open ended challenge in that such datasets are rarely complete. The continuous emergence of new information sources and the publication of new datasets mean that there is a steady supply of new data that can be incorporated into harvested datasets to improve accuracy and coverage and to reflect changes over time. In this context, we are interested in scalability, not in terms of the size of the dataset that we are collecting, but scalability in terms of the volume of data that we leverage in constructing our dataset. This concept of scalability is particularly relevant in the linked data domain, where interlinking facilitates the construction of datasets based on multiple externally managed datasets [START_REF] Schultz | LDIF -A Framework for Large-Scale Linked Data Integration[END_REF]. Improving productivity and efficiency of data quality control is critical to achieving this scalability, both by enabling the incorporation of automated data-harvesting approaches into data-collection efforts and by minimizing the time and effort required by human dataset managers and by domain experts.

The general problem that Dacura addresses is that we want to collect and publish linked datasets and build applications that depend on that data. However, we also want to continually improve, refine and extend our dataset by incorporating more sources of data over time.

Use Case and Requirements

This section describes our use case, and how our quality-measurement requirements were derived. We wish to support an internationally distributed community of humanities and social science scholars who are collecting, improving, sharing, exploring and analyzing time series data describing historical human societies. This community is collaborating on the Seshat Global History Databank project [START_REF] Turchin | The SESHAT Databank Project: the 2014 Report[END_REF] (Fig. 1), which aims to encode time-series datasets describing the most important features of all human societies since Neolithic times. The scope of the project -over 100 researchers and approximately $10 million in total funding, divided across multiple autonomous collaborating projects, with a 10 year time-frame -is such that the data-collection process is necessarily incremental. All data will have the potential to be progressively improved and extended, to take advantage of the potentially large community of volunteers, and the large number of potential sources of data available on the web 00 from structured datasets in DBpedia, to details of archaeological finds encoded in databases, or described in academic publications stored in electronic archives. The overarching goal of our work is to harness the input of the community of human experts to most efficiently and productively transform the wealth of knowledge and data available into high-quality datasets and to provide visualisations, analysis and modelling, data-export and a variety of other tools based upon that data. The system must be dynamic because a requirement of the research program is to iteratively publish datasets which cover specific regions and time-slices and subsets of the Seshat variables and to evolve the datasets so that they improve progressively over time as their coverage is extended. From this goal, we derived the following general system objectives of Dacura: O1. To maximize our ability to expand and improve the dataset over time, including evolving the schema, without compromising tools built on top of the dataset. O2. To minimise the effort required to incorporate new human expertise and new sources of data into the curated dataset. O3. To detect inconsistencies in the dataset, areas where it is incomplete, areas where it does not adhere to best practice in linked data publication. O4. To provide mechanisms to improve the dataset over time in a controlled way, including generation of suggestions for amendments. O5. To track the progress on the dataset in terms of the rate of change and time to completion.

The specific requirements of the domain dictated further requirements:

Req. 1: RDF-based storage and publication of shared Linked Data datasets.

Req. 2: Workflows and tools for distributed authoring and enrichment of consistent, high-quality datasets. Req. 3: Domain-specific data visualisations of historical dynamics through a range of temporal and geographic frames. Req. 4: Data quality analysis and enforcement functions that assure high quality data is produced. Req. 5: Processes and tools that support the lifecycle of data, allowing for controlled change of datasets and schemata. Req. 6: Application-aware processes and tools that constrain data changes such that data consuming applications continue to function despite an evolving dataset.

The system under study consists of data acquisition, data enrichment, data lifecycle management, data publication and data visualisation, exploration and analysis tools built on top of the data. Data acquisition initially focused on semantic uplift of previously collected data in structured formats such as spreadsheets or databases to a common Linked Data vocabulary. The next stage of data acquisition will support the semi-automated generation of new datasets from raw historical sources such as online newspaper archives. This second acquisition stage must minimise the effort required from domain experts to create the dataset by automating retrieval/conversion tasks and allowing less knowledgeable contributors to validate and incrementally improve candidate time series data before experts finally authorise it.

In order to develop tools which could meet these requirements, data-quality analysis was identified as a critically important capability. Monitoring of dataquality as it passes through the various lifecycle stages is required if the final published data is to remain of high enough quality to support meaningful statistical analysis. Furthermore, to facilitate the development of robust visualisation and exploration tools on top of the data, certain thresholds of quality must be met (for example, completeness of a location property is often a pre-requisite for datasets to be meaningfully mapped) and data-quality monitoring is required in order to ensure that the curated dataset continues to meet these thresholds as it changes over time. The rest of this paper describes the data-quality measurement features that we developed through the Dacura platform in order to allow us to create work-flows to meet these requirements.

Dacura System and Quality Control

The Dacura system [START_REF] Feeney | Improving curated web-data quality with structured harvesting and assessment[END_REF] developed at TCD is a data curation system designed to support the harvesting, assessment, management and publication of high-quality Linked Open Data. The Dacura workflow is outlined in Fig. 2.

Data architects define schemas which describe the information contained within external sources. These sources can range from other Linked Open Data sources to unstructured text such as books, journal articles, and newspapers. These sources are entered into the candidate queue. Architects can define what processing steps, such as human review and automated data quality checking, are required for candidates to be accepted into the Dacura datastore as reports. These reports can then be analysed by domain experts, in order to transform potentially incomplete, incorrect, or incompatible reports into coherent summaries of the information which they contain. These expert-generated facts can then be published in various formats, such as data dumps, browseable catalogues, or interactive visualisations. The published representations are then viewed by data consumers, who can offer suggestions for modifications to the underlying schemas and corrections to the generated data. Dacura provides tools at all steps of the data lifecycle to support users in these various roles.

Automated data quality analysis is deployed to ensure that the data harvested by this process is high quality and to improve the usefulness of generated datasets [START_REF] Feeney | Improving curated web-data quality with structured harvesting and assessment[END_REF]. Updates to data are inspected to ensure that they contain valid content and formatting. Messages are characterised by operation type and graph, and then tested against semantic rules which describe data quality issues. The system finally checks user permissions to determine if users can directly update the datastore or add items to the report processing queue.

Experiments using the Dacura tool to measure the speed of production and quality of political violence datasets indicated large variability between the quality of data produced by different human volunteers [START_REF] Feeney | Improving curated web-data quality with structured harvesting and assessment[END_REF] which can significantly affect the overall quality of the dataset. As a consequence, it is evident that there is a need to implement live data quality control, something that provides data curators with tools to assess the quality of the data being produced during the harvesting process itself, and not only after the final results are present. This could ensure that good and reliable Linked Data will be available during all the data lifecycle processes.

Currently, development of the Dacura system is focused on providing tool support for the Seshat Global History Databank. This is a large-scale effort to provide historical time-series data for the entirety of human history from the development of agriculture to the present day, in order to test and explore models of social structures and change. Seshat currently uses a wiki to collect data, but this approach makes it difficult to collate the collected information in a format amenable to statistical analysis. Dacura provides a set of web-based tools to allow Seshat researchers to more quickly and easily enter their data, as well as storing it in a format which allows easy manipulation in order to test historical hypotheses.

Conclusion

In this paper we provide an overview of the Dacura system. This paper outlines the requirements that led to its construction, a brief overview of how it functions, and some details as to how it integrates with the Seshat wiki. The Dacura system is under continuous development, and will be undergoing trials with users in the autumn of 2016. These trials will be used to further develop and improve the system.

Fig. 1 .

 1 Fig. 1. Use Case -scholars creating, sharing and improving HSS data

Fig. 2 .

 2 Fig. 2. Basic Dacura Workflow and Roles.

Fig. 3 .

 3 Fig. 3. Screenshot of the Dacura Codebook Analysis Tool.


Oriane Blondel

Marcelo R Hilário

Renato S Dos Santos

Vladas Sidoravicius

Augusto Teixeira

Random walk on random walks: higher dimensions

Keywords: Random walk, dynamic random environment, law of large numbers, central limit theorem, large deviations, renormalization, regeneration AMS MSC 2010: Primary 60F15, 60K35, Secondary 82B41, 82C22, 82C44

 to higher dimensions and more general transition kernels without the assumption of uniform ellipticity or nearest-neighbour jumps. Specifically, we obtain a strong law of large numbers, a functional central limit theorem and large deviation estimates for the position of the random walker under the annealed law in a high density regime. The main obstacle is the intrinsic lack of monotonicity in higher-dimensional, non-nearest neighbour settings.

.

Introduction s:intro

Random walks on random environments are models for the movement of a tracer particle in a disordered medium, and have been the subject of intense research for over 40 years. The seminal works [START_REF] Kesten | A limit law for random walk in a random environment[END_REF][START_REF] Ya | The limit behavior of a one-dimensional random walk in a random environment[END_REF][START_REF] Solomon | Random walks in a random environment[END_REF], concerning one-dimensional random walk in static random environment (i.e., constant in time), established a rich spectrum of asymptotic behaviours that can be very different from that of usual random walks. In higher dimensions, important questions remain open despite much investigation. For excellent expositions on this topic, see [START_REF] Sznitman | Topics in random walks in random environment[END_REF][START_REF] Zeitouni | Lectures on Probability Theory and Statistics: Ecole d'Eté de Probabilités de Saint-Flour XXXI -2001[END_REF]. The dynamic version of the model, i.e., when the random environment is allowed to evolve in time, has been also studied for over three decades (see e.g. [START_REF] Boldrighini | Random walk in dynamic environment with mutual influence[END_REF][START_REF] Madras | A process in a randomly fluctuating environment[END_REF]). However, models with both space and time correlations have been only considered relatively recently. For an overview, we refer to the PhD theses [START_REF] Avena | Random walks in dynamic random environments[END_REF][START_REF] Santos | Some case studies of random walks in dynamic random environments[END_REF]. We will abbreviate "RWRE" for random walk in static random environment, and "RWDRE" for random walk in dynamic random environment.

Asymptotic results for RWDRE under general conditions were derived e.g. in [START_REF] Avena | Large deviation principle for onedimensional random walk in dynamic random environment: Attractive spin-flips and simple symmetric exclusion[END_REF][START_REF] Avena | Law of large numbers for a class of random walks in dynamic random environments[END_REF][START_REF] Bethuelsen | Absolute continuity and weak uniform mixing of random walk in dynamic random environment[END_REF][START_REF] Campos | Level 1 quenched large deviation principle for random walk in dynamic random environment[END_REF][START_REF] Hollander | Law of large numbers for non-elliptic random walks in dynamic random environments[END_REF][START_REF] Orenshtein | Zero-one law for directional transience of onedimensional random walks in dynamic random environments[END_REF][START_REF] Redig | Random walks in dynamic random environments: a transference principle[END_REF], often requiring uniform mixing conditions on the random environment (implying e.g. that the conditional distribution of the environment at the origin given the initial state uniformly approaches a fixed law for large times). This uniformity can be relaxed in particular examples, e.g. [START_REF] Bethuelsen | The contact process as seen from a random walk[END_REF][START_REF] Hollander | Scaling of a random walk on a supercritical contact process[END_REF][START_REF] Mountford | Random walks generated by equilibrium contact processes[END_REF] (supercritical contact process), or under additional assumptions, e.g. [START_REF] Avena | A class of random walks in reversible dynamic environments: antisymmetry and applications to the East model[END_REF][START_REF] Avena | Lˆ2-perturbed Markov processes and applications to random walks in dynamic random environments[END_REF] (spectral gap, weakly non-invariant) and [START_REF] Bethuelsen | Law of large numbers for random walks on attractive spin-flip dynamics[END_REF] (attractivity). But arguably, some of the most challenging random environments are given by conservative particle systems, due to their poor mixing properties. Such cases have been considered in [START_REF] Avena | Symmetric exclusion as a random environment: hydrodynamic limits[END_REF][START_REF] Avena | Explicit LDP for a slowed RW driven by a symmetric exclusion process[END_REF][START_REF] Avena | Transient random walk in symmetric exclusion: limit theorems and an Einstein relation[END_REF][START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF][START_REF] Dos | Non-trivial linear bounds for a random walk driven by a simple symmetric exclusion process[END_REF] (simple symmetric exclusion), and in [START_REF] Hilário | Random walk on random walks[END_REF][START_REF] Hollander | Random walk in a high density dynamic random environment[END_REF] (independent random walks). Each of these works imposes additional conditions and explores very specific properties of the environment in question. In particular, the works [START_REF] Hilário | Random walk on random walks[END_REF][START_REF] Hollander | Random walk in a high density dynamic random environment[END_REF][START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] introduce perturbative approaches, where parameters of the system are driven to a limiting value where the behaviour is known.

In the present paper, we consider as in [START_REF] Hilário | Random walk on random walks[END_REF] dynamic random environments given by systems of independent simple symmetric random walks. As mentioned above, asymptotic results for this model are challenging since the random environment is conservative and has slow and non-uniform mixing. We extend the results of [START_REF] Hilário | Random walk on random walks[END_REF] to higher dimensions and more general transition kernels. Additional difficulties arise in this setting due to the loss of monotonicity properties present in the one-dimensional, nearest-neighbour case. Our main results are a strong law of large numbers, a functional central limit theorem and large deviation bounds for the position of the random walker under the annealed law in a high density regime. As an additional application of our methods, we re-obtain a (slightly improved) ballisticity condition for (the discrete-time version of) the infection-spread model considered in [START_REF] Kesten | The spread of a rumor or infection in a moving population[END_REF]. Some tools developed in the present paper will be also used in the accompanying article [START_REF] Blondel | Random walk on random walks: low densities[END_REF]. (1.1) e:alphaisprob

Definition of the model and main results

For a fixed a realization of N , the random walker in random environment X = (X t ) t∈Z + is the Markov chain that, when at position x ∈ Z d at time t ∈ Z + , jumps to x + z ∈ Z d with probability α(N (x, t), z). Note that the chain is time-inhomogeneous when the random environment is dynamic. The law of X conditioned on N is called the quenched law, and the quenched law averaged over the law of N is called the annealed law.

We are interested in the case where N is given by the occupation numbers of a system of simple symmetric random walks in equilibrium. More precisely, fix ρ ∈ (0, ∞) and let (N (x, 0)) x∈Z d be an i.i.d. collection of Poisson(ρ) random variables. From each site x ∈ Z d , start N (x, 0) independent simple symmetric random walks (which can be lazy or not). The value of N (x, t), t > 0 is then defined as the number of random walks present at x at time t. The process N (•, t) is a Markov chain in equilibrium on the state-space (Z + ) Z d . As already mentioned, N has relatively poor mixing properties; for example, it can be shown that Cov(N (0, t), N (0, 0)) decays as t -d/2 when t → ∞.

Let | • | denote the 1 -norm on Z d . We will make the following assumptions on α:

Assumption (S): The set of possible steps

S := x ∈ Z d : ∃ k ∈ Z + , α(k, x) > 0 (1.
2) e:defcS is finite. We set R := max x∈S |x|, which we call the range of the random walk.

Assumption (D):

We assume that Denote by P ρ the joint law of N and X and by E ρ the corresponding expectation. We can now state the main result of the present paper.

v • := lim inf k→∞ x∈S α(k, x)x • e 1 > 0, ( 1
thm:main Theorem 1.1. For every v ∈ (0, v • ), there exists a ρ = ρ (α, v ) < ∞ large enough such that, for every ρ ≥ ρ , there exists a

v = v(α, ρ) ∈ R d with v • e 1 ≥ v and: (i) (Law of large numbers) lim t→∞ X t t = v P ρ -almost surely.
(1.5) e:lln (ii) (Functional central limit theorem) There exists a deterministic covariance matrix Σ = Σ(α, ρ) such that, under P ρ ,

X [nt] -v[nt] √ n t≥0 ⇒ B Σ (1.6) e:clt
where B Σ is a Brownian motion on R d with covariance matrix Σ and "⇒" denotes convergence in distribution as n → ∞ with respect to the Skorohod topology.

(iii) (Large deviation bounds) For every ε > 0, there exists c > 0 such that

P ρ X t t -v > ε ≤ c -1 exp{-c(log t) 3/2 } for all t ∈ N.
(1.7) e:ldb Theorem 1.1 may be interpreted as follows: Assumption (D) ensures that the random walker has a positive local drift in direction e 1 inside densely occupied regions of Z d . Theorem 1.1 shows that, when the density ρ is large enough, this behaviour "takes over", i.e., the random walker exhibits a macroscopic drift in direction e 1 , which introduces enough mixing for a law of large numbers and a central limit theorem to hold.

Note that the matrix Σ in item (ii) above might be zero; indeed, our assumptions on α do not exclude the case that X is deterministic. However, Σ will be non-zero as soon as X is non-trivial, and it will be non-singular under mild ellipticity assumptions such as e.g. sup k∈Z + α(k, ±e i ) > 0 for all 1 ≤ i ≤ d; see (5.17). The speed of the decay in (1.7) is not optimal, and only reflects the limitations of our methods.

As previously mentioned, one of the biggest obstacles to obtain Theorem 1.1 are the poor space-time mixing properties of the random environment. A method to overcome this difficulty in ballistic situations was developed in [START_REF] Hilário | Random walk on random walks[END_REF] for the high density regime in one dimension, see also [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] for a similar approach when the random environment is given by a one-dimensional simple symmetric exclusion process. However, these results rely on monotonicity properties of the random walker that are in general not valid in higher-dimensional and/or non-nearest neighbour settings. A coupling method (cf. [START_REF] Holmes | Random walks in degenerate random environments[END_REF], [START_REF] Bethuelsen | Law of large numbers for random walks on attractive spin-flip dynamics[END_REF]) can sometimes be used to deal with this problem, but is limited to cases where α belongs to a set of at most two transition kernels. Here we follow a different approach, exploiting properties of the random environment through more general renormalization and renewal schemes that also bypass the requirement of uniform ellipticity.

As another application of our methods, we provide a short proof of ballisticity for the one-dimensional discrete-time version of the model for the spread of an infection studied in [START_REF] Kesten | The spread of a rumor or infection in a moving population[END_REF]. In this model, particles can be of two types: healthy or infected. Fix ρ ∈ (0, ∞). At time zero, we place on each site of Z an independent number of particles, each distributed as a Poisson(ρ) random variable. Given the assignment of particles to sites, we declare all particles to the right of the origin to be healthy and all particles to its left, including those on the origin, to be infected. Then the system evolves as follows: each particle, regardless of its state, moves independently as a discrete-time simple symmetric random walk (with a fixed random walk transition kernel), and any healthy particle sharing a site with an infected particle becomes immediately infected. We are interested in the position Xt of the rightmost infected particle at time t ∈ Z + . Still denoting by P ρ the underlying probability measure, we obtain: p:infection Proposition 1.2. For any ρ > 0, there exist v > 0 and c > 0 such that

P ρ Xt < vt ≤ c -1 exp{-c(log t) 3/2 } for all t ∈ N. (1.8) e:infection
The above proposition offers a slight improvement to the deviation bound given in [START_REF] Kesten | The spread of a rumor or infection in a moving population[END_REF], which is an important ingredient in establishing finer results about the infection front. For example, a similar statement was used in [START_REF] Kesten | A shape theorem for the spread of an infection[END_REF] to prove a law of large numbers, and in [START_REF] Bérard | Fluctuations of the front in a one-dimensional model for the spread of an infection[END_REF] to establish a central limit theorem for (the continuous-time version of) Xt .

The rest of the paper is organized as follows. Section 1.2 below contains a short heuristic description of ideas used in our proofs. In Section 2, we give a particular construction of our model with convenient properties. In Section 3, we develop a renormalization procedure for general classes of observables, relying on a key decoupling result for the environment (Theorem 3.4 below) whose proof is given in Appendix A. Applications of the renormalization scheme to show ballisticity of the random walker and of the infection front, including the proof of Proposition 1.2, are discussed in Section 4. Finally, in Section 5 we define and control a regeneration structure for the random walker path and finish the proof of Theorem 1.1.

Throughout the text, we denote by c a generic positive constant whose value may change at each appearance. These constants may depend on all model parameters discussed above but, in Section 3 and in Appendix A, they will not be allowed to depend on ρ, as we recall in the beginning of these sections.

Proof ideas ss:proofideas

The proof of Theorem 1.1 is split into two main steps that can be informally described as: a ballisticity condition and a renewal decomposition. They are performed respectively in Sections 4 and 5. Let us now describe them in more detail.

Our first result for the random walker described above is reminiscent of the (T )condition of Sznitman (see [START_REF] Sznitman | Topics in random walks in random environment[END_REF]): in Theorem 4.1, we show that, for ρ large enough, X t •e 1 diverges to infinity in a strong sense, i.e., the random walker is ballistic. This is done via a renormalization argument. Once ballisticity has been established, our intuition tells us that, as time passes, the random walker will see "fresh environments" since the particles of the random environment have no drift; this informal description is made precise by defining a regeneration structure for the path of the random walker. Here this step must be performed differently from [START_REF] Hilário | Random walk on random walks[END_REF] because of the higher dimensions and non-nearest neighbour transition kernels. Moreover, because of the lack of monotonicity, the tail of the regeneration time must also be controlled differently.

Proposition 1.2 is proved using a similar argument as for Theorem 4.1. First, the problem is reduced to showing that, with large probability, we can frequently find particles near Xt , cf. Lemma 4.4. Indeed, this implies the existence of a density of times where Xt behaves as a random walk with a drift, which is enough because it always dominates a simple symmetric random walk. The reduced problem can then be tackled using the renormalization procedure, driving not ρ to infinity but the size of the window around Xt where we look for particles. See Section 4.2.

Construction

s:construction

In this section, we introduce a construction of the environment of simple random walks in terms of a Poisson point process of trajectories as in [START_REF] Hilário | Random walk on random walks[END_REF]. This construction provides a convenient way to explore certain independence properties of the environment. We also provide a construction for the random walker and discuss positive correlations of certain monotone observables of the environment (cf. Proposition 2.2 below).

Define the set of trajectories

W = w : Z → Z d : |w(i + 1) -w(i)| ≤ 1 ∀ i ∈ Z . ( 2

.1) e:def˙W

Note that the trajectories in W are allowed to jump in any canonical direction, as well as to stay put. We endow the set W with the σ-algebra W generated by the canonical coordinates w → w(i), i ∈ Z. Let (S z,i ) z∈Z d ,i∈N be a collection of independent random elements of W , with each S z,i = (S z,i ) ∈Z distributed as a double-sided simple symmetric random walk on Z d started at z, i.e., the past (S z,i -) ≥0 and future (S z,i ) ≥0 are independent and distributed as a simple symmetric random walk on Z d started at z (lazy or not).

For a subset K ⊂ Z d × Z, denote by W K the set of trajectories in W that intersect K, i.e., W K := {w ∈ W : ∃ i ∈ Z, (w(i), i) ∈ K}. This allows us to define the space of point measures

Ω = ω = i δ w i ; w i ∈ W and ω(W {y} ) < ∞ for every y ∈ Z d × Z , (2.
2) e:Omega endowed with the σ-algebra generated by the evaluation maps ω → ω(W K ), K ⊂ Z d ×Z.

Fix ρ ∈ (0, ∞) and let N (x, 0), x ∈ Z d be i.i.d. Poisson(ρ) random variables. Defining the random element ω ∈ Ω by we may verify that N has the distribution described in Section 1.

ω := z∈Z d i≤N (z,0) δ S z,i , (2.3
We enlarge our probability space to support i.i.d. random variables U y , y ∈ Z d × Z sampled independently from ω, where each U y is uniformly distributed in the interval [0, 1]. We then define P ρ to be the joint law of ω and U = (U y ) y∈Z d ×Z . Our configuration space may be thus identified as Ω := Ω×[0, 1] Z d ×Z , equipped with the product σ-algebra.

To define our random walker, recall Assumption (R) and let

p • (k) := inf ≥k α( , x • ), k ∈ Z + . (2.6) e:defpbulletk For each k ∈ Z + , fix a partition of [0, 1] into intervals I k x , x ∈ S such that |I k x | = α(k, x) and [0, p • (k)] ⊂ ≥k I x• . Finally, for y ∈ Z d × Z, we define Y y = (Y y ) ∈Z + by Y y 0 = y, Y y +1 = Y y + x∈S (x, 1)1 U Y y ∈I N (Y y ) x , ≥ 0. (2.7) e:defY For y = (x, t) ∈ Z d × Z we write X y for the projection of Y y into Z d , i.e., Y y = Y (x,t) = (X y , + t).
When y = 0 we omit it from the notation. One may verify that the random walker X = (X ) ∈Z + is indeed distributed as described in Section 1.

We discuss next an important property of our random environment: the FKG inequality (cf. e.g. [START_REF] Liggett | Interacting particle systems[END_REF] Corollary 2.12 p. 78). It states that monotone functions of ω are positively correlated. This result will be used in the proof of Lemma 5.4, which is an important ingredient to control the tail of the regeneration time constructed in Section 5. We first need the following definition.

d:monotone˙FKG Definition 2.1. A measurable function f : Ω → R is called non-decreasing if f (ω ) ≥ f (ω) whenever ω , ω ∈ Ω satisfy ω (B) ≥ ω(B)
for all B ∈ W, and it is called nonincreasing if -f is non-decreasing. If either f or -f is non-decreasing, we say that f is monotone. An event A ∈ σ(ω) is said to be non-decreasing, non-increasing or monotone if the corresponding property is satisfied by its indicator function 1 A .

The inequality reads as follows.

prop:FKG Proposition 2.2 (FKG inequality). Let f, g : Ω → R be bounded measurable functions that are either both non-decreasing or both non-increasing. Then

E ρ [f (ω)g(ω)] ≥ E ρ [f (ω)] E ρ [g(ω)] .
(2.8) e:FKG

Proof. One may follow the proof of Theorem 3.1 in [START_REF] Teixeira | Interlacement percolation on transient weighted graphs[END_REF].

We extend the notion of monotonicity to functions defined on Ω as follows.

d:monotone Definition 2.3. A measurable function f : Ω → R is called non-decreasing, non- increasing or monotone if, for all U ∈ [0, 1] Z d , the function ω → f (ω, U
) satisfies the same property in the sense of Definition 2.1, and analogously for events in σ(ω, U ).

Remark 2.4. Note that monotone functions in the sense of Definition 2.3 are not necessarily positively correlated under P ρ : consider e.g. the indicator functions of the events {U 0 ∈ (0, 1/2)} and {U 0 ∈ (1/2, 1)}. However, such monotone functions are positively correlated under the conditional law given U , as can be deduced from Proposition 2.2.

We give next a few other useful definitions. For a measurable function g : Ω → E (with E some measurable space), we will abuse notation by writing g to refer also to the random variable g(ω, U ), distributed according to the push-forward of P ρ . d:supported Definition 2.5. We say that the function g :

Ω → E is supported on the set K ⊂ Z d × Z if g(ω, U ) ∈ σ(N (y), U y : y ∈ K).
(2.9) e:defsupportedK

For y = (x, n) ∈ Z d × Z and w ∈ W , define the space-time translation θ y w as

θ y w(i) := w(i -n) + x, i ∈ Z. (2.

10) e:defthetaw

For A ⊂ W , θ y A is defined analogously, i.e., θ y A := w∈A {θ y w}. We may then define space-time translations operating on Ω as follows. For (ω, U ) ∈ Ω, let

θ y (ω, U ) := (θ y ω, θ y U ) where (θ y ω)(A) := ω(θ y A) ∀ A ∈ W, (θ y U ) u := U y+u ∀ u ∈ Z d × Z. (2.11) e:def˙theta
The translations of a measurable function g : Ω → E are then defined by setting

g y = θ y g := g • θ y .
(2.12) e:def˙gy

Note that θ y N (u) = N (y + u), and that the law of (ω, U ) is invariant with respect to the space-time translations, i.e., θ y (ω, U ) is distributed as (ω, U ) under P ρ for any y ∈ Z d × Z. In particular, the law of Y y -y in (2.7) does not depend on y since Y y = y + θ y Y .

Renormalization s:renormalization

In this section, we develop an important tool in the analysis of our model, namely, a multi-scale renormalization scheme. We will keep the setup reasonably general so that it may be used in future applications. An important consequence of the technique developed here is the ballisticity of the random walker (cf. Theorem 4.1), which is an essential ingredient for proving Theorem 1.1. All constants in this section will be independent of ρ, but may depend on other parameters of the model.

General procedure

To describe the renormalization procedure, we introduce the sequence of scales

L 0 = 10 50 and L k+1 = L 1/2 k L k , for k ≥ 0. (3.1) e:Lk
The choice of constants 10 50 and 1/2 appearing above is not crucial; many other choices would have been equally good for our purposes. Note that

L 1/2 k ≥ L 1/2 k ≥ 1 2 L 1/2 k for all k ≥ 0. (3.
2) e:lowerbound˙Lk

Fix R ∈ N. In the relevant applications, R will be taken as in Assumption (S). Given do we ever use R for something else?

a scale k, we will consider translations of the space-time boxes

B k,0 = [-2RL k , 3RL k ) d × [0, L k ) ∩ (Z d × Z). (3.3) e:Bk
More precisely, let

M k = {k} × (Z d × Z), k ≥ 0, (3.4)
be the set of indices of scale k and, for k ≥ 0, let

M ≥ k = k≥ k M k (3.5)
be the set of indices of all scales greater or equal to k. For m = (k, y) ∈ M k , we define the corresponding translation of the box B k,0

B m = B k,0 + L k y. (3.6) e:Bm
The base of the box B k,0 is given by the set

I k,0 = ([0, RL k ) d × {0}) ∩ (Z d × Z)
and its corresponding translations are We aim to bound the probability of certain events A m inductively in k. For this, we will need another definition, concerning the occurrence of A m in consecutive scales. Definition 3.2. Fix k ≥ 0 and a collection of events (A m ) m∈M ≥ k . This collection is said to be cascading if, for every k ≥ k and m ∈ M k+1 , we have

I m = I k,0 + L k y, for m = (k, y) ∈ M k , (3.7
A m ⊆ m 1 ↔ m m 2 A m 1 ∩ A m 2 , (3.8) e:cascading
where

m 1 ↔ m m 2 stands for pairs of indices m 1 , m 2 ∈ M k such that B m 1 , B m 2 ⊆ B m
and such that the vertical distance between the boxes

B m 1 , B m 2 is at least L k .
In the definition above, if m 1 = (k, y 1 ) and

m 2 = (k, y 2 ) with y 1 = (x 1 , t), y 2 = (x 2 , s) ∈ Z d × Z we say that the vertical distance between the boxes B m 1 and B m 2 is equal to [(|t -s| -1)L k + 1] + .
Intuitively speaking, the above definition says that the occurrence of A m implies that two similar events happened in well-separated boxes of the smaller scale. The imposition that the boxes indexed by m 1 and m 2 in (3.8) are vertically separated will be useful to decouple the events A m 1 and A m 2 via Theorem 3.4. Examples of cascading events will be given in Section 3.2.

Given a family (A m ) m∈M ≥ k , we will be interested in the following quantities:

p k (ρ) = sup m∈M k P ρ (A m ), k ≥ k. (3.9) e:pk
Let us also denote

ι k := exp 2 k≥ k L -1/16 k ∈ (0, ∞). (3.10) e:defiota
The next theorem is the main result that we will use in order to bound p k (ρ). Then, writing ρ * := ι k ρ and ρ * * := ι -1 k ρ, for all k ≥ k we have

p k (ρ) ≤ exp{-(log L k ) γ } ∀ ρ ≥ ρ *
in the non-increasing case, ∀ ρ ≤ ρ * * in the non-decreasing case.

(3.12) e:pk˙decay

The upper bound 3/2 appearing in Theorem 3.3 is not sharp; any number β satisfying (3/2) β < 2 would suffice (see (3.16) below).

The statement of the previous theorem has two different cases, depending on whether the events A m are non-increasing or non-decreasing. All applications considered in this paper concern non-increasing events, but we choose to keep the exposition general in order to be able to use our results in the accompanying paper [START_REF] Blondel | Random walk on random walks: low densities[END_REF].

One of the main ingredients for the proof of Theorem 3.3 is a recursion inequality for p k , cf. Lemma 3.5 below. As the cascading property suggests, the key to obtain such a recursion is to decouple pairs of events A m 1 and A m 2 supported in boxes that are well-separated in time. Recall however that the environment of simple random walks, being conservative, presents poor mixing properties, which makes decoupling hard. We overcome this difficulty using a "sprinkling technique", which consists in performing a change in the density of particles in the environment in order to blur the dependency between such events. Thus, up to an error term, we bound P ρ(A m 1 ∩ A m 2 ) by the product P ρ (A m 1 )P ρ (A m 2 ), where ρ is slightly different from ρ. This is the content of Theorem 3.4 below, which has different statements for the cases where the events A m are non-increasing or non-decreasing. The proof of Theorem 3.4 is given in the Appendix A, and is very similar to the proof of Theorem C.1 in [START_REF] Hilário | Random walk on random walks[END_REF].

E ρ(1+n -1/16 ) [f 1 f 2 ] ≤ E ρ(1+n -1/16 ) [f 1 ] E ρ [f 2 ] + C o diam(B) + n d e -2coρn
E ρ [f 1 f 2 ] ≤ E ρ [f 1 ] E ρ(1+n -1/16 ) [f 2 ] + C o diam(B) + n d e -2coρn
We may now identify the constant k o appearing in Theorem 3. and

C o L 2d+1 k e -(2-(3/2) 3/2 )(log L k ) γ + e -coL 1/16 k +(3/2) 3/2 (log L k ) 3/2 < 1 ∀ k ≥ k o . (3.16) e:defk˙o2
As anticipated, Theorem 3.4 leads to the following recursion inequality for p k . ) in the non-decreasing case.

(3.17

p k+1 (ρ) = sup m∈M k+1 P ρ(A m ) ≤ sup m∈M k+1 m 1 ↔ m m 2 P ρ(A m 1 ∩ A m 2 ) (3.1) ≤ L 1/2 k 2(d+1) sup m∈M k+1 sup m 1 ↔ m m 2 P ρ(A m 1 ∩ A m 2 ) Theorem 3.4 ≤ L d+1 k sup m 1 ,m 2 ∈M k P ρ(A m 1 )P ρ (A m 2 ) + C o L d k exp{-2c o ρL 1/8 k } Am's non-increas. ≤ C o L 2d+1 k p k (ρ) 2 + exp{-2c o ρL 1/8 k } , (3.19)
This finishes the proof of (3.18) in the first case. Now assume that the events A m are all non-decreasing. As before, we can estimate

p k+1 (ρ) = sup m∈M k+1 P ρ(A m ) ≤ sup m∈M k+1 m 1 ↔ m m 2 P ρ(A m 1 ∩ A m 2 ) ≤ C o L 2d+1 k p k (ρ) 2 + exp{-2c o ρL 1/8 k } . (3.20)
Since, by the definition of L 0 , ρ ≥ ρ/2, (3.18) follows.

Now that we know how large the sprinkling should be as we move from scale k + 1 to k in order to obtain a good recursive inequality for the p k 's, we will introduce a sequence of densities ρ k .

Given ρ k > 0, define ρ k for k ≥ k recursively by setting

ρ k+1 = ρ k (1 + L -1/16 k
) when the A m 's are all non-increasing,

ρ k (1 -L -1/16 k
) when the A m 's are all non-decreasing.

(3.21) e:rhok Note that, with the above definition, when the A m 's are non-increasing,

log ρ k = log ρ k + k i= k log(1 + L -1/16 i ) ≤ log ρ k + ∞ i= k L -1/16 i < log(ι kρ k) < ∞ (3.
22) e:rho˙star while, when the A m 's are non-decreasing, since e -2x ≤ 1 -x for all x ∈ (0, L

-1/16 0 ), log ρ k ≥ log ρ k -2 ∞ i= k L -1/16 i = log(ι -1 k ρ k) > -∞. (3.

23) e:rho˙star˙star

This shows that the sequence of densities ρ k is not asymptotically trivial.

We are now in position to prove Theorem 3. , then

p k (ρ k ) ≤ exp{-(log L k ) γ } implies p k+1 (ρ k+1 ) ≤ exp{-(log L k+1 ) γ }. ( 3

.24) e:assume˙inductio

To see why this is true, let us first use (3.18) in order to estimate To this end, we first claim that, for all k ≥ k, by (3.28) and that (3.18) holds for ρ k and ρ k+1 replacing ρ and ρ respectively (because the relation between ρ k+1 and ρ k is exactly as for ρ and ρ in Lemma 3.5) we conclude by (3.24), that (3.27) also holds with k + 1 replacing k. This concludes the induction step and the proof of the theorem.

p k+1 (ρ k+1 ) exp{-(log L k+1 ) γ } ≤ C o L 2d+1 k e -2(log L k ) γ + e -coρ k L 1/8 k exp{(log L k+1 ) γ }. ( 3
C o L 2d+1 k e -(2-(3/2) 3/2 )(log L k ) γ + e -coL 1/16 k +(3/2) 3/2 (log L k ) 3/2
ρ k ≥ L -1/16 k . ( 3

Constructing cascading events ss:cascading

We provide in this section a systematic way to construct certain collections of cascading events based on averages of functions of the random environment along Lipschitz paths. Our ultimate goal is to obtain Corollary 3.11 below, which provides in this context a short-cut to ballisticity-type results with minimal reference to the bulkier technical setup of the previous section.

Let us first describe the type of paths that we will consider. We say that a function σ : Z → Z d is R-Lipschitz if for any x, y ∈ Z, we have |σ(x) -σ(y)| ≤ R|x -y|. The set of R-Lipschitz paths is defined as Remark 3.7. In the remainder of this paper, we will only be interested in applications where H ≡ 1, which implies that every R-Lipschitz function starting in I m is an (m, H)crossing. The more general set-up to be used in [START_REF] Blondel | Random walk on random walks: low densities[END_REF] will allow us to consider only paths σ that coincide with the trajectory performed by the random walker. f:Bm˙cross

S := σ : Z + → Z d : σ(0) = 0, |σ(i + 1) -σ(i)| ≤ R ∀ i ∈ Z + , ( 3
σ : [n, ∞) ∩ Z → Z d is an m-crossing if (σ(n), n) ∈ I m (
I m B m
The following definition plays a central role in our construction. where g y = θ y g as in (2.12).

Given a scale k ≥ 0 and

v k ∈ [L -1/16 k
, 1], recursively define (compare with (3.21))

v k+1 = v k (1 -L -1/16 k ), k ≥ k. ( 3

.32) e:vforchi

Note that v k decreases monotonically to (see (3.23)) Note that the events defined by (3.34) are not necessarily adapted or monotone. However, as already anticipated, we have the following. . The first thing we note is that this inequality holds for all k ≥ k. This indeed follows by induction using the definition of v k exactly as for (3.28).

v ∞ := v k k≥ k(1 -L -1/16 k ) ∈ (0, 1). ( 3
Next we claim that:

if A m occurs for some m ∈ M k+1 , then there exist at least three elements

m i = (k, y i ) in M k , i = 1, 2, 3, with y i = (x i , s i ) ∈ Z d × Z and B m i ⊂ B m
satisfying s i = s j when i = j and such that A m i occurs for i = 1, 2, 3. Let us denote by σ j , j ∈ {1, . . . , J}, the restriction of σ to [n + (j -1)L k , n + jL k ) which is again an (m j , H)-crossing for an appropriate index m j in M k , with B m j ⊂ B m (see Figure 2). We now estimate

χ g σ = 1 L k+1 n+L k+1 -1 i=n g (σ(i),i) = 1 L k+1 J j=1 n+(j+1)L k -1 i=n+jL k g (σ(i),i) = L k L k+1 J j=1 χ g σ j (3.36) e:displace ≥ -2 L k L k+1 + v k L k L k+1 L k+1 L k -2 (3.38) e:displace ≥ v k -4 L k L k+1 = v k+1 + (v k -v k+1 ) -4 L k L k+1 ,
where, in the first inequality, we used the fact that, if A m i does not occur for some i ∈ {1, . . . , J}, then 1 ≥ χ g σ ≥ v k . From the definition of v k , we see that

v k -v k+1 = v k L -1/16 k ≥ 1 L 1/8 k ≥ 4 L 1/2 k = 4 L k L k+1 , (3.39) e:k2large
where for the second inequality we use L k ≥ 10 50 (cf. (3.1)). Substituting this into (3.38), we get χ g σ ≥ v k+1 so that A m cannot occur. This proves the claim (3.35). Thus, on the event A m , we may assume that there exist m 1 = (k, y 1 ), m 3 = (k, y 3 ) in M k where y 1 = (x 1 , s 1 ) and y 3 = (x 3 , s 3 ) with s 3 ≥ s 1 + 2 (meaning that the vertical distance between B m 3 and B m 1 is at least L k ) and such that both A m 1 and A m 3 occur. This finishes the proof of the lemma.

The events defined by (3.34) may be analysed with the help of Theorem 3.3 whenever they are adapted and monotone. We next give a complementary result stating that, whenever the conclusion of Theorem 3.3 holds for (A m ) m∈M ≥ k , it can be extended by interpolation to boxes of length L ∈ N (not necessarily of the form L k ). We first need to extend the above definitions.

For y ∈ Z d × Z and L ∈ N, let

B y,L = y + {[-2RL, 3RL) d × [0, L)} ∩ (Z d × Z) (3.40)
and similarly

I y,L = y + ([0, RL) d × {0}) ∩ (Z d × Z). (3.41) Given a function H : Ω × Z d → {0, 1} and y = (x, n), we define a (y, L, H)-crossing to be an R-Lipschitz function σ : [n, ∞) ∩ Z → Z d such that (σ(n), n) ∈ I y,L and h σ (j) = 1 for every j ∈ [n, n + L) ∩ Z.
If the function H is identically equal to one we simply say that σ is a (y, L)-crossing.

Finally, given σ a (y, L, H)-crossing, we let

χ g σ (ω, U ) := 1 L n+L-1 i=n g (σ(i),i) (ω, U ). ( 3

.42) e:chi˙g˙L

Our interpolation result reads as follows.

p:interpolate Proposition 3.10. (3.34). Fix ρ > 0, γ ∈ (1, 3/2] and assume that p k (ρ) = max

Fix k ≥ 0, v k ∈ [L -1/16 k , 1] and two functions g : Ω → [-1, 1], H : Ω × Z d → {0, 1}. Define (A m ) m∈M ≥ k by
m∈M k P ρ (A m ) ≤ exp {-(log L k ) γ } ∀ k ≥ k. ( 3

.43) e:assump˙interpol

Then, for every ε > 0, there exists c > 0 such that

P ρ (∃ a (0, L)-crossing σ s.t. χ g σ < v ∞ -ε) ≤ c -1 e -c(log L) γ ∀ L ≥ 1, (3.44) e:interpolate
where v ∞ is given by (3.33).

Proof. We follow the proof of Lemma 3.5 in [START_REF] Hilário | Random walk on random walks[END_REF]. We may assume L to be so large that, defining ǩ by 2Lǩ +2 ≤ L < 2Lǩ +3 , then ǩ ≥ k and

L k+1 L k > 1 + 2/ε for all k ≥ ǩ. We first consider multiples of L k , k ≥ ǩ. Define M k := {m ∈ M k : B m ⊂ B (k+2,0) }, (3.45) Bǩ := k≥ ǩ m∈M k A c m (3.46) and Jǩ := k≥ ǩ L k+2 /L k l=1 {lL k } ⊂ N. (3.47)
Let us see that Bǩ has high probability. Indeed,

P ρ B c ǩ ≤ k≥ ǩ m∈M k P(A m ) (3.43) e:printerp1 ≤ k≥ ǩ c L k+2 L k d+1 e -(log L k ) γ ≤ c -1 e -c(log L ǩ ) γ ≤ c -1 e -c(log L) γ , (3.48) e:printerp1
where for the last inequality we used that Lǩ ≥ L

(2/3) 3 ǩ+3 > 1 2 L (2/3) 3 . We now claim that: on Bǩ, for any L ∈ Jǩ and any ((0, L ), h)-crossing σ, we have

χ g σ ≥ v ∞ . ( 3

.49) e:LinJ

Let us prove this for fixed k ≥ ǩ by induction on l ≤ L k+2 /L k . For l = 1, the claim holds since any ((0, L k ), h)-crossing σ is indeed an (m, H)-crossing for m = (k, 0) so that, on the event A c m ⊂ Bǩ, we have

χ g σ ≥ v k ≥ v ∞ . Assume that it holds for L = lL k with 1 ≤ l < L k+2 /L k . Fix a ((0, (l + 1)L k ), h)-crossing σ.
Notice that there exists m ∈ M k such that (σ(lL k ), lL k ) ∈ I m . Therefore, σ restricted to times i = lL k , . . . , (l+1)L k -1 is an (m, H)-crossing and σ restricted to times i = 0, . . . , lL k -1 is a ((0, lL k ), h)-crossing. Hence, by induction and since we are on Bǩ, To this end, for n as in (3.51), define k = k(n) to be the smallest integer such that n ∈ [ lLk, ( l + 1)Lk) for some 1 ≤ l ≤ Lk +2 /Lk. Note that k ≥ ǩ and that, by the minimality of k, we have n ≥ Lk +1 and thus l ≥ 2/ε. Then estimate

(l+1)L k -1 i=0 g (σ(i),i) = lL k -1 i=0 g (σ(i),i) + (l+1)L k -1 i=lL k g (σ(i),i) ≥ v ∞ lL k + v k L k ≥ v ∞ (l + 1)L k , ( 3
n-1 i=0 g (σ(i),i) = lLk-1 i=0 g (σ(i),i) + n-1 i= lLk g (σ(i),i) ≥ v ∞ lLk -Lk = Lk((v ∞ -ε) l + ε l -1) ≥ Lk(v ∞ -ε)( l + 1) ≥ n(v ∞ -ε), (3.52)
where we used (3.49), |g| ≤ 1 and v ∞ ≤ 1. This finishes the proof.

We may now state our target corollary, which conveniently summarizes ballisticitytype results without explicit reference to most of the technical renormalisation setup. Recall (3.42) and the definition above.

cor:renormnoscales Corollary 3.11. Let (L k ) k∈Z + be given by (3.1). For any γ ∈ (1, 3/2], there exists an index 16 and, for any v > 0, the event there exists a (0, L, H)-crossing σ such that χ g σ ≤ v (3.53) e:H˙g˙non˙decr is measurable in σ(N (y), U y : y ∈ B 0,L ) and non-increasing (respectively non-decreasing). Assume additionally that, for some k ≥ k o such that L k ≥ L * ,

k o = k o (γ, d) ∈ N satisfying the following. Fix two functions g : Ω → [-1, 1], H : Ω × Z d → {0, 1} and two non-negative sequences v(L), ρ(L). Assume that, for some L * ∈ N and all L ≥ L * , v(L) ∧ ρ(L) ≥ L -1/
P ρ(L k ) (∃ a (0, L k, H)-crossing σ such that χ g σ ≤ v(L k)) ≤ exp(-(log L k) γ ). ( 3

.54) e:H˙g˙upper˙bound

Then there exist (explicit) ρ ∞ , v ∞ > 0 such that, for each ε > 0,

P ρ (∃ a (0, L, H)-crossing σ such that χ g σ ≤ v ∞ -ε) ≤ c -1 exp(-c(log L) γ ) (3.55)
for some c ∈ (0, ∞), all L ∈ N and all ρ ≥ ρ ∞ (respectively, all ρ ≤ ρ ∞ ).

Before we proceed to the proof, a few words about Corollary 3.11. Assumption (3.54) can be interpreted as a triggering condition, i.e., an a-priori estimate that must be provided in order to start the renormalisation procedure. The measurability and monotonicity assumptions must be checked in each case. Note that measurability follows whenever g and H(•, x) (for all x ∈ Z d ) are local (i.e., supported in a finite set in the sense of Definition 2.9) and instantaneous, where we say that a function f :

Ω → R is instantaneous if f (ω, U ) ∈ σ(N (z, 0), U (z,0) : z ∈ Z d ), i.
k := v(L k), define v k , k > k as in (3.32)
and v ∞ as in (3.33). For k ≥ k, let A m be defined as in (3.34) and p k (ρ) as in (3.9). Note that the events A m , for m ∈ M ≥ k as above are cascading, adapted and non-decreasing (resp. non-increasing) according to Lemma 3.9 and our assumptions.

Set now ρ := ρ(L k) and note that, by (3.54),

p k( ρ) ≤ exp -(log L k) γ . (3.56)
Therefore we can use Theorem 3.3 to conclude that, for some ρ ∞ > 0 (more precisely, ρ ∞ := ρ * in the non-increasing case, or ρ ∞ := ρ * * in the non-decreasing case),

p k (ρ) ≤ exp -(log L k ) γ , for every k ≥ k (3.57)
for any ρ ≥ ρ ∞ in the non-increasing case, or any ρ ≤ ρ ∞ in the non-decreasing case.

The conclusion then follows from Proposition 3.10.

Applications s:applications

This section is dedicated to applying the renormalization setup developed in Section 3 to show ballistic behavior of two processes. Namely, for a random walker in the environment of simple random walks and for the front of an infection process.

Random walker on random walks (large density)

In this subsection, we will prove a ballisticity result for the random walker in the environment of simple random walks, generalizing Theorem 1.5 of [START_REF] Hilário | Random walk on random walks[END_REF]. Let For any v ∈ (0, v • ), there exists ρ ∈ (0, ∞) and c > 0 such that, for all ρ ≥ ρ ,

H v,L := (x, n) ∈ Z d × Z : x • e 1 ≤ -L + vn . ( 4
P ρ (∃ n ≥ 0 : Y n ∈ H v ,L ) ≤ c -1 e -c(log L) 3/2 ∀ L ≥ 1. (4.
2) e:LD Theorem 4.1 will be proved by means of two propositions stated and proved below. Both the theorem and these intermediate results will be crucial to control the tail of the regeneration time constructed in Section 5.

The next proposition is very intuitive, stating that if the density is high enough then all paths stay most of their time on points with a large number of particles.

prop:enoughparticles Proposition 4.2 (Uniform density control along paths). For all K ∈ N and ε ∈ (0, 1), there exists c > 0 and ρ(K, ε) ∈ (0, ∞) such that, for all ρ ≥ ρ(K, ε),

P ρ ∃ ≥ L/(2R), σ ∈ S : -1 i=0 1 {N (σ(i),i)≥K} < (1 -ε) ≤ c -1 e -c(log L) 3/2 (4.
3) e:enoughparticles for all L ≥ 1.

Proof. Take k o as in the statement of Theorem 3.3 for γ = 3/2, and let k ≥ k o be large enough such that k≥ k

(1 -L -1/16 k ) ≥ 1 -ε/2. Choose v k := 1, g := 1 {N (0,0)≥K} ,
H ≡ 1 (thus, we will say only m-crossing instead of (m, H)-crossing). Define the family (A m ) m∈M ≥ k as in (3.34) and note that it is adapted and that each A m is non-increasing. For a fixed ρ > 0, consider the crude bound

p k( ρ) ≤ P ρ ∃(y, n) ∈ B L k such that N (y, n) < K ≤ (5RL k) d L kP ρ(N (0, 0) < K) ≤ (5RL k) d L kK (ρ ∨ 1) K e -ρ . (4.4)
For fixed K, k, we can choose ρ ≥ L -1/16 k such that the right-hand side of (4.4) is less than exp(-(log L k) 3/2 ). Therefore, by Theorem 3.3 and Proposition 3.10, there exists c > 0 such that, for all ρ ≥ ρ(K, ε) := ι k ρ (with ι k as in (3.10)) and all ≥ 1, P ρ there exists a (0, )-crossing σ with

-1 i=0 1 {N (σ(i),i)≥K} < (1 -ε) ≤ c -1 e -c(log ) 3/2
The proposition follows by noticing that the first steps of any σ ∈ S form a (0, )crossing, and then applying a union bound.

Our second proposition is a quenched deviation estimate for the position of the random walk. Intuitively speaking, it says that if all paths spend a large proportion of their time in sites with many particles, then the random walker itself has to move ballistically.

For technical reasons we first have to restrict our attention to the collection of paths that behave well in a certain sense. For L ∈ N and v ∈ (0, R], let S v,L be those paths of S that never touch H v,L . More precisely be the total drift accumulated along the path that starts at y and has increments given by σ up to time ∈ N. When σ = X y -x we omit it and write D ω . On (A L,v,K,ε y ) c , for all ≥ L/(2R) and all σ ∈ S v,L ,

S v,L := {σ ∈ S : (σ(i), i) / ∈ H v,L ∀ i ∈ Z + } . ( 4
D ω (σ) ≥ (v + 2δ ) -1 k=0 1 {N (y+(σ(k),k))≥K} -R -1 k=0 1 {N (y+(σ(k),k))<K} ≥ [v + 2δ -ε (v + R + 2δ )] > (v + δ ) ≥ (v + δ ) .
(4.11) e:propdrift by our choice of δ , k and ε . Note that, under P ρ (• |ω), the process

M := (X y -x) • e 1 -D ω = -1 k=0 (X y k+1 -X y k ) • e 1 -E ρ (X y k+1 -X y k )
• e 1 X y 0 , . . . , X y k , ω (4.12) e:defmartingale is a zero-mean martingale with respect to the filtration σ(X y 0 , . . . , X y ), and has increments bounded by 2R. Therefore, by Azuma's inequality and a union bound, there exists a c > 0 such that

P ρ (∃ ≥ L/(2R) : |M | ≥ δ | ω) ≤ c -1 e -cL ∀ L ∈ N.
(4.13) e:applyAzuma

Now we argue that, on (A L,v,K,ε y

) c , {∃ ≥ 0 : Y y -y ∈ H v,L } ⊂ {∃ ≥ L/(2R) : |M | ≥ δ } . (4.14) e:lastargquenched
Indeed, let 0 ∈ N be the smallest time satisfying Y y 0 -y ∈ H v,L . Then 0 ≥ L/(R+v) ≥ L/(2R). Setting σ = X y -x up to time 0 -1 and equal to an arbitrary R-Lipschitz path that does not touch H v,L for times greater than 0 , then σ ∈ S v,L and we obtain by (4.11) that, on (A L,v,K,ε y ) c , D ω 0 ≥ (v + δ ) 0 . If additionally |M 0 | < δ 0 would hold, then we would have a contradiction since where g r is as in (4.21) and χ gr σ as in (3.31). Then (1.8) holds for some some v, c > 0.

(X y 0 -x) • e 1 ≥ D ω 0 (σ) -|M 0 | > v 0 ⇒ Y y 0 -y / ∈ H v,L . ( 4
Proof. One can check from the definition of the rightmost infected particle that the increment Xn+1 -Xn always dominates that of a symmetric random walk on Z. At some steps, however, this increment has a drift to the right, namely when there is more than one particle at Xn . The idea of the proof will be to bound the number of times at which such positive drift is observed. We first note that the front starts close to the origin. Indeed,

P ρ X0 < - √ L = P ρ N (z, 0) = 0 ∀ z ∈ [- √ L, 0] ∩ Z ≤ ce -ρ √ L . (4.23) e:controlfrontat0
Now, at every time n at which there is another particle at distance at most r from the front Xn at a site with the same parity as Xn , we can use the Markov property to see that, with uniformly positive probability, this additional particle will reach the front within the next r steps. This means that, if n is such a time, the increment Xn +r+1 -Xn stochastically dominates (under the conditional law given (N (•, )) ≤n ) a random variable ζ with positive expectation satisfying |ζ| ≤ r + 1. We will show that v = hE[ζ]/(3(r + 1)) fulfills (1.8).

Consider the 1-Lipschitz path given by the front ( X ) L =0 . Denote by D the intersection of the event appearing in (4.22) with { X0 ≥ -√ L}. On D, we see that, for at least hL steps between times zero and L, the front X is r-close to another particle. Therefore, the same happens for at least k L := hL /(r + 1) steps that are at least r + 1 time units apart from each other, and we can estimate using the Markov property

P ρ [ XL < vL] ≤ P ρ (D c ) + P ρ (ζ 1 + • • • + ζ k L < 2vL + √ L) + P ρ (S 0,1 L-(r+1)k L < -vL),
where the ζ i 's are i.i.d. and distributed as ζ. Applying standard large deviation estimates to the sum of the ζ i 's and to S 0,1 , we see that

P ρ ( Xn < vL) ≤ P ρ (D c ) + c -1 exp{-cL}+ ≤ c -1 exp{-c(log L) 3/2 }, (4.24)
finishing the proof of the lemma.

We next present the proof of Proposition 1.2. In light of Lemma 4.4, all we need to prove is (4.22), and for this we will use the renormalization procedure developed in Section 3. One might try to obtain (4.22) by direct application of Theorem 3.3, defining the events A m in a natural way and then taking r large enough. There is however a serious problem with this approach: for large values of r, the family A m will no longer be adapted in the sense of Definition 3.1. To circumvent this issue, we define intermediate classes of events that will certainly be adapted, although not necessarily cascading. The details are carried out next.

Proof of Proposition 1.2. Given ρ > 0, let ρ := ι -1 0 ρ (cf. (3.10)). Fix h 0 = 1/2 and define inductively the sequence h k by h

k+1 = h k (1 -L -1/16 k ). Since h 0 ≥ L -1/16 0 , using (3.1) it follows by induction that h k ≥ L -1/16 k for every k ≥ 0. Moreover, h k decreases monotonically to h ∞ := (2ι 0 ) -1 > 0. For m ∈ M k , let A m = there exists an m-crossing σ such that χ g L k σ < h k . (4.25)
In the definition of A m we have used the local function g L k , which means that we are looking for particles on even sites at distance at most L k from the origin. Intuitively speaking, this task will become easier and easier to accomplish as k grows. This is made precise in the following claim: there exists a c > 0 such that

P ρ(A m ) ≤ c -1 exp{-cL k }, for every m ∈ M k , k ≥ 0. ( 4
P ρ (A m ) ≤ exp{-(log L k) 3/2 } since A m = A m for m ∈ M k.
Applying Theorem 3.3 and Proposition 3.10, we obtain, since ρ = ι 0 ρ ≥ ι k ρ and by translation invariance, Define now a filtration (F k ) k≥0 by setting, for k ≥ 0,

P ρ there exists a 1-Lipschitz path σ : [0, L) ∩ Z → Z that is either a (0, L)-crossing or a ((-L, 0), L)-crossing with χ g L k σ < h ∞ /2 ≤ c -1 e -c(log L)
F k := B ∈ σ(ω, U ) : ∀ y ∈ Z d × Z, ∃ B y ∈ F y with B ∩ {Y R k = y} = B y ∩ {Y R k = y} ,
(5.10) e:filtration2

i.e., the sigma-algebra generated by

Y R k , all U z with z ∈ ∠ (Y R k ) and all ω(A) such that A ⊂ W ∠ Y R k ∪ W Y R k . In particular, (Y i ) 0≤i≤R k ∈ F k .
Finally we define the event

A y = Y y i ∈ ∠(y) ∀ i ∈ Z + (5.11) e:Axt
in which the walker started at y remains inside ∠(y), the probability measure

P ∠ (•) = P • ω W 0 = 0, A 0 (5.
12) e:pmarrom with corresponding expectation operator E ∠ , the regeneration record index and the same holds with E ∠ replacing E.

I = inf k ∈ N : ω W Y R k = 0, A Y R
The proof of Theorem 5.1 follows exactly as that of Theorem 4.1 in [START_REF] Hilário | Random walk on random walks[END_REF] and thus we omit it here. Theorem 5.2 will be proved in the next section. From them follows the: Proof of Theorem 1.1. Using Theorems 5.1-5.2, one may follow almost word for word the arguments given in Section 4.3 of [START_REF] Hilário | Random walk on random walks[END_REF], with the difference of having now random vectors instead of real-valued random variables. In particular, we obtain the formulas

v = E ∠ [X τ ] E ∠ [τ ]
,

(5.16) e:formulav

Σ i,j = E ∠ [(X τ -vτ ) • e i (X τ -vτ ) • e j ] E ∠ [τ ]
(5.17) e:formulaSigma for the velocity v and the covariance matrix Σ, from which the comments made after Theorem 1.1 may be deduced. The fact that v • e 1 ≥ v follows from Theorem 4.1.

Control of the regeneration time ss:tailregeneration

In this section, we prove Theorem 5.2 by adapting Section 4.2 of [START_REF] Hilário | Random walk on random walks[END_REF] to our setting. The two most important modifications are as follows. First, in order to bypass the requirement of uniform ellipticity, we do not require the random walker to make jumps in a fixed direction independently of the environment but instead only over points containing enough particles. For this, we need to estimate the probability of certain joint occupation events, cf. Lemma 5.3 below. Second, we need a substitute for Lemma 4.5 of [START_REF] Hilário | Random walk on random walks[END_REF], which gave a quenched estimate on the backtrack probability of the random walker and was obtained therein using a monotonicity property only available in one dimension. This is the role of Lemma 5.4 below, obtained with the help of Propositions 4.2-4.3.

In our first lemma, we construct a path for the random walk to follow where all the points have a large number of particles. This has a cost that is at most exponential. Using now that, for any i = 0, . . . , L-1, the sets of trajectories W ix•,i \(W Lx•,L ∪W 0 ) and W Lx•,L \ (W (L+1)x•,L+1 ∪ W Lx•,L ) are disjoint, and using also the translation invariance of P, we see that the right-hand side of (5.20) equals

P L-1 i=0 ω W ix•,i \ (W Lx•,L ∪ W 0 ) ≥ k P ω W 0 \ (W x•,1 ∪ W 0 ) ≥ k ≥ c L+1 0
(5.21) by the induction hypothesis, concluding the proof.

Our next result is an estimate on the conditional backtrack probability of the random walker, which as already mentioned can be seen as a substitute for Lemma 4.5 of [START_REF] Hilário | Random walk on random walks[END_REF]. Recall the definition of v = v ∧ 1 2 .

A.3 Coupling of trajectories ss:couptraj

Given a sequence of points (x j ) j∈J in Z d , let (Z j n ) n∈Z + , j ∈ J, be a sequence of independent simple random walks on Z d starting at x j , and let j∈J P x j denote their joint law. The next lemma, analogous to Lemma B.3 in [START_REF] Hilário | Random walk on random walks[END_REF], provides a coupling of (Z j n ) j∈J with a product Poisson measure on Z d . l:couple Lemma A.4. There exists a constant c ≥ 1 such that the following holds. Let (x j ) j∈J ⊂ Z d be ρ-sparse with respect to the L-paving {C i } i∈I . Then for any ρ ≥ ρ there exists a coupling Q of ⊗ j∈J P x j and the law of a Poisson point process j ∈J δ Y j on Z d with intensity ρ such that

Q 1 H j∈J δ Z j n ≤ 1 H j ∈J δ Y j ≥ 1 -|H | exp -(ρ -ρ)L + cρL 2 (log n) d √ n
(A.12) for all finite H ⊂ Z d and all n ≥ cL 2 . Proof. By Lemma A.1, there exists a coupling Q such that where the last two inequalities are justified using n ≥ cL 2 ≥ L, Lemma A.3 and (A.3). Inserting this estimate into (A.14), we get the claim.

Q 1 H j∈J δ Z j n ≤ 1 H j ∈J δ Y j ≥ Q G J (z) ≤ ρ ∀ z ∈ H ,

  Denote by N = {1, 2, . . .} the set of positive integers and let Z + := {0} ∪ N. Fix d ∈ N and let N = (N (x, t)) x∈Z d ,t∈Z + be a random process with each N (x, t) taking values in Z + , which we call the random environment. Let α : Z + × Z d → [0, 1] satisfy x∈Z d α(k, x) = 1 for every k ∈ Z + .

. 3 )

 3 e:defvbullet where e 1 is the first of the canonical base vectors e 1 , . . . , e d of Z d . Assumption (R): There exists x • ∈ S satisfying x • • e 1 > 0 and lim inf k→∞ α(k, x • ) > 0. (1.4) e:condxbullet Assumption (D) means that, for sufficiently high particle density, the random walker has a local drift in direction e 1 . Assumptions (S) and (R) are technical; (S) simplifies the execution of many technical steps while (R) ensures some regularity for α(k, •) over large enough k ∈ N. Note that (R) follows from (D) if either α(k, •) is constant for sufficiently large k, or the random walker moves by nearest-neighbour steps, i.e., S ⊂ {x ∈ Z d : |x| ≤ 1}.

Figure 1 :

 1 Figure 1: The box B m for some m ∈ M k+1 . At the bottom we picture the corresponding base I m and, in the upper left corner, a box B m in the previous scale k.

Theorem 3 . 4 .

 34 There exist constants n o ∈ N, C o ≥ 1 and c o > 0, depending only on d and on the law of S 0,1 , such that the following holds. Let B = ([a, b] d × [n, n ]) ∩ Z d × Z be a space-time box satisfying n ≥ n o , and let D = Z d × Z -be the space-time lower half-space. Let f 1 , f 2 : Ω → [0, 1] be measurable functions supported respectively in D and B (cf. Definition 2.5). Denote by diam(B) the diameter of B. Then, for all ρ > 0: (a) If both f 1 and f 2 are non-increasing (cf. Definition 2.3), then

3 .

 3 Fix γ ∈ (1, 3/2] and let n o , C o , c o as given by Theorem 3.4. Then fix k o = k o (d, γ) ∈ Z + such that L ko ≥ n o (3.15) e:defk˙o1

Lemma 3 . 5 .

 35 Fix γ ∈ (1, 3/2] and let k o ∈ Z + as in (3.15)-(3.16). Fix k ≥ k o and a collection (A m ) m∈M ≥ k that is adapted and cascading. Assume that the A m 's are either all non-increasing or all non-decreasing. For fixed ρ > 0 and k ≥ k, define

  ) e:barrho Then we have p k+1 (ρ) ≤ C o L 2d+1 k p k (ρ) 2 + exp{-c o ρL 1/8 k } , (3.18) e:induction where C o , c o are as in Theorem 3.4. Proof. We start with the case when the A m 's are all non-increasing. Using that the A m 's are adapted and cascading and that, by (3.15), L k ≥ n o , we apply Theorem 3.4 to the indicator functions of A m 1 , A m 2 to obtain

3 .

 3 Proof of Theorem 3.3. Given γ ∈ (1, 3/2], take k o as in (3.15)-(3.16). The first step in the proof is to show how one can use (3.18) to transport the bound p k (ρ k ) ≤ exp{-(log L k ) γ } to the scale k + 1. This can be summarized by saying that: if (3.18) e:assume˙induction holds with ρ = ρ k ≥ L -1/16 k

  .25) e:conseq˙induc0 Now, since ρ k ≥ L -1/16 k and by (3.1), (3.25) is at most

( 3 .

 3 [START_REF] Liggett | Interacting particle systems[END_REF] e:conseq˙induc which is smaller than 1 by (3.16), proving(3.24).Let us now see how (3.12) follows from (3.24) and Lemma 3.5. Let ρ k = ρ (from (3.11)) and define ρ k for k ≥ k through(3.21). We claim that, for all k ≥ k,p k (ρ k ) ≤ exp {-(log L k ) γ } . (3.27) e:ineqwithk Then (3.12) follows since, by the definition of ι k and (3.22)-(3.23), if ρ ≥ ι kρ k and the A m 's are non-increasing (resp. ρ ≤ ι -1 k ρ k and the A m 's are non-decreasing), then p k (ρ) ≤ p k (ρ k ). Thus we only need to prove (3.27).

  .28) e:rhokdoesnotdeca Indeed, if the A m 's are all non-increasing, then ρ k ≥ ρ k ≥ L of ρ k while, if the A m 's are all non-decreasing, then (3.28) follows by induction using (3.21), (3.1) and the assumption that ρ ≥ L -1/16 k . Let us now prove (3.27) by induction on k. The case k = k holds by hypothesis. Assume now that (3.27) holds for some k ≥ k. Noting that ρ k+1 ≥ L -1/16 k+1

  recall the definition of B m and I m in (3.6) and (3.7)). In addition, if for H : Ω × Z d → {0, 1} we have h σ (j) = 1 for all j ∈ [n, n + L k ) ∩ Z, we say that σ is an (m, H)-crossing.

Figure 2

 2 Figure 2 illustrates an (m, H)-crossing. Note that an (m, H)-crossing does not exit B m through its sides. Furthermore, if m ∈ M k+1 , every (m, H)-crossing induces L k+1 /L k (m i , H)-crossings for m i ∈ M k such that B m i ⊂ B m . Note that in the particular case where H ≡ 1 the notions of m-crossing and (m, H)-crossing coincide.

Figure 2 :

 2 Figure 2: The box B m for some m ∈ M k+1 and an illustrative m-crossing σ.

Definition 3 . 8 .L k n+L k - 1 i=ng

 381 Given g : Ω → [-1, 1], an index m ∈ M k and an m-crossing σ : [n, ∞) ∩ Z → Z d , we define the average χ g σ of g along σ by χ g σ (ω, U ) := 1 (σ(i),i) (ω, U ), (3.31) e:chi˙g

  .33) e:defvinfty Given g : Ω → [-1, 1], H : Ω × Z d → {0, 1} and an integer k ≥ k, define the events A m = there exists an (m, H)-crossing σ such that χ g σ < v k , m ∈ M k . (3.34) e:A˙m˙with˙chi

Lemma 3 . 9 .

 39 The family (A m ) m∈M ≥ k defined by (3.34) is cascading. Proof. Fix k ≥ k and recall that we have assumed v k ≥ L -1/16 k

( 3 .

 3 35) e:A˙k+1˙k Indeed, assume by contradiction that there are at most two elements m = (k, y ), m = (k, y ) in M k with y = (x , s ) and y = (x , s ), s = s and B m , B m contained in B m for which the events A m and A m happen. (3.36) e:at˙most˙two Let σ be an (m, H)-crossing. We split its domain into disjoint intervals of length L k : {n, . . . , n+L k+1 -1} = J j=1 {n+(j -1)L k , . . . , n+jL k -1}, where J = L k+1 /L k , (3.37)

  e., f depends only on one time slice of the random environment. Proof of Corollary 3.11. Let k o ∈ N be as in the statement of Theorem 3.3, and fix k ≥ k o satisfying L k ≥ L * and (3.54). Setting v

. 1 )Theorem 4 . 1 (

 141 Ballisticity condition).

. 5 ) 1 i=0 1

 511 e:deffrakSLv For K ∈ N, ε > 0 and y ∈ Z d × Z, let A L,v,K,ε y := ∃ ≥ L/(2R), σ ∈ S v,L :-{N (y+(σ(i),i))≥K} < (1 -ε) .

( 4 . 6 )Proposition 4 . 3 ( 1 - 1 k=0d

 464311 Quenched deviation estimate). For all v ∈ (0, v • ), there exist k ∈ N, ε ∈ (0, 1) and c > 0 such that, for all ρ ∈ (0, ∞), y ∈ Z d × Z, v ≤ v and K ≥ k , P ρ -almost surely, if the event A L,v,K,ε y does not occur thenP ρ ∃ ≥ 0 : Y y -y ∈ H v,L ω ≤ c -1 e -cL . (4.7) e:quencheddev Proof. Let y = (x, n) ∈ Z d × Z be fixed. Fix δ ∈ (0, 1) satisfying v + 2δ < v • . By Assumption (D), there exists a k ∈ N such that inf k≥k z∈S α(k, z)z • e 1 > v + 2δ . (4.8) e:largedriftafterksTake ε ∈ (0, 1) small enough such that 2(R + 1)ε < δ , and fixK ≥ k , v ≤ v . For (z, l) ∈ Z d × Z, let d ω (z, l) := E ρ (X (z,l) z) • e 1 ω = u∈S u • e 1 α(N (z, l), u)(4.9) e:deflocaldrift denote the quenched local drift in direction e 1 at the point (z, l). For σ ∈ S, let D ω (σ) := ω (y + (σ(k), k)) (4.10) e:deftotaldrift

  .15) e:contradiction This shows (4.14), and the conclusion follows by (4.13).

Lemma 4 . 4 .

 44 Fix ρ > 0 and r ≥ 0 and suppose that, for some h ∈ (0, 1), c > 0,P ρ χ gr σ ≥ h for every 1-Lipschitz path σ : {0, . . . , L} → Z with |σ(0)| < L ≥ 1 -c -1 e -c(log L) 3/2 ∀ L ≥ 1, (4.22) e:always˙close

c:probfill l:probfill Lemma 5 . 3 .

 53 There exists c 0 ∈ (0, 1) such that, for all L ∈ N,P ω W ix•,i \ (W Lx•,L ∪ W 0 ) ≥ k ∀ i = 0, . . . , L -1 ≥ c L 0 .(5.18) e:probfillProof. We proceed by induction in L. Recall the definition of S 0,1 in Section 2 and letc 0 := P (N (0) ≥ k ) P S 0,1 n / ∈ ∠ (0) ∪ ∠(x • , 1) ∀ n ∈ Z k > 0. (5.19) e:prprobfill2 Since P ω W 0 \ (W x•,1 ∪ W 0 ) ≥ k ≥ c 0 , the claim holds for L = 1. Assume that it holds for some L ≥ 1. Noting that ∠((i + 1)x • , i + 1) ⊂ ∠(ix • , i), write P L i=0 ω W ix•,i \ (W (L+1)x•,L+1 ∪ W 0 ) ≥ k ix•,i \ (W Lx•,L ∪ W 0 ) ≥ k ∩ ω W Lx•,L \ (W (L+1)x•,L+1 ∪ W Lx•,L ) ≥ k .(5.20) e:prprobfill1

2 . 1 - 1 .( 1 -

 2111 (A.13) e:coupleGG where G J (z) = j∈J ξ j p n (x j , z) with (ξ j ) j i.i.d. Exp(1) random variables. WriteQ ∃ z ∈ H : G J (z) > ρ ≤ |H | sup z∈H Q[G J (z) > ρ ] ≤ |H | e -ρ L sup z∈H E Q exp{LG J (z)} . (A.14) e:QGJz If n ≥ cL 2 with large enough c ≥ 1, then, by (A.3), sup x∈Z Lp n (0, x) ≤ 1 (A.15) e:localclt2Thus we may write, for any z ∈ Z,E Q exp{LG J (z)} = j∈J E Q exp{ξ j Lp n (x j , z)} = j∈J Lp n (x j , z) -(A.16) Using (A.15) and -log(1 -x) ≤ x + x 2 for all x ∈ [0, 1/2], we obtain j∈J Lp n (z, x j )) -1 ≤ j∈J exp Lp n (z, x j ) 1 + Lp n (z, x j ) ≤ exp j∈J Lp n (z, x j ) 1 + sup x∈Z Lp n (0, x) ≤ exp ρL 1 + cL(log n) d

  For any γ ∈ (1, 3/2], there exists k o = k o (d, γ) ∈ Z + such that the following holds. Fix k ≥ k o and a collection (A m ) m∈M ≥ k that is adapted and cascading. Assume that the A m 's are either all non-increasing or all non-decreasing and that, for some ρ ≥ L

	t:pk˙decay	Theorem 3.3. -1/16
		k

, p k( ρ) ≤ exp{-(log L k) γ }. (

3

.11)

e:kprime˙rhoprime

  .29) e:deffrakSWe will further restrict the class of paths using a function H : Ω × Z d → {0, 1} as follows. Given such a function H and a path σ : [n, ∞) → Z d , we define, for t ≥ n,

h σ (t) := H(θ (σ(t),t) (ω, U ), σ(t + 1) -σ(t)).

(3.30)

The interpretation is that h σ (t) = 1 if and only if the jump σ(t + 1) -σ(t) is allowed by the random environment according to the rule H. The formal definition is as follows.

Definition 3.6. Given a box index m ∈ M k , we say that an R-Lipschitz function

  .50) completing the induction step and proving(3.49).We now prove (3.44). In fact, we show that on Bǩ, χ g σ ≥ v ∞ -ε for any (0, n)-crossing σ with n ≥ 2Lǩ +2 .(3.51) e:printerp˙end

  .26) e:A˙prime˙m˙decay Indeed, this follows from a union bound over the points of the box B m together with a simple large deviations estimate on the sum of independent Poisson(ρ) random variables.

	g L k σ	< h k .	(4.28)

By (4.26)

, there exists a ko ∈ N such that

P ρ(A m ) ≤ exp{-(log L k ) 3/2 }, for every m ∈ M k , k ≥ ko . (

4

.27) e:A˙prime˙m˙decay

As mentioned above, the family A m may not be cascading, however it is clearly adapted. We now define another collection that will indeed be cascading. Let k o as in the statement of Theorem 3.3 and take k ≥ k o ∨ ko . Then define, for k ≥ k and m ∈ M k ⊂ M ≥ k, A m = there exists an m-crossing σ, such that χ e:A˙m˙notprime Note here that the local function g L k is fixed, i.e. it does not depend on the scale k associated with m. This allows us to employ Lemma 3.9 and conclude that the family (A m ) m∈M ≥ k is cascading. (4.29) e:A˙m˙cascading

Moreover, this collection is adapted and composed of non-increasing events. In view of (4.27) and (4.29), we have p k( ρ) := sup m∈M k

Acknowledgments. OB acknowledges the support of the French Ministry of Education through the ANR 2010 BLAN 0108 01 grant. MH was partially supported by CNPq grants 248718/2013-4 and 406659/2016-8 and by ERC AG "COMPASP". RSdS was supported by the German DFG project KO 2205/13-1. AT was supported by CNPq grants 306348/2012-8 and 478577/2012-5 and by FAPERJ grant 202.231/2015. OB, MH and RSdS thank IMPA for hospitality and financial support. AT and MH thank the CIB for hospitality and financial support. RSdS thanks the ICJ for hospitality and financial support. The research leading to the present results benefited from the financial support of the seventh Framework Program of the European Union (7ePC/2007-2013), grant agreement n o 266638. Part of this work was carried on while MH was on a sabbatical year on the University of Geneva. He thanks the mathematics department of this university for the financial support. OB and AT thank the University of Geneva for hospitality and financial support.

We can now finish the: Proof of Theorem 3.4. The proof of item (a) can be obtained by adapting Appendixes B-C of [16] to higher dimensions as follows. First of all, (B.1)-(B.3) therein should be substituted by their d-dimensional counterparts (A.3)-(A.5) above. Definition B.1 therein should be substituted by the ρ-dense analogue of Definition A.2 above, i.e., changing "≤" to "≥" in (A.7). One may then follow the arguments given in [16] to reobtain Lemmas B.2-B.3 therein with the following differences: in both (B.6) and (B.10) therein, log n should be substituted by (log n) d (analogously to Lemmas A.3-A.4 above). The proof of Theorem 3.4(a) then follows from these results exactly as in the proof of Theorem C.1 in [16]. The proof of Theorem 3.4(b) is completely analogous, following from Lemma A.4 above as Theorem C.1 in [16] follows from Lemma B.3 therein.

and that the probability of the right-hand side of (4.16) does not depend on y.

Infection ss:infection

In this subsection, we prove Proposition 1.2 regarding the front of the infection process described in the introduction. We start with a precise construction of the model.

Fix ρ > 0, d = 1 and let N (z, 0) and S z,i be as in Section 2, i.e., (N (z, 0)) z∈Z are i.i.d. Poisson(ρ) random variables and (S z,i -z) z∈Z,i∈N are i.i.d., each distributed as a double-sided simple symmetric random walk on Z started at 0.

We also introduce random variables η(z, i, n) ∈ {0, 1} to indicate whether the particle corresponding to S z,i is healthy (η(z, i, n) = 0) or infected (η(z, i, n) = 1) at time n. We will define them recursively as follows. Set the initial configuration to be η(z, i, 0) = 1 if z ≤ 0 and i ≤ N (z, 0), (4.17) η(z, i, 0) = 0 otherwise. (4.18) Supposing that, for some n ≥ 0, η(z, i, n) is defined for all z ∈ Z, i ∈ N, we set η(z, i, n + 1) =    1 if i ≤ N (z, 0) and there exists z ∈ Z, i ∈ N with η(z , i , n) = 1, S z ,i n = S z,i n , 0 otherwise. (4.19) e:defeta This definition means that, whenever a collection of particles share the same site at time n, if one of them is infected then they will all become infected at time n + 1.

We are interested in the process X = ( Xn ) n∈Z + defined by Xn = max{S z,i n : η(z, i, n) = 1}, (4.20) e:defbarX i.e., Xn is the rightmost infected particle at time n. We call X the front of the infection.

Note that the process η differs slightly from that described in the introduction, where particles sharing a site with an infected one were required to become immediately infected. However, it is easy to check that the process X is not affected by this difference, and we choose to work with η for simplicity.

Our first result towards Proposition 1.2 is a reduction step, stating that it suffices to find, with high probability, enough times n when the front Xn of the infection process is close to another particle. For this we fix r ≥ 0 and define g r by

that is, g r is the indicator function of the event that, at time zero, there are at least two particles at even sites within distance r from the origin. Our lemma reads as follows.

5 Regeneration: proof of Theorem 1.1

s:regmanyRWshighdim

In this section, we adapt Section 4 of [START_REF] Hilário | Random walk on random walks[END_REF] to our setting using Propositions 4.2 and 4.3. Theorem 1.1 will then follow as a consequence of the resulting renewal structure. Hereafter, we fix v ∈ (0, v • ) and take k ∈ N and ∈ (0, 1) as in Proposition 4.3. We then define ρ := ρ(k , ) as given by Proposition 4.2 and Theorem 4.1. We will also fix ρ ≥ ρ and write P := P ρ from now on. By Assumption (R) and Proposition 4.3, we may assume that For y ∈ R d × R, we define the following space-time regions:

where R is as in Assumption (S). As in [START_REF] Hilário | Random walk on random walks[END_REF], we define the sets of trajectories

W y = trajectories in W that intersect both ∠(y) and ∠ (y).

(

Note that W ∠ y , W ∠ y and W y are disjoint, and therefore the sigma-algebras

) e:sigmaalgebrastra are jointly independent under P. Define also the sigma-algebras

) e:sigmaalgebrauni and set

(5.8) e:sigmaalgebraFxt

Note that, for two space-time points y, y ∈ Z d × Z, if y ∈ ∠ (y ) then F y ⊂ F y . In order to define the regeneration time, we first need to introduce certain record times (R k ) k∈N . The definition here will be different from the one in [START_REF] Hilário | Random walk on random walks[END_REF]. To this end, set R 0 := 0 and, recursively for k ∈ N 0 ,

(5.9) e:records

l:no˙top Lemma 5.4. There exists a constant c 1 > 0 such that

(5.23) e:prnotop3

Recall (2.6) and the discussion below it. Put L := (1 -v )L and abbreviate

a.s.

(5.25) e:prnotop1.5

by Proposition 4.3 (recall that v ≤ v ). Substituting this back into (5.24) and using that B L y , A L y (L) ∈ σ(ω), C L y ∈ σ(U ), we obtain that (5.24) is a.s. larger than

when L is large enough. Reasoning as for equation (4.16) in [START_REF] Hilário | Random walk on random walks[END_REF], we see that, P-a.s.,

where

(5.28) e:prnotop6 Since B L 0 and ( A L Lx•,L ) c are functions of ω only and are both non-decreasing, it follows from Proposition 2.2 and Lemma 5.3 that (5.27) is at least

(5.29) e:prnotop7

Now note that, by Proposition 4.2,

(5.30) e:prnotop8

for some constant c > 0. For fixed L large enough, (5.30) is smaller than 1/2, and thus (5.22) follows from (5.24)-(5.30) with c 1 := 1 4 (c 0 p ) L .

We proceed with the adaptation of Section 4.2 of [START_REF] Hilário | Random walk on random walks[END_REF]. As in equation (4.21) therein, we define the influence field and we define the local influence field at a space-time point y ∈ Z d × Z to be:

Note that our definition is slightly different from that of [START_REF] Hilário | Random walk on random walks[END_REF]. As in Lemma 4.4 therein, we obtain: l:locinfl Lemma 5.6. For all T > 1 and all y ∈ Z d × Z, Proof. Note that h T (y) is independent of F y-( (v/R)T x•, (v/R)T ) and h T (y) ≤ h(y).

As in [START_REF] Hilário | Random walk on random walks[END_REF], an important definition is that of a good record time (g.r.t.): Note that, when (5.38) occurs,

With the above definitions and results in place, only minor modifications are required to adapt the rest of Section 4.2 of [START_REF] Hilário | Random walk on random walks[END_REF] to our setting. For completeness, we provide below all the details.

The following proposition is the main step in the proof of Theorem 5.2.

c:manygrts p:manygrts Proposition 5.7. There exists a constant c 4 > 0 such that, for all T > 1 large enough,

(5.41)

Proof. First we claim that there exists a c > 0 such that, for any k > T , Proof of (5.43): For B ∈ F k-T , write

). Thus we may upper-bound (5.47) by

for some constant Ĉ > 0, where for the first inequality we use Lemmas 5.4 and 5.6 (see also the comment after (5.8)), and for the second we use the definition of . Thus, for T large enough, (5.43) is satisfied with c = c 1 /2. Proof of (5.44): Let B L y as in (5.23) and note that B T y , (U y+(lx•,l) ) l∈Z + and F y are jointly independent. For B ∈ F k , write

to conclude that (5.38) is independent of F k . Then (5.44) follows by Lemma 5.3 and (5.34). Proof of (5.45): We may ignore the conditioning on (5.38) since this event is independent of (5.39) and F k . For B ∈ F k , write

where the second equality uses the independence between G ∠ y and F y . Proof of (5.46): For B ∈ F k+T , write

(5.52) e:manygrts6 by our choice of and δ.

The proof of Theorem 5.2 can then be finished as in [START_REF] Hilário | Random walk on random walks[END_REF].

Proof of Theorem 5.2. Since P ∠ (•) = P(•|A 0 , ω(W 0 ) = 0) and P(A 0 , ω(W 0 ) = 0) > 0, it is enough to prove the statement under P. To that end, let

Then, by Lemma 5.5, (4.2) and a union bound, there exists a c > 0 such that

(5.54) prtailreg2

Next we argue that, for all T large enough, if R k is a good record time with k ≤ (v/R)T and both E 1 and E 2 do not occur then τ ≤ R k+T ≤ T . Indeed, if T ≤ vT /R, then on under the conditions stated.

To verify (5.56), note that, on

which together with (5.40) implies (5.56).

To verify (5.55), first note that, by (5.37) and (5.39), it is enough to check that (5.58) follows from the definitions of E 1 and of h.

In conclusion, for T large enough we have

≤ c -1 e -c(log T ) 3/2 + e -c 4 (vT ) 1/2 (5.59) prtailreg8 from which (5.15) follows.

A Decoupling of space-time boxes s:decouple

The aim of this section is to prove Theorem 3.4. The proof is very similar to the proof of Theorem C.1 in [START_REF] Hilário | Random walk on random walks[END_REF]; only the most important changes are described here. In the following subsections, we will concentrate on intermediate results required for item (b) of Theorem 3.4, i.e., the case where f 1 , f 2 are both non-decreasing. The non-increasing case will be discussed in the proof of Theorem 3.4 itself at the end of this Appendix. The constants in this section will be all independent of ρ; this is crucial for the perturbative arguments of Section 3.

A.1 Soft local times ss:SLT

We start with a coupling result. For a Polish space Σ and a Radon measure µ on Σ, let m denote the Poisson point process on Σ × R + with intensity measure µ ⊗ dv, where dv is the Lebesgue measure on R + . We write m = i∈N δ z i ,v i with (z i , v i ) ∈ Σ × R + .

Fix a sequence of independent Σ-valued random elements Z j , j ∈ N. Assume that the law of Z j is absolutely continuous with respect to µ with density g j . As in Appendix A of [START_REF] Hilário | Random walk on random walks[END_REF], we define the soft local times G j : Σ → [0, ∞), j ∈ N by setting

This construction can be used to prove the following.

l:couplesystem

Lemma A.1. The random variables (ξ j ) j∈N in (A.1) are i.i.d. Exp(1). Furthermore, there exists a coupling Q of (Z j ) j∈N and m such that, for any J ∈ N, ρ > 0,

for all compact H ⊂ Σ.

Proof. Follows from Proposition A.2 in [START_REF] Hilário | Random walk on random walks[END_REF] (compare to Corollary A.3 therein).

A.2 Simple random walks ss:SRW

As in [START_REF] Hilário | Random walk on random walks[END_REF], we will need some basic facts about the heat kernel of random walks on Z d . Let p n (x, x ) = P x (S x,1 = x ), x, x ∈ Z d , with P z , S z,i as defined in Section 2. Hereafter we will assume that S 1,0 is lazy; non-lazy S 1,0 are bipartite, and the argument below may adapted as outlined in Remark C.4 of [START_REF] Hilário | Random walk on random walks[END_REF]. Lazy S 1,0 are aperiodic in the sense of [START_REF] Lawler | Random walk: a modern introduction[END_REF], and thus there exist constants C, c > 0 such that the following hold for all n ∈ N: The above inequalities will be used to prove Lemma A.3 below, regarding the integration of the heat kernel over a sparse cloud of sample points. In order to state it, we need the following definitions. In the above definition, by interval, we mean a subset of Z d that is a Cartesian products of intervals of Z.

The next lemma provides an estimate of the sum of the heat kernel over a sparse collection (x j ) j∈J .

l:integration

Lemma A.3. There exists c > 0 such that the following holds. Let {C i } i∈I be an Lpaving and (x j ) j∈J be ρ-sparse collection with respect to {C i } i∈I . Then, for all n ≥ L,


Kevin Feeney
email: feeneyk1@tcd.ie

Rajan Verma
email: vermar1@tcd.ie

Max Brunner

Andre Stern
email: andrestern88@gmail.com

Odhran Gavin
email: gavino@tcd.ie

Declan O'sullivan
email: declan.osullivan@tcd.ie

Rob Brennan
email: rbrenna@tcd.ie

Automated Monitoring of Data Quality in Linked Data Systems

Keywords: Linked data quality metrics, Data curation, Visualization, Semantic

This paper describes the Dacura system's ability to monitor data quality. This is evaluated in an experiment where a dataset of historical political violence is collected, enriched, interlinked, and published. The results of the experiment demonstrate that automated quality measures enable the construction of publication pipelines which allow datasets to evolve rapidly without loss of quality.

Introduction

Ensuring high-quality data is a difficult task. Most large-scale data sources contain a significant amount of inconsistent data, due to differences in encoding and available information, and human error. The Dacura system [START_REF] Feeney | Improving curated web-data quality with structured harvesting and assessment[END_REF] developed at TCD is a data curation system designed to support the harvesting, assessment, management and publication of high-quality Linked Open Data. We wish to support an internationally distributed community of humanities and social science scholars collaborating on the Seshat Global History Databank project [START_REF] Turchin | The SESHAT databank project: the 2014 report[END_REF], which aims to encode time-series datasets describing the most important features of all human societies since Neolithic times. The scope of the projectover 100 researchers and approximately $10 million in total funding, divided across multiple autonomous collaborating projects, with a 10 year time-frameis such that the data-collection process is necessarily incremental.

The goal of our work is to harness the input human experts to efficiently transform the wealth data into high-quality datasets and to provide visualisations, analysis and modelling, data-export and a variety of other tools based upon that data. The system must be dynamic because a requirement of the research program is to iteratively publish datasets which cover specific regions and time-slices and subsets of the Seshat variables and to evolve the datasets so that they improve progressively over time as their coverage is extended.

The goal of the experimental work described here was to use the Dacura system to create and improve a linked dataset of historical political violence events. The source of data was a database of 1599 events that took place between the years of 1784 and 2010, collected by Peter Turchin [START_REF] Turchin | Dynamics of political instability in the United States, 1780-2010[END_REF]. This database had been manually compiled and was of unknown quality. We applied an uplift script to import it into the Dacura system. We then used Dacura to assess the quality of the data and to improve this quality wherever possible using a pool of non-expert volunteers. The goal was to use this labour as efficiently as possible to improve the quality of the dataset.

The first step where Dacura's quality assessment features were used was immediately after uplift. The RDF generated by this step was tested for conformance with the Political Violence schema. This process immediately identified a problem with the dataset which was traced back to a bug in the uplift script. When this was fixed and the basic Dacura quality control check rerun, the dataset passed the quality checks. However, the accuracy of the data itself remained an unknown quantity.

The next stage in the data-quality improvement process was to load the dataset through our visualization application. Upon cursory observation, a number of inconsistencies were found. The locations of the events had been encoded as simple text strings in the original database and the structure of these strings varied, meaning that in many cases they could not be mapped to structured linked data location properties. Furthermore, the way that these properties were encoded varied over the course of the data-collection process, which made their mapping to real locations less reliable. The next challenge was to modify the dataset to improve these location properties to such an extent that they would be sufficiently accurate for analytics -we aimed to produce at least 90 % accuracies.

In order to achieve this improvement, we combined a selection of Dacura's automated and manual tools. We used Dacura's dataset interlinking tool to generate links between our dataset and DBpedia, based on the location in the original database. Where it proved impossible to match our strings to DBpedia location, we used Google's autocomplete API to suggest location names. We then ran a series of experiments where we got volunteers to go through the records in the dataset, using the automated interlinking tools that Dacura provided, to assist them in choosing the correct location.

To evaluate these experiments we went through each of the corrected location properties manually to identify whether it was, in fact, the correct location information for that particular event. The goal of these experiments was to assess whether we could use relatively unskilled volunteers with Dacura's tools to produce a high-quality dataset from the inconsistent database without requiring expert input. We ran several iterations of this experiment, improving the tools in each iteration, in order to ensure that User Interface issues were not impacting upon experimental results.

The process of improving the accuracy of the data by non-expert volunteer users was measured through two experimentsthe first involved 6 users, the second 10 users. Each user was presented with a series of events which had locations that could not be linked automatically to DBpedia locations. Two different Dacura inter-linking tools, one map-based, one table-based, were used by each user in both experiments (Fig. 1).

The most important conclusion is that we now know that by devoting approximately 2 h and forty minutes of non-expert human effort, we can reduce the amount of data that has to be examined for approval by an expert by approximately 80 %.

Conclusion and Future Work

In this paper we described how the Dacura framework has been used to improve and extend a dataset of political violence events. Dacura's tools were used to allow non-expert users to correct location errors in approximately 80 % of cases, requiring, on average, 6 s per record. Future work will see us extend the quality assessment aspects of the framework to non-location properties and other domains.

Fig. 1 .

 1 Fig. 1. Distribution of results by time and user