Optimal training sample allocation and asymptotic expansions for error rates in discriminant analysis

The sample-based rule obtained from Bayes classification rule by replacing the unknown parameters by ML estimates from a stratified training sample is used for the classification of a random observationX into one ofL populations. The asymptotic expansions in terms of the inverses of the training sample sizes for cross-validation, apparent and plug-in error rates are found. These are used to compare estimation methods of the error rate for a wide range of regular distributions as probability models for considered populations. The optimal training sample allocation minimizing the asymptotic expected error regret is found in the cases of widely applicable, positively skewed distributions (Rayleigh and Maxwell distributions). These probability models for populations are often met in ecology and biology. The results indicate that equal training sample sizes for each populations sometimes are not optimal, even when prior probabilities of populations are equal.     

Separation and probability of correct classification among two or more distributions

A function on theK-fold product of a set in normed vector space will be called a separation measurement if, for any collection ofK points, the function is bounded below and above, respectively, by maximum and total distance between pairs of points in the collection. Separation measurements are relavent toK-sample hypothesis testing and also to discrimination amongK classes, and several examples are given. In particular, ordinaryL ₁ distance between integrable functions can be generalized to a non-pairwise separation measurement for densitiesf ₁,f ₂,...,f _K inL ₁[μ]; and this separation is a linear transform of the optimal discriminant's probability of correct classification. This research was supported by grant A8044 from the National Research Council of Canada.     

Optimal balanced 27 fractional factorial designs of resolutionV,withN≦42

Summary In this paper, we present a class of fractional factorial designs of the 2⁷ series, which are of resolutionV. Such designs allow the estimation of the general mean, the main effects and the two factors interactions (29 parameters in all for the 2⁷ factorial) assuming that the higher order effects are negligible. For every value ofN (the number of runs) such that 29≦N≦42, we give a resolutionV design that is optimal (with respect to the trace criterion) within the subclass of balanced designs. Also, for convenience of analysis, we present for each design, the covariance matrix of the estimates of the various parameters. As a by product, we establish many interesting combinatorial theorems concerning balanced arrays of strength four (which are generalizations of orthogonal arrays of strength four, and also of balanced incomplete block designs with block sizes not necessarily equal).     

Underlying graph and total length of optimal realizations of variable distance matrices

The general problem is to investigate, for acceptable values ofx, the optimal graph realization of a matrixD(x) obtained from a given tree-realizable distance matrixD as follows: we partition the index set ofD into two convex subsetsH andK, we subtractx from all entriesd _hk andd _kh whereh H andk K and we leave all other entries unchanged. We describe the optimal realization of the matrixD(x) and the behaviour of the total length of the optimal realization as a function ofx. This work was supported by the National Science Foundation Grant DMS-8401686 and by the PSC/CUNY Research Award Program.     

Classification for Certain Simple Real Rank ZeroC*-Algebras

In this paper aK-theoretic classification is given of the simple real rank zeroC*-algebras that can be expressed as inductive limits of sequences of finite direct sums of matrix algebras over finite connected graphs (possibly with dimension drop). This class ofC*-algebras provides torsionK₁. The special case that the graphs are intervals is due to Elliott.     

The absolute maximum payoff in differential games and optimal control

This paper deals with a differential game or optimal control problem in which the payoff is the maximum (or minimum), during play, of some scalar functionK of the statex. This unconventional payoff has many practical applications. By defining certain auxiliary games for a significant class of problems, one can show how to solve the general case where more than one maximum ofk(t)=K[x(t)] occurs under optimal play. For a subclass of such problems, it is found thatclosed optimal solutions can exist on certain surfaces in the playing space. As the playing interval becomes indefinitely long, the open optimal trajectories converge to (or diverge from) such surfaces. In particular, for two-dimensional problems of this subclass, the closed optimal trajectories are periodic and called periodic barriers. They are analogous to limit cycles in uncontrolled nonlinear systems.The writer is indebted to Dr. R. Isaacs for many stimulating conversations in connection with this study.     

Homotopy after tensoring with uniformly hyperfiniteC*-algebras

The paper is devoted to the homotopy classification ofC*-algebras of continuous functions on a finite CW-complex with values in a UHF-algebra. The relevant invariants are based on (connective)K-theory.     

Über Bewertungen,welche unter einer reduktiven Gruppe invariant sind

Summary LetG be a reductive group defined over an algebraically closed fieldk and letX be aG-variety. In this paper we studyG-invariant valuationsv of the fieldK of rational functions onX. These objects are fundamental for the theory of equivariant completions ofX. LetB be a Borel subgroup andU the unipotent radical ofB. It is proved thatv is uniquely determined by its restriction toK ^U . Then we study the set of invariant valuations having some fixed restrictionv ₀, toK ^B . Ifv ₀ is geometric (i.e., induced by a prime divisor) then this set is a polyhedron in some vector space. In characteristic zero we prove that this polyhedron is a simplicial cone and in fact the fundamental domain of finite reflection groupW ^X . Thus, the classification of invariant valuations is almost reduced to the classification of valuations ofK ^B .

Unterstützt durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.     

Iwasawa invariants of imaginary quadratic fields

LetK be an imaginary quadratic field andp an odd prime which splits inK. We study the Iwasawa invariants for ℤ _p -extensions ofK. This is motivated in part by a recent result of Sands. The main result is the following. Assumep does not divide the class number ofK. LetK _∞ be a ℤ _p -extension ofK. SupposeK _∞ is not totally ramified at the primes abovep. Then the μ-invariant forK _∞/K vanishes. We also show that if μ=0 for all ℤ _p -extensions ofK, then the λ-invariant is bounded asK _∞ runs through all such extensions.     

The average number of normals through a point in a convex body and a related Euler-type identity

Anormal to a convex bodyK at a pointx in the boundary ofK is a ray with endpoint atx, perpendicular to support planeH ofK atx, and contained in the halfspace bounded byH that containsK. This work establishes bounds on the average number ofnormals through a point inK forK a polytope and forK with sufficiently smooth boundary. The integrals used to establish these bounds lead to an Euler-type relation.     

Classification of a screened data into one of two normal populations perturbed by a screening scheme

In normal classification analysis, there may be cases where the population distributions are perturbed by a screening scheme. This paper considers a new classification method for screened data that is obtained from the perturbed normal distributions. Properties of each population distribution is considered and the best region for classifying the screened data is obtained. These developments yield yet another optimal rule for the classification. The rule is studied from several aspects such as a linear approximation, error rates, and estimation of the rule using the EM algorithm. Relationships among these aspects as well as investigation of the rule’s performance are also considered. The screened classification ideas are illustrated in detail using numerical examples.     

On the existence of mandatory representation designs with block sizes 3 and k

A mandatory representation design MR[ν,K] is a pairwise balanced design on ν points with block sizes from K in which for each k ∈ K there is a block in the design of size k. Mendelsohn and Rees [4] investigated the existence of MR[ν,K]s, where 3 ∈ K. In this report we consider additional necessary conditions, where K = {3,k}. These conditions are proved to be sufficient for 4 ≤ k ≤ 50 with one genuine exception. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 122–131, 2000     

Generalized frobenius groups. II

A pair (G, K) in whichG is a finite group andK a normal nontrivial proper subgroup ofG is said to be an F2-pair (a Frobenius type pair) if |C _G (x)|=|C _G/K (xK)| for allx∈G\K. A theorem of Camina asserts that in this case eitherK orG/K is ap-group or elseG is a Frobenius group with Frobenius kernelK. The structure ofG will be described here under certain assumptions on the Sylowp-subgroups ofG. This author’s research was partially supported by the Technion V.P.R. fund — E.L.J. Bishop research fund. This author’s research was partially supported by the MPI fund.     

Construction of supersaturated design with large number of factors by the complementary design method

Supersaturated designs (SSDs) have been widely used in factor screening experiments. The present paper aims to prove that the maximal balanced designs are a kind of special optimal SSDs under the E(f _NOD) criterion. We also propose a new method, called the complementary design method, for constructing E(f _NOD) optimal SSDs. The basic principle of this method is that for any existing E(f _NOD) optimal SSD whose E(fNOD) value reaches its lower bound, its complementary design in the corresponding maximal balanced design is also E(f _NOD) optimal. This method applies to both symmetrical and asymmetrical (mixed-level) cases. It provides a convenient and efficient way to construct many new designs with relatively large numbers of factors. Some newly constructed designs are given as examples.     

Multiplicity formulas for finite dimensional and generalized principal series representations

The article presents two results. (1) Let a be a reductive Lie algebra over ℂ and let b be a reductive subalgebra of a. The first result gives the formula for multiplicity with which a finite dimensional irreducible representation of b appears in a given finite dimensional irreducible representation of a in a general situation. This generalizes a known theorem due to Kostant in a special case. (2) LetG be a connected real semisimple Lie group andK a maximal compact subgroup ofG. The second result is a formula for multiplicity with which an irreducible representation ofK occurs in a generalized representation ofG arising not necessarily from fundamental Cartan subgroup ofG. This generalizes a result due to Enright and Wallach in a fundamental case.     

Differential rings and ore extensions: Brown-McCoy rings

We consider here a ringK, a derivationD ofK and the differential polynomial ringR=K[X;D]. The ringK is said to be a Brown-McCoy ring if the prime radical coincides with the Brown-McCoy radical in every homomorphic image ofK. AD-Brown-McCoy ring is defined in a similar way. We prove the following conditions are equivalent: (i)K is aD-Brown-McCoy ring; (ii)R is a Brown-McCoy ring and for every maximal idealM ofR,K/(MνK) is aD-simple ring with 1. In addition, we give some applications and examples on the study of the transfer of the property of being a Brown-McCoy ring betweenK andR. Further, we study the relation between the prime and theD-prime ideals of a differential intermediate extension of a liberal extension. This paper was supported by a fellowship awarded by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Brazil.     

On Hajnal's triangle-free game

We investigate the triangle-free game proposed by András Hajnal. Starting with the empty graph onn points, two players alternatingly pick edges. The loser is the player who is forced to select an edge which completes a triangle. We determine the winner in a version of the game with the additional rule that the chosen edges must always give a connected subgraph ofK _n . Some other versions are also investigated.     

The connectivity of the block-intersection graphs of designs

It is shown that the vertex connectivity of the block-intersection graph of a balanced incomplete block design,BIBD (v, k, 1), is equal to its minimum degree. A similar statement is proved for the edge connectivity of the block-intersection graph of a pairwise balanced design,PBD (v, K, 1). A partial result on the vertex connectivity of these graphs is also given. Minimal vertex and edge cuts for the corresponding graphs are characterized.Research supported in part by a B.C. Science Council G.R.E.A.T. Scholarship.Research supported in part by an NSERC Postdoctoral Fellowship.     

The frattini subgroup of the absolute Galois group of a local field

LetK be a local field,T the maximal tamely ramified extension ofK, F the fixed field inK _sof the Frattini subgroup ofG(K), andJ the compositum of all minimal Galois extensions ofK containingT. The main result of the paper is thatF=J. IfK is a global field andK _solv is the maximal prosolvable extension ofK, then the Frattini group of % MathType!End!2!1!(K _solv/K) is trivial. Partially supported by a grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.