Search results for " Bounds"
showing 10 items of 291 documents
A Distribution-Free Two-Sample Equivalence Test Allowing for Tied Observations
1999
A new testing procedure is derived which enables to assess the equivalence of two arbitrary noncontinuous distribution functions from which unrelated samples are taken as the data to be analyzed. The equivalence region is defined to consist of all pairs (F, G) of distribution functions such that for independent X ∼F, Y ∼G the conditional probability of {X > Y} given {X ¬= Y} lies in some short interval around 1/2. The test rejects the null hypothesis of nonequivalence if and only if the standardized distance between the U-statistics estimator of P|X > Y | X ¬= Y] and the center of the equivalence interval (1/2 - e 1 , 1/2 + e 2 ) does not exceed a critical upper bound which has to be comput…
Cotas inferiores para el QAP-Arbol
1985
The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.
Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?
2011
The Adaptive Metropolis (AM) algorithm is based on the symmetric random-walk Metropolis algorithm. The proposal distribution has the following time-dependent covariance matrix at step $n+1$ \[ S_n = Cov(X_1,...,X_n) + \epsilon I, \] that is, the sample covariance matrix of the history of the chain plus a (small) constant $\epsilon>0$ multiple of the identity matrix $I$. The lower bound on the eigenvalues of $S_n$ induced by the factor $\epsilon I$ is theoretically convenient, but practically cumbersome, as a good value for the parameter $\epsilon$ may not always be easy to choose. This article considers variants of the AM algorithm that do not explicitly bound the eigenvalues of $S_n$ away …
SPECTRAL ANALYSIS WITH TAPERED DATA
1983
. A new method based on an upper bound for spectral windows is presented for investigating the cumulants of time series statistics. Using this method two classical results are proved for tapered data. In particular, the asymptotic normality for a class of spectral estimates including estimates for the spectral function and the covariance function is proved under integrability conditions on the spectra using the method of cumulants.
Minimax estimation with additional linear restrictions - a simulation study
1988
Let the parameter vector of the ordinary regression model be constrained by linear equations and in addition known to lie in a given ellipsoid. Provided the weight matrix A of the risk function has rank one, a restricted minimax estimator exists which combines both types of prior information. For general n.n.d. A two estimators as alternatives to the unfeasible exact minimax estimator are developed by minimizing an upper and a lower bound of the maximal risk instead. The simulation study compares the proposed estimators with competing least-squares estimators where remaining unknown parameters are replaced by suitable estimates.
On an approximation problem for stochastic integrals where random time nets do not help
2006
Abstract Given a geometric Brownian motion S = ( S t ) t ∈ [ 0 , T ] and a Borel measurable function g : ( 0 , ∞ ) → R such that g ( S T ) ∈ L 2 , we approximate g ( S T ) - E g ( S T ) by ∑ i = 1 n v i - 1 ( S τ i - S τ i - 1 ) where 0 = τ 0 ⩽ ⋯ ⩽ τ n = T is an increasing sequence of stopping times and the v i - 1 are F τ i - 1 -measurable random variables such that E v i - 1 2 ( S τ i - S τ i - 1 ) 2 ∞ ( ( F t ) t ∈ [ 0 , T ] is the augmentation of the natural filtration of the underlying Brownian motion). In case that g is not almost surely linear, we show that one gets a lower bound for the L 2 -approximation rate of 1 / n if one optimizes over all nets consisting of n + 1 stopping time…
On the gonality and the slope of a fibered surface
2018
Abstract Let f : X → B be a locally non-trivial relatively minimal fibration of curves of genus g ≥ 2 . We obtain a lower bound of the slope λ ( f ) increasing with the gonality of the general fiber of f. In particular, we show that λ ( f ) ≥ 4 provided that f is non-hyperelliptic and g ≥ 16 .
Learning small programs with additional information
1997
This paper was inspired by [FBW 94]. An arbitrary upper bound on the size of some program for the target function suffices for the learning of some program for this function. In [FBW 94] it was discovered that if “learning” is understood as “identification in the limit,” then in some programming languages it is possible to learn a program of size not exceeding the bound, while in some other programming languages this is not possible.
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata
2018
In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
Upper bounds on multiparty communication complexity of shifts
1996
We consider some communication complexity problems which arise when proving lower bounds on the complexity of Boolean functions. In particular, we prove an \(O(\frac{n}{{2\sqrt {\log n} }}\log ^{1/4} n)\)upper bound on 3-party communication complexity of shifts, an O(n e ) upper bound on the multiparty communication complexity of shifts for a polylogarithmic number of parties. These bounds are all significant improvements over ones recently considered “unexpected” by Pudlak [5].