A Model of Distributed Disorders Detection

In this paper the construction of the mathematical model of the phenomenon described above requires the determination of a probabilistic space in which all random quantities, random variables and stochastic processes, are defined. Let $(\Omega,{\mathcal{F}},{\bf P}(\cdot))$ be fixed probability space. The consideration will focus on the renewal-reward model of change points detection. A renewal–reward process is a jump process with a general holding time distributions and general distribution of jumps (see Brémaud [Brémaud(1981)], Jacobsen [Jacobsen(2006)]). Let us denote $\{W_{i}\}_{i=1}^{\infty}$ a sequence of iid rv (rewards) with the finite expected value. The random variable $Y_{t}=\sum_{i=1}^{X_{t}}W_{i}$, where $X_{t}$ is the renewal process, is called a renewal-reward process. On the turn, a renewal process is a pure jump process with a general distribution of the holding times. To describe this type of processes, let us consider a sequence of positive iid rv $\{S_{i}\}_{i=1}^{\infty}$ with the finite and positive expectation. The renewal process $X_{t}=\sum^{\infty}_{n=1}\mathbb{I}_{\{J_{n}\leq t\}}=\sup\left\{\,n:J_{n}\leq t\,\right\}$, where $J_{n}=\sum_{i=1}^{n}S_{i}$ for each $n>0$. The mentioned changes of distributions are assumed to appear on the sequences $\{S_{i}\}_{i=1}^{\infty}$ and $\{W_{i}\}_{i=1}^{\infty}$ at some random moments $\theta_{1}$ and $\theta_{2}$, respectively. The general detectors of disorders take values at $\Re^{+}$. In this approach the class of decision function will be restricted to the event (the jump) moments. This means that the moments of the decision can be identified with the index jumping moments in the process. The underlined models can be represented as the sequences of random vectors $\{(S_{n},W_{n})\}_{n=1}^{\infty}$. The r.v. $W_{n}$ and $S_{n}$ do not need to be necessarily independent in contrast to the classical theory of the renewal–reward processes. The aim of the research is to formulate the rigorous model of the problem and to investigate them.

The motivation for the project is the wide literature related to the optimal stopping problem and the scarce results for the multiple stopping settings. The related questions for the change point models are also stimulating. There is satisfactory literature describing the state of art in the disorder problem or the change-point problems in the off-line and on–line setting. Let us mention the monograph by Brodsky and Darkhovsky [Brodsky and Darkhovsky(1993)] and the story by Shiryaev [Shiryaev(2006)].

The disorder problem has a long history (see Shiryaev [Shiryaev(2006)], Proceedings of AMS-IMS-SIAM Summer Research Conference on ”Change point problems” E. Carlstein et al. (ed) [Carlstein et al.(1994)Carlstein, Múller, and Siegmund]). It is known from the early papers by Page [Page(1954), Page(1955)], Girshick and Rubin [Girshick and Rubin(1952)]. However, it was A.N. Kolmogorow who had formulated the realistic and mathematically precise model of rapid detection of a change point or disorder. His student, A.N. Shiryaev [Shiryaev(1961), Shiryaev(1963)] (see the history described in [Shiryaev(2006)]) published the first important results for the sequential problems of disorder detection in the Poisson distribution. This direction of research is the subject of intensive work of contemporary projects. Let us mention papers by Gal’chuk and Rozowski [Gal^′čuk and Rozovskiĭ(1971)], Davis [Davis(1974)], Peskir and Shiryaev [Peskir and Shiryaev(2002)] (see also Gapeev [Gapeev(2005)], Bayraktar, Dayanik and Karatzas [Bayraktar and Dayanik(2006)]. The manifold experiment to formulate the adequate model of disorder for more complex processes which appear in the observed phenomena of nature and economy, showed extreme difficulties (see Fuh [Fuh(2004)], Ivanoff and Merzbach [Ivanoff and Merzbach(2010)], Szajowski [Szajowski(2011)]).

The work continues to carry out research described in the papers published by Sarnowski and the author [Sarnowski and Szajowski(2008)], [Sarnowski and Szajowski(2011)] on the change point problem for the undefined, the Markovian type processes before and after the disorder. Related results can be found in the papers by Bojdecki i Hosza [Bojdecki and Hosza(1984)], Szajowski [Szajowski(1992)], Yoshida [Yoshida(1983)], Yakir [Yakir(1994)] and Moustakides [Moustakides(1998)]. The most important guidelines for considering the results of this work are contained in the authors’ works [Szajowski(2011)] on multivariate disorders detection.

The key technique used in the work is based on a multiple optimal stopping a Markov process. The fundamental knowledge on the optimal stopping of random processes can be found in the monographies by Chow, Robbins and Siegmund [Chow et al.(1971)Chow, Robbins, and Siegmund], [Shiryaev(2008)] or Peskir and Shiryaev [Peskir and Shiryaev(2006)]. The first work devoted to the multiple stopping of the discrete time sequences processes was published by Haggstroma [Haggstrom(1967)] and for the Markov processes Nikolaev [Nikolaev(1981)] (see also Eidukjavicjus [Eidukjavicjus(1979)], Nikolaev[Nikolaev(1998)]). The extension of the model to semi-Markov processes has been made by Stadje [Stadje(1985)]. Recent results for continuous time processes have been presented by Kobylanski, Quenez and Rouy-Mironescu [Kobylanski et al.(2010)Kobylanski, Quenez, and Rouy-Mironescu]) and the various applications of such an approach are described in papers by Feng and Xiao [Feng and Xiao(2000b)], [Feng and Xiao(2000a)], Karpowicz and Szajowski [Karpowicz and Szajowski(2007a), Karpowicz and Szajowski(2012)]. For the risk process such extension can be found in papers by Karpowicz and Szajowski [Karpowicz and Szajowski(2007b)]. However, in the approach applied here there is no need to refer to the results for the semi-Markov processes. The analytical difficulties for such problems open various questions concerning the construction of algorithms, approximate solutions and Monte Carlo methods.

A general formulation starts from a random sequences $\{S_{i}\}_{i=1}^{\infty}$ and $\{W_{i}\}_{i=1}^{\infty}$ having segments that are the homogeneous Markov sequences. Each segment has its own transition probability law and the length of the segment is unknown and random. It means that there are random moments $\theta_{1}$ and $\theta_{2}$, at which the source of observations is changed. The transition probabilities of each process at the segment are chosen from a given set of distributions. An a priori distributions of the disorder moments are given. The problem is to construct the detection algorithm of the disorders. The algorithm should detect the change points with the given precision and maximal probability.

To be more precise, let us see examples. It is easy to ascertain that in the renewal–reward process the distribution of holding time can be first changed in the moment $\theta_{1}$, and next, in the moment $\theta_{2}\geq\theta_{1}$ the distribution of the random variables $W_{n}$ changes. One can formulate three such problems:

• •

  it is known that $\theta_{1}<\theta_{2}$, ie holding time has the distribution change moment earlier than the rewards distribution;

• •

  the order of change points is different: the first the reward sequences are disordered;

• •

  there is no information which sequences will change distribution as the first.

In Bayesian model the last case needs additional a priori information about the chance that the disorder of rewards will appear before the holding time disorder.

If the process is a model of signals from the distributed sources then the disorders in different sources are combined to construct the final decision about the reason of non-homogeneous behavior of the process. Based on the idea of a simple game the model of the fusion center is proposed. The strategy of detection at each segment (source) of the process is defined as the equilibrium in a non-cooperative game between the selfish sensors (see [Szajowski(2011)]).

For the single process having structure similar to those of the generalized compound Poisson processes the temporal disorder is possible. It is a natural problem, mentioned by researchers (see [Bayraktar and Poor(2007)], [Yoshida(1983)] and others). When the model of the process is equivalent to the sequence of a vector of random variables, it is possible that each coordinate changes their distribution in some moments which could be different at each coordinate.

Our environment is described by the states of nature and they are viable over time. There are no objective boundaries in the state space defining safe or unsafe world. These borders are marked by a subjective knowledge. After the appointment of the task of maintaining a safe environment the aim is to observe and monitor the states in time to know their relation to the boundaries. Methodology presented in the paper allows to prepare the environment description and the detectors of the borders of the areas. For the illustration of a description it was selected variant environment in which states form the renewal–reward process. Areas of the state space, acceptable or not, describe the observed distributions of the process. Acceptable states of the system have a distribution, and unacceptable otherwise. Due to the multi-dimensional character of the process the specified areas are determined by the boundaries of the components of the state vector. The model is analysed and the boundaries are determine for the areas of warning states. To determine the boundaries of the detector indicates that to have the correct detection it is necessary a priori knowledge of the possible scenarios achieve a state of emergency. Efficient detection of threats is only possible if the nature implements provided by our scenario. Strategy to little knowledge about the possible scenario is far less effective and it is much more cumbersome to implement.

For any $D_{n}=\{\omega:X_{i}\in B_{i},\;i=1,\ldots,n\}$, where $B_{i}\in{\mathcal{B}}$, and any $x\in\mathbb{E}$ define

Let ${\mathcal{S}}$ be the set of all stopping times with respect to $({\mathcal{F}}_{n})$, $n=0,1,\ldots$ and ${\mathcal{T}}=\{(\tau,\sigma):\tau\leq\sigma,\ \tau,\sigma\in{\mathcal{S}}\}$.

The aim of the DM is to indicate the moments of switching with given precision $d_{1},d_{2}$ (Problem $\mbox{D}_{d_{1}d_{2}}$). We want to determine a pair of stopping times $(\tau^{*},\sigma^{*})\in{\mathcal{T}}$ such that for every $x\in\mathbb{E}$

The problem with the fixed transition distributions at each segment has been formulated in [Szajowski(1996)] and has been extended to the case $0\leq\theta_{1}\leq\theta_{2}$ in [Szajowski(2011)]. The investigated models here assume that between $\theta_{1}$ and $\theta_{2}$, the distribution is chosen from a given set (for simplification having two elements only). The distribution is predetermined in two models and chosen randomly in one model.

Let us introduce the following notation:

where the convention $\prod_{i=j_{1}}^{j_{2}}x_{i}=1$ for $j_{1}>j_{2}$ is used.

Let $B_{i}\in{{\mathcal{B}}}$, $m\leq i\leq n$ and let us assume that $X_{0}=x$ and denote $\underline{D}_{m,n}=\{\omega:X_{i}(\omega)\in A_{i},m\leq i\leq n\}$. For $D_{i}=\{\omega:X_{i}\in A_{i}\}\in{\mathcal{F}}_{i}$, $m\leq i\leq n$ we have by properties of the density function $S_{n}(\underline{x}_{1,n})$ with respect to the measure $\mu(\cdot)$

where $m+n\leq t-s+1$, $u_{1}\in{\mathcal{K}}$. Let us now define functions $S_{\cdot}(\cdot)$ and $H_{\cdot}(\cdot,\cdot,\cdot,\cdot)$ and the sequence of functions $S_{n}:\times_{i=1}^{n}\mathbb{E}\rightarrow\Re$ as follows: $S_{0}(x_{0})=1$ and for $n\geq 1$:

Aditionally, we have

For further calculation it is important to have $n$-dimensional distribution for various configurations of disorders.

Denote $\left\langle\ \underline{u}\>,\underline{v}\right\rangle=\sum_{i=1}^{d}u_{i}v_{i}$ and $1\mskip-3.0mu\mskip-3.0mu{\mathbb{I}}=(1,1,\ldots,1)\in\Re^{K}$.We have (cf. [Sarnowski and Szajowski(2008)], [Dube and Mazumdar(2001)])

Here $\overrightarrow{\Pi}_{n}=(\underline{\Pi_{n}^{1}},\underline{\Pi_{n}^{2}},\underline{\Pi_{n}^{12}})$ and $\Upsilon_{n}=(\Upsilon_{n}^{1},\Upsilon_{n}^{2},\ldots,\Upsilon_{n}^{K})$. One can formulate: $\mathbf{H}(x,y,\vec{\pi},\upsilon)=\left\langle\ 1\mskip-3.0mu\mskip-3.0mu{\mathbb{I}}\>,\underline{\mathbf{H}}\right\rangle=\sum_{u\in{\mathcal{K}}}\underline{\mathbf{H}}^{u}(x,y,\vec{\pi}^{u},\upsilon^{u})$. Let us assume $0\leq\theta_{1}\leq\theta_{2}$ and suppose that $B_{i}\in{{\mathcal{B}}}$, $1\leq i\leq n+1$ and $X_{0}=x$ and denote $D_{n}=\{\omega:X_{i}(\omega)\in B_{i},1\leq i\leq n\}$. For $A_{i}=\{\omega:X_{i}\in B_{i}\}\in{\mathcal{F}}_{i}$, $1\leq i\leq n+1$ we have by properties of the density function $S_{n}(\underline{x}_{1,n})$ with respect to the measure $\mu(\cdot)$

Now we split the conditional probability of $\{X_{n+1}\in A_{n+1},\epsilon_{1}=u\}$ into the following parts

In (13):

we have:

			$\displaystyle\int_{D_{n}}{\bf P}_{x}(\theta_{2}>\theta_{1}>n,X_{n+1}\in A_{n+1},\epsilon_{1}=u\mid{\mathcal{F}}_{n})d{\bf P}_{x}$
		$\displaystyle=$	$\displaystyle\int_{\times_{i=1}^{n}B_{i}}(f^{\epsilon_{1}=u,n<\theta_{1}<\theta_{2}}_{x}(\underline{x}_{1,n})\int_{B_{n+1}}(p_{1}f^{0}_{x_{n}}(x_{n+1})+q_{1}f^{1,u}_{x_{n}}(x_{n+1}))\mu(dx_{n+1}))\mu(d\underline{x}_{1,n})$
		$\displaystyle=$	$\displaystyle\int_{D_{n}}{\bf P}_{x}(\theta_{2}>\theta_{1}>n,\epsilon_{1}=u\mid{\mathcal{F}}_{n})[{\bf P}_{X_{n}}^{0}(A_{n+1})p_{1}+q_{1}{\bf P}_{X_{n}}^{1,u}(A_{n+1})]d{\bf P}_{x}.$

In (14):

we get by similar arguments as for (13)

			$\displaystyle{\bf P}_{x}(\theta_{1}\leq n<\theta_{2},X_{n+1}\in A_{n+1},\epsilon_{1}=u\mid{\mathcal{F}}_{n})$
		$\displaystyle=$	$\displaystyle\left({\bf P}_{x}(\theta_{1}\leq n,\epsilon_{1}=u\mid{\mathcal{F}}_{n})-{\bf P}_{x}(\theta_{2}\leq n,\epsilon_{1}=u\mid{\mathcal{F}}_{n})\right)$
			$\displaystyle\times\mskip-3.0mu[q_{2}{\bf P}_{X_{n}}^{2}(A_{n+1})+p_{2}{\bf P}_{X_{n}}^{1,u}(A_{n+1})]$

In (16):

this part has the form:

$${\bf P}_{x}(\theta_{2}\leq n,X_{n+1}\in A_{n+1},\epsilon_{1}=u\mid{\mathcal{F}}_{n})={\bf P}_{x}(\theta_{2}\leq n,\epsilon_{1}=u\mid{\mathcal{F}}_{n}){\bf P}_{X_{n}}^{2}(A_{n+1})$$

In (15):

the conditional probability is equal to

			$\displaystyle{\bf P}_{x}(\theta_{1}=\theta_{2}>n,X_{n+1}\in A_{n+1},\epsilon_{1}=u\mid{\mathcal{F}}_{n})$
		$\displaystyle=$	$\displaystyle{\bf P}_{x}(\theta_{1}=\theta_{2}>n,\epsilon_{1}=u\mid{\mathcal{F}}_{n})[q_{1}{\bf P}_{X_{n}}^{2}(A_{n+1})+p_{1}{\bf P}_{X_{n}}^{0}(A_{n+1})]$

These formulae lead to

It is not too difficult to get the recursive formula for $\mathbf{H}(\cdot)$.

Now we split the conditional probability of $\underline{A}_{n+1,n+d}$ into the following parts

Let us calculate: ${\bf P}_{x}(\theta_{1}\leq n<\theta_{2},\underline{X}_{n+1,n+d}\in\underline{B}_{n+1,n+d},\epsilon_{1}=u\mid{\mathcal{F}}_{n})$. This probability can be calculated as follows:

A posteriori processes: ${\Pi}^{1,u}_{n}$, ${\Pi}^{2,u}_{n}$, ${\Pi}^{12,u}_{n}$, $\underline{\Pi}_{m\;{n}}^{u}$ can be calculated based on the following formula:

for $m,n=1,2,\ldots$, $m<n$, $i=1,2$.

Let us definie $\Upsilon_{n}^{u}$ in the recursive way.