Asymptotically optimal empirical bayes procedures for selecting good

Let ∏₁,…,∏_k denote k independent populations, where a random observation from population ∏ _i has a uniform distribution over the interval (0,θ _i ) and θ _i is a realization of a random variable having an unknown prior distribution G _i . Population ∏ _i is said to be a good population if θ _i ≥θ₀, where θ₀ is a given, positive number. This paper provides a sequence of empirical Bayes procedures for selecting the good populationsamong ∏₁,…,∏ _k . It is shown that these procedures are asymptotically optimal and that the order of associated convergence rates is O(n^-r/4) for some r, 0<r<2, where n is the number of accumulated past observations

at hand     

Monotonicity of permanents of direct sums of doubly stochastic matrices

Let Ωn be the set of all n × n doubly stochastic matrices, let J_n be the n × n matrix all of whose entries are 1/n and let σ _k (A) denote the sum of the permanent of all k × k submatrices of A. It has been conjectured that if A ε Ω _n and A ≠ J_J then g_A,k (θ) ? σ _k ((1 θ)J_n 1 θA) is strictly increasing on [0,1] for k = 2,3,…,n. We show that if A = A ₁ ⊕ ⊕A_t (t ≥ 2) is an n × n matrix where A_i for i = 1,2, …,t, and if for each i g_Ai,ki (θ) is non-decreasing on [0.1] for k_t = 2,3,…,n_i , then g_A,k (θ) is strictly increasing on [0,1] for k = 2,3,…,n.     

Prime links in some skew-polynomial and skew-laurent rings

Let R be a Noetherian commutative ring and a α₁,…,α_n commuting automorphisms of R. Define T = R[θ₁,…,θ_n;α₁,…,α_n] to be the skew-polynomial ring with θ_ir = α_i(r)θ_i and θ_iθ_j= θ_jθ_i, for all i,j ? (1,…,n) and r ? R, and let S = Rθ₁,θ₁:^-1,…,θ_n:,θ_n;^-1;α₁:,…,α_n] be the corresponding skew-Laurent ring. In this paper we show that S and T satisfy the strong second layer condition and characterize the links between prime ideals in these rings.     

WAVELET ESTIMATION IN NONPARAMETRIC MODEL UNDER MARTINGALE DIFFERENCE ERRORS

§1　IntroductionConsider the following heteroscedastic regression model:Yi =g(xi) +σiei,　1≤i≤n,(1.1)whereσ2i=f(ui) ,(xi,ui) are nonrandom design points,0≤x0 ≤x1 ≤...≤xn=1and0≤u0≤u1 ≤...≤un=1,Yi are the response variables,ei are random errors,and f(·) andg(·) are unknown functions defined on closed interval[0 ,1] .It is well known thatregression model has many applications in practical problems,sothe model (1.1) and its special cases have been studied extensively. For instance,…     

On p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in [1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [4]. In [1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.     

Tridiagonal pairs and the quantum affine algebra {\boldmath U_q({\widehat {sl}}_2)}

Let ${\mathbb K}$ denote an algebraically closed field and let q denote a nonzero scalar in ${\mathbb K}$ that is not a root of unity. Let V denote a vector space over ${\mathbb K}$ with finite positive dimension and let A,A* denote a tridiagonal pair on V. Let θ₀, θ₁,…, θ _d (resp. θ*₀, θ*₁,…, θ* _d ) denote a standard ordering of the eigenvalues of A (resp. A*). We assume there exist nonzero scalars a, a* in ${\mathbb K}$ such that θ _i = aq ^2i?d and θ* _i = a*q ^d?2i for 0 ≤ i ≤ d. We display two irreducible ${\boldmath U_q({\widehat {sl}}_2)}$ -module structures on V and discuss how these are related to the actions of A and A*.     

Constant‐sign solutions for singular systems of Fredholm integral equations

We consider the system of Fredholm integral equations where T>0 is fixed and the nonlinearities H_i(t, u₁, u₂, …, u_n) can be singular at t=0 and u_j=0 where j∈{1, 2, …, n}. Criteria are offered for the existence of constant‐sign solutions, i.e. θ_iu_i(t)≥0 for t∈[0, 1] and 1≤i≤n, where θ_i∈{1,?1} is fixed. We also include an example to illustrate the usefulness of the results obtained. Copyright © 2010 John Wiley & Sons, Ltd.     

Cyclic Bernoulli polling

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to move from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilityp _i , or moves on to the next queue (w.p. 1 —p _i ) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all parameterized cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thep _i 's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {p _i } _i ^N =1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalp _i 's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp ₁=1 is the best strategy, and derive conditions under which it is optimal to havep ₁ < 1.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant Number 3321190.     

Large deviation estimates for a conditional probability distribution. Applications to random interaction Gibbs measures

Summary Let (X _i ,Y _i ) ^d , be independent identically distributed random variables with arbitrary distribution. We show that, for almost every(Y _i ) _i , the conditional law of the empirical field given(Y _i ) _i satisfies to large deviation inequalities. This applies to the study of Gibbs measures with random interaction, in the case of some mean-field models as well as of short range summable interaction. We show that the pressure is nonrandom, and is given by a variational formula. These random Gibbs measures have the same large deviation rate, which does not depend on the particular realization of the interaction; their local behaviour is described in terms of conditional probabilities given the interaction of solutions to the variational formula.     

Quasi-monotone mappings on θn-continua

A continuous function f from a continuum X onto a continuum Y is quasi-monotone if, for every subcontinuum M of Y with nonvoid interior, f^-1(M) has a finite number of components each of which is mapped onto M by f. A θ_n-continuum is one that no subcontinuum separates into more than n components. It is known that if f is quasi-monotone and X is a θ₁-continuum, then Y is a θ₁-continuum or a θ₂-continuum that is irreducible between two points. Examples are given to show that this cannot be generalized to a θ_n-continuum and n + 1 points for any n >1, but it is proved that if f is quasi-monotone and X is a θ_n-continuum, then Y is a θ_n-continuum or a θ_n+1-continuum that is the union of n + 2 continua H,S₁,S₂,…,S_n+1, whe for each i, S_i is the closure of a component of Y H, S_i is irreducible from some point P_i to H, and H is irreducible about its boundary. Some theorems and examples are given concerning the preservation of decomposition elements by a quasi-monotone map defined on a θ_n-continuum that admits a monotone, upper-semicontinuous decomposition onto a finite graph.     

An asymptotic minimax risk bound for estimation of a linear functional relationship

We consider estimation of the parameter B in a multivariate linear functional relationship X_i=ξ_i+ξ_1i, Y_i=Bξ_i+ξ_2i, i=1,…,n, where the errors (ζ_1i^′, ζ_2i^′) are independent standard normal and (ξ_i, i ) is a sequence of unknown nonrandom vectors (incidental parameters). If there are no substantial a priori restrictions on the infinite sequence of incidental parameters then asymptotically the model is nonparametric but does not fit into common settings presupposing a parameter from a metric function space. A special result of the local asymptotic minimax type for the m.1.e. of B is proved. The accuracy of the normal approximation for the m.l.e. of order n^−1/2 is also established.     

A TWO-STAGE SEMI-HYBRID FLOWSHOP PROBLEM IN GRAPHICS PROCESSING

In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.     

Optimal transmission of “television type” gaussian signals through a noiseless feedback channel

Using the methods and results of the theory of conditionally Gaussian filtering of stochastic processes and fields, an optimal scheme of “television type” signal transmission through a noiseless feedback channel is constructed under the usual power conditions, the signals being evolutionary Gaussian fields θ={θ_t(x)),tε[0,T),xεDεRⁿ . Explicit representations for optimal coding and decoding functionals, which are optimal in the sense of a special square criterion, and the expression for the error of signal reproduction are given.     

Estimation robuste pour des lois à symétrie elliptique à matrice de covariance inconnue

Let X,V₁,…,V_n−1 be n random vectors in ℝ^p with joint density of the form ƒ((X - θ)′ Σ⁻¹(X - θ) + Σ_j=1ⁿ⁻¹ V_jⁱ Σ⁻¹V_j), where both θ and Σ are unknown. We consider the problem of estimating θ under the invariant loss (δ - θ)′ Σ⁻¹ (δ - θ) and propose estimators which dominate the usual estimator δ₀(X) = X simultaneously for the entire class of such distributions. The proof involves the development of expressions which are analogous to unbiased estimators of risk and which in fact reduce to unbiased estimators of risk in the Gaussian case. The method is applicable to the case where Σ is structured.     

Improved bounds for sampling contingency tables

We study the problem of sampling contingency tables (nonnegative integer matrices with specified row and column sums) uniformly at random. We give an algorithm which runs in polynomial time provided that the row sums r_i and the column sums c_j satisfy r_i = Ω(n^3/2m log m), and c_j = Ω(m^3/2n log n). This algorithm is based on a reduction to continuous sampling from a convex set. The same approach was taken by Dyer, Kannan, and Mount in previous work. However, the algorithm we present is simpler and has weaker requirements on the row and column sums. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 135–146, 2002     

Multiparameter acoustic imaging in the born approximation

Samples of biological tissue are modelled as inhomogeneous fluids with density ?(X) and sound speed c(x) at point x. The samples are contained in the sphere |x| ? δ and it is assumed that ?(x) ? ?₀ = 1 and c(x) ? c₀ = 1 for |x| ? δ, and |γ_n(x)| ? 1 and |?γ?(x)| ? 1 where γ?(x) = ?(x) ? 1 and γ_n(x) = c^?2(x) ? 1. The samples are insonified by plane pulses s(x · θ₀ – t) where x = |θ₀| = 1 and the scattered pulse is shown to have the form |x|^?1 e_s(|x| – t, θ, θ₀) in the far field, where x = |x| θ. The response e_s(τ, θ, θ₀) is measurable. The goal of the work is to construct the sample parameters γn and γ? from e_s(τ, θ, θ₀) for suitable choiches of s, θ and θ₀. In the limiting case of constant density: γ?(x)_? 0 it is shown that Where δ represents the Dirac δ and S² is the unit sphere |θ| = 1. Analogous formulas, based on two sets of measurements, are derived for the case of variable c(x) and ?(x).     

Two generalizations of Dykstra’s cyclic projections algorithm

Dykstra’s cyclic projections algorithm allows one to compute best approximations to any pointx in a Hilbert space from the intersectionC = ⋂ _l ^r C _i of a finite number of closed convex setsC _i , by reducing it to a sequence of best approximation problems from theindividual setsC _i . Here we present two generalizations of this algorithm. First we allow the number of setsC _i to beinfinite rather than finite; secondly, we allow arandom, rather than cyclic, ordering of the setsC _i . This author was supported by NSF Grant DMS-9303705.     

Optimal maps for the multidimensional Monge-Kantorovich problem

Let μ₁,…, μ_N be Borel probability measures on ℝ^d. Denote by Γ(μ₁,…, μ_N) the set of all N-tuples T=(T₁,…, T_N) such that T_i:ℝ^d ↔ ℝ^d (i = 1,…, N) are Borel-measurable and satisfy μ₁ = μ_i[V] for all Borel V ⊂ ℝ^d. The multidimensional Monge-Kantorovich problem investigated in this paper consists of finding S=(S₁,…, S_N) ∈ Γ(μ₁,…, μ_N) minimizing over the set Γ(μ₁, ···, μ_N). We study the case where the μ_i's have finite second moments and vanish on (d - 1)-rectifiable sets. We prove existence and uniqueness of optimal maps S when we impose that S₁( x ) ≡ x and give an explicit form of the maps S_i. The result is obtained by variational methods and to the best of our knowledge is the first available in the literature in this generality. As a consequence, we obtain uniqueness and characterization of an optimal measure for the multidimensional Kantorovich problem. © 1998 John Wiley & Sons, Inc.     

Bose-Mesner Algebras Associated with Four-Weight Spin Models

It is known that for each matrix W _i and it's transpose ^t W _i in any four-weight spin model (X, W ₁, W ₂, W ₃, W ₄; D), there is attached the Bose-Mesner algebra of an association scheme, which we call Nomura algebra. They are denoted by N(W _i ) and N( ^t W _i ) = N′(W _i ) respectively. H. Guo and T. Huang showed that some of them coincide with a self-dual Bose-Mesner algebra, that is, N(W ₁) = N′(W ₁) = N(W ₃) = N′(W ₃) holds. In this paper we show that all of them coincide, that is, N(W _i ), N′(W _i ), i=1, 2, 3, 4, are the same self-dual Bose-Mesner algebra. Received: June 17, 1999 Final version received: Januray 17, 2000     

An Erd s–Ko–Rado Theorem for Direct Products

Letn_i, k_ibe positive integers,i=1, ..., d,satisfyingn_i≥2k_i.LetX₁, ..., X_dbe pairwise disjoint sets with |X_i| =n_i.Let be the family of those (k₁+···+k_d)-element sets which have exactlyk_ielements inX_i, I=1,..., d.It is shown that if is an intersecting family then | |/| |≤max_ik_i/n_i,and this is best possible. The proof is algebraic, although in thed=2 case a combinatorial argument is presented as well.