Moments of passage time in repeating part

Matrix $\mathbf{G}$ can be derived by the algorithm in Figure 3.12, but it is instructive to study an alternative derivation of $\mathbf{G}$. The idea is to simply iterate the following equation until it converges:

$$\mathbf{G} = \mbox{\boldmath {${\cal B}$}} + \mbox{\boldmat... ...thbf{G} + \mbox{\boldmath {${\cal F}$}} \mathbf{G}\mathbf{G}$$ (3.7)

The intuition behind Equation (3.7) should be clear: Recall that the $(i,j)$ entry of $\mathbf{G}^{(\ell)}$ represents the probability that state $(j,\ell-1)$ is the first state reached in level $\ell-1$, given that we start in state $(i,\ell)$. Now the right hand side of Equation (3.7) represents this same probability by conditioning on whether the first move is a backward transition, a local transition, or a forward transition. Specifically, the $(i,j)$ element of $\mbox{\boldmath {${\cal B}$}}^{(\ell)}$ represents the probability that the first move leaving state $(i,\ell)$ is to state $(j,\ell-1)$. The $(i,j)$ element of $\mbox{\boldmath {${\cal L}$}}^{(\ell)} \mathbf{G}^{(\ell)}$ represents the probability that the first transition out of state $(i,\ell)$ is to state $(v, \ell)$ for some $v$ multiplied by the probability that the the first state reached in level $\ell-1$ is $(j,\ell-1)$ when we start in state $(v, \ell)$, summed over all possible $v = 1, \ldots, n_\ell$. Finally, the $(i,j)$ element of $\mbox{\boldmath {${\cal F}$}}^{(\ell)} \mathbf{G}^{(\ell+1)} \mathbf{G}^{(\ell)}$ represents the product of three terms: (i) the probability that the first transition from $(i,\ell)$ is to some state $(v_1, \ell + 1)$ in level $\ell+1$, (ii) the probability that from state $(v_1, \ell + 1)$ the first state reached in level $\ell$ is some $(v_2, \ell)$, and (iii) the probability that from state $(v_2, \ell)$ the first state reached in level $\ell-1$ is state $(j,\ell-1)$, where the product is summed over all possible $v_1 = 1, \ldots, n_{\ell + 1}$ and $v_2 = 1, \ldots, n_{\ell}$. Since we are in the repeating region, all the superscripts are equal to $\hat{\ell}$, and can be dropped by our notation.

Matrices $\mathbf{G}_r$ for $r=1,2,3$ are derived in a similar manner, by using $\mathbf{G}$ which we have already derived. Matrix $\mathbf{G}_1$ is obtained by iterating:

$$\mathbf{G}_1 = \mbox{\boldmath {${\cal B}$}}_1 + \mbox{\bol... ...bf{G} + \mbox{\boldmath {${\cal F}$}} \mathbf{G} \mathbf{G}_1.$$ (3.8)

Similarly, matrix $\mathbf{G}_2$ is obtained by iterating:

$$\mathbf{G}_2 = \mbox{\boldmath {${\cal B}$}}_2 + \mbox{\boldmath {${\cal L}$}}_2... ...dmath {${\cal L}$}}_1 \mathbf{G}_1 + \mbox{\boldmath {${\cal L}$}} \mathbf{G}_2$$

$$+ \mbox{\boldmath {${\cal F}$}}_2 \mathbf{G} \mathbf{G} + 2\mbox{... ...\mathbf{G}_2 \mathbf{G} + 2\mathbf{G}_1 \mathbf{G}_1 + \mathbf{G} \mathbf{G}_2)$$ (3.9)

and matrix $\mathbf{G}_3$ is obtained by iterating:

$$\mathbf{G}_3 = \mbox{\boldmath {${\cal B}$}}_3 + \mbox{\boldmath {${\cal L}$}}_3... ...dmath {${\cal L}$}}_1 \mathbf{G}_2 + \mbox{\boldmath {${\cal L}$}} \mathbf{G}_3$$

$$+ \mbox{\boldmath {${\cal F}$}}_3 \mathbf{G} \mathbf{G} + 3\mbox{... ...\mathbf{G}_2 \mathbf{G} + 2\mathbf{G}_1 \mathbf{G}_1 + \mathbf{G} \mathbf{G}_2)$$

$$\quad + \mbox{\boldmath${\cal F}$} (\mathbf{G}_3 \mathbf{G} + 3\mathbf{G}_2 \mathbf{G}_1 + 3\mathbf{G}_1 \mathbf{G}_2 + \mathbf{G} \mathbf{G}_3).$$ (3.10)

We now give intuition behind expressions (3.8)-(3.10). The right hand side of (3.8) can be divided into three parts: Part 0: $\mbox{\boldmath {${\cal B}$}}_1$, Part 1: $\mbox{\boldmath {${\cal L}$}}_1 \mathbf{G} + \mbox{{\boldmath {${\cal L}$}}} \mathbf{G}_1$, and Part 2: $\mbox{\boldmath {${\cal F}$}}_1 \mathbf{G} \mathbf{G} + \mbox{{\boldmath {${\ca... ...\mathbf{G}_1 \mathbf{G} + \mbox{\boldmath {${\cal F}$}} \mathbf{G} \mathbf{G}_1$. The $(i,j)$ element of Part $h$ gives ``the first moment of the distribution of $T_{i,j}^{(\ell)}$ given that the first transition out of state $(i,\ell)$ is to level $\ell+h-1$ and event $E_{i,j}^{(\ell)}$'' multiplied by ``the probability that the first transition out of state $(i,\ell)$ is to level $\ell+h-1$ and event $E_{i,j}^{(\ell)}$'' for $h=0,1,2$. Part 1 consists of two terms. The first term, $\mbox{{\boldmath {${\cal L}$}}}_1 \mathbf{G}$, is the contribution of the time to the first transition, and the second term, $\mbox{{\boldmath {${\cal L}$}}} \mathbf{G}_1$, is the contribution of the time it takes to reach $(j,\ell-1)$ after the first transition. Similarly, Part 2 consists of three terms. The first term, $\mbox{{\boldmath {${\cal F}$}}}_1 \mathbf{G} \mathbf{G}$, is the contribution of the time to the first transition, the second term, $\mbox{{\boldmath {${\cal F}$}}} \mathbf{G}_1 \mathbf{G}$, is the contribution of the time it takes to come back from level $\ell+1$ to level $\ell$ after the first transition, and the third term, $\mbox{{\boldmath {${\cal F}$}}} \mathbf{G} \mathbf{G}_1$, is the contribution of the time it takes to go from level $\ell$ to level $\ell-1$.

The right hand sides of (3.9) and (3.10) can similarly be divided into three parts: Part 0 consists of terms containing $\mbox{\boldmath {${\cal B}$}}$ or $\mbox{\boldmath {${\cal B}$}}_{r}$; Part 1 consists of terms containing ${\cal L}$ or $\mbox{{\boldmath {${\cal L}$}}}_{r}$; Part 2 consists of terms containing ${\cal F}$ or $\mbox{\boldmath {${\cal F}$}}_{r}$. The three parts of (3.9) and (3.10) can be interpreted exactly the same way as the three parts of (3.8) except that ``the first moment'' in (3.8) must be replaced by ``the second moment'' and ``the third moment'' in (3.9) and (3.10), respectively. For example, the three terms in Part 1 of (3.9) can be interpreted as follows. Let $X$ be the time to the first transition and let $Y$ be the time it takes from level $\ell$ to level $\ell-1$. Then, the second moment of the distribution of these two times is

$$E[(X+Y)^2] = E[(X)^2] + 2E[X]E[Y] + E[(Y)^2],$$

since $X$ and $Y$ are independent. Roughly speaking, $\mbox{\boldmath {${\cal L}$}}_2 \mathbf{G}$ corresponds to $E[(X)^2]$, $2\mbox{\boldmath {${\cal L}$}}_1 \mathbf{G}_1$ corresponds to $2E[X]E[Y]$, and $\mbox{{\boldmath {${\cal L}$}}} \mathbf{G}_2$ corresponds to $E[(Y)^2]$. The other terms can be interpreted in the same way.