uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Hitting Times for Random Walks with Restarts
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2012 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 26, no 2, 537-547 p.Article in journal (Refereed) Published
Abstract [en]

The time it takes a random walker in a lattice to reach the origin from another vertex x has infinite mean. If the walker can restart the walk at x at will, then the minimum expected hitting time gamma(x, 0) (minimized over restarting strategies) is finite; it was called the "grade" of x by Dumitriu, Tetali, and Winkler. They showed that in a more general setting, the grade (a variant of the "Gittins index") plays a crucial role in control problems involving several Markov chains. Here we establish several conjectures of Dumitriu, Tetali, and Winkler on the asymptotics of the grade in Euclidean lattices. In particular, we show that in the planar square lattice, gamma(x, 0) is asymptotic to 2 vertical bar x vertical bar(2) log vertical bar x vertical bar as vertical bar x vertical bar ->infinity. The proof hinges on the local variance of the potential kernel h being almost constant on the level sets of h. We also show how the same method yields precise second order asymptotics for hitting times of a random walk (without restarts) in a lattice disk.

Place, publisher, year, edition, pages
2012. Vol. 26, no 2, 537-547 p.
Keyword [en]
random walk, hitting time, Gittins index, harmonic function, potential kernel
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-178157DOI: 10.1137/100796352ISI: 000305962300009OAI: oai:DiVA.org:uu-178157DiVA: diva2:542128
Available from: 2012-07-30 Created: 2012-07-30 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Janson, Svante

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Applied Mathematics
In the same journal
SIAM Journal on Discrete Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 387 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf