Consider a generalized queueing network model that is subject to two types of arrivals. The first type represents the regular customers; the second type represents signals. A signal induces a regular customer already present at a node to leave. Gelenbe [5] showed that such a network possesses a product form solution when each node consists of a single exponential server. In this paper we study a number of issues concerning this class of networks. First, we explain why such networks have a product form solution. Second, we generalize existing results to include different service disciplines, state-dependent service rates, multiple job classes, and batch servicing. Finally, we establish the relationship between these networks and networks of quasi-reversible queues. We show that the product form solution of the generalized networks is a consequence of a property of the individual nodes viewed in isolation. This property is similar to the quasi-reversibility property of the nodes of a Jackson network: if the arrivals of the regular customers and of the signals at a node in isolation are independent Poisson, the departure processes of the regular customers and the signals are also independent Poisson, and the current state of the system is independent of the past departure processes.

We consider queueing networks containing customers and signals that were recently introduced in Gelenbe [4]. Both customers and signals can be exogenous or can be obtained by a Markovian transition of a customer after service. A signal entering a queue forces a customer to move on to another queue according to a Markovian routing rule or to leave the network in batch mode. This synchronized or triggered motion is useful in representing the effect of tokens in Petri-nets, for systems in which customers and work can be instantaneously moved from one queue to the other on the arrival of a signal as well as for other network behaviors that are encountered in parallel computer system modelling. We show that this network has product form stationary solution and establish the non-linear customer flow equations that govern it. Network stability is discussed in this new context.

We define a notion of regularity ordering among stochastic processes called directionally convex (dcx) ordering and give examples of doubly stochastic Poisson and Markov renewal processes where such ordering is prevalent. Further-more, we show that the class of segmented processes introduced by Chang, Chao, and Pinedo [3] provides a rich set of stochastic processes where the dcx ordering can be commonly encountered. When the input processes to a large class of queueing systems (single stage as well as networks) are dcx ordered, so are the processes associated with these queueing systems. For example, if the input processes to two tandem /M/c1→/M/c2→…→/M/cm queueing systems are dcx ordered, so are the numbers of customers in the systems. The concept of directionally convex functions (Shaked and Shanthikumar [15]) and the notion of multivariate stochastic convexity (Chang, Chao, Pinedo, and Shanthikumar [4]) are employed in our analysis.

Knockout tournaments are often used in sports (or experiments where preferences are registered by comparisons instead of measurements) to determine the champion of an event. A knockout tournament plan (KTP) for n players is a rooted binary tree with n leaves to be labeled by the n players. Each subtree of two leaves represents a match between the two players labeling the two leaves; the winner of the match then moves on to label the root of the subtree. While there are many KTPs to choose from for a given number of players, in the real world an almost balanced KTP is usually chosen. One reason could be the perception that a balanced KTP is “fair” to the players, in the sense that, given a random labeling of leaves by players, a stronger player has a better chance to win the tournament. Surprisingly, it has been shown that not all KTPs have this property, and it is difficult to prove this property for any general class of KTPs. So far the property has been shown to hold only for balanced KTPs. In this paper we extend it to some classes of almost balanced KTPs.

We consider N sites (N ≤ ∞), each of which may be either occupied or unoccupied. Time is discrete, and at each time unit a set of occupied sites may attempt to capture a previously unoccupied site. The attempt will be successful with a probability that depends on the number of sites making the attempt, in which case the new site will also be occupied. A benefit is gained when new sites are occupied, but capture attempts are costly. The problem of optimal occupation is formulated as a Markov decision process in which the admissible actions are occupation strategies and the cost is a function of the strategy and the number of occupied sites. A partial order on the state-action pairs is used to obtain a comparison result for stationary policies and qualitative results concerning monotonicity of the value function for the n-stage problem (n ≤ ∞). The optimal policies are partially characterized when the cost depends on the action only through the total number of occupation attempts made.

We consider the following problem. For a given population of m items, we have to make a decision whether or not the population includes a relatively large cluster of identical items. This decision affects the effectiveness of a subsequent computational process, depending on the actual existence of the cluster and its size. To make a good decision, we use a statistical sample which should indicate the existence of a cluster and find a representative thereof. This paper describes the optimal sampling technique to be used in such a case, given the cost of the sampling and the potential gain in speed of the subsequent process. The optimal fixed sample size is specified, as well as the optimal sequential sampling, along with characterizing the dependence of the cost function on the truncation point.

For the case that the a priori distribution of the cluster proportion is known, we present formulae by which the optimal sampling procedures can be easily calculated. For the common situation in which the a priori distribution is not known, we present, in the case of a fixed sample size, a tight upper bound for the sample size, which is independent of the a priori distribution, and for the case of the sequential sampling, we present an approximately optimal truncation point, which is also independent of the a priori distribution.

The situation described arose in connection with choosing the best sorting method, an application that will be described in full detail. The most interesting practical result is that for our application truncating the sequential procedure at 35 observations, out of a population of 25,000–30,000 items, guarantees that in our sorting application we are always within 2.1% of the optimal cost independently of the a priori distribution.

Directed acyclic independence graphs (DAIGs) play an important role in recent developments in probabilistic expert systems and influence diagrams (Chyu [1]). The purpose of this note is to show that DAIGs can usefully be grouped into equivalence classes where the members of a single class share identical Markov properties. These equivalence classes can be identified via a simple graphical criterion. This result is particularly relevant to model selection procedures for DAIGs (see, e.g., Cooper and Herskovits [2] and Madigan and Raftery [4]) because it reduces the problem of searching among possible orientations of a given graph to that of searching among the equivalence classes.

Interest in the informational content of truncation motivates the study of the residual entropy function, that is, the entropy of a right truncated random variable as a function of the truncation point. In this note we show that, under mild regularity conditions, the residual entropy function characterizes the probability distribution. We also derive relationships among residual entropy, monotonicity of the failure rate, and stochastic dominance. Information theoretic measures of distances between distributions are also revisited from a similar perspective. In particular, we study the residual divergence between two positive random variables and investigate some of its monotonicity properties. The results are relevant to information theory, reliability theory, search problems, and experimental design.

Let [NA(t), t≥0] and [NB(t), t≥0] be two counting processes with independent interarrivals Ai and Bi, respectively, i ∈ + ≡ [1,2,… ], and let [Xi, i ∈ +] and [Yi, i ∈ +] be two sequences of independent non-negative random variables. Consider the two compound processes [U(t), t ≥ 0] and [V(t), t ≥ 0] defined as U(t) = Xi, t ≥ 0, and V(t) = Yi, t ≥ 0. Then it is well known (and not hard to verify) that if the Ai's are independent of the Xi's, and if the Bi's are independent of the yi's, and if Ai ≥st Bi and Xi ≤st Yi, for all i ∈ +, then [U(t), t ≥ 0] ≤st [V(t), t ≥ 0]. In this paper we provide conditions under which this stochastic order relation holds even if Ai ≤st Bi and/or Xi ≥st Yi for all i ∈ +. In fact, we derive the stochastic order relationships among processes that are much more general than the cumulative ones described above. For example, it is not necessarily assumed that the Ai's are independent of the Xi's or that the Bi's are independent of the Yi's. Examples that illustrate the applications of the theory are included.

Let X be a continuous random variable denoting the lifetime of a unit. Let Xk:n denote the kth order statistic based on n independent random observations on X. It has been shown that if Xk:n has decreasing failure rate (DFR) for some k, 1 ≤ k ≤ n, then X is DFR. For n ≥ 2, if Xk:n has increasing failure rate (IFR), then Xk:n–1 is also IFR, and if Xk:n is DFR, then Xk:n+1 is also DFR. The log concavity of the density, function is shown to be preserved by the kth order statistic. It has been established that if the density function of Xk:n is log convex then the density function of Xk:n+1 is also log convex. Because a k-out-of-n system of i.i.d. components each having a life distribution that of X has lifetime Xn-k+1:n the results have applications in the study of such systems.