Urn-driven random walks

Hosam Mahmoud; Srinivasan Balaji

arxiv: 2504.14813 · v3 · submitted 2025-04-21 · 🧮 math.PR

Urn-driven random walks

Srinivasan Balaji , Hosam Mahmoud This is my paper

Pith reviewed 2026-05-22 19:12 UTC · model grok-4.3

classification 🧮 math.PR

keywords random walksPólya urnrecurrencetransienceexchangeabilityFriedman urnMarkov chainlattice

0 comments

The pith

Pólya-Eggenberger urns drive random walks recurrent only in one dimension.

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

This paper compares the classical symmetric random walk, recurrent in one and two dimensions, to walks whose step probabilities are instead generated by draws from an urn. For the Pólya-Eggenberger urn the resulting process is recurrent solely in one dimension; exchangeability of the color sequence then shows the recurrence is null. In two or higher dimensions the walk has a positive probability of never returning. By contrast, walks driven by a Friedman urn retain the symmetric pattern of recurrence in one and two dimensions and transience beyond, with simulations suggesting positive recurrence in one dimension. The distinction matters because the dependence created by different urn replacement rules shifts the dimensional threshold at which escape becomes possible.

Core claim

If the probabilities of the random walk are instead driven by a Pólya-Eggenberger urn, the states are recurrent only in one dimension. Further consideration of exchangeability reveals that the walk is null recurrent. As soon as the underlying Markov chain of Pólya walk gets in two dimensions or higher, there is a positive probability that the walker gets lost in the space, and the probability of her recurrence is less than 1. On the other hand, a walk driven by Friedman urn behaves like the symmetric random walk, being recurrent in one and two dimensions and transient in higher dimensions.

What carries the argument

The exchangeable sequence of colors produced by the Pólya-Eggenberger urn, which determines the transition probabilities of the induced Markov chain on the integer lattice.

If this is right

The Pólya walk is null recurrent in one dimension.
In two or higher dimensions the Pólya walk has recurrence probability strictly less than one.
Friedman walks are recurrent in one and two dimensions and transient in three and higher.
Simulations indicate that the one-dimensional Friedman walk is positive recurrent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The long-range dependence enforced by exchangeability in the Pólya case prevents recurrence in dimensions where fixed-probability walks still return almost surely.
Different urn replacement schemes could be used to construct lattice walks whose recurrence threshold lies between one and two dimensions.
Exact moments of the number of visits could be derived for the Friedman case to replace the simulation evidence for positive recurrence.

Load-bearing premise

The exchangeable sequence from the Pólya-Eggenberger urn produces a Markov chain on the lattice to which the standard recurrence criteria for symmetric walks apply directly.

What would settle it

A calculation or simulation establishing that the return probability to the origin equals one in two dimensions for the Pólya-driven walk would disprove the positive escape probability.

Figures

Figures reproduced from arXiv: 2504.14813 by Hosam Mahmoud, Srinivasan Balaji.

read the original abstract

The symmetric random walk is known to be recurrent in one and two dimensions, and becomes transient in three or higher dimensions. We compare the symmetric random walk to walks driven by certain \polya\ urns. We show that, in contrast, if the probabilities of the random walk are instead driven by a \polya-Eggenberger urn, the states are recurrent only in one dimension. Further consideration of exchangeability reveals that the walk is null recurrent. As soon as the underlying Markov chain of \polya\ walk gets in two dimensions or higher, there is a positive probability that the walker gets lost in the space, and the probability of her recurrence is less than 1. On the other hand, a walk driven by Friedman urn behaves like the symmetric random walk, being recurrent in one and two dimensions and transient in higher dimensions. As Friedman urn scheme is not exchangeable, it is considerably harder to determine the nature of the recurrence in one and two dimensions. Empirical evidence through simulation suggests that in one dimension Friedman walk is positive recurrent.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The Pólya-driven walk's claimed null recurrence in one dimension conflicts with the almost-sure non-zero drift implied by its exchangeability.

read the letter

The key takeaway is that this paper compares recurrence for random walks whose steps are driven by Pólya-Eggenberger or Friedman urns. It claims the Pólya version is recurrent only in one dimension and null recurrent there, while in two or higher dimensions the recurrence probability drops below one. The Friedman version is said to behave like the ordinary symmetric walk, recurrent in one and two dimensions, with simulations suggesting positive recurrence in one dimension. The comparison is straightforward and the use of exchangeability for the Pólya case is a reasonable starting point. The simulations add some concrete evidence for the Friedman model where closed-form analysis is tougher. The main concern is the null-recurrence conclusion in one dimension for the Pólya walk. Exchangeability means the step sequence is a mixture of i.i.d. sequences with a random bias from the Beta distribution. Almost surely the bias is not one half, so the position has a random non-zero drift and tends to infinity, returning to zero only finitely often. This suggests transience, not recurrence. The paper appears to lean on exchangeability for the null-recurrence claim, but the almost-sure path properties point the other way. The higher-dimension claims may hold up better on similar grounds. This sort of work appeals to researchers focused on urn models and reinforced random walks. Someone in that area might find the specific distinctions useful for further study. I think it deserves peer review so that the recurrence arguments can be examined in detail against the de Finetti representation and standard criteria for dependent increments.

Referee Report

2 major / 1 minor

Summary. The manuscript examines random walks whose step probabilities are governed by Pólya-Eggenberger and Friedman urn models. It asserts that Pólya-Eggenberger driven walks are recurrent solely in one dimension, with null recurrence there due to exchangeability, and have recurrence probability less than 1 in dimensions two and higher. In contrast, Friedman urn driven walks are claimed to mimic the symmetric random walk, being recurrent in one and two dimensions and transient in higher dimensions, with simulation evidence suggesting positive recurrence in one dimension.

Significance. If the central claims held, the work would contribute to the understanding of recurrence and transience in dependent stochastic processes, particularly illustrating how urn mechanisms can alter the recurrence properties compared to i.i.d. symmetric walks and the impact of exchangeability versus non-exchangeability.

major comments (2)

Abstract: The assertion that the Pólya-Eggenberger urn driven walk is recurrent in one dimension is incorrect. By de Finetti's theorem, the exchangeable sequence of steps is a mixture of i.i.d. sequences with random bias p distributed as Beta(1,1) (uniform on [0,1]). Since P(p = 1/2) = 0, the walk has a non-zero drift almost surely, implying that |S_n| tends to infinity almost surely and the origin is visited only finitely many times, contradicting the claimed recurrence and null recurrence.
Abstract: The application of standard recurrence criteria (such as those for symmetric walks) to conclude null recurrence in one dimension overlooks the strong dependence induced by the urn; marginal return probabilities do not determine almost-sure recurrence for dependent increments.

minor comments (1)

The manuscript would benefit from explicit definitions of the urn schemes and the precise Markov chain construction in the introduction or a preliminary section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The observations regarding the recurrence claims for the Pólya-Eggenberger urn-driven walk are substantive and have led us to re-evaluate the arguments in the abstract and main text. We respond to each major comment below.

read point-by-point responses

Referee: Abstract: The assertion that the Pólya-Eggenberger urn driven walk is recurrent in one dimension is incorrect. By de Finetti's theorem, the exchangeable sequence of steps is a mixture of i.i.d. sequences with random bias p distributed as Beta(1,1) (uniform on [0,1]). Since P(p = 1/2) = 0, the walk has a non-zero drift almost surely, implying that |S_n| tends to infinity almost surely and the origin is visited only finitely many times, contradicting the claimed recurrence and null recurrence.

Authors: We agree with this analysis. De Finetti's theorem indeed represents the exchangeable step sequence as a mixture of i.i.d. walks with random bias p uniform on [0,1]. For almost every such p the resulting walk has nonzero drift and is transient, so the mixture is transient and the origin is visited only finitely often almost surely. Our earlier claim of recurrence (and null recurrence) in one dimension did not fully incorporate this consequence of the mixture representation. We will revise the abstract and the relevant discussion to state that the Pólya-Eggenberger driven walk is transient in every dimension, with recurrence probability strictly less than one. revision: yes
Referee: Abstract: The application of standard recurrence criteria (such as those for symmetric walks) to conclude null recurrence in one dimension overlooks the strong dependence induced by the urn; marginal return probabilities do not determine almost-sure recurrence for dependent increments.

Authors: We accept the referee's point that the strong dependence created by the urn precludes direct application of recurrence criteria that assume independent or symmetric increments. Our exchangeability-based argument for null recurrence relied on the marginal uniformity of the steps, but this is insufficient to establish almost-sure recurrence under dependence. In the revised manuscript we will remove the null-recurrence claim for this model and replace it with the transience statement indicated in the response to the first comment. revision: yes

Circularity Check

0 steps flagged

No circularity; recurrence claims rest on external urn exchangeability and standard Markov criteria

full rationale

The derivation invokes the known exchangeability of the Pólya-Eggenberger sequence (an external property of the urn model) and applies standard recurrence/transience criteria for lattice walks. These inputs are independent of the paper's conclusions and do not reduce to self-defined quantities or fitted parameters renamed as predictions. No load-bearing self-citations or ansatzes smuggled via prior work by the same authors are required for the central steps. The chain is self-contained against external benchmarks from urn theory and Markov-chain analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on established properties of Pólya and Friedman urns together with classical Markov-chain recurrence theory; no new free parameters or invented entities are introduced.

axioms (2)

domain assumption Pólya-Eggenberger urn produces exchangeable sequences
Invoked to establish null recurrence in one dimension.
standard math Standard recurrence/transience criteria for Markov chains on lattices
Applied to conclude escape probability greater than zero in dimensions two and higher.

pith-pipeline@v0.9.0 · 5702 in / 1354 out tokens · 47262 ms · 2026-05-22T19:12:47.709290+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2.1. In the one-dimensional Pólya random walk state 0 is null recurrent. ... P(X_{2n}=0) = ⟨w⟩_n ⟨b⟩_n / ⟨w+b⟩_{2n} ⋅ (2n choose n)
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Corollary 3.1. The d-dimensional Pólya random walk, with d≥2, is transient.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

and Laulin, L

Bercu, B. and Laulin, L. (2019). On the multi-dimensional elephant random walk.Journal of Statistical Physics175, 1146–1163

work page 2019
[2]

Bertoin, X. (2022). Counting the zeros of an elephant random walk. https://arxiv.org/abs/2105.09569

work page arXiv 2022
[3]

and P´ olya, G

Eggenberger, F. and P´ olya, G. (1923). ¨Uber die statistik verketteter vorg¨ ange.Zeitschrift f¨ ur Angewandte Mathematik und Mechanik3, 279– 289

work page 1923
[4]

and Puyhaubert, V

Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solv- able models of urn process theory. InDiscrete Mathematics and Com- puter Science Proceedings, Ed. Philippe ChassaingAG, 59–118

work page 2006
[5]

and Pekari, H

Flajolet, P., Gabarr´ o, J. and Pekari, H. (2005). Analytic urns.The An- nals of Probability33, 1200–1233

work page 2005
[6]

and Keller, J

Giladi, E. and Keller, J. (1994). Eulerian number asymptotics.Proceed- ings: Mathematical and Physical Science445, 291–303

work page 1994
[7]

and Patashnik, O

Graham, R., Knuth, D. and Patashnik, O. (1994).Concrete Mathe- matics: A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts

work page 1994
[8]

and Kotz, S

Johnson, N. and Kotz, S. (1977).Urn Models and Their Application. John Wiley, New York

work page 1977
[9]

(2008).P´ olya Urn Models

Mahmoud, H. (2008).P´ olya Urn Models. Chapam-Hall, Boca Rotan, Florida. 14

work page 2008
[10]

(1921).¨Uber eine aufgabe der wahrscheinlichkeitstheorie betr- effend die irrfahrt im straßennetz.Mathematische Annalen84, 149–160

P´ olya, G. (1921).¨Uber eine aufgabe der wahrscheinlichkeitstheorie betr- effend die irrfahrt im straßennetz.Mathematische Annalen84, 149–160

work page 1921
[11]

and Trimper, S

Sch¨ utz, G. and Trimper, S. (2004). Elephant random walk.Physical ReviewE, 70, 045101(R)

work page 2004
[12]

Shuo, Q. (2025). Recurrence and transience of multidimensional ele- phant random walks.Annals of Probability53, 1049–1078

work page 2025
[13]

(2015).Catalan Numbers

Stanley, R. (2015).Catalan Numbers. Cambridge University Press, Cam- bridge, UK. 15

work page 2015

[1] [1]

and Laulin, L

Bercu, B. and Laulin, L. (2019). On the multi-dimensional elephant random walk.Journal of Statistical Physics175, 1146–1163

work page 2019

[2] [2]

Bertoin, X. (2022). Counting the zeros of an elephant random walk. https://arxiv.org/abs/2105.09569

work page arXiv 2022

[3] [3]

and P´ olya, G

Eggenberger, F. and P´ olya, G. (1923). ¨Uber die statistik verketteter vorg¨ ange.Zeitschrift f¨ ur Angewandte Mathematik und Mechanik3, 279– 289

work page 1923

[4] [4]

and Puyhaubert, V

Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solv- able models of urn process theory. InDiscrete Mathematics and Com- puter Science Proceedings, Ed. Philippe ChassaingAG, 59–118

work page 2006

[5] [5]

and Pekari, H

Flajolet, P., Gabarr´ o, J. and Pekari, H. (2005). Analytic urns.The An- nals of Probability33, 1200–1233

work page 2005

[6] [6]

and Keller, J

Giladi, E. and Keller, J. (1994). Eulerian number asymptotics.Proceed- ings: Mathematical and Physical Science445, 291–303

work page 1994

[7] [7]

and Patashnik, O

Graham, R., Knuth, D. and Patashnik, O. (1994).Concrete Mathe- matics: A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts

work page 1994

[8] [8]

and Kotz, S

Johnson, N. and Kotz, S. (1977).Urn Models and Their Application. John Wiley, New York

work page 1977

[9] [9]

(2008).P´ olya Urn Models

Mahmoud, H. (2008).P´ olya Urn Models. Chapam-Hall, Boca Rotan, Florida. 14

work page 2008

[10] [10]

(1921).¨Uber eine aufgabe der wahrscheinlichkeitstheorie betr- effend die irrfahrt im straßennetz.Mathematische Annalen84, 149–160

P´ olya, G. (1921).¨Uber eine aufgabe der wahrscheinlichkeitstheorie betr- effend die irrfahrt im straßennetz.Mathematische Annalen84, 149–160

work page 1921

[11] [11]

and Trimper, S

Sch¨ utz, G. and Trimper, S. (2004). Elephant random walk.Physical ReviewE, 70, 045101(R)

work page 2004

[12] [12]

Shuo, Q. (2025). Recurrence and transience of multidimensional ele- phant random walks.Annals of Probability53, 1049–1078

work page 2025

[13] [13]

(2015).Catalan Numbers

Stanley, R. (2015).Catalan Numbers. Cambridge University Press, Cam- bridge, UK. 15

work page 2015