Questions on random walk

0. Let S0, S1, S2, ... be a simple (nearest neighbour) symmetric random walk on the line, starting from 0. For any site x on the lattice and any n, let L(n,x) be the number of visits of the random walk at x up to step n, i.e.,

L(n,x) = #{ i < n+1: Si = x}.

A site x is called "favourite" (at step n) if L(n,x) is greater than or equal to L(n,y) for any other site y.

Erdös-Révész (1984) and Bass-Griffin (1985) initiated the study of favourite sites. Here are a few open questions borrowed from them.

1. It is easy to see that

P{there is only one favourite site at step n, i.o.} = 1,
P{there are two favourite sites at step n, i.o.} = 1.
(Notation: i.o. = infinitely often in n). Here is a question of Erdös and Révész.

Problem A. P{there are at least three favourite sites at step n, i.o.} = ?

It is conjectured that the probability would be 0.

2. The random walk being symmetric and recurrent, one would be tempted to think that (almost surely) the site 0 would be a favourite site infinitely often. The answer is no. Bass and Griffin proved that the favourite sites are transient. More quantitatively, let V(n) be a favourite site at step n, b a real number, and bn = n-1/2(log n)b, then a theorem of Bass and Griffin says that, almost surely,

liminf bn |V(n)|

equals 0 if b<1, and infinity if b>11 (eleven). Here, "liminf" relates to the situation when n goes to infinity.

Problem B. Find the critical value for b. That is, find a such that almost surely, the "liminf" expression equals 0 if b<a, and infinity if b>a.

(You may ask a further question when you solve this problem...)

3. It is intuitively clear that we do not often have several favourite sites. Erdös and Révész formulated the following question. Let n1, n2, ... be an increasing (random) sequence such that for each k, there are at least two favourite sites at step nk.

Problem C. Does nk/k go to infinity almost surely?

4. Let V(n) denote as before a favourite site at step n. Erdös-Révész and Bass-Griffin independently proved a law of the iterated logarithm (LIL) for V(n). It is exactly the same as the usual LIL for (the maximum of) the random walk. This is somewhat unsatisfactory in the sense that, intuitively, V(n) can be a lot smaller than the maximum (up to step n) of the random walk. To distinguish their respective asymptotic behaviours, the idea is to determine the upper functions (in the sense of P. Lévy) of the two processes. Those of the random walk are characterized by the classical Kolmogorov integral test (sometimes referred to as the Erdös-Feller-Kolmogorov-Petrowsky or EFKP test). What about the upper functions of V(n)?

Problem D. Characterize the upper functions of V(n), i.e., find an integral criterion to decide, for any positive non-decreasing sequence (an), whether P{V(n)>an, i.o.} is 0 or positive.

Erdös and Révész proved that the integral test for V(n) will differ from the Kolmogorov one. They succeeded in constructing a (complicated) example of sequence (an), such that P{V(n)>an, i.o.} = 0, whereas P{Sn>an, i.o.} = 1.

5. One would think that new favourite sites do not come frequently. Let A(n) denote the accumulated number of different favourite sites up to step n. A conjecture of Erdös and Révész is as follows.

Conjecture E. There exists a constant c>0 such that with probability one, A(n) < (log n)c for all large n.

6. A few other open problems on favourite sites can be found in pages 130-131 of the Révész (1990) book.

7. References

8. Comments/remarks/solutions welcome.


9. This page is jointly maintained with Zhan Shi

Last updated : April 7, 1999.