2004/10/12 by Jianjun Tian, Jianjun Paul Tian, Xiao-Song Lin +2
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Opinion Dynamics and Social Influence #Probability (math.PR) #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0410298
18 pages
arxiv created 2004/10/12 · openalex publication_date 2004/10/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study continuous time Markov processes on graphs. The notion of frequency is introduced, which serves well as a scaling factor between any Markov time of a continuous time Markov process and that of its jump chain. As an application, we study ``multi-person simple random walks'' on a graph G with n vertices. There are n persons distributed randomly at the vertices of G. In each step of this discrete time Markov process, we randomly pick up a person and move it to a random adjacent vertex. We give estimate on the expected number of steps for these n persons to meet all together at a specific vertex, given that they are at different vertices at the begininng. For regular graphs, our estimate is exact.