Expected hitting time of a random walk on a complete graph

linear algebramarkov chainsmarkov-process

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 ?

Best Answer

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.

Related Question