Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

Approximate regular expression pattern matching with concave gap penalties

Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a₁a₂ ... a_M andB=b₁b₂... b_N is a list of ordered pairs, (i₁,j₁), (i₂j₂), ..., (i_t,j_tt) such that i_k < i_k+1 and j_k < j_k+1. In this case the alignmentaligns symbols a_ik and b_jk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log² P)) algorithm for approximate regular expression matching for an arbitrary and any concavew. This work was supported in part by the National Institute of Health under Grant RO1 LM04960.     

Selection and sorting in totally monotone arrays

A two-dimensional arrayA={a[i, j]} is calledtotally monotone if, for alli ₁i ₂ andj ₁j ₂,a[i ₁,j ₁]a[i ₁,j ₂] impliesa[i ₂,j ₁]a[i ₂,j ₂]. Totally monotone arrays were introduced in 1987 by Aggarwal, Klawe, Moran, Shor, and Wilber, who showed that several problems in computational geometry and VLSI river routing could be reduced to the problem of finding a maximum entry in each row of a totally monotone array. In this paper we consider several selection and sorting problems involving totally monotone arrays and give a number of applications of solutions for these problems. In particular, we obtain the following results for anm × n totally monotone arrayA:

Optimal strategies against a liar

We consider the following scenario: There are two individuals, say Q (Questioner) and R (Responder), involved in a search game. Player R chooses a number, say x, from the set S={1,…,M}. Player Q has to find out x by asking questions of type: “which one of the sets A₁,A₂,…,A_q, does x belong to?”, where the sets A₁,…,A_q constitute a partition of S. Player R answers “i” to indicate that the number x belongs to A_i. We are interested in the least number of questions player Q has to ask in order to be always able to correctly guess the number x, provided that R can lie at most e times. The case e=0 obviously reduces to the classical q-ary search, and the necessary number of questions is [log_qM]. The case q=2 and e1 has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary q2. Under the assumption that player R is allowed to lie at most twice throughout the game, we determine the minimum number of questions Q needs to ask in order to successfully search for x in a set of cardinality M=qⁱ, for any i1. As a corollary, we obtain a counterexample to a recently proposed conjecture of Aigner, for the case of an arbitrary number of lies. We also exactly solve the problem when player R is allowed to lie a fixed but otherwise arbitrary number of times e, and M=qⁱ, with i not too large with respect to q. For the general case of arbitrary M, we give fairly tight upper and lower bounds on the number of the necessary questions.     

A unified presentation of some classes of meromorphically multivalent functions

The authors introduce and investigate various properties of a general class

U_k[p,a,β,A,B]

p, k ε N {1, 2, 3,…,}; 0 α < p; β 0

;

−1 A < B 1; 0 < B 1)

,which unifies and extends several (known or new) subclasses of meromorphically multivalent functions. The properties and characteristics of this general class, which are presented here, include growth and distortion theorems; they also involve Hadamard products (or convolution) of functions belonging to the class U_k[p,α,β,A,B].     

Distributions having bases which generate finite dimensional Lie algebras

Let X¹,…, X^k be real analytic vector fields on an n-dimensional manifold M, k < n, which are linearly independent at a point p ε M and which, together with their Lie products at p, span the tangent space TM_p. Then X¹,…, X^k form a local basis for a real analytic k-dimensional distribution x→D^k(x)=span{X¹(x),…,X^k(x)}. We study the question of when D^k admits a basis which generates a nilpotent, or solvable (or finite dimensional) Lie algebra. If this is the case the study of affine control systems, or partial differential operators, described via X¹,…, X^k can often be greatly simplified.     

Compact Recognizers of Episode Sequences

Given two strings X=a₁…a_n and P=b₁…b_m over an alphabet Σ, the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O(n log |Σ|) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log |Σ| character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O(n²) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O(n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O(∑_i=1^mrocc_i·i) or O(n+∑_i=1^mrocc_i·i· log n), depending on whether the alphabet is fixed or arbitrary, where rocc_i is the number of distinct minimal substrings of X having b₁…b_i as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.     

Semigroup generation and stabilization by A-bounded feedback perturbations

Let A be a generator of a strongly continuous semigroup of operators, and assume that C and H are operators such that A + CH generates a strongly continuous semigroup S_H(t) on X. Let λ₀ be a real number in the resolvent set of A, and let ε [−1, 1]. Then there are some fairly unrestrictive conditions under which A+(λ₀ − A)CH(λ₀ − A)⁻ also generates a strongly continuous semigroup S_K(t) on X which has the same exponential growth rate as S_H(t). Given an input operator B, we can use this to identify a class of feedback perturbations K such that A + BK generates a strongly continuous semigroup. We can also use this result to identify classes of feedbacks which can and cannot uniformly stabilize a system. For example, we show that if the control on a cantilever beam in the state space H₀²[0, 1] × L²[0, 1] is a moment force on the free end, then we cannot stabilize the beam with an A^−1/2-bounded feedback, but we can find an A^−1/4-bounded feedback, for any > 0, which does stabilize the beam.     

Truncations of infinite matrices and algebraic series associated with some of grammars

We consider an algebraic system over $\text{R}$[x] of the form X = a₀(x)X^k+ a_k1(x)X+a_k(x), where a₀(x) and a_k(x) are in x$\text{R}$[x] and a_k?1(x) is in x$\text{R}$. Let A be the infinite incidence matrix associated with the algebraic system. Then we prove that the eigenvalues of northwest corner truncations of A are dense in some algebraic curves.Using this we get a result on positive algebraic series. We consider the case that the coefficients of a₁(x)(i = 0,…,k?1, k) are positive. The algebraic series generated by the algebraic system may be viewed as a function in the complex variable x. Then by the above fact we prove that the radius of convergence of the function equals the least positive zero of the modified discriminant of the system.As an application to context free languages we show a procedure for calculating the entropy of some one counter languages. Other applications to Dyck languages and the Lukasiewicz language are also described.     

On Nonnegative matrices generating a finite multiplicative monoid

Square nonnegative matrices with the property that the multiplicative monoid M(A) generated by the matrix A is finite are characterized in several ways. At first, the least general upper bound for the cardinality of M(A) is derived. Then it is shown that any square nonnegative matrix is cogredient to a lower triangular block form with the diagonal consisting of three blocks L, A ₀, and M where L and M are strictly lower triangular, A ₀ has no zero rows or columns, and M(A) is finite if and only if. M(A ₀) is so. Several criteria for, M(A ₀) to be finite are presented. One of the normal forms of A applies very well to the characterization of the nonnegative solutions of each of the matrix equations X ^k = 0, X ^k = 1, X ^k = X, and X ^k = X ^T where k > 1 is an integer. It also leads to a polynomial time algorithm for deciding whether or not M(A) is finite, if the entries of A are nonnegative rationals.     

An alternative solution to the H∞-optimal control problem

In this paper we present an alternative solution to the problem min _{X ε H^n×n∞} |A + BXC|_∞ where A, B, rmand C are rational matrices in H^n×n_∞. The solution circumvents the need to extract the matrix inner factors of B and C, providing a multivariable extension of Sarason's H^∞-interpolation theory [1] to the case of matrix-valued B(s) and C(s). The result has application to the diagonally-scaled optimization problem int |D(A + BXC)D⁻¹|_∞, where the infimum is over D, X εH^n×n_∞, D diagonal.     

Automatic Computation of a Linear Interval Enclosure

Recently, an alternative interval approximation F(X) for enclosing a factorable function f(x) in a given box X has been suggested. The enclosure is in the form of an affine interval function F(X)= a _i X _i +B where only the additive term B is an interval, the coefficients a _i being real numbers. The approximation is applicable to continuously differentiable, continuous and even discontinuous functions.In this paper, a new algorithm for determining the coefficients a _i and the interval B of F(X) is proposed. It is based on the introduction of a specific generalized representation of intervals which permits the computation of the enclosure considered to be fully automated.     

Characterizations of distributions of exponential or geometric type by the integrated lack of memory property and record values

Let be a sequence of i.i.d. random variables, the sequence of its upper record values (i.e. L(0) = 1, L(n) = inf{jX_j>X_L(n−1} for n≥1). Without any assumptions to the support of P^X₁ the equidistribution of X₁ and a record increment X_L(n − X_L(n−1), n ≥ 1 yields X₁ to be either exponentially or geometrically distributed according to whether the additive subgroup generated by the support of P^X₁ is dense or a lattice in . The integrated lack of memory property can easily be reduced to the above problem for the case n = 1. Similarly the independence of X_L(n−1) and X_L(n) − X_L(n−1) for some n>1 characterizes X₁ to have e exponential or a geometric tail provided that the support of P^X₁ is bounded to the left and its right extremity no atom. Hence, if also its left extremity is no atom the independence of X_L(n−1) and X_L(n−1) − X_L(n−1) characterizes X₁ to be exponentially distributed.     

Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes _∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞.     

Simulated annealing type algorithms for multivariate optimization

We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX _k +1 =X _k –a _k (U(X _k ) + _k) +b _k W _k . HereU(·) is a smooth function on a compact subset of ^d , {_k} is a sequence of ^d -valued random variables, {W _k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a _k }, {b _k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), { _k }, {a _k }, and {b _k } thatX _k converges in probability to the set of global minima ofU(·). A careful treatment of howX _k is restricted to a compact set and its effect on convergence is given.Research supported by the Air Force Office of Scientific Research contract 89-0276B, and the Army Research Office contract DAAL03-86-K-0171 (Center for Intelligent Control Systems).     

Parallel solution of recurrences on a tree machine

The recurrencex _o =a _o x _i =a _i+b _i x _i–1,i = 1, 2,...,n–1 requiresO(n) operations on a sequential computer. Elegant parallel solutions exist, however, that reduce the complexity toO(logN) usingNn processors. This paper discusses one such solution, designed for a tree-structured network of processors.A tree structure is ideal for solving recurrences. It takes exactly one sweep up and down the tree to solve any of several classes of recurrences, thus guaranteeing a solution inO(logN) time for a tree withNn leaf nodes. Ifn exceedsN, the algorithm efficiently pipelines the operation and solves the recurrence inO(n/N + logN) time.     

Class of globally stable saturated state feedback regulators

The aim is to find a feedback matrix F for a saturated stale feedback regulator, which guarantees its global asymptotic stability. We consider the discrete-time system with the constrained input described by x_k+1 = Ax_k + Bu_k , where u_k ? Ω R and matrix A is assumed to be critically stable, i.e. there exists some eigenvalues, lambda; _i (A), such that |λ _i (A)| = 1.     

Monoid-labeled transition systems

Given a -complete (semi)lattice , we consider -labeled transition systems as coalgebras of a functor ⁽⁻⁾, associating with a set X the set ^X of all -fuzzy subsets. We describe simulations and bisimulations of -coalgebras to show that L⁽⁻⁾ weakly preserves nonempty kernel pairs iff it weakly preserves nonempty pullbacks iff L is join infinitely distributive (JID).Exchanging for a commutative monoid , we consider the functor ⁽⁻⁾_ω which associates with a set X all finite multisets containing elements of X with multiplicities m M. The corresponding functor weakly preserves nonempty pullbacks along injectives iff 0 is the only invertible element of , and it preserves nonempty kernel pairs iff is refinable, in the sense that two sum representations of the same value, r₁ + … + r_m = c₁ + … + c_n, have a common refinement matrix (m_{(i, j)}) whose k-th row sums to r_k and whose l-th column sums to c_l for any 1≤ k ≤ m and 1 ≤ l ≤ n.     

Elements of small norm in Shanks’ cubic extensions of imaginary quadratic fields

Let be an imaginary quadratic number field with ring of integers Z_k and let k(α) be the cubic extension of k generated by the polynomial f_t(x)=x³−(t−1)x²−(t+2)x−1 with tZ_k. In the present paper we characterize all elements γZ_k[α] with norms satisfying |N_k(α)/k|≤|2t+1| for |t|≥14. This generalizes a corresponding result by Lemmermeyer and Pethő for Shanks’ cubic fields over the rationals.     

Optimal diagonal scaling for infinity-norm optimization

A solution is presented for the previously unsolved diagonally scaled multivariable infinity-norm optimization problem of minimizing D(s)(A(s) + Ψ(s) X(s))D⁻¹(s)_∞ over the set of stable minimum-phase diagonal D(s) and stable X(s). This problem is of central importance in the synthesis of feedback control laws for robust stability and insensitivity in the presence of ‘structured’ plant uncertainty. The result facilitates the design of feedback controllers which optimize the ‘excess stability margin’ [3] (or, equivalently, the ‘structured singular value μ’ [4]) of diagonally perturbed feedback systems.