Distribution of sample correlation coefficients

Let (Y, X_l,…, X_K) be a random vector distributed according to a multivariate normal distribution where X_l,…, X_K are considered as predictor variables and y is the predictand. Let r_i, and R_i denote the population and sample correlation coefficients, respectively, between Y and X_i. The population correlation coefficient r_i is a measure of the predictive power of X_i. The author has derived the joint distribution of R_l,…, R_K and its asymptotic property. The given result is useful in the problem of selecting the most important predictor variable corresponding to the largest absolute value of r_i.     

The asymptotic distribution of order statistics

For each n., X₁(n), X₂(n), …, X_n(n) are IID, with common pdf f_n(x). y₁(n) < … < Y_n (n) are the ordered values of X₁ (n), …, X_n(n). K_n is a positive integer, with lim K_n = ∞. Under certain conditions on K_n and f_n (x), it was shown in an earlier paper that the joint distribution of a special set of K_n + 1 of the variables Y₁ (n), …, Y_n (n) can be assumed to be normal for all asymptotic probability calculations. In another paper, it was shown that if f_n (x) approaches the pdf which is uniform over (0, 1) at a certain rate as n increases, then the conditional distribution of the order statistics not in the special set can be assumed to be uniform for all asymptotic probability calculations. The present paper shows that even if f_n (x) does not approach the uniform distribution as n increases, the distribution of the order statistics contained between order statistics in the special set can be assumed to be the distribution of a quadratic function of uniform random variables, for all asymptotic probability calculations. Applications to statistical inference are given.     

Technical note: Find a hidden “treasure”

This paper deals with a two searchers game and it investigates the problem of how the possibility of finding a hidden object simultaneously by players influences their behavior. Namely, we consider the following two‐sided allocation non‐zero‐sum game on an integer interval [1,n]. Two teams (Player 1 and 2) want to find an immobile object (say, a treasure) hidden at one of n points. Each point i ∈ [1,n] is characterized by a detection parameter λ_i (μ_i) for Player 1 (Player 2) such that p_i(1 ? exp(?λ_ix_i)) (p_i(1 ? exp(?μ_iy_i))) is the probability that Player 1 (Player 2) discovers the hidden object with amount of search effort x_i (y_i) applied at point i where p_i ∈ (0,1) is the probability that the object is hidden at point i. Player 1 (Player 2) undertakes the search by allocating the total amount of effort X(Y). The payoff for Player 1 (Player 2) is 1 if he detects the object but his opponent does not. If both players detect the object they can share it proportionally and even can pay some share to an umpire who takes care that the players do not cheat each other, namely Player 1 gets q₁ and Player 2 gets q₂ where q₁ + q₂ ≤ 1. The Nash equilibrium of this game is found and numerical examples are given. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Johnson's approximate method for the 3 × n job shop problem

The effectiveness of Johnson's Approximate Method (JAM) for the 3 × n job shop scheduling problems was examined on 1,500 test cases with n ranging from 6 to 50 and with the processing times A_i, B_i, C_i (for item i on machines A, B, C) being uniformly and normally distributed. JAM proved to be quite effective for the case B_i ? max (A_i, C_i) and optimal for B_i, ? min (A_i, C_i).     

Characterizations of the exponential distribution by higher-order gap

Suppose X₁,X₂, ?,X_n is a random sample of size n from a continuous distribution function F(x) and let X_1,n, ≦ X_2,n ≦ ? ≦ X_n,n be the corresponding order statistics. We define the jth-order gap g_i,j as g_i,j = X_i+j,n ? X_i,n, 1 ≦ i < n, 1 ≦ j ≦ n ? i. In this article characterizations of the exponential distribution are given by considering the distributional properties of g_k,n-k, 1 ≦ k ≦ n.     

Reliability of a 2‐dimensional k‐within‐consecutive‐r × s‐out‐of‐m × n:F system

A 2‐dimensional rectangular (cylindrical) k‐within‐consecutive‐r × s‐out‐of‐m × n:F system is the rectangular (cylindrical) m × n‐system if the system fails whenever k components in a r × s‐submatrix fail. This paper proposes a recursive algorithm for the reliability of the 2‐dimensional k‐within‐consecutive‐r × s‐out‐m × n:F system, in the rectangular case and the cylindrical case. This algorithm requires min ( O (mk^r(n?s)), O (nk^s(m?r))), and O (mk^rn) computing time in the rectangular case and the cylindrical case, respectively. The proposed algorithm will be demonstrated and some numerical examples will be shown. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 625–637, 2001.     

On estimating survival for reliability models based on age-related stochastic comparisons

A new class of nonparametric reliability models is introduced and studied. A distribution is said to be better at age s than at age t (sBt) if the residual lifetime at age s is stochastically greater than or equal to the residual lifetime at age t. Applications to various forms of replacement policies, including the cannibalization of failed systems, are noted. For fixed s < t, the problem of estimating a survival curve assumed to belong to the sBt class is addressed using recursive methods. An sBt estimator is derived in closed form, and its uniform strong consistency at an optimal rate of convergence is demonstrated. A simulation study strongly supports the claim that the sBt estimator tends to outperform the empirical survivor function in small- and moderate-size samples. © 1993 John Wiley & Sons, Inc.     

On the number of games played in a best of (2n – 1) series

Let p(⩾0.5) denote the probability that team A beats B in a single game. The series continues until either A or B wins n games. Assuming that these games are independent replications, we study some features of the distribution of X_n, the number of games played in the series. It is shown that X_n is unimodal, has an IFRA distribution, and is stochastically decreasing in p. Close approximations to its mode, mean, and variance are given. Finally, it is shown that the maximum-likelihood estimator of p based on X_n is unique.     

A characterization of the wald distribution

Suppose X is a random variable having an absolutely continuous distribution function F(x). We assume that F(x) has the Wald distribution. A relation between the probability density function of X⁻¹ with that of X is used to characterize the Wald distribution.     

On labeling the vertices of products of complete graphs with distance constraints

Variations of Hale's channel assignment problem, the L(j, k)‐labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph G subject to various distance constraints. The λ_j,k‐number of G and the radio number of G are respectively the minimum span among all L(j, k)‐labelings, and the minimum span plus 1 of all radio labelings of G (defined in the Introduction). In this paper, we establish the λ_j,k‐number of ∏ K for pairwise relatively prime integers t₁ < t₂ < … < t_q, t₁ ≥ 2. We also show the existence of an infinite class of graphs G with radio number |V(G)| for any diameter d(G). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

A remark on a helicopter and submarine game

The article considers a two-person zero-sum game in which the movement of the players is constrained to integer points …, −1, 0, 1, … of a line L. Initially the searcher (hider) is at point x = 0 (x = d, d > 0). The searcher and the hider perform simple motion on L with maximum speeds w and u, respectively, where w > u > 0. Each of the players knows the other's initial position but not the other's subsequent positions. The searcher has a bomb which he can drop at any time during his search. Between the dropping of the bomb and the bomb exploding there is a T time lag. If the bomb explodes at point i and the hider is at point i − 1, or i, or i + 1, then the destruction probability is equal to P, or 1, or P, respectively, where 0 < P < 1. d, w, u, and T are integer constants. The searcher can drop the bomb at integer moments of time t = 0, 1, … . The aim of the searcher is to maximize the probability of the destruction of the hider. © 1993 John Wiley & Sons, Inc.     

Optimal policies for M/M/m queue with two different kinds of (N,T)‐policies

In this paper, two different kinds of (N, T)‐policies for an M/M/m queueing system are studied. The system operates only intermittently and is shut down when no customers are present any more. A fixed setup cost of K > 0 is incurred each time the system is reopened. Also, a holding cost of h > 0 per unit time is incurred for each customer present. The two (N, T)‐policies studied for this queueing system with cost structures are as follows: (1) The system is reactivated as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T, and (2) the system is reactivated as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. The equations satisfied by the optimal policy (N*, T*) for minimizing the long‐run average cost per unit time in both cases are obtained. Particularly, we obtain the explicit optimal joint policy (N*, T*) and optimal objective value for the case of a single server, the explicit optimal policy N* and optimal objective value for the case of multiple servers when only predefined customers number N is measured, and the explicit optimal policy T* and optimal objective value for the case of multiple servers when only predefined time units T is measured, respectively. These results partly extend (1) the classic N or T policy to a more practical (N, T)‐policy and (2) the conclusions obtained for single server system to a system consisting of m (m ≥ 1) servers. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 240–258, 2000     

An application of the reflection principle to the transient analysis of the M/M/1 queue

This paper applies the well-known reflection principle for random walks to the analysis of the transient M/M/1 queueing system. A closed-form solution is obtained for the probability that exactly i arrivals and j departures occur over an interval of length t in an M/M/1 queueing system that contains n users at the beginning of the interval. The derivation of this probability is based on the calculation of the number of paths between two points in a two-dimensional −y coordinate system that lie above the x axis and touch the x axis exactly r times. This calculation is readily performed through the application of the reflection principle.     

On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A O(nm log(U/n)) time maximum flow algorithm

In this paper, we present an O(nm log(U/n)) time maximum flow algorithm. If U = O(n) then this algorithm runs in O(nm) time for all values of m and n. This gives the best available running time to solve maximum flow problems satisfying U = O(n). Furthermore, for unit capacity networks the algorithm runs in O(n^2/3m) time. It is a two‐phase capacity scaling algorithm that is easy to implement and does not use complex data structures. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 511–520, 2000     

Graph distance‐dependent labeling related to code assignment in computer networks

For nonnegative integers d₁, d₂, and L(d₁, d₂)‐labeling of a graph G, is a function f : V(G) → {0, 1, 2, …} such that |f(u) − f(v)| ≥ d_i whenever the distance between u and v is i in G, for i = 1, 2. The L(d₁, d₂)‐number of G, λ(G) is the smallest k such that there exists an L(d₁, d₂)‐labeling with the largest label k. These labelings have an application to a computer code assignment problem. The task is to assign integer “control codes” to a network of computer stations with distance restrictions, which allow d₁ ≤ d₂. In this article, we will study the labelings with (d₁, d₂) ∈ {(0, 1), (1, 1), (1, 2)}. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Scheduling with earliest start and due date constraints on multiple machines

We consider the scheduling of n jobs on m identical machines when the jobs become available for processing at ready times a_i, a_i, ? 0, require d_i time units for processing and must be completed by times b_i for i = 1, 2, … n. The objective chosen is that of minimizing the total elapsed time to complete all jobs subject to the ready time and due date constraints, preemption is not allowed. We present a multi-stage solution algorithm for this problem that is based on an implicit enumeration procedure and also uses the labelling type algorithm which solves the problem when preemption is allowed.     

On the rectangular p-center problem

The p-center problem involves finding the best locations for p facilities such that the furthest among n points is as close as possible to one of the facilities. Rectangular (sometimes called rectilinear, Manhattan, or l₁) distances are considered. An O(n) algorithm for the 1-center problem, an O(n) algorithm for the 2-center problem, and an O(n logn) algorithm for the 3-center problem are given. Generalizations to general p-center problems are also discussed.     

Steady-state analysis of load balancing with Coxian-2 distributed service times

This paper studies load balancing for many-server (N servers) systems. Each server has a buffer of size b ? 1, and can have at most one job in service and b ? 1 jobs in the buffer. The service time of a job follows the Coxian-2 distribution. We focus on steady-state performance of load balancing policies in the heavy traffic regime such that the normalized load of system is λ = 1 ? N^?α for 0 < α < 0.5. We identify a set of policies that achieve asymptotic zero waiting. The set of policies include several classical policies such as join-the-shortest-queue (JSQ), join-the-idle-queue (JIQ), idle-one-first (I1F) and power-of-d-choices (Po d) with d = O(N^α log N). The proof of the main result is based on Stein's method and state space collapse. A key technical contribution of this paper is the iterative state space collapse approach that leads to a simple generator approximation when applying Stein's method.