1
$\begingroup$

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 ?

$\endgroup$
1
  • $\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

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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