I didn't see this topic covered in the prompts.
I know how to find the fundamental matrix, N, of an absorbing transition matrix, P. This has also already been covered a lot in prior posts.
However, I'm having difficulty finding how to treat this when introducing a probability vector, u, for the starting state.
Would it simply be following the usual steps to find N, but using a canonical form of uP?
EDIT: If $u$ is instead a $nxn$ probability matrix, and $N$ is the $nxn$ fundamental matrix with $0$s for all absorbing states, then the Expected Time Until Absorption for each state can be found by $t^{u} = u \times N \times \textbf{1}$.
Typically (without a probability matrix), the Expected Time Until Absorption for each state is found by $t = N \times \textbf{1}$, and the Variance is found by $(2N – I) \times t – t_{sq}$, where $t_{sq}$ is each element of $t$ squared.
In an attempt to adjust the variance to account for the probability matrix $u$, I tried $(2u \times N – I) \times t^{u} – t^{u}_{sq}$. This is evidently not correct since there exists probability matrices $u$ such that $t^{u}_{sq}>(2u \times N – I) \times t^{u}$, leading to a negative variance. What would be the correct way to calculate variance in time until absorption adjusting for a probability matrix?
Best Answer
Regarding your first question, given the expected time $t(x)$ to absorb starting from each state $x$ and the initial probability distribution $u(x)$, the expected time to absorb with this initial probability distribution is $\sum_x u(x) t(x)$. Normally we write distributions as row vectors and functions as column vectors; in this case this can be written as just $ut$. In terms of the fundamental matrix, $t=N \mathbf{1}$ so this is $uN\mathbf{1}$.
Regarding your question about the variance, here is a way to do it from scratch. You have the recursion:
$$E[\tau^2 \mid X_0=x]=\sum_y E[(\tau+1)^2 \mid X_0=y] P[X_1=y \mid X_0=x]$$
which expands to
$$E[\tau^2 \mid X_0=x]=\sum_y E[\tau^2 \mid X_0=y] P[X_1=y \mid X_0=x] + 2 \sum_y E[\tau \mid X_0=y] P[X_1=y \mid X_0=y] + 1.$$
Thus the conditional variance can be obtained as
$$V[\tau^2 \mid X_0=x]=\sum_y E[\tau^2 \mid X_0=y] P[X_1=y \mid X_0=x] + \sum_y E[\tau \mid X_0=y] P[X_1=y \mid X_0=y]$$
for each non-absorbing state $x$. This follows by looking at the recursion for the expectation:
$$E[\tau \mid X_0=x]=1 + \sum_y E[\tau \mid X_0=y] P[X_1=y \mid X_0=y]$$
and subtracting on both sides. In matrix notation you could write the equation for the variance as
$$v(x)=(P(v+t))(x)$$
for each non-absorbing state $x$ and $v(x)=0$ for the absorbing states. You can then again multiply out $uv$ if you have an initial probability distribution $u$.
Regarding your question about computing the variance using the fundamental matrix, I looked into this, and it can be done. But you need to be careful about the grouping. The variance started from each state is given by the column vector
$$(2N-I)t-(t \circ t)$$
where $\circ$ is the Hadamard product. You can multiply that whole column vector by $u$ on the left to get the variance of the absorption time for an initial probability distribution $u$. You do not replace $t$ by $ut$ everywhere in the identity above.