Order statistic of Markov chain sample path and related probabilities

Question

Consider a one dimensional sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with transition probability matrix $P$, and initial occupation probability vector $p_{0}$. Let $X_{(1)} \leq ... X_{(j)} \leq ... \leq X_{(n)}$ denote the non-descending rearrangement of the sample path. As is well known, $X_{(j)}$ is called the $j$-th order statistic for this sample path of length $n$.

Problem 1. For $i,j\in\{1,...,m\}$, I want to compute the probability mass function (pmf) for $X_{(j)}$, that is, $\mathbb{P}\left(X_{(j)} = i\right)$. This probability for the easier i.i.d. case is well known, see for example p.23, left column top, here. How to do this for the Markov case?

Problem 2. Compute $\mathbb{P}(X(t) = X_{(j)})$.

Using total probability and Bayes rule, the probability for Problem 2 is $\sum_{i=1}^{m}\mathbb{P}(X_{(j)} = i \:|\:X(t) = i) \: \mathbb{P}(X(t)=i)$. The second term in the product can easily be written in terms of $p_{0}, P$ and $t$. But I don't know how to compute the conditional (I tried to think in terms of taboo probabilities with not much luck). Or perhaps there is a better strategy altogether?

Any reference or ideas are welcome. Assume irreducible, aperiodic if that helps.

Answer 1

Problem 1

For a general closed form expression of the joint density of order statistics, it is known intractable:

A problem that is closely related to the first-passage time problem is that of determining information on the length of time between the zeros of a random process. The ultimate goal of such an investigation would be to determine the probability density of the lengths of the intervals between zeros of the process. As this problem has so far proved intractable as far as closed-form expressions are concerned,other associated problems are considered. ... Problems concerning maxima are also considered as they are closely related to certain zero-crossing problems.[1]

Even if you fixed attention to a specific path $\omega$, the corresponding measure of the sample path $m_\omega$ gives you a joint pdf of order statistics as you pointed out, it may not apply to another path $\omega*$ and associated $m_{\omega*}$ because we do not have any useful information to relate $m_{\omega}$ and $m_{\omega*}$. There are some exceptions like Brownian motion with path continuity, but when the state space is discrete (Markov chain), there is no hope to relate probability measures associated with different paths.

Problem 2

A unified approach to the problem of order(actually only maximal) statistics is to consider the Markov renewal process defined in seminal papers [2,3,4]. In this theory, the renewal theory of Markov chains (instead of i.i.d. random variables) are built. The Markov renewal processes are one of the most important examples of semi-markov chains as you pointed out in Stone's paper.

However there are central limit theorem type results (Theorem 7.1 in [3]) and law of large number result in [3] that allows you to compute the counts of renewals. Given a sample path $\omega$, we can compute the distribution of $N(t)$, the number of renewals in the path $\omega$ up to time $t$. As soon as we get access to $N(t)$ we can also compute the distribution of maximas i.e. $\mathbb{P}(X(t) = X_{(n)})$ for a path up to time $n$. The best we can do, even in an ordinary renewal process, is to integrate it out as shown in [5]. The obstacle that prevents us from doing that in this case is that you need to integrate out Markov random variables instead of i.i.d random variables, where ordinary integral does not apply and usually do not have closed form.

Reference

[1]Blake, Ian, and William Lindsey. "Level-crossing problems for random processes." IEEE Transactions on Information Theory 19.3 (1973): 295-315.

[2]Pyke, Ronald. "Markov renewal processes: definitions and preliminary properties." The Annals of Mathematical Statistics (1961): 1231-1242.

[3]Pyke, Ronald. "Markov renewal processes with finitely many states." The Annals of Mathematical Statistics (1961): 1243-1259.

[4]Pyke, Ronald, and Ronald Schaufele. "Limit theorems for Markov renewal processes." The Annals of Mathematical Statistics (1964): 1746-1764.

[5]Gakis, K. G., and B. D. Sivazlian. "Distribution of order statistics of waiting times in an ordinary renewal process and the covariance of the renewal increments." Stochastic Analysis and Applications 11.4 (1993): 441-458.