Hitting Time Distributions of Random Walks on Finite Graphs
Anuraag Kumar · 2025
Read Hitting Time Distributions of Random Walks on Finite Graphs by Anuraag Kumar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04985.txt.
Introduction
Anuraag Kumar studies how long a random walk on a finite graph takes to first reach a target node. Most past work gave only the mean of that hitting time, yet the spread can be wide, so a mean alone can mislead.
Kumar looks at the full shape and the variance of hitting times. He uses Markov chain tools, plus Fourier and spectral methods, to derive formulas and step rules for these values. The work is marked as early, with some results still being refined and a journal version planned.
Catalog record
| CREATOR | Anuraag Kumar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04985
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hitting Time Distributions of Random Walks on Finite Graphs Anuraag Kumar Abstract We investigate the hitting times of random walks on graphs, where a hitting time is defined as the number of steps required for a random walker to move from one node to another. While much of the existing literature focuses on calculating or bounding expected hitting times, this approach is insufficient, as hitting time distributions often exhibit high variance. To address this gap, we analyze both the full distributions and variances of hitting times. Using general Markov chain techniques, as well as Fourier and spectral methods, we derive formulas and recurrence relations for computing these distributions. Introduction Random walks are a fundamental topic in probability theory with wide-ranging applications across physics, engineering, mathematics, and computer science. There are tens of thousands of papers that explore them in depth. Random walks can be used to model a variety of real-world phenomena, including fluid dynamics, stock price movements, genetic drift, animal foraging behavior, and search algorithms. The central focus of this paper is the hitting time , which refers to the number of steps required for a random walk to move from one vertex of a graph to another. In formal terms, for a graph G=(V,E) , we define the hitting time as \tau_{i,j}=\inf\{t\mid X_{0}=i,X_{t}=j\} where X_{t} denotes the position of the random walker at time t , and i and j are two distinct vertices in the graph. One effective way to explore hitting times is through simulation. For example, consider the cycle graph with 10 nodes. The following diagram shows the graph: Suppose we are interested in the random variable \tau_{0,5} , representing the number of steps needed to go from node 0 to node 5. After running 10,000 trials, we obtain the following frequency graph: What stands out here is the large variance in the distribution. The sample mean is 25.0306, and the sample variance is 410, indicating that the variance is relatively large compared to the mean. We can observe a similar behavior in the hypercube graph with 8 nodes, which is shown below: Now, suppose we are interested in \tau_{(0,0,0),(1,1,1)} , the number of steps needed to move from node (0,0,0) to node (1,1,1) . After running 10,000 trials, we obtain the following frequency graph: The sample mean in this case is 10, and the sample variance is 63. This observation leads to the central motivation for this paper. In the literature, the primary focus in the study of hitting times has been on expected hitting times , denoted E[\tau_{i,j}] [ 5 ] [ 7 ] [ 8 ] [ 9 ] . However, as demonstrated above, the expected value alone is often a poor predictor of how the random walk behaves. In this paper, we will examine two related quantities: P(\tau_{i,j}=n) , the probability mass function of hitting times, and \text{Var}(\tau_{i,j}) , the variance of the hitting time. Despite their importance, these quantities receive less attention due to computational challenges. Our approach will involve general computations, with a subsequent focus on vertex-transitive graphs. Hitting Times on General Graphs Distributions Let’s try to find the distribution of P(\tau_{i,j}=n) on our graph G with Markov matrix A . One relationship becomes clear. P(\tau_{i,j}=n)=\sum_{k\neq j}P(\tau_{i,k}=1)P(\tau_{k,j}=n-1) The above formula calculates the probability of reaching an adjacent node to our ending node in n-1 steps and then making a step from that adjacent node to the end. By setting k\neq j , we make sure that we aren’t adding the probability that we arrive to ending node j one move early. The above is true, as each step of a random walk is independent. Let us fix an ending node j , and then let us define a vector P_{n}=\begin{bmatrix}P(\tau_{1,j}=n)\\ P(\tau_{2,j}=n)\\ \vdots\\ P(\tau_{|V|-1,j}=n)\end{bmatrix} the nodes 1,2...|V|-1 represent some arbitrary numbering of the nodes of the graph once j is removed. Let Q be the matrix such that Q_{ik}=P(\tau_{ik}=1) such that i,k\neq j . We then have P_{n}=QP_{n-1} as the recursion above is simply matrix multiplication. So then by induction, we have the following theorem Theorem 1 (The Hitting Time Recurrence Formula) P_{n}=Q^{n-1}P_{1} One might notice that Q is simply the Markov matrix of our graph but with removed jth row and jth column. Therefore, here we have a solid way of calculating distributions. As we are taking arbitrary powers of a matrix, it often comes down to diagonalizing Q . This is often hard to do by hand, but a computer can help. There are a couple things to note about the eigenvalues of such a matrix. 1. Q is a substochastic matrix as the sum of every row is less than or equal to 1. This implies that |\lambda|<1 . Where \lambda is an eigenvalue of Q . 2. Q is the adjacency graph of a subgraph of G . Which implies by the Interlacing theorem of Spectral Graph Theory that all the eigenvalues of Q are embedded between the eigenvalues of A . Consider this graph . We will use every step on a random walk is independent and assuming that walking across any edge is equally likely. Setting j=0 and then Q is \begin{bmatrix}0&\frac{1}{3}&\frac{1}{3}\\ \frac{1}{3}&0&\frac{1}{3}\\ \frac{1}{2}&\frac{1}{2}&0\\ \end{bmatrix} and P_{1} is \begin{bmatrix}\frac{1}{3}\\ \frac{1}{3}\\ 0\\ \end{bmatrix} . Then Q^{n-1}P_{1}=\begin{bmatrix}P(\tau_{1,0}=n)\\ P(\tau_{2,0}=n)\\ P(\tau_{3,0}=n)\end{bmatrix}=\begin{bmatrix}\frac{-\left(-1\right)^{n}*2^{2n}*3^{n}*\sqrt{13}+\left(2\sqrt{13}+14\right)^{n}*\sqrt{13}}{13*\left(\sqrt{13}+1\right)^{n}2^{n}3^{n}}\\ \frac{-\left(-1\right)^{n}*2^{\left(2*n\right)}*3^{n}*\sqrt{13}+\left(2\sqrt{13}+14\right)^{n}\sqrt{13}}{13*\left(\sqrt{13}+1\right)^{n}2^{n}3^{n}}\\ \frac{13*\left(-1\right)^{n}*2^{2n}3^{n}+13\left(2\sqrt{13}+14\right)^{n}+\left(-1\right)^{n}2^{2n}3^{n}\sqrt{13}-\left(2\sqrt{13}+14\right)^{n}\sqrt{13}}{26*\left(\sqrt{13}+1\right)^{n}2^{n}3^{n}}\end{bmatrix} We can see that even for relatively simple looking graphs, the distributions can be very complicated and often intractable to compute by hand with larger graphs. Later, we will restrict the graphs we will work with to make sure this process is simpler. Characteristic Function One technique we consider is that of the characteristic function Definition 1 (Characteristic function) The characteristic function of a hitting time distribution \phi_{\tau_{i,j}}(t) is defined as follows. \phi_{\tau_{i,j}}(t)=E[e^{it\tau_{i,j}}]=\sum_{n=-\infty}^{\infty}e^{int}P(\tau_{i,j}=n)=\sum_{n=0}^{\infty}e^{int}P(\tau_{i,j}=n) This can help us compute moments. Theorem 2 (Fast Formulas for the Moments of Hitting Times) The first two moments of the hitting time distribution can be expressed as follows. [ 6 ] E[\tau_{*,j}]=(I-Q)^{-1}\mathbf{1}=\sum_{n=0}^{\infty}Q^{n}\mathbf{1} E[\tau_{*,j}^{2}]=2\sum_{n=0}^{\infty}nQ^{n}\mathbf{1} \tau_{*,j} is a vector of random variable such that the ith coordinate is the random variable is \tau_{i,j} . Q is the matrix such that the jth column and row removed corresponding with the fact that j is the fixed ending point. The Proof is in Appendix A and also in [ 6 ] When it comes to actually computing these quantities. The above calculations exist for approximate values found by a computer. In some cases, it is feasible to use the above formulae to find the distributions for general classes of graphs. The cases below are generally easier to compute. Later in this paper, we will introduce machinery to tackle harder cases. We can summarize these easy cases through the following theorem Hitting Times on Standard Graphs We illustrate hitting time distributions for several canonical graphs. Complete Graph ( K_{k} ) For a complete graph with k nodes, a simple random walk moves uniformly to any other node at each step. The hitting time \tau_{i,j} from node i to node j follows a geometric distribution with success probability 1/(k-1) : P(\tau_{i,j}=n)=\left(\frac{k-2}{k-1}\right)^{n-1}\frac{1}{k-1}. Consequently, the expectation and variance are E[\tau_{i,j}]=k-1,\quad Var[\tau_{i,j}]=(k-1)(k-2). Intuitively, each step either moves toward the target (success) or not (failure), producing the geometric pattern. Complete Bipartite Graph ( K_{k_{1},k_{2}} ) A complete bipartite graph consists