3
$\begingroup$

I know how to calculate the variance of the number of steps in an absorbing markov chain. However, I am not sure that the distribution of the number of steps is normal. Therefore I would like to express the spread as percentiles, e.g. 5% percentile and 95% percentile. Is there any computatial efficient way how to do this?

$\endgroup$
1
+50
$\begingroup$

Finding all the percentiles is equivalent to finding the quantile function for the number of steps, which is equivalent to finding the distribution of the number of steps. So this problem requires you to derive the distribution of the number of steps to the absorbing state. Depending on your Markov chain, this might be easy, or it might be really difficult. In the latter case you should be able to get a good approximation to the distribution by running simulations of the chain, recording the number of steps to the absorbing state in each simulation, and then using these to find the kernel density estimator (KDE) to approximate the true distribution.


Without specifying any further properties of the Markov chain, there is not much more that can be said. To narrow things down a bit, I am going to consider a finite-state Markov chain in discrete time $\{ X_t | t \in \mathbb{N}_{0+} \}$ with an absorbing state $X_t=1$ and non-absorbing states $X_t = 2,...,M$. We let $\mathbf{v}$ be a probability row vector for the initial state of the chain, and $\mathbf{P}$ be the transition probability matrix. This means that the state-probability at an arbitrary time can be written as:

$$\mathbb{P}(X_t = k) = [ \mathbf{v} \mathbf{P}^t]_k \quad \quad \quad \text{for all } t \in \mathbb{N}_{0+} \text{ and } k = 1,...,M.$$

Now, define the first time until the absorbing state as $T \equiv \min \{ t \in \mathbb{N}_{0+} | X_t = 1 \}$. Since the chain cannot leave the absorbing state once it has arrived there (that being the nature of an absorbing state), the cumulative distribution for this random variable is given by:

$$\begin{equation} \begin{aligned} F_T(t) = \mathbb{P}(T \leqslant t) = \mathbb{P}(X_t = 1) &= [ \mathbf{v} \mathbf{P}^t]_1. \\[6pt] \end{aligned} \end{equation}$$

The corresponding quantile function is:

$$Q_T(p) = \min \{ t \in \mathbb{N}_{0+} | p \leqslant F_T(t) \} = \min \{ t \in \mathbb{N}_{0+} | p \leqslant [ \mathbf{v} \mathbf{P}^t]_1 \}.$$

This gives you an explicit expression for the quantile function, written in terms of the underlying transition probability matrix $\mathbf{P}$ and the initial-state probability vector $\mathbf{v}$. With a bit more work, this result can be generalised to cases where there are infinite states, or continuous time.

$\endgroup$
  • $\begingroup$ Thanks, but I am looking for a solution that does not involve simulations. $\endgroup$ – ACNB Jul 10 at 9:18
  • 2
    $\begingroup$ At the moment you have not specified anything about your Markov chain other than the fact that it has an absorbing state. With this minimal information, there is not really anything more we can tell you about finding the solution. $\endgroup$ – Ben Jul 14 at 6:16
  • $\begingroup$ What additional information would help? My Markov chain seems very generic... $\endgroup$ – ACNB Jul 15 at 7:11
  • 1
    $\begingroup$ Normally you would specify a Markov chain by stating the initial state distribution and the transition probabilities. $\endgroup$ – Ben Jul 15 at 13:24
  • $\begingroup$ Sorry, I am interested in this problem in general. I cannot assume anyinitial state distribution or transition probabilities. $\endgroup$ – ACNB Jul 16 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.