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 .     

An estimate on the convergence of MKZ–Bézier operators

The pointwise approximation properties of the MKZ–Bézier operators M_n,α(f,x) for α≥1 have been studied in [X.M. Zeng, Rates of approximation of bounded variation functions by two generalized Meyer–König–Zeller type operators, Comput. Math. Appl. 39 (2000) 1–13]. The aim of this paper is to study the pointwise approximation of the operators M_n,α(f,x) for the other case 0<α<1. By means of some new estimate techniques and a result of Guo and Qi [S. Guo, Q. Qi, The moments for the Meyer–König and Zeller operators, Appl. Math. Lett. 20 (2007) 719–722], we establish an estimate formula on the rate of convergence of the operators M_n,α(f,x) for the case 0<α<1.     

Nonlinear eigenvalue problems for quasilinear systems

The paper deals with the existence of positive solutions for the quasilinear system (Φ(u'))' + λh(t)f(u) = 0,0 < t < 1 with the boundary condition u(0) = u(1) = 0. The vector-valued function Φ is defined by Φ(u) = (q(t)(p(t)u₁), …, q(t)(p(t)u_n)), where u = (u₁, …, u_n), andcovers the two important cases (u) = u and (u) = up > 1, h(t) = diag[h₁(t), …, h_n(t)] and f(u) = (f¹(u), …, fⁿ (u)). Assume that fⁱ and h_i are nonnegative continuous. For u = (u₁, …, u_n), let

, f₀ = maxf¹₀, …, fⁿ₀ and f_∞ = maxf¹_∞, …, fⁿ_∞. We prove that the boundary value problem has a positive solution, for certain finite intervals of λ, if one of f₀ and f_∞ is large enough and the other one is small enough. Our methods employ fixed-point theorem in a cone.     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).     

Asymptotic and oscillatory behavior of solutions of general nonlinear difference equations of second order

The asymptotic and oscillatory behavior of solutions of some general second-order nonlinear difference equations of the form

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=0 nZ,

is studied. Oscillation criteria for their solutions, when “p_n” is of constant sign, are established. Results are also presented for the damped-forced equation

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=e_n nZ.

Examples are inserted in the text for illustrative purposes.     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

Limiting optimal discounted-cost control of a class of time-varying stochastic systems

We consider a class of time-varying -valued control models, and with possibly unbounded costs. The processes evolve according to the system equation x_n+1=G_n(x_n,a_n)+ξ_n ( ), where {ξ_n} are i.i.d. random vectors and {G_n} a sequence of known functions converging to some function G_∞. Under suitable hypotheses, we show the existence of an α-discount optimal policy for the limiting system x_n+1=G_∞(x_n,a_n)+ξ_n.     

Worst-case identification in ℓ2: linear and nonlinear algorithms

We consider worst-case identification in the ℓ₂ norm. Given an unknown system h ε ℓ₁ one wishes to choose bounded inputs u ε ℓ∞ such that given finitely many corrupted output measurements {y(k): 0 ≤ k}of Y = h*u + η, where η is noise, assumed small, one can construct an approximation g with g - h₂ → 0 as η∞ → 0 and n → ∞. It is shown that inputs can be chosen such that to identify a sequence of length n with an ℓ₂ error of O(η∞) one requires only O(n) measurements. A numerical example is inclu     

On Parallel Integer Merging

The problem of merging two sorted arrays A = (a₁, a₂, ..., a_n1) and B = (b₁, b₂, ..., b_n2) is considered. For input elements that are drawn from a domain of integers [1...s] we present an algorithm that runs in O(log log log s) time using n/log log log s CREW PRAM processors (optimal speed-up) and O(ns^ε) space, where n = n₁ + n₂. For input elements that are drawn from a domain of integers [1...n] we present a second algorithm that runs in O(α(n)) time (where α(n) is the inverse of Ackermann′s function) using n/α(n) CREW PRAM processors and linear space. This second algorithm is non-uniform; however, it can be made uniform at a price of a certain loss of speed, or by using a CRCW PRAM.     

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n³) square submatrices ofTEXTin optimalO(n²) space. We identify 4ⁿ⁻¹families of indices forTEXT, each containing ∏ⁿ_i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n² log n) time andO(n²) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al.(in“Proceedings, Fourth Symposium on Theory of Computing,” pp. 125–136) for strings and matrices.     

On the Power of Multiple Reads in a Chip

A chip algorithm is called r-multilective if it reads its input bits r times. In this paper we relate the r-bound communication complexity of a language L and the area requirement for an r-multilective chip algorithm of a related language . More specifically Improving known lower bounds on the r-bound communication complexity of certain languages, we obtain several hierarchies of r-multilective languages depending on the parameter r. For example, if 0 < r < s, then there are constants 0 < c, c′ such that for infinitely many n there is a language L_n {0, 1}ⁿ such that there is an s-multilective algorithm recognizing L_n using area at most c log n and any r-multilective algoerithm recognizing L_n requires area at least c′n/log n. Similar results have been known only for s = 2 and r = 1 and have been open in other cases.     

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.     

Fully Scalable Fault-Tolerant Simulations for BSP and CGM

In this paper we consider general simulations of algorithms designed for fully operational BSP and CGM machines on machines with faulty processors. The BSP (or CGM) machine is a parallel multicomputer consisting of p processors for which a memory of n words is evenly distributed and each processor can send and receive at most h messages in a superstep. The faults are deterministic (i.e., worst-case distributions of faults are considered) and static (i.e., they do not change in the course of computation). We assume that a constant fraction of processors are faulty.  We present two fault-tolerant simulation techniques for BSP and CGM:  1. A deterministic simulation that achieves O(1) slowdown for local computations and O((log_h p)²) slowdown for communications per superstep, provided that a preprocessing is done that requires O((log_h p)²) supersteps and linear (in h) computation per processor in each superstep.  2. A randomized simulation that achieves O(1) slowdown for local computations and O(log_h p) slowdown for communications per superstep with high probability, after the same (deterministic) preprocessing as above.  Our results are fully scalable over all values of p from Θ(1) to Θ(n). Furthermore, our results imply that if pn for 0<<1 and h=Θ((n/p)^δ) for 0<δ1 (which hold in almost all practical BSP and CGM computations), algorithms can be made resilient to a constant fraction of processor faults without any asymptotic slowdown.     

Non-full-rank causal approximations of full-rank multivariate stationary processes with rational spectrum

Let Y = (Y_n)_{n ε ζ} be a q-variate wide-sense stationary process with full-rank rational spectral density. We characterize the q-variate stationary processes , causally subordinated to Y, whose spectral densities have rank p < q almost everywhere, and for which is minimum.     

Computing a Context-Free Grammar-Generating Series

The parallel complexity of computing context-free grammar generating series is investigated. It is known that this problem is in DIV, but in terms of n^σ rather than n, where n is the index of the desired coefficient and σ is the grammar size. A new method is presented which is in DIV in terms of 2^2O(σ)·n. Evidence is provided that any direct application of elimination theory to this problem leads to a space and time resource factor that is nearly exponential in grammar size.     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

Approximate fixed point sequence for a finite family of asymptotically pseudocontractive mappings

Let E be a real Banach space and K be a nonempty, closed, convex, and bounded subset of E. Let T_i:K→K, i=1,2,…,N, be N uniformly L-Lipschitzian, uniformly asymptotically regular with sequences {ε_n}, and asymptotically pseudocontractive mappings with sequences , where {ε_n} and , i=1,2,…,N, satisfy certain mild conditions. Let a sequence {x_n} be generated from x₁K by

for all integers n1, where T_n=T_n(modN), {u_n} be a sequence in K, and {λ_n}, {θ_n} and {μ_n} are three real sequences in [0,1] satisfying appropriate conditions; then x_n−T_lx_n→0 as n→∞ for each l{1,2,…,N}.     

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.     

Strong convergence theorems for a new iterative method of -strictly pseudo-contractive mappings in Hilbert spaces

In this paper, we introduce a new iterative method of a k-strictly pseudo-contractive mapping for some 0≤k<1 and prove that the sequence {x_n} converges strongly to a fixed point of T, which solves a variational inequality related to the linear operator A. Our results have extended and improved the corresponding results of Y.J. Cho, S.M. Kang and X. Qin [Some results on k-strictly pseudo-contractive mappings in Hilbert spaces, Nonlinear Anal. 70 (2008) 1956–1964], and many others.