First-passage percolation with exponential times on a ladder

DOI10.1017/S0963548310000052zbMATH Open1202.60158arXiv1002.3709MaRDI QIDQ4933602FDOQ4933602

Authors: Henrik Renlund 

Publication date: 14 October 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: We consider first-passage percolation on a ladder, i.e. the graph {0,1,...}*{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 approximately 0.6827. This time constant is the long-term average inverse speed of the process. We also calculate the average residual time.

Full work available at URL: https://arxiv.org/abs/1002.3709

Recommendations

• First-passage percolation on ladder-like graphs with inhomogeneous exponential times
• On the Markov transition kernels for first passage percolation on the ladder
• First-passage percolation on a ladder graph, and the path cost in a VCG auction
• Inequalities for the time constant in first-passage percolation
• Strict inequalities for the time constant in first passage percolation.

zbMATH Keywords

average residual timefirst-passage percolation on a ladderlong-term average inverse speed

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Random walks on graphs (05C81)

Cites Work

• Random self-avoiding walks on one-dimensional lattices
• First-passage percolation on the square lattice
• First-passage percolation on width-two stretches with exponential link weights

Cited In (4)

• First-passage percolation on ladder-like graphs with inhomogeneous exponential times
• Asymptotics of First-Passage Percolation on One-Dimensional Graphs
• On the Markov transition kernels for first passage percolation on the ladder
• First-passage percolation on a ladder graph, and the path cost in a VCG auction

This page was built for publication: First-passage percolation with exponential times on a ladder

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933602)