I have a random walk defined on a complete graph with n vertices(there is an edge between any pair of nodes). I need to compute the expected hitting time $E(\tau)$ of the set $A=\{1,2,3\}$ given some starting state $x_0 \not \in A$ say $x_0=4$

I know how to setup have the transition matrix $P$ ( as a function of $n$) and I define matrix $ Q $ that is $n-3 \times n-3 $ sub matrix of $P$ that captures the transitions from states $ \not \in A$ to states $ \not \in A$

From my text book I know I need to compute $ M= (I - Q)^{-1} $ and then simply compute $ E(\tau| x_0=i \not \in A) = \sum_{j=4}^{n} M_{ij} $

The matrix $ I -Q$ looks like this

$I -Q =\begin{bmatrix} 1 & -1/(n-1) & -1/(n-1) & \cdots \\ -1/(n-1) & 1 & -1/(n-1) & \cdots \\ -1/(n-1) & -1/(n-1) & 1 & \cdots \\ \cdots & \cdots & \cdots & 1 \\ \end{bmatrix}$

But I'm not sure how to compute its inverse.

Any idea ?

  • $\begingroup$ hint: what you want is $M\mathbf 1$ and if you confirm that $\mathbf 1$ is an eigenvector of $(I-Q)$ with eigenvalue $\lambda$ -- what does that tell you about $\mathbf 1$ and $(I-Q)^{-1}$? You may also want to justify how you know that $(I-Q)^{-1}$ exists $\endgroup$ Commented Apr 12, 2022 at 15:33

1 Answer 1


Since it is not specified in the question, I will assume that the random walk is a discrete-time random walk, which jumps to a neighbouring site at each time-step with equal probability (assuming no stay-back at any time-step).

Suppose the walker starts from a site $v \notin A$. At any given time-step, if the walker is not on a vertex in $A$, then the walker jumps to some vertex in $A$ with probability $\frac{3}{n-1}$ in the next time-step, or to a vertex outside $A$ with probability $\frac{n-4}{n-1}$. Now, you can imagine that the computation of the hitting time can be interpreted as a sequence of Bernoulli trials. Clearly, the mean time taken to hit $A$ will be $\frac{n-1}{3}$. But you can easily go beyond the mean, and calculate the $\textit{full distribution}$ of hitting times. Let us define the random variable $T$ to denote the hitting time. Then the probability that $T$ takes a value $t$ is given by

$$ Prob(T = t) = \big( \frac{n-4}{n-1}\big)^{t-1}\cdot\frac{3}{n-1}.$$ suggesting that the hitting time is geometrically distributed.

In this answer, even though I assumed that the random walk was taking place in discrete-time, and that there were no "stay-back" events, I suppose it will be easy to generalize this solution to those other settings.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .