|
Article Excerpt
In the compound Poisson disorder problem, arrival rate and/or jump distribution of some compound Poisson process changes suddenly at some unknown and unobservable time. The problem is to detect the change (or disorder) time as quickly as possible. A sudden regime shift may require some countermeasures be taken promptly, and a quickest detection rule can help with those efforts. We describe complete solution of the compound Poisson disorder problem with several standard Bayesian risk measures. Solution methods are feasible for numerical implementation and are illustrated by examples.
Key words: Poisson disorder problem; quickest detection; compound Poisson processes; optimal stopping MSC2000 subject classification: Primary: 62L10; secondary: 62L15, 62C10, 60G40 OR/MS subject classification: Primary: statistics: Bayesian, estimation; secondary: dynamic programming/optimal control: applications
History: Received June 1, 2005; revised November 7, 2005, February 10, 2006, and February 20, 2006.
1. Introduction. Let (12, [OMEGA], F, P) be a probability space hosting a compound Poisson process
[X.sub.t] = [X.sub.O] + [[N.sub.t].summation over (k=l)] [Y.sub.k], t [greater than or equal to] 0. (1)
Jumps arrive according to a standard Poisson process N = {[N.sub.t]; t [greater than or equal to 0} at some rate [[lambda].sub.0] > 0. The marks at each jump are i.i.d. [R.sub.d]-valued random variables [Y.sub.1], [Y.sub.2], ... with some common distribution [v.sub.0] (*) independent of the arrival process N. The process X may represent customer orders arriving in batches to a multiproduct service system, claims of various sizes filed with an insurance company, or sizes of electronic files requested for download from a network server.
Suppose that, at an unknown and unobservable time [theta], the initial arrival rate [[lambda].sub.0] and mark distribution [v.sub.0](*) of the process X change suddenly to [[lambda].sub.1] and [v.sub.1](*), respectively. This regime shift at the disorder time [theta] may become detrimental on the underlying system unless certain countermeasures are taken quickly. For example, optimal inventory levels, insurance premiums, or number of network servers may need to be revised as soon as the regime changes in order to maintain profitability, avoid bankruptcy, or ensure the network availability.
The objective of this paper is to detect the disorder time [theta] as quickly as possible to give decision makers an opportunity to react to the regime change on a timely basis. We assume that [[lambda].sub.0], [[lambda].1], [V.sub.0](*), and [v.sub.1](*) are known, and that the disorder time [theta] is a random variable whose prior distribution is
P{[theta] = [pi] and P{[theta] > t} = (1 - [pi])[e.sup.-[lambda]t], t [greater than or equal to] 0, [pi] [member of] [0, 1), [lambda] > 0.
The disorder time [theta] is still unobservable, and we need a quickest- detection rule adapted to the history F of the observation process X in (1). More precisely, we would like to find a stopping time [tau] of the process X whose Bayes risk
[R.sub.[tau]]([tau]) [??] P{[tau] < [theta]} + cE[([tau] - [theta]).sup.+], [pi] [member of ] [0, 1), [tau] [member of] F (2)
is the smallest ([x.sup.+] [??] max{x, 0}). If an F-stopping time [tau] attains the minimum Bayes risk
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)
then it is called a Bayes-optimal alarm time and optimally solves the trade-off between the false-alarm frequency P{[tau] < [theta]} and the expected detection delay cost c x E[([tau] - [theta]).sup.+].
All of the early work has dealt with the (simple) Poisson disorder problem. In that problem and in the notation above, the observation process was the counting process N, whose rate changes at some unobservable time [theta] from some known constant [[lambda].sup.0] to some other [[lambda].sub.1]. While the question was the same; namely, to detect the disorder time [theta] as quickly as possible, the information about marks [Y.sub.1], [Y.sub.2], ... was ignored completely. This omission was understandable because of the difficulty of the problem: Simple Poisson disorder problem was solved completely by Peskir and Shiryaev [13] only recently--more than 30 years after it was formulated by Galchuk and Rozovskii [9] for the first time. In the meantime, partial solutions and new insights were provided. Most notably, Davis [5] showed that quickest-detection rules should not differ much if they are to minimize some "standard" Bayes risks; namely, one of [R.sup.(1)], [R.sup.(2)] (same as R of (2)), or [R.sup.(3)] in
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)
where [epsilon], c, and [alpha] are some known positive constants (see also Shiryaev [17]). Recently, Bayraktar and Dayanik [1] solved the simple Poisson disorder problem with Bayes risk [R.sup.(4)] in (4), whose exponential detection-delay penalty makes it more suitable for financial applications. Later, Bayraktar et al. [2] showed that the measure [R.sup.(4)] is also a "standard" Bayes risk (if the latter is redefined suitably) and gave a general solution method for standard problems.
For the first time, Gapeev [10] has recently succeeded in including the observed marks [Y.sub.1], [Y.sub.2], ... into an optimal decision rule in order to detect the disorder time (more) quickly and accurately. He provided the full solution for the following very special instance of the compound Poisson disorder problem: Before and after the disorder time [theta], real-valued marks [Y.sub.1], [Y.sub.2], ... have exponential distributions, and the expected mark sizes are the same as the corresponding jump arrival rates. Namely, the mark distributions are
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)
where [[lambda].sub.0] and [[lambda].sub.1] are the arrival rates of jumps (i.e., the counting process N in (1)) before and after the disorder, respectively.
The main contribution of our paper is the complete solution of the compound Poisson disorder problem in its full generality. For any pair of arrival rates [[lambda].sub.0] and [[lambda].sub.1] and mark distributions [v.sub.0](*) and [v.sub.1] (*), we explicitly describe a quickest-detection rule. These rules depend on the same F-adapted odds-ratio process [PHI] = {[PHI]; t > 0}; see (11). At every t [greater than or equal to] 0, the random variable [PHI], is the conditional odds ratio of the event {[theta] [less than or equal to] t} where disorder has happened at or before time t, given past and present observations F of the process X. For a suitable constant [xi] > 0, the first crossing time [U.sub.0] = inf{t [greater than or equal to] 0: [[phi].sub.t] [greater than or equal to] [xi]} of the process [phi] turns out to be a quickest-detection rule: The Bayes risk [??] in (2) of [U.sub.0] is the smallest among all of the stopping times of the process X. The critical threshold [xi] can be calculated numerically, and the quickest-detection rule [U.sub.0] is suitable for online implementation because [[PHI].sub.t] [greater than or equal to] can be updated by a recursive formula; see (13).
We also show that every compound Poisson disorder problem with one of "standard" Bayes risks in (4) can be solved in the same way.
Our probabilistic methods are different from the analytical methods of all previously cited work. The latter attacked Poisson disorder problems by studying analytical properties of related free-boundary integrodifferential equations. Instead, we very carefully study sample paths of the process [PHI], which turn out to be piecewise deterministic and Markovian. General characterization of stopping times of jump processes allows us to approximate the minimum Bayes risk successively. This approximation is the key to our computational and theoretical results.
In the next section, we give the precise description of a compound Poisson disorder problem and show how to reduce it to an optimal stopping problem for a suitable Markov process. In [sub section]3 and 4, we introduce successive approximations of the value function of the optimal stopping problem and establish key results for an efficient numerical method, which is presented in [section]5. We illustrate this method on several old and new examples and briefly discuss some extensions in [section]6. Finally, in [section]7 we establish the connection between our method and the method of variational inequalities as applied to the compound Poisson disorder problem. Appendix A contains some basic derivations and long proofs.
2. Model and problem description. Starting with a reference probability measure, we will first construct a model containing all of the random elements of our problem with the correct probability laws.
Model. Let ([OMEGA], F, [P.sub.0) be a probability space hosting the following independent stochastic elements:
(i) a standard Poisson process N = {[N.sub.t] [greater than or equal to] 0} with the arrival rate [[lambda].sub.0],
(ii) independent and identically distributed [R.sup.d]-valued random variables [Y.sub.1], [Y.sub.2], ... with some common distribution [v.sub.0](B) [??] [p.sub.0]{[y.sub.1] [member of] B} for every set B in the Borel [sigma]-algebra B([R.sup.d]) and [v.sub.0]({0})= 0,
(iii) a random variable [theta] with the distribution
[P.sub.0]{[theta] = 0} = [pi] [member of] [0, 1) and [P.sub.0]{[theta] > t} = (1 - [pi])[e.sup-[lambda]t], t [greater than or equal to] 0, [lambda] > 0. (6)
Let X = {[X.sub.t]; t [greater than or equal to] 0} be the process defined by (1) with the jump times
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)
and F = [{[F.sub.t]}.sub.t[greater than or equal to]0] be the augmentation of its natural filtration [sigma]([X.sub.s], s [less than or equal to] t), t [P.sub.0] with [P.sub.0]-null sets. Then the process X is a ([P.sub.0, F)- compound Poisson process with the arrival rate [[lambda].sub.0] and the jump distribution [v.sub.0](*).
Let [[lambda].sub.1] > be a constant, and [v.sub.1] (*) be a probability measure on ([R.sup.d], B([R.sup.d])) absolutely continuous with respect to the distribution [v.sub.0](*). In general, every probability measure [v.sub.1](*) is the sum of two probability measures; one is singular, and the other is absolutely continuous with respect to [v.sub.0](*). If it is necessary, the distribution [v.sub.1] (*) is replaced with its component, that is absolutely continuous with respect to the measure [v.sub.0](*) without loss of generality, as explained by Poor [14, pp. 269-271]. Then the Radon-Nikodym derivative
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)
of [V.sub.1](*) with respect to [V.sub.0](*) exists and is a [v.sub.0]-a.e, nonnegative Borel function.
We shall denote by G = [{Gt}.sub.t[greater than or equal to]0] and [G.sub.t] [??] [F.sub.t] v [sigma] [theta], t [greater than or equal to] the enlargement of the filtration G with the sigma-algebra [sigma]([theta]) generated by [theta]. Let us define a new probability measure P on the measurable space ([omega], [V.sub.s[greater than or equal to] 0] [G.sub.s]) locally in terms of the Radon-Nikodym derivatives
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)
where [N.sub.[theta]-] is the number of arrivals in the time interval [0, [theta]). If the disorder time [theta] is known, then each random variable [Z.sub.t] is simply the likelihood ratio of the interarrival times [[sigma].sub.1], [[sigma].sub.2] - [[sigma]sub.1], ... and the jump sizes [Y.sub.1], [Y.sub.2], ... observed at or before time t. Under P, the interarrival times and jump sizes are conditionally independent and have the desired conditional distributions given [theta]: The rate of exponentially distributed interarrival times and the distribution of the jump sizes change at time [theta] from [[lambda].sub.0] and [v.sub.0](*) to [[lambda].sub.1] and [v.sub.1](*), respectively. See also Appendix A. 1 for another justification by using an absolutely continuous change of measure for point processes.
Finally, because [Z.sub.0] = 1 almost surely and the probability measures [P.sub.0] and P coincide on [G.sub.0] = [sigma]([theta]), the distribution of [theta] is the same under P and [P.sub.0]. Hence, under the probability measure P defined by (9), the process X and the random variable [theta] have the same properties as in the setup of the disorder problem described in the introduction.
Problem description. In the remainder, we will work with the concrete model described above. The random variable [theta] is the unobservable disorder time and must be detected as quickly as possible as the history F of the observation process X unfolds. The admissible detection rules are the stopping times of the filtration F.
Our problem is to find the smallest Bayes risk U(*) in (3) by minimizing over all stopping rules [tau] of...
|
