Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-17T16:07:20.315Z Has data issue: false hasContentIssue false
  • English
  • Français

First-Passage Percolation with Exponential Times on a Ladder

Published online by Cambridge University Press:  19 March 2010

HENRIK RENLUND
HENRIK RENLUND*
Affiliation:
Mathematics Department, Uppsala University, PO Box 480, 751 06 Uppsala, Sweden (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider first-passage percolation on a ladder, i.e., the graph ℕ × {0, 1}, where nodes at distance 1 are joined by an edge, and the times are exponentially i.i.d. with mean 1. We find an appropriate Markov chain to calculate an explicit expression for the time constant whose numerical value is ≈0.6827. This time constant is the long-term average inverse speed of the process. We also calculate the average residual time.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 4 , July 2010 , pp. 593 - 601
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Abramowitz, M. and Stegun, I. (1964) Handbook of Mathematical Functions, National Bureau of Standards Applied Mathematics Series, Vol. 55.Google Scholar
[2]Alm, S. E. and Janson, S. Personal communication.Google Scholar
[3]Alm, S. E. and Janson, S. (1990) Random self-avoiding walks on one-dimensional lattices. Commun. Statist. Stochastic Models 6 169–212.Google Scholar
[4]Alm, S. E. and Parviainen, R. (2002) Lower and upper bounds for the time constant of first-passage percolation. Combin. Probab. Comput. 11 433–445CrossRefGoogle Scholar
[5]Flaxman, A., Gamarnik, D. and Sorkin, G. (2006) First-passage percolation on a width-2 strip and the path cost in a VCG auction. Internet and Network Economics 4286 99–111.CrossRefGoogle Scholar
[6]Parviainen, R. and Renlund, H. In preparation.Google Scholar
[7]Schlemm, E. (2009) First-passage percolation rates on width-two stretches with exponential link weights. Electron. Commun. Probab. 14 424–434.CrossRefGoogle Scholar
[8]Sloane, N. (2007) The On-Line Encyclopedia of Integer Sequences. Published electronically at www.research.att.com/~njas/sequences/Google Scholar
[9]Smythe, R. T. and Wierman, J. C. (1978) First-Passage Percolation on the Square Lattice, Vol. 671 of Lecture Notes in Mathematics, Springer.CrossRefGoogle Scholar
[10]Watson, G. N. (1922) A Treatise on the Theory of Bessel Functions, Cambridge University Press.Google Scholar