Elephant random walk with attributed steps and extractions of random sizes
Pith reviewed 2026-05-10 06:05 UTC · model grok-4.3
The pith
A customer sampling model in an oligopolistic market produces a variant of the elephant random walk whose position tracks relative sales of two products.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The resulting stochastic process may be represented as a variant of the celebrated elephant random walk, with the relative performance (in terms of sale) of A with respect to B, up to and including the n-th sale, captured by the position S_n of the walker at time n. We study the almost sure convergence of S_n/n, as well as the convergence in distribution of suitably scaled versions of S_n (where the scaling depends on the regime we are in).
What carries the argument
The elephant random walk variant with steps attributed according to the stochastic decision rule based on random-sized samples from past customers and fixed satisfaction probabilities q1 and q2.
Load-bearing premise
The satisfaction probabilities q1 and q2 are constants independent of everything else, and the customer's decision rule produces steps that match those of the elephant random walk.
What would settle it
Running a simulation of the sampling process for large n and observing that S_n/n fails to converge would disprove the almost sure convergence claim.
read the original abstract
We study a model of market economics wherein the $(n+1)$-st customer, for each $n\geqslant N$, with $N$ being a prespecified positive integer, draws a sample of (random) size $K_{n}$, either with replacement or without, from the customers of the past. Each sampled customer is queried as to which of the two products, A and B, available in the oligopolistic market, they chose, and whether they are satisfied or not with their choice. The $(n+1)$-st customer now employs a stochastic rule, based on the information collected from the sampled customers, to decide which of the two products to buy. The probability that a customer is satisfied with the product they have purchased equals $q_{1}$ when the product is A, and $q_{2}$ when it is B, independent of all else. The resulting stochastic process may be represented as a variant of the celebrated elephant random walk, with the relative performance (in terms of sale) of A with respect to B, up to and including the $n$-th sale, captured by the position $S_{n}$ of the walker at time $n$. We study the almost sure convergence of $S_{n}/n$, as well as the convergence in distribution of suitably scaled versions of $S_{n}$ (where the scaling depends on the regime we are in).
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a market model in which the (n+1)st customer draws a random sample of size K_n (with or without replacement) from the first n customers, queries their product choices and satisfaction levels, and then selects product A or B according to a stochastic rule driven by the sampled satisfaction indicators. Satisfaction probabilities are q1 for A and q2 for B, independent of everything else. The resulting difference process S_n (relative sales of A versus B) is asserted to be a variant of the elephant random walk. The authors prove almost-sure convergence of S_n/n and convergence in distribution of suitably scaled versions of S_n, with the scaling regime depending on the model parameters.
Significance. If the representation as an ERW variant holds and the limit theorems are established, the work extends the ERW framework to random memory kernels arising from sampling, which could be relevant for modeling herding or information diffusion in markets. The a.s. and distributional results would then give concrete predictions for long-run market shares and fluctuations under random sampling. The strength of the contribution rests on whether the extra randomness in the memory kernel is fully controlled by the existing ERW machinery or requires genuinely new arguments.
major comments (2)
- Abstract and model-definition section: the claim that the process 'may be represented as a variant of the celebrated elephant random walk' is load-bearing for the subsequent limit theorems. Because K_n is random and the next step is chosen via a stochastic rule applied to a random sample, the conditional probability P(X_{n+1}=X_k | F_n) is itself a random variable that depends on the realized sample and the satisfaction indicators. Standard ERW proofs rely on a deterministic memory parameter and a fixed functional form for the conditional probabilities; the extra variance terms that appear in the recursion for E[S_{n+1}^2 | F_n] are not obviously controlled by the usual arguments. The manuscript must exhibit the explicit memory kernel and show how the a.s. and distributional proofs adapt to this randomness.
- Convergence statements (abstract): the scaling regimes for the distributional limits are stated to 'depend on the regime we are in,' but the precise conditions on q1, q2 and the distribution of K_n that delineate the diffusive, super-diffusive, or other regimes are not specified in the abstract or the provided summary. These thresholds are central to the claim that the scaling 'depends on the regime'; they must be stated explicitly and shown to be the same as (or different from) the classical ERW thresholds.
minor comments (2)
- Notation: the random variable K_n is introduced without an explicit probability law; the paper should state whether the law of K_n is fixed or may depend on n, and whether the with-replacement and without-replacement cases are treated uniformly or separately.
- The abstract refers to 'attributed steps'; this terminology should be defined at first use and related to the satisfaction indicators.
Simulated Author's Rebuttal
We thank the referee for the thorough reading and valuable feedback on our manuscript. We address each major comment below and will revise the paper to incorporate the suggested clarifications and explicit details.
read point-by-point responses
-
Referee: Abstract and model-definition section: the claim that the process 'may be represented as a variant of the celebrated elephant random walk' is load-bearing for the subsequent limit theorems. Because K_n is random and the next step is chosen via a stochastic rule applied to a random sample, the conditional probability P(X_{n+1}=X_k | F_n) is itself a random variable that depends on the realized sample and the satisfaction indicators. Standard ERW proofs rely on a deterministic memory parameter and a fixed functional form for the conditional probabilities; the extra variance terms that appear in the recursion for E[S_{n+1}^2 | F_n] are not obviously controlled by the usual arguments. The manuscript must exhibit the explicit memory kernel and show how the a.s. and distributional proofs adapt to this randomness.
Authors: We agree that the ERW representation is central and that the randomness in K_n introduces additional technical considerations. In the model definition (Section 2), the process is constructed so that the conditional law of X_{n+1} given F_n coincides with that of an ERW whose memory parameter is the random proportion of satisfied A-customers in the sampled set; this proportion is F_n-measurable. We will insert an explicit formula for the memory kernel p_n = K_n^{-1} sum_{i in sample} 1_{satisfied and chose A}. For the almost-sure convergence we adapt the standard martingale argument by verifying that the random drift remains bounded and the series of increments satisfies the necessary summability; the extra variance is controlled because the sampling is independent of the satisfaction indicators and E[K_n] is finite. For the distributional limits we add a lemma showing that the conditional second-moment recursion differs from the classical ERW case by a term whose expectation is o(n^{2alpha-1}) under the stated moment assumptions on K_n, allowing the same characteristic-function or moment-method arguments to go through after a uniform-integrability check. These details and the adapted proofs will be added in the revised version. revision: yes
-
Referee: Convergence statements (abstract): the scaling regimes for the distributional limits are stated to 'depend on the regime we are in,' but the precise conditions on q1, q2 and the distribution of K_n that delineate the diffusive, super-diffusive, or other regimes are not specified in the abstract or the provided summary. These thresholds are central to the claim that the scaling 'depends on the regime'; they must be stated explicitly and shown to be the same as (or different from) the classical ERW thresholds.
Authors: We accept that the abstract is insufficiently precise. The scaling exponent alpha is determined by the effective reinforcement parameter rho = (q1 - q2) * lim E[K_n / n] (when the limit exists) or by the appropriate moment of the distribution of K_n otherwise. The diffusive regime holds when |rho| < 1/2, yielding n^{-1/2} scaling; the super-diffusive regime occurs for |rho| > 1/2, with alpha = 1 - 1/(2 rho) or the analogous expression. These thresholds coincide with the classical ERW thresholds when K_n is deterministic and equal to a fixed fraction of n, but are shifted by the randomness in K_n. We will replace the phrase 'depend on the regime we are in' in the abstract by the explicit statement: 'with scaling n^{-alpha} where alpha = 1/2 if |rho(q1,q2, law(K))| <= 1/2 and alpha > 1/2 otherwise, with rho defined in Section 3.' The comparison to classical ERW will be added as a remark following the main theorems. revision: yes
Circularity Check
No circularity: model and limits derived from independent first-principles construction
full rationale
The process is defined directly via independent parameters (q1, q2, random K_n with/without replacement, stochastic decision rule on sampled satisfaction data) and the position S_n as cumulative relative sales performance. The statement that the resulting process 'may be represented as a variant of the elephant random walk' is a representational claim about the defined object, not a self-definitional equivalence that forces the a.s. convergence of S_n/n or the distributional limits of scaled S_n. No fitted parameters are renamed as predictions, no self-citation chain is load-bearing for the central results, and the convergence statements are presented as properties to be proved for the constructed process rather than tautological restatements of inputs. The derivation chain remains self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
free parameters (2)
- q1
- q2
Reference graph
Works this paper leans on
-
[1]
Stochastic (approximate) proximal point methods: Convergence, opti- mality, and adaptivity.SIAM Journal on Optimization, 29(3):2257–2290, 2019
Hilal Asi and John C Duchi. Stochastic (approximate) proximal point methods: Convergence, opti- mality, and adaptivity.SIAM Journal on Optimization, 29(3):2257–2290, 2019
2019
-
[2]
Kirszbraun’s theorem via an explicit formula
Daniel Azagra, Erwan Le Gruyer, and Carlos Mudarra. Kirszbraun’s theorem via an explicit formula. Canadian Mathematical Bulletin, 64(1):142–153, 2021. 38
2021
-
[3]
Generalized urn models of evolutionary processes
Michel Benaim, Sebastian J Schreiber, and Pierre Tarres. Generalized urn models of evolutionary processes. 2004
2004
-
[4]
A martingale approach for the elephant random walk.Journal of Physics A: Mathe- matical and Theoretical, 51(1):015201, 2017
Bernard Bercu. A martingale approach for the elephant random walk.Journal of Physics A: Mathe- matical and Theoretical, 51(1):015201, 2017
2017
-
[5]
On the elephant random walk with stops playing hide and seek with the mittag–leffler distribution.Journal of Statistical Physics, 189(1):12, 2022
Bernard Bercu. On the elephant random walk with stops playing hide and seek with the mittag–leffler distribution.Journal of Statistical Physics, 189(1):12, 2022
2022
-
[6]
On the multidimensional elephant random walk with stops, 2025
Bernard Bercu. On the multidimensional elephant random walk with stops, 2025. URLhttps: //arxiv.org/abs/2501.14594
-
[7]
On the center of mass of the elephant random walk.Stochastic Processes and their Applications, 133:111–128, 2021
Bernard Bercu and Lucile Laulin. On the center of mass of the elephant random walk.Stochastic Processes and their Applications, 133:111–128, 2021
2021
-
[8]
Functional limit theorems for the multi-dimensional elephant random walk.Sto- chastic Models, 38(1):37–50, 2022
Marco Bertenghi. Functional limit theorems for the multi-dimensional elephant random walk.Sto- chastic Models, 38(1):37–50, 2022
2022
-
[9]
Springer, 2008
Franco Blanchini and Stefano Miani.Set-theoretic methods in control, volume 78. Springer, 2008
2008
-
[10]
Springer, 2008
Vivek S Borkar.Stochastic approximation: a dynamical systems viewpoint, volume 9. Springer, 2008
2008
-
[11]
Introduction `a la g´eom´etrie infinit´esimale directe.(No Title), 1932
Georges Bouligand. Introduction `a la g´eom´etrie infinit´esimale directe.(No Title), 1932
1932
-
[12]
Solvable random-walk model with memory and its relations with markovian models of anomalous diffusion.Physical Review E, 90(4):042136, 2014
D Boyer and JCR Romo-Cruz. Solvable random-walk model with memory and its relations with markovian models of anomalous diffusion.Physical Review E, 90(4):042136, 2014
2014
-
[13]
Nonlinear ehrenfest’s urn model.Physical Review E, 91(4): 042139, 2015
GA Casas, FD Nobre, and EMF Curado. Nonlinear ehrenfest’s urn model.Physical Review E, 91(4): 042139, 2015
2015
-
[14]
Urn models for stochastic gene expression yield intuitive insights into the probability distributions of single-cell mrna and protein counts.Physical Biology, 17(6): 066001, 2020
Krishna Choudhary and Atul Narang. Urn models for stochastic gene expression yield intuitive insights into the probability distributions of single-cell mrna and protein counts.Physical Biology, 17(6): 066001, 2020
2020
-
[15]
Central limit theorem and related results for the elephant random walk.Journal of mathematical physics, 58(5), 2017
Cristian F Coletti, Renato Gava, and Gunter M Sch ¨utz. Central limit theorem and related results for the elephant random walk.Journal of mathematical physics, 58(5), 2017
2017
-
[16]
Exact solution of an anisotropic 2d random walk model with strong memory correlations.Journal of Physics A: Mathematical and Theo- retical, 46(50):505002, 2013
JC Cressoni, GM Viswanathan, and MAA3146031 Da Silva. Exact solution of an anisotropic 2d random walk model with strong memory correlations.Journal of Physics A: Mathematical and Theo- retical, 46(50):505002, 2013
2013
-
[17]
Non-gaussian propagator for elephant random walks.Physical Review E—Statistical, Non- linear, and Soft Matter Physics, 88(2):022115, 2013
M Antonio Alves da Silva, Jos ´e Carlos Cressoni, Gunter M Sch ¨utz, GM Viswanathan, and Steffen Trimper. Non-gaussian propagator for elephant random walks.Physical Review E—Statistical, Non- linear, and Soft Matter Physics, 88(2):022115, 2013
2013
-
[18]
Deborshi Das. Elephant random walks with graph based shared memory: First and second order asymptotics.arXiv preprint arXiv:2410.22969, 2024
-
[19]
Rates of convergence in the central limit theorem for the elephant random walk with random step sizes.Journal of Statistical Physics, 190(10):154, 2023
J ´erˆome Dedecker, Xiequan Fan, Haijuan Hu, and Florence Merlev `ede. Rates of convergence in the central limit theorem for the elephant random walk with random step sizes.Journal of Statistical Physics, 190(10):154, 2023
2023
-
[20]
Random walks and sustained competitive advantage.Management Science, 50(7): 922–934, 2004
Jerker Denrell. Random walks and sustained competitive advantage.Management Science, 50(7): 922–934, 2004
2004
-
[21]
M. Dhillon and K. K. Kataria. On elephant random walk with random memory, 2025. URLhttps: //arxiv.org/abs/2501.12866
-
[22]
Springer Science & Business Media, 2013
Marie Duflo.Random iterative models, volume 34. Springer Science & Business Media, 2013
2013
-
[23]
Stochastic approximations via large deviations: Asymptotic prop- erties.SIAM journal on control and optimization, 23(5):675–696, 1985
Paul Dupuis and Harold J Kushner. Stochastic approximations via large deviations: Asymptotic prop- erties.SIAM journal on control and optimization, 23(5):675–696, 1985
1985
-
[24]
Stochastic approximation and large deviations: Upper bounds and wp 1 convergence.SIAM Journal on Control and Optimization, 27(5):1108–1135, 1989
Paul Dupuis and Harold J Kushner. Stochastic approximation and large deviations: Upper bounds and wp 1 convergence.SIAM Journal on Control and Optimization, 27(5):1108–1135, 1989
1989
-
[25]
Cambridge university press, 2019
Rick Durrett.Probability: theory and examples, volume 49. Cambridge university press, 2019
2019
-
[26]
Cram ´er’s moderate deviations for martingales with applications
Xiequan Fan and Qi-Man Shao. Cram ´er’s moderate deviations for martingales with applications. In Annales de l’Institut Henri Poincare (B) Probabilites et statistiques, volume 60, pages 2046–2074. 39 Institut Henri Poincar´e, 2024
2046
-
[27]
Elephant random walk with multiple extractions.arXiv preprint arXiv:2507.06478, 2025
Simone Franchini. Elephant random walk with multiple extractions.arXiv preprint arXiv:2507.06478, 2025
-
[28]
Stochastic approximation with random step sizes and urn models with random replacement matrices having finite mean.The Annals of Applied Probability, 29 (4):2033–2066, 2019
Ujan Gangopadhyay and Krishanu Maulik. Stochastic approximation with random step sizes and urn models with random replacement matrices having finite mean.The Annals of Applied Probability, 29 (4):2033–2066, 2019
2033
-
[29]
Almost sure convergence of randomized urn models with application to elephant random walk.Statistics & Probability Letters, 191:109642, 2022
Ujan Gangopadhyay and Krishanu Maulik. Almost sure convergence of randomized urn models with application to elephant random walk.Statistics & Probability Letters, 191:109642, 2022
2022
-
[30]
Shyan Ghosh, Manisha Dhillon, and Kuldeep Kumar Kataria. On limiting behaviour of moves in multidimensional elephant random walk with stops.arXiv preprint arXiv:2601.07502, 2026
-
[31]
Variations of the elephant random walk.Journal of Applied Proba- bility, 58(3):805–829, 2021
Allan Gut and Ulrich Stadtm ¨uller. Variations of the elephant random walk.Journal of Applied Proba- bility, 58(3):805–829, 2021
2021
-
[32]
The elephant random walk with gradually increasing memory
Allan Gut and Ulrich Stadtm ¨uller. The elephant random walk with gradually increasing memory. Statistics & Probability Letters, 189:109598, 2022
2022
-
[33]
Academic press, 2014
Peter Hall and Christopher C Heyde.Martingale limit theory and its application. Academic press, 2014
2014
-
[34]
Memory-induced anomalous dynamics in a minimal random walk model.Physical Review E, 90(2):022136, 2014
Upendra Harbola, Niraj Kumar, and Katja Lindenberg. Memory-induced anomalous dynamics in a minimal random walk model.Physical Review E, 90(2):022136, 2014
2014
-
[35]
Random walkers with extreme value memory: modelling the peak-end rule.New Journal of Physics, 17(5):053049, 2015
Rosemary J Harris. Random walkers with extreme value memory: modelling the peak-end rule.New Journal of Physics, 17(5):053049, 2015
2015
-
[36]
Urn models and their applications in finance.Springer Books, 2025
Masato Hisakado. Urn models and their applications in finance.Springer Books, 2025
2025
-
[37]
Anomalous diffusion induced by enhancement of memory.Physical Review E, 90(1): 012103, 2014
Hyun-Joo Kim. Anomalous diffusion induced by enhancement of memory.Physical Review E, 90(1): 012103, 2014
2014
-
[38]
¨Uber die zusammenziehende und lipschitzsche transformationen.Fundamenta Mathematicae, 22(1):77–108, 1934
Mojzesz Kirszbraun. ¨Uber die zusammenziehende und lipschitzsche transformationen.Fundamenta Mathematicae, 22(1):77–108, 1934
1934
-
[39]
Niraj Kumar, Upendra Harbola, and Katja Lindenberg. Memory-induced anomalous dynamics: Emer- gence of diffusion, subdiffusion, and superdiffusion from a single random walk model.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 82(2):021101, 2010
2010
-
[40]
Random recursive trees and the elephant random walk.Physical Review E, 93(3): 032111, 2016
R ¨udiger K ¨ursten. Random recursive trees and the elephant random walk.Physical Review E, 93(3): 032111, 2016
2016
-
[41]
Stochastic approximation: a survey.Wiley Interdisciplinary Reviews: Computational Statistics, 2(1):87–96, 2010
Harold Kushner. Stochastic approximation: a survey.Wiley Interdisciplinary Reviews: Computational Statistics, 2(1):87–96, 2010
2010
-
[42]
Stochastic approximation.The annals of Statistics, 31(2):391–406, 2003
Tze Leung Lai. Stochastic approximation.The annals of Statistics, 31(2):391–406, 2003
2003
-
[43]
New insights on the reinforced elephant random walk using a martingale approach
Lucile Laulin. New insights on the reinforced elephant random walk using a martingale approach. Journal of Statistical Physics, 186:1–23, 2022
2022
-
[44]
Elephants explore in spirals sometimes.arXiv preprint arXiv:2511.16459, 2025
Lucile Laulin and Bastien Mallein. Elephants explore in spirals sometimes.arXiv preprint arXiv:2511.16459, 2025
-
[45]
Multidimensional elephant random walk with coupled memory.Physical Review E, 100(5):052131, 2019
Vitor M Marquioni. Multidimensional elephant random walk with coupled memory.Physical Review E, 100(5):052131, 2019
2019
-
[46]
Asymptotic properties of generalized ele- phant random walks.arXiv preprint arXiv:2406.19383, 2024
Krishanu Maulik, Parthanil Roy, and Tamojit Sadhukhan. Asymptotic properties of generalized ele- phant random walks.arXiv preprint arXiv:2406.19383, 2024
work page internal anchor Pith review arXiv 2024
-
[47]
Elephant random walks on infinite Cayley trees
Soumendu Sundar Mukherjee. Elephant random walks on infinite cayley trees.arXiv preprint arXiv:2509.03048, 2025
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[48]
¨Uber die lage der integralkurven gew ¨ohnlicher differentialgleichungen.Proceedings of the physico-mathematical society of Japan
Mitio Nagumo. ¨Uber die lage der integralkurven gew ¨ohnlicher differentialgleichungen.Proceedings of the physico-mathematical society of Japan. 3rd Series, 24:551–559, 1942
1942
-
[49]
Elephant random walk with polynomially decaying steps: Y
Yuzaburo Nakano. Elephant random walk with polynomially decaying steps: Y . nakano.Journal of Statistical Physics, 192(6):86, 2025. 40
2025
-
[50]
Yuzaburo Nakano and Masato Takei. Limit theorems for elephant random walks remembering the recent past, with applications to the takagi-van der waerden class functions.arXiv preprint arXiv:2505.08285, 2025
-
[51]
Elephant random walks with multiple extractions and general rein- forcement functions.Journal of Theoretical Probability, 39(1):17, 2026
Moumanti Podder and Archi Roy. Elephant random walks with multiple extractions and general rein- forcement functions.Journal of Theoretical Probability, 39(1):17, 2026
2026
-
[52]
A stochastic approximation method.The annals of mathematical statistics, pages 400–407, 1951
Herbert Robbins and Sutton Monro. A stochastic approximation method.The annals of mathematical statistics, pages 400–407, 1951
1951
-
[53]
The elephant random walk in the triangular array setting.Journal of Applied Probability, pages 1–13, 2024
Rahul Roy, Masato Takei, and Hideki Tanemura. The elephant random walk in the triangular array setting.Journal of Applied Probability, pages 1–13, 2024
2024
-
[54]
Phase transitions for a unidirectional elephant random walk with a power law memory.Electronic Communications in Probability, 29:1–12, 2024
Rahul Roy, Masato Takei, and Hideki Tanemura. Phase transitions for a unidirectional elephant random walk with a power law memory.Electronic Communications in Probability, 29:1–12, 2024
2024
-
[55]
Elephants can always remember: Exact long-range memory effects in a non-markovian random walk.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(4):045101, 2004
Gunter M Sch ¨utz and Steffen Trimper. Elephants can always remember: Exact long-range memory effects in a non-markovian random walk.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(4):045101, 2004
2004
-
[56]
Scaling behavior for random walks with memory of the largest distance from the origin.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 88(5):052141, 2013
Maurizio Serva. Scaling behavior for random walks with memory of the largest distance from the origin.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 88(5):052141, 2013
2013
-
[57]
Functional limit theorems for elephant random walks on general periodic structures
Shuhei Shibata. Functional limit theorems for elephant random walks on general periodic structures. arXiv preprint arXiv:2511.10347, 2025
-
[58]
Springer, 2003
Stephen Wiggins.Introduction to applied nonlinear dynamical systems and chaos. Springer, 2003
2003
-
[59]
Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs.Annals of Applied Probability, 26(6):3630–3658, 2016
Li-Xin Zhang. Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs.Annals of Applied Probability, 26(6):3630–3658, 2016
2016
-
[60]
arXiv preprint arXiv:2401.13884 , year=
Yixuan Zhang and Qiaomin Xie. Constant stepsize q-learning: Distributional convergence, bias and extrapolation.arXiv preprint arXiv:2401.13884, 2024
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.