On a Random Walk Reliability Problem With Arc Memory

Burak Buke, J. Cole Smith, Sadie Thomas

Research output: Working paper


Consider a directed network in which each arc can fail with some specied proba-
bility. An entity arrives on this network at a designated origin node and traverses the
network in a random-walk fashion until it either terminates at a destination node, or
until an arc fails while being traversed. We study the problem of assessing the prob-
ability that the random walk reaches the destination node, which we call the survival
probability of the network. Complicating our analysis is the assumption that certain
arcs have \memory," in the sense that after a memory arc is successfully traversed, it cannot fail on any subsequent traversal during the walk. We prove that this problem is #P-hard, provide methods for obtaining lower and upper bounds on the survival probability, and demonstrate the effectiveness of our bounding methods on randomly generated networks.
Original languageEnglish
Publication statusUnpublished - 2013


Dive into the research topics of 'On a Random Walk Reliability Problem With Arc Memory'. Together they form a unique fingerprint.

Cite this