On Elephant Random Walk with Random Memory

K. K. Kataria; M. Dhillon

REVIEW 2 major objections 4 minor 1 cited by

On Elephant Random Walk with Random Memory

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Random-memory elephant walk has exact finite-time mean formulas.

desk verdict New ERW variant with plausible explicit mean formulas, but the Section 2 conditional derivation is invalid as written; the recursions are repairable and the paper deserves a referee, not a desk reject. read the letter →

arxiv 2501.12866 v1 pith:WUMI6IFL submitted 2025-01-22 math.PR

M. Dhillon , K. K. Kataria This is my paper · ORCID

classification math.PR MSC 60K5060G50

keywords elephantrandomwalkmemorytime-changedconditionalmeandisplacementcombinatorialrecursioneffectsfinite-time

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a variant of the elephant random walk in which, before each step, the walker rolls an n-faced die and is allowed to remember only the steps up to the rolled number, then repeats or reverses a uniformly chosen remembered step. The authors establish recursive equations for the mean increment and mean position of this walk, and then solve those recursions in closed form as finite sums over explicitly described combinatorial sets. The result matters because it gives exact finite-time control of a non-Markovian walk with random memory, where the usual full-history Markovian tools do not apply, and it provides a concrete starting point for asymptotic analysis of memory effects.

What carries the argument

The central object is the random memory set $M_n=\{1,2,\dots,Y(n)\}$, with $Y(n)$ uniform on $\{1,\dots,n\}$ and the selected past index $K$ uniform on $M_n$, so the one-step transition is a composition of two uniform draws. The argument's workhorse is the conditional mean identity $\mathbb{E}(X_{n+1}|\mathcal{F}_n)=\frac{\alpha}{n}\sum_{r=1}^n \frac{1}{r}\sum_{k=1}^r X_k$, from which the law of iterated expectations yields the recursions for the means. The recursions are then unrolled into explicit sums indexed by the sets $\Phi_n^j$ and $\Theta_n^j$, whose elements are exponent vectors $(x_2,\dots,x_n)$ with $x_i\in\{0,1,2\}$, tracking how a given past step contributes through chains of remembered steps.

What would settle it

For $n=3$, compute $\mathbb{E}(X_4)$ by direct enumeration over all eight initial step sequences and all triples $(Y(1),Y(2),Y(3))$ under the memory rule, and check the result against the right-hand side of (3.1) with the sets $\Phi_3^1$, $\Phi_3^2$, and $\Phi_3^3$; any disagreement at a fixed $p\in[0,1]$ would falsify the explicit mean formula.

Watch

Extended reading notes

Core claim

The paper claims that for the elephant random walk with random memory, where the next step is $X_{n+1}=\alpha_n X_{K_n}$ with $K_n\sim \mathrm{unif}\{1,\dots,Y(n)\}$ and $Y(n)\sim\mathrm{unif}\{1,\dots,n\}$, the mean increments satisfy the recursion $\mathbb{E}(X_{n+1})=\frac{\alpha}{n}\sum_{r=1}^n \frac{1}{r}\sum_{k=1}^r \mathbb{E}(X_k)$ and the mean displacement satisfies $\mathbb{E}(S_{n+1})=\mathbb{E}(S_n)+\frac{\alpha}{n}\sum_{r=1}^n \frac{\mathbb{E}(S_r)}{r}$, where $\alpha=2p-1$. Solving these recursions gives explicit closed forms: $\mathbb{E}(X_{n+1})=\sum_{j=1}^n \alpha^j \sum_{(x_2,\dots,x_n)\in\Phi_n^j} \frac{1}{2^{x_2}3^{x_3}\cdots n^{x_n}}$ and $\mathbb{E}(S_{n+1})=\sum_{j=0}^n \alpha^j \sum_{(x_2,\dots,x_n)\in\Theta_n^j} \frac{1}{2^{x_2}3^{x_3}\cdots n^{x_n}}$, with the index sets defined by a recursive combinatorial construction.

Load-bearing premise

The derivation assumes that conditioning on the random collection of remembered steps does not reveal the random number of remembered steps, so that $Y(n)$ can still be averaged over; if $Y(n)$ is in fact measurable with respect to that conditioning, the stated conditional laws in (2.8) and Remark 2.1 need to be revised.

Editorial extensions

If this is right

For every time horizon $n$, both the mean increment and the mean displacement are polynomials of degree $n$ in $\alpha=2p-1$, with coefficients given by the combinatorial sums over $\Phi_n^j$ and $\Theta_n^j$.
If the first step has bias $q$, both explicit formulas are multiplied by $\beta=2q-1$, giving a clean separation of the initial bias from the memory parameter.
The cardinalities $|\Phi_n^j|$ and $|\Theta_n^j|$ are polynomials in $n$ of orders $2j-1$ and $2j$ respectively, so the number of terms contributing to each power of $\alpha$ is known exactly.
The paper also derives a second-moment recursion, yielding an expression for $\mathbb{E}(S_{n+1}^2)$ in terms of pairwise correlations $\mathbb{E}(X_kX_q)$, which gives a route toward variance computations.
These exact finite-time formulas can serve as baselines for simulation studies of memory-restricted elephant walks and for asymptotic comparisons with the full-memory elephant random walk.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the explicit mean formulas are unconditional, they are likely to survive a corrected conditioning step: the fragile part of the paper is the stated conditional law, not the recursions that produce the closed forms.
The same exponent-vector expansion may extend to higher moments; the structure of the second-moment recursion suggests that $\mathbb{E}(X_mX_n)$ is a polynomial in $\alpha$ with similar combinatorial coefficients.
A natural next question is whether the random-memory walk exhibits a diffusive-to-superdiffusive transition analogous to the standard elephant random walk; the polynomial-in-$\alpha$ structure invites an asymptotic analysis of the growth of these polynomials.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper gives a new elephant random walk variant—random memory via two independent uniform draws—and derives explicit finite-time formulas for the mean increments and mean displacement. That much is real. The model is a natural time-changed ERW, and the combinatorial sums in Section 3 are non-trivial and check out for small n. The cardinality remarks are also a nice touch. I believe the final formulas are likely correct.

The problem is the route. Section 2 defines F_n = sigma{X_k : k in M_n} with M_n = {1,...,Y(n)}. On any standard formalization, Y(n) is F_n-measurable, so you cannot average over its distribution in (2.2). The concrete n=2 counterexample from the stress-test note is decisive: take X1=1, X2=-1, Y(2)=2. On that atom, the right-hand side of (2.8) equals alpha/2, while the direct conditional expectation E(X3|F_n) is 0. So (2.8) is not a version of the conditional mean, and Remark 2.1 is unsupported. The unconditional recursions (2.9)-(2.10) are true, but they require conditioning on G_n = sigma(X_1,...,X_n), which is not what the paper does. That is a genuine proof gap, and it is load-bearing because the explicit formulas in Section 3 are derived from these recursions.

A second soft spot: the explicit formulas are introduced as 'proceeding inductively' without a complete induction. Given how intricate the sets Phi and Theta are, a referee would have to fill in substantial detail. This is a fixable issue but not a trivial one.

The impact is narrow: no asymptotics, no scaling regimes, no applications beyond exact moment computations. For the ERW community, this is a modest but legitimate extension. It is not a major advance, but it is not junk.

For peer review: I would send it out. The error in Section 2 is concrete but repairable, and the final formulas appear to be worth having. I'd require a corrected conditional derivation and a fuller proof of the explicit sums. If an editor desk-rejects on impact grounds, that's defensible, but the paper deserves referee time first.

Referee Report

2 major / 4 minor

Summary. The paper introduces a variant of the elephant random walk in which, at each time n, the walker's memory consists of the random set M_n = {1,...,Y(n)}, where Y(n) is uniform on {1,...,n}, and the next increment is obtained by choosing K uniformly from M_n and setting X_{n+1} = +X_K with probability p and -X_K with probability 1-p. The authors derive conditional probabilities and conditional means for the increments, then use them to obtain recursions and explicit combinatorial formulas for the mean increments E(X_{n+1}) and the mean displacement E(S_{n+1}). The main explicit results are equations (3.1) and (3.3), which express the means as polynomials in alpha = 2p-1 with coefficients given by sums over the sets Phi_n^j and Theta_n^j.

Significance. The model is a natural time-changed variant of the elephant random walk, and the explicit mean formulas, if rigorously established, would be a useful and nontrivial contribution to the exact analysis of this class of processes. The recursions (2.9) and (2.10) are in fact correct and can be proved by conditioning on the full history G_n, and the small-n expansions in Section 3 are consistent with those recursions. The paper proposes a clean combinatorial parametrization of the mean coefficients, with explicit cardinalities in Remarks 3.1 and 3.5. However, the conditioning framework in Section 2 is mathematically incorrect as written, and the inductive step from the small-n expansions to the general formulas in Section 3 is not supplied. The central claims are therefore not currently proven, although they appear repairable.

major comments (2)

[Section 2] The conditioning argument is not valid. The sigma-algebra F_n = sigma{X_k : k in M_n} with random M_n = {1,...,Y(n)} is never rigorously defined. If Y(n) is F_n-measurable, then in (2.2) one may not average over P{Y(n)=r}; the event {Y(n)=r} is already known, so P{Y(n)=r} should be replaced by 1_{Y(n)=r}. In that reading, (2.8) is not a version of E(X_{n+1}|F_n). Concretely, for n=2 on the atom {X1=1, X2=-1, Y(2)=2}, the right-hand side of (2.8) equals alpha(1 + (1-1)/2)/2 = alpha/2, whereas the direct conditional expectation is E(X3|F_2) = alpha(X1+X2)/2 = 0. If instead F_n is read as the stopped sigma-algebra without Y(n), then the right-hand side of (2.8) is actually E(X_{n+1}|G_n) with G_n = sigma(X_1,...,X_n), not E(X_{n+1}|F_n), and Remark 2.1 is false. The same flaw affects the conditional identity leading to (2.18). The unconditional recursions (2.9) and (2.10) are nevertheless correct and can be obtained directly by conditioning on G_n; the proof route in the manuscript must be rewritten accordingly.
[Section 3] The transition from the small-n expansions to the general explicit formulas is not proved. The sentence 'Proceeding inductively' replaces an induction that must show that the right-hand sides of (3.1) and (3.3), with the recursively defined sets Phi_n^j and Theta_n^j, satisfy the recursions (2.9) and (2.10) together with the stated initial conditions. This is not automatic from the set definitions as written: the j=2 case and the families B_{n-k}^{j-1} in Section 3.1 and Lambda_{n-k}^{j-1} in Section 3.2 are not accompanied by a proof that the construction is exhaustive, disjoint, and correctly encodes the recursion. Without such an induction, (3.1) and (3.3) are verified only for n <= 4, which does not establish the claimed general formulas.

minor comments (4)

[Section 2] The notation for the random index is inconsistent: the walk is written as X_{n+1} = alpha_n X_{beta(Y(n))}, but later beta(n) is used as if it were uniform on {1,...,n}; the distinction between beta(n) and beta(Y(n)) should be made explicit.
[Section 3.1] The displayed list of Phi_3^2 contains the malformed tuple '(1,2, )'; it should read '(1,2)'.
[Remark 3.2] Condition C1 in (3.2) uses the symbol k both for the total exponent sum and for half the number of ones after an entry equal to 2; this makes the condition difficult to parse and should be re-notated.
[Remark 3.5] The cardinalities in Remark 3.5 are written with lowercase theta (|theta_n^j|), while the sets in the main text are denoted by uppercase Theta_n^j; the notation should be unified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the mean formulas are combinatorial rearrangements of derived recursions, not fitted inputs or self-citations.

full rationale

The derivation chain is self-contained and does not reduce to its own inputs. The parameter alpha = 2p - 1 is fixed by the definition of the walk, not fitted to any target quantity. Equations (2.9) and (2.10) are unconditional recursions obtained from the conditional mean (2.8) by iterated expectation, and the explicit expressions (3.1) and (3.3) are algebraic reorganizations of those recursions, with the sets Phi and Theta defined explicitly, albeit recursively, to enumerate the multinomial terms. There are no load-bearing self-citations, no imported uniqueness theorem, and no known result merely renamed in new coordinates. The possible technical issue concerning the conditioning on F_n = sigma{X_k : k in M_n} would affect the validity of the stated proof route, but that is a mathematical correctness concern rather than circularity: the unconditional recursions can be checked directly for small n and do not presuppose the explicit formulas. Accordingly, no circular step is present and the score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The model has two fixed parameters p and q, but no fitted or ad hoc constants. The central claim depends on standard probability axioms and the specific independence structure of the model.

assumptions (4)

domain assumption The random variables Y(n), beta(n), and alpha_n are mutually independent and independent of the walk's past steps.
Assumed in Section 2 before equation (2.2); needed for all conditional and recursive calculations.
domain assumption Y(n) is uniform on {1,...,n} and beta(n) is uniform on {1,...,Y(n)}.
Defines the random memory model in Section 2; this is the process definition, not an empirical input.
standard math Standard conditional expectation and tower-law properties hold for the random sigma-algebra F_n.
Used throughout Section 2; the paper's mis-specified conditioning suggests this application needs care.
domain assumption The walk starts at the origin and X1 is Rademacher(q); p and q are fixed parameters in [0,1].
Model initialization in Section 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Elephant Random Walk with Random Memory." pith.science (2026). https://pith.science/paper/WUMI6IFL

@misc{pith2026250112866,
  author       = {Pith},
  title        = {Pith review of: On Elephant Random Walk with Random Memory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WUMI6IFL}},
  note         = {Machine review of arXiv:2501.12866}
}

read the original abstract

In this paper, we introduce the elephant random walk (ERW) with memory consisting of randomly selected steps from its history. It is a time-changed variant of the standard elephant random walk with memory consisting of its full history. At each time point, the time changing component is the composition of two uniformly distributed independent random variables with support over all the past steps. Several conditional distributional properties including the conditional mean increments and conditional displacement of ERW with random memory are obtained. Using these conditional results, we derive the recursive and explicit expressions for the mean increments and mean displacement of the walk.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Elephant Random Walk with multiple extractions
math.PR 2025-07 conditional novelty 3.0 of 10

The k-extraction Elephant Random Walk is shown to be a Hill-Lane-Sudderth urn, with a phase transition at p=5/6 for k=3, giving initial-condition-dependent limits and a sub-linear entropy region.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages · cited by 1 Pith paper

[1]

and Bertoin, J

Baur, E. and Bertoin, J. (2016). Elephant random walks and the ir connection to P´ olya-type urns. Phys. Rev. E 94, 052134

work page 2016
[2]

Bercu, B. (2018). A martingale approach for the elephant rand om walk. J. Phys. A 51(1), 015201, 16

work page 2018
[3]

Bertoin, J. (2022). Counting the zeros of an elephant random w alk. Trans. Amer. Math. Soc. 375(8), 5539-5560. 10

work page 2022
[4]

R., dos Santos, R

Blondel, O., Hil´ ario, M. R., dos Santos, R. S., Sidoravicius, V. and Te ixeira, A. (2020). Random walk on random walks: low densities. Ann. Appl. Probab. 30(4), 1614–1641

work page 2020
[5]

F., Gava, R

Coletti, C. F., Gava, R. and Sch¨ utz, G. M. (2017a). Central limit theorem and related results for the elephant random walk. J. Math. Phys. 58(5), 053303, 8

work page 2017
[6]

F., Gava, R

Coletti, C. F., Gava, R. and Sch¨ utz, G. M. (2017b). A strong inv ariance principle for the elephant random walk. J. Stat. Mech. Theory Exp. (12), 123207, 8

work page 2017
[7]

and Merlev` ede, F

Dedecker, J., Fan, X., Hu, H. and Merlev` ede, F. (2023). Elepha nts can always remember: Rates of convergence in the central limit theorem for the elephant random w alk with random step sizes. J. Stat. Phys. 190(10), 154, 30

work page 2023
[8]

and Shao, Q.-M

Fan, X. and Shao, Q.-M. (2024). Cram´ er’s moderate deviations for martingales with applications. Ann. Inst. Henri Poincar´ e Probab. Stat. 60(3), 2046-2074

work page 2024

Show all 15 references

[9]

and Jasiak, J

Gourieroux, C. and Jasiak, J. (2022). Long run predictions. Ann. Econ. Stat. (145), 75–90

2022
[10]

Gut, A, and Stadtm¨ uller, U. (2021). The number of zeros in ele phant random walks with delays. Statist. Probab. Lett. 174, 109112, 9

2021
[11]

and Stadtm¨ uller, U

Gut, A. and Stadtm¨ uller, U. (2021). Variations of the elephan t random walk. J. Appl. Probab. 58(3), 805-829

2021
[12]

and Stadtm¨ uller, U

Gut, A. and Stadtm¨ uller, U. (2022). Elephant random walks wit h delays. Rev. Roumaine Math. Pures Appl. 67(1-2), 51-66

2022
[13]

Roy R., Takei M., Tanemura H. (2025). The elephant random walk in the triangular array setting. J. Appl. Probab. doi: https://doi.org/10.1017/jpr.2024.106, 1-13

2025 doi
[14]

Sch¨ utz, M. G. and Trimper, S. (2004). Elephants can always r emember: Exact long-range memory eﬀects in a non-Markovian random walk. Phys. Rev. E. 70, 045101

2004
[15]

Velleman, D. J. (2014). A drug-induced random walk. Amer. Math. Monthly 121(4), 299-317. Manisha Dhillon, Department of Mathematics, Indian Instit ute of Technology Bhilai, Durg 491002, India. Email address : manishadh@iitbhilai.ac.in Kuldeep Kumar Kataria, Department of Mathe...

2014

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

and Bertoin, J

Baur, E. and Bertoin, J. (2016). Elephant random walks and the ir connection to P´ olya-type urns. Phys. Rev. E 94, 052134

work page 2016

[2] [2]

Bercu, B. (2018). A martingale approach for the elephant rand om walk. J. Phys. A 51(1), 015201, 16

work page 2018

[3] [3]

Bertoin, J. (2022). Counting the zeros of an elephant random w alk. Trans. Amer. Math. Soc. 375(8), 5539-5560. 10

work page 2022

[4] [4]

R., dos Santos, R

Blondel, O., Hil´ ario, M. R., dos Santos, R. S., Sidoravicius, V. and Te ixeira, A. (2020). Random walk on random walks: low densities. Ann. Appl. Probab. 30(4), 1614–1641

work page 2020

[5] [5]

F., Gava, R

Coletti, C. F., Gava, R. and Sch¨ utz, G. M. (2017a). Central limit theorem and related results for the elephant random walk. J. Math. Phys. 58(5), 053303, 8

work page 2017

[6] [6]

F., Gava, R

Coletti, C. F., Gava, R. and Sch¨ utz, G. M. (2017b). A strong inv ariance principle for the elephant random walk. J. Stat. Mech. Theory Exp. (12), 123207, 8

work page 2017

[7] [7]

and Merlev` ede, F

Dedecker, J., Fan, X., Hu, H. and Merlev` ede, F. (2023). Elepha nts can always remember: Rates of convergence in the central limit theorem for the elephant random w alk with random step sizes. J. Stat. Phys. 190(10), 154, 30

work page 2023

[8] [8]

and Shao, Q.-M

Fan, X. and Shao, Q.-M. (2024). Cram´ er’s moderate deviations for martingales with applications. Ann. Inst. Henri Poincar´ e Probab. Stat. 60(3), 2046-2074

work page 2024