Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Henry.L
Henry.L
  • 8.1k
  • 8
  • 48
  • 74

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 [6][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.

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 [6]. 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.

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.

Source Link
Henry.L
Henry.L
  • 8.1k
  • 8
  • 48
  • 74

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 [6]. 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.