# Expected hitting time of a random walk on a complete graph

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 ?

• 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 Commented Apr 12, 2022 at 15:33

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.