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 ?
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.