The small world effect on the coalescing time of random walks (Q544499)

From MaRDI portal
Revision as of 11:05, 1 July 2023 by Importer (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
The small world effect on the coalescing time of random walks
scientific article

    Statements

    The small world effect on the coalescing time of random walks (English)
    0 references
    0 references
    0 references
    15 June 2011
    0 references
    A random graph is constructed starting from a deterministic graph either by adding random connections, or by removing some connections randomly, as for percolation. Particular classes of random graphs of the first type are small world graphs, constructed starting from a \(d\)-dimensional (discrete) torus of size \(2L\), whose edges are called short range connections, adding some random connections, called long range connections. The authors study the asymptotic behavior of the meeting time \(T\) of two random walks moving on this small world and compare it with the result on the torus. On the torus, in order to have convergence, the authors rescale \(T\) by a dimension dependent factor. They prove that the walks always meet faster on the small world graphs than on the torus if \(d \leq 2\), while if \(d \geq 3\), this depends on the probability of moving along the random connection. As an application, the authors obtain results on the hitting time to the origin of a single walk and on the convergence of coalescing random walk systems on small world graphs.
    0 references
    small world
    0 references
    random walk
    0 references
    coalescing random walk
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references