1

I consider a state space $X$ with a partition $X=\bigcup_{i=0}^n X_i$. Assume we have a transition matrix $P=(p_{x,y})_{x,y\in S}$ which has the structure

$$P=\begin{pmatrix}Q_0 & R_{0,1} & 0 & 0 &... \\ 0 & Q_1 & R_{1,2} & 0 & ... \\ \vdots & 0 & \vdots & \ddots & \\ & & 0 & Q_{n-1} & R_{n-1,n} \\ &&&0 & I_{n} \\ \end{pmatrix}$$

where $Q_i$ is a square matrix of size $|X_i|^2$ and $I_n$ the identity matrix of size $|X_n|^2$. The induced Markov chain $S$ is, consequently absorbing in $X_n$. I want to find a bound for the expected time to absorption. My first attempt was the following because I can assume for some $\alpha\in (0,1)$ that \begin{equation} \sum_{x\in X_i,y\in X_{i+1}}p_{x,y}\geq \alpha |\{x\in X_i,y\in X_{i+1}| p_{x,y} > 0\}|.\qquad\qquad (1) \end{equation} Due to the structure of the transition matrix, $X_{i+1}$ is only accessible from $X_i$. Therefore, the time to absorption $T$ should satisfy $$\mathbb{E}[T|S_0\in X_0]=\sum_{i=0}^{n-1}\mathbb{E}[T_{i,i+1}|S_0\in X_i]$$ where $T_{i,i+1}$ is the time to transition from $X_i$ to $X_{i+1}$. Here I am not quite sure whether I can make the change in the condition from $S_0\in X_0$ to $S_0\in X_i$ but due to the homogenous Markov property this should be possible. Moreover, $T_{i,i+1}=T_{i,i} + 1$ where $T_{i,i}$ is the time spend in $X_i$. Then, $P[T_{i,i}=t]$ is linked to $Q_i^t$ but I run into problems due to the fact that I condition on $S_0\in X_i$ and not $S_0=x$ for some $x\in S_0$ which implies a dependence on the initial distribution by $$\mathbb{E}[T_{i,i+1}|S_0\in X_i]=\sum_{x\in X_i}\mathbb{E}[T_{i,i+1}|S_0= x]\color{red}{P[S_0=x|S_0\in X_i]}.$$ Is there a way that by using $(1)$ and estimates on $Q_i^t$ I can find an upper bound on $\mathbb{E}[T_{i,i+1}|S_0\in X_i]$? Or can I maybe exploit further the block-triangular matrix form?

Jfischer
  • 1,239
  • The issue you're grappling with here, where there is a dependence on where you entered $X_{i+1}$ and thus on where you exited $X_i$, is computationally nontrivial, meaning that you cannot in general get even a good estimate for the expected time using a pure death process method. However it is possible to give an estimate if all the exit probabilities from $X_i$ are all small, so that the distribution of the state from which you exit $X_i$ can be asymptotically independent of the state where you entered $X_i$. – Ian Nov 12 '21 at 10:45
  • I know the number of possible exits fron $X_i$ into $X_{i+1}$ but the transition probabilities might be as large as $1/2$... – Jfischer Nov 12 '21 at 12:39
  • Basically what you have to do in order to exploit this structure is find the joint distribution of the exit time and exit location from $X_0$ and then iterate that process on each block. This obviously gets more complicated once you get to $X_1$ because now even the initial state is random. It is probably less expensive to just solve the global linear system for the expected exit time rather than bothering to exploit this structure in an analytical fashion, at least when the number of blocks and the size of a block are comparable. How big are they in your real application anyway? – Ian Nov 12 '21 at 17:36
  • For some fixed $n$ the state space has size of order $\binom{n^2}{n}$ and block $i$ has size $\binom{k}{i}\binom{n^2-k}{n-i}$ for a fixed positive integer $k$. So, it is not something I can solve via the linear system. Additionally, I only know the lower bound of the transition probas explicitly. The transition probably are given implicitly by a function of all parameters involved, $n,k,i$. – Jfischer Nov 12 '21 at 21:29
  • Uh...without knowing what $n$ is, that doesn't tell me very much about how much it would cost to solve directly. Mainly I want to know the size of the whole state space and the size of the biggest block, which means knowing an actual typical value of $n$. – Ian Nov 12 '21 at 22:49
  • $n$ is the number of blocks and in a real world application probably around $10^9$. – Jfischer Nov 13 '21 at 07:06
  • Uh...this is probably too expensive for anything other than Monte Carlo then. – Ian Nov 13 '21 at 13:05

0 Answers0