Exact confidence coefficients of simultaneous confidence intervals for multinomial proportions

Simultaneous confidence intervals for multinomial proportions are useful in many areas of science. Since 1964, approximate simultaneous 1-α confidence intervals have been proposed for multinomial proportions. Although at each point in the parameter space, these confidence sets have asymptotic 1-α coverage probability, the exact confidence coefficients of these simultaneous confidence intervals for a fixed sample size are unknown before.In this paper, we propose a procedure for calculating exact confidence coefficients for simultaneous confidence intervals of multinomial proportions for any fixed sample size. With this methodology, exact confidence coefficients can be clearly derived, and the point at which the infimum of the coverage probability occurs can be clearly identified.     

Modeling the coverage probability of a confidence interval on the among-group variance component in the unbalanced random one-way model

The coverage probability of an approximate confidence interval on the among-group variance component, σ _α ² , in a one-way random model is modeled using generalized linear models techniques. The purpose of the proposed modeling is to derive an empirical relationship between the coverage probability on one hand, andk, n., ?, and the model’s variance components on the other hand, wherek is the number of groups, n. is the total number of observations, and ? is a measure of imbalance for the design used. The latter quantities serve as control variables in the derived model, and the coverage probability is treated as the response variable. Contour plots generated from this model can be easily used to depict the effects of the control variables on the coverage probability. In particular, the plots are utilized to compare four methods for constructing approximate confidence intervals on σ _α ² . Additional advantages of the derived model include prediction of the coverage probability for a given method using only specified values of the control variables, and the determination of operating conditions that result in improved coverage probability within the region of interest.     

On additive maps of prime rings satisfying the engel condition

Let A be a prime ring with nonzero right ideal R and f : R → A an additive map. Next, let k,n₁, n₂,…,n_k be natural numbers. Suppose that […[[(x), xn¹], xn²],…, xn^k]=0 for all x ∈ R. Then it is proved in Theorem 1.1 that [f(x),x]=0 provided that either char(A)=0 or char (A)> n₁+n₂+ …+n_k Theorem 1.1 is a simultaneous generalization of a number of results proved earlier.     

On chromatic uniqueness of two infinite families of graphs

In this paper, it is proven that for each k ≥ 2, m ≥ 2, the graph Θ_k(m,…,m), which consists of k disjoint paths of length m with same ends is chromatically unique, and that for each m, n, 2 ≤ m ≤ n, the complete bipartite graph K_m,n is chromatically unique. © 1993 John Wiley & Sons, Inc.     

Mixing Properties and Central Limit Theorem for a Class of Non-Identical Piecewise Monotonic C2 — Transformations

For a sequence T⁽¹⁾, T⁽²⁾,…of piecewise monotonic C² - transformations of the unit interval I onto itself, we prove exponential ψ- mixing, an almost Markov property and other higher-order mixing properties. Furthermore, we obtain optimal rates of convergence in the central limit Theorem and large deviation relations for the sequence f_k oT(k?1)o…oT⁽¹⁾, k=1, 2, …, provided that the real-valued functions f₁, f₂,…on I are of bounded variation and the corresponding probability measure on I possesses a positive, Lipschitz-continuous Lebesgue density.     

Old and new designs via difference multisets and strong difference families

Let X =((x_1,1,x_1,2,…,x_1,k),(x_2,1,x_2,2,…,x_2,k),…,(x_t,1,x_t,2,…,x_t,k)) be a family of t multisets of size k defined on an additive group G. We say that X is a t-(G,k,μ) strong difference family (SDF) if the list of differences (x_h,i-x_h,j∣h=1,…,t;i≠ j) covers all of G exactly μ times. If a SDF consists of a single multiset X, we simply say that X is a (G,k,μ) difference multiset. After giving some constructions for SDF's, we show that they allow us to obtain a very useful method for constructing regular group divisible designs and regular (or 1-rotational) balanced incomplete block designs. In particular cases this construction method has been implicitly used by many authors, but strangely, a systematic treatment seems to be lacking. Among the main consequences of our research, we find new series of regular BIBD's and new series of 1-rotational (in many cases resovable) BIBD's.     

On maximal antichains containing no set and its complement

Let 1?k₁?k₂?…?k_n be integers and let S denote the set of all vectors x = (x₁, …, x_n with integral coordinates satisfying 0?x_i?k_i, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of k_i elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities x_i?y_i, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k₁ + k₂ + …k_n. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k₁-x₁, k₂-x₂, …, k_n -x_n). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and$\text{|(}\text{1}\text{2}\text{K)X|}$ does not exceed the number of vectors in $\text{(}\text{1}\text{2}\text{K)S}$ with first coordinate different from k₁, then

$\text{∑}\text{i=0}\text{K}\text{i≠}\text{1}\text{2}\text{K}\text{|(i)X|}\text{|(i)S|}\text{+}\text{|(}\text{1}\text{2}\text{K)X|}\text{|(}\text{1}\text{2}\text{K-1)S|}\text{?1}$

.     

On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

THE EDGE-CHROHATIC NUMBER OF A CIRCULANT

ABSTRACT

The circulant graph C_p > a₁,…, a_k < with 0 > a₁ >…> a_k >(pt1)/2 has p vertices labeled 0,1,…,p-1 and x and y are adjacent if and only if x—y = ± a_i (mod p) for some i. We prove the following regarding the chromatic index of a circulant: if d = gcd (a₁,…, a_k, p), then x' (C_p > a_l,…,a_k) = Δ(C p > a₁,…,a_k) if and only if p/d is even.     

On the average number of records for sequences of not identically distributed random variables

The scheme of n series of independent random variables X ₁₁, X ₂₁, …, X _k1, X ₁₂, X ₂₂, …, X _k2, …, X _1n , X _2n , …, X _kn is considered. Each of these successive series X _1m , X _2m , …, X _km , m = 1, 2, …, n consists of k variables with continuous distribution functions F ₁, F ₂, …, F _k , which are the same for all series. Let N(nk) be the number of upper records of the given nk random variables, and EN(nk) be the corresponding expected value. For EN(nk) exact upper and lower estimates are obtained. Examples are given of the sets of distribution functions for which these estimates are attained.     

On the number of cycles of given length of a free word in several random permutations

Let w ≠ 1 be a free word in the symbols g₁,…, g_k and their inverses (i.e., an element of the free group F_k). For any s₁,…, s_k, in the group s_n of all permutation of n objects, we denote by w(s₁,…,s_k) ? S_n the permutation obtained by replacing g₁,…, g_k with s₁,…, s_k in the expression of w. Let X (s₁,…, s_k) denote the number of cycles of length L of w(s₁,…, s_k). For fixed w and L, we show that X, viewed as a random variable on S_n^k, has (for n →∞) a Poisson-type limit distribution, which can be computed precisely. © 1994 John Wiley & Sons, Inc.     

Analyzing Ek|Er|c queues

In this paper we study a system consisting of c parallel identical servers and a common queue. The service times are Erlang-r distributed and the interarrival times are Erlang-k distributed. The service discipline is first-come first-served. The waiting process may be characterized by (n₋₁, n₀, n₁,…, n_c) where n₋₁ represents the number of remaining arrival stages, n₀ the number of waiting jobs and n_i, i = 1,…, c, the number of remaining service stages for server i. Bertsimas has proved that the equilibrium probability for saturated states (i.e. states with all servers busy) can be written as a linear combination of geometric terms with n₀ as exponent. In the present paper it is shown that the coefficients also have a geometric form with respect to n₋₁, n₁, …, n_c. It is also shown how the factors may be found efficiently. The present paper uses a direct approach for solving the equilibrium equations rather than a generating function approach as Bertsimas does. The direct approach is based on separation of variables and has been inspired by previous work of two of the authors on the shortest queue problem in particular and the two-dimensional random walk more generally. The characterization of the equilibrium probabilities leads to exact expressions for performance measures such as the moments of the queue length and the waiting time, which are useful for numerical computations. Numerical results are presented.     

Self‐converse Mendelsohn designs with block size 4 and 5

A (v, k, λ)‐Mendelsohn design(X, ℬ︁) is called self‐converse if there is an isomorphic mapping ƒ from (X, ℬ︁) to (X, ℬ︁⁻¹), where ℬ︁⁻¹ = {B⁻¹ = 〈x_k, x_k−1,…,x₂, x₁〉: B = 〈x₁, x₂,…,x_k−1, x_k〉 ϵ ℬ︁}. In this paper, we give the existence spectrum for self‐converse (v, 4, 1)– and (v, 5, 1)– Mendelsohn designs. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 411–418, 2000     

Über Folgen,die BezÜglich Eines Mittels Rekurrent Sind

Let X be a convex subset of a finite-dimensional real vector space. A function M: X ^k → X is called a strict mean value, if M(x₁,…, x_k) lies in the convex hull of x₁,…, x_k), but does not coincide with one of its vertices. A sequence (x_n)_{n∈ ?} in X is called M-recursive if x_n+k = M(x_n, x_n+1,…, x_n+k?1) for all n. We prove that for a continuous strict mean value M every M-recursive sequence is convergent. We give a necessary and sufficient condition for a convergent sequence in X to be M-recursive for some continuous strict mean value M, and we characterize its limit by a functional equation. 39 B 72, 39 B 52, 40 A 05.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Mixed ramsey numbers: Chromatic numbers versus graphs

For positive integers n₁, n₂, …, n_I and graphs G_I+1, G_I+2, …, G_k, 1 ≤ / < k, the mixed Ramsey number _χ(n₁, …, n₁, G_I+1, …, G_k) is define as the least positive integer p such that for each factorization K_p = F₁⊕ … ⊕ F_⊕ F_I+1⊕ … ⊕ F_k, it it follows that χ(F_i) ≥ n_i for some i, 1 ? i ? l, or G_i is a subgraph of F_i for some i, l < i ? k. Formulas are presented for maxed Ramsey numbers in which the graphs G_I+1, G_I+2, …, G_k are connected, and in which k = I+1 and G_I+1 is arbitray.     

Handcuffed designs

Handcuffed designs are a particular case of block designs on graphs. A handcuffed design with parameters v, k, λ consists of a system of ordered k-subsets of a v-set, called handcuffed blocks. In a block {A₁, A₂,…, A_k} each element is assumed to be handcuffed to its neighbors and the block contains k ? 1 handcuffed pairs (A₁, A₂), (A₂, A₁), …, (A_k?1, A_k). These pairs are considered unordered. The collection of handcuffed blocks constitutes a handcuffed design if the following are satisfied: (1) each element of the v-set appears amongst the blocks the same number of times (and at most once in a block) and (2) each pair of distinct elements of the v-set are handcuffed in exactly λ of the blocks. If the total number of blocks is b and each element appears in r blocks the following conditions are necessary for the handcuffed design to exist. (1) λv (v ? 1) = (k ? 1)b. (2) rv = kb. In this paper it is shown that the necessary conditions are also sufficient.     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Disjoint skolem sequences and related disjoint structures

A Skolem sequence of order n is a sequence S = (s₁, s₂…, s²ⁿ) of 2n integers satisfying the following conditions: (1) for every k ∈ {1, 2,… n} there exist exactly two elements s_i,S_j such that S_i = S_j = k; (2) If s_i = s_j = k,i < j then j ? i = k. In this article we show the existence of disjoint Skolem, disjoint hooked Skolem, and disjoint near-Skolem sequences. Then we apply these concepts to the existence problems of disjoint cyclic Steiner and Mendelsohn triple systems and the existence of disjoint 1-covering designs. © 1993 John Wiley & Sons, Inc.