Percolation de premier passage

First passage percolation is a mathematical method used to describe the paths reachable in a random medium within a given amount of time. First passage percolation is one of the most classical areas of probability theory. It was first introduced by John Hammersley and Dominic Welsh in 1965 as a model of fluid flow in a porous media. It is part of percolation theory, and classical Bernoulli percolation can be viewed as a subset of first passage percolation. Most of the beauty of the model lies in its simple definition (as a random metric space) and the property that several of its fascinating conjectures do not require much effort to be stated. Most times, the goal of first passage percolation is to understand a random distance on a graph, where weights are assigned to edges. Most questions are tied to either find the path with the least weight between two points, known as a geodesic, or to understand how the random geometry behaves in large scales. As is the case in percolation theory in general, many of the problems related to first passage percolation involve finding optimal routes or optimal times. The model is defined as follows. Let be a graph. We place a non-negative random variable , called the passage time of the edge , at each nearest-neighbor edge of the graph . The collection is usually assumed to be independent, identically distributed but there are variants of the model. The random variable is interpreted as the time or the cost needed to traverse edge . Since each edge in first passage percolation has its own individual weight (or time) we can write the total time of a path as the summation of weights of each edge in the path. Given two vertices of one then sets where the infimum is over all finite paths that start at and end at . The function induces a random pseudo-metric on . The most famous model of first passage percolation is on the lattice . One of its most notorious questions is "What does a ball of large radius look like?".

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (5)

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by desc

EPFL2020

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of

CAMBRIDGE UNIV PRESS2020

Disjoint crossings, positive speed and deviation estimates for first passage percolation

Ghurumuruhan Ganesan

Consider bond percolation on the square lattice Z(2) where each edge is independently open with probability p : For some positive constants p(0) is an element of( 0; 1); epsilon(1) and epsilon(2); the

Univ Washington, Dept Mathematics2014