The Library
Choice and bias in random walks
Tools
Tools
Tools
Georgakopoulos, Agelos, Haslegrave, John, Sauerwald, Thomas and Sylvester, John A. (2020) Choice and bias in random walks. In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Seattle, 12-14 Jan 2019. Published in: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 151 76 :1-76 :19. ISBN 9783959771344. doi:10.4230/LIPIcs.ITCS.2020.76 ISSN 1868-8969.
|
PDF
WRAP-Choice-bias-random-walks-Haslegrave-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (642Kb) | Preview |
|
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-choice-bias-random-walks-Haslegrave-2019.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (895Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.76
Abstract
We analyse the following random walk process inspired by the power-of-two-choice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW). We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected time
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
| Library of Congress Subject Headings (LCSH): | Random walks (Mathematics), Markov processes -- Numerical solutions, Computer algorithm | ||||||
| Series Name: | Leibniz International Proceedings in Informatics | ||||||
| Journal or Publication Title: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | ||||||
| Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
| ISBN: | 9783959771344 | ||||||
| ISSN: | 1868-8969 | ||||||
| Official Date: | 6 January 2020 | ||||||
| Dates: |
|
||||||
| Volume: | 151 | ||||||
| Page Range: | 76 :1-76 :19 | ||||||
| DOI: | 10.4230/LIPIcs.ITCS.2020.76 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||
| Date of first compliant deposit: | 27 November 2019 | ||||||
| Date of first compliant Open Access: | 28 November 2019 | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Seattle | ||||||
| Date(s) of Event: | 12-14 Jan 2019 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
