NDLI: Coalescing Random Walks and Voting on Connected Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Elsässer, Robert Cooper, Colin Radzik, Tomasz Ono, Hirotaka
Copyright Year	2013
Abstract	In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let $G=(V,E)$ be an undirected and connected graph with $n$ vertices and $m$ edges. The coalescence time, $C(n)$, is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that $C(n) = O\big(\frac{1}{1-\lambda_2}\big(\log^{4} n + \frac{n}{\nu}\big)\big)$. Here $\lambda_2$ is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of $\nu$ is given by $\nu= \sum_{v\in V} d^2(v)/(d^2n)$, where $d(v)$ is the degree of vertex $v$, and $d=2m/n$ is the average degree. The parameter $\nu$ is an indicator of the variability of vertex degrees: $1 \le \nu = O(n)$, with $\nu=1$ for regular graphs. Our general bound on $C(n)$ holds for all connected graphs. This implies, for example, that $C(n)=O(n/(1-\lambda_2))$ for $d$-regular graphs with expansion parameterized by the eigenvalue gap $1-\lambda_2$. The bound on $C(n)$ given above is sublinear for some classes of graphs with skewed degree distributions. In the voter model, initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. Let ${\mathbf{E}} (C_{{\mbox{\boldmath$v$}}})$ be the expected time for voting to complete, that is, for a unique opinion to emerge. A system of coalescing particles, where initially one particle is located at each vertex, corresponds to the voter model in that $\mathbf{E}(C_{{\mbox{\boldmath$v$}}})=C(n)$. Thus our result stated above for $C(n)$ also gives general bounds for $\mathbf{E}(C_{{\mbox{\boldmath$v$}}})$.
Starting Page	1748
Ending Page	1758
Page Count	11
File Format	PDF
ISSN	08954801
DOI	10.1137/120900368
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	27
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-10-16
Access Restriction	Subscribed
Subject Keyword	random walks voter model coalescing random walks Markov chains Graph theory 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

Coalescing Random Walks and Voting on Connected Graphs∗ (2014)

Coalescing random walks and voting on graphs

A Spanning Tree Method for Bounding Hitting Times of Random Walks on Graphs

Coalescing random walks and voting on graphs (2012)

Deterministic Random Walks for Rapidly Mixing Chains

Random walks on graphs: new bounds on hitting, meeting, coalescing and returning

Coalescing random walks and voting on connected graphs

Mean field conditions for coalescing random walks

Short Random Walks on Graphs

Coalescing Random Walks and Voting on Connected Graphs

Similar Documents

Coalescing Random Walks and Voting on Connected Graphs∗ (2014)

Coalescing random walks and voting on graphs

A Spanning Tree Method for Bounding Hitting Times of Random Walks on Graphs

Coalescing random walks and voting on graphs (2012)

Deterministic Random Walks for Rapidly Mixing Chains

Random walks on graphs: new bounds on hitting, meeting, coalescing and returning

Coalescing random walks and voting on connected graphs

Mean field conditions for coalescing random walks

Short Random Walks on Graphs

Coalescing Random Walks and Voting on Connected Graphs