Doctoral School in Mathematics and Computer Science

Department of Stochastics/Institute of Mathematics

PhD supervisor: Bálint Tóth

Joint work with Illés Horváth

Self-repelling random walks

Introducing the research area

This is a joint work with Illés Horváth (PhD student, Dept. Stochastics) and Bálint Tóth (professor, Dept. Stochastics). We consider a natural model of self-repelling random motion called the "true" (or myopic) self-avoiding walk. It means that a particle performs random jumps in the d-dimensional integer lattice with special rules. Jumps are only allowed along the edges, and the transition probabilities are given in such a way that the particle is pushed locally towards areas which were less frequently visited in the past. The aim of our research is to describe the behaviour of the particle after long time in terms of limit theorems.

Brief introduction of the research place

The Department of Stochastics is a recognized research group in the area of probability theory with 4 professors. The department staff cover a wide spectrum of research areas, such as random walks, stochastic processes, limit theorems (Bálint Tóth, prof.), dynamical systems (Domokos Szász, prof.), interacting particle systems (Márton Balázs, assoc. prof.), random fractals (Károly Simon, prof.), information theory (Imre Csiszár, prof. em.) and stochastic analysis (Tamás Szabados, assoc. prof.). The Department provides an inspiring environment for the 8 active PhD students and for other young people joining the research works.

History and context of the research

The "true" self-avoiding random walk model was first introduced in the physics literature by Amit, Parisi and Peliti in 1983 [APP83]. They have already set up a conjecture about the dimension dependent behaviour of the true self-avoiding walk, which is described below.

The simple symmetric random walk in the d-dimensional integer lattice (which chooses each of the neighbours with equal probability) is transient in three- or higher dimensions, i.e. returns to the starting point only finitely many times as opposed to the one- and two-dimensional cases where infinitely many returns occur. The true self-avoiding random walk (where the self-repelling mechanism is defined in terms of the number of earlier visits to the given position) follows the same long-time behaviour as the simple symmetric random walk in transient regime (that is, in three or higher dimensions), because in these cases, the self-repelling effect vanishes on the larger time scale. In this case, the typical distance of the particle from the starting point after t steps is around the square root of t, if t is large. The position divided by the square root of t converges to a random vector with normal (Gaussian) distribution. Moreover, scaling the path of the random walk the same way, the random trajectory obtained converges to Brownian motion. In one- and two-dimensional cases, the self-repellence results in higher order of the typical distance from the starting point and an intricate, non-standard limiting distribution appears in one dimension, see [T95], [TV08], [TV09] and [V09].

Aim of the research

The aim of the research of the true self-avoiding walk is to verify mathematically the above conjectures. In the present project, we worked on the three- and higher dimensional cases jointly with Illés Horváth and Bálint Tóth and gave a rigorous proof. The goal here was to show that the limiting behaviour of the true self-avoiding walk was the same as that of the simple symmetric random walk. More precisely, after scaling the position of the particle with the square root of time, approximately normal (Gaussian) distribution is obtained, which is the central limit theorem for the true self-avoiding walk. In addition, so-called diffusive upper and lower bounds have had to be proved on the variance of the position, which yield that the normal distribution in the limit is non-degenerate. These goals have already been achieved and the results have been submitted for publication [HTV10].

While working on the proof, we also examined a similar model called the "self-repelling Brownian polymer," that was introduced by Durrett and Rogers in 1992 [DR92]. This model can be regarded as the continuous space counterpart of the true self-avoiding random walk, where a particle performs a diffusional process in d dimensions governing by a mechanism that pushes the particle towards less visited areas. Diffusive bounds and central limit theorem have been proved for this model in three- and higher dimensions and the results have been submitted for publication [HTV10].

We also found a new sufficient condition for the central limit theorem to hold, which generalizes the existing theory. It turned out that our new theorem is not needed to prove the central limit theorem neither for the high-dimensional true self-avoiding walk nor for the high-dimensional self-repelling Brownian polymer model. Our new target is to investigate possible applications of our new methods for random walk models where earlier results were not applicable.

Methods

In the proof of the central limit theorem for the true self-avoiding walk in three or more dimensions, the following ingredients are used. The main difficulty is caused by the long memory of the true self-avoiding walk, since the whole history of the walk influences the distribution of the next step. A natural observation that considering the motion from the point of view of the moving particle, the problem transforms to finding Gaussian behaviour (i.e. approximately normal distribution) for a certain additive functional of a Markov chain, which problem has an extensive coverage in the literature.

The first result on central limit theorem for additive functionals of Markov chains dates back to 1986 by Kipnis and Varadhan [KV86]. The main tool in their proof and later generalizations is the approximation via a martingale having stationary increments. Martingales are well-understood objects in probability theory, and the proof for central limit theorem for martingales with stationary increments is known long ago. The theorem of Kipnis and Varadhan is only applicable if the Markov chain under discussion is reversible, which is not the case here. Extensions of this theory for the non-reversible case were published in [T86], [V96] and [SVY00]. In the latter, a remarkable sufficient condition is given for the central limit theorem to hold, the so-called graded sector condition.

Checking the graded sector condition for the true self-avoiding walk in three or more dimensions requires advanced functional analytic tools. The theory of Gaussian Hilbert spaces provides the framework for the computations. The proof relies on deep understanding of the resolvent calculus of the operator which appears here as infinitesimal generator. The computations are performed in the space of Fourier transforms where the operators can be handled.

The proof of the diffusive upper bound follows from the Brascamp-Lieb inequality. The natural symmetries (most notably the so-called Yaglom reversibility) of the model are used several times, e.g. a modified time-reversed version of the process has the same distribution as the original one, which has useful consequences in the proofs.

For the self-repelling Brownian polymer, the above methods can also be applied, one notable difference being that the proof of the diffusive upper bound is technically less difficult. In this case, considerations based on symmetries are sufficient.

Results

As mentioned above, we proved the conjecture of Amit, Parisi and Peliti in three or more dimensions; we gave a mathematically rigorous proof of the central limit theorem for the true self-avoiding walk in this regime using the methods described in the previous section. Diffusive bounds are also proved on the variance of the position of the moving particle, that is, after dividing by the square root of time, a non-trivial probability distribution is obtained which converges to a normal distribution with positive and finite variance.

In the course of our examinations, we also managed to prove diffusive bounds and central limit theorem for the self-repelling Brownian polymer proposed by Durrett and Rogers in three or more dimensions.

We have also found a new natural sufficient condition of the central limit theorem for general additive functionals of Markov chains, which is more general than the graded sector condition. However, it was not needed for the proof of the central limit theorem for the true self-avoiding walk and the self-repelling Brownian polymer, because the graded sector condition is also applicable for higher dimensions. This more general condition (referred to as the "relaxed sector condition") is not published as yet. The next task is to find an appropriate model in which the relaxed sector condition can be naturally applied. This project leads us beyond the true self-avoiding walk model.

Expected impact and further research

The central limit theorem for the high dimensional true self-avoiding walk undoubtedly means a breakthrough in this area, because after a number of serious but unsuccessful attempts a more than 25-year old conjecture could finally be verified rigorously.

The first central limit theorem for additive functionals of Markov chains [KV86] was an important and celebrated result in the probabilist community. Any useful improvement of the general theory is interesting, therefore our new unpublished generalized condition is expected to be an important step in the research of this field. To show the utility of this condition, we are on the way to find an appropriate application, which requires further research.

Publications, references, links

[APP83] D. Amit, G. Parisi, L. Peliti: Asymptotic behavior of the "true" self-avoiding walk. Phys. Rev. B, 27: 1635–1645 (1983)

[DR92] R. T. Durrett, L. C. G. Rogers: Asymptotic behavior of Brownian polymers. Probab. Theory Rel. Fields 92: 337–349 (1992)

[HTV10] I. Horváth, B. Tóth, B. Vető: Diffusive limits for "true" (or myopic) self-avoiding random walks and self-repellent Brownian polymers in dimensions three or higher. http://www.math.bme.hu/~vetob/publ/htv3/horvath_toth_veto_paper.pdf, submitted (2010)

[KV86] C. Kipnis, S. R. S. Varadhan: Central limit theorem for additive functionals of reversible Markov processes with applications to simple exclusion. Commun. Math. Phys. 106: 1–19 (1986)

[SVY00] S. Sethuraman, S. R. S. Varadhan, H-T. Yau: Diffusive limit of a tagged particle in asymmetric simple exclusion processes. Comm. Pure Appl. Math. 53: 972–1006 (2000)

[T86] B. Tóth: Persistent random walk in random environment. Probab. Theory Rel. Fields 71: 615–625 (1986)

[T95] B. Tóth: The "true" self-avoiding walk with bond repulsion on Z: limit theorems. Ann. Probab. 23: 1523–1556 (1995)

[TV08] B. Tóth, B. Vető: Self-repelling random walk with directed edges on Z. Electr. J. Probab. 13: 1909–1926 (2008)

[TV09] B. Tóth, B. Vető: Continuous time "true" self-avoiding random walk on Z. http://www.math.bme.hu/~vetob/publ/stsaw/stsaw_paper090506.pdf, submitted (2009)

[V96] S. R. S. Varadhan: Self-diffusion of a tagged particle in equilibrium of asymmetric mean zero random walks with simple exclusion. Ann. Inst. H. Poincaré – Probab. et Stat. 31: 273–285 (1996)

[V09] B. Vető: The "True" Self-Avoiding Random Walk in Z, Wolfram Demonstration Project (2009)