Ana Tanevska
email: ana.tanevska@iit.it

Francesco Rea
email: francesco.rea@iit.it

Giulio Sandini
email: giulio.sandini@iit.it

Alessandra Sciutti
email: alessandra.sciutti@iit.it

Towards an Affective Cognitive Architecture for Human-Robot Interaction for the iCub Robot

Keywords: affective computing, human-robot interaction, humanoid robots, cognitive architecture, cognitive interaction ACM Classification I.2.9 Robotics

The ability to reason for itself and make decisions for its own actions is a highly desirable ability for robots engaged in human-robot interaction (HRI). By being able to perceive the environment, select the optimal action w.r.t. the state of the environment and then observe and learn from the reactions that occur, a robot can be said to be fully autonomous in the interaction. There have been several different types of frameworks focusing on cognitive functionalities for autonomous robots, and one particularly promising venue for cognition focuses on the affect-driven cognitive frameworks. This paper presents an ongoing study focused on developing an affect-based architecture for the humanoid robot iCub with the purpose of having fully autonomous interactions with humans.

INTRODUCTION

Having robots be able to autonomously interact with humans, in a context where they would have to continuously adapt to novel and unstructured scenarios is considered as a significant milestone in HRI. To reach this kind of autonomous behaviour in social robots it becomes necessary for some level of cognition to be implemented in the robot's architecture.

In general, cognition in both natural and artificial agents is seen as the collection of several crucial abilities that enable the autonomous behaviour of the system. Going by the definition of cognition from Vernon [START_REF] Vernon | Artificial cognitive systems: A primer[END_REF], a cognitive system or agent has to be capable of: environment perception, learning Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. CHI'14, April 26-May 1, 2014, Toronto, Canada. Copyright c 2014 ACM ISBN/14/04...$15.00. DOI string from ACM form confirmation from experience, anticipating the outcome of performed actions, adapting to changing circumstances in the environment and ultimately being able to act independently driven by its own motivation. For robots engaged in social HRI, the implementation of some (or all) of these cognitive abilities has been demonstrated in the context of autonomous social interaction [START_REF] Mccoll | A survey of autonomous human affect detection methods for social robots engaged in natural hri[END_REF] [START_REF] Adam | Social human-robot interaction: A new cognitive and affective interaction-oriented architecture[END_REF], in studies aimed at the employment of joint action [START_REF] Lemaignan | Artificial cognition for social human-robot interaction: An implementation[END_REF] as well as in studies where the robot is assisting the humans in achieving their goals [START_REF] Beer | Toward a framework for levels of robot autonomy in human-robot interaction[END_REF].

In our study, we are working in the context of social interaction generalized to fit different settings, where the robot would have interact with people autonomously, fluidly and above all with some level of intelligent behavior. Our aim is for the social robot to have cognitive skills resembling those of humans [START_REF] Breazeal | Toward sociable robots[END_REF]. Drawing inspiration from people, we propose to endow the robot with the ability to perceive the state of the person it is interacting with and to autonomously decide how to act, guided by an affect-driven motivational drive. There is some debate present on the question of whether affect and emotions in general play a vital part in the human cognitive architecture or whether they are separate from cognition [START_REF] Damasio | L'errore di Cartesio: emozione, ragione e cervello umano[END_REF]. This latter view can be evidenced in several studies for cognition in artificial systems where emotions are not included in the proposed cognitive architectures [START_REF] Lemaignan | Artificial cognition for social human-robot interaction: An implementation[END_REF] [START_REF] Beer | Toward a framework for levels of robot autonomy in human-robot interaction[END_REF].

Nonetheless, recently there have been researchers showing that emotions represent a crucial part of the human-inspired cognitive architectures for autonomous robots [START_REF] Vaufreydaz | Starting engagement detection towards a companion robot using multimodal features[END_REF] [START_REF] Dias | Fatima modular: Towards an agent architecture with a generic appraisal framework[END_REF]. Although emotional expressiveness can be implemented as a component in different functionalities, there are two main areas where it can serve a crucial part in the cognitive architecture -by representing an important perceptual input for the person in the HRI scenario, and by serving as an internal motivation and evaluation system for the robot. The ability to recognize the expression of emotions in other beings is providing information about the state of the environment after each iteration and can be used to evaluate how well the robot is performing [START_REF] Vaufreydaz | Starting engagement detection towards a companion robot using multimodal features[END_REF][14] [START_REF] Breazeal | How to build robots that make friends and influence people[END_REF]. There are several different methods used in HRI/HCI studies for evaluating and tracking the affective state of the person in the interaction [START_REF] Mccoll | A survey of autonomous human affect detection methods for social robots engaged in natural hri[END_REF], including emotion recognition from speech [START_REF] Han | Speech emotion recognition using deep neural network and extreme learning machine[END_REF] [START_REF] Pan | Speech emotion recognition using support vector machine[END_REF], body pose [START_REF] Vaufreydaz | Starting engagement detection towards a companion robot using multimodal features[END_REF] [START_REF] Schwarz | Combining body pose, gaze, and gesture to determine intention to interact in vision-based interfaces[END_REF] as well as distance from the robot and amount of touch [START_REF] Michalowski | A spatial model of engagement for a social robot[END_REF]. However, one of the more reliable and least intrusive method is the analysis of facial features and gaze [START_REF] Sariyanidi | Automatic analysis of facial affect: A survey of registration, representation, and recognition[END_REF][10] [START_REF] Palinko | Eye gaze tracking for a humanoid robot[END_REF]. On the other hand, emotions, if implemented in some pseudo form, can also constitute a value system for the cognitive robot, as emotions are often used both as motivation and evaluation mechanisms [START_REF] Vernon | Artificial cognitive systems: A primer[END_REF]. By implementing a (limited) range of pseudo emotions for the robot (eg. happy, sad, neutral, surprised etc), it is possible to make them a part of the anticipation and decision phases in the robot's schema, supporting learning and adaptation. There are already several examples of artificial cognitive architectures exploiting emotions as inner motivation, such as the FAtiMA architecture equipped with modules for appraisal and behaviour [START_REF] Dias | Fatima modular: Towards an agent architecture with a generic appraisal framework[END_REF], the WASABI architecture dealing with implementation of both primary and secondary emotions [START_REF] Becker-Asano | Affect simulation for agents with believable interactivity[END_REF], the CogAff architectural schema (and its upgrade to an actual cognitive architecture -H-CogAff) with reflective, deliberative and reactive processes [START_REF] Sloman | symposium on emotions, cognition, and affective computing[END_REF] and the "bidirectional grounding"-based cognitive schema described in [START_REF] Lowe | Utilizing emotions in autonomous robots: An enactive approach[END_REF].

That as may be, combining these two affect-based functionalities in robots is not yet a widespread practice. There have been studies on empathic HRI, e.g. with the iCat robot [START_REF] Castellano | Detecting user engagement with a robot companion using task and social interaction-based features[END_REF], however, there aren't many studies which attempt fully autonomous affect-based HRI with more elaborate humanoid platforms. The adoption of such a platform would entail additional challenges, such as the heightened human expectations for the robot's performance, as well as the complexity of the control of the platform.

The study described in this paper presents our work on developing a cognitive, self-learning architecture for social interaction for the iCub robot. The rest of the paper is organized as follows:Our Architecture presents the structure of our cognitive framework and the modules (shown in Figure 1). This is followed by Methods, which covers the implementations of the modules in the respective subsections Perception Module and Learning Module. Finally, in Results and Conclusion we present our results from testing the perception and learning components and we discuss our next steps in the study.

OUR ARCHITECTURE

The envisioned goal of our study is to develop a cognitive architecture for the iCub humanoid robot which would provide the iCub with the primary supportive functionalities necessary for autonomous HRI. The main concept is a framework which would allow the robot to perceive and evaluate the affective state of the persons with which it's interacting and make an intelligent decision when selecting and performing actions. This base framework, once established, can later be generalized to fit many different contexts of HRI social, educational, joint-action, assistive, etc -depending on the types of actions which would be implemented. Our intention is instead of focusing on developing a framework for a narrow set of behaviours, to set the groundwork for a learning and decision-making platform which could be utilized for any kind of interaction between a human and an intelligent robot.

However, this base framework cannot consist solely out of the standard action-perception loop, as it is insufficient to cover the full range of cognitive functionalities for the intelligent robots. To satisfy the abovementioned functionalities necessary for cognition, there is the need for additional components which would be responsible for learning and intelligence, for forming a connection between the robot's action and the person's reaction, as well as memorizing the emergent patterns of behavior and response for each person.

The closed loop then, needs to be extended by implementing a basic form of memory, and then adding either a reinforcement mechanism applied after the executed action, which provides feedback to the robot regarding its last action or series of actions, or an advice mechanism, which is implemented after the perception phase and provides the recommended course of action based on the perceived state. In supervised learning scenarios, this is done via a teacher who provides either the reinforcement or the advice [START_REF] Ackovska | Taxonomy of learning agents[END_REF]. In self-learning frameworks (as autonomous robots would preferably have), we would like to have both implemented and functioning in the extended closed loop.

In the previous section, we mentioned that the set of primary requirements for cognitive agents, apart from perception and action also included adaptation, anticipation, learning and motivation. For our architecture we propose a motivational system based on affect, where the robot's emotional state changes for the better or worse depending on the perceived change in the person's affective state. The knowlege of how each person's state changes over time and series of interaction needs to be stored in the robot's memory, and updated whenever the robot learns some new information about the behaviour of the person.

Thus the framework for interaction would take the format of this kind of loop: There are three distinct components functioning separately that needed to be developed for our architecture -the perception, internal evaluation/self-learning and action components.

•
The perception component was tasked with obtaining the visual feedback from the human peer, and processing the visual signal into information about the affective state of the person. The evaluation component is the one in charge of anticipating the outcome of the future actions, as well as learning postaction whether its beliefs were true. The action component is the one in charge of performing the action selected as the most potent one.

METHODS Perception Module

The perception component of our architecture is tasked at the moment with processing just the visual input, although there is consideration for expanding this with spatial or tactile sensor data further on. More specifically, we are processing the monocular information from one of iCub's cameras about the facial features of the person. The monocular input was selected since at the moment there is no requirement for stereo vision in the framework, and since we wanted to have as fast as possible perception module for real-time analysis of the face during at interaction.

The perception module was firstly implemented on a Windows machine so as to fully test its functionalities before porting it to the iCub. For the processing part we started with some of the functionalities integrated in the OpenFace framework developed by T. Baltrusaitis [START_REF] Baltrušaitis | Openface: an open source facial behavior analysis toolkit[END_REF].

OpenFace is an open-source architecture which offers the analysis of images (single image or a series), video or camera feed, and the extraction of all the relevant information about the facial landmarks, head orientation, facial expressions, gaze direction, etc (as shown in Figure 2). However, for the scope of our perception module we just required processing the camera feed and extracting the facial landmarks, so we started with their architecture for detecting the facial features and adapted it further to the iCub software. The perception module consists of several sub-modules. The first processing includes the analysis of the scene from the camera feed and the attempt to detect a face in it. Following the detection of the face, which is done by using the dlib library and its frontal face detector, the landmarks on the human face (shown in Figure 3) were extracted. From the 68 facial landmarks the most important factors for expression analysis can be extracted the facial action units (AUs). The facial action units are anatomically based facial actions (e.g. lifting/lowering eyebrows, smiling, opening mouth, wrinkling nose, etc), which can be associated with the expression of certain emotions (see Figure 4) [START_REF] Ekman | Facial action coding system (facs). A technique for the measurement of facial action[END_REF]. The extraction of the AUs was done using two phases: extracting the appearance of the AUs by using linear-kernel SVM and coding the appearance or non-appearance of a certain AU as 1 or 0; and extracting the intensity of the AUs by using a linear-kernel SVR, where the value given for each AU varies continuously between 0 and 5. Groups of these AUs can be highly exclusive and connected to separate affective states (i.e. anger, happiness, sadness, surprise, etc) [START_REF] Lucey | The extended cohn-kanade dataset (ck+): A complete dataset for action unit and emotion-specified expression[END_REF], which made it very simple to program the affect detection module depending on the summary intensity value of the AUs at a given frame. This has the additional benefit of not requiring the training of a classifier or regressor for detecting the facial expressions, as they have been shown to be linked with the activation of specific subsets of AUs.

We also evaluated whether the same module could be used for distinguishing the engagement state of the person (i.e. whether the person is interested or bored in the interaction). However, unlike the detection and classification of the affective states, which are very salient and can be detected without the need of a trained classifier but just by evaluating and comparing values, to assess the engagement of the persons we needed a classifier.

For the training and testing of the classifier we used the videos of the AMFED database [START_REF] Mcduff | Affectiva-mit facial expression dataset (am-fed): Naturalistic and spontaneous facial expressions collected[END_REF]. The database consists of videos of people responding to advertisements, annotated by the selfdescribed reaction of the users about how engaged they felt during the advertismenent and if they would watch it again. There were a total of 235 videos, with average duration of 55 seconds. The set of videos was first processed and the intensities of the expressive AUs were extracted for each of the videos, excluding only the first 100 frames which depicted the people getting ready to play the advertisement. The processed AU data was then used to train several classifiers : K-nearest neighbours (KNN), ADA boost, Neural Networks (NN), Decision Trees (DT) and Random Forest (RF). The training was done using the sci-kit library for python and its implementations of the abovementioned classifiers, using the default provided parameters [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF].

Learning Module

The learning module was the component providing the link between perception and action. In the previous section we mentioned that the functionalities that needed to be covered were motivation, anticipation, learning and adaptation. We addressed this issue in three steps. Firstly, by defining that every change (be it positive or negative) in the person's affective state impacts the robot's emotions. Next, by defining that the internal goal of the robot is to maximize its own happiness, by making sure the person's affective state changes for the better. And finally, by implementing a basic system responsible of storing the robot's knowledge about what each person prefers in the interaction, and also responsible of learning and adapting w.r.t. to the observed behavior of each person following a robot's action.

The value system used for these functionalities was implemented in the form of Markov chains of transitional probabilities, with a separate graph for each of the robot's behaviors, and a separate group of graphs for each person separately. A sample graph is depicted in Figure 5. The values of the transitions are the probabilities with which a person's state could change from state A to state B, by performing the selected action.

The scenario covered by this graph shows the values given a robot's behavior of play and the tracked states of neutral, interested and bored for the person. This was extracted from our previous study on affect-based autonomous framework, where the robot could exhibit two different typologies of behavior (i.e. engaging the users to learn something or to play with the robot), and was tracking the engagement state of its human peers [START_REF] Tanevska | Can emotions enhance the robot's cogntive abilities: a study in autonomous hri with an emotional robot[END_REF]. The process that happens in between perceiving the state of the person and selecting an optimal action is the following: for each of the possible actions (or behaviours) the robot can perform, it needs to calculate which one has the highest probability to improve the state of the person. For instance, if the perception module has evaluated the person is now sad, the robot needs to evaluate which action has the greatest probability to make the robot feel better by improving the state of the person.

Evaluating these probabilities is done by utlizing the Markov chains to calculate the conditional probabilities about the change in the affective states of the robot and the person (see equations below).

Shown in the equations are the calculations for the probabilities of the robot state r1 changing to the value m1 depending on the affective state of the person u1, as well as the probability for the state of the person u1 entering the new affective state n1, for a given action of the robot r1.

This can be further extended if the perceptual input is twodimensional, i.e.if the robot needs to consider the changes in both the level of engagement of the user and their affective state. Tracking both dimensions can be beneficial in HRI, if we consider that not only do we want to know whether the person is feeling happy or sad or angry, but also whether those emotions are related to the interaction with the robot, or are caused by external factor not related to the robot's behaviour.

There are two methods of tracking the changes in a twodimensional space: either by noting the combination of the changes (e.g. increased affect + decreased engagement) or by giving preference to one of the dimensions (i.e. whether it's more important to have engaged but angry users, or slightly bored but happy). The decision which way would be the more beneficial one depends strongly on the context of the HRI, which is to say on the types of behaviours exhibited by the robot and the scene of the HRI.

RESULTS AND DISCUSSION

While the system described in this paper is still a work-inprogress, we already have obtained some results from the implementation and testing of the components in the perception module, as well as previous results supporting the integration of the learning module.

Perception Module Affect detection

The affect detection module was tested successfully in several demos in the form of an emotional mimicry module. This module was executed in parallel with the face tracking module for the iCub, and it presented a scenario where the iCub was following the face of the user, while simultaneously also mimicking the facial expressions the user was showing (see Figure 6).

This was done by comparing the intensity values of the groups of AUs and evaluating the emotional state the user was expressing; and then using the predefined combinations of the LEDs in the face of the iCub to express the same emotional state. The module was tested during demos in our laboratory with both adults and children present, to quite noticeable interest from the audience, and it has also been implemented as a part of a greater composite demos.

Currently, we are also looking into more formal, quantitative testing for the affect detection component with the purpose of obtaining a benchmark for its accuracy, as all of the evaluation so far has been of a more qualitative nature.

Engagement detection

Out of the five classifiers trained on the AM-FED videos, the highest accuracy and efficiency in training showed the Random Forest classifier, implemented with constraints of 10 trees per forest and maximum depth of level 5. Table 1 shows the training time in seconds, and the results from the 5-fold cross-validation for each classifier. Considering the comparison in difficulties for classifying engagement over classifying affect, as well as the fact that recent state-of-the-art accuracy for classifying facial expressions ranges around 75.2%, our result of 69.5% can still be considered satisfactory. However, the situations in which a robot has to assess the engagement of its human peers would be quite different regarding the display of the engagement from the context in which the AM-FED videos were recorded. To evaluate whether also natural interaction with iCub can evoke engagement similarly readable from facial expressions, we processed recordings of an HRI experiment with the iCub, covering the part of the experiment where iCub is explaining the procedure for the experiment to the people, thus engaging them in direct interaction [START_REF] Palinko | Robot reading human gaze: Why eye tracking is better than head tracking for human-robot collaboration[END_REF]. To obtain a benchmark of the level of engagement exhibited by the people, we asked four raters (2 females, 2 males; avg age: 28years) to watch the same videos and continuously rate the degree of engagement by pressing a key (either 0: disengaged, 1: neutral or 2: engaged). A subject in the video was labeled as engaged for a rater if the rating was 2 for the majority of its duration, disengaged if the rating was 0 most of the time and neutral if it was 1 for most of its duration. For the final calculations, we opted for a binary labeling (engaged vs. disengaged) by accumulating neutral votes to the label containing the higher number of raters and then picking the most voted category as label for the video.

We used the rating from the human judges to obtain the degree of inter-rater reliability and calculate the Fleiss kappa value. However, the results showed a low kappa value of 0.569892 (with a standard error of 0.129099), which falls short of the value of 0.61+, required for detecting "substantial agreement" between raters. This showed that unlike with affective expressions, evaluating the level of engagement in people is difficult even for human judges. Because of that, if we plan on using the facial features to evaluate the engagement level via a classifier, we will need to train it with a more context-relevant dataset.

Learning Module

As of now, the learning component has not yet been tested in an HRI experiment with the current setup on the iCub robot, since its functioning is strongly dependent on the integration with a fully developed action module. However, the same framework for the learning module was already tested out in our previous study, in a child-robot scenario with the NAO humanoid robot [START_REF] Tanevska | Can emotions enhance the robot's cogntive abilities: a study in autonomous hri with an emotional robot[END_REF].

The study involved three pre-school children engaging in playful or educational interaction with the NAO robot, and the framework proved as capable of learning each of the children's preferences during the sessions of interaction. Figure 6 shows the adjustment learned for each of the children after just three sessions of interaction.

Figure 7: Depiction of the changes to the initial belief values after three sessions of interaction with the three participants, extracted from [START_REF] Tanevska | Can emotions enhance the robot's cogntive abilities: a study in autonomous hri with an emotional robot[END_REF].

CONCLUSION

The goal of our study was to attempt to implement a new architecture for the iCub which would equip it with abilities for autonomous cognitive interaction with humans. Through detecting and tracking the affective state of the users, while simultaneously developing and maintaining its own internal evaluation system, iCub will have an effective system for evaluating the desirability of each possible action at a time, by calculating which action would make it happier with the highest probability.

A planned expansion for the perception module is to also look into utilizing information for the gaze of the person as a measurement of the level of engagement they're expressing, which if successful could be a step towards two-dimensional evaluation of the user state.

In addition to expanding the perception component, we also need to develop novel groups of differing behaviours for the iCub to perform with the participants in the experiments. We would like to monitor the emerging behaviour of iCub with each of the users, and note how the belief networks modify specifically for each one of them. Our hope for this architecture is that it will provide for a more natural, long-term, adaptive interaction between humans and robots.

Figure 1 :

 1 Figure 1: The layout of our architecture.

  Perceiving the state of the human • Before performing an action -Predicting which action would be most beneficial for robot and human (by improving their affective states) -Performing the most beneficial action • After performing an action -Evaluating from perceptual input if the person's reaction is as predicted -Modifying the belief values if wrong, reinforcing them if right

Figure 2 :

 2 Figure 2: Output from the OpenFace modules.

Figure 3 :

 3 Figure 3: The 68 facial landmarks extracted from a frontal face view.

Figure 4 :

 4 Figure 4: Some of the AUs extracted from facial landmarks.

Figure 5 :

 5 Figure 5: Example of a Markov chain in the learning module.

Figure 6 :

 6 Figure 6: Examples of the mimicry module in action.

Table 1 :

 1 Results from 5-fold cross-validation on the AM-FED database

	KNN ADA	DT	RF	NN
	Accuracy 59.6% 66.8% 68.1% 69.5% 63.7 %
	Train time 7.48 s 41.59 s 2.06 s 1.85 s 141.47 s


Michele Salvi

¸ois Simenhaus
email: simenhaus@ceremade.dauphine.fr

RANDOM WALK ON A PERTURBATION OF THE INFINITELY-FAST MIXING INTERCHANGE PROCESS

Keywords: AMS subject classification (2010 MSC): 60K37, 82C22, 60Fxx, 82D30 Random walk, dynamic random environment, interchange process, limit theorems, renormalisation

We consider a random walk in dimension d ≥ 1 in a dynamic random environment evolving as an interchange process with rate γ > 0. We only assume that the annealed drift is non-zero. We prove that, if we choose γ large enough, almost surely the empirical velocity of the walker X t t eventually lies in an arbitrary small ball around the annealed drift. This statement is thus a perturbation of the case γ = +∞ where the environment is refreshed between each step of the walker. We extend three-way part of the results of [HS15], where the environment was given by the 1-dimensional exclusion process: (i) We deal with any dimension d ≥ 1; (ii) We treat the much more general interchange process, where each particle carries a transition vector chosen according to an arbitrary law µ; (iii) We show that X t t is not only in the same direction of the annealed drift, but that it is also close to it.

Introduction, model and result

We are interested in a Markovian walker on Z d whose transitions are given by an underlying random environment. The environment itself evolves in time according to an interchange process, also called random stirring process in the physical literature: We initially put a single particle on each site of Z d and suppose the particles carry a transition-probability vector chosen in an i.i.d. way from some law µ. We attach independent Poisson clocks with parameter γ > 0 on each edge of Z d and, when the clock attached to {x, y} rings, the system is updated by exchanging the particles sitting in x and y. We consider a time-discrete walker (X t ) t∈N on top of this system: For each jump it chooses a direction according to the transition-probability vector carried by the particle on which it sits. We assume that the expected drift of the transition-probability vectors is non-zero. If the environment is completely refreshed at each step of (X t ) (corresponding to γ = +∞), the walker evolves in a homogenous environment and thus admits the expected drift as asymptotic velocity. We are concerned here with a perturbation of this regime. We actually prove that, choosing γ large enough, the empirical velocity of the walker X t t eventually lives in an arbitrary small ball around the expected drift.

While the problem of the asymptotic velocity for random walks in random media has been widely studied in the case of static environments (see for example [START_REF] Berger | Local limit theorem and equivalence of dynamic and static points of view for certain ballistic random walks in i.i.d. environments[END_REF] and references therein for the general i.i.d. setting and [START_REF] Berger | On the speed of random walks among random conductances[END_REF] for the reversible case), the case of media that evolve in time has gained a great attention from the mathematical and physical communities only in recent years. The typical examples are that of the tracer (or tagged) particle in lattice gases (as in [START_REF] Spohn | Tracer diffusion in lattice gases[END_REF]) or that of random walks moving on top of an interacting particle system (such as a spin flip dynamics or a conservative particle systems). When the environment dynamics has good space-time mixing conditions, traps, i.e. "unfavorable" regions of the environment, tend to dissolve on a shorter time scale than the one that is interesting for the analysis of the walker, and therefore in many cases it has been possible to derive a law of large numbers (see, e.g., [START_REF] Dolgopyat | Random walk in Markovian environment[END_REF] for environments given by a space-time mixing Markov chain, [START_REF] Avena | Law of large numbers for a class of random walks in dynamic random environments[END_REF][START_REF] Frank Den Hollander | Law of large numbers for non-elliptic random walks in dynamic random environments[END_REF], where the so-called cone-mixing and conditional cone-mixing conditions are introduced, [START_REF] Avena | Analysis of random walks in dynamic random environments via l 2 -perturbations[END_REF][START_REF] Avena | A class of random walks in reversible dynamic environments: antisymmetry and applications to the East model[END_REF] for perturbations of walks on a class of dynamic environments satisfying the Poincaré inequality, or [START_REF] Bandyopadhyay | Random walk in dynamic Markovian random environment[END_REF][START_REF] Frank Den Hollander | Scaling of a random walk on a supercritical contact process[END_REF] for results on specific models). It appears more complicated to study the asymptotic properties of a walker moving in an environment that mixes slowly, for example when the underlying dynamics is conservative: Some results have been lately obtained for a walk on the simple symmetric exclusion process with strong drift conditions in [START_REF] Avena | Transient random walk in symmetric exclusion: limit theorems and an Einstein relation[END_REF], for a walk moving on a collection of independent particles performing simple symmetric random walks in [HdHdS + 15, BHDST17a, BHDST17b] and for rather general ergodic Markovian environments with sufficiently fast polynomial mixing in [START_REF] Redig | Random walks in dynamic random environments: a transference principle[END_REF]. In the slow-mixing setting, the authors of [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] consider a one-dimensional dynamic random environment evolving as the Simple Symmetric Exclusion Process (SSEP) with jump parameter γ. A nearest-neighbor walker moves on this environment at integer times, jumping to the right (left) with probability α > 0 (resp. 1 -α) if it finds itself on a site occupied by a particle, and to the right (left) with probability β > 0 (resp. 1 -β) if it is on an empty site. The authors show that if in the case γ = +∞ the walker has a strictly positive limiting speed, then, for γ big enough, the walk will admit a strictly positive limiting speed, too. They also prove an analogous result (requiring only transience of the walk for γ = 0) for γ small enough.

In the present paper we consider a walker moving on the interchange process, or random stirring process. This interacting particle system often appears in studies of the quantum Heisenberg ferromagnetic model and its cycle and loop representations (see e.g. [T 93] or [START_REF] Goldschmidt | Quantum Heisenberg models and their probabilistic representations[END_REF] for a review). Even if we do not prove a full law of large numbers, the present work can be thought as a generalization of the result about the perturbation of the γ = +∞ regime in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] (see Theorem 1.1 therein) in three different directions:

(i) We pass from dimension d = 1 to d ≥ 1. We point out that most of the results for random walks in dynamic random environment have been achieved so far for dimension d = 1, especially in the slowly-mixing dynamics framework;

(ii) Instead of considering the SSEP for the environment dynamics, we deal with the interchange process. In particular, while in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] only two possible transition-probability vectors are allowed, initially chosen with a Bernoulli product measure, in the present article we consider any vector coming from the d-dimensional simplex, sampled at time 0 with an arbitrary product measure µ ⊗Z d ; (iii) While in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] it is proven that, for γ sufficiently large, X t t is just eventually positive in the average drift direction, we prove here that, eventually, X t t stays in fact close to the average drift. We will follow the general strategy of [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF], readapting and enhancing its techniques into our much more general setting. In particular, we will use concentration inequalities to control the environment behavior and a renormalization procedure for obtaining the asymptotics of the walker. We postpone to a future work the study of the full law of large numbers and of the CLT. The major obstacle is due to the high dimensionality of the problem, which makes rather hard to study the frequency of times when the walker is "ahead" of any particle it visited. This prevents one from constructing a proper renewal structure (see e.g. [AdSV13, HdHdS + 15, HS15]), which is the main tool to derive such theorems.

1.1. Notation, model and main result. We call N ∶= {0, 1, ...} the set of natural numbers. We write I ∶= {-1, ⋯, -d} ∪ {1, ⋯, d} and define N ∶= (e i ) i∈I , where, for each i = 1, ..., d, e i denotes the i-th element of the canonical basis of R d , while e -i ∶= -e i . We define S ∶= {s ∈ [0, 1] I ∶ s 1 + ... + s d + s -1 + ... + s -d = 1} to be the simplex of possible transition-probability vectors and we associate to each s ∈ S its drift D(s) ∶= i∈I s i e i .

We denote by Ω ∶= (S Z d ) R+ the space of space-time environments. We think of an element ω as a time-indexed sequence of environments, where an environment is a collection of transition-probability vectors associated to each point of the lattice: ω y (t) ∈ S is the transition-probability vector in the site y ∈ Z d at time t ≥ 0, and ω i y (t) represents its i-th coordinate, i ∈ I. Given an environment ω ∈ Ω we define the discrete-time random walk (X t ) t∈N on Z d with law P ω as the process defined by the following: For all k ∈ N, y ∈ Z d and i ∈ I we have

P ω (X 0 = 0) = 1 , P ω (X k+1 = y + e i X k = y) = ω i y (k) .
Notice that, albeit ω has been defined for each positive real time t, the walk (X t ) t∈N is influenced only by the environment at integer times.

We now construct a probability measure on Ω, corresponding to an interchange process where each particle carries a transition-probability vector chosen once and for all at time zero. We let µ be a probability measure on S and indicate with E µ [⋅] the expectation w.r.t. µ. Our unique assumption on µ is that

E µ [D] ≠ 0 .
(1.1)

In particular, we point out that we do not require any kind of ellipticity on the environment. We consider the product law π ∶= µ ⊗Z d on S Z d . We finally construct a law P on Ω in the following way: We start from an η ∈ S Z d chosen according to π, and we let it evolve according to the generator

Lf (η) = γ 2 x,y∈Z d ∶ x-y =1 f (η ○ σ xy ) -f (η) ,
where σ xy (η) indicates the environment obtained from η ∈ S Z d by interchanging the particles in x and y, i.e. the values of ηx and ηy . We indicate by ⋅ the usual L 2 -norm. We indicate with P η the law of the evolution of the environment started from a given η ∈ S Z d , E η being the corresponding expectation. Notice that we will always use bold characters for indicating probabilities and expectations when we will deal with the sole environment process. In our particle representation, we see that L is nothing but the generator of the interchange process: We can think to assign to each edge in Z d an exponential clock of parameter γ, independent of all the other clocks. Whenever the clock of an edge {x, y} rings, we proceed with exchanging the positions of the particles in x and y. We define the law of the random walk in the dynamic environment starting from a given η ∈ S Z d as P η ∶= P η × P ω , and finally the annealed law, where we average over the initial configuration according to π, is

P ∶= P × P ω .
Our goal is to prove the following theorem: Theorem 1. Under assumption (1.1), for all ε > 0, there exists γ(ε) such that, for all γ ≥ γ(ε), P -a.s. it holds that, for t large enough,

X t t ∈ B ε E µ [D] ,
where

B ε (E µ [D]) is the L 2 -ball of radius ε around the averaged drift E µ [D].
Remark 1.1. Theorem 1 answers one of the issues left open in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF]. In fact, in the case of an environment driven by a one dimensional SSEP,our theorem implies the convergence of the asymptotic velocity v(γ) (which was proven to exist in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF]) to the annealed drift E µ [D] when γ goes to +∞.

1.2. Outline of the paper. In Section 2 we will prepare the technical machinery needed for the proof of Theorem 1. The section is devoted only to the properties of the underlying interchange process: We say that a site x ∈ Z d is L-good for a configuration η ∈ S Z d if the empirical distribution of the environment in any ball of size larger than L centred in x is close to µ, see Definition 2.2 for a precise statement. In Proposition 2.4 we prove that if a site is L-good at time 0, then it will be J-good (J < L) after a time t satisfying γt > L 3 with high probability. To this end, we will need a concentration inequality, Lemma 2.5, and some estimates on the density of the particles carrying some type of transition-probability vector, Lemma 2.6. In Section 3 we pass to the proof of Theorem 1. This will be achieved through a renormalization procedure.

Proposition 3.2 deals with the initial step of the renormalization, giving the result up to any time T choosing γ large enough depending on T . Proposition 3.3 extends the result for any time t > T by iteration. Finally, in Subsection 3.4 we finalize the proof.

Auxiliary results on the environment dynamics

In this section we will collect a series of results that concern only the environment dynamics. We fix here and for the whole section an integer N ∈ N. Note that all the statements in this section involve constants that may or may not depend on N , but we will not comment on that since it will not affect the results that we want to prove. We consider a map T ∶ S → T , where we call T ∶= {0, ..., 2 N -1} I the space of types, with T ∶ s ↦ T (s) such that, for each coordinate i ∈ I,

T i (s) ∶= max j ∈ {0, ..., 2 N -1} ∶ 2 -N j ≤ s i . In particular, if s i = 1, then T i (s) 2 N ≤ s i < T i (s)+1 2 N . We simply say that an element s ∈ S is of type k (where k is a 2d-dimensional integer multi-index) if T (s) = k and call p k ∶= µ(T (s) = k) the µ-probability that a configuration s is of type k.
We point out that if µ gave positive weight only to a finite number of possible transition-probability vectors of S, there would be no need to introduce types (notice for example that the SSEPtreated in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] corresponds to having only two possible transition-probability vectors). On the other hand, in order to deal with much more general µ's, the reduction to a finite number of types of particles is fundamental for our technique to work.

Given

x ∈ Z d , L ∈ N, k ∈ T and η ∈ S Z d , we let ⟨η⟩ k x,L ∶= 1 B L (x) y∈B L (x)
1 T (ηy)=k be the empirical density of particles of type k in a ball of radius L around x. We consider L 2 balls:

B L (x) ∶= {y ∈ Z d ∶ x -y ≤ L}, so that the cardinality of a ball is c 1 L d ≤ B L (x) ≤ c 2 L d for some constants c 1 , c 2 > 0 depending on the dimension d.
Remark 2.1. For simplicity, throughout the article we will denote by c, c 1 , c 2 , ... some strictly positive constants the value of which might change from one expression to the other. These constants will not depend on the other variables involved (with the possible exception of d and N ), unless otherwise specified.

For simplicity, for L ∈ N, we abbreviate ⟨η⟩ k L ∶= ⟨η⟩ k 0,L and B L ∶= B L (0). We also fix a decreasing sequence ( L ) L∈N of real numbers in (0, 1) by

L ∶= 1 1 + ln(L)
.

(2.1)

The numbers L are meant to control the difference between the theoretical density p k and the empirical density of particles of type k in a box of size L:

Definition 2.2. For L ∈ N, we say that a site x ∈ Z d is L-good for a configuration η ∈ S Z d if ⟨η⟩ k x,L ′ -p k ≤ L ∀L ′ ≥ L, ∀k ∈ T . (2.2)
In a configuration η, we call the set of L-good sites G(η, L).

Remark 2.3. Note that the definition of good sites depends on N .

In words, x ∈ G(η, L) if in every ball of radius L ′ ≥ L the density of particles of type k is close to its theoretical mean, with an error of at most L , for every possible type k. The typical deviation, under the equilibrium measure, of the empirical density in a d-dimensional ball of radius L is of order 1 L d 2 . Our conservative choice of ( L ) in (2.1) guarantees that a site has large probability to be good when L is large.

The following proposition is one of the main tools that we will use for proving Theorem 1.

Proposition 2.4. Suppose that 0 ∈ G(η, L) for some η ∈ S Z d , L ∈ N. Then there exist c 1 , c 2 > 0 such that the following is true: For all J ∈ N, J < L, such that L( J -L ) is large enough, and for all t > 0 such that γt > L 3 , it holds

P η 0 ∈ G(η(t), J) ≤ c 1 e -c 2 J d ( J -L ) 2 ( J -L ) 2 .
In order to prove Propositions 2.4 (which will be done in Subsection 2.3) we will need the following two lemmas, that will be proven in Subsection 2.1 and Subsection 2.2, respectively. Lemma 2.5 is a concentration-of-measure kind of statement, claiming that ⟨η(t)⟩ k L stays close to its mean. Lemma 2.6 controls the expectation E η [⟨η(t)⟩ k M ] in terms of the initial configuration η. Lemma 2.5. There exists a constant c > 0 such that, given η ∈ S Z d , L ∈ N, k ∈ T and a ≥ 0,

P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≥ a ≤ 2 e -c a 2 L d . Lemma 2.6.
For each α > 0, there exists a constant c > 0 such that, given η ∈ S Z d , M, L ∈ N, k ∈ T and t ≥ 1, the two following inequalities hold:

E η ⟨η(t)⟩ k M ≤ 1 + c L d+1 (γt) (d+1) 2 + 1 (γt) 1 2-α sup ⟨η⟩ k L ′ ∶ L ′ ≥ L (2.3) E η ⟨η(t)⟩ k M ≥ 1 -c L d+1 (γt) (d+1) 2 + 1 (γt) 1 2-α inf ⟨η⟩ k L ′ ∶ L ′ ≥ L .
(2.4)

Remark 2.7. Lemma 2.5 provides a control of the average number of particles of a given type in a ball of size M at time t in terms of the initial particle configuration, for any M ∈ N. It is not clear if the rates of decay in t of the r.h.s. of (2.3) and of (2.4) are optimal: While the term (L √ γt) d+1 is due to the diffusive dissipation of traps, the term 1 (γt) 1 2-α is present for technical reasons and it could perhaps be improved. Nevertheless, not being interested here in sharp quantitative statements on γ, the bounds (2.3) and (2.4) will be more than sufficient for our purpose.

2.1. Proof of Lemma 2.5. We prove the two following inequalities, which imply the lemma:

P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≥ a ≤ e -ca 2 L d , (2.5) P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≤ -a ≤ e -ca 2 L d . (2.6)
Let us start with (2.5). We will replicate the argument used in [HS15, Lemma 1], considering each k-particle of our system as a 1-particle in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF]. Even if there are only few minor modifications, we repeat here the whole proof in order to make the present article self-contained. For 0 < δ < B L , exponential Markov inequality gives

P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≥ a ≤ e -δa ⋅ e -δE η [⟨η(t)⟩ k L ] ⋅ E η e δ⟨η(t)⟩ k L .
(2.7)

Notice that we can write

E η ⟨η(t)⟩ k L = 1 B L y∈B L E η [1 T (ηy(t))=k ] = 1 B L y∈B L z∈Z d p(t, y -z)1 T (ηz)=k = z∈Z d p L (t, z)1 T (ηz)=k , (2.8)
where p(t, x) is the heat kernel associated to the Laplacian γ∆, i.e. the probability that a simple random walk jumping at rate γ and starting at the origin will be in site x after time t, and

p L (t, x) ∶= 1 B L y∈B L p(t, x + y) .
(2.9)

The third factor of (2.7) can be handled through Ligget's inequalities (see [Lig05, Prop. 1.7, pag. 366]): Let θ = (θ(t)) t≥0 be the collective motion of continuous-time independent simple random walks on Z d with rate γ, so that θ x (t) indicates the number of particles on site x at time t. We consider as starting configuration θ(0) the one such that θ x (0) = 1 T (ηx)=k , i.e. we let a simple random walk start in site x if and only if the particle at site x in η is of type k. We arbitrarily label these random walks and call them (X j (t)) t≥0 , with j ∈ N. We indicate the empirical average of the number of particles at time t in a box of size L around the origin as ⟨θ(t)⟩ L . Set p L (t, x) ∶= B L ⋅ p L (t, x). Using Liggett's inequality for the first line, we can now bound

E η e δ⟨η(t)⟩ k L ≤ E η e δ⟨θ(t)⟩ L = j∈N E η e δ B L 1 X j (t)∈B L = j∈N e δ B L p L (t, X j (0)) + 1 -p L (t, X j (0)) = z∈Z d e δ B L p L (t, z) + (1 -p L (t, z)) 1 T (ηz )=k ≤ exp (e δ B L -1) z∈Z d p L (t, z)1 T (ηz)=k = exp (e δ B L -1) B L E η [⟨η(t)⟩ k L ] , (2.10)
where the last equality follows from (2.8). Since δ B L ≤ 1, we can expand e δ B L -1 to the first order in (2.10) and find a constant C < ∞ such that

E η e δ⟨η(t)⟩ k L ≤ e δE η [⟨η(t)⟩ k L ]+C δ 2 B L E η [⟨η(t)⟩ k L ] .
Plugging this back into (2.7), we get

P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≥ a ≤ e -aδ+C δ 2 B L E η [⟨η(t)⟩ k L ] .
Minimizing this expression in δ ∈ [0, B L ] (see [HS15, Proof of Lemma 2.3] for more details) and remembering that c 1 L d ≤ B L ≤ c 2 L d , we obtain the claim.

We are left to show (2.6). To this end, we just consider all the particles of type j = k as being of the same type. We call ⟨η(t)⟩ k L ∶= 1 -⟨η(t)⟩ k L the empirical average of particles of type different form k in B L and notice that

P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≤ -a = P η ⟨η(t)⟩ k L -E η [⟨η(t)⟩ k L ] ≥ a .
Then we just have to replay exactly the same game as above.

2.2. Proof of Lemma 2.6. Recall the definition (2.9). We divide Z d in disjoint crowns centered in 0:

Z d = ⋃ n∈N C n with C n ∶= {z ∈ Z d ∶ n -1 < z ≤ n}.
For y ∈ Z d we define the crown of y as C(y) ∶= C n(y) where n(y) is the unique integer such that y ∈ C n(y) . For each n ∈ N we choose representatives xn , xn ∈ C n such that

p + M (t, n) ∶= p M (t, xn ) = max z∈Cn {p M (t, z)} , p - M (t, n) ∶= p M (t, xn ) = min z∈Cn {p M (t, z)}.
We also define, for y ∈ Z d , p + M (t, y) ∶= max z∈C(y) {p M (t, z)} and p - M (t, y) ∶= min z∈C(y) {p M (t, z)}.

Claim 2.8. Take y ∈ Z d such that ⟨y, e i ⟩ > 0 for some i ∈ I. Then p M (t, y) ≥ p M (t, y + e i ).

Corollary 2.9 (Corollary of the Claim).

p + M (t, y) ≥ p + M (t, y ′ ) and p - M (t, y) ≥ p - M (t, y ′ ) ∀y, y ′ ∈ Z d ∶ y ′ ≥ y .
We postpone the easy proofs of Claim 2.8 and Corollary 2.9 to, respectively, Subsection A.1 and Subsection A.2 in the Appendix. With Corollary 2.9 at hand, we would like to proceed in a similar fashion as in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF], but the high dimensionality represents an obstacle to this end as, due to the geometry of the lattice, the particles starting in a given crown do not have exactly the same probability to reach the ball of radius M at a given time. For each positive function u ∶ Z d → R, we can write

p M (t, y)u(y) ≤ p + M (t, y)u(y) = n∈N p + M (t, n) -p + M (t, n + 1) u(y)1 y ≤n . (2.11)
If we sum over all y ∈ Z d , take u(y) = 1 T (ηy)=k and use (2.8), we obtain

E η [⟨η(t)⟩ k M ] ≤ n∈N p + M (t, n) -p + M (t, n + 1) y∈Z d 1 T (ηy)=k 1 y ≤n = n∈N p + M (t, n) -p + M (t, n + 1) B n ⟨η⟩ k n .
(2.12)

We abbreviate R ∶= sup{⟨η⟩ k L ′ ∶ L ′ ≥ L} and split the final sum in (2.12) for n < L and n ≥ L. For n < L we have that B n ⟨η⟩ k n ≤ B L R, since the r.h.s. is bigger than the total number of particles of type k at time 0 in the ball of radius L and this clearly dominates the number of particles in any smaller ball. Hence,

n<L p + M (t, n) -p + M (t, n + 1) B n ⟨η⟩ k n ≤ p + M (t, 0) -p + M (t, L) B L R ≤ cL d+1 (γt) d+1 2 R.
(2.13)

To see why the last inequality holds, we expand, for any z ∈ Z d and t > 0, in Fourier variables p(t, z) = e γt∆ δ 0 (z). We call α(ξ) ∶= ∑ d j=1 2(cos(2πξ ⋅ e j ) -1) and bound, for each z ∈ Z d , e ∈ N , t > 0,

p(t, z) -p(t, z + e) = R d e γtα(ξ) (2π) d e iξ⋅z (1 -e iξ⋅e ) dξ ≤ c R d ξ e -c 1 γt ξ 2 dξ ≤ c 2 (γt) d+1 2
.

(2.14)

Then we are done, since (2.14) is uniform in z and e and since we can find a path of neighbors leading from any point y ∈ B M to the point xL + y in

√ dL steps, which gives p + M (t, 0) -p + M (t, L) ≤ cL (γt) (d+1) 2 . We want to show now that n≥L p + M (t, n) -p + M (t, n + 1) B n ⟨η⟩ k n ≤ 1 + c L d (γt) d+1 2 + 1 (γt) 1 2 -α R . (2.15)
This together with (2.13) and (2.12) will imply the first half of the lemma, inequality (2.3). For n ≥ L we have that ⟨η⟩ k n ≤ R by definition and we are left to bound ∑ n≥L (p + M (t, n) -p + M (t, n + 1)) B n . By summing by parts we have

n≥L p + M (t, n) -p + M (t, n + 1) B n = n≥L p + M (t, n) C n + p + M (t, L) B L-1 = y ∈B L-1 p M (t, y) + n≥L y∈Cn p + M (t, n) -p M (t, y) + p + M (t, L) B L-1 . (2.16)
Since by Corollary 2.9 we have, for each

y ∈ C m with m < L, that p M (t, y) ≥ p - M (t, m) ≥ p - M (t, L), we can bound p + M (t, L) B L-1 ≤ p + M (t, L)-p - M (t, L) B L-1 + ∑ y∈B L-1 p M (t, y) , which inserted into (2.16) gives n≥L p + M (t, n) -p + M (t, n + 1) B n ≤ 1 + n≥L E M (t, n) C n + E M (t, L) B L-1 ,
(2.17)

where we have used the fact that ∑ y∈Z d p M (t, y) = 1 and where we have called

E M (t, n) ∶= p M (t, xn ) -p M (t, xn )
the maximum error we commit in the n-th crown.

Claim 2.10. For each ε > 0 there exist constants c 1 and c 2 such that n≥L

E M (t, n) C n ≤ c 1 1 (γt) 1 2-εd (2.18) and E M (t, L) B L-1 ≤ c 2 L d (γt) (d+1) 2 .
(2.19)

The proof of Claim 2.10 is rather technical and we postpone it to Subsection A.3 in the Appendix. We show now how to conclude the proof of Lemma 2.6. Plugging (2.18) and (2.19) into (2.17) we obtain (2.15) with α = εd. This implies (2.3) as mentioned before.

The lower bound (2.4) can be proven in an almost identical way as the upper bound: As in (2.11), we first note that for any positive u one has p M (t, y)u(y) ≥ ∑ n∈N (p - M (t, n)-p - M (t, n + 1))u(y)1 n≥ y and obtain a lower bound with the same flavor of (2.12). Then one splits once again the sum in n: This time the case n < L can be lower-bounded directly with 0. For the case n ≥ L we follow the same calculation as in (2.16) and produce a similar lower bound that this time reads:

n≥L (p - M (t, n) -p - M (t, n + 1)) B n ≥ 1 - n≥L E M (t, n) C n -E M (t, L) B L-1 .
Then we can use again the results of Claim 2.10 and proceed exactly as for the upper bound (2.3), concluding the proof of the lemma.

2.3. Proof of Proposition 2.4. We extend the argument in [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF] to the case of N different kinds of particles. By union bound

P η 0 ∈ G(η(t), J) ≤ k∈T J ′ ≥J P η ⟨η(t)⟩ k J ′ -p k > J .
(2.20)

Notice that if p k = 0 for some k ∈ T , the relative probability in the r.h.s. is just zero. For all the other k's we want to bound

P η ⟨η(t)⟩ k J ′ -p k > J = P η ⟨η(t)⟩ k J ′ > p k + J + P η ⟨η(t)⟩ k J ′ < p k -J .
(2.21) For the first summand we rewrite

P η ⟨η(t)⟩ k J ′ > p k + J = P η ⟨η(t)⟩ k J ′ -E η [⟨η(t)⟩ k J ′ ] > p k + J -E η [⟨η(t)⟩ k J ′ ] . (2.22)
Since by hypothesis γt > L 3 and 0 ∈ G(η, L), Lemma 2.6 with α small enough guarantees that

E η [⟨η(t)⟩ k J ′ ] ≤ (1 + c L) sup{⟨η⟩ k L ′ , L ′ ≥ L} ≤ (1 + c L)(p k + L ) so that p k + J -E η [⟨η(t)⟩ k J ′ ] ≥ J -L -c(p k + L ) L ≥ ( J -L ) 2
, where for the last inequality we have used the hypothesis that L( J -L ) is large enough. This applied to (2.22) gives

P η ⟨η(t)⟩ k J ′ > p k + J ≤ P η ⟨η(t)⟩ k J ′ -E η [⟨η(t)⟩ k J ′ ] ≥ ( J -L ) 2 ≤ 2 e -c( J -L ) 2 J ′d , (2.23)
where the last inequality follows from Lemma 2.5. Conversely, we bound the second summand of (2.21) by noticing that, by Lemma 2.6,

E η [⟨η(t)⟩ k J ′ ] ≥ (1 -c L) inf{⟨η⟩ k L ′ , L ′ ≥ L} ≥ (1 -c L)(p k -L ), so that p k -J -E η [⟨η(t)⟩ k 0,J ′ ] ≤ -( J -L ) 2 < 0.
Hence, as before,

P η ⟨η(t)⟩ k J ′ < p k -J ≤ P η ⟨η(t)⟩ k J ′ -E η [⟨η(t)⟩ k 0,J ′ ] > ( J -L ) 2 ≤ 2 e -c( J -L ) 2 J ′d .
(2.24) Plugging (2.23) and (2.24) into (2.21) and this back into (2.20) we finally obtain

P η 0 ∈ G(η(t), J) ≤ J ′ ≥J k∈T ∶ p k >0 4 e -cJ ′d ( J -L ) 2 ≤ c 1 k∈T ∶ p k >0 e -cJ d ( J -L ) 2 ( J -L ) 2 ≤ c 1 (2 N ) 2d e -cJ d ( J -L ) 2 ( J -L ) 2 .

Proof of Theorem 1

Given a vector ⃗ v ∈ R d , we denote, for t ≥ 0,

X ⃗ v t ∶= ⟨X t , ⃗ v⟩ ,
where ⟨⋅, ⋅⟩ denotes the usual inner product. In order to prove Theorem 1, we will actually prove the following proposition, which is clearly equivalent to Theorem 1:

Proposition 3.1 (Equivalent of Theorem 1). Assume (1.1) and consider ⃗ v ∈ R d with norm 1 such that v ∶= ⟨E µ [D], ⃗ v⟩ > 0.
For all ε > 0, there exists γ(ε) such that, for all γ ≥ γ(ε), P -a.s. it holds that, for t large enough,

X ⃗ v t t ∈ (v -ε, v + ε) .
The proof of Proposition 3.1 is postponed to Subsection 3.4. Without being too rigorous, we call trap a region where an anomalous density of some type of particles occurs. If all sites of a given region are L-good for some L > 0, we say that there are no traps larger than L in that region. We define now a sequence of positive numbers (φ L ) L∈N . One can think of φ L as the size of "acceptable" traps in a ball of radius L. We are not interested in a sharp estimate of the typical size of the maximal trap (that should be of order log L). Instead, in order to simplify our computation, we choose rather to overestimate this typical size and define, for L ∈ N, φ L ∶= L 1 100 .

(3.1) 3.1. Outline of the proof. The proof relies on a renormalisation procedure adapted from [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF]. We fix throughout the rest of the section a vector ⃗ v satisfying the assumption of Proposition 3.1. Heuristically, the hypothesis we want to iterate is the following: "If the box of size t at time 0 around the walker has no trap larger than φ t , then, at time t, the walker is, with large probability, at a distance (v + o(1)) t from the origin in the direction ⃗ v". The first step of the procedure (see Proposition 3.2) relies on a homogenization obtained by choosing a large enough finite time T and some γ large enough chosen accordingly. To prove the iteration itself (which consists in going from scale t to scale t 2 ) we divide the space-time box of size t 2 into boxes of size t and use Proposition 2.4 to control the size of the traps in each of these sub-boxes. This allows us to apply the iteration hypothesis at scale t.

Initialization of the renormalization.

Proposition 3.2. For all ε > 0, there exists N large enough, T ∈ N large enough and γ > 0 large enough (e.g., γ ≥ φ 3 T ) such that the following holds:

Given η ∈ S Z d satisfying y ∈ G(η, φ T ) ∀y ∈ B T , it holds that P η X ⃗ v T -vT ≥ εT ≤ e -φ 1 4
T . Proof. We will first prove that

P η (X ⃗ v T ≤ (v -ε)T ) ≤ 1 2 e -φ 1 4 T . (3.2)
Since we have no information on the particle at the origin at time 0, we just bound the first step with the worst case:

P η X ⃗ v T ≤ (v -ε)T ≤ P η X ⃗ v T -X ⃗ v 1 ≤ (v -ε)T + 1 . For j ∈ I we let v j ∶= ⟨⃗ v, e j ⟩ ∈ [-1, 1].
For simplicity we suppose that v j = v i for all i = j (the proof can be easily adapted to the other cases). We also define v max ∶= max j∈I {v j }, v min ∶= -v max and their relative indices j max ∶= arg max v max , j min ∶= -j max . By eventually enlarging the original space, we consider a sequence (Y k ) k∈N of i.i.d. random variables under P η with values in {v -d , ..., v d }. The Y k 's are independent of η, of the interchange process and of the random walker, and they satisfy

P η (Y 1 = v j ) = E µ [s j ] -δ for j = j min E µ [s j min ] + (2d -1)δ for j = j min ,
where δ > 0 is chosen small enough and N ∈ N is chosen large enough such that 2 -(N -1) d < δ < min{E µ [s i ] > 0} and 2dv max δ < ε 2. Notice that: (i) Y 1 is well defined, or can be made well defined with little effort. In fact, if E µ [s j ] > 0 for all j ∈ I, Y 1 is well defined because of the choice of δ that we made. If instead there is some j = j min such that E µ [s j ] = 0, then we can easily modify the law of Y 1 so that we define P η (Y 1 = v j ) = 0 and adapt the definition of

P η (Y 1 = v min ) consequently; (ii) E η [Y 1 ] > v -ε 2. In fact, it is straightforward to check that E η [Y 1 ] = v + δ (2d -1)v min - j =j min v j = v -2dv max δ > v -ε 2,
where we have used the symmetry of the v ⋅ 's for the second equality, which implies ∑ j =j min v j = v max and v min = -v max . In analogy with [START_REF] Huveneers | Random walk driven by the simple exclusion process[END_REF], for m ≥ 1 we define the events

E m ∶= y ∈ G(η(m), J), ∀y ∈ B m+1 with J ∶= ⌊φ 1 2
T ⌋. and E 0 ∶= y ∈ G(η(0), φ T ), ∀y ∈ B 1 . Notice that, by hypothesis, P η (E 0 ) = 1. Loosely speaking, the event E c m indicates that at step m the random walk sees around itself an unfavorable environment. Our aim is to show that

P η (X ⃗ v T -X ⃗ v 1 ≤ (v -ε)T + 1) ≤ P η T -1 m=1 Y m ≤ (v -ε)T + 1 + T -1 m=1 P η (E c m-1 ). (3.3)
Before showing why this is true, we explain how this implies the first half of the lemma, i.e. equation (3.2). The first term of the right-hand-side of (3.3) can be bounded with classical large deviations for sequences of i.i.d. random variables: Keeping in mind that E η [Y 1 ] ∈ (v -ε 2, v), we have

P η T -1 m=1 Y m ≤ (v -ε)T + 1 ≤ e -cT ≤ e -φ 1 3 T . (3.4)
The second term in the right hand side of (3.3) can be bounded thanks to Proposition 2.4 and by taking T and, consequently, γ large enough as

T -1 m=1 P η (E c m-1 ) ≤ T -1 m=1 y∈Bm P η y ∈ G(η(m -1), J) ≤ c T -1 m=1 y∈Bm e -cJ d (ε J -ε φ T ) 2 (ε J -ε φ T ) 2 ≤ c T d+1 e -cJ d (ε J -ε φ T ) 2 (ε J -ε φ T ) 2 ≤ e -φ d 3 T . (3.5)
Putting back (3.4) and (3.5) into (3.3) we obtain (3.2).

Let us go back to the proof of (3.3). We show that, for any m ≥ 1 and any a ∈ R,

P η (X ⃗ v m+1 -X ⃗ v 1 ≤ a) ≤ P η (X ⃗ v (m-1)+1 + Y m -X ⃗ v 1 ≤ a) + P η (E c m-1 ) . (3.6)
Iterating this formula and using Fubini gives (3.3). We bound

P η (X ⃗ v m+1 -X ⃗ v 1 ≤ a) ≤ E η P η (X ⃗ v m+1 -X ⃗ v m + X ⃗ v m -X ⃗ v 1 ≤ a η(m -1), X 1 , X m ) ⋅ 1 E m-1 + P η (E c m-1 ) . (3.7)
For any b ∈ R we call J (b) ∶= {j ∈ I ∶ v j ≤ b} and compute

P η (X ⃗ v m+1 -X ⃗ v m ≤ b η(m -1), X 1 , X m ) = j∈J(b) k∈T P η X ⃗ v m+1 -X ⃗ v m = v j η(m -1), X 1 , X m , T (η Xm (m)) = k P η (T (η Xm (m)) = k η(m -1), X 1 , X m ) ≤ j∈J (b) k∈T k j + 1 2 N P η (T (η Xm (m)) = k η(m -1), X 1 , X m ) . (3.8)
On E m-1 , using Markov property, we can apply Lemma 2.6 with

M = 0, t = 1, L = ⌊φ T ⌋ if m = 1 and L = ⌊φ 1 2
T ⌋ if m ≥ 2 to control the probability in the last display, so that if T is large enough we have, since γ ≥ φ 3

T , P η (T (η Xm (m)) =k η(m -1), X 1 , X m ) ≤ 1 + c L d+1 γ d+1 2 + 1 γ 1 2 -α sup ⟨η(m -1)⟩ k z,L ′ ∶ L ′ ≥ L, z ∼ X m ≤ 1 + c 1 φ T (p k + φ 1 2 T ) = p k + δ T ,
where the last inequality is valid for any m ≥ 1 and where δ T is some function that goes to 0 as T grows. Putting this back into (3.8) we obtain that on E m-1

P η (X ⃗ v m+1 -X ⃗ v m ≤ b η(m -1), X 1 , X m ) ≤ j∈J(b) k∈T k j + 1 2 N p k + c δ T ≤ j∈J(b) k∈T k j 2 N p k + J (b) 2 N + c δ T , (3.9)
where J (b) is the cardinality of J (b). We notice that ∀j = j min we have

∑ k∈T k j 2 N p k ≤ P η (Y m = v j ) + δ. On the other hand, ∑ k∈T k j min 2 N p k ≤ P (Y m = v j min ) -(2d -1)δ. Hence on E m-1 , P η (X ⃗ v m+1 -X ⃗ v m ≤ b η(m -1), X 1 , X m ) ≤ P (Y m ≤ b) -(2d -J (b) )δ + J (b) 2 N + c δ T ≤ P (Y m ≤ b)
if T is big enough and J (b) ≤ 2d -1, since we chose δ > 2d 2 N . This last inequality is trivial in the case J(b) = 2d, that is b ≥ v max , as both terms are equal to 1. Plugging the last display back into (3.7), we easily obtain (3.6).

We prove the "other half" of the lemma in a completely specular way. We need

P η (X ⃗ v T ≥ (v + ε)T ) ≤ 1 2 e -φ 1 4 T , (3.10)
since this combined with (3.2) gives the final result. As before, we bound the first step with the worst case

P η (X ⃗ v T ≥ (v + ε)T ) ≤ P η (X ⃗ v T -X ⃗ v 1 ≥ (v + ε)T -1
) and define a new sequence of i.i.d. random variables ( Ỹk ) k∈N with values in {v -d , ..., v d }, independent of the interchange process and of the walker and such that

P η ( Ỹ1 = v j ) = E µ [s j ] -δ for j = j max E µ [s jmax ] + (2d -1)δ for j = j max .
Similar comments (and eventually corrections) made for the Y j 's hold for the Ỹj 's, that is, the Ỹj 's are (or can be easily made) well defined and

E η [ Ỹ1 ] ∈ (v, v +ε 2).
We keep the previous definition of the good events (E m ) m∈N and aim to prove

P η (X ⃗ v T -X ⃗ v 1 ≥ (v + ε)T -1) ≤ P η T -1 m=1 Ỹm ≥ (v + ε)T -1 + T -1 m=1 P η (E c m-1 ). (3.11)
As we have seen before, we can use a mild large deviations argument as in (3.4) combined with (3.5) to bound (3.11) and conclude (3.10).

The proof of (3.11) is similar to the one of (3.3). We proceed in the same way as before and obtain the equivalent of (3.9) that now reads as follows: For any b ∈ R, m ≥ 1, on the event E m-1 we have that

P η (X ⃗ v m+1 -X ⃗ v m ≥ b η(m -1), X 1 , X m ) ≤ j∉J (b) k∈T k j 2 N p k + 2d -J (b) 2 N + c δ T ,
where again δ T is some function that goes to 0 when T grows to infinity. For all j = j max we have ∑ k∈T

k j 2 N p k ≤ P (Y m = v j ) + δ, while ∑ k∈T k jmax 2 N p k ≤ P (Y m = v jmax ) -(2d -1)δ. Hence, P η (X ⃗ v m+1 -X ⃗ v m ≥ b η(m -1), X 1 , X m ) ≤ P (Y m ≥ b) -J (b) δ + (2d -J (b) )2 -N + c δ T ≤ P (Y m ≥ b)
if T is big enough and J (b) ≥ 1 as δ > 2d 2 N (here again, if J (b) = 0, that is b < v min the inequality is trivial). From there we prove easily the equivalent of (3.7) with the opposite inequality and conclude the proof of (3.11).

Renormalization step.

Proposition 3.3. Take any ε > 0. Let N , T and γ be large enough. Given η ∈ S Z d and t ≥ T such that y ∈ G(η, φ t ) ∀y ∈ B t , it holds that

P η X ⃗ v t -vt ≥ εt ≤ e -φ 1 4 t .
Proof. We consider T so large that the conclusion of Proposition 3.2 holds for the time T 1 3 and consider t ≥ T . We first prove that

P η X ⃗ v t < (v -ε) t ≤ 1 2 e -φ 1 4 t .
(3.12)

We define a sequence of times (t n ) n∈N such that t 0 ∈ [T 1 3 , T ] and, for n ≥ 0,

t n+1 ∈ [t 2 n , (t n + 1) 2 ] , (3.13)
so that for some ñ ≥ 0 we have t ñ = t (for example define t ñ = t for a suitable ñ and then define recursively t k-1 = ⌊ √ t k ⌋ until reaching the interval [T 1 3 , T ]). We also define a sequence of positive real numbers (c n ) n∈N such that

v ≥ c n ∶= 1 2 3 - n k=0 ε 1 + ε k v ≥ (1 -ε 2) v for n ∈ N.
Note that (c n ) n∈N is a decreasing sequence and that c 0 = v and lim n→∞ c n = v(1 -ε 2). We want to prove by induction that, given n ∈ N and η ∈ S Z d , if ∀y ∈ B tn it holds that y ∈ G(η, φ tn ), then P η (X ⃗ v tn < c n t n ) ≤ 1 2 e -φ 1 4 tn . (3.14) Proposition 3.2 takes care of the initialization step n = 1. We assume now that (3.14) holds for some n ≥ 1 and we show that this implies the case n + 1. By (3.13) we can write t n+1 = t n (t n -1) + r, where the rest r is a number between, say, t n and 4t n . We first have to wait an initial time lapse, since we can not use the iteration assumption at time 0 as the maximal trap could be of order φ t n+1 instead of φ tn :

P η (X ⃗ v t n+1 < c n+1 t n+1 ) ≤ P η (X ⃗ v t n+1 -X ⃗ v r < c n+1 t n+1 + r) .
We define on the same probability space (enlarged if necessary) a sequence (Z k ) k∈N of i.i.d. random variables independent from η, from the interchange process and from the walker, with distribution

P η (Z k = c n t n ) = 1 -e -φ 1 4 tn , P η (Z k = -t n ) = e -φ 1 4 tn .
Using our inductive hypothesis we aim to show that

P η (X ⃗ v t n+1 -X ⃗ v r < c n+1 t n+1 + r) ≤ P η tn-1 k=1 Z k ≤ c n+1 t n+1 + r + y∈Bt n+1 r≤s≤t n+1 P η y ∈ G(η(s), φ tn ) . (3.15)
To obtain this, we just show that, for all m ≥ 1 and for any a ∈ R, we have

P η (X ⃗ v mtn+r -X ⃗ v r ≤ a) ≤ P η (X ⃗ v (m-1)tn+r -X ⃗ v r + Z m ≤ a) + P η (E c m-1 ) , (3.16)
where for m ≥ 0 E m ∶= {y ∈ G(η(mt n + r), φ tn ), ∀y ∈ B (m+1)tn+r } is the event of having a favorable environment at step m (i.e., at time mt n + r).

Let us prove (3.16):

P η (X ⃗ v mtn+r -X ⃗ v r ≤ a) = P η (X ⃗ v mtn+r -X ⃗ v (m-1)tn+r + X ⃗ v (m-1)tn+r -X ⃗ v r ≤ a) ≤ x,y∈Z d P η (X ⃗ v mtn+r -X ⃗ v (m-1)tn+r ≤ a -⟨y -x, ⃗ v⟩ A x,y )P η (X (m-1)tn+r = y, X r = x) + P η (E c m-1 )
with A x,y ∶= {X (m-1)tn+r = y, X r = x, E m-1 }. Thanks to the inductive step we have that

P η (X ⃗ v mtn+r -X ⃗ v (m-1)tn+r ≤ a -⟨y -x, ⃗ v⟩ A x,y ) ≤ P η (Z m ≤ a -⟨y -x, ⃗ v⟩),
and therefore

P η (X ⃗ v mtn+r -X ⃗ v r ≤ a) ≤ P η (Z m + X ⃗ v (m-1)tn+r -X ⃗ v r ≤ a) + P η (E c m-1
) . This proves (3.16). Iterating (3.16) and bounding ∑ tn-1 j=1 P η (E c j ) with the union bound of the probability that no trap bigget than φ tn appears after time r and until time t n+1 in the whole ball of radius t n+1 gives (3.15).

We are left to bound the r.h.s. of (3.15). The first summand is equal to

P η tn-1 k=1 Z k -E η [Z k ] ≤ c n+1 t n+1 + r -E η [Z k ](t n -1) ≤ P η tn-1 k=1 Z k -E η [Z k ] ≤ (t n -1) c n+1 t n -E η [Z k ] + 8t n ≤ P η tn-1 k=1 Z k -E η [Z k ] ≤ -t 3 4 n (t n -1) ≤ e -c t 1 2 n ≤ e -φ 1 3 tn , (3.17)
where we have used the fact that c n+1 < 1 and that r ≤ 4t n for the first inequality.

The second inequality just comes from the definitions of t n and c n . We point out that for this inequality there might be the need to choose a T bigger than the one considered until this point, depending on ε; this constitutes no problem, since in this case it will be sufficient to repeat the proof with a bigger T (and hence a bigger γ). The last inequality in (3.17) is just a classical concentration inequality for sums of independent bounded random variables (note that Z k ≤ t n a.s.).

For the second summand in the r.h.s. of (3.15) we assume (see (3.14)) that y ∈ G(η, φ t n+1 ) for any y ∈ B t n+1 and notice that, by the choice made in (3.1), γr ≥ γt n ≥ φ 3 t n+1 . We can therefore use Proposition 2.4 with L = φ t n+1 and J = φ tn (we can suppose to have taken T large enough such that the condition "L( J -L ) large enough" is satisfied) to bound

y∈Bt n+1 r≤s≤t n+1 P η y ∈ G(η(s), φ tn ) ≤ c 1 t d+1 n+1 exp{-c 2 φ d tn ( φt n -φt n+1 ) 2 } ( φt n -φt n+1 ) 2 ≤ e -φ d 3 tn , (3.18)
where the last bound comes from the explicit expression (2.1). Plugging (3.18) and (3.17) into (3.15) gives the conclusion of (3.14), so that (3.12) is proven.

For the converse

P η X ⃗ v t > (v + ε)t ≤ 1 2 e -φ 1 4
t we follow a very similar strategy. We take the same definition of t n and a new sequence of c n 's, this time increasing:

c n ∶= 1 2 1 + n k=0 ε 1 + ε k v .
The inductive step in this case will be if ∀y ∈ B tn it holds that y ∈ G(η, φ tn ), then P η (X ⃗ v tn > c n t n ) ≤ 1 2 e -φ 1 4 tn .

We define new random variables (Z k ) such that Z k = c n t n with probability 1 -e -φ 1 4 tn and Z k = t n with probability e -φ 1 4 tn . The events E m-1 stay the same. We can now just follow the same steps as before. The only slight difference is with estimate (3.17), which now reads

P η tn-1 k=1 Z k ≥ c n+1 t n+1 + r ≤ P η tn-1 k=1 Z k -E η [Z k ] ≥ (t n -1) c n+1 t n -E η [Z k ] ≤ P η tn-1 k=1 Z k -E η [Z k ] ≥ t 3 4 n (t n -1) ≤ e -c t 1 2 n ,
which holds with the same arguments as before.

3.4. Proof of Proposition 3.1. We fix ε > 0 and pick N , T and γ large enough so that Proposition 3.3 holds. Since under P the initial distribution for the environment is a product measure, by a union bound we have that By the Borel-Cantelli lemma, it then follows from Proposition 3.3 that Pa.s., eventually X ⃗ v t t ∈ (v -ε, v + ε).

Appendix A.

A.1. Proof of Claim 2.8. Take f ∶ Z d → R such that f (x) -f (x + e i ) ≥ 0 for all x ∈ Z d with ⟨x, e i ⟩ ≥ 0 and such that f (x) = f (x i ) for all x ∈ Z d , where xi ∶= (x 1 , x 2 , ..., -x i , ..., x d ). Consider f (t, x), the unique solution of ∂ t f (t, x) = γ∆f (t, x) ∀t ≥ 0 f (0, x) = f (x) .

Then we have that (1) f (t, x) = f (t, xi ) for all t ≥ 0, x ∈ Z d and (2) f (t, x)f (t, x + e i ) ≥ 0 for all t ≥ 0 and x ∈ Z d with ⟨x, e i ⟩ > 0. The first property is true by symmetry. The second can be explained by noticing, for example, that the continuous-in-time function g(t, x) ∶= f (t, x) -f (t, x + e i ) if ⟨x, e i ⟩ ≥ 0 f (t, x) -f (t, xe i ) otherwise is clearly everywhere positive for t = 0, but also stays positive for all t > 0. In fact, take a time t such that g is positive everywhere; then, in the points x where g(t, x) = 0, one has ∂ t g(t, x) ≥ 0, as it is easy to verify. To conclude the proof, just take f (t, x) = p M (t, x).

A.2. Proof of the Corollary 2.9. If y and y ′ are in the same crown there is nothing to prove. Suppose then that y ′ ∈ C n ′ and y ∈ C n with n ′ > n. Consider xn ′ and an e ∈ N such that ⟨x n ′ , e⟩ > 0 and xn ′ -me belongs to C n for some m ∈ N. Applying Claim 2.8 m-times, we have that p M (t, xn ′ -me) ≥ p M (t, xn ′ ) and therefore p + M (t, y) ≥ p + M (t, y ′ ). The same argument reversed gives the p - M (⋅, ⋅) case.

A.3. Proof of Claim 2.10. We focus on (2.18) and split the sum into three parts:

n≥L E M (t, n) C n = M--1 n=L E M (t, n) C n + M+-1 n=M- E M (t, n) C n + ∞ n=M+ E M (t, n) C n =∶ H 1 + H 2 + H 3 , (A.1)
where we have called M -∶= ⌊M -(γt) 1 2+ε ⌋ ∨ L and M + ∶= ⌊M + (γt) 1 2+ε ⌋ ∨ L (note that the first two sums might be empty). Part H 3 falls into a large deviations regime, since it can be dominated by the probability that a walker starting from far away enters the ball of radius M by time t:

H 3 = ∞ n=M+ E M (t, n) C n ≤ c ∞ n=M+ p M (t, xn ) n d-1 = c ∞ n=M+ n d-1 M d P xn (Y t ∈ B M ),
where (Y t ) t≥0 is a simple random walk that jumps at rate γt. Notice that P xn (Y t ∈ B M ) ≤ P 0 ( Y t ≥ n -M ) ≤ e -c 1 (n-M ) 2 (γt) , where for the last inequality we have applied the continuous-time version of the large deviations estimate [LL10, Eq. 2.7]. Hence, as can be easily checked,

H 3 ≤ c ∞ n=M+ n d-1
M d e -c 1 (n-M ) 2 (γt) ≤ c 2 e -c 3 (γt) 2ε . (A.2)

P

  (∃y ∈ B t s.t. y ∉ G(η, φ t )) ≤ y∈Bt L≥φt k∈T P ⟨η(t)⟩ k y,L -p k > φt ≤ y∈Bt L≥φt k∈T ∶ p k >0 e -cL d 2 φ t ≤ T t d e -c φt 2 φ t c 2 φt ≤ c 1 e -t c 2 .

M. Salvi was financially supported by the European Union's Horizon 2020 research and innovation program under the Marie Sk lodowska-Curie Grant agreement No 656047. F. Simenhaus research was supported by the ANR-15-CE40-0020-01 grant LSD and the ANR/FNS-16-CE93-0003 grant MALIN.

Part H 1 , if not empty, can be treated similarly as it can be dominated by the probability that a walker that starts well inside the ball of radius M will leave the ball by time t:

Part H 2 , when not empty, is more delicate. For M -≤ n < M + we write

where

is the Gaussian kernel.

We treat together A 1 and A 3 from (A.4), since the calculation here below is valid for both of them (as can be seen simply by substituting xn by xn ). We consider just A 1 for simplicity and write

The sum over Ŝ2 can be bounded by

where (Y t ) t≥0 is a simple random walk on Z d starting at the origin that jumps at rate γt and Z is a d-dimensional normal random variable with zero mean and covariance γt ⋅ Id. Inserting the last two displays into (A.5) shows that

as can be checked by distinguishing the case M > t 1 2+ε and M ≤ t 1 2+ε .

We estimate now A 2 . Using the definition of Ŝ1 and Ŝ2 given above and

The sums over Ŝ2 and Š2 can be bounded by

where Z is again a d-dimensional normal random variable with zero mean and variance γt ⋅ Id. We are left with the sums over Ŝ1 and Š1 of (A.7). We use once more the triangular inequality to obtain

where we have called, for z ∈ R d , G(t, z) = ∫ K(z) G(t, w) dw, and K(z) is the cube of size one centered in z. The first and third term of (A.9) can be roughly bound thanks to the mean value theorem: For each y ∈ Ŝ1

and the same bound holds for terms of the sum in Š1 .

For bounding the middle term in (A.9), we call D = D(n) ∶= ⋃ y∈ Ŝ1 K(x n -y) ⊆ R d and Ď = Ď(n) ∶= ⋃ y∈ Š1 K(x n -y) ⊆ R d and notice that ∑ y∈ Ŝ1 G(t, xny) is exactly the probability that a Brownian Motion (W t ) started at the origin ends up in D after time γt (the same for Ď). Call R the rotation that brings xn on the half-line from the origin and passing through xn and let Ď′ ∶= R( Ď). By rotation and translation invariance of W t we have then that

and we further notice that D ∖ Ď′ and Ď′ ∖ D have volume smaller than c (M ∧ (γt) 1 2+ε ) d-1 , i.e. the smallest between the d -1-dimensional surface of B M and the d -1-dimensional surface of B t 1 2+ε times a constant that depends on the dimension but not on M or n.

In the case M > (γt) 1 2+ε , expression (A.11) can therefore be bounded by c 1 (γt) -1 2+ε(d-1) . Using this estimate and (A.10) for bounding (A.9), and putting this together with (A.8) back into (A.7), we obtain

In the case M ≤ (γt) 1 2+ε we further notice the following: For n ∈ [L, t 1 2+ε ], D and Ď are exactly the same object, so that D and Ď′ have the same volume. It follows that also D ∖ Ď′ and Ď′ ∖ D have the same volume, and this volume is smaller than c M d-1 as explained before. Hence, for these n's, we can bound (A.11) by

, where z + and z -are, respectively, the farthest and the closest point to the origin into

For the second inequality we have used the mean value theorem, while for the third we have used the fact that the distance between z + and z -is at most a constant times M and then we have took the worst-case for ξ (corresponding to ξ ≃ (γt) 1 2 ). For n ∈ (t 1 2+ε , M + -1] we just bound (A.11) with cM d-1 (γt) -d 2 . We obtain

This, together with (A.12) and (A.6), shows that H 2 ≤ c (γt) -1 2+εd . Putting back together this bound for H 2 , the bound for H 3 (A.2) and for H 1 (A.3) into (A.1) gives (2.18). Our estimates for A 1 , A 2 and A 3 and (A.4) also imply (2.19).