Expected value of minimum first passage time of several Markov Chains

42 Views Asked by At

Consider $m$ finite state discrete time Markov chains $X_t^1,X_t^2,...,X_t^m(t=0,1,...)$. All of these $m$ Markov Chains have $N$ states $1,2,...,N$ and are irreducible. Let $P^l=[p_{ij}^l]$ be the transition matrix of Markov chain $X_t^l(l=1,...,m)$, where $$p_{ij}^l=\mathbb{P}\{X_{t+1}^l=j|X_t^l=i\},i,j=1,...,N$$ Please notice that the transition matrix of different Markov chains are different.

Consider the first passage time from state $i$ to state $j$ of Markov chain $X_t^l$ : $$T_{ij}^l=min\{t\geq1,X_t^l=j|X_0^l=i\}$$ Mark the expected value of $\ T_{ij}^l\ $ as $\ m_{ij}^l$, then $\ m_{ij}^l\ $ can be computed by solving the linear system (Hunter J J. The computation of the mean first passage times for Markov chains[J]. Linear Algebra and its Applications, 2018, 549: 100-122.): $$m_{ij}^l=1+\sum_{k\neq j}p_{ik}^lm_{kj}^l$$ Next, let us consider the minimum first passage time of all $m$ Markov chains $X_t^1,X_t^2,...,X_t^m$: $$T_{ij}=min\{T_{ij}^1,T_{ij}^2,...,T_{ij}^m\}$$ My question is, how to compute the expected value of $T_{ij}$?