Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process

Quasi-birth-and-death (QBD) processes with infinite “phase spaces” can exhibit unusual and interesting behavior. One of the simplest examples of such a process is the two-node tandem Jackson network, with the “phase” giving the state of the first queue and the “level” giving the state of the second queue. In this paper, we undertake an extensive analysis of the properties of this QBD. In particular, we investigate the spectral properties of Neuts’s R-matrix and show that the decay rate of the stationary distribution of the “level” process is not always equal to the convergence norm of R. In fact, we show that we can obtain any decay rate from a certain range by controlling only the transition structure at level zero, which is independent of R. We also consider the sequence of tandem queues that is constructed by restricting the waiting room of the first queue to some finite capacity, and then allowing this capacity to increase to infinity. We show that the decay rates for the finite truncations converge to a value, which is not necessarily the decay rate in the infinite waiting room case. Finally, we show that the probability that the process hits level n before level 0 given that it starts in level 1 decays at a rate which is not necessarily the same as the decay rate for the stationary distribution.

A fast cross-entropy method for estimating buffer overflows in queuing networks

In this paper, we propose a fast adaptive importance sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First, we estimate the minimum cross-entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level. Finally, the tilting parameter just found is used to estimate the overflow probability of interest. We study various properties of the method in more detail for the M/M/1 queue and conjecture that similar properties also hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

An improved seeded region growing algorithm

Recently Adams and Bischof (1994) proposed a novel region growing algorithm for segmenting intensity images. The inputs to the algorithm are the intensity image and a set of seeds - individual points or connected components - that identify the individual regions to be segmented. The algorithm grows these seed regions until all of the image pixels have been assimilated. Unfortunately the algorithm is inherently dependent on the order of pixel processing. This means, for example, that raster order processing and anti-raster order processing do not, in general, lead to the same tessellation. In this paper we propose an improved seeded region growing algorithm that retains the advantages of the Adams and Bischof algorithm fast execution, robust segmentation, and no tuning parameters - but is pixel order independent. (C) 1997 Elsevier Science B.V.

Formal derivation of finite state machines for class testing

Previous work on generating state machines for the purpose of class testing has not been formally based. There has also been work on deriving state machines from formal specifications for testing non-object-oriented software. We build on this work by presenting a method for deriving a state machine for testing purposes from a formal specification of the class under test. We also show how the resulting state machine can be used as the basis for a test suite developed and executed using an existing framework for class testing. To derive the state machine, we identify the states and possible interactions of the operations of the class under test. The Test Template Framework is used to formally derive the states from the Object-Z specification of the class under test. The transitions of the finite state machine are calculated from the derived states and the class's operations. The formally derived finite state machine is transformed to a ClassBench testgraph, which is used as input to the ClassBench framework to test a C++ implementation of the class. The method is illustrated using a simple bounded queue example.

Experimental evidence that partner choice is a driving force in the payoff distribution among cooperators or mutualists: the cleaner fish case

Supply and demand largely determine the price of goods on human markets. It has been proposed that in animals, similar forces influence the payoff distribution between trading partners in Sexual selection, intraspecific cooperation and interspecific mutualism. Here we present the first experimental evidence supporting biological market theory in it study on cleaner fish, Labroides dimidiatus. Cleaners interact with two classes of clients: choosy client species with access to several cleaners usually do not queue for service and do not return if ignored, while resident client species with access to only one cleaning station do queue or return. We used plexiglas plates with equal amounts of food to stimulate these behaviours of the two client classes. Cleaners soon inspected 'choosy' plates before 'resident' plates. This supports previous field observations that suggest that client species with access to several cleaners exert choice to receive better(immediate) service.

Divorce, dispersal and incest avoidance in the cooperatively breeding superb fairy-wren Malurus cyaneus

1. Between 1988 and 2001, we studied social relationships in the superb fairy-wren Malurus cyaneus (Latham), a cooperative breeder with male helpers in which extra-group fertilizations are more common than within-pair fertilizations. 2. Unlike other fairy-wren species, females never bred on their natal territory. First-year females dispersed either directly from their natal territory to a breeding vacancy or to a foreign 'staging-post' territory where they spent their first winter as a subordinate. Females dispersing to a foreign territory settled in larger groups. Females on foreign territories inherited the territory if the dominant female died, and were sometimes able to split the territory into two by pairing with a helper male. However, most dispersed again to obtain a vacancy. 3. Females dispersing from a staging post usually gained a neighbouring vacancy, but females gaining a vacancy directly from their natal territory travelled further, perhaps to avoid pairing or mating with related males. 4. Females frequently divorced their partner, although the majority of relationships were terminated by the death of one of the pair. If death did not intervene, one-third of pairings were terminated by female-initiated divorce within 1000 days. 5. Three divorce syndromes were recognized. First, females that failed to obtain a preferred territory moved to territories with more helpers. Secondly, females that became paired to their sons when their partner died usually divorced away from them. Thirdly, females that have been in a long relationship divorce once a son has gained the senior helper position. 6. Dispersal to avoid pairing with sons is consistent with incest avoidance. However, there may be two additional benefits. Mothers do not mate with their sons, so dispersal by the mother liberates her sons to compete for within-group matings. Further, divorcing once their son has become a breeder or a senior helper allows the female to start sons in a queue for dominance on another territory. Females that do not take this option face constraints on their ability to recruit more sons into the local neighbourhood.

Heavy tails, importance sampling and cross-entropy

We consider the problem of estimating P(Yi + (...) + Y-n > x) by importance sampling when the Yi are i.i.d. and heavy-tailed. The idea is to exploit the cross-entropy method as a toot for choosing good parameters in the importance sampling distribution; in doing so, we use the asymptotic description that given P(Y-1 + (...) + Y-n > x), n - 1 of the Yi have distribution F and one the conditional distribution of Y given Y > x. We show in some specific parametric examples (Pareto and Weibull) how this leads to precise answers which, as demonstrated numerically, are close to being variance minimal within the parametric class under consideration. Related problems for M/G/l and GI/G/l queues are also discussed.

Subgeometric rates of convergence for a class of continuous-time Markov process

Let (Phi(t))(t is an element of R+) be a Harris ergodic continuous-time Markov process on a general state space, with invariant probability measure pi. We investigate the rates of convergence of the transition function P-t(x, (.)) to pi; specifically, we find conditions under which r(t) vertical bar vertical bar P-t (x, (.)) - pi vertical bar vertical bar -> 0 as t -> infinity, for suitable subgeometric rate functions r(t), where vertical bar vertical bar - vertical bar vertical bar denotes the usual total variation norm for a signed measure. We derive sufficient conditions for the convergence to hold, in terms of the existence of suitable points on which the first hitting time moments are bounded. In particular, for stochastically ordered Markov processes, explicit bounds on subgeometric rates of convergence are obtained. These results are illustrated in several examples.

Improved algorithms for rare event simulation with heavy tails

The estimation of P(S-n > u) by simulation, where S, is the sum of independent. identically distributed random varibles Y-1,..., Y-n, is of importance in many applications. We propose two simulation estimators based upon the identity P(S-n > u) = nP(S, > u, M-n = Y-n), where M-n = max(Y-1,..., Y-n). One estimator uses importance sampling (for Y-n only), and the other uses conditional Monte Carlo conditioning upon Y1,..., Yn-1. Properties of the relative error of the estimators are derived and a numerical study given in terms of the M/G/1 queue in which n is replaced by an independent geometric random variable N. The conclusion is that the new estimators compare extremely favorably with previous ones. In particular, the conditional Monte Carlo estimator is the first heavy-tailed example of an estimator with bounded relative error. Further improvements are obtained in the random-N case, by incorporating control variates and stratification techniques into the new estimation procedures.