Exact analytic expressions for discrete first-passage time probability distributions in Markov networks

• Published in: arXiv.org 2024-03
• Main Author: Albert, Jaroslav
• Format: Article
• Language: English
• Subjects: Continuity (mathematics); Delta function; Networks; Nodes; Travel time
• ISSN: 2331-8422

The first-passage time (FPT) is the time it takes a system variable to cross a given boundary for the first time. In the context of Markov networks, the FPT is the time a random walker takes to reach a particular node (target) by hopping from one node to another. If the walker pauses at each node for a period of time drawn from a continuous distribution, the FPT will be a continuous variable; if the pauses last exactly one unit of time, the FPT will be discrete and equal to the number of hops. We derive an exact analytical expression for the discrete first-passage time (DFPT) in Markov networks. Our approach is as follows: first, we divide each edge (connection between two nodes) of the network into \(h\) unidirectional edges connecting a cascade of \(h\) fictitious nodes and compute the continuous FPT (CFPT). Second, we set the transition rates along the edges to \(h\), and show that as \(h\to\infty\), the distribution of travel times between any two nodes of the original network approaches a delta function centered at 1, which is equivalent to pauses lasting 1 unit of time. Using this approach, we also compute the joint-probability distributions for the DFPT, the target node, and the node from which the target node was reached. A comparison with simulation confirms the validity of our approach.