Journal article

Biased Random Walk on the Trace of Biased Random Walk on the Trace of ...

David Croydon, Mark Holmes



We study the behaviour of a sequence of biased random walks (X(i))i≥0 on a sequence of random graphs, where the initial graph is Zd and otherwise the graph for the ith walk is the trace of the (i- 1) st walk. The sequence of bias vectors is chosen so that each walk is transient. We prove the aforementioned transience and a law of large numbers, and provide criteria for ballisticity and sub-ballisticity. We give examples of sequences of biases for which each (X(i))i≥1 is (transient but) not ballistic, and the limiting graph is an infinite simple (self-avoiding) path. We also give examples for which each (X(i))i≥1 is ballistic, but the limiting graph is not a simple path.

University of Melbourne Researchers


Awarded by Australian Research Council

Awarded by JSPS

Funding Acknowledgements

The authors thank an anonymous referee for suggestions that helped us improve the paper. The work of MH was supported by Future Fellowship FT160100166, from the Australian Research Council. DC would like to thank the School of Mathematics and Statistics at the University of Melbourne for its generous support during a visit to Melbourne in August 2018, which is when the majority of the work on this article was completed, and also acknowledge the support of his JSPS Grant-in-Aid for Research Activity Start-up, 18H05832. MH thanks Ross Ihaka for providing the main R code used to perform simulations.