NDLI: Multiple Random Walks in Random Regular Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Cooper, Colin Frieze, Alan Radzik, Tomasz
Copyright Year	2009
Abstract	We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random r-regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728740], where it was shown with high probability (whp) that for $r\geq3$ the cover time is asymptotic to $\theta_r n\ln n$, where $\theta_r=(r-1)/(r-2)$. In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph G. For k independent walks on G, the cover time $C_G(k)$ is asymptotic to $C_G/k$, where $C_G$ is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/\binom{k}{2}$. If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to $\frac{2\ln k}{k}\theta_r n$ as $k,n\rightarrow\infty$. We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to $(2\ln2)\theta_r n$ as $k\rightarrow\infty$. The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to $2\theta_r n$. Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with k predators and $\ell$ prey the expected detection time is $\theta_r H_{\ell}n/k$, where $H_{\ell}$ is the $\ell$th harmonic number.
Starting Page	1738
Ending Page	1761
Page Count	24
File Format	PDF
ISSN	08954801
DOI	10.1137/080729542
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-11-25
Access Restriction	Subscribed
Subject Keyword	random walks random regular graphs Random graphs multiple walks Random walks on graphs
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Random Walks on Regular and Irregular Graphs

Multiple random walks in random regular graphs.

Viral processes by random walks on random regular graphs

Random Walks with Look-Ahead in Scale-Free Random Graphs

On the Implementation of Huge Random Objects

Cutoff phenomena for random walks on random regular graphs

Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk

Coalescing Random Walks and Voting on Connected Graphs

Periodic Walks on Large Regular Graphs and Random Matrix Theory

Multiple Random Walks in Random Regular Graphs

Similar Documents

Random Walks on Regular and Irregular Graphs

Multiple random walks in random regular graphs.

Viral processes by random walks on random regular graphs

Random Walks with Look-Ahead in Scale-Free Random Graphs

On the Implementation of Huge Random Objects

Cutoff phenomena for random walks on random regular graphs

Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk

Coalescing Random Walks and Voting on Connected Graphs

Periodic Walks on Large Regular Graphs and Random Matrix Theory

Multiple Random Walks in Random Regular Graphs