James Evans, Andrzej Korzeniowski
Department of Mathematics, University of Texas at Arlington, Arlington, TX, USA.
DOI: 10.4236/apm.2025.158029   PDF    HTML   XML   104 Downloads   460 Views   Citations

Abstract

We obtain a closed form expression for the joint probability mass function of the occupation times for a Three-State Markov chain. Our representation extends the long-standing result for a Two-State Markov chain by utilizing the method of probability generating functions given in Pedler.

Keywords

Occupation Times, Markov Chains, Probability Generating Functions, Probability Mass Function

Share and Cite:

1. Introduction

The probability mass function of the occupation time for a Markov chain was the subject of intense research during the 50s, 60s, and 70s as seen in the work of Pedler , Darroch [2], Gabriel [3], and Good [4] and has re-emerged as a topic of interest with recent notable work by Shah [5] and Pollett [6]. The aforementioned authors, through various methods, were able to obtain the probability mass function of the occupation time for a Two-State Markov chain. In this paper, we extend the method given by Pedler and provide an explicit closed form expression for the occupation time probability mass function of a Three-State Markov chain. This new expression is the first extension beyond two states and provides much-needed insight in the search for an occupation time formula of an arbitrary M-State Markov chain.

2. Occupation time for a Three-State Markov Chain

Consider a three state time homogeneous Markov chain ${\left(M_k\right)}_{k=0}^n$ with states $E_1,E_2,E_3$ . Define $p_{ij}=P\left[M_k=E_j|M_{k-1}=E_i\right]>0$ to be the probability of transitioning from state $E_i$ to $E_j$ in one step. Since $p_{ij}$ is strictly positive, ${\left(M_k\right)}_{k=0}^n$ is ergodic. Further define $0\le {\pi }_i\le 1$ to be the probability that $M_0=E_i$ where ${\pi }_1+{\pi }_2+{\pi }_3=1$ . Let $X_n={\displaystyle {\sum }_{k=1}^{n}1{\text{l}}_{E_1}}$ , $Y_n={\displaystyle {\sum }_{k=1}^{n}1{\text{l}}_{E_2}}$ , $Z_n={\displaystyle {\sum }_{k=1}^{n}1{\text{l}}_{E_3}}$ be the occupation time of state $E_1,E_2,E_3$ during the interval $\left\{1,\cdots ,n\right\}$ . The initial state not being counted towards the occupation time of any state. Then given $X_n=x,Y_n=y,Z_n=z$ we have $x+y+z=n$ and the joint probability mass function of the occupation times by time n reads $p_n\left(x,y,z\right)=P\left(X_n=x,Y_n=y,Z_n=z\right)=p_n\left(x,y,n-x-y\right)$ .

Theorem 1 The probability mass function of the occupation time for a Three-State Markov chain is given by

$\begin{array}{l}{p}_n\left(x,y,n-x-y\right)\\ =F\left(x,y,n-x-y\right)+\left({\pi }_1{d}_1+{\pi }_3{d}_8\right)F\left(x,y-1,n-x-y\right)\\ +\left({\pi }_1{d}_2+{\pi }_2{d}_5\right)F\left(x,y,n-x-y-1\right)\\ +\left({\pi }_2{d}_4+{\pi }_3{d}_7\right)F\left(x-1,y,n-x-y\right)+{\pi }_3{d}_{9}F\left(x-1,y-1,n-x-y\right)\\ +{\pi }_2{d}_{6}F\left(x-1,y,n-x-y-1\right)+{\pi }_1{d}_{3}F\left(x,y-1,n-x-y-1\right)\end{array}$ (1)

where

$d_1=p_{12}-p_{22}$

$d_2=p_{13}-p_{33}$

$d_3=p_{22}{p}_{33}-p_{23}{p}_{32}+p_{12}{p}_{23}+p_{13}{p}_{32}-p_{12}{p}_{33}-p_{13}{p}_{22}$

$d_4=p_{21}-p_{11}$

$d_5=p_{23}-p_{33}$

$d_6=p_{13}{p}_{21}-p_{11}{p}_{23}-p_{13}{p}_{31}+p_{23}{p}_{31}+p_{11}{p}_{33}-p_{21}{p}_{33}$

$d_7=p_{31}-p_{11}$

$d_8=p_{32}-p_{22}$

$d_9=-p_{12}{p}_{21}+p_{11}{p}_{22}+p_{12}{p}_{31}-p_{22}{p}_{31}-p_{11}{p}_{32}+p_{21}{p}_{32}$

${\lambda }_{st}=\frac{p_{12}{p}_{21}}{p_{11}{p}_{22}};{\lambda }_{su}=\frac{p_{13}{p}_{31}}{p_{11}{p}_{33}};{\lambda }_{tu}=\frac{p_{23}{p}_{32}}{p_{22}{p}_{33}};$

${\lambda }_{stu}=\frac{-p_{13}{p}_{22}{p}_{31}+p_{12}{p}_{23}{p}_{31}+p_{13}{p}_{21}{p}_{32}-p_{11}{p}_{23}{p}_{32}-p_{12}{p}_{21}{p}_{33}}{p_{33}{p}_{22}{p}_{11}}$

$\begin{array}{c}F\left(x,y,z\right)={\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{l=0}^{\infty }\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ l\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)}}}}\\ \ast \left[{\lambda }_{st}^k{\lambda }_{su}^j{\lambda }_{tu}^i{\lambda }_{stu}^{l-k-j-i}{p}_{11}^x{p}_{22}^y{p}_{33}^z\right]\end{array}$

Remark. In fact, as Lemma 2 shows, $F\left(x,y,z\right)$ is the sum of finitely many known terms.

3. Derivation of Three-State Occupation Time Probability Mass Function

The proof of Theorem 1 is based on the following Lemmas:

Lemma 2

$\begin{array}{l}{\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{l=0}^{\infty }\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ l\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)}}}}\\ ={\displaystyle \sum _{k=0}^n{\displaystyle \sum _{j=0}^n{\displaystyle \sum _{i=0}^n{\displaystyle \sum _{l=0}^{\min \left[x+i,y+j,z+k\right]}\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ l\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)}}}}\end{array}$ (2)

Proof of Lemma 2. For occupation times $x,y,z$ , we have $x+y+z=n$ and

recall that for $m\ge 0$ , $k<0$ or $k>m$ implies $\left(\begin{array}{c}m\\ k\end{array}\right)=0$ . Then (2) simplifies to

${\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{l=0}^{\min \left[x+i,y+j,z+k\right]}\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ l\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)}}}}$ (3)

Using $\left(\begin{array}{c}r\\ m\end{array}\right)\left(\begin{array}{c}m\\ c\end{array}\right)=\frac{r!m!}{m!c!\left(r-m\right)!\left(m-c!\right)}=\frac{r!\left(r-c\right)!}{\left(r-c\right)!c!\left(r-c-m+c\right)!\left(m-c\right)!}=\left(\begin{array}{c}r\\ c\end{array}\right)\left(\begin{array}{c}r-c\\ m-c\end{array}\right)$ three times for $\left(\begin{array}{c}r\\ m\end{array}\right)\left(\begin{array}{c}m\\ c\end{array}\right)=\left(\begin{array}{c}z+k\\ l\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)$ , $\left(\begin{array}{c}r\\ m\end{array}\right)\left(\begin{array}{c}m\\ c\end{array}\right)=\left(\begin{array}{c}z\\ l-k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)$ , and $\left(\begin{array}{c}r\\ m\end{array}\right)\left(\begin{array}{c}m\\ c\end{array}\right)=\left(\begin{array}{c}z-j\\ l-k-j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)$ in that specific order, (3) may be written as

${\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{l=0}^{\min \left[x+i,y+j,z+k\right]}\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ k\end{array}\right)\left(\begin{array}{c}z\\ j\end{array}\right)\left(\begin{array}{c}z-j\\ i\end{array}\right)\left(\begin{array}{c}z-j-i\\ l-k-j-i\end{array}\right)}}}}$ (4)

Note that from $\left(\begin{array}{c}z\\ j\end{array}\right)$ , (4) reduces to 0 for $j<0$ or $j>z$ , thus $j$ ranges from

0 to $z$ . However, we may pick an upper bound $m\ge z$ for $j$ without altering the final summation of (4). Then from $0\le j\le z\le x+y+z=n$ , (4) becomes

${\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^n{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{l=0}^{\min \left[x+i,y+j,z+k\right]}\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ k\end{array}\right)\left(\begin{array}{c}z\\ j\end{array}\right)\left(\begin{array}{c}z-j\\ i\end{array}\right)\left(\begin{array}{c}z-j-i\\ l-k-j-i\end{array}\right)}}}}$ (5)

Applying a similar argument for $0\le i\le z-j\le n$ and $0\le k\le l\le x+i\le x+z\le n$ , (5) may be re-written as

${\displaystyle \sum _{k=0}^n{\displaystyle \sum _{j=0}^n{\displaystyle \sum _{i=0}^n{\displaystyle \sum _{l=0}^{\min \left[x+i,y+j,z+k\right]}\left(\begin{array}{c}x+i\\ l\end{array}\right)\left(\begin{array}{c}y+j\\ l\end{array}\right)\left(\begin{array}{c}z+k\\ k\end{array}\right)\left(\begin{array}{c}z\\ j\end{array}\right)\left(\begin{array}{c}z-j\\ i\end{array}\right)\left(\begin{array}{c}z-j-i\\ l-k-j-i\end{array}\right)}}}}$ (6)

Then from the equality of (6) and (2), the index bounds of (6) may be applied to (2) to give us the desired result. □

Lemma 3

$\begin{array}{l}{\displaystyle \sum _{l=0}^{\infty }{\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{\zeta =-k}^{\infty }{\displaystyle \sum _{\gamma =-j}^{\infty }{\displaystyle \sum _{\chi =-i}^{\infty }\left(\begin{array}{c}\chi +i\\ l\end{array}\right)\left(\begin{array}{c}\gamma +j\\ l\end{array}\right)\left(\begin{array}{c}\zeta +k\\ k\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)}}}}}}}\\ \ast \left[{\lambda }_{st}^k{\lambda }_{su}^j{\lambda }_{tu}^i{\lambda }_{stu}^{l-k-j-i}{\sigma }^{\chi }{\tau }^{\gamma }{\upsilon }^{\zeta }\right]\\ ={\displaystyle \sum _{\zeta =-\infty }^{\infty }{\displaystyle \sum _{\gamma =-\infty }^{\infty }{\displaystyle \sum _{\chi =-\infty }^{\infty }F}}}\left(\chi ,\gamma ,\zeta \right){\left(\frac{\sigma }{p_{11}}\right)}^{\chi }{\left(\frac{\tau }{p_{22}}\right)}^{\gamma }{\left(\frac{\upsilon }{p_{33}}\right)}^{\zeta }1{\text{l}}_{\left[\zeta \ge -k\right]}1{\text{l}}_{\left[\gamma \ge -j\right]}1{\text{l}}_{\left[\chi \ge -i\right]}\\ =\frac{1}{\left(1-\sigma \right)\left(1-\tau \right)\left(1-\upsilon \right)-\left({\lambda }_{st}\sigma \tau +{\lambda }_{su}\sigma \upsilon +{\lambda }_{tu}\tau \upsilon +{\lambda }_{stu}\sigma \tau \upsilon \right)}\end{array}$ (7)

where $1{\text{l}}_A$ denotes the indicator function on $A$ .

Proof of Lemma 3. By factoring (7), we obtain

${\left(1-\frac{\left[{\lambda }_{st}\sigma \tau +{\lambda }_{su}\sigma \upsilon +{\lambda }_{tu}\tau \upsilon +{\lambda }_{stu}\sigma \tau \upsilon \right]}{\left[\left(1-\sigma \right)\left(1-\tau \right)\left(1-\upsilon \right)\right]}\right)}^{-1}{\left(\left(1-\sigma \right)\left(1-\tau \right)\left(1-\upsilon \right)\right)}^{-1}$

which can be rewritten using a geometric series as

${\displaystyle \sum }_{l=0}^{\infty }{\left[{\lambda }_{st}\sigma \tau +{\lambda }_{su}\sigma \upsilon +{\lambda }_{tu}\tau \upsilon +{\lambda }_{stu}\sigma \tau \upsilon \right]}^l{\left[\left(1-\sigma \right)\left(1-\tau \right)\left(1-\upsilon \right)\right]}^{-l-1}$

Expand the multinomial and negative binomial(s), write (7) as

$\begin{array}{l}{\displaystyle \sum _{l=0}^{\infty }\left[{\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right){\lambda }_{st}^k{\lambda }_{su}^j{\lambda }_{tu}^i{\lambda }_{stu}^{l-k-j-i}{\sigma }^{l-i}{\tau }^{l-j}{\upsilon }^{l-k}}}}\right]}\\ \ast \left[{\displaystyle \sum _{\zeta =0}^{\infty }{\displaystyle \sum _{\gamma =0}^{\infty }{\displaystyle \sum _{\chi =0}^{\infty }\left(\begin{array}{c}l+\chi \\ \chi \end{array}\right)\left(\begin{array}{c}l+\gamma \\ \gamma \end{array}\right)\left(\begin{array}{c}l+\zeta \\ \zeta \end{array}\right){\sigma }^{\chi }{\tau }^{\gamma }{\upsilon }^{\zeta }}}}\right]\end{array}$ (8)

and apply the product of series convolution formula

${\displaystyle {\sum }_{q=0}^{\infty }{\displaystyle {\sum }_{r=0}^{\infty }{a}_q{b}_r}}=\left({\displaystyle {\sum }_{q=0}^{\infty }{a}_q}\right)\left({\displaystyle {\sum }_{r=0}^{\infty }{b}_r}\right)={\displaystyle {\sum }_{r=0}^{\infty }{\displaystyle {\sum }_{q=0}^r{a}_q{b}_{r-q}}}$ to (8) three times for

$r=\chi ,r=\gamma ,r=\zeta$ and $q=l$ to obtain

$\begin{array}{l}{\displaystyle \sum _{l=0}^{\infty }\left[{\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right){\lambda }_{st}^k{\lambda }_{su}^j{\lambda }_{tu}^i{\lambda }_{stu}^{l-k-j-i}{\sigma }^{l-i}{\tau }^{l-j}{\upsilon }^{l-k}}}}\right]}\\ \ast \left[{\displaystyle \sum _{\zeta =0}^{\infty }{\displaystyle \sum _{\gamma =0}^{\infty }{\displaystyle \sum _{\chi =0}^{\infty }\left(\begin{array}{c}\chi \\ l\end{array}\right)\left(\begin{array}{c}\gamma \\ l\end{array}\right)\left(\begin{array}{c}\zeta \\ l\end{array}\right){\sigma }^{\chi -l}{\tau }^{\gamma -l}{\upsilon }^{\zeta -l}}}}\right]\end{array}$ (9)

Substituting $\chi ,\gamma ,\zeta$ with $\chi +i,\gamma +j,\zeta +k$ respectively, (9) becomes

$\begin{array}{l}{\displaystyle \sum _{l=0}^{\infty }{\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{\zeta =-k}^{\infty }{\displaystyle \sum _{\gamma =-j}^{\infty }{\displaystyle \sum _{\chi =-i}^{\infty }\left(\begin{array}{c}\chi +i\\ l\end{array}\right)\left(\begin{array}{c}\gamma +j\\ l\end{array}\right)\left(\begin{array}{c}\zeta +k\\ k\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)\left(\begin{array}{c}l-k-j\\ i\end{array}\right)}}}}}}}\\ \ast \left[{\lambda }_{st}^k{\lambda }_{su}^j{\lambda }_{tu}^i{\lambda }_{stu}^{l-k-j-i}{\sigma }^{\chi }{\tau }^{\gamma }{\upsilon }^{\zeta }\right]\\ ={\displaystyle \sum _{\zeta =-\infty }^{\infty }{\displaystyle \sum _{\gamma =-\infty }^{\infty }{\displaystyle \sum _{\chi =-\infty }^{\infty }{\displaystyle \sum _{k=0}^{\infty }{\displaystyle \sum _{j=0}^{\infty }{\displaystyle \sum _{i=0}^{\infty }{\displaystyle \sum _{l=0}^{\infty }\left(\begin{array}{c}\chi +i\\ l\end{array}\right)\left(\begin{array}{c}\gamma +j\\ l\end{array}\right)\left(\begin{array}{c}\zeta +k\\ k\end{array}\right)\left(\begin{array}{c}l\\ k\end{array}\right)\left(\begin{array}{c}l-k\\ j\end{array}\right)}}}}}}}\\ \ast \left[\left(\begin{array}{c}l-k-j\\ i\end{array}\right){\lambda }_{st}^k{\lambda }_{su}^j{\lambda }_{tu}^i{\lambda }_{stu}^{l-k-j-i}{\sigma }^{\chi }{\tau }^{\gamma }{\upsilon }^{\zeta }1{\text{l}}_{\left[\zeta \ge -k\right]}1{\text{l}}_{\left[\gamma \ge -j\right]}1{\text{l}}_{\left[\chi \ge -i\right]}\right]\\ ={\displaystyle \sum _{\zeta =-\infty }^{\infty }{\displaystyle \sum _{\gamma =-\infty }^{\infty }{\displaystyle \sum _{\chi =-\infty }^{\infty }F}}}\left(\chi ,\gamma ,\zeta \right){\left(\frac{\sigma }{p_{11}}\right)}^{\chi }{\left(\frac{\tau }{p_{22}}\right)}^{\gamma }{\left(\frac{\upsilon }{p_{33}}\right)}^{\zeta }1{\text{l}}_{\left[\zeta \ge -k\right]}1{\text{l}}_{\left[\gamma \ge -j\right]}1{\text{l}}_{\left[\chi \ge -i\right]}\end{array}$

which completes the proof of Lemma 3. □

Proof of Theorem 1. Given Markov chain ${\left(M_k\right)}_{k=0}^n$ we define $\Pi$ to be the initial distribution of states $E_1,E_2,E_3$ at time 0. Set

$P\left(s,t,u\right)=\left[\begin{array}{lll}s{p}_{11}\hfill & t{p}_{12}\hfill & u{p}_{13}\hfill \\ s{p}_{21}\hfill & t{p}_{22}\hfill & u{p}_{23}\hfill \\ s{p}_{31}\hfill & t{p}_{32}\hfill & u{p}_{33}\hfill \end{array}\right],\Pi =\left[\begin{array}{ccc}{\pi }_1& {\pi }_2& {\pi }_3\end{array}\right],1=\left[\begin{array}{l}1\hfill \\ 1\hfill \\ 1\hfill \end{array}\right]$

and notice that $P\left(1,1,1\right)$ is the one-step transition probability matrix. The probability generating function of $p_n\left(x,y,z\right)$ is given by

$G_n\left(s,t,u\right)={\displaystyle \sum _{z=0}^{\infty }{\displaystyle \sum _{y=0}^{\infty }{\displaystyle \sum _{x=0}^{\infty }{s}^x{t}^y{u}^z{p}_n\left(x,y,z\right)}}}n\ge 0$ (10)

and we define $p_0\left(0,0,0\right)=P\left(X_0=0,Y_0=0,Z_0=0\right)=G_0\left(s,t,u\right)=1$ . Since $z=n-x-y$ , $0\le x\le n-y$ , and $0\le y\le n$ , (10) simplifies to

$G_n\left(s,t,u\right)={\displaystyle \sum _{y=0}^n{\displaystyle \sum _{x=0}^{n-y}{s}^x{t}^y{u}^z{p}_n\left(x,y,z\right)}}$ (11)

Since the spectral radius of $P\left(1,1,1\right)$ is exactly 1, restricting $s,t,u$ between 0 and 1 allows us to sum (11) over $n$ to obtain

$\begin{array}{c}{\displaystyle \sum _{n=0}^{\infty }{G}_n\left(s,t,u\right)}={\displaystyle \sum _{n=0}^{\infty }{\displaystyle \sum _{y=0}^n{\displaystyle \sum _{x=0}^{n-y}{s}^x{t}^y{u}^z{p}_n\left(x,y,z\right)}}}={\displaystyle \sum _{n=0}^{\infty }\Pi P{\left(s,t,u\right)}^{n}1}\\ =\Pi {\left[I-P\left(s,t,u\right)\right]}^{-1}1\end{array}$

which is equal to

$\frac{{\pi }_1\left(d_{1}t+d_{2}u+d_{3}tu\right)+{\pi }_2\left(d_{4}s+d_{5}u+d_{6}su\right)+{\pi }_3\left(d_{7}s+d_{8}t+d_{9}st\right)}{\left(1-\sigma \right)\left(1-\tau \right)\left(1-\upsilon \right)-\left({\lambda }_{st}\sigma \tau +{\lambda }_{su}\sigma \upsilon +{\lambda }_{tu}\tau \upsilon +{\lambda }_{stu}\sigma \tau \upsilon \right)}$ (12)

where $\sigma =s{p}_{11},\tau =t{p}_{22},\upsilon =u{p}_{33}$ . Defining the numerator of (12) as $N$ and applying Lemma 3 to (12), we have

${\displaystyle \sum _{\zeta =-\infty }^{\infty }{\displaystyle \sum _{\gamma =-\infty }^{\infty }{\displaystyle \sum _{\chi =-\infty }^{\infty }N\ast F\left(\chi ,\gamma ,\zeta \right)s^{\chi }{t}^{\gamma }{u}^{\zeta }1{\text{l}}_{\left[\zeta \ge -k\right]}1{\text{l}}_{\left[\gamma \ge -j\right]}1{\text{l}}_{\left[\chi \ge -i\right]}}}}$ (13)

Now note that for a given $n$ , if $z\ne n-x-y$ then $p_n\left(x,y,z\right)=0$ and (11) reduces to 0. Then from the equality of (11) and (13), (13) must also be 0 and simplifies to

${\displaystyle \sum _{\gamma =-\infty }^{\infty }{\displaystyle \sum _{\chi =-\infty }^{\infty }N\ast F\left(\chi ,\gamma ,\zeta \right)s^{\chi }{t}^{\gamma }{u}^{\zeta }1{\text{l}}_{\left[\gamma \ge -j\right]}1{\text{l}}_{\left[\chi \ge -i\right]}}}$ (14)

for $\zeta =n-x-y$ . Further note that if $x<0$ or $x>n-y$ , then $p_n\left(x,y,z\right)=0$ and using a similar argument for $y$ , (14) becomes

${\displaystyle \sum _{\gamma =0}^n{\displaystyle \sum _{\chi =0}^{n-\gamma }N\ast F\left(\chi ,\gamma ,\zeta \right)s^{\chi }{t}^{\gamma }{u}^{\zeta }}}$ (15)

Since (15) is another representation of (11), they are equal.

${\displaystyle \sum _{y=0}^n{\displaystyle \sum _{x=0}^{n-y}{p}_n\left(x,y,z\right)s^x{t}^y{u}^z}}={\displaystyle \sum _{\gamma =0}^n{\displaystyle \sum _{\chi =0}^{n-\gamma }N\ast F\left(\chi ,\gamma ,\zeta \right)s^{\chi }{t}^{\gamma }{u}^{\zeta }}}$

The above shows $p_n\left(x,y,z\right)=N\ast F\left(\chi ,\gamma ,\zeta \right)$ hence by applying (12) gives

$\begin{array}{c}{p}_n\left(x,y,z\right)=F\left(\chi ,\gamma ,\zeta \right)+t\left({\pi }_1{d}_1+{\pi }_3{d}_8\right)F\left(\chi ,\gamma ,\zeta \right)\\ +u\left({\pi }_1{d}_2+{\pi }_2{d}_5\right)F\left(\chi ,\gamma ,\zeta \right)+s\left({\pi }_2{d}_4+{\pi }_3{d}_7\right)F\left(\chi ,\gamma ,\zeta \right)\\ +st{\pi }_3{d}_{9}F\left(\chi ,\gamma ,\zeta \right)+su{\pi }_2{d}_{6}F\left(\chi ,\gamma ,\zeta \right)+tu{\pi }_1{d}_{3}F\left(\chi ,\gamma ,\zeta \right)\end{array}$ (16)

Finally, substituting the power of $s,t,u$ with $x,y,z$ in each individual summand in (16) and then setting $s,t,u=1$ gives (1) as claimed. □

4. Illustrative Example

Consider one-step transition probability matrix and initial distribution as follows

$P=\left[\begin{array}{ccc}\frac{1}{2}& \frac{1}{8}& \frac{3}{8}\\ \frac{1}{5}& \frac{12}{25}& \frac{8}{25}\\ \frac{3}{10}& \frac{6}{10}& \frac{1}{10}\end{array}\right],\Pi =\left[\begin{array}{ccc}\frac{1}{2}& \frac{1}{4}& \frac{1}{4}\end{array}\right]$

The occupation time probabilities for $n=5$ were calculated by Wolfram Mathematica implementation of (1). Furthermore, 10⁷ Monte Carlo paths of the Markov chain during times $\left\{0,1,\cdots ,5\right\}$ were simulated using C++, and the proportion of paths satisfying $x,y\in \left\{0,1,\cdots ,5\right\}$ were computed. The results are given in Table 1 and Table 2. Note that using the exact probabilities from Table 2 gives

${\displaystyle \sum _{y=0}^5{\displaystyle \sum _{x=0}^{5-y}p}}\left(x,y,5-x-y\right)=1$

Table 1. Comparison of (1) with a path simulation.

$p_5\left(x,y,5-x-y\right)$	x = 0	x = 1	x = 2	x = 3	x = 4	x = 5
y = 0	0.00002925	0.00121556	0.0136948	0.0485930	0.0601875	0.0234375
y = 1	0.0019667	0.03310590	0.1049150	0.0925238	0.0212031	0
y = 2	0.0289906	0.12225600	0.1058140	0.0232519	0	0
y = 3	0.0897800	0.09565950	0.0221396	0	0	0
y = 4	0.0753021	0.01828400	0	0	0	0
y = 5	0.0176505	0	0	0	0	0
Path Simulation	x = 0	x = 1	x = 2	x = 3	x = 4	x = 5
y = 0	0.0000289	0.0012255	0.0136814	0.0486363	0.0601069	0.0234127
y = 1	0.0019584	0.0331114	0.1049500	0.0922447	0.0212642	0
y = 2	0.0289699	0.1222960	0.1059210	0.0232506	0	0
y = 3	0.0897527	0.0956537	0.0221802	0	0	0
y = 4	0.0752589	0.0182716	0	0	0	0
y = 5	0.0176218	0	0	0	0	0

Table 2. Exact values obtained by (1).

$p_5\left(x,y,5-x-y\right)$	x = 0	x = 1	x = 2	x = 3	x = 4	x = 5
y = 0	$\frac{117}{4000000}$	$\frac{19449}{16000000}$	$\frac{175293}{12800000}$	$\frac{62199}{1280000}$	$\frac{963}{16000}$	$\frac{3}{128}$
y = 1	$\frac{19667}{10000000}$	$\frac{2648469}{80000000}$	$\frac{6714561}{64000000}$	$\frac{74019}{800000}$	$\frac{1357}{64000}$	0
y = 2	$\frac{181191}{6250000}$	$\frac{764099}{6250000}$	$\frac{8465129}{80000000}$	$\frac{37203}{1600000}$	0	0
y = 3	$\frac{350703}{3906250}$	$\frac{2989359}{31250000}$	$\frac{1771169}{80000000}$	0	0	0
y = 4	$\frac{735372}{9765625}$	$\frac{285687}{15625000}$	0	0	0	0
y = 5	$\frac{172368}{9765625}$	0	0	0	0	0

5. Discussion

We would like to point out that in principle the method given in Pedler [1] could be extended to any finite-state Markov chain provided tractability of the large number of terms involved, however to the best of our knowledge no such result appears in existing literature. The derivation would be analogous to the proof of Theorem 1. Granted, Gabriel [3] and Shah [5] present a method that enumerates transition paths which is straightforward in the Two-State case, but becomes increasingly involved as the number of states grows. On the other hand, Pollett [6], Sericola [7], and Darroch [8] employ methods that could extend to any finite state Markov chain, but depend on an often unknown transition matrix between subsets of states. In contrast, Pedler’s method is conceptually straightforward, as it relies on rudimentary level identities and algebraic manipulations to obtain the key result.

Acknowledgements

The authors would like to thank the reviewers for their valuable suggestions that considerably improved the presentation of our findings in the revised version of the manuscript.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Pedler, P.J. (1971) Occupation Times for Two State Markov Chains. Journal of Applied Probability, 8, 381-390.[CrossRef]
[2]	Darroch, J.N. and Morris, K.W. (1968) Passage-Time Generating Functions for Continuous-Time Finite Markov Chains. Journal of Applied Probability, 5, 414-426.[CrossRef]
[3]	Gabriel, K.R. (1959) The Distribution of the Number of Successes in a Sequence of Dependent Trials. Biometrika, 46, 454-460.[CrossRef]
[4]	Good, I.J. (1961) The Frequency Count of a Markov Chain and the Transition to Continuous Time. The Annals of Mathematical Statistics, 32, 41-48.[CrossRef]
[5]	Shah, M.T. (2025) A Note on Exact State Visit Probabilities in Two-State Markov Chains. arXiv:2502.03073.
[6]	Pollett, P. (2025) A Note on the State Occupancy Distribution for Markov Chains. arXiv:2503.17647.
[7]	Sericola, B. (2000) Occupation Times in Markov Processes. Communications in Statistics. Stochastic Models, 16, 479-510.[CrossRef]
[8]	Darroch, J.N. and Morris, K.W. (1967) Some Passage-Time Generating Functions for Discrete-Time and Continuous-Time Finite Markov Chains. Journal of Applied Probability, 4, 496-507.[CrossRef]