By variously killing a stable Lévy process when it leaves the positive half-line, conditioning it to stay positive, and conditioning it to hit 0 continuously, we obtain three different, positive, self-similar Markov processes which illustrate the three classes described by Lamperti (1972). For each of these processes, we explicitly compute the infinitesimal generator and from this deduce the characteristics of the underlying Lévy process in the Lamperti representation. The proof of this result bears on the behaviour at time 0 of stable Lévy processes before their first passage time across level 0, which we describe here. As an application, for a certain class of Lévy processes we give the law of the minimum before an independent exponential time. This provides the explicit form of the spatial Wiener-Hopf factor at a particular point and the value of the ruin probability for this class of Lévy processes.

We discuss two Monte Carlo algorithms for finding the global maximum of a simple random walk with negative drift. This problem can be used to connect the analysis of random input Monte Carlo algorithms with ideas and principles from mathematical statistics.

The trie is a sort of digital tree. Ideally, to achieve balance, the trie should grow from an unbiased source generating keys of bits with equal likelihoods. In practice, the lack of bias is not always guaranteed. We investigate the distance between randomly selected pairs of nodes among the keys in a biased trie. This research complements that of Christophi and Mahmoud (2005); however, the results and some of the methodology are strikingly different. Analytical techniques are still useful for moments calculation. Both mean and variance are of polynomial order. It is demonstrated that the standardized distance approaches a normal limiting random variable. This is proved by the contraction method, whereby the limit distribution is shown to approach the fixed-point solution of a distributional equation in the Wasserstein metric space.

In a recent paper, Kleinberg (2000) considered a small-world network model consisting of a d-dimensional lattice augmented with shortcuts. The probability of a shortcut being present between two points decays as a power, r-α, of the distance, r, between them. Kleinberg showed that greedy routeing is efficient if α = d and that there is no efficient decentralised routeing algorithm if α ≠ d. The results were extended to a continuum model by Franceschetti and Meester (2003). In our work, we extend the result to more realistic models constructed from a Poisson point process wherein each point is connected to all its neighbours within some fixed radius, and possesses random shortcuts to more distant nodes as described above.

A full-information version of the secretary problem in which the objective is to maximize the time of possession of a relatively best object is considered both in the case in which only the most recently observed object may be chosen and in the case in which any of the previously observed objects may be chosen. The main purpose of this paper is to obtain, under an optimal rule, both the asymptotic proportional durations when the number of objects tends to infinity, and the expected durations when the number of objects remains finite. The integral expressions for these asymptotic values are derived in both cases: the approximate numerical values are 0.435 in the former (no-recall) case and 0.449 in the latter (recall) case, indicating a surprisingly small difference. The expected values of the optimal stopping times are also obtained from the planar Poisson process analysis.

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.

In this paper we consider stochastic recursive equations of sum type, , and of max type, , where Ai, bi, and b are random, (Xi) are independent, identically distributed copies of X, and denotes equality in distribution. Equations of these types typically characterize limits in the probabilistic analysis of algorithms, in combinatorial optimization problems, and in many other problems having a recursive structure. We develop some new contraction properties of minimal Ls-metrics which allow us to establish general existence and uniqueness results for solutions without imposing any moment conditions. As an application we obtain a one-to-one relationship between the set of solutions to the homogeneous equation and the set of solutions to the inhomogeneous equation, for sum- and max-type equations. We also give a stochastic interpretation of a recent transfer principle of Rösler from nonnegative solutions of sum type to those of max type, by means of random scaled Weibull distributions.

We consider the problem of optimally stopping a general one-dimensional Itô diffusion X. In particular, we solve the problem that aims at maximising the performance criterion Ex[exp(-∫0τr(Xs)ds)f(Xτ)] over all stopping times τ, where the reward function f can take only a finite number of values and has a ‘staircase’ form. This problem is partly motivated by applications to financial asset pricing. Our results are of an explicit analytic nature and completely characterise the optimal stopping time. Also, it turns out that the problem's value function is not C1, which is due to the fact that the reward function f is not continuous.

We consider a stochastic process in a modified Ehrenfest urn model. The modification prescribes there to be a minimum number of balls in each urn, and the process records the differences between treatment assignments under a sampling scheme implemented with this modified Ehrenfest urn model. In contrast to the result that the difference process forms a Markov chain and converges to a stationary distribution under the Ehrenfest urn model, the corresponding process under this modified Ehrenfest urn design satisfies the central limit property. We prove this asymptotic normality property using a central limit theorem for dependent random variables, renewal theory, and two Kolmogorov-type maximal inequalities.

We consider the optimal stopping problem for g(Zn), where Zn, n = 1, 2, …, is a homogeneous Markov sequence. An algorithm, called forward improvement iteration, is presented by which an optimal stopping time can be computed. Using an iterative step, this algorithm computes a sequence B0 ⊇ B1 ⊇ B2 ⊇ · · · of subsets of the state space such that the first entrance time into the intersection F of these sets is an optimal stopping time. Various applications are given.

We characterize the (continuous) majorization of integrable functions introduced by Hardy, Littlewood, and Pólya in terms of the (discrete) majorization of finite-dimensional vectors, introduced by the same authors. The most interesting version of this result is the characterization of the (increasing) convex order for integrable random variables in terms of majorization of vectors of expected order statistics. Such a result includes, as particular cases, previous results by Barlow and Proschan and by Alzaid and Proschan, and, in a sense, completes the picture of known results on order statistics. Applications to other stochastic orders are also briefly considered.

We consider a diffusion process X(t) with a one-sided Brownian potential starting from the origin. The limiting behavior of the process as time goes to infinity is studied. For each t > 0, the sample space describing the random potential is divided into two parts, Ãt and B̃t, both having probability ½, in such a way that our diffusion process X(t) exhibits quite different limiting behavior depending on whether it is conditioned on Ãt or on B̃t (t → ∞). The asymptotic behavior of the maximum process of X(t) is also investigated. Our results improve those of Kawazu, Suzuki, and Tanaka (2001).

It was recently proved by Jelenković and Radovanović (2004) that the least-recently-used (LRU) caching policy, in the presence of semi-Markov-modulated requests that have a generalized Zipf's law popularity distribution, is asymptotically insensitive to the correlation in the request process. However, since the previous result is asymptotic, it remains unclear how small the cache size can become while still retaining the preceding insensitivity property. In this paper, assuming that requests are generated by a nearly completely decomposable Markov-modulated process, we characterize the critical cache size below which the dependency of requests dominates the cache performance. This critical cache size is small relative to the dynamics of the modulating process, and in fact is sublinear with respect to the sojourn times of the modulated chain that determines the dependence structure.

We discuss the limit behavior of the partial sums process of stationary solutions to the (autoregressive) AR(1) equation Xt = atXt−1 + εt with random (renewal-reward) coefficient, at, taking independent, identically distributed values Aj ∈ [0,1] on consecutive intervals of a stationary renewal process with heavy-tailed interrenewal distribution, and independent, identically distributed innovations, εt, belonging to the domain of attraction of an α-stable law (0 < α ≤ 2, α ≠ 1). Under suitable conditions on the tail parameter of the interrenewal distribution and the singularity parameter of the distribution of Aj near the unit root a = 1, we show that the partial sums process of Xt converges to a λ-stable Lévy process with index λ < α. The paper extends the result of Leipus and Surgailis (2003) from the case of finite-variance Xt to that of infinite-variance Xt.

We consider risk processes with reinsurance. A general family of reinsurance contracts is allowed, including proportional and excess-of-loss policies. Claim occurrence is regulated by a classical compound Poisson process or by a Markov-modulated compound Poisson process. We provide some large deviation results concerning these two risk processes in the small-claim case. Finally, we derive the so-called Lundberg estimate for the ruin probabilities and present a numerical example.

Let {X(s, t), s = (s1, s2) ∈ ℝ2, t ∈ ℝ} be a stationary random field defined over a discrete lattice. In this paper, we consider a set of domain of attraction criteria giving the notion of extremal index for random fields. Together with the extremal-types theorem given by Leadbetter and Rootzen (1997), this will give a characterization of the limiting distribution of the maximum of such random fields.

Methods using gambling teams and martingales are developed and applied to find formulae for the expected value and the generating function of the waiting time to observation of an element of a finite collection of patterns in a sequence generated by a two-state Markov chain of first, or higher, order.

A continuous-time model with stationary increments for asset price {Pt} is an extension of the symmetric subordinator model of Heyde (1999), and allows for skewness of returns. In the setting of independent variance-gamma-distributed returns the model resembles closely that of Madan, Carr, and Chang (1998). A simple choice of parameters renders {e−rtPt} a familiar martingale. We then specify the activity time process, {Tt}, for which {Tt − t} is asymptotically self-similar and {τt}, with τt = Tt − Tt−1, is gamma distributed. This results in a skew variance-gamma distribution for each log price increment (return) Xt and a model for {Xt} which incorporates long-range dependence in squared returns. Our approach mirrors that for the (symmetric) Student process model of Heyde and Leonenko (2005), to which the present work is intended as a complement and a sequel. One intention is to compare, partly on the basis of fitting to data, versions of the general model wherein the returns have either (symmetric) t-distributions or variance-gamma distributions.

A sequence of objects with independent, identically distributed qualities is presented to a selector who must choose two on-line, i.e. without anticipation or recall. The selector's aim is to obtain a satisfactory pair as quickly as possible. Two versions of the problem are considered, and optimal selection rules are derived and compared. An investigation is also made of a heuristic rule suitable for a selector who has no prior knowledge of the nature of the object sequence.

In this paper we introduce the concepts of instantaneous reversibility and instantaneous entropy production rate for inhomogeneous Markov chains with denumerable state spaces. The following statements are proved to be equivalent: the inhomogeneous Markov chain is instantaneously reversible; it is in detailed balance; its entropy production rate vanishes. In particular, for a time-periodic birth-death chain, which can be regarded as a simple version of a physical model (Brownian motors), we prove that its rotation number is 0 when it is instantaneously reversible or periodically reversible. Hence, in our model of Markov chains, the directed transport phenomenon of Brownian motors can occur only in nonequilibrium and irreversible systems.