5
$\begingroup$

Let $\{X_n\}$ be a homogenous Markov chain, taking values in N.

$T_i:=\inf\{k\ge0:X_k=i\}$ is the first time when the chain arrives at i. I know that if X is irreducible positive recurrent, then $E_iT_i$ is finite.

Now I want to know some results about $E_j T_i$, the expected time of first arrival at state $i$ starting from state $j$. I think that it should be finite almost surely.

Is there any explicit form of $E_j T_i$, or inequality? And what about an arbitrary initial distribution? Any help would be appreciated.

$\endgroup$
4
  • $\begingroup$ What exactly do you mean by "discrete parameter"? $\endgroup$
    – Math1000
    Commented Jun 1, 2015 at 14:38
  • $\begingroup$ By $E_jT_i$ do you mean the expected time, starting from state $j$, to first arrive at state $i$? $\endgroup$
    – Brian Tung
    Commented Jun 1, 2015 at 16:14
  • 1
    $\begingroup$ discrete parameter means that the markov chain takes value in a discrete space. Or explicitly, in N={0,1,2,...}. And $E_jT_i$ means the expected time, starting from j, to first arrive at i. For any recurrent state i, we can compute $E_iT_i$ by construct its invarient measure, and I want to know is there any similar result about $E_jT_i$. Or for any positive recurrent chain, is $E_jT_i$ finite? $\endgroup$
    – Hu ju yuan
    Commented Jun 2, 2015 at 14:48
  • $\begingroup$ I have edited to reopen, but there is likely a problem with your defintion of $E_i T_i$ as the infimum of times when $X = i$ starting from $i$ is simply zero. Therefore the finiteness of $E_i T_i$ would not depend on whether states are recurrent with positive probability. Also, is "N" supposed to be the natural numbers $\mathbb{N}$? Any computation will require knowledge of the transition probabilitiies for these states. $\endgroup$
    – hardmath
    Commented Jun 8, 2015 at 13:35

1 Answer 1

10
$\begingroup$

For a fixed $i$, let $\psi(j) = \mathbb{E}_j T_i$, i.e. the expected time to reach state $i$ starting from state $j$. Then for $\psi(j)$ the following holds:

$$ \psi(j) = \begin{cases} 0\text{,} & j = i\\ 1 + \sum\limits_{k \neq j} p_{j k}\psi(k)\text{,} & j \neq i \end{cases} $$

where $p_{j k}$ denotes the one-step transition probability from $j$ to $k$.


Proof sketch Start from state $j$. If $j = i$, then obviously $T_i = 0$, and so $\mathbb{E}_j[T_i \mid j = i] = 0$. If, however, $j \neq i$, then $T_i = 1 + T^{\prime}_i$, where $T^{\prime}_i$ denotes the remaining time to reach $i$. Invoking the Markov property conditional on the first step, and the chain's homogeneity, we can get the recurrence stated above.


You can generalize the above recurrence using an arbitrary award function depending on which state you end up in. Here, for example, the award function gives $1$ (you can count this $1$ as a penalty though) whenever $j \neq i$, and $0$ when $j = 0$.


Another way you can calculate this is by marking the state you want to reach as an absorbing one, and use the fundamental matrix to calculate the expected time until absorption. There is also a mean first passage matrix. See Grinstead & Snell, pp. 461 onward.

$\endgroup$
1
  • 2
    $\begingroup$ The formula is incorrect, the correct is $$\psi(j) = \begin{cases} 0\text{,} & j = i\\ 1 + \sum\limits_{\color{red}{k \neq i}} p_{j k}\psi(k)\text{,} & j \neq i \end{cases}$$ $\endgroup$ Commented Nov 25, 2020 at 16:43

You must log in to answer this question.

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