Search

In this note we re-examine the analysis of the paper "On the martingale property of stochastic exponentials" by B. Wong and C.C. Heyde, Journal of Applied Probability, 41(3):654-664, 2004. Some counterexamples are presented and alternative formulations are discussed., Comment: To appear in Journal of Applied Probability, 11 pages

In [5] Doeblin considered some classes of finite non-homogeneous Markov chains and gave without proofs several results concerning their asymptotic behaviour. In the present paper we first attempt to make Doeblin's results precise and try to reconstruct his arguments. Subsequently we investigate more general situations, where a state space decomposition is provided by the sets occurring in the representation of the atomic sets of the tail or-field. We show that Doeblin's notion of an associated chain, as well as considerations regarding the tail ar-field structure of the chain, can be used to solve such cases. FINITE MARKOV CHAIN; FINAL CLASS; CYCLICALLY MOVING SUBCLASS; TAIL ar-FIELD; ATOMIC SET; RECURRENCE; WHIRLPOOL

In a recent paper Weiss (1965) has suggested a simple model for a carrier-borne epidemic such as typhoid. He considers a population (of size m) of susceptibles into which a number (k) of carriers is introduced. These carriers exhibit no overt symptoms and are only detectable by the discovery of infected persons. He supposed that after the initial introduction of the carriers, the population remains entirely closed and no new carriers arise. The epidemic then progresses until either all the carriers have been traced and isolated or until the entire population has succumbed to the disease.

We illustrate a technique for computing certain integrals that arise in probability theory by giving a new derivation of a formula of Kingman. This formula contains the joint distribution of the processes F(t) = inf {s: X(t + s) = b} and B(t) = inf{s: X(t - s) = b} where X is a time homogeneous, continuous parameter, Markov process and b is a fixed point in its state space. We then extend this formula to the situation in which b is replaced by a finite set {b 1, …, b n }.

This paper establishes a new version of integration by parts formula of Markov chains for sensitivity computation, under much lower restrictions than the existing researches. Our approach is more fundamental and applicable without using Girsanov theorem or Malliavin calculus as did by past papers. Numerically, we apply this formula to compute sensitivity regarding the transition rate matrix and compare with a recent research by an IPA (infinitesimal perturbation analysis) method and other approaches.

In this paper, to model cascading failures, a new stochastic failure model is proposed. In a system subject to cascading failures, after each failure of the component, the remaining component suffers from increased load or stress. This results in shortened residual lifetimes of the remaining components. In this paper, to model this effect, the concept of the usual stochastic order is employed along with the accelerated life test model, and a new general class of stochastic failure models is generated.

In this paper, we first use the distribution of the number of records to demonstrate that the right tail probabilities of counts of rare events are generally better approximated by the right tail probabilities of Poisson distribution than {those} of normal distribution. We then show the moderate deviations in Poisson approximation generally require an adjustment and, with suitable adjustment, we establish better error estimates of the moderate deviations in Poisson approximation than those in \cite{CFS}. Our estimates contain no unspecified constants and are easy to apply. We illustrate the use of the theorems in six applications: Poisson-binomial distribution, matching problem, occupancy problem, birthday problem, random graphs and 2-runs. The paper complements the works of \cite{CC92,BCC95,CFS}., 29 pages and 5 figures

Large samples from a light-tailed distribution often have a well-defined shape. This paper examines the implications of the assumption that there is a limit shape. We show that the limit shape determines the upper quantiles for a large class of random variables. These variables may be described loosely as continuous homogeneous functionals of the underlying random vector. They play an important role in evaluating risk in a multivariate setting. The paper also looks at various coefficients of tail dependence and at the distribution of the scaled sample points for large samples. The paper assumes convergence in probability rather than almost sure convergence. This results in an elegant theory. In particular, there is a simple characterization of domains of attraction.

This paper generalizes the Kunita–Watanabe decomposition of an $L^2$ space. The generalization comes from using nonlinear stochastic integrals where the integrator is a family of continuous martingales bounded in $L^2$ . This result is also the solution of an optimization problem in $L^2$ . First, martingales are assumed to be stochastic integrals. Then, to get the general result, it is shown that the regularity of the family of martingales with respect to its spatial parameter is inherited by the integrands in the integral representation of the martingales. Finally, an example showing how the results of this paper, with the Clark–Ocone formula, can be applied to polynomial functions of Brownian integrals.

In this paper, we extend the strong laws of large numbers and entropy ergodic theorem for partial sums for tree-indexed nonhomogeneous Markov chains fields to delayed versions of nonhomogeneous Markov chains fields indexed by a homogeneous tree. At first we study a generalized strong limit theorem for nonhomogeneous Markov chains indexed by a homogeneous tree. Then we prove the generalized strong laws of large numbers and the generalized asymptotic equipartition property for delayed sums of finite nonhomogeneous Markov chains indexed by a homogeneous tree. As corollaries, we can get the similar results of some current literatures. In this paper, the problem settings may not allow to use Doob's martingale convergence theorem, and we overcome this difficulty by using Borel–Cantelli Lemma so that our proof technique also has some new elements compared with the reference Yang and Ye (2007).

In this paper, we mainly study the moderate deviation principle of sample quantiles and order statistics for stationary m-dependent random variables. The results obtained in this paper extend the corresponding ones for an independent and identically distributed sequence to a stationary m-dependent sequence.

In this paper, some results on the complete moment convergence for arrays of rowwise negatively associated (NA, for short) random variables are established. The results obtained in this paper correct the corresponding one obtained in Ko [13] and also improve and generalize the corresponding ones of Kuczmaszewska [14] and Ko [13]. As an application of the main results, we present a result on complete consistency for the estimator in a non-parametric regression model based on NA errors. Finally, we provide a numerical simulation to verify the validity of our result.

The Ginibre point process (GPP) is one of the main examples of determinantal point processes on the complex plane. It is a recurring distribution of random matrix theory as well as a useful model in applied mathematics. In this paper we briefly overview the usual methods for the simulation of the GPP. Then we introduce a modified version of the GPP which constitutes a determinantal point process more suited for certain applications, and we detail its simulation. This modified GPP has the property of having a fixed number of points and having its support on a compact subset of the plane. See Decreusefond et al. (2013) for an extended version of this paper.

In this paper we use tools from differential topology to give a geometric description of cohomology for Hilbert manifolds. Our model is Quillen’s geometric description of cobordism groups for finite-dimensional smooth manifolds [Quillen, ‘Elementary proofs of some results of cobordism theory using steenrod operations’, Adv. Math., 7 (1971)]. Quillen stresses the fact that this construction allows the definition of Gysin maps for ‘oriented’ proper maps. For finite-dimensional manifolds one has a Gysin map in singular cohomology which is based on Poincaré duality, hence it is not clear how to extend it to infinite-dimensional manifolds. But perhaps one can overcome this difficulty by giving a Quillen type description of singular cohomology for Hilbert manifolds. This is what we do in this paper. Besides constructing a general Gysin map, one of our motivations was a geometric construction of equivariant cohomology, which even for a point is the cohomology of the infinite-dimensional space $BG$, which has a Hilbert manifold model. Besides that, we demonstrate the use of such a geometric description of cohomology by several other applications. We give a quick description of characteristic classes of a finite-dimensional vector bundle and apply it to a generalized Steenrod representation problem for Hilbert manifolds and define a notion of a degree of proper oriented Fredholm maps of index $0$.

In a defaultable market, an investor trades having only partial information about the behavior of the market. Taking into account the intraday stock movements, the risky asset prices are modelled by marked point processes. Their dynamics depend on an unobservable process, representing the amount of news reaching the market. This is a marked point process, which may have common jump times with the risky asset price processes. The problem of hedging a defaultable claim is studied. In order to discuss all these topics, in this paper we examine stochastic control problems using backward stochastic differential equations (BSDEs) and filtering techniques. The goal of this paper is to construct a sequence of functions converging to the value function, each of these is the unique solution of a suitable BSDE.

In this paper we investigate the limiting behavior of the failure rate for the convolution of two or more life distributions. In a previous paper on mixtures, Block, Mi and Savits (1993) showed that the failure rate behaves like the limiting behavior of the strongest component. We show a similar result here for convolutions. We also show by example that unlike a mixture population, the ultimate direction of monotonicity does not necessarily follow that of the strongest component.

In this paper we study the speed of infection spread and the survival of the contact process in the random geometric graph G = G(n, r n , f) of n nodes independently distributed in S = [-½, ½]2 according to a certain density f(·). In the first part of the paper we assume that infection spreads from one node to another at unit rate and that infected nodes stay in the same state forever. We provide an explicit lower bound on the speed of infection spread and prove that infection spreads in G with speed at least D 1 nr n 2. In the second part of the paper we consider the contact process ξ t on G where infection spreads at rate λ > 0 from one node to another and each node independently recovers at unit rate. We prove that, for every λ > 0, with high probability, the contact process on G survives for an exponentially long time; there exist positive constants c 1 and c 2 such that, with probability at least 1 - c 1 / n 4, the contact process starting with all nodes infected survives up to time t n = exp(c 2 n/logn) for all n.

Let 𝓈 be a finite or countable set. Given a matrix F = (F ij ) i,j∈𝓈 of distribution functions on R and a quasistochastic matrix Q = (q ij ) i,j∈𝓈 , i.e. an irreducible nonnegative matrix with maximal eigenvalue 1 and associated unique (modulo scaling) positive left and right eigenvectors u and v, the matrix renewal measure ∑ n≥0 Q n ⊗ F *n associated with Q ⊗ F := (q ij F ij ) i,j∈𝓈 (see below for precise definitions) and a related Markov renewal equation are studied. This was done earlier by de Saporta (2003) and Sgibnev (2006, 2010) by drawing on potential theory, matrix-analytic methods, and Wiener-Hopf techniques. In this paper we describe a probabilistic approach which is quite different and starts from the observation that Q ⊗ F becomes an ordinary semi-Markov matrix after a harmonic transform. This allows us to relate Q ⊗ F to a Markov random walk {(M n , S n )} n≥0 with discrete recurrent driving chain {M n } n≥0. It is then shown that renewal theorems including a Choquet-Deny-type lemma may be easily established by resorting to standard renewal theory for ordinary random walks. The paper concludes with two typical examples.

This paper provides a simple proof for the fact that the hitting time to an infrequently visited subset for a one-dependent regenerative process converges weakly to an exponential distribution. Special cases are positive recurrent Harris chains and Harris processes. The paper further extends this class of limit theorems to ‘rewards’ that are cumulated to the hitting time of such a rare set.

In this paper, the componentwise increasing convex order, the upper orthant order, the upper orthant convex order, and the increasing directionally convex order for random vectors are generalized to hierarchical classes of integral stochastic order relations. The elements of the generating classes of functions possess nonnegative partial derivatives up to some given degrees. Some properties of these new stochastic order relations are studied. Particular attention is paid to the comparison of weighted sums of the respective components of ordered random vectors. By providing a unified derivation of standard multivariate stochastic orderings, the present paper shows how some well-known results derive from a common principle.

We present new ideas about the type of random tessellation which evolves through successive division of its cells. These ideas are developed in an intuitive way, with many pictures and only a modicum of mathematical formalism–so that the wide application of the ideas is clearly apparent to all readers. A vast number of new tessellation models, with known probability distribution for the volume of the typical cell, follow from the concepts in this paper. There are other interesting models for which results are not presented (or presented only through simulation methods), but these models have illustrative value. A large agenda of further research is opened up by the ideas in this paper.

This thesis is concerned with the study of stochastic epidemic models for infectious diseases in heterogeneous populations. All diseases treated are of SIR type, i.e. individuals are either Susceptible, Infectious or Recovered (and immune). The transitions between these states are according to S to I to R. The thesis consists of five papers. Papers I and II treat approximations for the distribution of the time to extinction. In Paper I, a sub-community version of the SIR model with demography is considered. The interest is in how the distribution of the time to extinction is affected by varying the degree of interaction between the sub-communities. Paper II is concerned with a two-type version of Bartlett's model. The distribution of the time to extinction is studied when the difference in susceptibility/infectivity between the types of individuals is varied. Papers III and IV treat random intersection graphs with tunable clustering. In Paper III a Reed-Frost epidemic is run on such a random intersection graph. The critical parameter R_0 and the probability of a large outbreak are derived and it is investigated how these quantities are affected by the clustering in the graph. In Paper IV the interest is in the component structure of such a graph, i.e. the size and the emergence of a giant component is studied. The last paper, Paper V, treats the situation when a simple epidemic is running in a varying environment. A varying environment is in this context any external factor that affects the contact rate in the population, but is itself unaffected by the population. The model treated is a term-time forced version of the stochastic general epidemic where the contact rate is modelled by an alternating renewal process. A threshold parameter R_* and the probability of a large outbreak are derived and studied.

In this paper we obtain some equivalent conditions and sufficient conditions for the local and nonlocal asymptotics of the φ-moments of the overshoot and undershoot of a random walk, where φ is a nonnegative, long-tailed function. By the strong Markov property, it can be shown that the moments of the overshoot and undershoot and the moments of the first ascending ladder height of a random walk satisfy some renewal equations. Therefore, in this paper we first investigate the local and nonlocal asymptotics for the moments of the first ascending ladder height of a random walk, and then give some equivalent conditions and sufficient conditions for the asymptotics of the solutions to some renewal equations. Using the above results, the main results of this paper are obtained.

In this paper we investigate the ‘local’ properties of a random mapping model, T n D̂, which maps the set {1, 2, …, n} into itself. The random mapping T n D̂ , which was introduced in a companion paper (Hansen and Jaworski (2008)), is constructed using a collection of exchangeable random variables D̂ 1, …, D̂ n which satisfy In the random digraph, G n D̂ , which represents the mapping T n D̂ , the in-degree sequence for the vertices is given by the variables D̂ 1, D̂ 2, …, D̂ n , and, in some sense, G n D̂ can be viewed as an analogue of the general independent degree models from random graph theory. By local properties we mean the distributions of random mapping characteristics related to a given vertex v of G n D̂ - for example, the numbers of predecessors and successors of v in G n D̂ . We show that the distribution of several variables associated with the local structure of G n D̂ can be expressed in terms of expectations of simple functions of D̂ 1, D̂ 2, …, D̂ n . We also consider two special examples of T n D̂ which correspond to random mappings with preferential and anti-preferential attachment, and determine, for these examples, exact and asymptotic distributions for the local structure variables considered in this paper. These distributions are also of independent interest.

Consider a random graph, having a pre-specified degree distribution F but other than that being uniformly distributed, describing the social structure (friendship) in a large community. Suppose one individual in the community is externally infected by an infectious disease and that the disease has its course by assuming that infected individuals infect their not yet infected friends independently with probability p. For this situation the paper determines R_0 and tau_0, the basic reproduction number and the asymptotic final size in case of a major outbreak. Further, the paper looks at some different local vaccination strategies where individuals are chosen randomly and vaccinated, or friends of the selected individuals are vaccinated, prior to the introduction of the disease. For the studied vaccination strategies the paper determines R_v: the reproduction number, and tau_v: the asymptotic final proportion infected in case of a major outbreak, after vaccinating a fraction v., 31 pages, 3 figures

This paper is concerned with the analysis of Markov decision processes in which a natural form of termination ensures that the expected future costs are bounded, at least under some policies. Whereas most previous analyses have restricted attention to the case where the set of states is finite, this paper analyses the case where the set of states is not necessarily finite or even countable. It is shown that all the existence, uniqueness, and convergence results of the finite-state case hold when the set of states is a general Borel space, provided we make the additional assumption that the optimal value function is bounded below. We give a sufficient condition for the optimal value function to be bounded below which holds, in particular, if the set of states is countable.

Let X = (X1, X2, …, Xn) be an exchangeable random vector, and write X(1:i) = min{X1, X2, …, Xi}, 1 ≤ i ≤ n. In this paper we obtain conditions under which X(1:i) decreases in i in the hazard rate order. A result involving more general (that is, not necessarily exchangeable) random vectors is also derived. These results are applied to obtain the limiting behaviour of the hazard rate function of the lifetimes of various coherent systems in reliability theory. The notions of the Samaniego signatures and the minimal signatures of such systems are extensively used in the paper. An interesting relationship between these two signatures is obtained. The results are illustrated in a series of examples.

This thesis consists of four papers.In paper 1, we prove central limit theorems for Markov chains under (local) contraction conditions. As a corollary we obtain a central limit theorem for Markov chains associated with iterated function systems with contractive maps and place-dependent Dini-continuous probabilities.In paper 2, properties of inverse subordinators are investigated, in particular similarities with renewal processes. The main tool is a theorem on processes that are both renewal and Cox processes.In paper 3, distributional properties of supercritical and especially immortal branching processes are derived. The marginal distributions of immortal branching processes are found to be compound geometric.In paper 4, a description of a dynamic population model is presented, such that samples from the population have genealogies as given by a Lambda-coalescent with mutations. Depending on whether the sample is grouped according to litters or families, the sampling distribution is either regenerative or non-regenerative.

In this paper, we describe a class of Wiener functionals that are ‘indeterminate by their moments’, that is, whose distributions are not uniquely determined by their moments. In particular, it is proved that the integral of a geometric Brownian motion is indeterminate by its moments and, moreover, shown that previous proofs of this result are incorrect. The main result of this paper is based on geometric inequalities in Gauss space and on a generalization of the Krein criterion due to H. L. Pedersen.

This paper studies the subexponential properties of the stationary workload, actual waiting time and sojourn time distributions in work-conserving single-server queues when the equilibrium residual service time distribution is subexponential. This kind of problem has been previously investigated in various queueing and insurance risk settings. For example, it has been shown that, when the queue has a Markovian arrival stream (MAS) input governed by a finite-state Markov chain, it has such subexponential properties. However, though MASs can approximate any stationary marked point process, it is known that the corresponding subexponential results fail in the general stationary framework. In this paper, we consider the model with a general stationary input and show the subexponential properties under some additional assumptions. Our assumptions are so general that the MAS governed by a finite-state Markov chain inherently possesses them. The approach used here is the Palm-martingale calculus, that is, the connection between the notion of Palm probability and that of stochastic intensity. The proof is essentially an extension of the M/GI/1 case to cover ‘Poisson-like’ arrival processes such as Markovian ones, where the stochastic intensity is admitted.

This paper studies a discrete-time single-server queue with two independent inputs and service interruptions. One of the inputs to the queue is an independent and identically distributed process. The other is a much more general process and it is not required to be Markov nor is it required to be stationary. The service interruption process is also general and it is not required to be Markov or to be stationary. This paper shows that a stochastic decomposition property for the virtual waiting-time process holds in the discrete-time single-server queue with service interruptions. To the best of the author's knowledge, no stochastic decomposition results for virtual waiting-time processes in non-work-conserving queues, such as queues with service interruptions, have been obtained before and only work-conserving queues have been studied in the literature.

The full-information best-choice problem, as posed by Gilbert and Mosteller in 1966, asks us to find a stopping rule which maximizes the probability of selecting the largest of a sequence of n i.i.d. standard uniform random variables. Porosiński, in 1987, replaced a fixed n by a random N, uniform on {1,2,…,n} and independent of the observations. A partial-information problem, imbedded in a 1980 paper of Petruccelli, keeps n fixed but allows us to observe only the sequence of ranges (max - min), as well as whether or not the current observation is largest so far. Recently, Porosiński compared the solutions to his and Petruccelli's problems and found that the two problems have identical optimal rules as well as risks that are asymptotically equal. His discovery prompts the question: why? This paper gives a good explanation of the equivalence of the optimal rules. But even under the lens of a planar Poisson process model, it leaves the equivalence of the asymptotic risks as somewhat of a mystery. Meanwhile, two other problems have been shown to have the same limiting risks: the full-information problem with the (suboptimal) Porosiński-Petruccelli stopping rule, and the full-information ‘duration of holding the best’ problem of Ferguson, Hardwick and Tamaki, which turns out to be nothing but the Porosiński problem in disguise.

In this paper, we study the on-line parameter estimation problem for a partially observable system subject to deterioration and random failure. The state of the system evolves according to a continuous-time homogeneous Markov process with a finite state space. The state of the system is hidden except for the failure state. When the system is operating, only the information obtained by condition monitoring, which is related to the working state of the system, is available. The condition monitoring observations are assumed to be in continuous range, so that no discretization is required. A recursive maximum likelihood (RML) algorithm is proposed for the on-line parameter estimation of the model. The new RML algorithm proposed in the paper is superior to other RML algorithms in the literature in that no projection is needed and no calculation of the gradient on the surface of the constraint manifolds is required. A numerical example is provided to illustrate the algorithm.

We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square. In this paper we introduce a notion of a minimal directed spanning tree. To illustrate this, consider the following model of transmission of radio waves by transmitters, receivers and amplifiers. Suppose a source transmitter located at the origin transmits messages which can be received only by receivers placed in the positive quadrant. These receivers in turn amplify the message and transmit it to the receivers lying in the positive quadrant with respect to these amplifiers. In this way each receiver lying in the positive quadrant with respect to the transmitter receives the message. The graph which represents this model of transmission may be viewed as a directed spanning tree. For transmission of radio waves in this model, the required strength of the source transmitter is clearly related to the number of receivers which receive the message directly from the transmitter at the origin, as well as the sum of the distances of these receivers from the origin and the distance of the receiver farthest away from the origin which receives the message directly from the origin. In this paper we investigate these three factors when the receivers are located at random in the unit square (say) and we study the asymptotics as the number of transmitters goes to infinity. This model of transmission of radio waves is in contrast to that introduced by Gilbert (1961) where the radio waves can travel in any direction from the point of their origin. However, they may be received only by receivers located within a certain fixed distance from the source of transmission.

This thesis, consisting of six papers and a summary, studies the area of continuous time financial mathematics. A unifying theme for many of the problems studied is the implications of possible mis-specifications of models. Intimately connected with this question is, perhaps surprisingly, convexity properties of option prices. We also study qualitative behavior of different optimal stopping boundaries appearing in option pricing.In Paper I a new condition on the contract function of an American option is provided under which the option price increases monotonically in the volatility. It is also shown that American option prices are continuous in the volatility.In Paper II an explicit pricing formula for the perpetual American put option in the Constant Elasticity of Variance model is derived. Moreover, different properties of this price are studied.Paper III deals with the Russian option with a finite time horizon. It is shown that the value of the Russian option solves a certain free boundary problem. This information is used to analyze the optimal stopping boundary.A study of perpetual game options is performed in Paper IV. One of the main results provides a condition under which the value of the option is increasing in the volatility.In Paper V options written on several underlying assets are considered. It is shown that, within a large class of models, the only model for the stock prices that assigns convex option prices to all convex contract functions is geometric Brownian motion.Finally, in Paper VI it is shown that the optimal stopping boundary for the American put option is convex in the standard Black-Scholes model.

Suppose that {X s , 0 ≤ s ≤ T} is an m-dimensional geometric Brownian motion with drift, μ is a bounded positive Borel measure on [0,T], and ϕ : ℝ m → [0,∞) is a (weighted) l q (ℝ m )-norm, 1 ≤ q ≤ ∞. The purpose of this paper is to study the distribution and the moments of the random variable Y given by the L p (μ)-norm, 1 ≤ p ≤ ∞, of the function s ↦ ϕ(X s ), 0 ≤ s ≤ T. By using various geometric inequalities in Wiener space, this paper gives upper and lower bounds for the distribution function of Y and proves that the distribution function is log-concave and absolutely continuous on every open subset of the distribution's support. Moreover, the paper derives tail probabilities, presents sharp moment inequalities, and shows that Y is indetermined by its moments. The paper will also discuss the so-called moment-matching method for the pricing of Asian-styled basket options.

In this paper, we study the classification of matrix GI/M/1-type Markov chains with a tree structure. We show that the Perron–Frobenius eigenvalue of a Jacobian matrix provides information for classifying these Markov chains. A fixed-point approach is utilized. A queueing application is presented to show the usefulness of the classification method developed in this paper.

This paper studies the law of any power of the integral of geometric Brownian motion over any finite time interval. As its main results, two integral representations for this law are derived. This is by enhancing the Laplace transform ansatz of Yor (1992) with complex analytic methods, which is the main methodological contribution of the paper. The one of our integrals has a similar structure to that obtained by Yor, while the other is in terms of Hermite functions as those of Dufresne (2001). Performing or not performing a certain Girsanov transformation is identified as the source of these two forms of the laws. While our results specialize for exponents equal to 1 to those obtained by Yor, they yield on specialization representations for the exponent equal to minus 1 laws which are markedly different from those obtained by Dufresne., 18 pages, 2 figures

In this paper, we consider denumerable-state continuous-time Markov decision processes with (possibly unbounded) transition and reward rates and general action space under the discounted criterion. We provide a set of conditions weaker than those previously known and then prove the existence of optimal stationary policies within the class of all possibly randomized Markov policies. Moreover, the results in this paper are illustrated by considering the birth-and-death processes with controlled immigration in which the conditions in this paper are satisfied, whereas the earlier conditions fail to hold.

This paper presents an algorithmic procedure to calculate the delay distribution of a type k customer in a first-come-first-served (FCFS) discrete-time queueing system with multiple types of customers, where each type has different service requirements (the MMAP[K]/PH[K]/1 queue). First, we develop a procedure, using matrix analytical methods, to handle arrival processes that do not allow batch arrivals to occur. Next, we show that this technique can be generalized to arrival processes that do allow batch arrivals to occur. We end the paper by presenting some numerical examples.

The purpose of this paper is to study ageing properties of first-passage times of increasing Markov chains. We extend the literature to some new ageing classes, such as the IFR(2), NBU(2), DRLLt and NBULt classes. We also give sufficient conditions in the finite case, that are more efficient computationally, just in terms of the transition matrix K, in the discrete case, or the generator matrix Q, in the continuous case. For the uniformizable, continuous-time Markov processes, we derive conditions in terms of the discrete uniformized Markov chain for the NBU(2) and the NBULt classes. In the last section, a review of the main results in this direction in the literature is given, and we compare some of the conditions stated in this paper with others given in the literature about some other ageing classes. Some examples where these results are applied are given.

In [20] Krajíček and Pudlák discovered connections between problems in computational complexity and the lengths of first-order proofs of finite consistency statements. Later Pudlák [25] studied more statements that connect provability with computational complexity and conjectured that they are true. All these conjectures are at least as strong as $\mathsf {P}\neq \mathsf {NP}$ [23–25].One of the problems concerning these conjectures is to find out how tightly they are connected with statements about computational complexity classes. Results of this kind had been proved in [20, 22].In this paper, we generalize and strengthen these results. Another question that we address concerns the dependence between these conjectures. We construct two oracles that enable us to answer questions about relativized separations asked in [19, 25] (i.e., for the pairs of conjectures mentioned in the questions, we construct oracles such that one conjecture from the pair is true in the relativized world and the other is false and vice versa). We also show several new connections between the studied conjectures. In particular, we show that the relation between the finite reflection principle and proof systems for existentially quantified Boolean formulas is similar to the one for finite consistency statements and proof systems for non-quantified propositional tautologies.

This paper raises the following question: let {Φn(A), A ⊂ ℝd} be a Poisson process with intensity nf(x), x ∈ ℝd and let c(Xi | Φn) be a Voronoi tile with nucleus Xi (a jump point of Φn). Let μ(.) denote Lebesgue measure in ℝd. Is it true that, for any bounded measurable subset B of ℝd, ∑Xi∈Bμ(c(Xi| Φn)) → μ(B) almost surely as n → ∞ only if f > 0 almost everywhere? This statement can be viewed as the strong law of large numbers for Voronoi tessellation. Though the positive answer may seem ‘obvious’, we could not find any such statement, especially for arbitrary measurable B and nonhomogeneous Poisson processes. For B with the boundary of Lebesgue measure 0 the proof is simple. We prove in this paper that the statement is true for ℝ1.

Consider a renewal process. The renewal events partition the process into i.i.d. renewal cycles. Assume that on each cycle, a rare event called 'success’ can occur. Such successes lend themselves naturally to approximation by Poisson point processes. If each success occurs after a random delay, however, Poisson convergence may be relatively slow, because each success corresponds to a time interval, not a point. In 1996, Altschul and Gish proposed a finite-size correction to a particular approximation by a Poisson point process. Their correction is now used routinely (about once a second) when computers compare biological sequences, although it lacks a mathematical foundation. This paper generalizes their correction. For a single renewal process or several renewal processes operating in parallel, this paper gives an asymptotic expansion that contains in successive terms a Poisson point approximation, a generalization of the Altschul-Gish correction, and a correction term beyond that.

The paper considers one of the standard processes for modeling returns in finance, the stochastic volatility process with regularly varying innovations. The aim of the paper is to show how point process techniques can be used to derive the asymptotic behavior of the sample autocorrelation function of this process with heavy-tailed marginal distributions. Unlike other non-linear models used in finance, such as GARCH and bilinear models, sample autocorrelations of a stochastic volatility process have attractive asymptotic properties. Specifically, in the infinite variance case, the sample autocorrelation function converges to zero in probability at a rate that is faster the heavier the tails of the marginal distribution. This behavior is analogous to the asymptotic behavior of the sample autocorrelations of independent identically distributed random variables.

This paper studies the dependence structure and bounds of several basic prototypical parallel queueing systems with correlated arrival processes to different queues. The marked feature of our systems is that each queue viewed alone is a standard single-server queuing system extensively studied in the literature, but those queues are statistically dependent due to correlated arrival streams. The major difficulty in analysing those systems is that the presence of correlation makes the explicit computation of a joint performance measure either intractable or computationally intensive. In addition, it is not well understood how and in what sense arrival correlation will improve or deteriorate a system performance measure. The objective of this paper is to provide a better understanding of the dependence structure of correlated queueing systems and to derive computable bounds for the statistics of a joint performance measure. In this paper, we obtain conditions on arrival processes under which a performance measure in two systems can be compared, in the sense of orthant and supermodular orders, among different queues and over different arrival times. Such strong comparison results enable us to study both spatial dependence (dependence among different queues) and temporal dependence (dependence over different time instances) for a joint performance measure. Further, we derive a variety of upper and lower bounds for the statistics of a stationary joint performance measure. Finally, we apply our results to synchronized queueing systems, using the ideas combined from the theory of orthant and supermodular dependence orders and majorization with respect to weighted trees (Xu and Li (2000)). Our results reveal how a performance measure can be affected, favourably or adversely, by different types of dependencies.

This paper arose from interest in assessing the quality of random number generators. The problem of testing randomness of a string of binary bits produced by such a generator gained importance with the wide use of public key cryptography and the need for secure encryption algorithms. All such algorithms are based on a generator of (pseudo) random numbers; the testing of such generators for randomness became crucial for the communications industry where digital signatures and key management are vital for information processing. The concept of approximate entropy has been introduced in a series of papers by S. Pincus and co-authors. The corresponding statistic is designed to measure the degree of randomness of observed sequences. It is based on incremental contrasts of empirical entropies based on the frequencies of different patterns in the sequence. Sequences with large approximate entropy must have substantial fluctuation or irregularity. Alternatively, small values of this characteristic imply strong regularity, or lack of randomness, in a sequence. Pincus and Kalman (1997) evaluated approximate entropies for binary and decimal expansions of e, π, √2 and √3 with the surprising conclusion that the expansion of √3 demonstrated much less irregularity than that of π. Tractable small sample distributions are hardly available, and testing randomness is based, as a rule, on fairly long strings. Therefore, to have rigorous statistical tests of randomness based on this approximate entropy statistic, one needs the limiting distribution of this characteristic under the randomness assumption. Until now this distribution remained unknown and was thought to be difficult to obtain. To derive the limiting distribution of approximate entropy we modify its definition. It is shown that the approximate entropy as well as its modified version converges in distribution to a χ2-random variable. The P-values of approximate entropy test statistics for binary expansions of e, π and √3 are plotted. Although some of these values for √3 digits are small, they do not provide enough statistical significance against the randomness hypothesis.

This paper focuses on the analyticity of the limiting behavior of a class of dynamical systems defined by iteration of non-expansive random operators. The analyticity is understood with respect to the parameters which govern the law of the operators. The proofs are based on contraction with respect to certain projective semi-norms. Several examples are considered, including Lyapunov exponents associated with products of random matrices both in the conventional algebra, and in the (max, +) semi-field, and Lyapunov exponents associated with non-linear dynamical systems arising in stochastic control. For the class of reducible operators (defined in the paper), we also address the issue of analyticity of the expectation of functionals of the limiting behavior, and connect this with contraction properties with respect to the supremum norm. We give several applications to queueing theory.

In this paper, we give necessary and sufficient conditions to ensure the validity of confidence intervals, based on the central limit theorem, in simulations of highly reliable Markovian systems. We resort to simulations because of the frequently huge state space in practical systems. So far the literature has focused on the property of bounded relative error. In this paper we focus on ‘bounded normal approximation’ which asserts that the approximation of the normal law, suggested by the central limit theorem, does not deteriorate as the reliability of the system increases. Here we see that the set of systems with bounded normal approximation is (strictly) included in the set of systems with bounded relative error.

On the basis of the Karlin and McGregor result, which states that the transition probability functions of a birth and death process can be expressed via the introduction of an orthogonal polynomial system and a spectral measure, we investigate in this paper how the Laplace transforms and the distributions of different transient characteristics related to excursions of a birth and death process can be expressed by means of the basic orthogonal polynomial system and the spectral measure. This allows us in particular to give a probabilistic interpretation of the series introduced by Stieltjes to study the convergence of the fundamental continued fraction associated with the system. Throughout the paper, we pay special attention to the case when the birth and death process is ergodic. Under the assumption that the spectrum of the spectral measure is discrete, we show how the distributions of different random variables associated with excursions depend on the fundamental continued fraction, the orthogonal polynomial system and the spectral measure.