Workshop on
"Self-Interacting Random Walks"
March 29-31, 2006
EURANDOM, Eindhoven, The Netherlands
ABSTRACTS
Berg van den, Rob (CWI and Free University of Amsterdam)
Self-destructive percolation in the plane
Most of this talk is about joint work with Rachel Brouwer and Balint Vagvolgyi.
A few years ago we introduced, motivated by the study of certain forest-fire processes, the self-destructive percolation model. A typical configuration for this model with parameters $p$ and $\delta$ is generated in three steps: First we generate a typical configuration for the ordinary percolation model with parameter $p$. Next, we make all sites in the infinite occupied cluster vacant. Finally, each site that was already vacant in the beginning or made vacant by the above action, becomes occupied with probability $\delta$. Let $\theta(p,\delta)$ be the probability that some specified vertex belongs,in the final configuration, to an infinite occupied cluster. A few years ago we stated the conjecture that, for the square lattice and other planar lattices, the function $\theta$ has a discontinuity at points of the form $(p_c, \delta)$, with $\delta$ sufficiently small. We also showed remarkable consequences for the forest-fire models. The conjecture naturally raises the question whether the above mentioned function is continuous outside some region of the above mentioned form. We have proved that this is indeed the case. An important ingredient in the proof is a modification of a recent ingenious RSW-like percolation result of Bollob\'{a}s and Riordan.
Biskup, Marek (University of California at Los Angeles)
A quenched invariance principle for random walk on percolation clusters
I will consider the simple random walk on the (unique) infinite cluster of super-critical bond percolation in Z^d with d>1. By analyzing a harmonic embedding of the cluster, I will sketch a proof of the fact that, for almost every percolation configuration, the path distribution of the walk converges weakly to that of non-degenerate, isotropic Brownian motion. Based on joint work with Noam Berger.
Brydges, David (University of British Columbia)
A combinatorial generalisation of Cramers Rule
We show that a ratio of generating functions for disjoint oriented loops in a finite graph can be expressed in terms of the generating function of a single path in the graph weighted according to loops in the path. The result is a generalisation of Cramer's formula for the inverse of a matrix.
Collevecchio, Andrea (University D'Annunzio)
On the transience of processes defined on trees and other graphs
We introduce a simple technique to prove the transience of processes defined on trees generated by supercritical branching processes. We apply this method to biased random walk, once-reinforced random walk and vertex-reinforced jump process. We also prove the transience of certain reinforced random walks defined on certain graphs with cycles.
Davis, Burgess (Purdue University)
Vertex reinforced jump processes
A vertex reinforced jump process is a continuous time walk on the vertices of a graph. If at time t the walk is at vertex v, its next jump is to one of the nearest neighbors of v, and the rate at which it jumps to one of these neighbors w is one plus the total amount of time before t that the process has been at w. Stanislas Volkov and I have proved precise results about this process on the integers, especially about how its range grows with t, and have also studied recurrence/transience on trees. I will talk about this work and some recent developments.
Häggström, Olle (Chalmers University of Technology)
Optimization, evolution, and the two kinds of applied mathematics
Applied mathematics can be classified into two types depending on whether its purpose is to enlighten and explain, or to obscure and confuse. I approve of only one of these two purposes. After a brief general discussion, I intend to illustrate the other type with a work by W. Dembski that purports to draw far-reaching consequences about evolutionary biology from the theory of discrete optimization.
Holmes, Mark (EURANDOM)
Senile reinforced random walks
In joint work with Akira Sakai, we consider random walks with transition probabilities depending only on the number of consecutive traversals of the edge most recently traversed. Such walks may get stuck on a single edge, or have every vertex recurrent or every vertex transient depending on the reinforcement function that characterises the model. We prove recurrence/transience results and investigate the diffusion constant for such walks.
Limic, Vlada (Marseille)
Attracting edge: does it happen and if so when?
Reinforcement is observed frequently in nature and society, where beneficial interactions tend to be repeated. Edge reinforced random walker on a graph remembers the number of times each edge was traversed in the past, and decides to make the next random step with probabilities favoring places visited before. This talk will address several natural questions on asymptotic behavior of ''strongly reinforced walks'', i.e. those where the reinforcement weight function k->W(k) is reciprocally summable. It was recently established (jointly with Pierre Tarres) that the walker asymptotically keeps traversing a single random edge with probability 1 under the above summability condition and some fairly general technical assumptions. In an ongoing work (jointly with Codina Cotar) we obtain further information on the time of appearance of this attracting edge.
Matzinger, Henry (Georgia Institute of Technology)
Some recent developments in the LCS-problem and Optimal Alignment
We present some recent result on the order of the fluctuation
and the structure of the optimal alignment path for two independent texts. We
consider the Longest Common Subsequence
(LCS) case as well as cases with different scoring functions.
We also introduce a particle process in a random environment which we show to be
equivalent to the LCS-problem.
Skyrms, Brian (University of California)
Learning to Signal
This motivates and considers application of reinforcement learning to signaling games. The question is if and how meaning of signals spontaneously emerges. Even the simplest models lead to problems that have not yet been solved.
Steif, Jeff (Chalmers University of Technology)
Joint work with Tom Liggett and Balint Toth
Statistical mechanical systems on complete graphs, infinite exchangeability and finite extensions
We show that a large collection of statistical mechanical systems with quadratically represented Hamiltonians on the complete graph can be extended to infinite exchangeable processes. This includes all ferromagnetic Ising, Potts and Heisenberg models. We obtain sharp quantitative results on how much the antiferromagnetic Ising model can be extended using a solution to a new moment problem. We also discuss the Ising model with an addition 3-body interaction as well as a number of other issues.
Takeshima, Masaki (Osaka University)
Recurrence of once edge-reinforced random walks with exponential weights on trees
Edge-Reinforced Random Walk (ERRW), introduced by Coppersmith and Diaconis in 1986 [1], is a random process evolving in an environment constantly modified by its own behaviour: at each step, the probability to move along an edge is proportional to a function - called the weight function - of the number of visits to this edge. Pemantle introduced the notion of Vertex-Reinforced Random Walk (VRRW) in 1988 [3], which favours the more visited vertices instead.
Although introduced by similar definitions, these processes show significantly different behaviours. For instance, if the walk is on the integers and has linear weight function, then the VRRW eventually a.s. gets stuck on five (random) points, as proved in [6], whereas the ERRW visits all the sites infinitely often. However, if the weight function is nondecreasing and reciprocally summable then, on any graph of bounded degree, the (strongly) ERRW localizes and in fact ends up visiting the same (random) edge back and forth, as shown in [2] (joint work with V. Limic).
The result presented in [6] was conjectured by Pemantle and Volkov [5], who proved that the the walk has a.s. finite range and that the five points localization indeed happens with positive probability. The attracting edge property proved in [2] for strongly ERRW was originally shown on graphs without odd cycles by Sellke [4] in 1994 (without requiring a nondecreasing weight function), who conjectured that the result remains true for all graphs.
The purpose of this talk is to present these results [2] and [6], and the methods to tackle them. The study of strongly ERRW requires the combination of local probabilistic properties, whereas VRRW needs more global tools, corresponding to an longer-range interaction in a certain sense.
[1] D. Coppersmith and P. Diaconis. Random walks with reinforcement. Unpublished manuscript, 1986.
[2] V. Limic and P. Tarrès. Attracting edge and strongly edge reinforced walks. Preprint, 2006
[3] R. Pemantle. Random processes with reinforcement. Massachussets Institute of Technology Doctoral Dissertation, 1988.
[4] R. Pemantle and S. Volkov, Vertex-reinforced random walk on Z has finite range, Annals of Probability, 27(3):1368-1388, 1999
[5] T. Sellke, Reinforced random walks on the d-dimensional integer lattice. Technical report 94-26, Purdue University, 1994
[6] P. Tarrès. VRRW on Z eventually gets stuck on five points. Annals of Probability, 32(3B):2650-2701, 2004.
Van der Hofstad, Remco (Eindhoven University of Technology and EURANDOM)
Joint work with Mark Holmes and Vlada Limic
An expansion for self-interacting random walks
Self-interacting random processes are receiving tremendous attention in the
past years. Examples are reinforced random walks, true self-avoiding walk,
excited random walk, and loop-erased random walk. Often, martingale techniques
are used to prove laws of large numbers and/or central limit theorems.
Unfortunately, the description of the limiting parameters, for example the
limiting drift, is rather implicit, which makes it hard to investigate its
properties. For example, for many models it is natural that the drift is
monotone in the parameter in the model.
In statistical mechanics, expansions such as the lace expansion have proved a
powerful tool to investigate models with an interaction above the upper critical
dimension. We propose an expansion that applies in the general setting of
self-interacting random walks. In order to prove a LLN and/or a CLT, apart from
the expansion, one needs bounds on the coefficients. We are able to prove these
bounds in two cases: excited random walk above 6 dimensions and directed once
reinforced random walk, where the reference random walk has a drift.
Interestingly, the drift is given explicitly in terms of the expansion
coefficients, which may make it possible to prove monotonicity properties of the
drift.
Excited random walks
Excited random walks are non-Markovian walks which have a drift in a certain
direction, the strength of which might depend on the local time of the walk and
on a random environment.
We discuss criteria for recurrence, transience and positivity of speed of these
walks.
This page is maintained by Lucienne Coolen