Status
On this page
Status
Topics
Status
On this page
Status
Topics
Given a random walk in , starting at the origin, let count the number of such that .
Let
be the set of 'favourite values'. Find
for .
Given a simple random walk in , starting at the origin, let count the number of such that .
Let
be the set of 'favourite values'. Find
for .
Source: erdosproblems.com/1165
An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.
Solved, on the site's label, which credits the value for to Tóth [To01] and the value for to Hao, Li, Okada and Zheng [HLOZ24]: the probability is for and for every integer . Hao–Li–Okada–Zheng, Theorem 1.1 proves almost surely , which gives both values; it is recorded as an accepted claim. Tóth's paper concerns the walk on , as the assessment below explains, and has no claim page.
The site's wording does not say which random walk is meant, and the answer depends on the law: for the walk whose steps are and with probability each, no site is visited twice, so equals only at and the probability is for every , while for the simple random walk it is at . The poser's own text leaves the law open as well: the setup of Section 6.1 of [Va99], printed p. 11, which precedes Erdős and Révész's item 6.77 on printed p. 12, says only "a random walk on ", so the ambiguity is already in the poser's text and the site's wording copies it. The change inserts "simple" before "random walk", the walk whose independent increments are uniform on ; nothing else changes, and the time-zero visit is counted as the site counts it. The evidence is the literature's statement of the question as Erdős and Révész's. Hao, Li, Okada and Zheng [HLOZ24], Section 1, display (1.2), state it for discrete-time simple random walk on for every , apart from their theorem's range . Tóth [To01], Section 1, printed pp. 484–485, independently states Erdős and Révész's favorite-site question for simple symmetric random walk on . The site credits both papers, each about simple random walk, with the answer. The correction does not rest on the texts in which Erdős and Révész raised the question (1984, 1987 and 1991, cited by both papers). No result about any other law is recorded. The standing judges this precise Statement.