The cost of resetting discrete-time random walks
John C. Sunil, Richard A. Blythe, Martin R. Evans, Satya N. Majumdar · 2025
Read The cost of resetting discrete-time random walks by John C. Sunil, Richard A. Blythe, Martin R. Evans, Satya N. Majumdar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03697.txt.
Introduction
John Sunil, Richard Blythe, Martin Evans, and Satya Majumdar wrote a 2025 paper on the cost of a wandering search. Their model is a random walker that jumps step by step and, now and then, restarts from home. Each jump and each restart carries a cost, like time or fuel. They ask how the total cost of reaching a target is spread out.
Using a backward equation for the walk, they turn the problem into an integral equation of a classic form. They solve it exactly for broad choices of jump cost and some restart costs. For one key case, where jumps mimic run-and-tumble motion like that of bacteria, the equation shrinks to a simpler one that is easy to solve. The results show whether restarts or long jumps drive up the final bill.
Catalog record
| CREATOR | John C. Sunil, Richard A. Blythe, Martin R. Evans, Satya N. Majumdar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-03697
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The cost of resetting discrete-time random walks John C. Sunil, Richard A. Blythe, Martin R. Evans, Satya N. Majumdar Abstract We consider a discrete-time continuous-space random walk, with a symmetric jump distribution, under stochastic resetting. Our aim is to understand how costs, associated with the random walk jumps and the resetting, contribute to the total cost of the motion. We calculate the distribution of the total cost up to first passage of the random walker to a target. By using the backward master equation approach we demonstrate that the distribution of the total cost can be reduced to a Wiener-Hopf integral equation. The resulting integral equation can be exactly solved (in Laplace space) for arbitrary cost functions for the jump and selected functions for the reset cost. We show that the large cost behaviour is dominated by resetting or the jump distribution according to the choice of the jump distribution. In the important case of a Laplace jump distribution, which corresponds to run-and-tumble particle dynamics, and linear costs for jumps and resetting, the Wiener-Hopf equation simplifies to a differential equation which can easily be solved. , , , August 24, 2026 Journal: \JSTAT 1 Introduction Over time, a physical entity may undergo motions of several different types. For example, a foraging animal [ 1 , 2 ] might spend time searching a local area for food, and occasionally traverse greater distances more rapidly to locate a more fertile patch. Different costs may be associated with these different motions, for example, an energy cost with the local moves and the risk of moving to a unknown area with the longer-range moves. The effect of combining a ‘normal’ motion (such as diffusion or run and tumble dynamics) with stochastic resetting to an initial or other fixed position has attracted intense scrutiny [ 3 , 4 , 5 , 6 , 7 ] , wherein the reset has a cost that may be a time penalty [ 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 ] , energetic cost [ 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 ] or entropy production cost [ 24 , 25 ] . Here, our aim is to understand how costs associated with the normal motion and the resetting combine, with a particular focus on properties up to the first passage to a pre-determined position [ 26 , 27 , 28 , 29 , 30 ] and identifying regimes where one cost dominates. These types of first passage problems model scenarios such as a foraging animal successfully finding food, or the decision to buy or sell in financial markets. We pursue our aim in the context of a random walker in discrete time and continuous space, where the normal motion comprises jumps drawn from a general distribution, and a reset to the initial position occurs with a constant probability at each time step. More precisely, we denote the position of the random walker at the k^{\text{th}} time step as x_{k} . The random walker jumps to the new position x_{k}+\eta_{k} with a probability (1-r) with \eta drawn from a jump distribution f(\eta) . With complementary probability r the random walker is reset to position x_{r} . Resetting in discrete-time jump processes, without costs, was studied in [ 5 ] . Here we introduce two separate cost functions for the jumps and the resets, both of which depend on the distance travelled by the particle: for jumps the cost is h(\eta_{k}) and for resets the cost is g(x_{r}-x_{k-1}) . We note that the jump dynamics is very general, encompassing, for example, standard diffusion and Lévy flights as special cases. As such, we extend separate studies of the cost of diffusion with resetting [ 13 , 14 , 12 , 10 , 25 , 31 ] and the cost of random walk dynamics without resetting [ 32 , 33 , 34 , 35 ] . In particular, [ 13 ] considered diffusion for a general class of resetting costs, while [ 35 ] found a general formula for the cost up to first passage to the target for a general jump process with a general cost function but no resetting. The model considered here thus combines the disparate features of [ 13 ] and [ 35 ] to obtain a model of a discrete-time jump process with resetting. The discrete-time jump process may also be mapped onto the motion of a run and tumble particle in continuous time, as noted in [ 35 ] . A run and tumble particle models an active entity such as a bacterium that consumes energy from the environment and moves via self-propulsion [ 36 ] . The particle performs a run, in its direction of motion, whose length is a random variable before tumbling and choosing anew its direction of motion. In the mapping onto a discrete-time jump process the run length becomes the jump length of the discrete-time process and the discrete times become the tumbling times. In one dimension a symmetric jump length distribution corresponds to the run and tumble particle choosing the forward or backward directions with equal probability. The standard run and tumble particle, also known as a persistent random walker, moves with constant speed v_{0} and the tumbles occur at constant rate so that the time between tumbles is exponentially distributed. This amounts to a Laplace distribution for the jumps f(\eta)=(\lambda/2)\exp(-\lambda|\eta|) where \lambda=\gamma/v_{0} and \gamma is the tumbling rate. Resetting of run and tumble dynamics has been of particular interest [ 6 , 37 , 38 , 39 , 40 ] and it is natural to consider a resetting cost for this process. We study the general discrete-time jump process described in the preceding paragraphs for two different choices of reset cost functions: constant cost and linear cost, with arbitrary jump distributions and jump costs. The constant reset cost plays the role of a refractory period after each reset [ 8 , 9 ] , whereas a linear cost plays the role of the time required to reset the particle back to the starting position with a constant velocity [ 10 , 12 , 13 , 14 ] . Our main findings take the form of exact closed form expressions in Laplace space for the total cost up to first passage to the target for each of the two reset cost functions. Further we also compute how the cost behaves in the asymptotic regime. In the case of constant resetting cost, our results reveal that for jump cost distributions with finite mean cost per jump, resetting converts the power-law distribution of large costs observed in [ 35 ] to an exponentially distributed tail. On the other hand, when the mean cost per jump is not finite, the jumps dominate and the power-law tail is retained. The paper is organised as follows, in Section 2 , we define the model of a discrete time random walker under stochastic resetting, using which we derive the backward master equation (BME) for the total cost up to first passage to the target. We then present the important exactly solvable case of a Laplace jump distribution (negative exponential of