Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be the maximal integer such that almost every random walk from the origin in visits every with in at most steps.
Is it true that
Let be the maximal integer such that the random walk from the origin in visits every with in at most steps.
Is it true that, in probability,
Source: erdosproblems.com/1164
An accepted solution exists. The statement is true.
PROVED, the site's label (page last edited 25 January 2026), which describes the corrected Statement: the commentary credits the order as proved independently by Révész [Re90] and Kesten, and the stronger limit law to Dembo, Peres, Rosen and Zeitouni [DPRZ04]. Both results are accepted full claims, Révész's two-sided bound and the limit law with rate 4, and the derived standing is solved, proved. Kesten's independent proof has no publication of his own, the 2004 paper citing it as quoted by Aldous and by Lawler, so it has no claim page and is disclosed on Révész's. An independent Lean proof of the order in probability, in Boris Alexeev's repository, is a pending full claim.
The site's is one number for each : the largest radius whose disc almost every walk covers by time . The change replaces "almost every random walk" by "the random walk", so that is the radius covered by each path, and inserts "in probability": for every there are constants with for all large . The evidence is the poser's own statement of the question, Some of Paul's favorite problems (1999), Problem 6.76 (Erdős, Taylor), printed p. 12, on the source page: it lets count the visits of the walk to up to time (printed p. 11) and takes to be the largest integer with for each , a quantity of the path with no "almost every". The same item conjectures that " is about " and calls Kesten's limit law the "stronger conjecture"; the site's commentary also calls that law the stronger conjecture. A limit law with that continuous limit implies the two-sided comparison in probability, so the comparison in probability is the reading of that the law strengthens. Dembo, Peres and Rosen (2007), equation (1.1), reprint p. 1, define in the same pathwise way. The defect is the site's: the 1999 statement has no "almost every".