Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T12:59:55.834Z Has data issue: false hasContentIssue false

The degree-wise effect of a second step for a random walk on a graph

Published online by Cambridge University Press:  16 January 2019

Kenneth S. Berenhaut*
Affiliation:
Wake Forest University
Hongyi Jiang*
Affiliation:
Johns Hopkins University
Katelyn M. McNab*
Affiliation:
Wake Forest University
Elizabeth J. Krizay*
Affiliation:
Georgia Institute of Technology
*
* Postal address: Department of Mathematics and Statistics, Wake Forest University, Winston-Salem, NC 27109, USA.
*** Postal address: Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218, USA.
* Postal address: Department of Mathematics and Statistics, Wake Forest University, Winston-Salem, NC 27109, USA.
**** Postal address: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we consider the degree-wise effect of a second step for a random walk on a graph. We prove that under the configuration model, for any fixed degree sequence the probability of exceeding a given degree threshold is smaller after two steps than after one. This builds on recent work of Kramer et al. (2016) regarding the friendship paradox under random walks.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2018